Connexions

You are here: Home » Content » Split-radix FFT Algorithms
Content Actions

Split-radix FFT Algorithms

Module by: Douglas L. Jones

Summary: 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-2radix-4
image1.pngimage2.png
Subfigure 1.1
Subfigure 1.2
Figure 1: 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.
image3.pngimage4.png
Subfigure 2.1
Subfigure 2.2
Figure 2: 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 Xk=∑n=0N2-1x2nⅇ-ⅈ2π2nkN+∑n=0N4-1x4n+1ⅇ-ⅈ2π4n+1kN+∑n=0N4-1x4n+3ⅇ-ⅈ2π4n+3kN= DFT N 2 x2n+ W N k DFT N 4 x4n+1 + W N 3 k DFT N 4 x4n+3 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 (1)
Figure 3 illustrates the resulting split-radix butterfly.
Decimation-in-Time Split-Radix Butterfly
image5.png
Figure 3: 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.
image6.png
Figure 4: 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 ON3log2N O N 3 2 N 43Nlog2N-389N+6+29-1M 4 3 N 2 N 38 9 N 6 2 9 1 M Nlog2N-3N+4 N 2 N 3 N 4
Additions ONlog2N O N 2 N 83Nlog2N-169N+2+29-1M 8 3 N 2 N 16 9 N 2 2 9 1 M 3Nlog2N-3N+4 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 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.
References
  1. P. Duhamel and H. Hollman. (1984, Jan 5). Split-radix FFT algorithms. Electronics Letters, 20, 14-16.
  2. R. Yavne. (1968). An economical method for calculating the discrete Fourier transform. Proc. AFIPS Fall Joint Computer Conf.,, 33, 115-125.
  3. S.G Johnson and M. Frigo. (2006). A modified split-radix FFT with fewer arithmetic operations. IEEE Transactions on Signal Processing, 54,
  4. H.V. Sorensen, M.T. Heideman, and C.S. Burrus. (1986). On computing the split-radix FFT. IEEE Transactions on Signal Processing, 34(1), 152-156.
  5. G. Bruun. (1978, February). Z-Transform DFT Filters and FFTs. IEEE Transactions on Signal Processing, 26, 56-63.

Comments, questions, feedback, criticisms?

Send feedback