Prime Factor FFT

Typically, people implement the Fast Fourier Transform for powers of 2. Also, most common algorithms give a bit-reversed output, so an extra shuffling pass is needed to get the values into the correct order.

A less well-known FFT algorithm is the prime-factor algorithm (PFA). Instead of powers of 2, the transform size is a product of several relatively prime small numbers. Compared to a radix-2 FFT, the prime-factor FFT has a couple of advantages:

Each butterfly contains all factors needed for the transform; there are no twiddle factors, as used in a radix-2 FFT.

With proper indexing of the butterflies, it is possible to implement an in-place, in-order version of the transform. That is, the transformed values replace the input values in memory, and the output values are in naturaly frequency order when the input values are in natural time order. When implementing the transform in a general-purpose computer, these features can simplify the operation and allow the transform to be done faster than a radix-2 FFT.

The in-place, in-order feature of the PFA was first described by Dr. C. S. Burrus (see references in my paper). His published approach used an indexing scheme that had to be hand-coded for each composite transform size. My contribution was the development of a simple way to compute the indexing and implement it using a 2-level indirect indexing method. Although originally implemented in Fortran, the method should be relatively easy to port to a CPU or DSP that supports indirect addressing. I am not aware of anyone who has actually implemented it on a DSP, though.

The paper citation is

J. H. Rothweiler, "Implementation of the In-Order Prime Factor Transform for Variable Sizes," IEEE Trans. on Acoustics, Speech, and Signal Processing, pp. 105-107, Feb. 1982.

I currently don't have a copy online.