Next  |  Prev  |  Up  |  Top  |  Index  |  JOS Index  |  JOS Pubs  |  JOS Home  |  Search


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 $ x$ and an impulse response $ h$ , in which both $ x$ and $ h$ 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.,

$\displaystyle \mathbf{h}= \left[\begin{array}{cccccc}
h_0 & 0 & 0 & 0 & h_2 & h_1 \\ [2pt]
h_1 & h_0 & 0 & 0 & 0 & h_2 \\ [2pt]
h_2 & h_1 & h_0 & 0 & 0 & 0 \\ [2pt]
0 & h_2 & h_1 & h_0 & 0 & 0 \\ [2pt]
0 & 0 & h_2 & h_1 & h_0 & 0 \\ [2pt]
0 & 0 & 0 & h_2 & h_1 & h_0
\end{array}\right].
$

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 $ N\times N$ circulant matrix are the DFT sinusoids for a length $ N$ DFT [84]. Similarly, the eigenvalues may be found by simply taking the DFT of the first row.

The DFT eigenstructure of circulant matrices is directly related to the DFT convolution theorem [84]. The above $ 6\times 6$ circulant matrix $ \mathbf{h}$ , when multiplied times a length 6 vector $ {\underline{x}}$ , implements cyclic convolution of $ {\underline{x}}$ with $ \underline{h}=[h_0,h_1,h_3,0,0,0]$ . Using the DFT to perform the circular convolution can be expressed as

$\displaystyle \underline{y}={\underline{x}}\circledast \underline{h}=$IDFT$\displaystyle ($DFT$\displaystyle ({\underline{x}})\cdot$DFT$\displaystyle (\underline{h})),
$

where ` $ \circledast $ ' denotes circular convolution. Let $ \mathbf{S}$ denote the matrix of sampled DFT sinusoids for a length $ N$ DFT: $ \mathbf{S}[k,n]\isdeftext e^{j2\pi k n/N}$ . Then $ \mathbf{S}^\ast$ is the DFT matrix, where `$ \ast $ ' denotes Hermitian transposition (transposition and complex-conjugation). The DFT of the length-$ N$ vector $ {\underline{x}}$ can be written as $ \underline{X}=\mathbf{S}^\ast\,{\underline{x}}$ , and the corresponding inverse DFT is $ {\underline{x}}=(1/N)\mathbf{S}\underline{X}$ . The DFT-eigenstructure of circulant matrices provides that a real $ N\times N$ circulant matrix $ \mathbf{h}$ having top row $ \underline{h}^T$ satisfies $ \mathbf{h}\mathbf{S}=
\mathbf{S}\cdot$   diag$ (\underline{H})$ , where $ \underline{H}=\mathbf{S}^\ast\,\underline{h}$ is the length $ N$ DFT of $ \underline{h}$ , and diag$ (\underline{H})$ denotes a diagonal matrix with the elements of $ \underline{H}$ along the diagonal. Therefore, diag$ (\underline{H})=\mathbf{S}^{-1}\mathbf{h}\mathbf{S}=(1/N)\mathbf{S}^\ast\,\mathbf{h}\,\mathbf{S}$ . By the DFT convolution theorem,

\begin{eqnarray*}
\underline{y}=\underline{h}\circledast {\underline{x}}
&\Leftrightarrow&
\underline{Y}[k]=\underline{H}[k]\,\underline{X}[k], \,\forall k\in[0,N-1]\\
&\Leftrightarrow&
\underline{Y}= \mbox{diag}(\underline{H})\,\underline{X}=(1/N)\mathbf{S}^\ast\,\mathbf{h}\,\mathbf{S}\,\underline{X}.
\end{eqnarray*}

Premultiplying by the IDFT matrix $ (1/N)\mathbf{S}$ yields

$\displaystyle \underline{y}= (1/N)\mathbf{S}\underline{Y}=(1/N)\mathbf{S}\mathbf{S}^\ast\,\mathbf{h}\,(1/N)\mathbf{S}\underline{X}= \mathbf{h}{\underline{x}}.
$

Thus, the DFT convolution theorem holds if and only if the circulant convolution matrix $ \mathbf{h}$ has eigenvalues $ \underline{H}$ and eigenvectors given by the columns of $ \mathbf{S}$ (the DFT sinusoids).


Next  |  Prev  |  Up  |  Top  |  Index  |  JOS Index  |  JOS Pubs  |  JOS Home  |  Search

[How to cite this work]  [Order a printed hardcopy]  [Comment on this page via email]

``Introduction to Digital Filters with Audio Applications'', by Julius O. Smith III, (September 2007 Edition).
Copyright © 2014-03-23 by Julius O. Smith III
Center for Computer Research in Music and Acoustics (CCRMA),   Stanford University
CCRMA