Equation 4 can be re-written as(6):
(5) |
Where the the center calculation for G[n_{2} + (N/2) k_{1}] is the 2-point DFT ``butterfly'' shown in (7):
G[n_{2} + (N/2) k_{1}] = (x[n_{2}] + (-1)^{k1} x[N/2 + n_{2}]) W_{N}^{k1 n2} | (6) |
This result can be expanded with the knowledge from (3) that k_{1} can equal only 0 or 1 (8):
This two-point DFT butterfly is the building block for the radix-2 FFT algorithm. An entire 2^{m} point sequence can be reduced to two-point DFTs upon realization that equation (6) is merely a N/2 point DFT of the sequence G[n_{2} + (N/2) k_{1}] and is subject to a recursive application of the Cooley-Tukey DFT simplification expanded above.
The radix-4 FFT algorithm follows the same development with the exception of the terms in the sequence G[n_{2} + (N/4) k_{1}] that form a four point DFT butterfly (9):
(7) |
Which, with k_{1} = 0 .. 3 is expanded to (10):
Some initial comparisons between radix-2 and radix-4 may be obtained by looking at the number of mathematical operations required for each. My implementation of radix-2 has 8 additions and 4 multiplications per 2-point DFT (due to the twiddle factors) with a total cost times (N/2) log_{2}(N) 2-point stages. For my algorithm (11 and 12):
For my implementation of radix-4, 26 additions per 4 point stage were required, and 4 multiplications due, again, to the twiddle factors. Computations for radix-4 are as follows (13 and 14):
Taking a 1024 point sequence as an example, radix-2 would require 40960 additions and 20480 multiplications. Radix-4 requires 30720 additions and only 5120 multiplications!
Mike Andrews