AN2768 Freescale Semiconductor / Motorola, AN2768 Datasheet - Page 5

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

Figure 5 shows a radix-4 butterfly.
If the FFT number of points is a power of 2, the successive decomposition results in 2-point butterflies. If the
number of points in an FFT is a power of 4, the FFT can be broken down into several 4-point DFTs. The twiddle
factors of a radix-4 FFT possess the unique property that they belong to the set of
radix-4 FFT requires fewer complex multiplications but more additions than the radix-2 FFT for the same number
of points. The radix-4 FFT is more efficient than the radix-2 FFT, so its hardware implementation is simpler. The
implementation of the radix-4 FFT is beyond the scope of this application note, which focuses on a radix-2
decimation in time implementation.
For an N-point FFT, the FFT algorithm decomposes the DFT into
butterfly computations. Each butterfly takes two complex numbers
computes from them two other numbers,
Where
Figure 6 shows the 2-point butterfly operation.
Freescale Semiconductor
x
x
re
re
W
W
W
W
[k
[k
2q
3q
N
N
N
N
0
q
1
2
] + jx
] + jx
W
G
G
N
r
Implementation of a 128-Point FFT on the MRC6011 Device, Rev. 0
[
im
im
[
k
k
[k
[k
1
2
W
]
]
1
2
]
]
=
=
r
N
x
x
=
re
re
[
[
e
k
k
Figure 6. Radix-2 Butterfly Operation
–
--------------- -
1
1
j2πr
]
]
N
+
+
Figure 5. Radix-4 Butterfly
jx
jx
=
im
im
[
[
k
cos
k
1
1
]
]
+
−
⎛
⎝
2πr
-------- -
W
W
N
–1
N
N
r
r
{
⎞
⎠
{
(x
(x
x
x
–
re
re
re
re
[
[k
[k
[
j
k
k
sin
1
1
2
2
] + jx
] + jx
]
]
⎛
⎝
+
log
+
x
2πr
-------- -
re
N
jx
jx
im
im
[
2
k
im
[k
[k
im
⎞
⎠
N
1
1
1
[
[
]
k
]) +
]) – W
k
stages, each of which consists of N/2
+
2
2
]
]
jx
}
}
W
Basics of the Fast Fourier Transform
im
N
N
r
r
[
k
, 1 {
(x
(x
1
]
re
re
−
and
[k
[k
, 1
2
2
j −
] + jx
] + jx
,
x
re
j
}
[
im
im
k
. Therefore, the
[k
[k
2
]
2
2
])
+
])
jx
Equation 6
Equation 7
Equation 8
im
[
k
2
]
and
5