Page 104 - DSP Integrated Circuits

3.16 FFT—The Fast Fourier Transform Algorithm 89

while k < N do
begin
for q := 1 to Ns do
begin
A
p := Digit_Reverse( k/2 Ml);
WCos := cos(TwoPiN * p); {W to the power of p}
WSin := -sin(TwoPiN * p); {W = exp(-j2rc/N)}
kNs := k + Ns;
{Butterfly} TempRe := x[kNs].re * WCos - x[kNs].im * WSin;
Templm := x[kNs].im * WCos + x[kNs].re * WSin;
x[kNs].re := x[k].re - TempRe;
x[kNs].im := x[k].im - Templm;
x[k].re := x[k].re + TempRe;
x[k].im := x[k].im + Templm;
k:=k+l ;
end;
k := k + Ns;
end;
end;
Unscramble; { OUTPUT DATA STORED IN x }
end.

Box 3.3. The Cooley-Tukey FFT. Decimation-in-time

function Digit_Reverse(Digit: Integer): Integer;
var
N, q, NewAddr, Rmbit, OldAddr : Integer;
begin
NewAddr := 0;
OldAddr := Digit;
for q := 1 to M do
begin
Rmbit := OldAddr mod 2;
OldAddr := OldAddr div 2;
if Rmbit = 1 then
NewAddr := NewAddr * 2 + 1
else
NewAddr := NewAddr + NewAddr;
end;
Digit_Reverse := NewAddr;
end;

Box 3.4. Digit reversal

A signal-flow graph for the Cooley-Tukey FFT for N = 8 is shown in Figure
3.23. The arrows represent multiplication with complex coefficients, so-called
twiddle factors, of the form WP, where W = e~J 2n/N and p = an integer.
As just mentioned, the FFT is based on a divide-and-conquer approach. The
AT-point DFT is first divided into two M2-point DFTs. These DFTs are then
divided into four A/74-point DFTs, and so on. The quantity of arithmetic operations
is reduced to O(N\og2(N}).