Page 298 - DSP Integrated Circuits

7.3 FFT Processor, Cont. 283

frequency of 32 MHz, i.e. twice the I/O data rate. The time required for the FFT
then becomes

and the minimum required clock frequency for the PEs is

The throughput becomes

7.3.2 Second Design Iteration
Note that both the original FFT program and the description using communicat-
ing processes are sequential descriptions. Execution of the statements (operations)
in the Pascal program is determined by the ordering of the statements, while exe-
cution of the processes is controlled by the availability of valid inputs. The follow-
ing design iteration therefore aims to modify the original sequential algorithm
into a parallel description that can be mapped efficiently onto the hardware
resources. We must modify the original program so that two butterfly operations
can be executed concurrently. We must also compute two coefficients WP concur-
rently. There are many possible ways to do this. Let us therefore first consider a
smaller problem.
Figure 7.4 shows the signal-flow graph for a 16-point Sande-Tukey's FFT
where the butterfly operation has been chosen as the basic operation. There are
M = log2(AT) stages, excluding the unscrambling stage, with N/2 butterfly opera-
tions each. The coefficients (i.e., the twiddle factors) in the two parts are the same.
The relation between the coefficients for the butterflies in rows p and p + N/4
in the first stage of the FFT is

Thus, the twiddle factor for one of the butterfly PEs can be obtained from the
twiddle factor of the corresponding butterfly PE by simply changing the sign and
interchanging the real and imaginary parts. In Chapter 11 we will show that these
modifications can be implemented with an insignificant amount of hardware. We
will therefore partition the FFT to have two concurrent butterfly processes while
exploiting the fact that one W^-process is sufficient. In general, only one process-
ing element is required to generate the twiddle factors.
We begin by rewriting the original Pascal code for the ST-FFT using VHDL.
The new representation is shown in the Box 7.1.