The split-radix FFT is a fast Fourier transform (FFT) algorithm for computing the discrete Fourier transform (DFT), and was first described in an initially little-appreciated paper by R. Yavne (1968)[1] and subsequently rediscovered simultaneously by various authors in 1984. (The name "split radix" was coined by two of these reinventors, P. Duhamel and H. Hollmann.) 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 (total exact number of required real additions and multiplications) to compute a DFT of power-of-two sizes N. The arithmetic count of the original split-radix algorithm was improved upon in 2004 (with the initial gains made in unpublished work by J. Van Buskirk via hand optimization for N=64 [2] [3]), but it turns out that one can still achieve the new lowest count by a modification of split radix (Johnson and Frigo, 2007). 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 tight lower bound on the operation count has currently been proven.) 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 = ∑ n = 0 N − 1 x n ω N n k {\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}\omega _{N}^{nk}}
where k {\displaystyle k} is an integer ranging from 0 {\displaystyle 0} to N − 1 {\displaystyle N-1} and ω N {\displaystyle \omega _{N}} denotes the primitive root of unity:
ω N = e − 2 π i N , {\displaystyle \omega _{N}=e^{-{\frac {2\pi i}{N}}},}
and thus: ω N N = 1 {\displaystyle \omega _{N}^{N}=1} . The split-radix algorithm works by expressing this summation in terms of three smaller summations. (Here, we give the "decimation in time" version of the split-radix FFT; the dual decimation in frequency version is essentially just the reverse of these steps.) First, a summation over the even indices x 2 n 2 {\displaystyle x_{2n_{2}}} . Second, a summation over the odd indices broken into two pieces: x 4 n 4 + 1 {\displaystyle x_{4n_{4}+1}} and x 4 n 4 + 3 {\displaystyle x_{4n_{4}+3}} , according to whether the index is 1 or 3 modulo 4. Here, n m {\displaystyle n_{m}} denotes an index that runs from 0 to N / m − 1 {\displaystyle N/m-1} . The resulting summations look like:
… excerpt ends here. Continue reading the full article.
