Connexions

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

What is 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.

This content is ...
Affiliated with (?)
This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.

  • This module is included inLens: Rice University OpenCourseWare
    By: OpenCourseWare ConsortiumAs a part of collection:"Intro to Digital Signal Processing"

    Click the "Rice University OCW" link to see all content affiliated with them.

    Rice University OCW
Tags

(?)

These tags come from the endorsement, affiliation, and other lenses that include this content.

Filtering with the DFT

Module by: Robert Nowak

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.

Introduction

sec11_fig1.png
Figure 1
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.
Problem 1
How can we implement XωHω X ω H ω in a computer?
[ Click for Solution 1 ]
Solution 1
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 ?
[ Hide Solution 1 ]
Recall that the DFT treats NN-point sequences as if they are periodically extended (Figure 2):
sec11_fig2.png
Figure 2

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:
sec11_fig3.png
Figure 3
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.
sec11_fig4.png
Figure 4: The above symbol for the circular convolution is for an NN-periodic extension.

DFT Pair

sec11_fig5.png
Figure 5
Note that in general:
sec11_fig6.png
Figure 6
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)
Regular Convolution Result
sec11_fig7.png
Figure 7: Result is finite duration, not periodic!
  • 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)
Circular Convolution Result
sec11_fig8.png
Figure 8: Result is 3-periodic.
Figure 9 illustrates the relationship between circular convolution and regular convolution using the previous two figures:
Circular Convolution from Regular
sec11_fig9.png
Figure 9: The left plot (the circular convolution results) has a "wrap-around" effect due to periodic extension.

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):
no_image.png
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!
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).
sec11_fig11.png
Figure 11: Note that the lower two images are simply the top images that have been zero-padded.

DSP System

no_image.png
Figure 12: The system has a length NN impulse response, hn h n
  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

Comments, questions, feedback, criticisms?

Send feedback