1.2 Discrete-time systems  (Page 4/5)

If we define the diagonal matrix ${\mathbf{H}}_{\mathbf{d}}$ as an $L$ by $L$ matrix with the values of the DFT of $h\left(n\right)$ on its diagonal, the convolution property of the DFT becomes

This implies

which is the basis of the earlier statement that the eigenvalues of the cyclic convolution matrix are the values of the DFT of $h\left(n\right)$ and the eigenvectors are the orthogonal columns of $\mathbf{F}$ . The DFT matrix diagonalizes the cyclic convolution matrix. This is probably the mostconcise statement of the relation of the DFT to convolution and to linear systems.

An important practical question is how one calculates the non-cyclic convolution needed by system analysis using the cyclic convolution of theDFT. The answer is easy to see using the matrix description of $H$ . The length of the output of non-cyclic convolution is $N+M-1$ . If $N-1$ zeros are appended to the end of $h\left(n\right)$ and $M-1$ zeros are appended to the end of $x\left(n\right)$ , the cyclic convolution of these two augmented signals will produce exactly the same $N+M-1$ values as non-cyclic convolution would. This is illustrated for the example considered before.

Just enough zeros were appended so that the nonzero terms in the upper right-hand corner of $\mathbf{H}$ are multiplied by the zeros in the lower part of $\mathbf{x}$ and, therefore, do not contribute to $\mathbf{y}$ . This does require convolving longer signals but the output is exactly whatwe want and we calculated it with the DFT-compatible cyclic convolution. Note that more zeros could have been appended to $h$ and $x$ and the first $N+M-1$ terms of the output would have been the same only more calculations would have been necessary. This is sometimes done in orderto use forms of the FFT that require that the length be a power of two.

If fewer zeros or none had been appended to $h$ and $x$ , the nonzero terms in the upper right-hand corner of $\mathbf{H}$ , which are the “tail" of $h\left(n\right)$ , would have added the values that would have been at the end of the non-cyclic output of $y\left(n\right)$ to the values at the beginning. This is a natural part of cyclic convolution but is destructive if non-cyclicconvolution is desired and is called aliasing or folding for obvious reasons. Aliasing is a phenomenon that occurs in several arenas of DSPand the matrix formulation makes it easy to understand.

The z-transform transfer function

Although the time-domain convolution is the most basic relationship of the input to the output for linear systems, the z-transform is a close secondin importance. It gives different insight and a different set of tools for analysis and design of linear time-invariant discrete-time systems.

If our system in linear and time-invariant, we have seen that its output is given by convolution.

Assuming that $h\left(n\right)$ is such that the summation converges properly, we can calculate the output to an input that we already know has a specialrelation with discrete-time transforms. Let $x\left(n\right)=z^n$ which gives

With the change of variables of $k=n-m$ , we have