UM0304

Complex 16-bit radix-4 FFT

13/19

Block 2: Kernel

Perform the equivalent of the following loop:

●

denotes complex multiplication

# define pi 3.14159265358

for (n=2; n<=N; n <<= 1) {

w=2*pi/n;

for (m=0; m<N; m+=n) {

for (k=0; k<n/2; k++) {

y=X[m+k];

z=X[m+k+n/2] * exp(-ikw);

X[m+k]=(y+z)/2;

X[m+k+n/2]=(y-z)/2;

}

}

}

After n=2 we have performed N/2 two-element FFTs, positioned at offsets m=0, 2, 4, ... N-2.

After n=4 we have performed N/4 four-element FFTs positioned at offset m=0, 4, 8, … N-4.

After n=N we are left with the answer to the main FFT in the buffer X.

k bN 1 - ... b2

b1

b0

()?= 2

Because each pass of the FFT divides the data by 4 (radix4 passes) there is no bit growth.

Four cases were tested as shown in Table 4.

Table 4.

Bit growth of FFT routine

Case name

Description

Input amplitude

Output bin amplitude

Single sine max neg.

Single sine at 1600; Fs

=25600; 1 complete

waveform in 16

samples;

0x8001

2 bins of 0xC000 (+/-

0x2)

Single sine max pos.

Single sine at 1600; Fs

=25600; 1 complete

waveform in 16

samples;

0x7FFF

2 bins of 0x4000 (+/-

0x2)