Discrete-time Filter as a Matrix Operation

Module by: Ivan Selesnick

Consider a linear time-invariant system with impulse response hn h n . (Is assumed in these notes that all impulses response hn h n are real-valued.) (Figure 1)

Figure 1

The block diagram is represented in matrix form as ⋮y0y1y2y3y4y5y6⋮=⋱⋱h0000⋱h1h000⋱h2h1h00⋱h3h2h1h00h3h2h1⋱00h3h2⋱000h3⋱⋱⋮x0x1x2x3x4x5x6⋮ ⋮ y0 y1 y2 y3 y4 y5 y6 ⋮ ⋱ ⋱ h0 000 ⋱ h1 h0 00 ⋱ h2 h1 h0 0 ⋱ h3 h2 h1 h0 0 h3 h2 h1 ⋱ 00 h3 h2 ⋱ 000 h3 ⋱ ⋱ ⋮ x0 x1 x2 x3 x4 x5 x6 ⋮ where Q=⋱⋱h0000⋱h1h000⋱h2h1h00⋱h3h2h1h00h3h2h1⋱00h3h2⋱000h3⋱⋱ Q ⋱ ⋱ h0 000 ⋱ h1 h0 00 ⋱ h2 h1 h0 0 ⋱ h3 h2 h1 h0 0 h3 h2 h1 ⋱ 00 h3 h2 ⋱ 000 h3 ⋱ ⋱

The vectors are of infinite length. The matrix has infinitely many rows and infinitely many columns. We can write convolution as a matrix-vector multiplication: yn=hn*xn⇔y=Qx ⇔ y n h n x n y Q x where QQ is the convolution matrix. The matrix QQ is also called the Toeplitz matrix - a Toeplitz matrix is constant along its diagonals. Note that the impulse response hnh n appears in each column of the matrix QQ.

What is the transpose of the linear time-invariant system with impulse response hn h n ? Usually, we do not think about the transpose of a system. However, we can derive the transpose of the system by using the matrix representation. We just need to look at the transpose of the matrix QQ. The columns of QQ are the rows of QT Q , so QT Q has the following form: QT=⋱⋱h3000⋱h2h300⋱h1h2h30⋱h0h1h2h30h0h1h2⋱00h0h1⋱000h0⋱⋱ Q ⋱ ⋱ h3 000 ⋱ h2 h3 00 ⋱ h1 h2 h3 0 ⋱ h0 h1 h2 h3 0 h0 h1 h2 ⋱ 00 h0 h1 ⋱ 000 h0 ⋱ ⋱ We can observe that QT Q is again a convolution matrix (it is constant along the diagonals). So QT Q represents a linear time-invariant system. The impulse response of this system can be found by looking at the columns of QT Q , which we see is the flipped version of hn h n . Therefore, QT Q represents convolution by h-n h n . (Figure 2)

Figure 2

y=Qx⇔yn=hn*xn ⇔ y Q x y n h n x n z=QTy⇔zn=h-n*yn ⇔ z Q y z n h n y n Can the filter hn h n represent an orthogonal transformation? Equivalently, is it possible that QT Q is the inverse of QQ? If QTQ=I Q Q I , then z=QTy=QTQx=Ix=x z Q y Q Q x I x x or zn=xn z n x n . But

Note that h-n*hn=δn⇔H1zHz=1⇔H-ⅇⅈωHⅇⅈω=1⇔|Hⅇⅈω|2=1 ⇔ h n h n δ n H1z Hz 1 H ω H ω 1 H ω 2 1 That means Hz Hz must be an allpass system. The only orthonormal LTI systems are allpass systems. But they provide no frequency selective filtering - the allpass filter does not provide a subband decomposition of the signal xn x n .

Comments, questions, feedback, criticisms?

Send feedback

• E-mail the author of the module, Discrete-time Filter as a Matrix Operation

Footer

More about this content: Metadata | Version History

• How to reuse and attribute this content
• How to Cite and attribute this content

This work is licensed by Ivan Selesnick under a Creative Commons Attribution License (CC-BY 1.0).

Last edited by Charlet Reedstrom on Aug 13, 2005 11:05 am GMT-5.