Summary of Overlap-Add FFT Processing

Overlap-add FFT processors provide efficient implementations for FIR filters longer than 100 or so taps on single CPUs. Specifically, we ended up with:

$$y = \sum_{m=-\infty}^\infty \hbox{\sc Shift}_{mR} \left( \hbox{\sc DFT}_N^{-1} \left\{ H \cdot \hbox{\sc DFT}_N\left[\hbox{\sc Shift}_{-mR}(x)\cdot w \right]\right\}\right)$$ (9.24)

where $\hbox{\sc Shift}()$ is acyclic in this context. Stated as a procedure, we have the following steps in an overlap-add FFT processor:

(1)

Extract the $m$ th length $M$ frame of data at time $mR$ .

(2)

Shift it to the base time interval $[0,M-1]$ (or $[-(M-1)/2,(M-1)/2]$ ).

(3)

Optionally apply a length $M$ analysis window $w$ (causal or zero phase, as preferred). For simple LTI filtering, the rectangular window is fine.

(4)

Zero-pad the windowed data out to the FFT size $N$ (a power of 2), such that $N\geq M+L-1$ , where $L$ is the FIR filter length.

(5)

Take the $N$ -point FFT.

(6)

Apply the filter frequency-response $H=\hbox{\sc FFT}_N(h)$ as a windowing operation in the frequency domain.

(7)

Take the $N$ -point inverse FFT.

(8)

Shift the origin of the $N$ -point result out to sample $mR$ where it belongs.

(9)

Sum into the output buffer containing the results from prior frames (OLA step).

The condition $N\geq M+L-1$ is necessary to avoid time aliasing, i.e., to implement acyclic convolution using an FFT; this condition is equivalent to a minimum sampling-rate requirement in the frequency domain.

A second condition is that the analysis window be COLA at the hop size used:

$$\sum_m w(n-mR) = 1, \, \forall n\in\mathbb{Z}.$$ (9.25)