Discrete-time Filter as a Matrix Operation 2.2 2003/03/19 2003/04/14 Ivan Selesnick selesi@taco.poly.edu Erin Maloney emaloney@rice.edu Ivan Selesnick selesi@taco.poly.edu allpass convolution filter orthogonal transformation Toeplitz Matrix Consider a linear time-invariant system with impulse response h n . (Is assumed in these notes that all impulses response h n are real-valued.) ()

The block diagram is represented in matrix form as ⋮ 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 ⋱ ⋱ 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: ⇔ y n h n x n y Q x where Q is the convolution matrix. The matrix Q is also called the Toeplitz matrix - a Toeplitz matrix is constant along its diagonals. Note that the impulse response h n appears in each column of the matrix Q. What is the transpose of the linear time-invariant system with impulse response 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 Q. The columns of Q are the rows of Q , so Q has the following form: 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 Q is again a convolution matrix (it is constant along the diagonals). So Q represents a linear time-invariant system. The impulse response of this system can be found by looking at the columns of Q , which we see is the flipped version of h n . Therefore, Q represents convolution by h n . ()

⇔ y Q x y n h n x n ⇔ z Q y z n h n y n Can the filter h n represent an orthogonal transformation? Equivalently, is it possible that Q is the inverse of Q? If Q Q I , then z Q y Q Q x I x x or z n x n . But z n h n y n h n h n x n so z n x n only if h n h n δ n Note that ⇔ h n h n δ n H1z Hz 1 H ω H ω 1 H ω 2 1 That means 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 x n .