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

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

 (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: 4 Results Up: Implementation and Comparison of Previous: 2 Theory

Mike Andrews
6/29/1998