Page 109 - DSP Integrated Circuits

94 Chapter 3 Digital Signal Processing

Program ST_FFT;
const
A
N = 1024, M = 10, Nminusl = 1023; { N = 2 M }
type
Complex = record
re : Double;
im : Double;
end;
C_array : array[0..Nminusl] of Complex;
var
x : C_array;
Stage, Ns, k, kNs, n, p, q : integer;
Wcos, Wsin, TwoPiN, TempRe, Templm : Double;
begin
{ READ INPUT DATA INTO x }
Ns := N;
TwoPiN := 2 * PiTN;
for Stage := 1 to M do
begin
k:=0;
Ns := Ns div 2; {index distance between a dual node pair }
for q := 1 to (N div (2 * Ns)) do
begin
for n := 1 to Ns do
begin
A
p := k * 2 (Stage -1) mod (N div 2);
Wcos := cos(TwoPiN * p);{W to the power of p}
Wsin := -sin(TwoPiN * p);{W = exp(-j2;c/N)}
kNs := k + Ns;
{Butterfly} TempRe := x[k].re - x[kNs].re;
Templm := x[k].im - x[kNs].im;
x[k].re := x[k].re + x[kNs].re;
x[k].im := x[k].im + x[kNs].im;
x[kNs].re := TempRe * Wcos - Templm * Wsin;
x[kNs].im := Templm * Wcos + TempRe * Wsin;
k:=k+l ;
end;
k := k + Ns;
end;
end;
Unscramble; { OUTPUT DATA STORED IN x }
end.

Box 3.6. The Sande-Tukey FFT. Decimation-in-frequency.

Figure 3.26 shows the signal-flow graph for ST-FFT for N = 8. Note that two sig-
nal values are always used to compute what is called a dual node pair. For example,
the dual node pair #(3) and x(7) in Figure 3.26 are used to compute the dual node
pair £i(3) and xi(7). The computation of a dual node pair is independent of all other
computations in the same column. It is therefore unnecessary to use any additional
memory for the intermediate or the final result, except for the N (complex values)