1.2 Discrete-time systems  (Page 3/5)

The matrix formulation of convolution

Some of the properties and characteristics of convolution and of the systems it represents can be better described by a matrix formulation thanby the summation notation. The first $L$ values of the discrete-time convolution defined above can be written as a matrix operator on a vectorof inputs to give a vector of the output values.

If the input sequence $x$ is of length $N$ and the operator signal $h$ is of length $M$ , the output is of length $L=N+M-1$ . This is shown for $N=4$ and $M=3$ by the rectangular matrix operation

It is clear that if the system is causal ( $h\left(n\right)=0$ for $n<0$ ), the $H$ matrix is lower triangular. It is also easy to see that the system being time-invariant is equivalent to the matrix being Toeplitz [link] . This formulation makes it obvious that if a certain output were desiredfrom a length 4 input, only 4 of the 6 values could be specified and the other 2 would be controlled by them.

Although the formulation of constructing the matrix from the impulse response of the system and having it operate on the input vector seemsmost natural, the matrix could have been formulated from the input and the vector would have been the impulse response. Indeed, this might theappropriate formulation if one were specifying the input and output and designing the system.

The basic convolution defined in [link] , derived in [link] , and given in matrix form in [link] relates the input to the output for linear systems. This isthe form of convolution that is related to multiplication of the DTFT and z-transform of signals. However, it is cyclic convolution that isfundamentally related to the DFT and that will be efficiently calculated by the fast Fourier transform (FFT) developed in Part III of these notes.Matrix formulation of length-L cyclic convolution is given by

This matrix description makes it clear that the matrix operator is always square and the three signals, $x\left(n\right)$ , $h\left(n\right)$ , and $y\left(n\right)$ , are necessarily of the same length.

There are several useful conclusions that can be drawn from linear algebra [link] . The eigenvalues of the non-cyclic are all the same since the eigenvalues of a lower triangular matrix are simply the values on thediagonal.

Although it is less obvious, the eigenvalues of the cyclic convolution matrix are the $N$ values of the DFT of $h\left(n\right)$ and the eigenvectors are the basis functions of the DFT which are the column vectors of the DFTmatrix. The eigenvectors are completely controlled by the structure of $H$ being a cyclic convolution matrix and are not at all a function of the values of $h\left(n\right)$ . The DFT matrix equation from [link] is given by

where $\mathbf{X}$ is the length-N vector of the DFT values, $\mathbf{H}$ is the matrix operator for the DFT, and $\mathbf{x}$ is the length-N vector of the signal $x\left(n\right)$ values. The same is true for the comparable terms in $y$ .

The matrix form of the length-N cyclic convolution in [link] is written

Taking the DFT both sides and using the IDFT on $x$ gives