Page 358 - DSP Integrated Circuits

7.11 FFT Processor, Cont. 343

To determine possible Af-memory assignments, we partition the graph into N
parts by assigning the vertices (variables) with exclusion branches to different
memories. There is only one way to partition this graph into two such parts.
Hence, there is only one possible memory assignment, except for a trivial inter-
change of the memories.
Note that the new exclusion branches in the four-point exclusion graph com-
pared to the two-point exclusion graph are due to the first stage. This becomes
even more clear in the exclusion graph of the eight-point FFT illustrated in
Figure 7.86. The effect of adding a first stage is that an exclusion branch will occur
between the corresponding indices in the two smaller FFTs.
Generally, there will be an exclusion branch between vertices corresponding
to the values with index i and i + N/2 for 0 < i < N/2.
For a two-point FFT, the variables must be assigned to different memories, as
shown in Figures 7.84 and 7.87. This must also hold for each of the two-point FFTs
in a four-point FFT, but the corresponding variables in the two-point FFTs must also
be stored in different memories. For example, x(Q) in the first two-point FFT in
Figure 7.87 is stored in RAMo- Hence, x(2) must be stored in RAMi. This pattern
repeats for larger FFTs as illustrated in Figure 7.87. The two-RAM assignment [15]
can be expressed in terms of the binary representation of i - IL i^i - 13 i% i\ IQ
where L = log2(AT) - 1.

Figure 7.86 An eight-point ST-FFT and exclusion graph for memories