An infinite Toeplitz matrix implements, in principle, acyclic
convolution (which is what we normally mean when we just say
``convolution''). In practice, the convolution of a signal
and an
impulse response
, in which both
and
are more than a
hundred or so samples long, is typically implemented fastest using
FFT convolution (i.e., performing fast convolution using the
Fast Fourier Transform (FFT)
[84]F.3). However, the FFT computes
cyclic convolution unless sufficient zero padding is used
[84]. The matrix representation of cyclic (or ``circular'')
convolution is a circulant matrix, e.g.,
As in this example, each row of a circulant matrix is obtained from the previous row by a circular right-shift. Circulant matrices are thus always Toeplitz (but not vice versa). Circulant matrices have many interesting properties.F.4 For example, the eigenvectors of an
The DFT eigenstructure of circulant matrices is directly related to
the DFT convolution theorem [84]. The above
circulant matrix
, when multiplied times a length 6 vector
,
implements cyclic convolution of
with
.
Using the DFT to perform the circular convolution can be expressed as
where `
Premultiplying by the IDFT matrix
yields
Thus, the DFT convolution theorem holds if and only if the circulant convolution matrix