FFT algoritms

In "Chapter 12 - The Fast Fourier Transform / FFT Programs" of _The 
Scientist and Engineer's Guide to Digital Signal Processing_
Smith says "There are also FFT routines that completely eliminate the 
bit reversal sorting."

Could someone point me to a description of one, preferably with BASIC or 
FORTRAN sample code.

TIA

"Richard Owlett" schrieb
> In "Chapter 12 - The Fast Fourier Transform / FFT Programs" of
> _The Scientist and Engineer's Guide to Digital Signal Processing_
> Smith says "There are also FFT routines that completely eliminate
> the bit reversal sorting."
>
> Could someone point me to a description of one, preferably
> with BASIC or FORTRAN sample code.
>
Maybe www.nr.com helps. Viewing the book on-line needs a plugin,
which I'm too lazy to install right now, so I don't know if the
answer is in there.

HTH.
Martin

Martin Blume wrote:
> "Richard Owlett" schrieb
> 
>>In "Chapter 12 - The Fast Fourier Transform / FFT Programs" of
>>_The Scientist and Engineer's Guide to Digital Signal Processing_
>>Smith says "There are also FFT routines that completely eliminate
>>the bit reversal sorting."
>>
>>Could someone point me to a description of one, preferably
>>with BASIC or FORTRAN sample code.
>>
> 
> Maybe www.nr.com helps. Viewing the book on-line needs a plugin,
> which I'm too lazy to install right now, so I don't know if the
> answer is in there.
> 
> HTH.
> Martin
> 
> 

Installation repeatedly fails with a "file corrupt" message. I suspect 
that Windows version is dependent on using IE. I'll see if local library 
can get me a hard copy on inter-library loan.

Thanks.

"Richard Owlett" schrieb 
> > 
> > Maybe www.nr.com helps. Viewing the book on-line 
> > needs a plugin, ... 
> Installation repeatedly fails with a "file corrupt" message. 
> I suspect that Windows version is dependent on using IE. 
> I'll see if local library can get me a hard copy on 
> inter-library loan.
> 
You might want to look at the source code first to check whether
they have an algorithm that works without bit reversal sorting.

Regards
Martin

PS: My ancient dead-tree version (from 1987) mentions other 
algorithms (other than bit-reversal) briefly (2 pages), but 
says that these are used for convolution using the FFT and 
that not doing the bit-reversal step doesn't save much time.

"Martin Blume" schrieb
> > In "Chapter 12 - The Fast Fourier Transform / FFT Programs" of
> > _The Scientist and Engineer's Guide to Digital Signal
Processing_
> > Smith says "There are also FFT routines that completely
eliminate
> > the bit reversal sorting."
> >
> > Could someone point me to a description of one, preferably
> > with BASIC or FORTRAN sample code.
> >
Another possible site is:
http://mathworld.wolfram.com/FastFourierTransform.html
(didn't  see any mention at first glance of non-bit-reversal stuff,
but you might follow the links [*])

Regards
Martin

[*] beware of the danger mentioned in http://xkcd.com/214/

On Nov 24, 7:14 am, "Martin Blume" <mbl...@socha.net> wrote:
> "Richard Owlett" schrieb> In "Chapter 12 - The Fast Fourier Transform / FFT Programs" of
> > _The Scientist and Engineer's Guide to Digital Signal Processing_
> > Smith says "There are also FFT routines that completely eliminate
> > the bit reversal sorting."

Why do you need to avoid sorting?

> > Could someone point me to a description of one, preferably
> > with BASIC or FORTRAN sample code.
>
> Maybe www.nr.com helps.

The FFT routine in my copy of Numerical Recipes in Basic
uses a common decimation-in-time (presort) in-place FFT
algorithm with a recurrence formula for the trig/twiddle
factors.

If you don't need to do your FFT in place (using the same
array for input, output and intermediate data), you could try
bit-reversed addressing (perhaps by table look up) instead of
bit-reversed sorting.  You could even hide the fact that you are
doing bit-reversed addressing by using different dimensions of
2d arrays for each layer (essentially hiding each bit of
address arithmetic behind a transposition of 2d coordinates).

I have source code for a simple DIT in-place FFT in Basic
for Chipmunk Basic:
  http://www.nicholson.com/rhn/basic
which is an old-fashioned and fairly generic Basic dialect,
if that would be of any value.




IMHO. YMMV.
--
rhn A.T nicholson d.0.t C-o-M

