Split-radix FFT algorithm

The split-radix FFT algorithm is an fast Fourier transform (FFT) algorithm, first described by Yavne (1968) and rediscovered simultaneously by various authors in 1984, for computing the discrete Fourier transform (DFT). 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, and its variations, have the distinction of achieving the lowest published arithmetic operation count (total exact number of required real additions and multiplications, sometimes called the "arithmetic complexity") to compute a DFT of power-of-two sizes N. Although the number of arithmetic operations is not the sole factor (or even necessarily the dominant 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. (No strict lower bound is currently known.)

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:

$X_{k}=\sum _{n=0}^{N-1}x_{n}\omega _{N}^{nk}$

where $k$ is an integer ranging from $0$ to $N-1$ and $\omega _{N}$ denotes the primitive root of unity:

$\omega _{N}=e^{-{\frac {2\pi i}{N}}},$

and thus $\omega _{N}^{N}=1$.

The split-radix algorithm works by expressing this summation in terms of three smaller summations. First, a summation over the even indices $x_{2n_{2}}$. Second, a summation over the odd indices broken into two pieces: $x_{4n_{4}+1}$ and $x_{4n_{4}+3}$, according to whether the index is 1 or 3 modulo 4. Here, $n_{m}$ denotes an index that runs from 0 to $N/m-1$. The resulting summations look like:

$X_{k}=\sum _{n_{2}=0}^{N/2-1}x_{2n_{2}}\omega _{N/2}^{n_{2}k}+\omega _{N}^{k}\sum _{n_{4}=0}^{N/4-1}x_{4n_{4}+1}\omega _{N/4}^{n_{4}k}+\omega _{N}^{3k}\sum _{n_{4}=0}^{N/4-1}x_{4n_{4}+3}\omega _{N/4}^{n_{4}k}$

where we have used the fact that $\omega _{N}^{mnk}=\omega _{N/m}^{nk}$.

However, 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 $U_{k_{2}}$ denote the result of the DFT of length N/2 (for $k_{2}=0,\ldots ,N/2-1$), and let $Z_{k_{4}}$ and $Z'_{k_{4}}$ denote the results of the DFTs of length N/4 (for $k_{4}=0,\ldots ,N/4-1$). Then, for $k<N/4$, the output $X_{k}$ is simply $X_{k}=U_{k}+\omega _{N}^{k}Z_{k}+\omega _{N}^{3k}Z'_{k}$.

What about $k\geq N/4$? If we add N/4 to k, the smaller DFTs are not changed (because they are periodic in k), so the only things that change are the $\omega _{N}^{k}$ and $\omega _{N}^{3k}$ terms, known as "twiddle factors". Here, we use the identities:

$\omega _{N}^{k+N/4}=-i\omega _{N}^{k}$

$\omega _{N}^{3(k+N/4)}=i\omega _{N}^{3k}$

to finally arrive at:

$X_{k}=U_{k}+\left(\omega _{N}^{k}Z_{k}+\omega _{N}^{3k}Z'_{k}\right),$

$X_{k+N/2}=U_{k}+\left(\omega _{N}^{k}Z_{k}+\omega _{N}^{3k}Z'_{k}\right),$

$X_{k+N/4}=U_{k}-i\left(\omega _{N}^{k}Z_{k}-\omega _{N}^{3k}Z'_{k}\right),$

$X_{k+N/4}=U_{k}+i\left(\omega _{N}^{k}Z_{k}-\omega _{N}^{3k}Z'_{k}\right),$

which gives all of the outputs $X_{k}$if we let $k$ range from $0$ to $N/2-1$.

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 $k=0$ (where the twiddle factors are unity) and for $k=N/8$ (where the twiddle factors are $(1\pm i)/{\sqrt {(}}2)$ and can be multiplied more quickly). Multiplications by $\pm 1$ and $\pm i$ are ordinarily counted as free (all negations can be absorbed by converting additions into subtractions or vice versa).

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 $X_{0}=x_{0}$, and N=2, where the DFT is an addition $X_{0}=x_{0}+x_{1}$ and a subtraction $X_{1}=x_{0}-x_{1}$.

These considerations result in a count: $4N\log _{2}N-6N+8$ real additions and multiplications, for N a power of two greater than 1.

References

• R. Yavne, "An economical method for calculating the discrete Fourier

transform," in Proc. AFIPS Fall Joint Computer Conf. 33, 115–125 (1968).

• P. Duhamel and H. Hollmann, "Split-radix FFT algorithm," Electron.

Lett. 20 (1), 14–16 (1984).

• M. Vetterli and H. J. Nussbaumer, "Simple FFT and DCT algorithms

with reduced number of operations," Signal Processing 6 (4), 267–278 (1984).

• J. B. Martens, "Recursive cyclotomic factorization—a new algorithm for

calculating the discrete Fourier transform," IEEE Trans. Acoust., Speech, Signal Processing 32 (4), 750–761 (1984).