2.11 Fast convolution (ticket #5015)

Fast circular convolution

Since, $$\sum_{m=0}^{N-1} x(m)h(n-m)\mod N=y(n)\mathrm{is\; equivalent\; to}Y(k)=X(k)H(k)$$ $y(n)$ can be computed as $y(n)=\mathrm{IDFT}(\mathrm{DFT}(x(n))\mathrm{DFT}(h(n)))$

Cost

• Direct

  • $N^2$ complex multiplies.
  • $N(N-1)$ complex adds.

• Via ffts

  • 3 FFTs + $N$ multipies.
  • $N+\frac{3N}{2}\log_{2}N$ complex multiplies.
  • $3N\log_{2}N$ complex adds.

Fast linear convolution

DFT produces cicular convolution. For linear convolution, we must zero-pad sequences so that circular wrap-around alwayswraps over zeros.

To achieve linear convolution using fast circular convolution, we must use zero-padded DFTs of length $N\ge L+M-1$

Choose shortest convenient $N()$ (usually smallest power-of-two greater than or equal to $L+M-1$ ) $$y(n)={\mathrm{IDFT}}_N({\mathrm{DFT}}_N(x(n)){\mathrm{DFT}}_N(h(n)))$$

Running convolution

Suppose $L$∞ , as in a real time filter application, or $(L, M)$ . There are efficient block methods for computing fast convolution.

Overlap-save (ols) method

Note that if a length- $M$ filter $h(n)$ is circularly convulved with a length- $N$ segment of a signal $x(n)$ ,

The Overlap-Save Method: Break long signal into successive blocks of $N$ samples, each block overlapping the previous block by $M-1$ samples. Perform circular convolution of each block with filter $h(m)$ . Discard first $M-1$ points in each output block, and concatenate the remaining points to create $y(n)$ .

Computation cost for a length- $N$ equals $2^n$ FFT per output sample is (assuming precomputed $H(k)$ ) 2 FFTs and $N$ multiplies $$\frac{2\frac{N}{2}\log_{2}N+N}{N-M+1}=\frac{N(\log_{2}N+1)}{N-M+1}\mathrm{complex\; multiplies}$$ $$\frac{2N\log_{2}N}{N-M+1}=\frac{2N\log_{2}N}{N-M+1}\mathrm{complex\; adds}$$

Compare to $M$ mults, $M-1$ adds per output point for direct method. For a given $M$ , optimal $N$ can be determined by finding $N$ minimizing operation counts. Usualy, optimal $N$ is $4M\le N_{\mathrm{opt}}\le 8M$ .

Overlap-add (ola) method

Zero-pad length- $L$ blocks by $M-1$ samples.

Add successive blocks, overlapped by $M-1$ samples, so that the tails sum to produce the complete linear convolution.