Convolution

  Convolution is both a mathematical concept and an important tool in data processing, in particular in digital signal and image processing.

Discussing first the mathematical aspect, let us assume the goal of an experiment is to measure a random variable X, described by the probability density function f_x(x). Instead of X, however, the setup allows us to observe only the sum U = X+Y of two random variables, where Y has the probability density function f_y (y) (typically Y is a composite of the measurement error and acceptance functions). The (convolved or folded) sum has the probability density f(u) given by the convolution integrals

If f(u) and f_y (y) are known it may be possible to solve the above equation for f_x (x) analytically ( deconvolution or unfolding).

Most frequently, one knows the general form of f_x (x) and f_y(y), but wants to determine some open parameters in one or both functions. One then performs the above integrals and, from fitting the result f(u) to the distribution obtained by experiment, finds the unknown parameters. For a number of cases f(u) can be computed analytically. A few important ones are listed below.

The convolution of two two normal distributions with zero mean and variances and is a normal distribution with zero mean and variance .

The convolution of two distributions with f₁ and f₂ degrees of freedom is a distribution with f₁ +f₂ degrees of freedom.

The convolution of two Poisson distributions with parameters and is a Poisson distribution with parameter .

The convolution of an exponential and a and a normal distribution is approximated by another exponential distribution. If the original exponential distribution is

and the normal distribution has zero mean and variance , then for the probability density of the sum is

In a semi-logarithmic diagram where is plotted versus x and versus u the latter lies by the amount higher than the former but both are represented by parallel straight lines, the slope of which is determined by the parameter .

The convolution of a uniform and a and a normal distribution results in a quasi-uniform distribution smeared out at its edges. If the original distribution is uniform in the region and vanishes elsewhere and the normal distribution has zero mean and variance , the probability density of the sum is

Here

is the distribution function of the standard normal distribution. For the function f(u) vanishes for u<a and u>b and is equal to 1/(b-a) in between. For finite the sharp steps at a and b are rounded off over a width of the order .

Convolutions are also an important tool in the area of digital signal or signal or image processing . They are used for the description of the response of linear shift-invariant systems, and are used in many filter operations.

One-dimensional discrete convolutions are written

(often abbreviated to ).

Convolutions are commutative, associative, and distributive; they have as the identity operation

with for all , and . The figure shows a one-dimensional example of two sequences and their convolution.

For longer sequences, convolution may pose a problem of processing time; it is often preferred to perform the operation in the frequency domain: if X, Y and Z are the Fourier transforms of x, y and z, respectively, then:

Normally one uses a fast Fourier transform (FFT), so that the transformation becomes

For the FFT, sequences x and y are padded with zeros to a length of a power of 2 of at least M + N - 1 samples. For more e.g. [Kunt80]details and more references , [Oppenheim75] or [Rabiner75].