Path: utzoo!attcan!uunet!husc6!bloom-beacon!apple!vsi1!wyse!mips!sultra!dtynan
From: dtynan@sultra.UUCP (Der Tynan)
Newsgroups: comp.arch
Subject: Re: Leading zero and pop count
Summary: FFT's have multiple sizes.
Message-ID: <2671@sultra.UUCP>
Date: 22 Nov 88 00:32:04 GMT
References: <10882@hall.cray.com> <3300039@m.cs.uiuc.edu>
Organization: Tynan Computers, Sunnyvale, CA
Lines: 30

In article <3300039@m.cs.uiuc.edu>, wsmith@m.cs.uiuc.edu writes:
> 
> >One thing that is difficult to do in software (counter examples are welcomed
> >please!) and easy to do in hardware is to reverse a bit stream.
> 
> What exactly to you mean by bit stream?   If you mean a single word, it is
> very easy.  If it is more than a word the same trick may be used on a larger
> scale:  (This is actually Pete Madany's code on loan.)
> 
> The 256 byte array, table,  begins { 0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0 ... }
> 
> Bill Smith

The original author was talking about bit-reversal within a word.  The classic
example of this, is the addressing problem in a Fast Fourier Transform.  The
address bits must be reversed, during the last iteration.  The problem is not
so much the reversal (as shown by your table), but the fact that it is
dependant on the transform size.  For example, a 64-pt FFT must be bit-reversed
in six bits.  Your table can be used for this, but the result must be shifted
twice.  In real architectures, the bit-reversal can be anywhere from six to
twenty-one bits.  Thus, the table approach won't work.  TI has a barrel shifter
which does this (to sixteen bits -- the partnumber escapes me) bit-reversal,
which goes to prove the original point, that it can be done in hardware easier
than software.
						- Der
-- 
	dtynan@zorba.Tynan.COM  (Dermot Tynan @ Tynan Computers)
	{apple,mips,pyramid,uunet}!Tynan.COM!dtynan

 ---  If the Law is for the People, then why do we need Lawyers? ---