FFT algoritms
in [DSP]
|
Prev: Scilab and DSP
Next: Separating Harmonic Spectra
From: Richard Owlett on 24 Nov 2007 09:45 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
From: Martin Blume on 24 Nov 2007 10:14 "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
From: Richard Owlett on 24 Nov 2007 12:22 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.
From: Martin Blume on 24 Nov 2007 12:42 "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.
From: Martin Blume on 24 Nov 2007 12:55
"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/ |