Digital Signal Processing Reference
In-Depth Information
(IDFT) will give us the desired result. FFT offers a considerable advantage in
performing convolution. Exercise caution as this will result in a circular convolu-
tion.
4
Let x
k
and y
k
be sequences of length m and n, respectively, then the circular
convolution is defined as x
k
y
k
¼
IDFT
ð
DFT
ð
x
k
Þ
DFT
ð
y
k
Þ
f
g
.
4.6.1 Circular Convolution
In normal convolution the sequence beyond its length is assumed to have zeros. In
circular convolution the sequences are assumed to be periodic, and this produces
improper results if sufficient precautions are not taken. Consider a sequence x
k
of
length 50
ð
m
¼
50
Þ
and another sequence y
k
of length 15
ð
n
¼
15
Þ
and we perform
a normal convolution to get a sequence z
k
¼
x
k
y
k
; this is the line marked with
open circles in Figure 4.11(a) and has a length of 64 (50
þ
15
1).
10
5
50
5
OK
0
0
64
13
−5
−10
−5
0
20
40
60
80
0
20
40
60
80
(a)
(b)
Figure 4.11 Understanding circular convolution
In Figure 4.11(a) two sequences were circularly convolved by multiplying the
DFT of x
k
with the DFT of y
k
and taking the inverse DFT of the resulting sequence,
leading to circular convolution
z
k
¼
x
k
y
k
. In order to take the DFTs and multiply
them, we need the lengths to be the same. We have to make the lengths equal, so we
have padded the sequence y
k
with 35 zeros. The sequence
^
^
z
k
of length 50 is a
consequence of this padding and is shown in Figure 4.11(a).
A comparison of the sequences z
k
and
z
k
is shown as an error in Figure 4.11(b). It
reveals that the first 12 points are erroneous and at the tail we need another 14
points of correct data. Figure 4.11(b) shows that only the length from 13 to 50 is
numerically correct; the rest of the head and tail are not okay. To get over this
problem we pad the sequence of length 50 with 14
ð¼
n
1
Þ
zeros and the
sequence of length 15 with 49
ð¼
m
1
Þ
zeros, giving both sequences a length
^
4
The symbol
denotes circular convolution.
Search WWH ::
Custom Search