Digital Signal Processing Reference
In-Depth Information
2
0
−2
0
10
20
30
40
50
60
(a) Sample
2
0
−2
0
10
20
30
40
50
60
(b) Sample
5
0
−5
0
10
20
30
40
50
60
(c) Sample
Figure 3.24:
(a) A periodic sequence over eight samples; (b) Two cycles of an eight-sample sequence;
(c) Linear convolution, showing periodicity (in saturation) of eight samples.
[
−
]
yields
y
= 6 which is
N
- 2. Recall that in evaluating the linear convolution formula (Eq. (3.24)),
x
k
n
=0if
k
in MathScript, an offset of +1 is needed since 0
indices, like negative indices, are not permitted in MathScript. Thus, for example, to evaluate a circular
convolution of two length-
N
sequences
b
−
n<
0. Note also that in evaluating
x
[
k
−
n
]
[
n
]
and
x
[
n
]
in MathScript, you might employ the statement
y(m) = sum(b(n).*(x(mod(m - n, N) +1)));
(3.26)
where
n
is the vector 1:1:
N
and
m
may assume values from 1 to
N
.
Figure 3.25 shows, at (a) and (b), two eight point sequences and, at (c), their linear convolution,
having length 15 (8+8-1),and, at (d), their (8-pt) circular convolution computed using Eq. (3.25) as
implemented in MathScript by Eq. (3.26). Compare this figure, plots (a), (b), and (d), to plots (a)-(c) of
Fig. 3.23.
3.16.3
DF T CONVOLUTION THEOREM
[
]
[
]
If
f
are both time domain sequences that are periodic over
N
samples, then the DFT of
the (periodic) convolution over
N
samples is
N
times the product of the DFTs of each sequence. Stated
more compactly
n
and
g
n
DFT (f
[
n
]
N
g
[
n
]
)
=
NF
[
k
]
G
[
k
]
where
N
means a periodic (or circular) convolution over
N
samples. Taking the inverse DFT of each
side of the equation, we get
DFT
−
1
(F
f
[
n
]
N
g
[
n
]=
N
·
[
k
]
G
[
k
]
)
(3.27)