AN2768 Freescale Semiconductor / Motorola, AN2768 Datasheet - Page 4

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

Basics of the Fast Fourier Transform
Similar to DIT, the DIF principle is illustrated in the following equations, also originating from Equation 1.
1.2 Radix-2 and Radix-4
The radix-2 FFT algorithm breaks the DFT calculation down into several 2-point DFTs, each consisting of a
multiply-and-accumulate (MAC) operation called a bufferfly, as shown in Figure 4.
4
X[0]
X[1]
X[2]
X[3]
X[5]
X[6]
X[4]
x[7]
Figure 3. Decimation in Frequency of an N-Point DFT into Two (N/2)-Point DFT (N = 8)
X
2 [
r
X
+
2 [
] 1
r
x[k
x[k
]
=
Implementation of a 128-Point FFT on the MRC6011 Device, Rev. 0
=
1
2
(
]
]
N
(
∑
N
n
/
∑
=
n
) 2
/
=
0
) 2
0
−
(
1
−
(
x
W
1
x
[
[
n
N
r
n
]
]
−
+
x
x
[
[
n
Figure 4. Radix-2 Butterfly
n
+
+
(
N
N
2 /
2 /
])
)])
W
–1
–1
–1
–1
W
N
g[0]
g[1]
g[2]
g[3]
rn
N
h[0]
h[1]
h[2]
h[3]
n
2 /
W
,
r
N
nr
2 /
=
,
W
W
W
W
0
–1
r
1 ,
N
N
N
N
0
1
2
3
=
,...,
0
1 ,
(
,...,
N
N/2-Point DFT
N/2-Point DFT
/
(
) 2
N
−
/
) 2
. 1
−
G[k
G[k
. 1
1
2
]
]
Freescale Semiconductor
Equation 4
Equation 5
x[0]
x[2]
x[4]
x[6]
x[1]
x[3]
x[5]
x[7]