In mathematics, the convolution theorem states that under suitable conditions the Fourier transform of a convolution of two functions (or signals) is the product of their Fourier transforms. More generally, convolution in one domain (e.g., time domain) equals point-wise multiplication in the other domain (e.g., frequency domain). Other versions of the convolution theorem are applicable to various Fourier-related transforms.
Consider two functions
u(x)
v(x)
U
V
\begin{align} U(f)&\triangleql{F}\{u\}(f)=
infty | |
\int | |
-infty |
u(x)e-idx, f\inR\\ V(f)&\triangleql{F}\{v\}(f)=
infty | |
\int | |
-infty |
v(x)e-idx, f\inR \end{align}
where
l{F}
2\pi
\sqrt{2\pi}
u
v
r(x)=\{u*v\}(x)\triangleq
infty | |
\int | |
-infty |
u(\tau)v(x-\tau)d\tau=
infty | |
\int | |
-infty |
u(x-\tau)v(\tau)d\tau.
In this context the asterisk denotes convolution, instead of standard multiplication. The tensor product symbol
⊗
The convolution theorem states that:
Applying the inverse Fourier transform
l{F}-1,
The theorem also generally applies to multi-dimensional functions.
Consider functions
u,v
L1(Rn),
U,V
\begin{align} U(f)&\triangleql{F}\{u\}(f)=
\int | |
Rn |
u(x)e-idx, f\inRn\\ V(f)&\triangleql{F}\{v\}(f)=
\int | |
Rn |
v(x)e-idx, \end{align}
where
f ⋅ x
Rn
f ⋅ x=
n | |
\sum | |
j=1 |
{f}jxj,
dx=
n | |
\prod | |
j=1 |
dxj.
The convolution of
u
v
r(x)\triangleq
\int | |
Rn |
u(\tau)v(x-\tau)d\tau.
Also:
\iint|u(\tau)v(x-\tau)|dxd\tau=\int\left(|u(\tau)|\int|v(x-\tau)|dx\right)d\tau=\int|u(\tau)|\|v\|1d\tau=\|u\|1\|v\|1.
Hence by Fubini's theorem we have that
r\inL1(Rn)
R
\begin{align} R(f)\triangleql{F}\{r\}(f)&=
\int | |
Rn |
r(x)e-idx\\ &=
\int | |
Rn |
\left(\int | |
Rn |
u(\tau)v(x-\tau)d\tau\right)e-idx. \end{align}
Note that
|u(\tau)v(x-\tau)e-i|=|u(\tau)v(x-\tau)|,
\begin{align} R(f)&=
\int | |
Rn |
u(\tau) \underbrace{\left(\int | |
Rn |
v(x-\tau) e-i
dx\right)} | |
V(f) e-i |
d\tau\\ &=\underbrace{\left(\int | |
Rn |
u(\tau) e-id\tau\right)}U(f) V(f). \end{align}
This theorem also holds for the Laplace transform, the two-sided Laplace transform and, when suitably modified, for the Mellin transform and Hartley transform (see Mellin inversion theorem). It can be extended to the Fourier transform of abstract harmonic analysis defined over locally compact abelian groups.
Consider
P
u | |
P |
v | |
P |
,
u | |
P |
(x) \triangleq
infty | |
\sum | |
m=-infty |
u(x-mP)
v | |
P |
(x) \triangleq
infty | |
\sum | |
m=-infty |
v(x-mP).
In practice the non-zero portion of components
u
v
P,
The Fourier series coefficients are:
\begin{align} U[k]&\triangleq
l{F}\{u | |
P |
\}[k]=
1 | |
P |
\intP
u | |
P |
(x)e-idx, k\inZ; \scriptstyleintegrationoveranyintervaloflengthP\\ V[k]&\triangleq
l{F}\{v | |
P |
\}[k]=
1 | |
P |
\intP
v | |
P |
(x)e-idx, k\inZ \end{align}
where
l{F}
u | |
P |
(x) ⋅
v | |
P |
(x)
P
U
V
l{F}\{u | |
P |
⋅
v | |
P |
\}[k]=\{U*V\}[k].
\begin{align} \{u | |
P |
*v\}(x) &\triangleq
infty | |
\int | |
-infty |
u | |
P |
(x-\tau) ⋅ v(\tau) d\tau\\ &\equiv\intP
u | |
P |
(x-\tau) ⋅
v | |
P |
(\tau) d\tau; \scriptstyleintegrationoveranyintervaloflengthP \end{align}
is also
P
infty | |
\begin{align} \int | |
-infty |
u | |
P |
(x-\tau) ⋅ v(\tau)d\tau &=
infty | |
\sum | |
k=-infty |
xo+(k+1)P | |
\left[\int | |
xo+kP |
u | |
P |
(x-\tau) ⋅ v(\tau) d\tau\right] x0isanarbitraryparameter\\
infty | |
&=\sum | |
k=-infty |
xo+P | |
\left[\int | |
xo |
\underbrace{u | |
P |
(x-
\tau-kP)} | |||||||
|
⋅ v(\tau+kP) d\tau\right] substituting\tau → \tau+kP\\
xo+P | |
&=\int | |
xo |
u | |
P |
(x-\tau) ⋅
infty | |
\underbrace{\left[\sum | |
k=-infty |
v(\tau+
kP)\right]} | |||||||
|
d\tau \end{align}
The corresponding convolution theorem is:
\begin{align} l{F}\{u | |
P |
*v\}[k]&\triangleq
1 | |
P |
\intP\left(\intP
u | |
P |
(\tau) ⋅
v | |
P |
(x-\tau) d\tau\right)e-idx\\ &=\intP
u | (\tau)\left( | |
P |
1 | |
P |
\intP
v | |
P |
(x-\tau) e-idx\right)d\tau\\ &=\intP
u | |
P |
(\tau) e-i\underbrace{\left(
1 | |
P |
\intP
v | |
P |
(x-\tau) e-idx\right)}V[k],d\tau\\ &=\underbrace{\left(\intP u
P |
(\tau) e-id\tau\right)}P ⋅ V[k]. \end{align}
By a derivation similar to Eq.1, there is an analogous theorem for sequences, such as samples of two continuous functions, where now
l{F}
u[n]
v[n]
U
V
\begin{align} U(f)&\triangleql{F}\{u\}(f)=
infty | |
\sum | |
n=-infty |
u[n] ⋅ e-i , f\inR,\\ V(f)&\triangleql{F}\{v\}(f)=
infty | |
\sum | |
n=-infty |
v[n] ⋅ e-i , f\inR. \end{align}
The of
u
v
r[n]\triangleq(u*v)[n]=
infty | |
\sum | |
m=-infty |
u[m] ⋅ v[n-m]=
infty | |
\sum | |
m=-infty |
u[n-m] ⋅ v[m].
The convolution theorem for discrete sequences is:
U(f)
V(f),
N
u | |
N |
v | |
N |
u | |
N |
[n] \triangleq
infty | |
\sum | |
m=-infty |
u[n-mN]
v | |
N |
[n] \triangleq
infty | |
\sum | |
m=-infty |
v[n-mN], n\inZ.
These functions occur as the result of sampling
U
V
1/N
N
\{u | |
N |
*v\}[n] \triangleq
infty | |
\sum | |
m=-infty |
u | |
N |
[m] ⋅ v[n-m]\equiv
N-1 | |
\sum | |
m=0 |
u | |
N |
[m] ⋅
v | |
N |
[n-m]
is also
N
l{F}
N
And therefore:
Under the right conditions, it is possible for this
N
u*v
u(n)
v(n)
N,
V(k/N)
For
u
v
N,
This form is often used to efficiently implement numerical convolution by computer. (see and)
As a partial reciprocal, it has been shown [1] that any linear transform that turns convolution into a product is the DFT (up to a permutation of coefficients).
A time-domain derivation proceeds as follows:
\begin{align} \scriptstyle{\rmDFT}\displaystyle
\{u | |
N |
*v\}[k]&\triangleq
N-1 | |
\sum | |
n=0 |
N-1 | |
\left(\sum | |
m=0 |
u | |
N |
[m] ⋅
v | |
N |
[n-m]\right)e-i\\ &=
N-1 | |
\sum | |
m=0 |
u | |
N |
[m]
N-1 | |
\left(\sum | |
n=0 |
v | |
N |
[n-m] ⋅ e-i\right)\\ &=
N-1 | |
\sum | |
m=0 |
u | |
N |
[m] ⋅ e-i
N-1 | |
\underbrace{ \left(\sum | |
n=0 |
v | |
N |
[n-m] ⋅ e-i\right)}\scriptstyle{\rm
\displaystyle\{v | |
N |
\}[k] \scriptstyleduetoperiodicity
A frequency-domain derivation follows from, which indicates that the DTFTs can be written as:
l{F}\{u | |
N |
*v\}(f)=
1 | |
N |
infty | |
\sum | |
k=-infty |
\left(\scriptstyle{\rmDFT}\displaystyle
\{u | |
N |
*v\}[k]\right) ⋅ \delta\left(f-k/N\right). \scriptstyle(Eq.5a)
l{F}\{u | |
N |
\}(f)=
1 | |
N |
infty | |
\sum | |
k=-infty |
\left(\scriptstyle{\rm
DFT}\displaystyle\{u | |
N |
\}[k]\right) ⋅ \delta\left(f-k/N\right).
The product with
V(f)
\begin{align} l{F}\{u | |
N |
*v\}(f)&=
G | |
N |
(f)V(f)\\ &=
1 | |
N |
infty | |
\sum | |
k=-infty |
\left(\scriptstyle{\rm
DFT}\displaystyle\{u | |
N |
\}[k]\right) ⋅ V(f) ⋅ \delta\left(f-k/N\right)\\ &=
1 | |
N |
infty | |
\sum | |
k=-infty |
\left(\scriptstyle{\rm
DFT}\displaystyle\{u | |
N |
\}[k]\right) ⋅ V(k/N) ⋅ \delta\left(f-k/N\right)\\ &=
1 | |
N |
infty | |
\sum | |
k=-infty |
\left(\scriptstyle{\rm
DFT}\displaystyle\{u | |
N |
\}[k]\right) ⋅ \left(\scriptstyle{\rm
DFT}\displaystyle\{v | |
N |
\}[k]\right) ⋅ \delta\left(f-k/N\right), \scriptstyle(Eq.5b) \end{align}
where the equivalence of
V(k/N)
\left(\scriptstyle{\rm
DFT}\displaystyle\{v | |
N |
\}[k]\right)
\scriptstyle{\rmDFT} \displaystyle
{\{u | |
N |
*v\}[k]} =\left(\scriptstyle{\rm
DFT} \displaystyle\{u | |
N |
\}[k]\right) ⋅ \left(\scriptstyle{\rm
DFT}\displaystyle\{v | |
N |
\}[k]\right).
We can also verify the inverse DTFT of (5b):
\begin{align} (u | |
N |
*v)[n]&=
1 | ||
\int | \left( | |
0 |
1 | |
N |
infty | |
\sum | |
k=-infty |
\scriptstyle{\rm
DFT}\displaystyle\{u | |
N |
\}[k] ⋅ \scriptstyle{\rm
DFT}\displaystyle\{v | |
N |
\}[k] ⋅ \delta\left(f-k/N\right)\right) ⋅ eidf\\ &=
1 | |
N |
infty | |
\sum | |
k=-infty |
\scriptstyle{\rm
DFT}\displaystyle\{u | |
N |
\}[k] ⋅ \scriptstyle{\rm
DFT}\displaystyle\{v | |
N |
\}[k] ⋅
1 | |
\underbrace{\left(\int | |
0 |
\delta\left(f-k/N\right) ⋅ eidf\right)}0,for\\ &=
1 | |
N |
N-1 | |
\sum | |
k=0 |
(\scriptstyle{\rm
DFT}\displaystyle\{u | |
N |
\}[k] ⋅ \scriptstyle{\rm
DFT}\displaystyle\{v | |
N |
\}[k]) ⋅
| ||||||
e |
\\ &= \scriptstyle{\rmDFT}-1\displaystyle(\scriptstyle{\rmDFT}\displaystyle
\{u | |
N |
\} ⋅ \scriptstyle{\rmDFT}\displaystyle
\{v | |
N |
\}). \end{align}
There is also a convolution theorem for the inverse Fourier transform:
Here, "
⋅
*
\begin{align} &l{F}\{u*v\}=l{F}\{u\} ⋅ l{F}\{v\}\\ &l{F}\{u ⋅ v\}=l{F}\{u\}*l{F}\{v\} \end{align}
so that
\begin{align} &u*v=l{F}-1\left\{l{F}\{u\} ⋅ l{F}\{v\}\right\}\\ &u ⋅ v=l{F}-1\left\{l{F}\{u\}*l{F}\{v\}\right\} \end{align}
The convolution theorem extends to tempered distributions. Here,
v
\begin{align} &l{F}\{u*v\}=l{F}\{u\} ⋅ l{F}\{v\}\\ &l{F}\{\alpha ⋅ v\}=l{F}\{\alpha\}*l{F}\{v\}. \end{align}
But
u=F\{\alpha\}
-infty
+infty
\alpha=F-1\{u\}
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
v\equiv\operatorname{Ш
u\equiv\delta
\alpha\equiv1
For a visual representation of the use of the convolution theorem in signal processing, see: