Circular convolution, also known ascyclic convolution, is a special case ofperiodic convolution, which is theconvolution of two periodic functions that have the same period. Periodic convolution arises, for example, in the context of thediscrete-time Fourier transform (DTFT). In particular, the DTFT of the product of two discrete sequences is the periodic convolution of the DTFTs of the individual sequences. And each DTFT is aperiodic summation of a continuous Fourier transform function (seeDiscrete-time Fourier transform § Relation to Fourier Transform). Although DTFTs are usually continuous functions of frequency, the concepts of periodic and circular convolution are also directly applicable to discrete sequences of data. In that context, circular convolution plays an important role in maximizing the efficiency of a certain kind of common filtering operation.

Theperiodic 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${\displaystyle t_o}$ is an arbitrary parameter.  An alternative definition, in terms of the notation of normallinear oraperiodic convolution, follows from expressing${\displaystyle h_{{}_T}(t)}$ and${\displaystyle x_{{}_T}(t)}$ asperiodic summations of aperiodic components${\displaystyle h}$ and${\displaystyle x}$, i.e.:

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

Then:

Both forms can be calledperiodic convolution.^[a] The termcircular 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 aperiodic extension^[b], which can also be expressed as acircular function:

${\displaystyle x_{{}_T}(t)=x(t_{\mathrm{m}\mathrm{o}\mathrm{d}T}),t\in \mathbb{R}}$ (any real number)^[c]

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

${\displaystyle (h\ast x_{{}_T})(t)={\int }_0^{T}h(\tau )\cdot x((t-\tau {)}_{\mathrm{m}\mathrm{o}\mathrm{d}T})d\tau .}$^[d][e]

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

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

This function isN-periodic. It has at mostN unique values. For the special case that the non-zero extent of bothx andh are≤ N, it is reducible tomatrix multiplication where the kernel of the integral transform is acirculant matrix.

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

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

This method uses a block size equal to the FFT size (1024). We describe it first in terms of normal orlinear convolution. When a normal convolution is performed on each block, there are start-up and decay transients at the block edges, due to the filterlatency (200-samples). Only 824 of the convolution outputs are unaffected by edge effects. The others are discarded, or simply not computed. That would cause gaps in the output if the input blocks are contiguous. The gaps are avoided by overlapping the input blocks by 200 samples. In a sense, 200 elements from each input block are "saved" and carried over to the next block. This method is referred to asoverlap-save,^[4] although the method we describe next requires a similar "save" with the output samples.

When an FFT is used to compute the 824 unaffected DFT samples, we don't have the option of not computing the affected samples, but the leading and trailing edge-effects are overlapped and added because of circular convolution. Consequently, the 1024-point inverse FFT (IFFT) output contains only 200 samples of edge effects (which are discarded) and the 824 unaffected samples (which are kept). To illustrate this, the fourth frame of the figure at right depicts a block that has been periodically (or "circularly") extended, and the fifth frame depicts the individual components of a linear convolution performed on the entire sequence. The edge effects are where the contributions from the extended blocks overlap the contributions from the original block. The last frame is the composite output, and the section colored green represents the unaffected portion.

This method is known asoverlap-add.^[4] In our example, it uses contiguous input blocks of size 824 and pads each one with 200 zero-valued samples. Then it overlaps and adds the 1024-element output blocks. Nothing is discarded, but 200 values of each output block must be "saved" for the addition with the next block. Both methods advance only 824 samples per 1024-point IFFT, but overlap-save avoids the initial zero-padding and final addition.

• Convolution theorem
• Circulant matrix
• Discrete Hilbert transform

• Functional analysis
• Image processing
• Binary operations

• Articles with short description
• Short description matches Wikidata