AN2768 Freescale Semiconductor / Motorola, AN2768 Datasheet - Page 2

• 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
1
The DFT is the basis of the fast Fourier transform. The DFT of a finite-length sequence of length N is defined as
follows:
Where
In these two equations, both x[n] and X[k] can be complex, so N complex multiplications and (N –1) complex
additions are required to compute each value of the DFT if we use Equation 1 directly. Computing all N values of
the frequency components requires a total of
improve efficiency in computing the DFT, the properties of symmetry and periodicity of
they are described as follows:
To simplify the notation of the two preceding expressions, we let r=(kn)mod (N) so that the property of symmetry
becomes
twiddle factors in FFT computation, where
1.1 Decimation in Time and Frequency
FFT algorithms decompose the DFT of a time domain sequence of length N into successively smaller DFTs—a
divide and conquer strategy. Among the variety of divide and conquer algorithms are decimation in time (DIT) and
decimation in frequency (DIF). DIT decomposes the time sequence x[n] into successively smaller sub-sequences
until there are only two elements in the sequences for a radix-2 DFT. Figure 1 and Figure 2 show the decimation
process for a time sequence of eight elements.
2
W
Basics of the Fast Fourier Transform
1.
2.
W
N
W
W
N
=
r
+
N
N
e
N
k
kn
[
−
2 /
N
j
=
−
2 (
n
=
π
W
]
/
−
=
N
N
k
W
)
W
(
. The Inverse Discrete Fourier Transform is given by
n
+
N
r
N
Implementation of a 128-Point FFT on the MRC6011 Device, Rev. 0
N
−
kn
and the property of periodicity is
)
=
=
x
W
[
(
X
n
W
N
(
]
[
k
N
k
=
+
kn
N
]
)
)
N
1
=
*
n
(Complex conjugate symmetry)
(Periodicity in n and k)
∑
∑
N
n
N
k
=
=
−
−
0
0
1
1
x
W
X
[
n
[
N
N
k
]
W
]
2
=
W
complex multiplications and N(N –1) complex additions. To
N
kn
e
N
−
−
,
kn
j
k
2
,
π
n
=
/
N
=
0
1 ,
=
0
W
,...,
1 ,
cos(
,...,
N
r
+
N
N
2
N
−
π
=
, 1
−
W
/
. 1
N
N
r
)
. The
−
j
sin(
W
N
r
2
are often referred to as the
π
/
N
)
W
is the
Freescale Semiconductor
N
kn
are exploited, and
N
th
root of unity.
Equation 1
Equation 2