Digital Signal Processing Reference
In-Depth Information
We begin by substituting the first equation in (12.30) into the second one. In
the first equation,
n
is the summation variable; we change this summation variable
to
m
, to avoid confusion with variable
n
in the second equation. Then
N- 1
N- 1
N- 1
1
N
a
1
N
a
X[k]W
-kn
B
x[m]W
km
R
W
-kn
.
x[n] =
=
(12.36)
a
k= 0
k= 0
m= 0
Next, the order of the summations is reversed:
N- 1
N- 1
1
N
a
W
k(m-n)
.
x[n] =
x[m]
a
(12.37)
m= 0
k= 0
From (12.35), we can write
N- 1
N,
n = m
W
k(m-n)
b
=
n Z m
.
a
0,
k= 0
Thus, (12.37) becomes
N- 1
1
N
a
x[n] =
x[m]Nƒ
n=m
= x[n],
(12.38)
m= 0
and the validity of the discrete Fourier transform is proved.
An example will help us to understand computation of the DFT.
Calculation of a DFT with a MATLAB program
EXAMPLE 12.9
We wish to find the discrete Fourier transform of the sequence
x[n],
given by the data in
W
4
= e
-j2p/4
= 1
l
-
90°
=-j,
Table 12.3. For this case,
N = 4.
From (12.30), with
N = 4
and
X[0] = x[0] + x[1] + x[2] + x[3] = 1 + 2 + 3 + 4 = 10,
X[1] = x[0] + x[1](-j) + x[2](-j)
2
+ x[3](-j)
3
= 1 - j2 +-3 + j4 =-2 + j2,
X[2] = x[0] + x[1](-j)
2
+ x[2](-j)
4
+ x[3](-j)
6
= 1 - 2 + 3 - 4 =-2,
TABLE 12.3
Values for Example 12.9
n
x
[
n
]
k
X
[
k
]
0
1
0
10
1
2
1
-2 + j2
2
3
2
-2
3
4
3
-2 - j2
