# OpenStax_CNX

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

### Recently Viewed

This feature requires Javascript to be enabled.

### Tags

(What is a tag?)

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

# Filtering with the DFT

Module by: Robert Nowak. E-mail the author

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: You are viewing an old version of this document. The latest version is available here.

## Introduction

yn=xn*hn= k =xkhnk 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):

## Compute IDFT of Y[k]

y ~ n=1N k =0N1Ykei2πkNn=1N k =0N1XkHkei2πkNn=1N k =0N1 m =0N1xme(i2πkNm)Hkei2πkNn= m =0N1xm(1N k =0N1Hkei2πkN(nm))= m =0N1xmh (( 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 ~ nm=h (( n m )) N h ~ n m h (( n m )) N This computes as shown in Figure 3:

y ~ n= m =0N1xmh (( 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.

### DFT Pair

Note that in general:

### 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 =02xmhnm 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)

• 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 9 illustrates the relationship between circular convolution and regular convolution using the previous two figures:

### 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 =04XkHkei2π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):

#### 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+N1 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).

## DSP System

1. Sample finite duration continuous-time input xt x t to get xn x n where n=0M1 n 0 M 1 .
2. Zero-pad xn x n and hn h n to length M+N1 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=0M+N1 n 0 M N 1 .
5. Reconstruct yt y t

## Content actions

### Give feedback:

My Favorites (?)

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

| A lens I own (?)

#### Definition of a lens

##### Lenses

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

##### What is in a lens?

Lens makers point to 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 member, a community, or a respected organization.

##### What are tags?

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