Digital Signal Processing Reference
In-Depth Information
Note that
X
e
[k]
and
X
o
[k]
are periodic; for example,
X
e
[2] = x
e
[0] + x
e
[1](-1)
2
= X
e
[0]
and
X
e
[3] = x
e
[0] + x
e
[1](-1)
3
= X
e
[1].
The four-point DFT then is
X[0] = X
e
[0] + X
o
[0]W
1(0)
= X
e
[0] + X
o
[0];
X[1] = X
e
[1] + X
o
[1]W
1(1)
= X
e
[1] + X
o
[1]W
1
;
X[2] = X
e
[0] - X
o
[0]W
1(2)
= X
e
[0] - X
o
[0];
X[3] = X
e
[1] - X
o
[1]W
1(3)
= X
e
[1] - X
o
[1]W
1
.
(12.40)
W
1(k)
Here, the changed term is for the hosen value
k
.
We see that the four-point DFT can be computed by the generation of two two-
point DFTs, followed by a
recomposition
of terms, as shown in the signal flow graph
of Figure 12.10. In other words,
[4-point DFT of x[n]] = [2-point DFT of x
e
[n]] + W
1k
[2-point DFT of x
o
[n]].
The Equations (12.40) are known as the
recomposition equations
of the four-point
DFT.
X
e
[0]
1
1
x
e
[0]
x
[0]
X
[0]
1
1
1
1
X
e
[1]
1
1
x
e
[1]
x
[2]
X
[1]
1
X
o
[0]
1
1
x
o
[0]
x
[1]
X
[2]
1
1
1
W
4
X
o
[1]
1
1
x
o
[1]
x
[3]
X
[3]
Figure 12.10
Signal flow graph for a four-point DFT.
