Digital Signal Processing Reference
In-Depth Information
4.2 The DFT (Discrete Fourier Transform)
We now develop a Fourier representation for finite-length signals; to do so,
we need to find a set of oscillatory signals of length
N
which contain a whole
number of periods over their support. We start by considering a family of
finite-length sinusoidal signals (indexed by an integer
k
)oftheform
l
g
r
,
y
i
d
.
,
©
,
L
s
e
j
ω
k
n
,
w
k
[
n
]=
n
=
0,...,
N
−
1
(4.1)
where all the
ω
k
's are distinct frequencies which fulfill our requirements. To
determine these frequency values, note that, in order for
w
k
[
n
]
to contain a
whole number of periods over
N
samples, it must conform to
w
k
[
N
]=
w
k
[
0
]=
1
which translates to
e
j
ω
k
N
=
1
The above equation has
N
distinct solutions which are the
N
roots of unity
e
j
2
π
m
/
N
,
m
=
0,...,
N
−
1; if we define the complex number
e
−j
2
N
W
N
=
then the family of
N
signals in (4.1) can be written as
W
−nk
N
w
k
[
n
]=
,
n
=
0,...,
N
−
1
(4.2)
for each value of
k
=
0,...,
N
−
1. We can represent these
N
signals as a set
of vectors
w
(
k
)
k
=
0,...,
N−
1
in
N
with
w
(
k
)
=
1
W
−k
N
W
−
2
k
T
...
W
−
(
N−
1
)
k
N
(4.3)
N
The real and imaginary parts of
w
(
k
)
for
N
=
32 and for some values of
k
are
plotted in Figures 4.2 to 4.5.
We can verify that
w
(
k
)
k
=
0,...,
N−
1
is a set of
N
orthogonal vectors and
therefore a basis for
N
; indeed we have (noting that
W
−
N
∗
=
W
N
):
⎧
⎨
⎩
N
for
m
=
n
N
−
1
w
(
m
)
,
w
(
n
)
=
W
(
m−n
)
i
N
W
(
m−n
)
N
N
=
1
−
(4.4)
=
0 r
m
=
n
i
=
0
W
(
m−n
)
1
−
N
since
W
iN
N
=
1forall
i
∈
. Inmore compact notation we can therefore state
that
w
(
m
)
,
w
(
n
)
=
N
δ
[
n
−
m
]
(4.5)
The vectors
w
(
k
)
k
=
0,...,
N−
1
are the Fourier basis for
N
, and therefore for
the space of length-
N
signals. It is immediately evident that this basis is not
