convolution theorem
   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 operation (mathematics), mathematical operation on two function (mathematics), functions ( and ) that produces a third function (f*g) that expresses how the shape of one is ...
of two functions (or
signals In signal processing, a signal is a function that conveys information about a phenomenon. Any quantity that can vary over space or time can be used as a signal to share messages between observers. The ''IEEE Transactions on Signal Processing'' ...
) 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 mul ...
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 cas ...
) 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 signa ...
). Other versions of the convolution theorem are applicable to various
Fourier-related transforms This is a list of linear transformations of functions related to Fourier analysis. Such transformations map a function to a set of coefficients of basis functions, where the basis functions are sinusoidal and are therefore strongly localized i ...
.


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 \otimes W ...
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 In mathematics, an integral transform maps a function from its original function space into another function space via integra ...
, the
two-sided Laplace transform In mathematics, the two-sided Laplace transform or bilateral Laplace transform is an integral transform equivalent to probability's moment generating function. Two-sided Laplace transforms are closely related to the Fourier transform, the Mellin t ...
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 i ...
and
Hartley transform In mathematics, the Hartley transform (HT) is an integral transform closely related to the Fourier transform (FT), but which transforms real-valued functions to real-valued functions. It was proposed as an alternative to the Fourier transform by R ...
(see
Mellin inversion theorem In mathematics, the Mellin inversion formula (named after Hjalmar Mellin) tells us conditions under which the inverse Mellin transform, or equivalently the inverse two-sided Laplace transform, are defined and recover the transformed function. Met ...
). It can be extended to the Fourier transform of
abstract harmonic analysis Harmonic analysis is a branch of mathematics concerned with the representation of functions or signals as the superposition of basic waves, and the study of and generalization of the notions of Fourier series and Fourier transforms (i.e. an ...
defined over locally compact abelian groups.


Periodic convolution (Fourier series coefficients)

Consider P-periodic functions g_ and h_, which can be expressed as
periodic summation In signal processing, any periodic function s_P(t) with period ''P'' can be represented by a summation of an infinite number of instances of an aperiodic function s(t), that are offset by integer multiples of ''P''. This representation is called p ...
s: 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 ''p ...
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 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 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. 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 complex- ...
(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. 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 Execution (computing), carry out sequences of arithmetic or logical operations (computation) automatically. Modern digital electronic computers can perform generic sets of operations known as C ...
. (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 derivative, differentiate functions whose de ...
. 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 In mathematics, the Dirac delta distribution ( distribution), also known as the unit impulse, is a generalized function or distribution over the real numbers, whose value is zero everywhere except at zero, and whose integral over the entire ...
, 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 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 ...
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 In probability theory and statistics, the moment-generating function of a real-valued random variable is an alternative specification of its probability distribution. Thus, it provides the basis of an alternative route to analytical results compare ...
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 audio signal processing, sound, image processing, images, and scientific measurements. Signal processing techniq ...
, see: *
Johns Hopkins University Johns Hopkins University (Johns Hopkins, Hopkins, or JHU) is a private university, private research university in Baltimore, Maryland. Founded in 1876, Johns Hopkins is the oldest research university in the United States and in the western hem ...
'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 List ...
-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