Circular convolution

The periodic convolution of two T-periodic functions, ${\displaystyle h_{_{T}}(t)}$ and ${\displaystyle x_{_{T}}(t)}$ can be defined as:

${\displaystyle \int _{t_{o}}^{t_{o}+T}h_{_{T}}(\tau )\cdot x_{_{T}}(t-\tau )\,d\tau ,}$   [1][2]

where t_o is an arbitrary parameter.  An alternative definition, in terms of the notation of normal linear or aperiodic convolution, follows from expressing ${\displaystyle h_{_{T}}(t)}$ and ${\displaystyle x_{_{T}}(t)}$ as periodic summations of aperiodic components ${\displaystyle h}$ and ${\displaystyle x}$, i.e.:

${\displaystyle h_{_{T}}(t)\ \triangleq \ \sum _{k=-\infty }^{\infty }h(t-kT)=\sum _{k=-\infty }^{\infty }h(t+kT).}$

Then:

${\displaystyle \int _{t_{o}}^{t_{o}+T}h_{_{T}}(\tau )\cdot x_{_{T}}(t-\tau )\,d\tau =\int _{-\infty }^{\infty }h(\tau )\cdot x_{_{T}}(t-\tau )\,d\tau \ \triangleq \ (h*x_{_{T}})(t)=(x*h_{_{T}})(t).}$

(Eq.1)

Derivation of Eq.1

$${\displaystyle {\begin{aligned}\int _{-\infty }^{\infty }h(\tau )\cdot x_{_{T}}(t-\tau )\,d\tau &=\sum _{k=-\infty }^{\infty }\left[\int _{t_{o}+kT}^{t_{o}+(k+1)T}h(\tau )\cdot x_{_{T}}(t-\tau )\ d\tau \right]\quad t_{0}{\text{ is an arbitrary parameter}}\\&=\sum _{k=-\infty }^{\infty }\left[\int _{t_{o}}^{t_{o}+T}h(u+kT)\cdot \underbrace {x_{_{T}}(t-u-kT)} _{x_{_{T}}(t-u),{\text{ by periodicity}}}\ du\right]\quad {\text{substituting }}u\triangleq \tau -kT\\&=\int _{t_{o}}^{t_{o}+T}\left[\sum _{k=-\infty }^{\infty }h(u+kT)\cdot x_{_{T}}(t-u)\right]\ du\\&=\int _{t_{o}}^{t_{o}+T}\underbrace {\left[\sum _{k=-\infty }^{\infty }h(u+kT)\right]} _{\triangleq \ h_{_{T}}(u)}\cdot x_{_{T}}(t-u)\ du\\&=\int _{t_{o}}^{t_{o}+T}h_{_{T}}(\tau )\cdot x_{_{T}}(t-\tau )\ d\tau \quad {\text{substituting }}\tau \triangleq u\end{aligned}}}$$

Both forms can be called periodic convolution.[lower-alpha 1] The term circular convolution[2][3] arises from the important special case of constraining the non-zero portions of both ${\displaystyle h}$ and ${\displaystyle x}$ to the interval ${\displaystyle [0,T].}$ Then the periodic summation becomes a periodic extension[lower-alpha 2], which can also be expressed as a circular function:

${\displaystyle x_{_{T}}(t)=x(t_{\mathrm {mod} \ T}),\quad t\in \mathbb {R} \,}$ (any real number)[lower-alpha 3]

And the limits of integration reduce to the length of function ${\displaystyle h}$:

${\displaystyle (h*x_{_{T}})(t)=\int _{0}^{T}h(\tau )\cdot x((t-\tau )_{\mathrm {mod} \ T})\ d\tau .}$[lower-alpha 4][lower-alpha 5]

Similarly, for discrete sequences, and a parameter N, we can write a circular convolution of aperiodic functions ${\displaystyle h}$ and ${\displaystyle x}$ as:

${\displaystyle (h*x_{_{N}})[n]\ \triangleq \ \sum _{m=-\infty }^{\infty }h[m]\cdot \underbrace {x_{_{N}}[n-m]} _{\sum _{k=-\infty }^{\infty }x[n-m-kN]}}$

This function is N-periodic. It has at most N unique values. For the special case that the non-zero extent of both x and h are ≤ N, it is reducible to matrix multiplication where the kernel of the integral transform is a circulant matrix.

Circular convolution can be expedited by the FFT algorithm, so it is often used with an FIR filter to efficiently compute linear convolutions. These graphs illustrate how that is possible. Note that a larger FFT size (N) would prevent the overlap that causes graph #6 to not quite match all of #3.

A case of great practical interest is illustrated in the figure. The duration of the x sequence is N (or less), and the duration of the h sequence is significantly less. Then many of the values of the circular convolution are identical to values of x∗h,  which is actually the desired result when the h sequence is a finite impulse response (FIR) filter. Furthermore, the circular convolution is very efficient to compute, using a fast Fourier transform (FFT) algorithm and the circular convolution theorem.

There are also methods for dealing with an x sequence that is longer than a practical value for N. The sequence is divided into segments (blocks) and processed piecewise. Then the filtered segments are carefully pieced back together. Edge effects are eliminated by overlapping either the input blocks or the output blocks. To help explain and compare the methods, we discuss them both in the context of an h sequence of length 201 and an FFT size of N = 1024.

• Convolution theorem
• Circulant matrix
• Discrete Hilbert transform