Page 302 - DSP Integrated Circuits

7.3 FFT Processor, Cont. 287

and introduce two new integers q' and n'. The integers N 8, n', and q can be
expressed in terms of Stage and N:

Note that the binary representations of q' and n' require Stage - 1 and
log2(AO - Stage bits, respectively. Hence, the total number of bits is log2(AT) -1 = 9
bits. We introduce another integer variable, m, with the range 0 < m < N/2 = 512.
The integers q', n', and k can now be written

Thus, the q and n loops can be replaced with a single loop only controlled by
the integer m, as shown in Box 7.2. It is now easy to modify the inner loop so that
it will contain two butterfly operations.

-Fast Fourier Transform—Sande-Tukey-modified
-Filename: FFT_STO.VHD

architecture beh_STO of ent_FFT is
begin
Main: process(x_in)
variable Ns, Stage, m, k, kNs, p : integer;
variable Wcos, Wsin : real;
variable x_tmp : complexArr;
begin
x_tmp := x_in; —copy input signal
Ns := N;
for Stage in 1 to M loop
Ns := Ns/2; —index distance between a dual node pair
for m in 0 to ((N/2) - 1) loop
k := 2 * Ns * (m/Ns) + m mod(Ns); - Integer division
p := k*2**(Stage - 1) mod(N/2);
Wcos := cos(TwoPiN*real(p)); -W to the power of p
Wsin := -sin(TwoPiN*real(p)); -W = exp(-j2pi/N)
kNs := k + Ns;
Butterfly(x_tmp, k, kNs, Wcos, Wsin);
end loop; —for loop
end loop;~for loop
Unscramble(x_tmp);
x_ut <= x_tmp; —output signal
end process Main;
end beh_STO;

Box 7.2 Modified Sande-Tukey's FFT