The ideas of using the DFT to filter a signal and recover a signal from a noisy transmission are addressed based on the ideas of the DFT and convolution.
Introduction
Assume that
is specified.
How can we implement
in a computer?
Discretize (sample)
and
. In order to do this, we should take the DFTs
of
and
to get
and
. Then we will compute
Does
?
Recall that the DFT treats
-point sequences as if they are
periodically extended (
):
Compute idft of y[k]
And the IDFT periodically extends
:
This computes as shown in
:
is called
circular convolution and is denoted by
.
The above symbol for the circular convolution is for an
-periodic extension.
Dft pair
Note that in general:
Regular vs. circular convolution
To begin with, we are given the following two length-3
signals:
We can zero-pad these signals so that we have the following
discrete sequences:
where
and
.
Regular Convolution:
Using the above convolution formula (refer to the
link if you need a review of
convolution ), we can
calculate the resulting value for
to
. Recall that because we have two length-3
signals, our convolved signal will be length-5.
Regular convolution result
Result is finite duration, not periodic!
Circular Convolution:
And now with circular convolution our
changes and becomes a periodically extended
signal:
Circular convolution result
Result is 3-periodic.
illustrates the
relationship between circular convolution and regularconvolution using the previous two figures:
Circular convolution from regular
The left plot (the circular convolution results) has a
"wrap-around" effect due to periodic extension.
"Zero-pad"
and
to avoid the overlap (wrap-around) effect. We
will zero-pad the two signals to a length-5 signal (5being the duration of the regular convolution result):
Now take the DFTs of the zero-padded signals:
Now we can plot this result (
):
The sequence from 0 to 4 (the underlined part of the
sequence) is the regular convolution result. From thisillustration we can see that it is 5-periodic!
We can compute the regular convolution result of a
convolution of an
-point
signal
with an
-point
signal
by padding each signal with zeros to obtain two
length sequences and computing the circular
convolution (or equivalently computing the IDFT of
, the product of the DFTs of the zero-padded
signals) (
).
Note that the lower two images are simply the top images
that have been zero-padded.
Dsp system
The system has a length
impulse response,
Sample finite duration continuous-time input
to get
where
.