Digital Signal Processing Reference
In-Depth Information
x
p
(1
−
m)
01234567
m
f
p
(
m)
−
01234567
8
m
f
p
(1
−
m)
0
7
m
f
p
(2
−
m)
012
7
m
f
p
(3
−
m)
0123456
7
m
Figure 3.32
Circular convolution of
x
p
(n)
and
f
p
(n)
with
N
=
8.
coefficients of its DFT, which indicates the frequency response of the signal at
N
discrete frequencies equally spaced between 0 and 2
π
.
3.7 FAST FOURIER TRANSFORM
Note that when we computed each of the eight samples of the DFT in the previous
example, there was multiplication of the complex number
e
j(
2
π/N)kn
=
W
−
kn
,
k
−
1
)
, with the eight real-valued samples of the signal and
the product were added. So the total number of multiplications is 8
2
=
0
,
1
,
2
,...,(N
=
64 and
the number of additions are 7
2
=
49 in computing the eight samples of the
DFT. The same number of multiplications and additions are required to find the
inverse DFT; in this case, samples of both
X(k)
and
W
−
kn
are complex-valued.
In general, direct computation of the DFT and IDFT using (3.79) and (3.80)
requires
N
2
multiplications and
(N
−
1
)
2
additions; so they become very large
Search WWH ::
Custom Search