AN2768 Freescale Semiconductor / Motorola, AN2768 Datasheet - Page 18

• Manufacturer Part Number: AN2768
• Description: Implementation of a 128-Point FFT on the MRC6011 Device
• Manufacturer: Freescale Semiconductor / Motorola

The FFT on the MRC6011 Device
As indicated in the code segment of Example 3, the outputs of the butterflies go into R8, R9, R4, R0 of all 16 cells
of the RC array, which are addressed as R8{*,*}. Stage 1 butterfly operations are formed within individual cells.
As shown in Figure 14, the butterfly span increases with each stage. To continue with the 16 parallel butterfly
computations as in stage 1 for subsequent stages, data regrouping is needed. Data regrouping is handled via register
exchanges on the RC array.
3.5.2 Data Regrouping
From stage 1 to stage 6, data regrouping is required at the end of each stage because of the increased butterfly
spans. Data regrouping changes the original butterfly data flow as the intermediate nodes are regrouped. The
change is not a problem if the first four stages of the butterfly operations are regrouped since butterflies are formed
from within the groups. It is not a problem either when the group boundary is crossed to form the butterflies for
stages 5 through 7 since all groups perform the same exchanges. Figure 16 shows an example of data regrouping
for stage 2 of Group 1 data. The output nodes are stored in registers R8, R9, R0, and R4. If no regrouping occurred
for this data, the butterfly operations would have been performed across the cell boundary, which is not efficient on
an RC array. The data samples used in a particular computation (in general) are better aligned column-wise for
efficient computation. Data regrouping simplifies the next butterfly operation. Data regrouping for stage 2 swaps
data items with neighboring cells to transform inter-cell butterflies to intra-cell butterflies.
18
Stage 1 Butterfly
Operations
Stage 1 Butterfly
Operations
G1
G2
Cell →
R4{0,*}
R0{0,*}
R5{0,*}
R1{0,*}
R4{0,*}
R0{0,*}
R5{0,*}
R1{0,*}
Figure 15. Sixteen Butterfly Operations in Parallel for the Group 1 and Group 2 Data
X[ 0]r
X[ 0]i
X[ 64]r
X[ 4]r
X[ 4]i
X[ 68]r
X[ 68]i
1
Implementation of a 128-Point FFT on the MRC6011 Device, Rev. 0
X[ 32]r
X[ 32]i
X[ 96]r
X[ 96]i
X[ 36]r
X[ 36]i
X[ 100]r
X[ 100]i
2
X[ 16]r
X[ 16]i
X[ 80]r
X[ 80]i
X[ 20]r
X[ 20]i
X[ 84]r
X[ 84]i
3
X[ 48]r
X[ 48]i
X[ 112]r
X[ 112]i
X[ 52]r
X[ 52]i
X[ 116]r
X[ 116]i
4
X[ 8]r
X[ 8]i
X[ 72]r
X[ 72]i
X[ 12]r
X[ 12]i
X[ 76]r
X[ 76]i
5
X[ 40]r
X[ 40]i
X[ 104]r
X[ 104]i
X[ 44]r
X[ 44]i
X[ 108]r
X[ 108]i
6
X[ 24]r
X[ 24]i
X[ 88]r
X[ 88]i
X[ 28]r
X[ 28]i
X[ 92]r
X[ 92]i
7
Freescale Semiconductor
X[ 56]r
X[ 56]i
X[ 120]r
X[ 60]r
X[ 60]i
X[ 124]r
8
G[ ] Nodes
G[ ] Nodes