Circular convolution

Last updated April 13, 2024

Circular convolution, also known as cyclic convolution, is a special case of periodic convolution, which is the convolution of two periodic functions that have the same period. Periodic convolution arises, for example, in the context of the discrete-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 a periodic summation of a continuous Fourier transform function (see DTFT § Definition). 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.

Definitions

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

\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 $h_{_{T}}(t)$ and $x_{_{T}}(t)$ as periodic summations of aperiodic components $h$ and $x$ , i.e.:

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

Then:

$\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

{\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 $h$ and $x$ to the interval $[0,T].$ Then the periodic summation becomes a periodic extension^{[lower-alpha 2]}, which can also be expressed as a circular function:

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 $h$ :

(h*x_{_{T}})(t)=\int _{0}^{T}h(\tau )\cdot x((t-\tau )_{\mathrm {mod} \ T})\ d\tau .

^{[lower-alpha 4]}^{[lower-alpha 5]}

Discrete sequences

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

(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.

Example

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.

Overlapping input blocks

This method uses a block size equal to the FFT size (1024). We describe it first in terms of normal or linear convolution. When a normal convolution is performed on each block, there are start-up and decay transients at the block edges, due to the filter latency (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 as overlap-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.

Overlapping output blocks

This method is known as overlap-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.

Page citations

↑ McGillem and Cooper, p 172 (4-6)
↑ McGillem and Cooper, p 183 (4-51)
↑ Oppenheim and Shafer, p 559 (8.59)
↑ Oppenheim and Shafer, p 571 (8.114), shown in digital form
↑ McGillem and Cooper, p 171 (4-22), shown in digital form

Related Research Articles

Autocorrelation, sometimes known as serial correlation in the discrete time case, is the correlation of a signal with a delayed copy of itself as a function of delay. Informally, it is the similarity between observations of a random variable as a function of the time lag between them. The analysis of autocorrelation is a mathematical tool for finding repeating patterns, such as the presence of a periodic signal obscured by noise, or identifying the missing fundamental frequency in a signal implied by its harmonic frequencies. It is often used in signal processing for analyzing functions or series of values, such as time domain signals.

In mathematics, convolution is a mathematical operation on two functions that produces a third function. The term convolution refers to both the result function and to the process of computing it. It is defined as the integral of the product of the two functions after one is reflected about the y-axis and shifted. The integral is evaluated for all values of shift, producing the convolution function. The choice of which function is reflected and shifted before the integral does not change the integral result. Graphically, it expresses how the 'shape' of one function is modified by the other.

In mathematics, the discrete Fourier transform (DFT) converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time Fourier transform (DTFT), which is a complex-valued function of frequency. The interval at which the DTFT is sampled is the reciprocal of the duration of the input sequence. An inverse DFT (IDFT) is a Fourier series, using the DTFT samples as coefficients of complex sinusoids at the corresponding DTFT frequencies. It has the same sample-values as the original input sequence. The DFT is therefore said to be a frequency domain representation of the original input sequence. If the original sequence spans all the non-zero values of a function, its DTFT is continuous, and the DFT provides discrete samples of one cycle. If the original sequence is one cycle of a periodic function, the DFT provides all the non-zero values of one DTFT cycle.

In mathematics, Fourier analysis is the study of the way general functions may be represented or approximated by sums of simpler trigonometric functions. Fourier analysis grew from the study of Fourier series, and is named after Joseph Fourier, who showed that representing a function as a sum of trigonometric functions greatly simplifies the study of heat transfer.

In mathematics, the convolution theorem states that under suitable conditions the Fourier transform of a convolution of two functions is the pointwise product of their Fourier transforms. More generally, convolution in one domain equals point-wise multiplication in the other domain. Other versions of the convolution theorem are applicable to various Fourier-related transforms.

In mathematics and signal processing, the Z-transform converts a discrete-time signal, which is a sequence of real or complex numbers, into a complex valued frequency-domain representation.

In signal processing, a finite impulse response (FIR) filter is a filter whose impulse response is of finite duration, because it settles to zero in finite time. This is in contrast to infinite impulse response (IIR) filters, which may have internal feedback and may continue to respond indefinitely.

In signal processing, a periodogram is an estimate of the spectral density of a signal. The term was coined by Arthur Schuster in 1898. Today, the periodogram is a component of more sophisticated methods. It is the most common tool for examining the amplitude vs frequency characteristics of FIR filters and window functions. FFT spectrum analyzers are also implemented as a time-sequence of periodograms.

In mathematics, the Poisson summation formula is an equation that relates the Fourier series coefficients of the periodic summation of a function to values of the function's continuous Fourier transform. Consequently, the periodic summation of a function is completely defined by discrete samples of the original function's Fourier transform. And conversely, the periodic summation of a function's Fourier transform is completely defined by discrete samples of the original function. The Poisson summation formula was discovered by Siméon Denis Poisson and is sometimes called Poisson resummation.

The Fourier transform of a function of time, s(t), is a complex-valued function of frequency, S(f), often referred to as a frequency spectrum. Any linear time-invariant operation on s(t) produces a new spectrum of the form H(f)•S(f), which changes the relative magnitudes and/or angles (phase) of the non-zero values of S(f). Any other type of operation creates new frequency components that may be referred to as spectral leakage in the broadest sense. Sampling, for instance, produces leakage, which we call aliases of the original spectral component. For Fourier transform purposes, sampling is modeled as a product between s(t) and a Dirac comb function. The spectrum of a product is the convolution between S(f) and another function, which inevitably creates the new frequency components. But the term 'leakage' usually refers to the effect of windowing, which is the product of s(t) with a different kind of function, the window function. Window functions happen to have finite duration, but that is not necessary to create leakage. Multiplication by a time-variant function is sufficient.

In mathematics and signal processing, the Hilbert transform is a specific singular integral that takes a function, $u (t)$ of a real variable and produces another function of a real variable $H(u)(t)$ . The Hilbert transform is given by the Cauchy principal value of the convolution with the function $(see § Definition). The Hilbert transform has a particularly simple representation in the frequency domain: It imparts a phase shift of \pm90° (π /2 radians) to every frequency component of a function, the sign of the shift depending on the sign of the frequency (see § Relationship with the Fourier transform). The Hilbert transform is important in signal processing, where it is a component of the analytic representation of a real-valued signal u (t) . The Hilbert transform was first introduced by David Hilbert in this setting, to solve a special case of the Riemann-Hilbert problem for analytic functions.$

In signal processing, cross-correlation is a measure of similarity of two series as a function of the displacement of one relative to the other. This is also known as a sliding dot product or sliding inner-product. It is commonly used for searching a long signal for a shorter, known feature. It has applications in pattern recognition, single particle analysis, electron tomography, averaging, cryptanalysis, and neurophysiology. The cross-correlation is similar in nature to the convolution of two functions. In an autocorrelation, which is the cross-correlation of a signal with itself, there will always be a peak at a lag of zero, and its size will be the signal energy.

In mathematics, the discrete-time Fourier transform (DTFT) is a form of Fourier analysis that is applicable to a sequence of discrete values.

In digital signal processing, downsampling, compression, and decimation are terms associated with the process of resampling in a multi-rate digital signal processing system. Both downsampling and decimation can be synonymous with compression, or they can describe an entire process of bandwidth reduction (filtering) and sample-rate reduction. When the process is performed on a sequence of samples of a signal or a continuous function, it produces an approximation of the sequence that would have been obtained by sampling the signal at a lower rate.

In system analysis, among other fields of study, a linear time-invariant (LTI) system is a system that produces an output signal from any input signal subject to the constraints of linearity and time-invariance; these terms are briefly defined below. These properties apply (exactly or approximately) to many important physical systems, in which case the response $y (t)$ of the system to an arbitrary input $x (t)$ can be found directly using convolution: $y (t) = (x * h)(t)$ where $h (t)$ is called the system's impulse response and ∗ represents convolution (not to be confused with multiplication). What's more, there are systematic methods for solving any such system (determining $h (t)$ ), whereas systems not meeting both properties are generally more difficult (or impossible) to solve analytically. A good example of an LTI system is any electrical circuit consisting of resistors, capacitors, inductors and linear amplifiers.

In signal processing, the overlap–add method is an efficient way to evaluate the discrete convolution of a very long signal $with a finite impulse response (FIR) filter :$

In signal processing, overlap–save is the traditional name for an efficient way to evaluate the discrete convolution between a very long signal $and a finite impulse response (FIR) filter :$

In digital signal processing, the term Discrete Fourier series (DFS) is any periodic discrete-time signal comprising harmonically-related discrete real sinusoids or discrete complex exponentials, combined by a weighted summation. A specific example is the inverse discrete Fourier transform.

In mathematics, any integrable function $can be made into a periodic function with period P by summing the translations of the function by integer multiples of P . This is called periodic summation:$

In signal processing, multidimensional discrete convolution refers to the mathematical operation between two functions f and g on an n-dimensional lattice that produces a third function, also of n-dimensions. Multidimensional discrete convolution is the discrete analog of the multidimensional convolution of functions on Euclidean space. It is also a special case of convolution on groups when the group is the group of n-tuples of integers.

References

↑ Jeruchim, Michel C.; Balaban, Philip; Shanmugan, K. Sam (October 2000). Simulation of Communication Systems: Modeling, Methodology and Techniques (2nd ed.). New York: Kluwer Academic Publishers. pp. 73–74. ISBN 0-30-646267-2.
1 2 Udayashankara, V. (June 2010). Real Time Digital Signal Processing. India: Prentice-Hall. p. 189. ISBN 978-8-12-034049-7.
↑ Priemer, Roland (July 1991). Introductory Signal Processing. Advanced Series in Electrical and Computer Engineering. Vol. 6. Teaneck, N.J.: World Scientific Pub Co Inc. pp. 286–289. ISBN 9971-50-919-9.
1 2 Rabiner, Lawrence R.; Gold, Bernard (1975). Theory and application of digital signal processing . Englewood Cliffs, N.J.: Prentice-Hall. pp. 63–67. ISBN 0-13-914101-4.

Oppenheim, Alan V.; Schafer, Ronald W.; Buck, John R. (1999). Discrete-time signal processing (2nd ed.). Upper Saddle River, N.J.: Prentice Hall. pp. 548, 571. ISBN 0-13-754920-2.
McGillem, Clare D.; Cooper, George R. (1984). Continuous and Discrete Signal and System Analysis (2 ed.). Holt, Rinehart and Winston. ISBN 0-03-061703-0.