Equation 4 can be re-written as(6):
Where the the center calculation for G[n2 + (N/2) k1] is the 2-point DFT ``butterfly'' shown in (7):
|G[n2 + (N/2) k1] = (x[n2] + (-1)k1 x[N/2 + n2]) WNk1 n2||(6)|
This result can be expanded with the knowledge from (3) that k1 can equal only 0 or 1 (8):
This two-point DFT butterfly is the building block for the radix-2 FFT algorithm. An entire 2m 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[n2 + (N/2) k1] 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[n2 + (N/4) k1] that form a four point DFT butterfly (9):
Which, with k1 = 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) log2(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!