Biomedical Engineering Reference
In-Depth Information
The discrete Fourier transform (DFT)
N
1
2p
mk
N
0
x
ð
k
Þ
e
j
X
ð
m
Þ¼
;
m
¼
0, 1,
...
,
N
=
2
ð
11
:
18
Þ
k
¼
provides the tool necessary to analyze and represent discrete signals in the frequency
domain. The DFT is essentially the digital version of the Fourier transform. The index
m
represents the digital frequency index,
x
(
k
) is the sampled approximation of
x
(
t
),
k
is the dis-
crete time variable,
N
is an even number that represents the number of samples for
x
(
k
), and
X
).
The inverse discrete Fourier transform (IDFT) is the discrete-time version of the inverse
Fourier transform. The inverse discrete Fourier transform (IDFT) is represented as
(
m
) is the DFT of
x
(
k
N
1
1
N
2p
mk
N
0
X
ð
m
Þ
e
j
x
ð
k
Þ¼
;
k
¼
0, 1,
...
,
N
1
ð
11
:
19
Þ
m
¼
As for the FT and IFT, the DFT and IFT represent a Fourier transform pair in the discrete
domain. The DFT allows one to convert a set of digital time samples to its frequency
domain representation. In contrast, the IDFT can be used to invert the DFT samples, allow-
ing one to reconstruct the signal samples
x
(
k
) directly from its frequency domain form,
X
). These two equations are thus interchangeable, since either conveys all of the signal
information.
(
m
EXAMPLE PROBLEM 11.12
Find the discrete Fourier transform of the signal
25
k
x
ð
k
Þ¼
0
:
for
k
¼
0:15
k
X
ð
m
Þ¼
N
1
k
¼
¼
X
15
¼
X
15
¼
X
15
2p
mk
N
2p
mk
16
2p
m
N
0
x
ð
k
Þ
e
j
25
k
e
j
e
j
0
a
k
0
:
0
:
25
k
¼
0
k
¼
0
k
¼
2p
m
N
. Since for a geometric sum
e
j
Note that the preceding is a geometric sum in which
a
¼
0
:
25
N
a
k
¼
a
N
þ1
a
M
a
1
k
¼
M
we obtain
32
m
p
N
25
16
e
j
16
a
0
0
:
1
X
ð
m
Þ¼
a
¼
2
m
p
N
a
1
e
j
1
An efficient computer algorithm for calculating the DFT is the fast Fourier transform (FFT). The
output of the FFT and DFT algorithms are the same, but the FFT has a much faster execution time
than the DFT (proportional to
0
:
25
2
operations). The ratio of computing time for
N
log
2
ð
N
Þ
versus
N
the DFT and FFT is therefore
2
DFT computing time
FFT computing time
¼
N
N
log
2
N
log
2
N
¼
ð
11
:
20
Þ
N
