Split-radix FFT algorithm


The split-radix FFT is a fast Fourier transform algorithm for computing the discrete Fourier transform, and was first described in an initially little-appreciated paper by R. Yavne and subsequently rediscovered simultaneously by various authors in 1984. In particular, split radix is a variant of the Cooley–Tukey FFT algorithm that uses a blend of radices 2 and 4: it recursively expresses a DFT of length N in terms of one smaller DFT of length N/2 and two smaller DFTs of length N/4.
The split-radix FFT, along with its variations, long had the distinction of achieving the lowest published arithmetic operation count to compute a DFT of power-of-two sizes N. The arithmetic count of the original split-radix algorithm was improved upon in 2004, but it turns out that one can still achieve the new lowest count by a modification of split radix. Although the number of arithmetic operations is not the sole factor in determining the time required to compute a DFT on a computer, the question of the minimum possible count is of longstanding theoretical interest.
The split-radix algorithm can only be applied when N is a multiple of 4, but since it breaks a DFT into smaller DFTs it can be combined with any other FFT algorithm as desired.

Split-radix decomposition

Recall that the DFT is defined by the formula:
where is an integer ranging from to and denotes the primitive root of unity:
and thus:.
The split-radix algorithm works by expressing this summation in terms of three smaller summations.
First, a summation over the even indices. Second, a summation over the odd indices broken into two pieces: and, according to whether the index is 1 or 3 modulo 4. Here, denotes an index that runs from 0 to. The resulting summations look like:
where we have used the fact that. These three sums correspond to portions of radix-2 and radix-4 Cooley–Tukey steps, respectively.
These smaller summations are now exactly DFTs of length N/2 and N/4, which can be performed recursively and then recombined.
More specifically, let denote the result of the DFT of length N/2, and let and denote the results of the DFTs of length N/4. Then the output is simply:
This, however, performs unnecessary calculations, since turn out to share many calculations with. In particular, if we add N/4 to k, the size-N/4 DFTs are not changed, while the size-N/2 DFT is unchanged if we add N/2 to k. So, the only things that change are the and terms, known as twiddle factors. Here, we use the identities:
to finally arrive at:
which gives all of the outputs if we let range from to in the above four expressions.
Notice that these expressions are arranged so that we need to combine the various DFT outputs by pairs of additions and subtractions, which are known as butterflies. In order to obtain the minimal operation count for this algorithm, one needs to take into account special cases for and for ; see, e.g. Sorensen et al.. Multiplications by and are ordinarily counted as free.
This decomposition is performed recursively when N is a power of two. The base cases of the recursion are N=1, where the DFT is just a copy, and N=2, where the DFT is an addition and a subtraction.
These considerations result in a count: real additions and multiplications, for N>1 a power of two. This count assumes that, for odd powers of 2, the leftover factor of 2 is handled directly by the DFT definition, or equivalently by a radix-2 Cooley–Tukey FFT step.