Page 301 - DSP Integrated Circuits

286 Chapter 7 DSP System Design

—Fast Fourier Transform-Sande-Tukey
library ieee;
use ieee.math_real.all;
use work.fft_pck.all;
entity ent_FFT is
port(x_in : in complexArr; x_ut: out complexArr);
end ent_FFT;

architecture beh_ST of ent_FFT is
begin
Main:process(x_in)
variable Ns, Stage, k, kNs, p : integer;
variable Wcos, Wsin : real;
variable x: complexArr;
begin
x := x_in; —copy insignal
Ns := N;
for Stage in 1 to M loop
k:=0;
Ns := Ns/2; —index distance between a dual node pair
for q in 1 to (N /(2*Ns)) loop
for n in 1 to Ns loop
p := k*2**(Stage-l) mod (N/2);
Wcos := cos(TwoPiN*real(p)); ~W to the power of p
Wsin := -sin(TwoPiN*real(p));--W = exp(-j27t/N)
kNs := k + Ns;
Butterfly(x,k,kNs,Wcos,Wsin);
k:=k+l ;
end loop;
k := k + Ns;
end loop;
end loop;
Unscramble(x); --output data
x_ut <= x; —output
end process Main;
end beh_ST;

Box 7.1 Sande-Tukey's FFT

The VHDL description in Box 7.1 is sequential and must be modified into a
description with two parallel butterfly processes in order to meet the perfor-
mance constraints. The original code contains three loops: the Stage loop, the q
loop, and the n loop. The Stage loop makes sure the FFT is computed stage by
stage. The q and n loops are used to compute indices to the variables x(n) in each
stage. Since we want two parallel butterfly processes in each stage, we must
modify the q and n loops. First we note that the index k can be expressed in
terms of q and n: