Skip to content Skip to navigation

Connexions

You are here: Home » Content » Filtering with the DFT

Navigation

Recently Viewed

This feature requires Javascript to be enabled.

Filtering with the DFT

Module by: Robert Nowak. E-mail the author

User rating (How does the rating system work?)
Ratings

Ratings allow you to judge the quality of modules. If other users have ranked the module then its average rating is displayed below. Ratings are calculated on a scale from one star (Poor) to five stars (Excellent).

How to rate a module

Hover over the star that corresponds to the rating you wish to assign. Click on the star to add your rating. Your rating should be based on the quality of the content. You must have an account and be logged in to rate content.

:
(0 ratings)

Summary: 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.

Note: Your browser may not currently support MathML. See our browser support page for additional details. You can always view the correct math in the PDF version.

Introduction

Figure 1
Figure 1 (sec11_fig1.png)

yn=xn*hn=∑k=-∞∞xkhn−k y n x n h n k x k h n k (1)
Yω=XωHω Y ω X ω H ω (2)
Assume that Hω H ω is specified.

Exercise 1

How can we implement XωHω X ω H ω in a computer?

Solution

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

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

Figure 2
Figure 2 (sec11_fig2.png)

Compute IDFT of Y[k]

y ~ n=1N∑k=0N−1Ykⅇⅈ2πkNn=1N∑k=0N−1XkHkⅇⅈ2πkNn=1N∑k=0N−1∑m=0N−1xmⅇ-ⅈ2πkNmHkⅇⅈ2πkNn=∑m=0N−1xm1N∑k=0N−1Hkⅇⅈ2πkNn−m=∑m=0N−1xmh (( n − m )) N 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 (3)
And the IDFT periodically extends hn h n : h ~ n−m=h (( n − m )) N h ~ n m h (( n − m )) N This computes as shown in Figure 3:

Figure 3
Figure 3 (sec11_fig3.png)

y ~ n=∑m=0N−1xmh (( n − m )) N y ~ n m N 1 0 x m h (( n − m )) N (4)
is called circular convolution and is denoted by Figure 4.

Figure 4: The above symbol for the circular convolution is for an NN-periodic extension.
Figure 4 (sec11_fig4.png)

DFT Pair

Figure 5
Figure 5 (sec11_fig5.png)

Note that in general:

Figure 6
Figure 6 (sec11_fig6.png)

Example 1: Regular vs. Circular Convolution

To begin with, we are given the following two length-3 signals: xn=123 x n 1 2 3 hn=102 h n 1 0 2 We can zero-pad these signals so that we have the following discrete sequences: xn=…01230… x n … 0 1 2 3 0 … hn=…01020… h n … 0 1 0 2 0 … where x0=1 x 0 1 and h0=1 h 0 1 .

  • Regular Convolution:
    yn=∑m=02xmhn−m y n m 2 0 x m h n m (5)
    Using the above convolution formula (refer to the link if you need a review of convolution), we can calculate the resulting value for y0 y 0 to y4 y 4 . Recall that because we have two length-3 signals, our convolved signal will be length-5.
    • n=0 n 0 …0001230… … 0 0 0 1 2 3 0 … …0201000… … 0 2 0 1 0 0 0 …
      y0=1×1+2×0+3×0=1 y 0 1 1 2 0 3 0 1 (6)
    • n=1 n 1 …001230… … 0 0 1 2 3 0 … …020100… … 0 2 0 1 0 0 …
      y1=1×0+2×1+3×0=2 y 1 1 0 2 1 3 0 2 (7)
    • n=2 n 2 …01230… … 0 1 2 3 0 … …02010… … 0 2 0 1 0 …
      y2=1×2+2×0+3×1=5 y 2 1 2 2 0 3 1 5 (8)
    • n=3 n 3
      y3=4 y 3 4 (9)
    • n=4 n 4
      y4=6 y 4 6 (10)

Figure 7: Result is finite duration, not periodic!
Regular Convolution Result
Regular Convolution Result (sec11_fig7.png)

  • Circular Convolution:
    y ~ n=∑m=02xmh (( n − m )) N y ~ n m 2 0 x m h (( n − m )) N (11)
    And now with circular convolution our hn h n changes and becomes a periodically extended signal:
    h (( n )) N =…102102102… h (( n )) N … 1 0 2 1 0 2 1 0 2 … (12)
    • n=0 n 0 …0001230… … 0 0 0 1 2 3 0 … …1201201… … 1 2 0 1 2 0 1 …
      y ~ 0=1×1+2×2+3×0=5 y ~ 0 1 1 2 2 3 0 5 (13)
    • n=1 n 1 …0001230… … 0 0 0 1 2 3 0 … …0120120… … 0 1 2 0 1 2 0 …
      y ~ 1=1×1+2×1+3×2=8 y ~ 1 1 1 2 1 3 2 8 (14)
    • n=2 n 2
      y ~ 2=5 y ~ 2 5 (15)
    • n=3 n 3
      y ~ 3=5 y ~ 3 5 (16)
    • n=4 n 4
      y ~ 4=8 y ~ 4 8 (17)

Figure 8: Result is 3-periodic.
Circular Convolution Result
Circular Convolution Result (sec11_fig8.png)

Figure 9 illustrates the relationship between circular convolution and regular convolution using the previous two figures:

Figure 9: The left plot (the circular convolution results) has a "wrap-around" effect due to periodic extension.
Circular Convolution from Regular
Circular Convolution from Regular (sec11_fig9.png)

Regular Convolution from Periodic Convolution

  1. "Zero-pad" xn x n and hn h n to avoid the overlap (wrap-around) effect. We will zero-pad the two signals to a length-5 signal (5 being the duration of the regular convolution result): xn=12300 x n 1 2 3 0 0 hn=10200 h n 1 0 2 0 0
  2. Now take the DFTs of the zero-padded signals:
    y ~ n=1N∑k=04XkHkⅇⅈ2πk5n=∑m=04xmh (( n − m )) 5 y ~ n 1 N k 4 0 X k H k 2 k 5 n m 4 0 x m h (( n − m )) 5 (18)
Now we can plot this result (Figure 10):

Figure 10: The sequence from 0 to 4 (the underlined part of the sequence) is the regular convolution result. From this illustration we can see that it is 5-periodic!
Figure 10 (no_image.png)

General Result:

We can compute the regular convolution result of a convolution of an MM-point signal xn x n with an NN-point signal hn h n by padding each signal with zeros to obtain two M+N−1 M N 1 length sequences and computing the circular convolution (or equivalently computing the IDFT of HkXk H k X k , the product of the DFTs of the zero-padded signals) (Figure 11).

Figure 11: Note that the lower two images are simply the top images that have been zero-padded.
Figure 11 (sec11_fig11.png)

DSP System

Figure 12: The system has a length NN impulse response, hn h n
Figure 12 (no_image.png)

  1. Sample finite duration continuous-time input xt x t to get xn x n where n=0…M−1 n 0 … M 1 .
  2. Zero-pad xn x n and hn h n to length M+N−1 M N 1 .
  3. Compute DFTs Xk X k and Hk H k
  4. Compute IDFTs of XkHk X k H k yn= y ~ n y n y ~ n where n=0…M+N−1 n 0 … M N 1 .
  5. Reconstruct yt y t

Content actions

Give Feedback:

E-mail the module author | Rate module ( How does the rating system work?)

Rating system

Ratings

Ratings allow you to judge the quality of modules. If other users have ranked the module then its average rating is displayed below. Ratings are calculated on a scale from one star (Poor) to five stars (Excellent).

How to rate a module

Hover over the star that corresponds to the rating you wish to assign. Click on the star to add your rating. Your rating should be based on the quality of the content. You must have an account and be logged in to rate content.

(0 ratings)

Download:

Module PDF

Add module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections directly in Connexions. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need a Connexions account to use 'My Favorites'.

| A lens (?)

Definition of a lens

Lenses

A lens is a custom view of Connexions content. You can think of it as a fancy kind of list that will let you see Connexions through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to Connexions materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual Connexions member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks