MIT OpenCourseWare http://ocw.mit.edu 2.161 Signal Processing: Continuous and Discrete Fall 2008 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.� k n - k 0 0 - 3 f k n - k 0 h n - k n = 8 8 1 Massachusetts Institute of Technology Department of Mechanical Engineering 2.161 Signal Processing - Continuous and Discrete Fall Term 2008 Lecture 181 Reading: • Proakis and Manolakis: 7.3.1, 7.3.2, 10.3 • Oppenheim, Schafer, and Buck: 8.7.3, 7.1 FFT Convolution for FIR Filters The response of an FIR filter with impulse response {hk} to an input { fk} is given by the linear convolution ∞ yn = fkhn−k. k=−∞ The length of the convolution of two finite sequences of lengths P and Q is N = P + Q − 1. The following figure shows a sequence {fn} of length P = 6, and a sequence {hn} of length Q = 4 reversed and shifted so as to compute the extremes of the convolved sequence y0 and y8. P = 6 n = 0 h n - k 5 Q = 4 Q = 4 The convolution property of the DFT suggests that the FFT might be used to convolve two equal length sequences yn = IDFT {DFT {fn} .DFT {hn}} . 1copyright cD.Rowell 2008 18–1However, DFT convolution is a circular convolution, involving periodic extensions of the two sequences. The following figure shows the circular convolution of length 6, on two sequences {fn} of length P = 6 and {hn} of length Q = 4. The periodic extensions cause overlap in the first Q − 1 samples, generating “wrap-around” errors in the DFT convolution. P = 6 Q = 4 k n - k 0 5 0- 3 f k h n - kn = 0 o v e r l a p o f Q - 1 s a m p l e s DFT convolution of two sequences of length P and Q (P ≥ Q) in DFTs of length P 1. Produces an output sequence of length P , whereas linear convolution produces an output sequence of length P + Q − 1. 2. Introduces wrap-around error in the first Q−1 samples of the output sequence. The solution is to zero-pad both input sequences to a length N ≥ P +Q−1 and then to use DFT convolution with the length N sequences. For example, if {fn} is of length P = 237, and {hn} is of length Q = 125, for error-free convolution we must perform the DFTs in length N ≥ 237 + 125 − 1 = 461. If the available FFT routine is radix-2, we should choose N=512. The use of the FFT for Filtering Long Data Sequences: The DFT convolution method provides an attractive alternative to direct convolution when the length of the data record is very large. The general method is to break the data into manageable sections, then use the FFT to to perform the convolution and then recombine the output sections. Care must be taken, however, to avoid wrap-around errors. There are two basic methods used for convolving long data records. Let the impulse response {hn} have length Q. Overlap-Save Method: (Also known as the overlap-discard,or select-savings method.) In this method the data is divided into blocks of length P samples, but with successive blocks overlapping by Q − 1. The DFT convolution is done on each block with length P , and wrap-around errors are allowed to contaminate the first Q − 1 samples of the output. These initial samples are then discarded, and only the error-free P − (Q − 1) samples are saved in the output record. 18–2� � n With the overlap of the data blocks, in the mth block the samples are fm(n)= f(n + m(P − (Q − 1))), n =0,...,P − 1, and after DFT convolution in length P , giving ymP (n), the output is taken as ymP (n +(Q − 1)),n =0,...,P − (Q − 1) ym(n)= 0, otherwise. and the output is formed by concatenating all such records: ∞ y(n)= ym(n − m(P − Q + 1)). m=0 P P P P y ( n )0 P n f ( n ) h ( n ) Q n Q - 1 P n Q - 1 P n Q - 1 o v e r l a p p i n g i n p u t s e c t i o n s y ( n )1 P y ( n )2 P d i s c a r d o u t p u t s a m p l e s i n t h i s r e g i o n d i s c a r d o u t p u t s a m p l e s i n t h i s r e g i o n d i s c a r d o u t p u t s a m p l e s i n t h i s r e g i o n Overlap-Add Method: In this method the data is divided into blocks of length P , but the DFT convolution is done in zero-padded blocks of length N = P + Q − 1 so that 18–3n � � 2 wrap-around errors do not occur. In this case the output is identical to the linear convolution of the two blocks, with an initial rise of length Q − 1 samples, and a trailing section also of length Q − 1 samples. It is easy to show that if the trailing section of the mth output block is overlapped with the initial section of the (m + 1)th block, the samples add together to generate the correct output values. P P P n n f ( n ) h ( n ) Q a d d o u t p u t s a m p l e s i n t h i s r e g i o n a d d o u t p u t s a m p l e s i n t h i s r e g i o n P + Q - 1 P + Q - 1 P + Q - 1 y ( n )1y ( n )2y ( n )3n n MATLAB’s fftfilt() function performs DFT convolution using the overlap-add method. The Design of IIR Filters An IIR filter is characterized by a recursive difference equation N M yn = akyn−k + bkfn−k k=1 k=0 and a rational transfer function of the form b0z0 + b1z−1 + ...+ bM z−M H(z)= z0 + a1z−1 + ...+ aN z−N IIR filters have the advantage that they can give a better cut-off characteristic than a FIR filter of the same order, but have the disadvantage that the phase response cannot be well controlled. 18–4� �The most common design procedure for digital IIR filters is to design a continuous filter in the s-plane, and then to transform that filter to the z-plane. Because the mapping between the continuous and discrete domains cannot be done exactly, the various …