<< Chapter < Page Chapter >> Page >
Fy = Y = FHx = FHF - 1 X

If we define the diagonal matrix H d as an L by L matrix with the values of the DFT of h ( n ) on its diagonal, the convolution property of the DFT becomes

Y = H d X

This implies

H d = FHF - 1 and H = F - 1 H d F

which is the basis of the earlier statement that the eigenvalues of the cyclic convolution matrix are the values of the DFT of h ( n ) and the eigenvectors are the orthogonal columns of 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 ( n ) and M - 1 zeros are appended to the end of x ( n ) , 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.

y 0 y 1 y 2 y 3 y 4 y 5 = h 0 0 0 0 h 2 h 1 h 1 h 0 0 0 0 h 2 h 2 h 1 h 0 0 0 0 0 h 2 h 1 h 0 0 0 0 0 h 2 h 1 h 0 0 0 0 0 h 2 h 1 h 0 x 0 x 1 x 2 x 3 0 0

Just enough zeros were appended so that the nonzero terms in the upper right-hand corner of H are multiplied by the zeros in the lower part of x and, therefore, do not contribute to 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 H , which are the “tail" of h ( n ) , would have added the values that would have been at the end of the non-cyclic output of y ( n ) 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.

y ( n ) = m = - h ( n - m ) x ( m )

Assuming that h ( n ) 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 ( n ) = z n which gives

y ( n ) = m = - h ( n - m ) z m

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

y ( n ) = k = - h ( k ) z n - k = [ k = - h ( k ) z - k ] z n

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Digital signal processing and digital filter design (draft). OpenStax CNX. Nov 17, 2012 Download for free at http://cnx.org/content/col10598/1.6
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Digital signal processing and digital filter design (draft)' conversation and receive update notifications?

Ask