Some of the properties and characteristics of convolution and of the
systems it represents can be better described by a matrix formulation than
by the summation notation. The first LL values of the discrete-time
convolution defined above can be written as a matrix operator on a vector
of inputs to give a vector of the output values.
y
0
y
1
y
2
⋮
y
L
-
1
=
h
0
0
0
⋯
0
h
1
h
0
0
h
2
h
1
h
0
⋮
⋮
h
L
-
1
⋯
h
0
x
0
x
1
x
2
⋮
x
L
-
1
y
0
y
1
y
2
⋮
y
L
-
1
=
h
0
0
0
⋯
0
h
1
h
0
0
h
2
h
1
h
0
⋮
⋮
h
L
-
1
⋯
h
0
x
0
x
1
x
2
⋮
x
L
-
1
(10)If the input sequence xx is of length NN and the operator signal hh is of
length MM, the output is of length L=N+M-1L=N+M-1. This is shown for N=4N=4 and M=3M=3 by the rectangular matrix operation
y
0
y
1
y
2
y
3
y
4
y
5
=
h
0
0
0
0
h
1
h
0
0
0
h
2
h
1
h
0
0
0
h
2
h
1
h
0
0
0
h
2
h
1
0
0
0
h
2
x
0
x
1
x
2
x
3
y
0
y
1
y
2
y
3
y
4
y
5
=
h
0
0
0
0
h
1
h
0
0
0
h
2
h
1
h
0
0
0
h
2
h
1
h
0
0
0
h
2
h
1
0
0
0
h
2
x
0
x
1
x
2
x
3
(11)It is clear that if the system is causal (h(n)=0h(n)=0 for n<0n<0), the HH
matrix is lower triangular. It is also easy to see that the system being
time-invariant is equivalent to the matrix being Toeplitz [1].
This formulation makes it obvious that if a certain output were desired
from 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 seems
most natural, the matrix could have been formulated from the input and the
vector would have been the impulse response. Indeed, this might the
appropriate formulation if one were specifying the input and output and
designing the system.
The basic convolution defined in Equation 2, derived in Equation 3,
and given in matrix form in Equation 10 relates the input to the
output for linear systems. This is
the form of convolution that is related to multiplication of the DTFT and
z-transform of signals. However, it is cyclic convolution that is
fundamentally 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
y
0
y
1
y
2
⋮
y
L
-
1
=
h
0
h
L
-
1
h
L
-
2
⋯
h
1
h
1
h
0
h
L
-
1
h
2
h
2
h
1
h
0
h
3
⋮
⋮
h
L
-
1
⋯
h
0
x
0
x
1
x
2
⋮
x
L
-
1
y
0
y
1
y
2
⋮
y
L
-
1
=
h
0
h
L
-
1
h
L
-
2
⋯
h
1
h
1
h
0
h
L
-
1
h
2
h
2
h
1
h
0
h
3
⋮
⋮
h
L
-
1
⋯
h
0
x
0
x
1
x
2
⋮
x
L
-
1
(12)This matrix description makes it clear that the matrix operator is always
square and the three signals, x(n)x(n), h(n)h(n), and y(n)y(n), are necessarily
of the same length.
There are several useful conclusions that can be drawn from linear algebra
[1]. The eigenvalues of the non-cyclic are all the same since
the eigenvalues of a lower triangular matrix are simply the values on the
diagonal.
Although it is less obvious, the eigenvalues of the cyclic convolution
matrix are the NN values of the DFT of h(n)h(n) and the eigenvectors are
the basis functions of the DFT which are the column vectors of the DFT
matrix. The eigenvectors are completely controlled by the structure of
HH being a cyclic convolution matrix and are not at all a function of the
values of h(n)h(n). The DFT matrix equation from Equation 10 is given by
X
=
Fx
and
Y
=
Fy
X
=
Fx
and
Y
=
Fy
(13)where XX is the length-N vector of the DFT values, HH is the
matrix operator for the DFT, and xx is the length-N
vector of the signal x(n)x(n) values. The same is true for the comparable
terms in yy.
The matrix form of the length-N cyclic convolution in Equation 10 is written
Taking the DFT both sides and using the IDFT on xx gives
Fy
=
Y
=
FHx
=
FHF
-
1
X
Fy
=
Y
=
FHx
=
FHF
-
1
X
(15)If we define the diagonal matrix HdHd as an LL by LL matrix with
the values of the DFT of h(n)h(n) on its diagonal, the convolution property
of the DFT becomes
This implies
H
d
=
FHF
-
1
and
H
=
F
-
1
H
d
F
H
d
=
FHF
-
1
and
H
=
F
-
1
H
d
F
(17)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)h(n) and the
eigenvectors are the orthogonal columns of FF. The DFT matrix
diagonalizes the cyclic convolution matrix. This is probably the most
concise 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 the
DFT. The answer is easy to see using the matrix description of HH. The
length of the output of non-cyclic convolution is N+M-1N+M-1. If N-1N-1 zeros
are appended to the end of h(n)h(n) and M-1M-1 zeros are appended to the end of
x(n)x(n), the cyclic convolution of these two augmented signals will produce
exactly the same N+M-1N+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
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
(18)Just enough zeros were appended so that the nonzero terms in the upper
right-hand corner of HH are multiplied by the zeros in the lower
part of xx and, therefore, do not contribute to yy.
This does require convolving longer signals but the output is exactly what
we want and we calculated it with the DFT-compatible cyclic convolution.
Note that more zeros could have been appended to hh and xx and the first
N+M-1N+M-1 terms of the output would have been the same only more
calculations would have been necessary. This is sometimes done in order
to use forms of the FFT that require that the length be a power of two.
If fewer zeros or none had been appended to hh and xx, the nonzero
terms in the upper right-hand corner of HH, which are the “tail" of
h(n)h(n), would have added the values that would have been at the end of the
non-cyclic output of y(n)y(n) to the values at the beginning. This is a
natural part of cyclic convolution but is destructive if non-cyclic
convolution is desired and is called aliasing or folding for obvious
reasons. Aliasing is a phenomenon that occurs in several arenas of DSP
and the matrix formulation makes it easy to understand.
