next up previous
Next: 4 Results Up: Implementation and Comparison of Previous: 2 Theory

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}\end{displaymath} (5)

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):

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

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!

next up previous
Next: 4 Results Up: Implementation and Comparison of Previous: 2 Theory

Mike Andrews