Digital Signal Processing Reference
In-Depth Information
and
X¿
2
[k] = [6, -2.5245 - j4.0333, -0.1540 + j2.2383, -0.3216 - j1.7950,
-0.3216 + j1.7950, -0.1540 - j2.2383, -2.5245 + j4.0333].
We find
Y¿[k]
by multiplying the corresponding elements of the two discrete-frequency
sequences:
Y¿[k] = [60, -19.9928 + j23.8775, -5.6024 + j0.3927, -5.8342 - j0.8644,
-4.4049 + j0.4585, -5.6024 - j0.3927, -19.9928 + j23.8775].
Now we find the IDFT to complete the convolution calculation:
t
5
Y¿[k]
6
= y¿[n] = [0, 1, 4, 10, 16, 17, 12].
The following MATLAB program can be used to reproduce the results of this example:
% This MATLAB program reproduces the results of
% Example 12.18.
x1 = [1 2 3 4];
x2 = [0 1 2 3];
y = conv(x1,x2);
% Zero-pad the vectors to 7 elements each.
x1p = zeros(1:7);, x1p(1:4) = x1(1:4);
x2p = zeros(1:7);, x2p(1:4) = x2(1:4);
X1 = fft(x1p,7);
X2 = fft(x2p,7);
Y = X1.*X2;
yp = ifft(Y);
y
yp
■
The discovery that we can use the DFTs of two sequences to compute their
convolution is an important result for signal processing, as shown in examples to fol-
low. We should now consider the computational efficiency of calculating a convolu-
tion by the DFT rather than the direct method. Figure 12.25 shows a block-diagram
representation of the convolution process by the DFT method. In this system, both
DFTs and the IDFT are computed with the use of a radix-2 FFT algorithm. The two
N
-element sequences to be convolved are extended by zero padding so that each of
the extended sequences contains
2N - 1
elements. To simplify the algebra without
x
1
[
n
]
x
1
[
n
]
N
1
X
1
[
k
]
Zero padding
N
2
DFT
1 zeros
N
1
samples
N
2
1
samples
x
1
[
n
]
x
2
[
n
]
N
1
X
2
[
k
]
Y
[
k
]
y
[
n
]
Zero padding
N
1
DFT
IDFT
1 zeros
Figure 12.25
Block diagram of
convolution using DFTs.
N
2
x
1
[
n
]
x
2
[
n
]
N
2
samples
1
samples
