Complex 16-bit radix-4 FFT

UM0304

12/19

4

Complex 16-bit radix-4 FFT

4.1

Description

The DFT X[k] of a complex sequence x[n] of length N is calculated by:

X[k] = S n=0 N-1 x[n]*exp(-j2pnk/N) for k=0, 1,2 0.N-1

A direct calculation of N complex values of X[k] will require 4N2 multiplications and 4N(N-1)

additions given the trigonometric function values. For example, if N=128, 65536

multiplications and 65024 additions are required.

In this report, a radix-4 FFT algorithm is implemented. More details about FFT algorithms

including radix-4 are found in references [3] [4] and [5].

4.2

Algorithm

The algorithm works as follows:

Block 1: Bit reverse

Copy the data from the input buffer to the output buffer in bit-reversed order. It is an integer

between 0 and N-1, with binary representation as shown, for the bit reversal of k, we will

write. So we perform the equivalent of the following loop:

int k, khat, bit;

for (k=0, khat=0; k<N; k++) {

X[khat]=x[k];

for (bit=N/2; (khat & bit)!=0; bit >>=1) khat ^= bit;

khat ^= bit; /* finish incrementing khat */

}

The bit loop inside increments khat as a bit reversed number. If the input buffers and output

buffers are equal (X=x), more care needs to be taken to do the action in place, but it can be

performed faster as fewer elements need to be moved. Putting the elements in bit reversed

order has the effect of grouping together all the Ys and Zs of the previous subsection so no

further rearrangement needs to be done.