Circular convolution

Periodic convolution arises, for example, in the context of the discrete-time Fourier transform (DTFT).

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.

An alternative definition, in terms of the notation of normal linear or aperiodic convolution, follows from expressing

[a] The term circular convolution[2][3] arises from the important special case of constraining the non-zero portions of both

Then the periodic summation becomes a periodic extension[b], which can also be expressed as a circular function: And the limits of integration reduce to the length of function

: Similarly, for discrete sequences, and a parameter N, we can write a circular convolution of aperiodic functions

A case of great practical interest is illustrated in the figure.

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.

Then the filtered segments are carefully pieced back together.

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.

We describe it first in terms of normal or linear convolution.

Only 824 of the convolution outputs are unaffected by edge effects.

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.

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.

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 last frame is the composite output, and the section colored green represents the unaffected portion.

[4] In our example, it uses contiguous input blocks of size 824 and pads each one with 200 zero-valued samples.

Both methods advance only 824 samples per 1024-point IFFT, but overlap-save avoids the initial zero-padding and final addition.

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.