FFT Programs for Prime Lengths

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
  • 3 point FFT - fft3.m, cap3.m
  • 5 point FFT - fft5.m, cap5.m
  • 7 point FFT - fft7.m, cap7.m
  • 11 point FFT - fft11.m, cap11.m
  • 13 point FFT - fft13.m, cap13.m
  • 17 point FFT - fft17.m, cap17.m
  • 19 point FFT - fft19.m, cap19.m
  • 29 point FFT - fft29.m, cap29.m
  • 31 point FFT - fft31.m, cap31.m
  • 37 point FFT - fft37.m, cap37.m
  • 41 point FFT - fft41.m, cap41.m
  • 43 point FFT - fft43.m, cap43.m
  • 61 point FFT - fft61.m, cap61.m
  • 71 point FFT - fft71.m, cap71.m
  • 73 point FFT - fft73.m, cap73.m
  • 109 point FFT - fft109.m, cap109.m
  • 113 point FFT - fft113.m, cap113.m
  • 127 point FFT - fft127.m, cap127.m
  • More available.

• Required subroutines:
  • Reduction operations
    • RED.m
    • KRED.m
    • tRED.m
    • tKRED.m

  • 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.

Download the programs individually.

Please direct comments and questions to I. W. Selesnick (selesi@ece.rice.edu).