On Nov 24, 10:30 am, "Ron N." <rhnlo...@yahoo.com> wrote:
> On Nov 24, 7:14 am, "Martin Blume" <mbl...@socha.net> wrote:
>
> > "Richard Owlett" schrieb> In "Chapter 12 - The Fast Fourier Transform / FFT Programs" of
> > > _The Scientist and Engineer's Guide to Digital Signal Processing_
> > > Smith says "There are also FFT routines that completely eliminate
> > > the bit reversal sorting."
>
> Why do you need to avoid sorting?
>
> > > Could someone point me to a description of one, preferably
> > > with BASIC or FORTRAN sample code.
>
> > Maybewww.nr.comhelps.
>
> The FFT routine in my copy of Numerical Recipes in Basic
> uses a common decimation-in-time (presort) in-place FFT
> algorithm with a recurrence formula for the trig/twiddle
> factors.
>
> If you don't need to do your FFT in place (using the same
> array for input, output and intermediate data), you could try
> bit-reversed addressing (perhaps by table look up) instead of
> bit-reversed sorting.  You could even hide the fact that you are
> doing bit-reversed addressing by using different dimensions of
> 2d arrays for each layer (essentially hiding each bit of
> address arithmetic behind a transposition of 2d coordinates).

Another option for hiding some sorting is to do the FFT by
depth-first recursion (setting up the parameters passed can
presort the data).  This might be useful if multiple levels
of caching or local memory are smaller than the data vectors.



> IMHO. YMMV.
> --
> rhn A.T nicholson d.0.t C-o-M

Martin Blume wrote:
> "Richard Owlett" schrieb 
> 
>>>Maybe www.nr.com helps. Viewing the book on-line 
>>>needs a plugin, ... 
>>
>>Installation repeatedly fails with a "file corrupt" message. 
>>I suspect that Windows version is dependent on using IE. 
>>I'll see if local library can get me a hard copy on 
>>inter-library loan.
>>
> 
> You might want to look at the source code first to check whether
> they have an algorithm that works without bit reversal sorting.
> 
> Regards
> Martin
> 
> PS: My ancient dead-tree version (from 1987) mentions other 
> algorithms (other than bit-reversal) briefly (2 pages), but 
> says that these are used for convolution using the FFT and 
> that not doing the bit-reversal step doesn't save much time.
> 

I'm not interested in the computation time but in whether or not I can 
follow what's going on. Eventually I want to experiment with using 
square waves instead of sinusoids as my basis functions. I suspect it 
will be a better model for my situation.

On Nov 24, 11:13 am, Richard Owlett <rowl...@atlascomm.net> wrote:
> Martin Blume wrote:
> > "Richard Owlett" schrieb
>
> >>>Maybewww.nr.comhelps. Viewing the book on-line
> >>>needs a plugin, ...
>
> >>Installation repeatedly fails with a "file corrupt" message.
> >>I suspect that Windows version is dependent on using IE.
> >>I'll see if local library can get me a hard copy on
> >>inter-library loan.
>
> > You might want to look at the source code first to check whether
> > they have an algorithm that works without bit reversal sorting.
>
> > Regards
> > Martin
>
> > PS: My ancient dead-tree version (from 1987) mentions other
> > algorithms (other than bit-reversal) briefly (2 pages), but
> > says that these are used for convolution using the FFT and
> > that not doing the bit-reversal step doesn't save much time.
>
> I'm not interested in the computation time but in whether or not I can
> follow what's going on. Eventually I want to experiment with using
> square waves instead of sinusoids as my basis functions. I suspect it
> will be a better model for my situation.

For experimenting with other basis vectors, you probably
want to stick with the N^2 DFT algorithm.  The N*log(N) FFT
algorithm depends on the fact that sinusoidal basic vectors
have periodicity, symmetry and factorization properties.



IMHO. YMMV.
--
rhn A.T nicholson d.0.t C-o-M

> > "Richard Owlett" schrieb
> I'm not interested in the computation time but in whether or not I can
> follow what's going on. Eventually I want to experiment with using
> square waves instead of sinusoids as my basis functions. I suspect it
> will be a better model for my situation.

For experimenting with other basis vectors, you probably
want to stick with the N^2 DFT algorithm.  The N*log(N) FFT
algorithm depends on the fact that sinusoidal basis vectors
have periodicity, symmetry and factorization properties.

IMHO. YMMV.
--
rhn A.T nicholson d.0.t C-o-M