Linear Convolution of Short Signals

Convolution theorem for DFTs:

$$(h*x) \leftrightarrow H \cdot X$$

or

   DFT$$_k(h*x)=H(\omega_k)X(\omega_k)$$

where $h,x\in \mathbb{C}^N$ , and $H$ and $X$ are the $N$ -point DFTs of $h$ and $x$ , respectively.

DFT performs circular (or cyclic) convolution:

$$y(n) \;\mathrel{\stackrel{\mathrm{\Delta}}{=}}\;(x*h)(n) \;\mathrel{\stackrel{\mathrm{\Delta}}{=}}\;\sum_{m=0}^{N-1} x(m)h(n-m)_N$$

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

Another way to look at this is as the inner product of $x$ , and $\hbox{\sc Shift}_n[\hbox{\sc Flip}(\overline{h})]$ , i.e.,

$$y(n) = \langle x, \hbox{\sc Shift}_n[\hbox{\sc Flip}(\overline{h})] \rangle % \qquad\hbox{($h$ real)}$$