FFT algoritms
in [DSP]
|
Prev: Scilab and DSP
Next: Separating Harmonic Spectra
From: Ron N. on 24 Nov 2007 13:30 On Nov 24, 7:14 am, "Martin Blume" <mbl...(a)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
From: Ron N. on 24 Nov 2007 14:13 On Nov 24, 10:30 am, "Ron N." <rhnlo...(a)yahoo.com> wrote: > On Nov 24, 7:14 am, "Martin Blume" <mbl...(a)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
From: Richard Owlett on 24 Nov 2007 14:13 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.
From: Ron N. on 24 Nov 2007 14:20 On Nov 24, 11:13 am, Richard Owlett <rowl...(a)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
From: Ron N. on 24 Nov 2007 15:42
> > "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 |