<< Chapter < Page Chapter >> Page >
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

y n x n h n k x k h n k
Y X H
Assume that H is specified.

How can we implement X H in a computer?

Discretize (sample) X and H . In order to do this, we should take the DFTs of x n and h n to get X k and X k . Then we will compute y ~ n IDFT X k H k Does y ~ n y n ?

Got questions? Get instant answers now!

Recall that the DFT treats N -point sequences as if they are periodically extended ( ):

Compute idft of y[k]

y ~ n 1 N k N 1 0 Y k 2 k N n 1 N k N 1 0 X k H k 2 k N n 1 N k N 1 0 m N 1 0 x m 2 k N m H k 2 k N n m N 1 0 x m 1 N k N 1 0 H k 2 k N n m m N 1 0 x m h (( n m )) N
And the IDFT periodically extends h n : h ~ n m h (( n m )) N This computes as shown in :

y ~ n m N 1 0 x m h (( n m )) N
is called circular convolution and is denoted by .

The above symbol for the circular convolution is for an N -periodic extension.

Dft pair

Note that in general:

Regular vs. circular convolution

To begin with, we are given the following two length-3 signals: x n 1 2 3 h n 1 0 2 We can zero-pad these signals so that we have the following discrete sequences: x n 0 1 2 3 0 h n 0 1 0 2 0 where x 0 1 and h 0 1 .

  • Regular Convolution:
    y n m 2 0 x m h n m
    Using the above convolution formula (refer to the link if you need a review of convolution ), we can calculate the resulting value for y 0 to y 4 . Recall that because we have two length-3 signals, our convolved signal will be length-5.
    • n 0 0 0 0 1 2 3 0 0 2 0 1 0 0 0
      y 0 1 1 2 0 3 0 1
    • n 1 0 0 1 2 3 0 0 2 0 1 0 0
      y 1 1 0 2 1 3 0 2
    • n 2 0 1 2 3 0 0 2 0 1 0
      y 2 1 2 2 0 3 1 5
    • n 3
      y 3 4
    • n 4
      y 4 6

Regular convolution result

Result is finite duration, not periodic!

  • Circular Convolution:
    y ~ n m 2 0 x m h (( n m )) N
    And now with circular convolution our h n changes and becomes a periodically extended signal:
    h (( n )) N 1 0 2 1 0 2 1 0 2
    • n 0 0 0 0 1 2 3 0 1 2 0 1 2 0 1
      y ~ 0 1 1 2 2 3 0 5
    • n 1 0 0 0 1 2 3 0 0 1 2 0 1 2 0
      y ~ 1 1 1 2 1 3 2 8
    • n 2
      y ~ 2 5
    • n 3
      y ~ 3 5
    • n 4
      y ~ 4 8

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.
Got questions? Get instant answers now!

Regular convolution from periodic convolution

  • "Zero-pad" x n and h n 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): x n 1 2 3 0 0 h n 1 0 2 0 0
  • Now take the DFTs of the zero-padded signals:
    y ~ n 1 N k 4 0 X k H k 2 k 5 n m 4 0 x m h (( n m )) 5
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 M -point signal x n with an N -point signal h n by padding each signal with zeros to obtain two M N 1 length sequences and computing the circular convolution (or equivalently computing the IDFT of H k X k , 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 N impulse response, h n

  • Sample finite duration continuous-time input x t to get x n where n 0 M 1 .
  • Zero-pad x n and h n to length M N 1 .
  • Compute DFTs X k and H k
  • Compute IDFTs of X k H k y n y ~ n where n 0 M N 1 .
  • Reconstruct y t

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Intro to digital signal processing. OpenStax CNX. Jan 22, 2004 Download for free at http://cnx.org/content/col10203/1.4
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Intro to digital signal processing' conversation and receive update notifications?

Ask