Circular convolution


Circular convolution

The circular convolution, also known as cyclic convolution, of two aperiodic functions occurs when one of them is convolved in the normal way with a periodic summation of the other function.  That situation arises in the context of the Circular convolution theorem.  The identical operation can also be expressed in terms of the periodic summations of both functions, if the infinite integration interval is reduced to just one period.  That situation arises in the context of the discrete-time Fourier transform (DTFT) and is also called periodic convolution.  In particular, the transform (DTFT) of the product of two discrete sequences is the periodic convolution of the transforms of the individual sequences.[1]

For a periodic function xT, with period T, the convolution with another function, h, is also periodic, and can be expressed in terms of integration over a finite interval as follows:


\begin{align}
(x_T * h)(t)\quad &\stackrel{\mathrm{def}}{=} \ \int_{-\infty}^\infty h(\tau)\cdot x_T(t - \tau)\,d\tau \\
&= \int_{t_o}^{t_o+T} h_T(\tau)\cdot x_T(t - \tau)\,d\tau,
\end{align}
[2]

where to is an arbitrary parameter, and hT is a periodic summation of h, defined by:

h_T(t) \ \stackrel{\mathrm{def}}{=} \ \sum_{k=-\infty}^\infty  h(t - kT) = \sum_{k=-\infty}^\infty  h(t + kT).

This operation is a periodic convolution of functions xT and hT.  When xT is expressed as the periodic summation of another function, x, the same operation may also be referred to as a circular convolution of functions h and x.

Contents

Discrete sequences

Similarly, for discrete sequences and period N, we can write the circular convolution of functions h and x as:


\begin{align}
(x_N * h)[n] \ &\stackrel{\mathrm{def}}{=} \ \sum_{m=-\infty}^\infty  h[m] \cdot x_N[n-m] \\
&= \sum_{m=-\infty}^\infty  \left( h[m] \cdot \sum_{k=-\infty}^\infty  x[n -m -kN] \right).
\end{align}

This corresponds to matrix multiplication, and the kernel of the integral transform is a circulant matrix.

Example

Circular convolution example.png

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[3], although the method we describe next requires a similar "save" with the output samples.

When the DFT or FFT is used, 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.

See also

Notes

  1. ^ If a sequence, x[n], represents samples of a continuous function, x(t), with Fourier transform X(ƒ), its DTFT is a periodic summation of X(ƒ).  (see Discrete-time_Fourier_transform#Relationship_to_sampling)
  2. ^ Proof:
    \int_{-\infty}^\infty  h(\tau)\cdot x_T(t - \tau)\,d\tau
    
\begin{align}
&= \sum_{k=-\infty}^\infty  \left[\int_{t_o+kT}^{t_o+(k+1)T} h(\tau)\cdot x_T(t - \tau)\ d\tau\right] \\
&\stackrel{\tau \rightarrow \tau+kT}{=}\  \sum_{k=-\infty}^\infty \left[\int_{t_o}^{t_o+T} h(\tau+kT)\cdot x_T(t - \tau -kT)\ d\tau\right] \\
&= \int_{t_o}^{t_o+T} \left[\sum_{k=-\infty}^\infty h(\tau+kT)\cdot \underbrace{x_T(t - \tau-kT)}_{X_T(t - \tau), \text{ by periodicity}}\right]\ d\tau\\
&= \int_{t_o}^{t_o+T} \underbrace{\left[\sum_{k=-\infty}^\infty  h(\tau+kT)\right]}_{\stackrel{\mathrm{def}}{=} \ h_T(\tau)}\cdot x_T(t - \tau)\ d\tau \quad \quad \mbox{(QED)}
\end{align}
  3. ^ Rabiner 1975, pp 65–67.
  4. ^ Rabiner 1975, pp 63–65.

References

  • 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 A. (1999). Discrete-time signal processing. Upper Saddle River, N.J.: Prentice Hall. ISBN 0-13-754920-2. .

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Circular — is a basic geometric shape such as a Circle. Contents 1 Documents 2 Travel and transportation 3 Places …   Wikipedia

  • Convolution — For the usage in formal language theory, see Convolution (computer science). Convolution of two square pulses: the resulting waveform is a triangular pulse. One of the functions (in this case g) is first reflected about τ = 0 and then offset by t …   Wikipedia

  • Symmetric convolution — In mathematics, symmetric convolution is a special subset of convolution operations in which the convolution kernel is symmetric across its zero point. Many common convolution based processes such as Gaussian blur and taking the derivative of a… …   Wikipedia

  • Negacyclic convolution — In mathematics, negacyclic convolution is a convolution between two vectors a and b. It is also called skew circular convolution or wrapped convolution. It results from multiplication of a skew circulant matrix, generated by vector a, with vector …   Wikipedia

  • Overlap–add method — The overlap–add method (OA, OLA) is an efficient way to evaluate the discrete convolution of a very long signal x[n] with a finite impulse response (FIR) filter h[n]: where h[m]=0 for m outside the region [1, M]. The concept is to divide the… …   Wikipedia

  • Overlap-add method — The overlap add method (OA, OLA) is an efficient way to evaluate the discrete convolution between a very long signal x [n] with a finite impulse response (FIR) filter h [n] ::egin{align}y [n] = x [n] * h [n] stackrel{mathrm{def{=} sum {m=… …   Wikipedia

  • Discrete Fourier transform — Fourier transforms Continuous Fourier transform Fourier series Discrete Fourier transform Discrete time Fourier transform Related transforms In mathematics, the discrete Fourier transform (DFT) is a specific kind of discrete transform, used in… …   Wikipedia

  • List of mathematics articles (C) — NOTOC C C closed subgroup C minimal theory C normal subgroup C number C semiring C space C symmetry C* algebra C0 semigroup CA group Cabal (set theory) Cabibbo Kobayashi Maskawa matrix Cabinet projection Cable knot Cabri Geometry Cabtaxi number… …   Wikipedia

  • Circulant matrix — In linear algebra, a circulant matrix is a special kind of Toeplitz matrix where each row vector is rotated one element to the right relative to the preceding row vector. In numerical analysis, circulant matrices are important because they are… …   Wikipedia

  • Hilbert transform — In mathematics and in signal processing, the Hilbert transform is a linear operator which takes a function, u ( t ), and produces a function, H ( u )( t ), with the same domain. The Hilbert transform is named after David Hilbert, who first… …   Wikipedia