Page 303 - DSP Integrated Circuits

288 Chapter 7 DSP System Design

First Alternative
In this and the next section we will investigate two different alternative choices of
order for the computations of the butterflies in the inner loop. Having two concur-
rent butterflies means that we must generate two indices k in parallel: k\ and k%.
In the first alternative, we choose to execute butterflies p andp + N/4 concurrently.
Since two butterfly operations will be performed for each pass through the inner
loop, the range of m is reduced to 0 < m < N/4 and the integers k± and &2 become

The modified program is shown in Box 7.3.

--Fast Fourier Transform - Sande-Tukey, ALTERNATIVE #1
-Filename: FFT_ST1.VHD

architecture beh_STl of ent_FFT is
begin
Main: process(x_in)
variable Ns, Stage, m, kl, k2, klNs, k2Ns, 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/4) - 1) loop
kl := 2 * Ns * (m/Ns) + m mod(Ns);
if (stage = 1) then
k2 := kl + N/4;
else
k2 := kl + N/2;
end if;
p := kl*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)
klNs := kl + Ns;
k2Ns := k2 + Ns;
Butterfly(x_tmp, kl, klNs, Wcos, Wsin); -Concurrent
if (Stage = 1) then
Butterfly(x_tmp, k2, k2Ns, Wsin, -Wcos); -Butterflies
else
Butterfly(x_tmp, k2, k2Ns, Wcos, Wsin);
end if;
end loop; -for loop
end loop; —for loop
Unscramble(x_tmp);
x_ut <= x_tmp; —output signal
end process Main;
end beh_STl;

Box 7.3 Alternative #1