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) \leftrightarrow H \cdot X$$

or,

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

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) = (x*h)(n) \isdef \sum_{m=-\infty}^{\infty} x(m)h(n-m).$$

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

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

where now $h,x,H,X\in {\bf 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 [243]:

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

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) = \langle x, \hbox{\sc Shift}_n[\hbox{\sc Flip}(h)] \rangle. % \qquad\hbox{($h$ real)}$$

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 [243, p. 105] for an illustration of graphical convolution.