Filtering with the DFT 2.2 2003/01/21 2003/02/10 Rob "The Kid" Nowak nowak@rice.edu Michael Haag mjhaag@rice.edu A/D circular convolution convolution D/A DFT discrete fourier transform filters fourier transform 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 ? 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 regular convolution 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.

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 (5 being 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 this illustration 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