Convolution of Short Signals

Figure: System diagram for filtering an input signal $x(n)$ by filter $h(n)$ to produce output $y(n)$ as the convolution of $x$ and $h$ .

Figure 8.1 illustrates the conceptual operation of filtering an input signal $x(n)$ by a filter with impulse-response $h(n)$ to produce an output signal $y(n)$ . By the convolution theorem for DTFTs (§2.3.5),

$$(h*x) \;\longleftrightarrow\;H \cdot X$$ (9.9)

or,

$$\hbox{\sc DTFT}_\omega(h*x)\eqsp H(\omega)X(\omega)$$ (9.10)

where $h$ and $x$ are arbitrary real or complex sequences, and $H$ and $X$ are the DTFTs of $h$ and $x$ , respectively. The convolution of $x$ and $h$ is defined by

$$y(n) \eqsp (x*h)(n) \isdefs \sum_{m=-\infty}^{\infty} x(m)h(n-m).$$ (9.11)

In practice, we always use the DFT (preferably an FFT) in place of the DTFT, in which case we may write

$$\hbox{\sc DFT}_k(h*x)\eqsp H(\omega_k)X(\omega_k)$$ (9.12)

where now $h,x,H,X\in \mathbb{C}^N$ (length $N$ complex sequences). It is important to remember that the specific form of convolution implied in the DFT case is cyclic (also called circular) convolution [264]:

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

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

Another way to look at convolution is as the inner product of $x$ , and $\hbox{\sc Shift}_n[\hbox{\sc Flip}(h)]$ , where $\hbox{\sc Flip}_n(h)\isdeftext h(-n)=h(N-n)$ , i.e.,

$$y(n) \eqsp \langle x, \hbox{\sc Shift}_n[\hbox{\sc Flip}(h)] \rangle.$$ (9.14)

This form describes graphical convolution in which the output sample at time $n$ is computed as an inner product of the impulse response after flipping it about time 0 and shifting time 0 to time $n$ . See [264, p. 105] for an illustration of graphical convolution.