Cyclic Convolution Matrix

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)
[83]^{6.9}). However, the FFT computes
*cyclic convolution* unless sufficient zero padding is used
[83]. The matrix representation of cyclic (or ``circular'')
convolution is a *circulant matrix*, *e.g.*,

The DFT eigenstructure of circulant matrices is directly related to the DFT convolution theorem [83]. 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

IDFTDFTDFT

where `
' denotes circular convolution. Let
denote
the matrix of sampled DFT sinusoids for a length DFT:
. Then
is the

Premultiplying by the IDFT matrix yields

[How to cite this work] [Order a printed hardcopy]

Copyright ©

Center for Computer Research in Music and Acoustics (CCRMA), Stanford University

[Automatic-links disclaimer]