Mixed radix FFT
Mixed radix Fast Fourier Transform (FFT) with large power-of-2 factors

Abstract:

A graph demonstrating how mixed radix FFTs can be performed using large power-of-2 FFTs and efficient vectorized prime factor FFTs. While the technique is useful for splitting the mixed radix FFT into a power-of-2 FFT and one FFT with no power-of-2 computations, it can be used recursively to implement algorithms whose size has an arbitrary number of factors. The same factorization technique can be used to implement large power-of-2 FFTs that are not supported directly by the DSP library being used.

 

Problem:

Efficiently implement a mixed radix FFT. The size of the FFT is given as N = P*Q where Q contains all of the power-of-2 factors. Use only power-of-2 factor FFTs (as commonly supplied by DSP libraries) and DFTs (matrix multiply) for the non-power-of-2 factor P.

 

Solution:

The mixed radix FFT is based on the factorization of a size-N FFT into two stages. The first stage performs P size-Q FFTs, where Q contains all the powers of 2. The results are multiplied by twiddle factors (point-wise multiplication of results by a complex vector). The second stage performs Q size-P DFTs. The five identity transformations contain three matrix transpose functions requiring the only computation time.

 

In the example graphs, range variables are defined for use in the comments. These range variables are not used for graph instantiation. For further details about their use, see the bracket notation web page.

 

Implementation:

The following graph is the top-level of the solved problem. The source generates a modulated, random complex signal that is used as input for three different FFT implementations. The output displays allow you to compare the signal's frequency spectrum computed by the different implementations.

 

The graph's top branch calculates an FFT using a primitive from the library. It is used as a comparison against the factorized implementation of the FFT. In the center branch the mixed radix FFT is used to show how the same factorization technique can be used to implement a large power-of-2 FFT. The hierarchical function box mr_fft is used in a second instantiation mr_fft_1 with different parameters to implement the FFT where the size of the FFT is factored into two stages. The first stage using power-of-2 FFTs and the second stage not using power-of-2 FFTs.

 

For more details on the implementation, double-click on either the source box or the mr_fft box. box. Since mr_fft and mr_fft_1 are instantiations of the same hierarchical box their contents are identical, only the input parameters are different.

 

The next figures are random samplings of the output from the graph display on scope1 and scope2. This is a quick comparison of the outputs of the branches of the FFT calculations. This is an easy method of seeing if the two functions are performing roughly the same calculations. As you can see, both the single function vx_fft and parallelized mr_fft have the same output.

This is the output of the top two branches in the graph. The "reference" FFT output is the top trace. The factored FFT's output is in the bottom trace.

 

This is the output of the bottom graph branch FFT that contains calculations that are not powers-of-2.

Notice in these displays the scale matches the size of the FFT.

Application Note last updated 3/26/98