Split-radix FFT Algorithms 1.5 2004/05/18 09:27:16 GMT-5 2006/11/02 22:05:27.208 US/Central Douglas L. Jones dl-jones@uiuc.edu Douglas L. Jones dl-jones@uiuc.edu Harika Basana ilsai@rice.edu Kyle Evan Clarkson kclarks@rice.edu Bruun FFT split-radix Yavne The split-radix FFT mixes radix-2 and radix-4 decompositions, yielding an algorithm with about one-third fewer multiplies than the radix-2 FFT. The split-radix FFT has lower complexity than the radix-4 or any higher-radix power-of-two FFT. The split-radix algorithm, first clearly described and named by Duhamel and Hollman in 1984, required fewer total multiply and add operations operations than any previous power-of-two algorithm. (Yavne first derived essentially the same algorithm in 1968, but the description was so atypical that the work was largely neglected.) For a time many FFT experts thought it to be optimal in terms of total complexity, but even more efficient variations have more recently been discovered by Johnson and Frigo. The split-radix algorithm can be derived by careful examination of the radix-2 and radix-4 flowgraphs as in Figure 1 below. While in most places the radix-4 algorithm has fewer nontrivial twiddle factors, in some places the radix-2 actually lacks twiddle factors present in the radix-4 structure or those twiddle factors simplify to multiplication by , which actually requires only additions. By mixing radix-2 and radix-4 computations appropriately, an algorithm of lower complexity than either can be derived.

Motivation for split-radix algorithm radix-2 radix-4 See Decimation-in-Time (DIT) Radix-2 FFT and Radix-4 FFT Algorithms for more information on these algorithms.

An alternative derivation notes that radix-2 butterflies of the form shown in Figure 2 can merge twiddle factors from two successive stages to eliminate one-third of them; hence, the split-radix algorithm requires only about two-thirds as many multiplications as a radix-2 FFT.

Note that these two butterflies are equivalent

The split-radix algorithm can also be derived by mixing the radix-2 and radix-4 decompositions. DIT Split-radix derivation X k n N 2 1 0 x 2 n 2 2 n k N n N 4 1 0 x 4 n 1 2 4 n 1 k N n N 4 1 0 x 4 n 3 2 4 n 3 k N DFT N 2 x 2 n W N k DFT N 4 x 4 n 1 W N 3 k DFT N 4 x 4 n 3 Figure 3 illustrates the resulting split-radix butterfly.

Decimation-in-Time Split-Radix Butterfly The split-radix butterfly mixes radix-2 and radix-4 decompositions and is L-shaped

Further decomposition of the half- and quarter-length DFTs yields the full split-radix algorithm. The mix of different-length FFTs in different parts of the flowgraph results in a somewhat irregular algorithm; Sorensen et al. show how to adjust the computation such that the data retains the simpler radix-2 bit-reverse order. A decimation-in-frequency split-radix FFT can be derived analogously.

The split-radix transform has L-shaped butterflies

The multiplicative complexity of the split-radix algorithm is only about two-thirds that of the radix-2 FFT, and is better than the radix-4 FFT or any higher power-of-two radix as well. The additions within the complex twiddle-factor multiplies are similarly reduced, but since the underlying butterfly tree remains the same in all power-of-two algorithms, the butterfly additions remain the same and the overall reduction in additions is much less.Operation Counts Complex M/As Real M/As (4/2) Real M/As (3/3) Multiplies O N 3 2 N 4 3 N 2 N 38 9 N 6 2 9 1 M N 2 N 3 N 4 Additions O N 2 N 8 3 N 2 N 16 9 N 2 2 9 1 M 3 N 2 N 3 N 4 Comments The split-radix algorithm has a somewhat irregular structure. Successful progams have been written (Sorensen) for uni-processor machines, but it may be difficult to efficiently code the split-radix algorithm for vector or multi-processor machines. G. Bruun's algorithm requires only N 2 more operations than the split-radix algorithm and has a regular structure, so it might be better for multi-processor or special-purpose hardware. The execution time of FFT programs generally depends more on compiler- or hardware-friendly software design than on the exact computational complexity. See Efficient FFT Algorithm and Programming Tricks for further pointers and links to good code. P. Duhamel and H. Hollman Split-radix FFT algorithms Electronics Letters 1984 20 14-16 Jan 5 R. Yavne An economical method for calculating the discrete Fourier transform Proc. AFIPS Fall Joint Computer Conf., 1968 33 115-125 S.G Johnson and M. Frigo A modified split-radix FFT with fewer arithmetic operations IEEE Transactions on Signal Processing 2006 54 H.V. Sorensen, M.T. Heideman, and C.S. Burrus On computing the split-radix FFT IEEE Transactions on Signal Processing 1986 34 1 152-156 G. Bruun Z-Transform DFT Filters and FFTs IEEE Transactions on Signal Processing 1978 26 56-63 February