3 Implementation

  The radix-2 and radix-4 algorithms implemented for this project are decimation-in-frequency and in-place, requiring only two C ``double'' types for each of N input sequence indices but forcing a bit reversal on the output frequency sequence (radix-4 has a base 4 digit reversal.) Implementation of the radix-2 algorithm is considered first, radix-4 is a natural extension thereof.

Equation 4 can be re-written as(6):

 

$$X[k_1 + 2 k_2] = \sum_{n_2 = 0}^{N/2 -1} G[n_2 + (N/2) k_1] W_{N/2}^{k_2 n_2}$$ (5)

Where the the center calculation for G[n₂ + (N/2) k₁] is the 2-point DFT ``butterfly'' shown in (7):

 

G[n₂ + (N/2) k₁] = (x[n₂] + (-1)^k₁ x[N/2 + n₂]) W_N^{k₁ n₂} (6)

This result can be expanded with the knowledge from (3) that k₁ 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₂ + (N/2) k₁] 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₂ + (N/4) k₁] that form a four point DFT butterfly (9):

 

$$G[n_2 + (N/4) k_1] = ( x[n_2] + (-j)^{k_1} x[\frac{N}{4} + n... ...ac{N}{2} + n_2] + (j)^{k_1}x[\frac{3}{4}N + n_2]) W_N^{k_1 n_2}$$ (7)

Which, with k₁ = 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₂(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!