Digital Signal processing - Chapter 4: Fir filtering and convolution

Click to edit Master subtitle style Nguyen Thanh Tuan, M.Eng. Department of Telecommunications (113B3) Ho Chi Minh City University of Technology Email: nttbk97@yahoo.com FIR filtering and Convolution Chapter 4 Digital Signal Processing Content 2 FIR Filtering and Convolution  Block processing methods  Convolution: direct form, convolution table  Convolution: LTI form, LTI table  Matrix form  Flip-and-slide form  Overlap-add block convolution method  Sample processing methods  FIR filtering in direct form Digital Signal Processing Introduction 3  Block processing methods: data are collected and processed in blocks. FIR Filtering and Convolution  FIR filtering of finite-duration signals by convolution  Fast convolution of long signals which are broken up in short segments  DFT/FFT spectrum computations  Speech analysis and synthesis  Image processing  Sample processing methods: the data are processed one at a time- with each input sample being subject to a DSP algorithm which transforms it into an output sample.  Real-time applications  Digital audio effects processing  Digital control systems  Adaptive signal processing Digital Signal Processing 1. Block Processing method 4  The collected signal samples x(n), n=0, 1,, L-1, can be thought as a block: The duration of the data record in second: TL=LT x=[x0, x1, , xL-1]  Consider a casual FIR filter of order M with impulse response: h=[h0, h1, , hM] The length (the number of filter coefficients): Lh=M+1 FIR Filtering and Convolution Digital Signal Processing 11.1. Direct form 5  The convolution in the direct form:  Find index n: index of h(m)  0≤m≤M ( ) ( ) ( ) m y n h m x n m   For DSP implementation, we must determine  The range of values of the output index n  The precise range of summation in m index of x(n-m)  0≤n-m≤L-1  0 ≤ m ≤ n ≤m+L-1 ≤ M+L-1 0 n M L 1     Lx=L input samples which is processed by the filter with order M yield the output signal y(n) of length yL L M=L Mx   FIR Filtering and Convolution Digital Signal Processing 1Direct form 6  Find index m: index of h(m)  0≤m≤M index of x(n-m)  0≤n-m≤L-1  n+L-1≤ m ≤ n    max 0, n L 1 m min M, n    min( , ) max(0, 1) ( ) ( ) ( ) M n m n L y n h m x n m        h x  The direct form of convolution is given as follows: FIR Filtering and Convolution 0 n M L 1    with  Thus, y is longer than the input x by M samples. This property follows from the fact that a filter of order M has memory M and keeps each input sample inside it for M time units. Digital Signal Processing Example 1 7  Consider the case of an order-3 filter and a length of 5-input signal. Find the output ? FIR Filtering and Convolution h=[h0, h1, h2, h3] x=[x0, x1, x2, x3, x4 ] y=h*x=[y0, y1, y2, y3, y4 , y5, y6, y7 ] Digital Signal Processing 1.2. Convolution table 8  It can be observed that FIR Filtering and Convolution , ( ) ( ) ( ) i j i j n y n h i x j      Convolution table  The convolution table is convenient for quick calculation by hand because it displays all required operations compactly. Digital Signal Processing Example 2 9  Calculate the convolution of the following filter and input signals? FIR Filtering and Convolution h=[1, 2, -1, 1], x=[1, 1, 2, 1, 2, 2, 1, 1]  Solution: sum of the values along anti-diagonal line yields the output y: y=[1, 3, 3, 5, 3, 7, 4, 3, 3, 0, 1] Note that there are Ly=L+M=8+3=11 output samples. Digital Signal Processing 1.3. LTI Form 10  LTI form of convolution: FIR Filtering and Convolution ( ) ( ) ( ) m y n x m h n m  0 1 2 3 4( ) ( ) ( 1) ( 2) ( 3) ( 4)y n x h n x h n x h n x h n x h n          Consider the filter h=[h0, h1, h2, h3] and the input signal x=[x0, x1, x2, x3, x4 ]. Then, the output is given by We can represent the input and output signals as blocks: Digital Signal Processing 1.3. LTI Form 11 FIR Filtering and Convolution  LTI form of convolution:  LTI form of convolution provides a more intuitive way to under stand the linearity and time-invariance properties of the filter. Digital Signal Processing Example 3 12 FIR Filtering and Convolution  Using the LTI form to calculate the convolution of the following filter and input signals? h=[1, 2, -1, 1], x=[1, 1, 2, 1, 2, 2, 1, 1]  Solution: Digital Signal Processing 1.4. Matrix Form 13 FIR Filtering and Convolution  Based on the convolution equations y Hx  x is the column vector of the Lx input samples.  y is the column vector of the Ly =Lx+M put samples.  H is a rectangular matrix with dimensions (Lx+M)xLx . we can write Digital Signal Processing 1.4. Matrix Form 14 FIR Filtering and Convolution  It can be observed that H has the same entry along each diagonal. Such a matrix is known as Toeplitz matrix. Matrix representations of convolution are very useful in some applications:  Image processing  Advanced DSP methods such as parametric spectrum estimation and adaptive filtering Digital Signal Processing Example 4 15 FIR Filtering and Convolution  Using the matrix form to calculate the convolution of the following filter and input signals? h=[1, 2, -1, 1], x=[1, 1, 2, 1, 2, 2, 1, 1]  Solution: since Lx=8, M=3  Ly=Lx+M=11, the filter matrix is 11x8 dimensional Digital Signal Processing 1.5. Flip-and-slide form 16 FIR Filtering and Convolution 0 1 1 ...n n n M n My h x h x h x      The output at time n is given by  Flip-and-slide form of convolution  The flip-and-slide form shows clearly the input-on and input-off transient and steady-state behavior of a filter. Digital Signal Processing 1.6. Transient and steady-state behavior 17 FIR Filtering and Convolution  Transient and steady-state filter outputs:  From LTI convolution: 0 1 1 0 ( ) ( ) ( ) ... M n n M n M m y n h m x n m h x h x h x          The output is divided into 3 subranges: Digital Signal Processing 1.7. Overlap-add block convolution method 18 FIR Filtering and Convolution Overlap-add block convolution method:  As the input signal is infinite or extremely large, a practical approach is to divide the long input into contiguous non-overlapping blocks of manageable length, say L samples. Digital Signal Processing Example 5 19 FIR Filtering and Convolution  Using the overlap-add method of block convolution with each bock length L=3, calculate the convolution of the following filter and input signals? h=[1, 2, -1, 1], x=[1, 1, 2, 1, 2, 2, 1, 1]  Solution: The input is divided into block of length L=3 The output of each block is found by the convolution table: Digital Signal Processing Example 5 20 FIR Filtering and Convolution  The output of each block is given by  Following from time invariant, aligning the output blocks according to theirs absolute timings and adding them up gives the final results: Digital Signal Processing 2. Sample processing methods 21 FIR Filtering and Convolution  The direct form convolution for an FIR filter of order M is given by Fig: Direct form realization of Mth order filter Sample processing algorithm  Introduce the internal states  Sample processing methods are convenient for real-time applications Digital Signal Processing Example 6 22 FIR Filtering and Convolution  Consider the filter and input given by Using the sample processing algorithm to compute the output and show the input-off transients. Digital Signal Processing Example 6 23 FIR Filtering and Convolution Digital Signal Processing Example 24 FIR Filtering and Convolution Digital Signal Processing Hardware realizations 25 FIR Filtering and Convolution  The FIR filtering algorithm can be realized in hardware using DSP chips, for example the Texas Instrument TMS320C25 MAC: Multiplier Accumulator Digital Signal Processing Hardware realizations 26 FIR Filtering and Convolution  The signal processing methods can efficiently rewritten as  In modern DSP chips, the two operations can carried out with a single instruction.  The total processing time for each input sample of Mth order filter: where Tinstr is one instruction cycle in about 30-80 nanoseconds.  For real-time application, it requires that Digital Signal Processing Example 7 27 FIR Filtering and Convolution What is the longest FIR filter that can be implemented with a 50 nsec per instruction DSP chip for digital audio applications with sampling frequency fs=44.1 kHz ? Solution: Digital Signal Processing Homework 1 28 FIR Filtering and Convolution Digital Signal Processing Homework 2 29 FIR Filtering and Convolution Digital Signal Processing Homework 3 30 FIR Filtering and Convolution Digital Signal Processing Homework 4 31 FIR Filtering and Convolution  Compute the output y(n) of the filter h(n) = {1, -1, 1, -1} and input x(n) = {1, 2, 3, 4, @, -3, 2, -1} Digital Signal Processing Homework 5 32  Compute the convolution, y = h ∗ x, of the filter and input, h(n) = {1, -1, -1, 1} , x(n) = {1, 2, 3, 4, @, -3, 2, -1} using the following methods: 1. The convolution table. 2. The LTI form of convolution, arranging the computations in a table form. 3. The overlap-add method of block convolution with length-3 input blocks. 4. The overlap-add method of block convolution with length-4 input blocks. 5. The overlap-add method of block convolution with length-5 input blocks. FIR Filtering and Convolution