HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, the convolution theorem states that under suitable conditions the
Fourier transform A Fourier transform (FT) is a mathematical transform that decomposes functions into frequency components, which are represented by the output of the transform as a function of frequency. Most commonly functions of time or space are transformed ...
of a
convolution In mathematics (in particular, functional analysis), convolution is a mathematical operation on two functions ( and ) that produces a third function (f*g) that expresses how the shape of one is modified by the other. The term ''convolution'' ...
of two functions (or signals) is the
pointwise product In mathematics, the pointwise product of two functions is another function, obtained by multiplying the images of the two functions at each value in the domain. If and are both functions with domain and codomain , and elements of can be m ...
of their Fourier transforms. More generally, convolution in one domain (e.g.,
time domain Time domain refers to the analysis of mathematical functions, physical signals or time series of economic or environmental data, with respect to time. In the time domain, the signal or function's value is known for all real numbers, for the c ...
) equals point-wise multiplication in the other domain (e.g.,
frequency domain In physics, electronics, control systems engineering, and statistics, the frequency domain refers to the analysis of mathematical functions or signals with respect to frequency, rather than time. Put simply, a time-domain graph shows how a s ...
). Other versions of the convolution theorem are applicable to various Fourier-related transforms.


Functions of a continuous variable

Consider two functions g(x) and h(x) with
Fourier transform A Fourier transform (FT) is a mathematical transform that decomposes functions into frequency components, which are represented by the output of the transform as a function of frequency. Most commonly functions of time or space are transformed ...
s G and H: \begin G(f) &\triangleq \mathcal\(f) = \int_^g(x) e^ \, dx, \quad f \in \mathbb\\ H(f) &\triangleq \mathcal\(f) = \int_^h(x) e^ \, dx, \quad f \in \mathbb \end where \mathcal denotes the Fourier transform operator. The transform may be normalized in other ways, in which case constant scaling factors (typically 2\pi or \sqrt) will appear in the convolution theorem below. The convolution of g and h is defined by: r(x) = \(x) \triangleq \int_^ g(\tau) h(x-\tau)\, d\tau = \int_^ g(x-\tau) h(\tau)\, d\tau. In this context the
asterisk The asterisk ( ), from Late Latin , from Ancient Greek , ''asteriskos'', "little star", is a typographical symbol. It is so called because it resembles a conventional image of a heraldic star. Computer scientists and mathematicians often voc ...
denotes convolution, instead of standard multiplication. The
tensor product In mathematics, the tensor product V \otimes W of two vector spaces and (over the same field) is a vector space to which is associated a bilinear map V\times W \to V\otimes W that maps a pair (v,w),\ v\in V, w\in W to an element of V \otime ...
symbol \otimes is sometimes used instead. The convolution theorem states that: Applying the inverse Fourier transform \mathcal^, produces the corollary: The theorem also generally applies to multi-dimensional functions. This theorem also holds for the
Laplace transform In mathematics, the Laplace transform, named after its discoverer Pierre-Simon Laplace (), is an integral transform that converts a function of a real variable (usually t, in the '' time domain'') to a function of a complex variable s (in the ...
, the two-sided Laplace transform and, when suitably modified, for the
Mellin transform In mathematics, the Mellin transform is an integral transform that may be regarded as the multiplicative version of the two-sided Laplace transform. This integral transform is closely connected to the theory of Dirichlet series, and is often used ...
and Hartley transform (see Mellin inversion theorem). It can be extended to the Fourier transform of
abstract harmonic analysis Harmonic analysis is a branch of mathematics concerned with the representation of Function (mathematics), functions or signals as the Superposition principle, superposition of basic waves, and the study of and generalization of the notions of Fo ...
defined over locally compact abelian groups.


Periodic convolution (Fourier series coefficients)

Consider P-periodic functions g_ and h_, which can be expressed as periodic summations: g_(x)\ \triangleq \sum_^ g(x-mP)   and   h_(x)\ \triangleq \sum_^ h(x-mP). In practice the non-zero portion of components g and h are often limited to duration P, but nothing in the theorem requires that. The
Fourier series A Fourier series () is a summation of harmonically related sinusoidal functions, also known as components or harmonics. The result of the summation is a periodic function whose functional form is determined by the choices of cycle length (or '' ...
coefficients are: \begin G &\triangleq \mathcal\ = \frac \int_P g_(x) e^ \, dx, \quad k \in \mathbb; \quad \quad \scriptstyle \text P\\ H &\triangleq \mathcal\ = \frac \int_P h_(x) e^ \, dx, \quad k \in \mathbb \end where \mathcal denotes the Fourier series integral. * The pointwise product: g_(x)\cdot h_(x) is also P-periodic, and its Fourier series coefficients are given by the discrete convolution of the G and H sequences: \mathcal\ = \ *The convolution: \begin \(x)\ &\triangleq \int_^ g_(x-\tau)\cdot h(\tau)\ d\tau\\ &\equiv \int_P g_(x-\tau)\cdot h_(\tau)\ d\tau; \quad \quad \scriptstyle \text P \endis also P-periodic, and is called a
periodic convolution 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 discre ...
. The corresponding convolution theorem is:


Functions of a discrete variable (sequences)

By a derivation similar to Eq.1, there is an analogous theorem for sequences, such as samples of two continuous functions, where now \mathcal denotes the
discrete-time Fourier transform In mathematics, the discrete-time Fourier transform (DTFT) is a form of Fourier analysis that is applicable to a sequence of values. The DTFT is often used to analyze samples of a continuous function. The term ''discrete-time'' refers to the ...
(DTFT) operator. Consider two sequences g /math> and h /math> with transforms G and H: \begin G(f) &\triangleq \mathcal\(f) = \sum_^ g cdot e^\;, \quad f \in \mathbb\\ H(f) &\triangleq \mathcal\(f) = \sum_^ h cdot e^\;. \quad f \in \mathbb \end The of g and h is defined by: r \triangleq (g * h) = \sum_^\infty g cdot h - m= \sum_^\infty g -mcdot h The convolution theorem for discrete sequences is:


Periodic convolution

G(f) and H(f), as defined above, are periodic, with a period of 1. Consider N-periodic sequences g_ and h_: g_ \triangleq \sum_^ g -mN/math>   and   h_ \triangleq \sum_^ h -mN \quad n \in \mathbb. These functions occur as the result of sampling G and H at intervals of 1/N and performing an inverse
discrete Fourier transform 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 comple ...
(DFT) on N samples (see ). The discrete convolution: \ \triangleq \sum_^ g_ cdot h -m\equiv \sum_^ g_ cdot h_ -m/math> is also N-periodic, and is called a
periodic convolution 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 discre ...
. Redefining the \mathcal operator as the N-length DFT, the corresponding theorem is: And therefore: Under the right conditions, it is possible for this N-length sequence to contain a distortion-free segment of a g*h convolution. But when the non-zero portion of the g(n) or h(n) sequence is equal or longer than N, some distortion is inevitable.  Such is the case when the H(k/N) sequence is obtained by directly sampling the DTFT of the infinitely long impulse response. For g and h sequences whose non-zero duration is less than or equal to N, a final simplification is: This form is often used to efficiently implement numerical convolution by
computer A computer is a machine that can be programmed to carry out sequences of arithmetic or logical operations ( computation) automatically. Modern digital electronic computers can perform generic sets of operations known as programs. These prog ...
. (see and ) As a partial reciprocal, it has been shown that any linear transform that turns convolution into pointwise product is the DFT (up to a permutation of coefficients).


Convolution theorem for inverse Fourier transform

There is also a convolution theorem for the inverse Fourier transform: \mathcal\ = \mathcal\ \cdot \mathcal\ \mathcal\= \mathcal\*\mathcal\ so that g*h= \mathcal^\left\ g \cdot h= \mathcal^\left\


Convolution theorem for tempered distributions

The convolution theorem extends to
tempered distributions Distributions, also known as Schwartz distributions or generalized functions, are objects that generalize the classical notion of functions in mathematical analysis. Distributions make it possible to differentiate functions whose derivatives d ...
. Here, g is an arbitrary tempered distribution (e.g. the
Dirac comb In mathematics, a Dirac comb (also known as shah function, impulse train or sampling function) is a periodic function with the formula \operatorname_(t) \ := \sum_^ \delta(t - k T) for some given period T. Here ''t'' is a real variable and th ...
) \mathcal\ = \mathcal\ \cdot \mathcal\ \mathcal\= \mathcal\*\mathcal\ but f = F\ must be "rapidly decreasing" towards -\infty and +\infty in order to guarantee the existence of both, convolution and multiplication product. Equivalently, if \alpha = F^\ is a smooth "slowly growing" ordinary function, it guarantees the existence of both, multiplication and convolution product. In particular, every compactly supported tempered distribution, such as the Dirac Delta, is "rapidly decreasing". Equivalently, bandlimited functions, such as the function that is constantly 1 are smooth "slowly growing" ordinary functions. If, for example, g\equiv\operatorname is the
Dirac comb In mathematics, a Dirac comb (also known as shah function, impulse train or sampling function) is a periodic function with the formula \operatorname_(t) \ := \sum_^ \delta(t - k T) for some given period T. Here ''t'' is a real variable and th ...
both equations yield the Poisson summation formula and if, furthermore, f\equiv\delta is the Dirac delta then \alpha \equiv 1 is constantly one and these equations yield the Dirac comb identity.


See also

* Moment-generating function of a
random variable A random variable (also called random quantity, aleatory variable, or stochastic variable) is a mathematical formalization of a quantity or object which depends on random events. It is a mapping or a function from possible outcomes (e.g., the po ...


Notes


References


Further reading

* * * {{refend


Additional resources

For a visual representation of the use of the convolution theorem in
signal processing Signal processing is an electrical engineering subfield that focuses on analyzing, modifying and synthesizing '' signals'', such as sound, images, and scientific measurements. Signal processing techniques are used to optimize transmissions, ...
, see: *
Johns Hopkins University Johns Hopkins University (Johns Hopkins, Hopkins, or JHU) is a private research university in Baltimore, Maryland. Founded in 1876, Johns Hopkins is the oldest research university in the United States and in the western hemisphere. It consi ...
's
Java Java (; id, Jawa, ; jv, ꦗꦮ; su, ) is one of the Greater Sunda Islands in Indonesia. It is bordered by the Indian Ocean to the south and the Java Sea to the north. With a population of 151.6 million people, Java is the world's mo ...
-aided simulation: http://www.jhu.edu/signals/convolve/index.html Theorems in Fourier analysis Articles containing proofs de:Faltung (Mathematik)#Faltungstheorem 2 fr:Produit de convolution