Digital Signal Processing Reference
In-Depth Information
1
1
N
2
x
[
n
]
x
[
n
]
x n
1
1
N
2
N
2
W
n
x
[
n
]
x n
x n
Figure 12.13
A decomposition-in-
frequency FFT flow diagram.
W
n
1
Four-point decomposition
x
[0]
x
[2]
X
1
[0]
Two-point FFT
x
[0]
X
[0]
x
[3]]
W
0
X
1
[1]
[
x
[1]
x
[1]
X
[2]
1
x
[0]
x
[2]
1
X
2
[0]
x
[2]
X
[1]
W
0
4
x
[3]]
W
1
[
x
[1]
1
x
[3]
X
[3]
Figure 12.14
A four-point decomposition-
in-frequency FFT.
W
1
X
2
[1]
1
The decomposition-in-frequency method of calculating the FFT
EXAMPLE 12.13
The decomposition-in-frequency (DIF) method of the FFT will be used to compute the DFT
of the discrete sequence
x[n] = [1, 2, 3, 4]
listed in Table 12.3. Referring to Figure 12.14 for the four-point DIF FFT, we find the following:
X
1
[0] = x[0] + x[2] = 1 + 3 = 4;
X
1
[1] = W
0
[x[1] + x[3]] = 2 + 4 = 6;
X
2
[0] = x[0] - x[2] = 1 - 3 =-2;
X
2
[1] = W
1
[x[1] - x[3]] =-j[2 - 4] = j2.
