Digital Signal Processing Reference
In-Depth Information
EXAMPLE 12.12
The decomposition-in-time method of calculating the FFT
The decomposition-in-time (DIT) method of the FFT will be used to compute the DFT of the
discrete sequence listed in Table 12.3:
x[n] = [1, 2, 3, 4].
Referring to Figure 12.10 for the four-point FFT, we find the following:
X
e
[0] = x[0] + x[2] = 1 + 3 = 4;
X
e
[1] = x[0] - x[2] = 1 - 3 =-2;
X
o
[0] = x[1] + x[3] = 2 + 4 = 6;
X
o
[1] = x[1] - x[3] = 2 - 4 =-2.
Thus,
X[0] = X
e
[0] + X
o
[0] = 4 + 6 = 10,
X[1] = X
e
[1] + W
1
X
o
[1] =-2 + (-j)(-2) =-2 + j2,
X[2] = X
e
[0] - X
o
[0] = 4 - 6 =-2,
and
X[3] = X
e
[1] - W
1
X
o
[1] =-2 - (j)(-2) =-2 - j2,
which is in agreement with the results found in Example 12.9 and listed in Table 12.3.
■
The idea behind the decomposition-in-frequency (DIF) FFT algorithm is similar to
that of the decomposition-in-time (DIT) FFT presented previously. The DIT FFT
and the DIF FFT require the same number of complex multiplications to compute.
We begin the derivation of the DIF FFT with the equation of the standard DFT,
namely,
N- 1
x[n]W
kn
, k = 0, 1, 2, Á , N - 1,
X[k] =
a
n= 0
and divide the summation in half, so that
(N/2) - 1
N- 1
x[n]W
kn
x[n]W
kn
, k = 0, 1, 2, Á , N - 1.
X[k] =
+
a
a
n= 0
n= (N/2)
Next, we rewrite the second summation as
N- 1
(N/2) - 1
(N/2) - 1
x[n]W
kn
x[n + N/2]W
k(n+N/2)
x[n + N/2]W
kn
W
kN/2
,
=
=
a
a
a
n= (N/2)
n= 0
n= 0
