Convolution and cross/auto-correlation

Convolution, cross-correlation and auto-correlation

We provide here a short reminder of the properties of convolution, and we define two important operations: the cross correlation of two functions and the auto-correlation of a function.

continuous time

Let $h(t)$ and $x(t)$ be two continuous time functions. When it exists, the convolution between $h$ and $x$ is given by $$ \begin{aligned} y(t) & = (h* x)(t)\\ & = \int_{\mathbb{R}} h(u)x(t-u)\mathrm{d}u \end{aligned} $$

the convolution is commutative:

$$ \begin{aligned} y(t) & = (h* x)(t)\\ & = (x* h)(t)\\& = \int_{\mathbb{R}} h(t-u)x(u)\mathrm{d}u \end{aligned} $$

The neutral element of the convolution is Dirac distribution $\delta (t)$ : $$ (\delta*x)(t) = (x*\delta)(t) = x(t) $$

discrete time

Let $h[t]$ and $x[t]$ be two continuous time functions. When it exists, the convolution between $h[t]$ and $x[t]$ is given by $$ \begin{aligned} y[t] & = (h* x)[t]\\ & = \sum{k\in\mathbb{Z}} h[k]x[t-k] \end{aligned} $$

the convolution is commutative:

$$ \begin{aligned} y[t] & = (h* x)[t]\\ & = (x* h)[t]\\& = \sum{k\in\mathbb{Z}} h[t-u]x[u] \end{aligned} $$

The neutral element of the convolution is Dirac sequence $\delta [t]$ : $$ (\delta*x)[t] = (x*\delta)[t] = x[t] $$

discrete finite signals

Full convolution

For finite discrete signals, several convolution products can be defined. The most straightforward way is to dive the finite signal into the space of numerical signal by zeros padding. Let $\boldsymbol{h} = \lbrace h[0],\ldots,h[M]\rbrace$ and $\boldsymbol{x} = \lbrace x[0],\ldots,x[N]\rbrace$. Define the two numerical sequences $h[t]$ and $x[t]$ from $\boldsymbol{h}$ and $\boldsymbol{x}$ such that $h[t]=0$ $\forall t\notin \lbrace 0,\ldots,M \rbrace$ and $x[t]=0$ $\forall t\notin \lbrace 0,\ldots,N \rbrace$. Then the full convolution of these numerical sequence gives a finite numerical signal $\boldsymbol{y}$ of size $M+N-1$ :

$$ \begin{aligned} y[t] & = (h* x)[t] = \sum{k\in\mathbb{Z}} h[k]x[t-k] \\& = \sum{k=0}^{M-1} h[k]x[t-k]\\& = \sum{k=0}^{N-1} x[k]h[t-k] \end{aligned} $$ which is non zeros for $t\in\lbrace 0,\ldots,M+N-1 \rbrace.

Circular convolution

However, another to dive a finite sequence into the space of numerical signal is by periodization. Without lost of generality, suppose that $N>M$. Define the two $N$-periodic numerical sequences $h[t]$ and $x[t]$ from $\boldsymbol{h}$ and $\boldsymbol{x}$ such that $\forall t$ $h[t+N] = h[t]$ and $x[t+N]=x[t]$. The circular convolution of these numerical sequence gives a $N$-periodic finite numerical signal $\boldsymbol{y}$ of size $N$:

$$ \begin{aligned} y[t] & = (h* x)[t] = \sum{k=0}^N h[k]x[t-k] \\ & = \sum{k=0}^{N-1} x[k]h[t-k] \end{aligned} $$ In practice, we only keep one period of this $N$-periodic sequence to produce the vector $\boldsymbol{y}=\lbrace y[0],\ldots,y[N-1] \rbrace$.

The circular convolution will be essential with the finite Fourier transform.

Cross and auto correlation

continuous time

The cross correlation of two analog signals $x(t)$ and $y(t)$ is given by $$ \begin{aligned} (x\star y)(t) & = \int_{\mathbb{R}} \overline{x(u)}y(t+u)\mathrm{d}u \\ & = \int_{\mathbb{R}} x(t-u)\overline{y(u)}\mathrm{d}u \end{aligned} $$ The cross correlation is not a commutative operation !

Let $\tilde x(t)=\overline{x(-t)}$, then $$ (x\star y)(t) = (\tilde x * y)(t) $$

The autocorrelation of the signal $x(t)$ is the cross correlation with itself.

discrete time

The cross correlation of two numerical signals $x[t]$ and $y[t]$ is given by $$ \begin{aligned} (x\star y)[t] & = \sum_{k\in\mathbb{Z}} \overline{x[k]}y[t+k] \\ & = \sum_{k\in\mathbb{Z}} x[t-k]\overline{y[k]} \end{aligned} $$ The cross correlation is not a commutative operation !

Let $\tilde x[t]=\overline{x[-t]}$, then $$ (x\star y)(t) = (\tilde x * y)(t) $$

For finite numerical sequence, we have the same possibilities as for the convolution: a full cross correlation, or a circular cross correlation.

The autocorrelation of the signal $x[t]$ is the cross correlation with itself.