Bài giảng Digital Signal Processing - Chapter 4: FIR Filtering and Convolution - Võ Trung Dũng

where T is the sampling time interval
 Number of time samples L: 
2Block Processing Methods – Convolution - cont
 Input block: is L collected signal samples:
 Direct and LTI forms of convolution:
 Sum of the indices notice:
 Convolution table form:
Block Processing Methods – Direct Form
 Block of impulse response: Consider a causal FIR filter of order M with impulse 
response h(n), n = 0, 1, . . . , M:
 Filter’s length:
 Index determination requirement:
(i) the range of values of the output index n, and 
(ii) the precise range of summation in m
 Range of indices h(m):
 Range of indices x(n − m): 
or
or 
This is the index range of the output sequence y(n)
Block Processing Methods – Direct Form - cont
 Output sequence:
 Output length:
where
y is longer than the input x by M samples, follows from the fact that a filter of order 
M has memory M
 Relative lengths of filter, input, and output blocks:
Block Processing Methods – Direct Form - cont
 Filter index’s range:
or
 Direct form of convolution:
for n = 0, 1, . . . , L+M−1.
 Compact notation:
3Block Processing Methods – Direct Form - cont
 Example: consider the case of an order-3 filter and a length-5 input signal
output length:
convolutional equation:
for example, at n = 5:
Block Processing Methods – Direct Form - cont
 All output samples:
Block Processing Methods – Convolution Table
 Note: each output yn is the sum of all possible products hixj with i + j = n
 Convolution table: 
 Calculation: entries within each antidiagonal strip are summed together to form 
the corresponding output value:
The convolution table is convenient for quick calculation by hand because it displays
all required operations compactly
Block Processing Methods – Convolution Table - cont
 Example: calculate the convolution of the following filter and input signals
Solution: the convolution table, with h arranged vertically and x horizontally, is
Folding the table
Number of output samples
4Block Processing Methods – LTI Form
 Input: as a linear combination of delayed impulses
or
 Output: 
Block Processing Methods – LTI Form - cont
 Blocks of input and output signals:
 Linear combinations of right-hand side: 
Block Processing Methods – LTI Form - cont
 LTI form of convolution:
 Calculation: the rows of the table correspond to the successive delays (right
shifts) of the h sequence—the mth row corresponds to delay by m units. Each row is 
scaled by the corresponding input sample, that is, the mth row represents the term 
xmhn-m in the LTI form. After the table is filled, the table entries are summed 
column-wise to obtain the output samples y(n)
Block Processing Methods – LTI Form - cont
 Example: calculate the convolution of the following filter and input signals
Solution: the convolution table, with h arranged vertically and x horizontally, is
5Block Processing Methods – Matrix Form
 Linear matrix form:
 Filter matrix H: must be rectangular with dimensions
 Matrix form: columns of H are the successively delayed replicas of the impulse
response vector h. H is Toeplitz matrix, which has the same entry along each 
diagonal
Block Processing Methods – Matrix Form Form - cont
 Example: calculate the convolution using the matrix form
Solution: Because Ly = 11 and Lx = 8, the filter matrix will be 11 × 8 dimensional
Block Processing Methods – Matrix Form
 Alternative matrix form:
 Compact form:
 Data matrix X dimension:
Block Processing Methods – Matrix Form Form - cont
 Example: calculate the convolution using the matrix form
Solution: The X matrix will have dimension Ly×Lh = 11×4. Its first column is the 
input signal padded with 3 zeros at the end
Matrix representations of convolution are very useful in some applications, such as
image processing, and in more advanced DSP methods such as parametric spectrum
estimation and adaptive filtering
6Block Processing Methods – Flip-and-Slide Form
 Flip-and-slide form of convolution: filter h(n) is flipped around or reversed 
and then slid over the input data sequence
 Calculation: output sample is obtained by computing the dot product of the 
flipped filter vector h with the M+1 input samples aligned below it. The input 
sequence is assumed to have been extended by padding M zeros to its left and to 
its right.
Block Processing Methods – Flip-and-Slide Form - cont
 Input-on transient: At time n = 0, the only nonzero contribution to the dot 
product comes from h0 and x0 which are time aligned. It takes the filter M time 
units before it is completely over the nonzero portion of the input sequence. The 
first M outputs correspond to the input-on transient behavior of the filter
 Steady-state: for a period of time M ≤ n ≤ L−1, the filter remains completely 
over the nonzero portion of the input data, and the outputs are given by the form
 Input-off transients: During this period the filter slides over the last M zeros 
padded at the end of the input
Block Processing Methods – Transient and Steady-
State Behavior
 Time index n range:
 Three subranges:
 Transient and steady-state filter outputs:
