next Computational Complexity
previous Circulant Feedback Delay Networks
up Circulant Feedback Delay Networks   Contents   Global Contents
global_index Global Index   Index   Search

Design of Poles and Zeros in CFDNs

A matrix that is both unitary and circulant has all eigenvalues on the unit circle, and the DFT can be used to compute the eigenvalue phases. In the case of equal-length delay lines, the eigenvalues determine the resonance frequencies in a simple way. From (16), when ${\bf D}(z^{-1})=z^m
{\bf I}$, the system poles are the $m$-th complex roots of the eigenvalues of ${\bf A}$.

Conversely, we can easily design a circulant matrix to have a desired distribution of eigenvalues. This is also true for any lossless matrix, since Theorem 1 gives that any ${\bf A}$ of the form ${\bf A}=
{\bf T}^{-1}{\bf D}{\bf T}$ is lossless, where ${\bf D}$ is any unit-modulus diagonal matrix, and ${\bf T}$ is any invertible matrix. Thus, a lossless matrix is characterized by the arguments of its eigenvalues and a similarity transformation matrix ${\bf T}$. The advantage of choosing circulant FDNs over other kinds of FDNs is the possibility of computing ${\bf A}$ from its eigenvalues very efficiently by means of a single inverse FFT.

As we will see in section V, in a practical implementation the delay lengths are typically not equal. However, the equal-delay case is easier to analyze. The limitations and advantages of such a choice will become clearer in section V.

The actual presence of resonance peaks corresponding to the eigenvalues depends on the positions of the zeros, as given by (19). Assuming equal-length delay lines and $d=1$, (19) becomes

\begin{displaymath}
\det[{\bf A} - {\bf b}{\bf c}^T- z^{m}{\bf I}] = 0
\end{displaymath} (30)

which means that the zeros are the $m$-th complex roots of the eigenvalues of ${\bf A} - {\bf b}{\bf c}^T$.

In order to have ``colorless'' reverberation, it may be desirable to make the envelope of the amplitude response flat. To do this, each zero should be equal to the reciprocal of a pole. In prototype CFDNs, the feedback matrix is lossless, and the system poles are on the unit circle, so the zeros must equal the poles. However, when all zeros and poles cancel exactly, the impulse response of the FDN degenerates to an impulse.4 This is a general problem with any all-pass reverberator: Lengthening the reverberation time without changing the delay lengths forces the impulse response converge to an impulse. In our case, we depart from the idealized case by slightly changing the delay lengths. As we will show in section V, this approach leads to reverberators having a frequency response which is nearly flat at low frequencies, while preserving the richness of the echo density in the time domain.

Therefore, we continue treating the prototype case of equal-length delay lines and $d=1$, and show that we can obtain perfect canceling of zeros and poles by using (1) ${\bf b}^T=[1, 1, \ldots, 1]$ and (2) ${\bf c}$ having $n$ entries equal to $1$, $n$ entries equal to $-1$, and zeros for the remaining entries. This result is due to the following

Theorem 2: Given a circulant $N$x$N$ matrix ${\bf A}$, let $A'$ be obtained by adding a constant $c$ to each entry of $n$ rows (columns) and subtracting the same constant $c$ from each entry of another $n$ rows (columns). Then ${\bf A}$ and ${\bf A'}$ have the same eigenvalues.

Before providing the proof of Theorem 2, we need to prove the following

Lemma: All the eigenvectors of a circulant matrix other than the ``dc'' vector $[1, \ldots, 1]^T$ lie in the null space of any matrix with constant rows. Thus, adding constant rows cannot alter eigenvalues or eigenvectors other than the 0th.

Proof: This follows immediately from the fact that the eigenvectors of every circulant matrix are given by the columns of the DFT matrix of the same size, and these vectors are orthogonal. Therefore, a constant row is orthogonal to all eigenvectors of the DFT matrix except the dc eigenvector.

The lemma states that all we can do by adding constant rows to a circulant matrix is move the ``dc'' eigenvector to some other vector and change its eigenvalue.

Proof of Theorem 2:
Consider the matrix ${\bf A}'$ given by:

\begin{displaymath}
{\bf A}'= {\bf A} - {\bf b}{\bf c}^T
\end{displaymath} (31)

where ${\bf b}^T=[1, -1, 0, \ldots, 0]$ and ${\bf c}^T=[1, 1, \ldots, 1]$. Since any circulant matrix is diagonalized by the DFT matrix, if we pre-multiply and post-multiply both sides of (31) by the DFT matrices ${\bf F}^*$ and ${\bf F}$, we obtain

\begin{displaymath}
{\bf F}^* {\bf A}' {\bf F}
= {\bf F}^* {\bf A} {\bf F}
-...
...c}^T {\bf F}
= {\bf D}- {\bf F}^* ({\bf b}{\bf c}^T {\bf F})
\end{displaymath}

where ${\bf D}$ is a diagonal matrix and the term within parentheses is an $N$ by $N$ matrix having non-null entries only in position (1,1) and (2,1). Moreover these two entries have opposite sign. It turns out that ${\bf F}^*
{\bf b}{\bf c}^T {\bf F}$ has non-null elements only on the first column under the diagonal. This means that the matrix ${\bf A}'$ can be triangularized by means of the DFT matrix and its eigenvalues (found on the diagonal) are the same as those of ${\bf A}$. This argument works for any number of oppositely signed couples of distinct values arbitrarily distributed in the vector ${\bf b}$. The same argument can be followed for proving the claim relative to the columns. In this case we would start by forming the product ${\bf F}^* {\bf b}{\bf c}^T$. $\Box$

Note that the $0th$ eigenvalue is no longer a ``dc'' eigenvalue. The corresponding eigenvector must be found in $ker({\bf A} - {\bf b}{\bf c}^T-\lambda _
0{\bf I})$, where $ker()$ gives the nullspace of its argument. In the case of a real circulant matrix ${\bf A}$ with eigenvalues along the unit circle, we have that $\lambda _0 = 1$ (the sum of the elements of a row of ${\bf A}$ is 1).

With the above choice of $\bf b$ and $\bf c$ coefficients, we obtain a perfectly flat amplitude response for equal-length delay lines. However, this is degenerate since this is the condition for pole-zero cancellation. As we will show in section V, when using slightly different delay lengths, a nearly flat response at low frequencies is obtained as a perturbation of the pole-zero cancellation configuration.


next Computational Complexity
previous Circulant Feedback Delay Networks
up Circulant Feedback Delay Networks   Contents   Global Contents
global_index Global Index   Index   Search

``Circulant and Elliptic Feedback Delay Networks for Artificial Reverberation'', by Davide Rocchesso and Julius O. Smith III, preprint of version in IEEE Transactions on Speech and Audio, vol. 5, no. 1, pp. 51-60, Jan. 1996.

Download PDF version (cfdn.pdf)
Download compressed PostScript version (cfdn.ps.gz)

(Browser settings for best viewing results)

Copyright © 2005-03-10 by Davide Rocchesso and Julius O. Smith III
Center for Computer Research in Music and Acoustics (CCRMA),   Stanford University
CCRMA  (automatic links disclaimer)