FFT Convolution

If $x$ and $h$ have finite (nonzero) support, then so does $x\ast h$ , and we may sample the frequency axis of the DTFT:

   DFT$$_k(h\ast x) \eqsp H(\omega_k)X(\omega_k)$$

where $H$ and $X$ are the $N$ -point DFTs of $h$ and $x$ , respectively.

The DFT performs circular (cyclic) convolution:

$$y(n) \isdefs (x\ast h)(n) \isdefs \sum_{m=0}^{N-1} x(m)h(n-m)_N$$

where $(n-m)_N$ means ``$(n-m)$ modulo $N$ ''

Two methods:

• direct calculation of the summation $= {\cal O}(N^2)$
• frequency-domain approach $= {\cal O}(N$   lg$N)$
  • DFT both $x$ and $h$ to obtain $X$ and $H$
  • Multiply pointwise to obtain $Y = X\cdot H$
  • Inverse DFT to get $y$ in the time domain