FFT Algorithms
Provided below are Matlab programs to illustrate the algorithm described in Automatic Generation of Prime Length FFT Programs (.ps.gz or .pdf), (Abstract), IEEE Transactions on Signal Processing, 44(1):14-24, Jan 1996.
The short length (N=3,5,7) ffts are given just for completeness. See the book by Blahut or Nussbaumer, for example, for straightline code for these and some other lengths lengths.
"capn.m" is a file of constants and permutations for "fftn.m"
* List of FFT programs
o 3 point FFT - fft3.m, cap3.m
o 5 point FFT - fft5.m, cap5.m
o 7 point FFT - fft7.m, cap7.m
o 11 point FFT - fft11.m, cap11.m
o 13 point FFT - fft13.m, cap13.m
o 17 point FFT - fft17.m, cap17.m
o 19 point FFT - fft19.m, cap19.m
o 29 point FFT - fft29.m, cap29.m
o 31 point FFT - fft31.m, cap31.m
o 37 point FFT - fft37.m, cap37.m
o 41 point FFT - fft41.m, cap41.m
o 43 point FFT - fft43.m, cap43.m
o 61 point FFT - fft61.m, cap61.m
o 71 point FFT - fft71.m, cap71.m
o 73 point FFT - fft73.m, cap73.m
o 109 point FFT - fft109.m, cap109.m
o 113 point FFT - fft113.m, cap113.m
o 127 point FFT - fft127.m, cap127.m
o More available.
* Required subroutines:
o Reduction operations
+ RED.m
+ KRED.m
+ tRED.m
+ tKRED.m
o Small linear convolution operations
+ D2.m
+ D2t.m
+ ID2I.m
+ ID2tI.m
+ D3.m
+ D3t.m
+ ID3I.m
+ ID3tI.m
Download all programs above as a tar file. Unpack the tar file with the UNIX command `tar' (e.g., `tar xvf fftprogs.tar'). Doing so will create a directory called `primffts' containing the programs listed above.
Please direct comments and questions to I. W. Selesnick (selesi@ece.rice.edu).
Authors: Ivan Selesnick, Sidney BurrusPublication: Automatic Generation of Prime Length FFT Programs
Copyright ©2009, DSP Group, Rice University