Acyclic Convolution

Getting back to acyclic convolution, we may write it as

$\begin{eqnarray*} y(n) &=& (x * h)(n), \quad n\in{\bf Z}\\ &=& \left ( \left( ... ... Shift}_{mR} ( \hbox{\sc DTFT}^{-1}( {\tilde X}_m \cdot H) ) \\ \end{eqnarray*}$

Since ${\tilde x}_m$ is time limited to $[0,\ldots,M-1]$ (or ), ${\tilde X}_m$ can be sampled at intervals of $\Omega_M = 2\pi/M$ without time aliasing. If is time-limited to , then ${\tilde x}_m * h$ will be time limited to . Therefore, we may sample ${\tilde X}_m\cdot H$ at intervals of

$\displaystyle \Omega_{M+L-1} = \frac{2 \pi}{L+M-1}$

or less along the unit circle. This is the dual of the usual sampling theorem.

We conclude that practical FFT acyclic convolution may be carried out using an FFT of any length satisfying

$\displaystyle N \ge M+L-1,$

where is the frame size and is the filter length. Our final expression for is

$\begin{eqnarray*} y(n) &=& \sum_m \hbox{\sc Shift}_{mR,n} \left[\frac{1}{N} \su... ...hbox{\sc FFT}_N({\tilde x}_m)\cdot \hbox{\sc FFT}_N(h)]\right\}, \end{eqnarray*}$

where ${\tilde X}_m$ is the length DFT of the zero-padded $m^{\mbox{th}}$ frame ${\tilde x}_m$ , and ${\tilde H}$ is the length DFT of , also zero-padded out to length , with $N\geq L+M-1$ .

Note that the terms in the outer sum overlap when even if $H(\omega_k)\equiv1$ . In general, an LTI filtering by increases the amount of overlap among the frames.

This completes our derivation of FFT convolution between an indefinitely long signal and a reasonably short FIR filter (short enough that its zero-padded DFT can be practically computed using one FFT).

The fast-convolution processor we have derived is a special case of the Overlap-Add (OLA) method for short-time Fourier analysis, modification, and resynthesis. See [8,10] for more details.

Order a Hardcopy of Spectral Audio Signal Processing

Previous: STFT of COLA Decomposition
Next: Example of Overlap-Add Convolution

written by Julius Orion Smith III
Julius Smith's background is in electrical engineering (BS Rice 1975, PhD Stanford 1983). He is presently Professor of Music and Associate Professor (by courtesy) of Electrical Engineering at Stanford's Center for Computer Research in Music and Acoustics (CCRMA), teaching courses and pursuing research related to signal processing applied to music and audio systems. See http://ccrma.stanford.edu/~jos/ for details.

Sign in

Search Online Books

Free Online Books

Sponsor

Chapters

Spectral Audio Signal Processing
    Overlap-Add (OLA) STFT Processing
       Convolving with Long Signals
          Acyclic Convolution