Scribd Logo
Upload

Welcome to Scribd!

  • 76 views

    FIR Filtering and Convolution

    Uploaded by

    Thành Vinh Phạm
    This document discusses methods for FIR filtering and convolution, including block processing and sample processing. For block processing, it describes direct form, convolution table, LTI form, matrix form, flip-and-slide form, and overlap-add block convolution. For sample processing, it discusses direct form FIR filtering. It provides examples to illustrate the different methods.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    FIR Filtering and Convolution

    Uploaded by

    Thành Vinh Phạm
    76 views32 pages
    This document discusses methods for FIR filtering and convolution, including block processing and sample processing. For block processing, it describes direct form, convolution table, LTI form, matrix form, flip-and-slide form, and overlap-add block convolution. For sample processing, it discusses direct form FIR filtering. It provides examples to illustrate the different methods.

    Original Title

    DSP-Chapter4_student_20022017

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses methods for FIR filtering and convolution, including block processing and sample processing. For block processing, it describes direct form, convolution table, LTI form, matrix form, flip-and-slide form, and overlap-add block convolution. For sample processing, it discusses direct form FIR filtering. It provides examples to illustrate the different methods.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    76 views32 pages

    FIR Filtering and Convolution

    Uploaded by

    Thành Vinh Phạm
    This document discusses methods for FIR filtering and convolution, including block processing and sample processing. For block processing, it describes direct form, convolution table, LTI form, matrix form, flip-and-slide form, and overlap-add block convolution. For sample processing, it discusses direct form FIR filtering. It provides examples to illustrate the different methods.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 32

    Chapter 4

    FIR filtering and Convolution


    Nguyen Thanh Tuan, Click
    M.Eng.
    to edit Master subtitle style
    Dang Ngoc Hanh, M.Eng.
    Department of Telecommunications (113B3)
    Ho Chi Minh City University of Technology hanhdn@hcmut.edu.vn
    Email: nttbk97@yahoo.com
    Content

     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 2 FIR Filtering and Convolution


    Introduction

     Block processing methods: data are collected and processed in blocks.


     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 3 FIR Filtering and Convolution


    1. Block Processing method

     The collected signal samples x(n), n=0, 1,…, L-1, can be thought as a
    block:
    x=[x0, x1, …, xL-1]

    The duration of the data record in second: TL=LT

     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

    Digital Signal Processing 4 FIR Filtering and Convolution


    11.1. Direct form

     The convolution in the direct form:


    y ( n )   h ( m) x ( n  m )
    m

     For DSP implementation, we must determine


     The range of values of the output index n
     The precise range of summation in m

     Find index n: index of h(m)  0≤m≤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 L y  L  M=L x  M
    Digital Signal Processing 5 FIR Filtering and Convolution
    1Direct form

     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 

     The direct form of convolution is given as follows:


    min( M , n )
    y ( n)  
    m  max(0, n  L 1)
    h( m) x ( n  m)  h  x with 0   n   M  L  1

     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 6 FIR Filtering and Convolution


    Example 1

     Consider the case of an order-3 filter and a length of 5-input signal.


    Find the output ?

    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 7 FIR Filtering and Convolution


    1.2. Convolution table

     It can be observed that y ( n)   h(i) x( j )


    i, j
    i j n

     Convolution table

     The convolution
    table is convenient
    for quick calculation
    by hand because it
    displays all required
    operations
    compactly.

    Digital Signal Processing 8 FIR Filtering and Convolution


    Example 2

     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:

    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 9 FIR Filtering and Convolution


    1.3. LTI Form

     LTI form of convolution: y ( n)   x ( m) h( n  m)


    m
     Consider the filter h=[h0, h1, h2, h3] and the input signal x=[x0, x1, x2,
    x3, x4 ]. Then, the output is given by
    y (n)  x0 h(n)  x1h(n  1)  x2 h(n  2)  x3 h(n  3)  x4 h(n  4)
     We can represent the input and output signals as blocks:

    Digital Signal Processing 10 FIR Filtering and Convolution


    1.3. LTI Form

     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 11 FIR Filtering and Convolution
    Example 3

     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 12 FIR Filtering and Convolution


    1.4. Matrix Form

     Based on the convolution equations

    we can write 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 .

    Digital Signal Processing 13 FIR Filtering and Convolution


    1.4. Matrix Form

     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 14 FIR Filtering and Convolution


    Example 4
     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 15 FIR Filtering and Convolution


    1.5. Flip-and-slide form

     The output at time n is given by


    yn  h0 xn  h1 xn 1  ...  hM xn  M

     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 16 FIR Filtering and Convolution
    1.6. Transient and steady-state behavior
    M
     From LTI convolution: y(n)  h(m) x(n  m)  h0 xn  h1xn1  ...  hM xnM
    m0
     The output is divided into 3 subranges:

     Transient and steady-state filter outputs:

    Digital Signal Processing 17 FIR Filtering and Convolution


    1.7. 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.
     Overlap-add block convolution method:

    Digital Signal Processing 18 FIR Filtering and Convolution


    Example 5
     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 19 FIR Filtering and Convolution


    Example 5
     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 20 FIR Filtering and Convolution


    2. Sample processing methods
     The direct form convolution for an FIR filter of order M is given by

     Introduce the internal states

    Sample processing algorithm

    Fig: Direct form realization  Sample processing methods are


    of Mth order filter convenient for real-time applications
    Digital Signal Processing 21 FIR Filtering and Convolution
    Example 6
     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 22 FIR Filtering and Convolution


    Example 6

    Digital Signal Processing 23 FIR Filtering and Convolution


    Example

    Digital Signal Processing 24 FIR Filtering and Convolution


    Hardware realizations
     The FIR filtering algorithm can be realized in hardware using DSP
    chips, for example the Texas Instrument TMS320C25

     MAC: Multiplier
    Accumulator

    Digital Signal Processing 25 FIR Filtering and Convolution


    Hardware realizations

     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 26 FIR Filtering and Convolution


    Example 7

     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 27 FIR Filtering and Convolution


    Homework 1

    Digital Signal Processing 28 FIR Filtering and Convolution


    Homework 2

    Digital Signal Processing 29 FIR Filtering and Convolution


    Homework 3

    Digital Signal Processing 30 FIR Filtering and Convolution


    Homework 4

     Compute the output y(n) of the lter h(n) = {1, -1, 1, -1} and input
    x(n) = {1, 2, 3, 4, @, -3, 2, -1}

    Digital Signal Processing 31 FIR Filtering and Convolution


    Homework 5

     Compute the convolution, y = h x, of the lter 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.

    Digital Signal Processing 32 FIR Filtering and Convolution

    You might also like