Convolution theorem
In mathematics, the convolution theorem states that
under suitable conditions the Fourier transform of a
convolution is the pointwise product of Fourier transforms. In other words, convolution in one domain (e.g.,
time domain) equals point-wise multiplication in the
other domain (e.g., frequency domain). Versions of
the convolution theorem are true for various Fourierrelated transforms. Let f and g be two functions with
convolution f g . (Note that the asterisk denotes convolution in this context, and not multiplication. The tensor
product symbol is sometimes used instead.) Let F denote the Fourier transform operator, so F{f } and F{g}
are the Fourier transforms of f and g , respectively.
Then
Fourier transform, the complexity of the convolution can
be reduced to O(n log n). This can be exploited to construct fast multiplication algorithms.
F{f g} = F{f } F{g}
F () = F{f } =
1 Proof
The proof here is shown for a particular normalization of
the Fourier transform. As mentioned above, if the transform is normalized dierently, then constant scaling factors will appear in the derivation.
Let f, g belong to L1 (Rn ). Let F be the Fourier transform
of f and G be the Fourier transform of g :
where denotes point-wise multiplication. It also works
the other way around:
G() = F{g} =
f (x)e2ix dx
Rn
g(x)e2ix dx,
Rn
where the dot between x and indicates the inner product
of Rn . Let h be the convolution of f and g
F{f g} = F{f } F{g}
By applying the inverse Fourier transform F 1 , we can
write:
f (x)g(z x) dx.
h(z) =
Rn
{
}
f g = F 1 F{f } F{g}
Now notice that
and:
f g =F
{
1
|f (x)g(zx)| dz dx =
}
F{f } F{g}
|f (x)|
|g(zx)| dz dx =
1
n
Note that the relationships above are only valid for the Hence by Fubinis theorem we have that h L (R ) so
form of the Fourier transform shown in the Proof section its Fourier transform H is dened by the integral formula
below. The transform may be normalized in other ways,
in
which case constant scaling factors (typically 2 or
2 ) will appear in the relationships above.
H() = F{h} =
h(z)e2iz dz
n
R
This theorem also holds for the Laplace transform, the
two-sided Laplace transform and, when suitably modi=
f (x)g(z x) dx e2iz dz.
n
n
R
R
ed, for the Mellin transform and Hartley transform (see
Mellin inversion theorem). It can be extended to the
Observe that |f (x)g(z x)e2iz | = |f (x)g(z x)|
Fourier transform of abstract harmonic analysis dened
and hence by the argument above we may apply Fubinis
over locally compact abelian groups.
theorem again (i.e. interchange the order of integration):
This formulation is especially useful for implementing a
numerical convolution on a computer: The standard con(
)
volution algorithm has quadratic computational complex2iz
dz dx.
ity. With the help of the convolution theorem and the fast H() = Rn f (x) Rn g(z x)e
|f (x)| g1
REFERENCES
Substitute y = z x ; then dy = dz , so:
(
H() =
f (x)
Rn
g(y)e
dy
xN [n] =
dx
g(y)e2iy dy
)
dx
Rn
f (x)e
x[n mN ].
It can then be shown that:
Rn
m=
Rn
f (x)e2ix
2i(y+x)
def
2ix
dx
g(y)e2iy dy.
Rn
Rn
[
]
xN y =DT F T 1 DT F T {xN } DT F T {y}
[
]
=DF T 1 DF T {xN } DF T {yN } ,
where DFT represents the discrete Fourier transform.
The proof follows from DTFT#Periodic data, which indicates that DT F T {xN } can be written as:
These two integrals are the denitions of F () and G()
, so:
DT F T {xN }(f )
The product with DT F T {y}(f ) is thereby reduced to a
discrete-frequency function:
QED.
Convolution theorem for inverse
Fourier transform
With similar argument as the above proof, we have the
convolution theorem for the inverse Fourier transform.
F 1 {f g} = F 1 {f } F 1 {g}
F 1 {f g} = F 1 {f } F 1 {g}
{
}
f g = F F 1 {f } F 1 {g}
DT F T {xN }
1
N
x y =DT F T 1
DT F T {x}
]
DT F T {y} ,
k/N )
{z
}
DF T {yN }[k]
ing Sampling the DTFT).
|
(also
us-
The inverse DTFT is:
(xN y)[n] =
0
{
}
f g = F F 1 {f } F 1 {g}
By similar arguments, it can be shown that the discrete
convolution of sequences x and y is given by:
DF T {xN }[k]
Functions of discrete variable sequences
DT F T {y}
k=
DT F T {y}(k/N ) (f
and:
1
(DF T {xN }[k]) (f k/N )
N
k=
H() = F () G(),
1
N
1
N
k=
DF T {xN }[k] DF T {yN }[k]
DF T {xN }[k] DF T {yN }[k]
k=
(f k/N )
1
(f k/N )
0
N 1
n
1
i2 N
k
DF T {xN }[k] DF T {yN }[k] e
N
k=0
[
]
=DF T 1 DF T {xN } DF T {yN } ,
QED.
4 References
Katznelson, Yitzhak (1976), An introduction to Harmonic Analysis, Dover, ISBN 0-486-63331-4
where DTFT represents the discrete-time Fourier transform.
Weisstein, Eric W., Convolution Theorem,
MathWorld.
An important special case is the circular convolution of
x and y dened by xN y, where xN is a periodic summation:
Crutcheld, Steve (October 9, 2010), The Joy of
Convolution, Johns Hopkins University, retrieved
November 19, 2010
Additional resources
For visual representation of the use of the convolution
theorem in signal processing, see:
Johns Hopkins University's Java-aided simulation:
[Link]
6 TEXT AND IMAGE SOURCES, CONTRIBUTORS, AND LICENSES
Text and image sources, contributors, and licenses
6.1
Text
Convolution theorem Source: [Link] Contributors: AxelBoldt,
LC~enwiki, Taw, Rade Kutil, Michael Hardy, Stevenj, Charles Matthews, Robbot, Wile E. Heresiarch, Giftlite, Gene Ward Smith,
Lupin, Nayuki, Ottjes, Thorwald, Phreed, Oleg Alexandrov, Btyner, BD2412, Kevmitch, SpuriousQ, SmackBot, RDBury, BeteNoir,
Ohnoitsjamie, Oli Filth, Bob K, Javalenok, Hu12, Mct mht, Cydebot, Nuwewsco, Almwi, Mckee, Thenub314, AtticusX, Bobbyi, Hanacy,
LokiClock, Pthibault, Pbanta, Visionat, Addbot, MrOllie, Download, Yobot, OrgasGirl, ^musaz, Gtz, Qorilla, Bdmy, Yimuyin, Erik9bot,
MathHisSci, Taweetham, Gaba p, Mrhota, Kallikanzarid, Alexweigel, Slawekb, Tommathew-NJITWILL, ClueBot NG, Snotbot, Isusprof,
Brad7777, Mark viking, Ruoyao and Anonymous: 33
6.2
Images
File:Text_document_with_red_question_mark.svg Source: [Link]
with_red_question_mark.svg License: Public domain Contributors: Created by bdesham with Inkscape; based upon [Link]
from the Tango project. Original artist: Benjamin D. Esham (bdesham)
6.3
Content license
Creative Commons Attribution-Share Alike 3.0
