DFT-Based FIR Filtering1/18DFT-Based FIR FilteringSee Proakis & Manolakis 7.32/18Motivation: DTFT View of FilteringThere are two views of filtering: * Time Domain* Frequency Domain)(][fθHnh)(][fθXnx)()()(][*][][fffθθθXHYnxnhny==The FD viewpoint is indispensable for analysis and designof filters:* Passband, Stopband, etc. of |Hf(θ)|* Linearity of Phase ∠Hf(θ), etc.Q: What about using DTFT for implementation?* Compute DTFT of input signal and filter* Multiply the two and take inverse DTFTA: NO!!!Can’t compute DTFT – must compute at infinitemany frequency values3/18Desired Intention: But Does It Work?But wait…. • If input signal is finite length, the DFT computes “samples of the DTFT”• Likewise, if filter impulse response is finite lengthQ: So… can we use this?N-ptDFTN-ptDFTN-ptIDFTx(0)x(1):x(N-1)h(0) h(1) … h(N-1)Do we get….y(n) = h[n]*x[n]??Hf[k]Xf[k]Xf[k]4/18DFT Theory and Cyclic ConvolutionA: Not Necessarily!!!! DFT Theory (Sect. 7.2.2 in Proakis & Manolakis) tells us:Circular (Cyclic) Convolution][*][]}[][{ffnxnhkXkH ⊕=IDFTThus… this block diagram gives something called cyclic convolution, not the “ordinary” convolution we want!!!Q: When doesit work???A: Only when we “trick” the DFT Theoryinto making circular= linear convolution!!!!!!Q: So… when does Cyclic = Linear Convolution???Easiest to see from an example!!!!!5/18Linear Convolution for the ExampleWhat does linear convolution give for 2 finite duration signals:Length N1 = 9Length N2 = 5x[n]h[n]Original Signals:nn(flip, no shift – since n=0, multiply and add up)First Non-Zero Output is at n=0:nnx[n]h[-n]6/18Linear Convolution for the Example (cont.)Last Non-Zero Output is at n = N1+ N2– 2 = 12:(flip, shift by N1+ N2– 2 = 12, multiply and add up)The non-zero outputs are for n = 0, 1, … , 12 Î 13 of themIn General: Length of Output of Linear Convolution = N1+ N2–1nnx[n]h[12 - n]7/18Now… What does cyclic convolution give for these 2 signals:“Original” Signals:1. Zero-Pad Shorter Signal to Length of Longer One2. Then Periodize EachCyclic Convolution for the Example“First” Output Sample:1. Flip periodized version around this point2. No shift needed to get n = 0 Output Value3. Sum over one cycleSame as in Linear Conv!!!!Not Present in Linear Conv!!!!8/18“Last” Output Sample (i.e., n = 8):1. Flip periodized version around this point2. Shift by 8 to get n = 8 Output Value3. Sum over one cycleSame as in Linear Conv!!!!Note: If I try to compute the output for n = 9 Î Exactly the same case as for n = 0!!Thus, the output is cyclic (i.e., periodic) with unique values for n = 0, 1, …. 8In General: Length of Output of Cyclic Convolution = max{N1, N2}Linear Convolution for the Example (cont.)9/18Making Cyclic = Linear ConvolutionFrom the example above we can verify:If we choose K ≥ N1+ N2–1And Zero-Pad Each Signal to Length KThen Cyclic = Linear Convolution N1= Length of x[n]N2= Length of h[n]Exercise: Verify this for the above example!!!! So…. Some of the output values of cyclic conv are different from linear conv!!!Some of the output values of cyclic conv are same as linear convAnd….The length of cyclic conv differs from the length of linear conv!!!10/18Why Do This?The FFT’s Efficiency Makes This Faster Than Time-Domain Implementation(In Many Cases)Why Do This?The FFT’s Efficiency Makes This Faster Than Time-Domain Implementation(In Many Cases)K-ptFFTK-ptFFTK-ptIFFTX(0)H(0)X(1)H(1):X(K-1)H(K-1)The DFT of h(n) is usually Pre-ComputedThe DFT of h(n) is usually Pre-Computedx(0)x(1):x(N1-1)0:0h(0) h(1) … h(N2-1) 0 … 0Zero-Pad Both to Length K ≥ N1+N2−1 Zero-Pad Both to Length K ≥ N1+N2−1 Simple Frequency-Domain Implementation of FIR Filteringy(0)y(1)::y(K-1)If K is Strictly > N1+N2−1 Then there will be extra zeroshere that can be ignored11/18Problems with the Simple FD ImplementationQ: What if N1 >> N2? A: Then, need Really Big FFT Î Not Good!!!(Input signal much longer than filter length)Also… can’t get any output samples until after whole signal is available and FFT processing is done. Long Delay.Example: Filter 0.2 sec of a radar signal sampled at Fs = 50 MHzN1 = (0.2 sec)×(50×106samples/sec) = 107samplesFFT Size > 107Î Really Big FFT!!!!Q: What if N1is unknown in advance?Example: Filtering a stream of audioA: FFT size can’t be set ahead of time – difficult programmingSimple FD Implementation Has Serious Limitations!!!12/18Better FD-Based FIR Filter ImplementationsTwo Very Similar Methods Exist• Overlap – Add (OLA)• Overlap – Save (OLS)Covered HereThe difference between OLA & OLSlies in how the xi[n] blocks are formed Use the SimpleFD-Based Method to Compute Each Output Block∑∑====iiinzinznhxnhxnzi][])[*(])[*(][][∑=iinxnx ][][Both methods exploit linearity of filter:• Break input signal into a sum of blocks Ε Output = sum of response to each blockÐ13/18OLA Method for FD-Based FIRNBis a Design ChoiceFor OLA: Choose xi[n] to be non-overlapped blocks of length NB(blocks are contiguous) ⎩⎨⎧+<≤=otherwise ,0)1(],[][BBiNiniNnxnx<See Fig. 5.8 (a) on next slide>Q: Now what happens when each of these length-NBblocks gets convolved with the length-N2 filter?A: The output block has length N2+ NB–1> NB* Output Blocks are Bigger than Input Blocks* But are separated by NB points* Thus… Output Blocks Overlap* Total Output = “Sum of Overlapped Blocks”<See Fig. 5.8 (b) – (d) on next slide>“Overlap-Add”14/18Figure from Porat’s Book15/18OLA Method Steps Assume: Filter h[n] length N2 is specifiedChoose: Block Size NB& FFT Size NFFT = 2p ≥ NB+ N2–1Choose NBsuch that: NB+ N2–1 = 2p It gives minimal complexity for method (see below)Run:Zero-Pad h[n] & Compute NFFT-pt FFT (can be pre-computed) For each i value (“For Each Block”)• Compute zi[n] using Simple FD-Based Methodf Zero-Pad xi[n] & Compute NFFT-pt FFTf Multiply by FFT of h[n] f Compute IFFT to get zi[n]• Overlap the zi[n] with previously computed output blocks • Add it to the output buffer<See Fig. 5.8 (e) on previous slide>16/18OLA Method Complexity• The FFT of filter h[n] can be pre-computed Î Don’t Count it!• We’ll measure complexity using # Multiplies/Input Sample•Use 2NFFTlog2NFFTReal Multiplies as measure for FFT • Assume input samples are Real ValuedCan do 2 real-signal FFT’s for price of ≈ 1 Complex FFT (Classic FFT Result!)• For Each Pair of Input