AN2768 Freescale Semiconductor / Motorola, AN2768 Datasheet - Page 3

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

Equation 3 demonstrates the decimation in time principle and is derived from the Equation 1, with the help of the
symmetry and periodicity properties.
DIF algorithms decompose the sequence of DFT coefficients X[k] into successively smaller sub-sequences.
Figure 3 illustrates the decimation process in the discrete frequency sequence of eight. Alternatively, the N-point
DFT can be represented in terms of successively smaller sequences with N/2 frequency samples. Figure 3
illustrates the decimation process for a discrete frequency of eight.
Freescale Semiconductor
x[0]
x[2]
x[4]
x[6]
x[1]
x[3]
x[5]
x[7]
Figure 2. Decimation in Time of an (N/2)-Point DFT into Two (N/4)-Point DFT (N = 8)
Figure 1. Decimation in Time of an N-Point DFT into Two (N/2)-Point DFT (N = 8)
X
Implementation of a 128-Point FFT on the MRC6011 Device, Rev. 0
[
k
N/2-Point DFT
N/2-Point DFT
]
=
=
x[0]
x[4]
x[2]
x[6]
G
(
N
∑
r
[
/
=
k
) 2
0
]
−
1
+
x
W
2 [
N
r
k
]
H
W
[
N
rk
k
2 /
],
+
W
N/4-Point
N/4-Point
G[0]
G[1]
G[2]
G[3]
H[0]
H[1]
H[2]
H[3]
N
DFT
DFT
k
(
N
∑
r
/
=
) 2
0
k
−
x
1
=
2 [
0
r
1 ,
+
,...,
] 1
W
N
N
rk
−
2 /
. 1
Basics of the Fast Fourier Transform
Equation 3
W
W
W
W
W
W
W
W
N
N
N
N
N
N
0
1
2
3
4
5
N
N
6
7
X[4]
X[7]
X[0]
X[1]
X[2]
X[3]
X[5]
X[6]
3