AN2768 Freescale Semiconductor / Motorola, AN2768 Datasheet - Page 15

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

3.4 Post-Transpose Data Organization
The 128 complex data are divided into eight groups, each with 16 complex numbers, as shown in Figure 13.
Simultaneous butterfly operations are performed in stages within groups and between groups to reach the final FTT
results.
3.5 Parallel Butterfly Operations
An FFT with 128-point input data is composed of seven stages of butterfly operations. In the first four stages, 16
data samples from the same group are used in the butterfly computation. No data exchange is necessary between
different groups. However, in stage 5, data exchange between groups is needed. For example, G1 data and G2 data
form butterflies in stage 5. The butterfly span increases as the number of stages increases. In stage 7, G1 data work
with G5 data to complete butterflies of the final stage.
If we partition the data of the 8-point DIT FFT into groups of 2, stage 1 of this particular FFT needs data only from
its own group, and stage 2 requires data with increased distance—that is, from G1 and G3 or G2 and G4. The last
stage of this FFT requires data with a distance of half the FFT length, as shown in Figure 14.
The first half of the 128-point input data is independent of the second half of the data until stage 7 of the FFT.
Taking this into consideration, as well as the number of registers available in RCs for the FFT computations, we
divide the 128-point FFT into three steps. In the first step, G1–G4 are register-resident while the first six stages of
their butterfly computations are performed. Then the intermediate results from the first six stages of G1–G4 data
are sent to the frame buffer for temporary storage. In the second step, G5–G8 are moved into the RC registers to
perform the first six stages of the butterfly operations and the intermediate results from these groups stay in the RC.
In the last step, the partial results of G5–G8 in RC the registers are paired with those of G1–G4 in the frame buffer
to form the butterflies of stage 7 and complete the 128-point FFT.
Freescale Semiconductor
Cell 0
Cell 1
Cell 2
Cell 3
Cell 4
Cell 5
Cell 6
Cell 7
G1
Implementation of a 128-Point FFT on the MRC6011 Device, Rev. 0
Figure 13. Data Partitioned into Groups for Parallel Butterflies
112
104
120
64
32
96
16
80
48
72
40
24
88
56
0
8
G2
100
116
108
124
68
36
20
84
52
12
76
44
28
92
60
4
G3
114
106
122
66
34
98
18
82
50
10
74
42
26
90
58
2
G4
102
118
110
126
70
38
22
86
54
14
78
46
30
94
62
6
G5
113
105
121
65
33
97
17
81
49
73
41
25
89
57
1
9
G6
101
117
109
125
69
37
21
85
53
13
77
45
29
93
61
The FFT on the MRC6011 Device
5
G7
115
107
123
67
35
99
19
83
51
11
75
43
27
91
59
3
G8
103
119
111
127
71
39
23
87
55
15
79
47
31
95
63
7
15