Block Processing Methods – Transient and Steady-
State Behavior
 LTI form:
 Transient and steady-state filter outputs:
7Block Processing Methods – Convolution of Infinite 
Sequences
 LTI form:
 Three cases of infinite Sequences:
1. Infinite filter, finite input; i.e., M =∞, L < ∞.
2. Finite filter, infinite input; i.e.,M <∞, L=∞.
3. Infinite filter, infinite input; i.e., M =∞, L=∞.
 Output of these three cases of infinite Sequences:
Block Processing Methods – Convolution of Infinite 
Sequences
 Example: An IIR filter has impulse response h(n)= (0.75)nu(n). Using 
convolution, derive closed-form expressions for the output signal y(n) when the 
input is:
(a) A unit step, x(n)= u(n).
(b) An alternating step, x(n)= (−1)nu(n).
(c) A square pulse of duration L = 25 samples, x(n)= u(n)−u(n − 25).
In each case, determine the steady-state response of the filter.
 Solution:
(a) because both the input and filter are causal and have infinite duration, we
use the formula:
The steady-state response is the large-n limit of this formula, that is, as n→∞
Block Processing Methods – Convolution of Infinite 
Sequences
 Example: An IIR filter has impulse response h(n)= (0.75)nu(n). Using 
convolution, derive closed-form expressions for the output signal y(n) when the 
input is:
(a) A unit step, x(n)= u(n).
(b) An alternating step, x(n)= (−1)nu(n).
(c) A square pulse of duration L = 25 samples, x(n)= u(n)−u(n − 25).
In each case, determine the steady-state response of the filter.
 Solution:
(b) :
The steady-state response is the large-n limit of this formula, that is, as n→∞
Block Processing Methods – Convolution of Infinite 
Sequences
 Example: An IIR filter has impulse response h(n)= (0.75)nu(n). Using 
convolution, derive closed-form expressions for the output signal y(n) when the 
input is:
(c) A square pulse of duration L = 25 samples, x(n)= u(n)−u(n − 25).
 Solution:
(c) :
For 0 ≤ n ≤ 24
for 25 ≤ n < ∞,
which corresponds to the input-off transient behavior
8Block Processing Methods – Overlap-Add Block 
Convolution Method
 Infinite or extremely long input: divide the long input into contiguous non-
overlapping blocks of manageable length, say L samples, then filter each block and 
piece the output blocks together to obtain the overall output:
Block Processing Methods – Overlap-Add Block 
Convolution Method
 Example: calculate the convolution using the matrix form
using the overlap-add method of block convolution. Use input blocks of length L = 
3. Perform the required individual convolutions of using the convolution table
Solution: The input is divided into the following three contiguous blocks
Convolving each block separately with h = [1, 2,−1, 1] gives:
Block Processing Methods – Overlap-Add 
Block Convolution Method
These convolutions can be done by separately folding the three convolution 
subtables
Aligning the output blocks according to their absolute timings and adding
them up gives the final result:
 Basic building blocks of DSP systems:
 Single delay:
 Internal state of the filter
Sample Processing Methods – FIR direct form
9 Two processing steps:
 Table of values:
 Output:
Sample Processing Methods – FIR direct form
 Double delay:
 I/O equations:
 Table of values:
Sample Processing Methods – FIR direct form
 D unit delay:
 I/O equations:
Sample Processing Methods – FIR direct form
 I/O equation of a third-order filter:
In order to mechanize this equation, we need to use an adder to accumulate the 
sum of products in the right-hand side; we need multipliers to implement the 
multiplications by the filter weights; and, we need delays to implement the delayed 
terms x(n − 1), x(n − 2), x(n − 3)
Sample Processing Methods – FIR direct form
10
 Three internal states w1(n), w2(n), w3(n):
Output:
Sample Processing Methods – FIR direct form
 I/O equation:
 Block diagram form
Sample Processing Methods – FIR direct form
 Direct form realization of Mth order filter:
Sample Processing Methods – FIR direct form
 Example: Determine the sample processing algorithm of Example 4.1.1, which 
had filter and input
Then, using the algorithm compute the corresponding output, including the input-off 
transients.
Solution: The I/O equation
output equation and the state updating
Sample Processing Methods – FIR direct form
11
 Example: Determine the sample processing algorithm of Example 4.1.1, which 
had filter and input
Then, using the algorithm compute the corresponding output, including the input-off 
transients.
Solution:
Block diagram realization and sample processing algorithm
Sample Processing Methods – FIR direct form
 Homework: 4.1, 4.2, 4.3, 4.4, 4.5, 4.15, 4.16, 4.17, 4.18
Stability