●
H o m e
●
R a n d o m
●
N e a r b y
●
L o g i n
●
S e t t i n g s
●
D o n a t e
●
A b o u t W i k i p e d i a
●
D i s c l a i m e r s
Search
C o n v o l u t i o n t h e o r e m ●
A r t i c l e ●
T a l k ●
L a n g u a g e
●
●
Functions of a continuous variable
edit
Consider two functions
u (
x )
{\displaystyle u(x )}
v (
x )
{\displaystyle v(x )}
Fourier transforms
U
{\displaystyle U}
V
{\displaystyle V}
U (
f )
≜
F
{
u }
(
f )
=
∫
−
∞
∞
u (
x )
e
−
i 2 π
f x
d x ,
f ∈
R
V (
f )
≜
F
{
v }
(
f )
=
∫
−
∞
∞
v (
x )
e
−
i 2 π
f x
d x ,
f ∈
R
{\displaystyle {\begin{aligned}U(f )&\triangleq {\mathcal {F}}\{u\}(f )=\int _{-\infty }^{\infty }u(x )e^{-i2\pi fx}\,dx,\quad f\in \mathbb {R} \\V(f )&\triangleq {\mathcal {F}}\{v\}(f )=\int _{-\infty }^{\infty }v(x )e^{-i2\pi fx}\,dx,\quad f\in \mathbb {R} \end{aligned}}}
where
F
{\displaystyle {\mathcal {F}}}
Fourier transform operator . The transform may be normalized in other ways, in which case constant scaling factors (typically
2 π
{\displaystyle 2\pi }
or
2 π
{\displaystyle {\sqrt {2\pi }}}
u
{\displaystyle u}
v
{\displaystyle v}
r (
x )
=
{
u ∗
v }
(
x )
≜
∫
−
∞
∞
u (
τ
)
v (
x −
τ
)
d τ
=
∫
−
∞
∞
u (
x −
τ
)
v (
τ
)
d τ
.
{\displaystyle r(x )=\{u*v\}(x )\triangleq \int _{-\infty }^{\infty }u(\tau )v(x-\tau )\,d\tau =\int _{-\infty }^{\infty }u(x-\tau )v(\tau )\,d\tau .}
In this context the asterisk denotes convolution, instead of standard multiplication. The tensor product symbol
⊗
{\displaystyle \otimes }
The convolution theorem states that: [1 ] [2 ] : eq.8
R (
f )
≜
F
{
r }
(
f )
=
U (
f )
V (
f )
.
f ∈
R
{\displaystyle R(f )\triangleq {\mathcal {F}}\{r\}(f )=U(f )V(f ).\quad f\in \mathbb {R} }
(Eq.1a )
Applying the inverse Fourier transform
F
−
1
,
{\displaystyle {\mathcal {F}}^{-1},}
: [2 ] : eqs.7, 10
Convolution theorem
r (
x )
=
{
u ∗
v }
(
x )
=
F
−
1
{
U ⋅
V }
,
where
⋅
denotes point-wise multiplication
{\displaystyle r(x )=\{u*v\}(x )={\mathcal {F}}^{-1}\{U\cdot V\},\quad \scriptstyle {\text{where }}\displaystyle \cdot \scriptstyle {\text{ denotes point-wise multiplication}}}
(Eq.1b )
The theorem also generally applies to multi-dimensional functions.
Multi-dimensional derivation of Eq.1
Consider functions
u ,
v
{\displaystyle u,v}
in L p
L
1
(
R
n
)
,
{\displaystyle L^{1}(\mathbb {R} ^{n}),}
U ,
V
{\displaystyle U,V}
:
U (
f )
≜
F
{
u }
(
f )
=
∫
R
n
u (
x )
e
−
i 2 π
f ⋅
x
d x ,
f ∈
R
n
V (
f )
≜
F
{
v }
(
f )
=
∫
R
n
v (
x )
e
−
i 2 π
f ⋅
x
d x ,
{\displaystyle {\begin{aligned}U(f )&\triangleq {\mathcal {F}}\{u\}(f )=\int _{\mathbb {R} ^{n}}u(x )e^{-i2\pi f\cdot x}\,dx,\quad f\in \mathbb {R} ^{n}\\V(f )&\triangleq {\mathcal {F}}\{v\}(f )=\int _{\mathbb {R} ^{n}}v(x )e^{-i2\pi f\cdot x}\,dx,\end{aligned}}}
where
f ⋅
x
{\displaystyle f\cdot x}
inner product of
R
n
{\displaystyle \mathbb {R} ^{n}}
f ⋅
x =
∑
j =
1
n
f
j
x
j
,
{\displaystyle f\cdot x=\sum _{j=1}^{n}{f}_{j}x_{j},}
d x =
∏
j =
1
n
d
x
j
.
{\displaystyle dx=\prod _{j=1}^{n}dx_{j}.}
The convolution of
u
{\displaystyle u}
v
{\displaystyle v}
:
r (
x )
≜
∫
R
n
u (
τ
)
v (
x −
τ
)
d τ
.
{\displaystyle r(x )\triangleq \int _{\mathbb {R} ^{n}}u(\tau )v(x-\tau )\,d\tau .}
Also:
∬
|
u (
τ
)
v (
x −
τ
)
|
d x d τ
=
∫
(
|
u (
τ
)
|
∫
|
v (
x −
τ
)
|
d x
)
d τ
=
∫
|
u (
τ
)
|
‖
v
‖
1
d τ
=
‖
u
‖
1
‖
v
‖
1
.
{\displaystyle \iint |u(\tau )v(x-\tau )|\,dx\,d\tau =\int \left(|u(\tau )|\int |v(x-\tau )|\,dx\right)\,d\tau =\int |u(\tau )|\,\|v\|_{1}\,d\tau =\|u\|_{1}\|v\|_{1}.}
Hence by Fubini's theorem we have that
r ∈
L
1
(
R
n
)
{\displaystyle r\in L^{1}(\mathbb {R} ^{n})}
R
{\displaystyle R}
:
R (
f )
≜
F
{
r }
(
f )
=
∫
R
n
r (
x )
e
−
i 2 π
f ⋅
x
d x
=
∫
R
n
(
∫
R
n
u (
τ
)
v (
x −
τ
)
d τ
)
e
−
i 2 π
f ⋅
x
d x .
{\displaystyle {\begin{aligned}R(f )\triangleq {\mathcal {F}}\{r\}(f )&=\int _{\mathbb {R} ^{n}}r(x )e^{-i2\pi f\cdot x}\,dx\\&=\int _{\mathbb {R} ^{n}}\left(\int _{\mathbb {R} ^{n}}u(\tau )v(x-\tau )\,d\tau \right)\,e^{-i2\pi f\cdot x}\,dx.\end{aligned}}}
Note that
|
u (
τ
)
v (
x −
τ
)
e
−
i 2 π
f ⋅
x
|
=
|
u (
τ
)
v (
x −
τ
)
|
,
{\displaystyle |u(\tau )v(x-\tau )e^{-i2\pi f\cdot x}|=|u(\tau )v(x-\tau )|,}
:
R (
f )
=
∫
R
n
u (
τ
)
(
∫
R
n
v (
x −
τ
)
e
−
i 2 π
f ⋅
x
d x
)
⏟
V (
f )
e
−
i 2 π
f ⋅
τ
d τ
=
(
∫
R
n
u (
τ
)
e
−
i 2 π
f ⋅
τ
d τ
)
⏟
U (
f )
V (
f )
.
{\displaystyle {\begin{aligned}R(f )&=\int _{\mathbb {R} ^{n}}u(\tau )\underbrace {\left(\int _{\mathbb {R} ^{n}}v(x-\tau )\ e^{-i2\pi f\cdot x}\,dx\right)} _{V(f )\ e^{-i2\pi f\cdot \tau }}\,d\tau \\&=\underbrace {\left(\int _{\mathbb {R} ^{n}}u(\tau )\ e^{-i2\pi f\cdot \tau }\,d\tau \right)} _{U(f )}\ V(f ).\end{aligned}}}
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 .
edit
Consider
P
{\displaystyle P}
u
P
{\displaystyle u_{_{P}}}
v
P
,
{\displaystyle v_{_{P}},}
periodic summations :
u
P
(
x )
≜
∑
m =
−
∞
∞
u (
x −
m P )
{\displaystyle u_{_{P}}(x )\ \triangleq \sum _{m=-\infty }^{\infty }u(x-mP)}
v
P
(
x )
≜
∑
m =
−
∞
∞
v (
x −
m P )
.
{\displaystyle v_{_{P}}(x )\ \triangleq \sum _{m=-\infty }^{\infty }v(x-mP).}
In practice the non-zero portion of components
u
{\displaystyle u}
v
{\displaystyle v}
P ,
{\displaystyle P,}
The Fourier series coefficients are:
U [
k ]
≜
F
{
u
P
}
[
k ]
=
1 P
∫
P
u
P
(
x )
e
−
i 2 π
k x
/
P
d x ,
k ∈
Z
;
integration over any interval of length
P
V [
k ]
≜
F
{
v
P
}
[
k ]
=
1 P
∫
P
v
P
(
x )
e
−
i 2 π
k x
/
P
d x ,
k ∈
Z
{\displaystyle {\begin{aligned}U[k ]&\triangleq {\mathcal {F}}\{u_{_{P}}\}[k ]={\frac {1}{P}}\int _{P}u_{_{P}}(x )e^{-i2\pi kx/P}\,dx,\quad k\in \mathbb {Z} ;\quad \quad \scriptstyle {\text{integration over any interval of length }}P\\V[k ]&\triangleq {\mathcal {F}}\{v_{_{P}}\}[k ]={\frac {1}{P}}\int _{P}v_{_{P}}(x )e^{-i2\pi kx/P}\,dx,\quad k\in \mathbb {Z} \end{aligned}}}
where
F
{\displaystyle {\mathcal {F}}}
Fourier series integral .
The pointwise product:
u
P
(
x )
⋅
v
P
(
x )
{\displaystyle u_{_{P}}(x )\cdot v_{_{P}}(x )}
P
{\displaystyle P}
discrete convolution of the
U
{\displaystyle U}
V
{\displaystyle V}
F
{
u
P
⋅
v
P
}
[
k ]
=
{
U ∗
V }
[
k ]
.
{\displaystyle {\mathcal {F}}\{u_{_{P}}\cdot v_{_{P}}\}[k ]=\{U*V\}[k ].}
{
u
P
∗
v }
(
x )
≜
∫
−
∞
∞
u
P
(
x −
τ
)
⋅
v (
τ
)
d τ
≡
∫
P
u
P
(
x −
τ
)
⋅
v
P
(
τ
)
d τ
;
integration over any interval of length
P
{\displaystyle {\begin{aligned}\{u_{_{P}}*v\}(x )\ &\triangleq \int _{-\infty }^{\infty }u_{_{P}}(x-\tau )\cdot v(\tau )\ d\tau \\&\equiv \int _{P}u_{_{P}}(x-\tau )\cdot v_{_{P}}(\tau )\ d\tau ;\quad \quad \scriptstyle {\text{integration over any interval of length }}P\end{aligned}}}
is also
P
{\displaystyle P}
periodic convolution
Derivation of periodic convolution
∫
−
∞
∞
u
P
(
x −
τ
)
⋅
v (
τ
)
d τ
=
∑
k =
−
∞
∞
[
∫
x
o
+
k P
x
o
+
(
k +
1 )
P
u
P
(
x −
τ
)
⋅
v (
τ
)
d τ
]
x
0
is an arbitrary parameter
=
∑
k =
−
∞
∞
[
∫
x
o
x
o
+
P
u
P
(
x −
τ
−
k P )
⏟
u
P
(
x −
τ
)
,
by periodicity
⋅
v (
τ
+
k P )
d τ
]
substituting
τ
→
τ
+
k P
=
∫
x
o
x
o
+
P
u
P
(
x −
τ
)
⋅
[
∑
k =
−
∞
∞
v (
τ
+
k P )
]
⏟
≜
v
P
(
τ
)
d τ
{\displaystyle {\begin{aligned}\int _{-\infty }^{\infty }u_{_{P}}(x-\tau )\cdot v(\tau )\,d\tau &=\sum _{k=-\infty }^{\infty }\left[\int _{x_{o}+kP}^{x_{o}+(k+1)P}u_{_{P}}(x-\tau )\cdot v(\tau )\ d\tau \right]\quad x_{0}{\text{ is an arbitrary parameter}}\\&=\sum _{k=-\infty }^{\infty }\left[\int _{x_{o}}^{x_{o}+P}\underbrace {u_{_{P}}(x-\tau -kP)} _{u_{_{P}}(x-\tau ),{\text{ by periodicity}}}\cdot v(\tau +kP)\ d\tau \right]\quad {\text{substituting }}\tau \rightarrow \tau +kP\\&=\int _{x_{o}}^{x_{o}+P}u_{_{P}}(x-\tau )\cdot \underbrace {\left[\sum _{k=-\infty }^{\infty }v(\tau +kP)\right]} _{\triangleq \ v_{_{P}}(\tau )}\ d\tau \end{aligned}}}
The corresponding convolution theorem is:
F
{
u
P
∗
v }
[
k ]
=
P ⋅
U [
k ]
V [
k ]
.
{\displaystyle {\mathcal {F}}\{u_{_{P}}*v\}[k ]=\ P\cdot U[k ]\ V[k ].}
(Eq.2 )
Derivation of Eq.2
F
{
u
P
∗
v }
[
k ]
≜
1 P
∫
P
(
∫
P
u
P
(
τ
)
⋅
v
P
(
x −
τ
)
d τ
)
e
−
i 2 π
k x
/
P
d x
=
∫
P
u
P
(
τ
)
(
1 P
∫
P
v
P
(
x −
τ
)
e
−
i 2 π
k x
/
P
d x
)
d τ
=
∫
P
u
P
(
τ
)
e
−
i 2 π
k τ
/
P
(
1 P
∫
P
v
P
(
x −
τ
)
e
−
i 2 π
k (
x −
τ
)
/
P
d x
)
⏟
V [
k ]
,
due to periodicity
d τ
=
(
∫
P
u
P
(
τ
)
e
−
i 2 π
k τ
/
P
d τ
)
⏟
P ⋅
U [
k ]
V [
k ]
.
{\displaystyle {\begin{aligned}{\mathcal {F}}\{u_{_{P}}*v\}[k ]&\triangleq {\frac {1}{P}}\int _{P}\left(\int _{P}u_{_{P}}(\tau )\cdot v_{_{P}}(x-\tau )\ d\tau \right)e^{-i2\pi kx/P}\,dx\\&=\int _{P}u_{_{P}}(\tau )\left({\frac {1}{P}}\int _{P}v_{_{P}}(x-\tau )\ e^{-i2\pi kx/P}dx\right)\,d\tau \\&=\int _{P}u_{_{P}}(\tau )\ e^{-i2\pi k\tau /P}\underbrace {\left({\frac {1}{P}}\int _{P}v_{_{P}}(x-\tau )\ e^{-i2\pi k(x-\tau )/P}dx\right)} _{V[k ],\quad {\text{due to periodicity}}}\,d\tau \\&=\underbrace {\left(\int _{P}\ u_{_{P}}(\tau )\ e^{-i2\pi k\tau /P}d\tau \right)} _{P\cdot U[k ]}\ V[k ].\end{aligned}}}
edit
By a derivation similar to Eq.1, there is an analogous theorem for sequences, such as samples of two continuous functions, where now
F
{\displaystyle {\mathcal {F}}}
discrete-time Fourier transform
u [
n ]
{\displaystyle u[n ]}
v [
n ]
{\displaystyle v[n ]}
U
{\displaystyle U}
V
{\displaystyle V}
U (
f )
≜
F
{
u }
(
f )
=
∑
n =
−
∞
∞
u [
n ]
⋅
e
−
i 2 π
f n
,
f ∈
R
,
V (
f )
≜
F
{
v }
(
f )
=
∑
n =
−
∞
∞
v [
n ]
⋅
e
−
i 2 π
f n
,
f ∈
R
.
{\displaystyle {\begin{aligned}U(f )&\triangleq {\mathcal {F}}\{u\}(f )=\sum _{n=-\infty }^{\infty }u[n ]\cdot e^{-i2\pi fn}\;,\quad f\in \mathbb {R} ,\\V(f )&\triangleq {\mathcal {F}}\{v\}(f )=\sum _{n=-\infty }^{\infty }v[n ]\cdot e^{-i2\pi fn}\;,\quad f\in \mathbb {R} .\end{aligned}}}
The § Discrete convolution of
u
{\displaystyle u}
v
{\displaystyle v}
:
r [
n ]
≜
(
u ∗
v )
[
n ]
=
∑
m =
−
∞
∞
u [
m ]
⋅
v [
n −
m ]
=
∑
m =
−
∞
∞
u [
n −
m ]
⋅
v [
m ]
.
{\displaystyle r[n ]\triangleq (u*v)[n ]=\sum _{m=-\infty }^{\infty }u[m ]\cdot v[n-m]=\sum _{m=-\infty }^{\infty }u[n-m]\cdot v[m ].}
The convolution theorem : [3 ] [4 ] : p.60 (2.169)
R (
f )
=
F
{
u ∗
v }
(
f )
=
U (
f )
V (
f )
.
{\displaystyle R(f )={\mathcal {F}}\{u*v\}(f )=\ U(f )V(f ).}
(Eq.3 )
Periodic convolution
edit
U (
f )
{\displaystyle U(f )}
V (
f )
,
{\displaystyle V(f ),}
N
{\displaystyle N}
u
N
{\displaystyle u_{_{N}}}
v
N
{\displaystyle v_{_{N}}}
:
u
N
[
n ]
≜
∑
m =
−
∞
∞
u [
n −
m N ]
{\displaystyle u_{_{N}}[n ]\ \triangleq \sum _{m=-\infty }^{\infty }u[n-mN]}
v
N
[
n ]
≜
∑
m =
−
∞
∞
v [
n −
m N ]
,
n ∈
Z
.
{\displaystyle v_{_{N}}[n ]\ \triangleq \sum _{m=-\infty }^{\infty }v[n-mN],\quad n\in \mathbb {Z} .}
These functions occur as the result of sampling
U
{\displaystyle U}
V
{\displaystyle V}
1
/
N
{\displaystyle 1/N}
discrete Fourier transform
N
{\displaystyle N}
§ Sampling the DTFT ). The discrete convolution:
{
u
N
∗
v }
[
n ]
≜
∑
m =
−
∞
∞
u
N
[
m ]
⋅
v [
n −
m ]
≡
∑
m =
0
N −
1
u
N
[
m ]
⋅
v
N
[
n −
m ]
{\displaystyle \{u_{_{N}}*v\}[n ]\ \triangleq \sum _{m=-\infty }^{\infty }u_{_{N}}[m ]\cdot v[n-m]\equiv \sum _{m=0}^{N-1}u_{_{N}}[m ]\cdot v_{_{N}}[n-m]}
is also
N
{\displaystyle N}
periodic convolution
F
{\displaystyle {\mathcal {F}}}
N
{\displaystyle N}
[5 ] [4 ] : p. 548
F
{
u
N
∗
v }
[
k ]
=
F
{
u
N
}
[
k ]
⏟
U (
k
/
N )
⋅
F
{
v
N
}
[
k ]
⏟
V (
k
/
N )
,
k ∈
Z
.
{\displaystyle {\mathcal {F}}\{u_{_{N}}*v\}[k ]=\ \underbrace {{\mathcal {F}}\{u_{_{N}}\}[k ]} _{U(k/N)}\cdot \underbrace {{\mathcal {F}}\{v_{_{N}}\}[k ]} _{V(k/N)},\quad k\in \mathbb {Z} .}
(Eq.4a )
And therefore:
{
u
N
∗
v }
[
n ]
=
F
−
1
{
F
{
u
N
}
⋅
F
{
v
N
}
}
.
{\displaystyle \{u_{_{N}}*v\}[n ]=\ {\mathcal {F}}^{-1}\{{\mathcal {F}}\{u_{_{N}}\}\cdot {\mathcal {F}}\{v_{_{N}}\}\}.}
(Eq.4b )
Under the right conditions, it is possible for this
N
{\displaystyle N}
u ∗
v
{\displaystyle u*v}
u (
n )
{\displaystyle u(n )}
or
v (
n )
{\displaystyle v(n )}
N ,
{\displaystyle N,}
V (
k
/
N )
{\displaystyle V(k/N)}
§ Discrete Hilbert transform impulse response.[A ]
For
u
{\displaystyle u}
v
{\displaystyle v}
N ,
{\displaystyle N,}
Circular convolution
{
u
N
∗
v }
[
n ]
=
F
−
1
{
F
{
u }
⋅
F
{
v }
}
.
{\displaystyle \{u_{_{N}}*v\}[n ]=\ {\mathcal {F}}^{-1}\{{\mathcal {F}}\{u\}\cdot {\mathcal {F}}\{v\}\}.}
(Eq.4c )
This form is often used to efficiently implement numerical convolution by computer . (see § Fast convolution algorithms and § Example )
As a partial reciprocal, it has been shown [6 ]
edit
There is also a convolution theorem for the inverse Fourier transform:
Here, "
⋅
{\displaystyle \cdot }
Hadamard product , and "
∗
{\displaystyle *}
F
{
u ∗
v }
=
F
{
u }
⋅
F
{
v }
F
{
u ⋅
v }
=
F
{
u }
∗
F
{
v }
{\displaystyle {\begin{aligned}&{\mathcal {F}}\{u*v\}={\mathcal {F}}\{u\}\cdot {\mathcal {F}}\{v\}\\&{\mathcal {F}}\{u\cdot v\}={\mathcal {F}}\{u\}*{\mathcal {F}}\{v\}\end{aligned}}}
so that
u ∗
v =
F
−
1
{
F
{
u }
⋅
F
{
v }
}
u ⋅
v =
F
−
1
{
F
{
u }
∗
F
{
v }
}
{\displaystyle {\begin{aligned}&u*v={\mathcal {F}}^{-1}\left\{{\mathcal {F}}\{u\}\cdot {\mathcal {F}}\{v\}\right\}\\&u\cdot v={\mathcal {F}}^{-1}\left\{{\mathcal {F}}\{u\}*{\mathcal {F}}\{v\}\right\}\end{aligned}}}
Convolution theorem for tempered distributions
edit
The convolution theorem extends to tempered distributions .
Here,
v
{\displaystyle v}
F
{
u ∗
v }
=
F
{
u }
⋅
F
{
v }
F
{
α
⋅
v }
=
F
{
α
}
∗
F
{
v }
.
{\displaystyle {\begin{aligned}&{\mathcal {F}}\{u*v\}={\mathcal {F}}\{u\}\cdot {\mathcal {F}}\{v\}\\&{\mathcal {F}}\{\alpha \cdot v\}={\mathcal {F}}\{\alpha \}*{\mathcal {F}}\{v\}.\end{aligned}}}
But
u =
F {
α
}
{\displaystyle u=F\{\alpha \}}
−
∞
{\displaystyle -\infty }
+
∞
{\displaystyle +\infty }
α
=
F
−
1
{
u }
{\displaystyle \alpha =F^{-1}\{u\}}
[7 ] [8 ] [9 ]
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
{\displaystyle 1}
v ≡
Ш
{\displaystyle v\equiv \operatorname {\text{Ш}} }
Dirac comb both equations yield the Poisson summation formula and if, furthermore,
u ≡
δ
{\displaystyle u\equiv \delta }
α
≡
1
{\displaystyle \alpha \equiv 1}
Dirac comb identity .
See also
edit
Notes
edit
References
edit
^
McGillem, Clare D.; Cooper, George R. (1984). Continuous and Discrete Signal and System Analysis (2 ed.). Holt, Rinehart and Winston. p. 118 (3–102). ISBN 0-03-061703-0
^ a b
Weisstein, Eric W. "Convolution Theorem" . From MathWorld--A Wolfram Web Resource . Retrieved 8 February 2021 .
^
Proakis, John G.; Manolakis, Dimitri G. (1996), Digital Signal Processing: Principles, Algorithms and Applications Bibcode :1996dspp.book.....P , ISBN 9780133942897
^ a b
Oppenheim, Alan V. ; Schafer, Ronald W. ; Buck, John R. (1999). Discrete-time signal processing ISBN 0-13-754920-2
^
Rabiner, Lawrence R. ; Gold, Bernard (1975). Theory and application of digital signal processing ISBN 978-0139141010
^ Amiot, Emmanuel (2016). Music through Fourier Space doi :10.1007/978-3-319-45581-5 . ISBN 978-3-319-45581-5 S2CID 6224021 .
^ Horváth, John (1966). Topological Vector Spaces and Distributions . Reading, MA: Addison-Wesley Publishing Company.
^ Barros-Neto, José (1973). An Introduction to the Theory of Distributions . New York, NY: Dekker.
^ Petersen, Bent E. (1983). Introduction to the Fourier Transform and Pseudo-Differential Operators . Boston, MA: Pitman Publishing.
Katznelson, Yitzhak (1976), An introduction to Harmonic Analysis , Dover, ISBN 0-486-63331-4
Li, Bing; Babu, G. Jogesh (2019), "Convolution Theorem and Asymptotic Efficiency", A Graduate Course on Statistical Inference , New York: Springer, pp. 295–327, ISBN 978-1-4939-9759-6
Crutchfield, Steve (October 9, 2010), "The Joy of Convolution" , Johns Hopkins University , retrieved November 19, 2010
Additional resources
edit
For a visual representation of the use of the convolution theorem in signal processing , see:
R e t r i e v e d f r o m " https://en.wikipedia.org/w/index.php?title=Convolution_theorem&oldid=1226718213 "
L a s t e d i t e d o n 1 J u n e 2 0 2 4 , a t 1 1 : 4 2 L a n g u a g e s
● C a t a l à ● D e u t s c h ● E s p a ñ o l ● F r a n ç a i s ● I t a l i a n o ● P o r t u g u ê s ● Р у с с к и й ● 中 文
● T h i s p a g e w a s l a s t e d i t e d o n 1 J u n e 2 0 2 4 , a t 1 1 : 4 2 ( U T C ) . ● C o n t e n t i s a v a i l a b l e u n d e r C C B Y - S A 4 . 0 u n l e s s o t h e r w i s e n o t e d . ● P r i v a c y p o l i c y ● A b o u t W i k i p e d i a ● D i s c l a i m e r s ● C o n t a c t W i k i p e d i a ● C o d e o f C o n d u c t ● D e v e l o p e r s ● S t a t i s t i c s ● C o o k i e s t a t e m e n t ● T e r m s o f U s e ● D e s k t o p
and 
![{\displaystyle {\begin{aligned}U[k]&\triangleq {\mathcal {F}}\{u_{_{P}}\}[k]={\frac {1}{P}}\int _{P}u_{_{P}}(x)e^{-i2\pi kx/P}\,dx,\quad k\in \mathbb {Z} ;\quad \quad \scriptstyle {\text{integration over any interval of length }}P\\V[k]&\triangleq {\mathcal {F}}\{v_{_{P}}\}[k]={\frac {1}{P}}\int _{P}v_{_{P}}(x)e^{-i2\pi kx/P}\,dx,\quad k\in \mathbb {Z} \end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/51b732f1fe5d5074f423f1b96c4eea07631284ed)
is also ![{\displaystyle {\mathcal {F}}\{u_{_{P}}\cdot v_{_{P}}\}[k]=\{U*V\}[k].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ab30eb678559f102051cedba4be0fc07f346a4c0)
![{\displaystyle u[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e6f1362207606428a09d907db25527859eab6ac3)
![{\displaystyle v[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7cbc20699310c20ae48d376fc4f6365c67966405)
![{\displaystyle {\begin{aligned}U(f)&\triangleq {\mathcal {F}}\{u\}(f)=\sum _{n=-\infty }^{\infty }u[n]\cdot e^{-i2\pi fn}\;,\quad f\in \mathbb {R} ,\\V(f)&\triangleq {\mathcal {F}}\{v\}(f)=\sum _{n=-\infty }^{\infty }v[n]\cdot e^{-i2\pi fn}\;,\quad f\in \mathbb {R} .\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/244dd8c93040378c9c8849ab6483c6582445d1b7)
![{\displaystyle r[n]\triangleq (u*v)[n]=\sum _{m=-\infty }^{\infty }u[m]\cdot v[n-m]=\sum _{m=-\infty }^{\infty }u[n-m]\cdot v[m].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/22aac1f7102502f6b39153be6aacd9bce5fc7cdd)
![{\displaystyle u_{_{N}}[n]\ \triangleq \sum _{m=-\infty }^{\infty }u[n-mN]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ed44f4cf6f7e56baa871eef261cd01f53855dd07)
and ![{\displaystyle v_{_{N}}[n]\ \triangleq \sum _{m=-\infty }^{\infty }v[n-mN],\quad n\in \mathbb {Z} .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/62b3cb372f16be04589aa1f446455da9d8bcd8f0)
![{\displaystyle \{u_{_{N}}*v\}[n]\ \triangleq \sum _{m=-\infty }^{\infty }u_{_{N}}[m]\cdot v[n-m]\equiv \sum _{m=0}^{N-1}u_{_{N}}[m]\cdot v_{_{N}}[n-m]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/907f89efecfca8b8c1519230c0efe93f721d0ad3)
![{\displaystyle {\begin{aligned}\int _{-\infty }^{\infty }u_{_{P}}(x-\tau )\cdot v(\tau )\,d\tau &=\sum _{k=-\infty }^{\infty }\left[\int _{x_{o}+kP}^{x_{o}+(k+1)P}u_{_{P}}(x-\tau )\cdot v(\tau )\ d\tau \right]\quad x_{0}{\text{ is an arbitrary parameter}}\\&=\sum _{k=-\infty }^{\infty }\left[\int _{x_{o}}^{x_{o}+P}\underbrace {u_{_{P}}(x-\tau -kP)} _{u_{_{P}}(x-\tau ),{\text{ by periodicity}}}\cdot v(\tau +kP)\ d\tau \right]\quad {\text{substituting }}\tau \rightarrow \tau +kP\\&=\int _{x_{o}}^{x_{o}+P}u_{_{P}}(x-\tau )\cdot \underbrace {\left[\sum _{k=-\infty }^{\infty }v(\tau +kP)\right]} _{\triangleq \ v_{_{P}}(\tau )}\ d\tau \end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f1575bd74f86366816ffc18d0fabd05dd5cd1269)
![{\displaystyle {\mathcal {F}}\{u_{_{P}}*v\}[k]=\ P\cdot U[k]\ V[k].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9d4ee3375f365aa800cc34e56a6bf89e0a90ed3b)
![{\displaystyle {\begin{aligned}{\mathcal {F}}\{u_{_{P}}*v\}[k]&\triangleq {\frac {1}{P}}\int _{P}\left(\int _{P}u_{_{P}}(\tau )\cdot v_{_{P}}(x-\tau )\ d\tau \right)e^{-i2\pi kx/P}\,dx\\&=\int _{P}u_{_{P}}(\tau )\left({\frac {1}{P}}\int _{P}v_{_{P}}(x-\tau )\ e^{-i2\pi kx/P}dx\right)\,d\tau \\&=\int _{P}u_{_{P}}(\tau )\ e^{-i2\pi k\tau /P}\underbrace {\left({\frac {1}{P}}\int _{P}v_{_{P}}(x-\tau )\ e^{-i2\pi k(x-\tau )/P}dx\right)} _{V[k],\quad {\text{due to periodicity}}}\,d\tau \\&=\underbrace {\left(\int _{P}\ u_{_{P}}(\tau )\ e^{-i2\pi k\tau /P}d\tau \right)} _{P\cdot U[k]}\ V[k].\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/252a143162a38ecc1ee2c1780ed231edf64ed597)
![{\displaystyle {\mathcal {F}}\{u_{_{N}}*v\}[k]=\ \underbrace {{\mathcal {F}}\{u_{_{N}}\}[k]} _{U(k/N)}\cdot \underbrace {{\mathcal {F}}\{v_{_{N}}\}[k]} _{V(k/N)},\quad k\in \mathbb {Z} .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cbf1eab2ab63c1b6db4fc8f33c8a4a30b1391f50)
![{\displaystyle \{u_{_{N}}*v\}[n]=\ {\mathcal {F}}^{-1}\{{\mathcal {F}}\{u_{_{N}}\}\cdot {\mathcal {F}}\{v_{_{N}}\}\}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cd918e288950dc7554d3cb3e478d441022b16afc)
![{\displaystyle \{u_{_{N}}*v\}[n]=\ {\mathcal {F}}^{-1}\{{\mathcal {F}}\{u\}\cdot {\mathcal {F}}\{v\}\}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6ac7a801e261a01f897517049a2095ee7d745cf6)
![{\displaystyle {\begin{aligned}\scriptstyle {\rm {DFT}}\displaystyle \{u_{_{N}}*v\}[k]&\triangleq \sum _{n=0}^{N-1}\left(\sum _{m=0}^{N-1}u_{_{N}}[m]\cdot v_{_{N}}[n-m]\right)e^{-i2\pi kn/N}\\&=\sum _{m=0}^{N-1}u_{_{N}}[m]\left(\sum _{n=0}^{N-1}v_{_{N}}[n-m]\cdot e^{-i2\pi kn/N}\right)\\&=\sum _{m=0}^{N-1}u_{_{N}}[m]\cdot e^{-i2\pi km/N}\underbrace {\left(\sum _{n=0}^{N-1}v_{_{N}}[n-m]\cdot e^{-i2\pi k(n-m)/N}\right)} _{\scriptstyle {\rm {DFT}}\displaystyle \{v_{_{N}}\}[k]\quad \scriptstyle {\text{due to periodicity}}}\\&=\underbrace {\left(\sum _{m=0}^{N-1}u_{_{N}}[m]\cdot e^{-i2\pi km/N}\right)} _{\scriptstyle {\rm {DFT}}\displaystyle \{u_{_{N}}\}[k]}\left(\scriptstyle {\rm {DFT}}\displaystyle \{v_{_{N}}\}[k]\right).\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/61dd82c63ec339357bb750973d87a819d0490c8e)
![{\displaystyle {\mathcal {F}}\{u_{_{N}}*v\}(f)={\frac {1}{N}}\sum _{k=-\infty }^{\infty }\left(\scriptstyle {\rm {DFT}}\displaystyle \{u_{_{N}}*v\}[k]\right)\cdot \delta \left(f-k/N\right).\quad \scriptstyle {\mathsf {(Eq.5a)}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9dc6053c6711e16180fcaf82615d9ba6d205646c)
![{\displaystyle {\mathcal {F}}\{u_{_{N}}\}(f)={\frac {1}{N}}\sum _{k=-\infty }^{\infty }\left(\scriptstyle {\rm {DFT}}\displaystyle \{u_{_{N}}\}[k]\right)\cdot \delta \left(f-k/N\right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/42c03475328868e8c4027366eb1a6740a38895e6)
![{\displaystyle {\begin{aligned}{\mathcal {F}}\{u_{_{N}}*v\}(f)&=G_{_{N}}(f)V(f)\\&={\frac {1}{N}}\sum _{k=-\infty }^{\infty }\left(\scriptstyle {\rm {DFT}}\displaystyle \{u_{_{N}}\}[k]\right)\cdot V(f)\cdot \delta \left(f-k/N\right)\\&={\frac {1}{N}}\sum _{k=-\infty }^{\infty }\left(\scriptstyle {\rm {DFT}}\displaystyle \{u_{_{N}}\}[k]\right)\cdot V(k/N)\cdot \delta \left(f-k/N\right)\\&={\frac {1}{N}}\sum _{k=-\infty }^{\infty }\left(\scriptstyle {\rm {DFT}}\displaystyle \{u_{_{N}}\}[k]\right)\cdot \left(\scriptstyle {\rm {DFT}}\displaystyle \{v_{_{N}}\}[k]\right)\cdot \delta \left(f-k/N\right),\quad \scriptstyle {\mathsf {(Eq.5b)}}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fbfa658cb06c8f39bd4f6c14c0cf49ebb7f614af)
![{\displaystyle \left(\scriptstyle {\rm {DFT}}\displaystyle \{v_{_{N}}\}[k]\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/867247cbc04ad960f719050702f1b613652470f0)
![{\displaystyle \scriptstyle {\rm {DFT}}\displaystyle {\{u_{_{N}}*v\}[k]}=\left(\scriptstyle {\rm {DFT}}\displaystyle \{u_{_{N}}\}[k]\right)\cdot \left(\scriptstyle {\rm {DFT}}\displaystyle \{v_{_{N}}\}[k]\right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8f7b413f938f761ac2c932b93215c4e166e02071)
![{\displaystyle {\begin{aligned}(u_{_{N}}*v)[n]&=\int _{0}^{1}\left({\frac {1}{N}}\sum _{k=-\infty }^{\infty }\scriptstyle {\rm {DFT}}\displaystyle \{u_{_{N}}\}[k]\cdot \scriptstyle {\rm {DFT}}\displaystyle \{v_{_{N}}\}[k]\cdot \delta \left(f-k/N\right)\right)\cdot e^{i2\pi fn}df\\&={\frac {1}{N}}\sum _{k=-\infty }^{\infty }\scriptstyle {\rm {DFT}}\displaystyle \{u_{_{N}}\}[k]\cdot \scriptstyle {\rm {DFT}}\displaystyle \{v_{_{N}}\}[k]\cdot \underbrace {\left(\int _{0}^{1}\delta \left(f-k/N\right)\cdot e^{i2\pi fn}df\right)} _{{\text{0, for}}\ k\ \notin \ [0,\ N)}\\&={\frac {1}{N}}\sum _{k=0}^{N-1}{\bigg (}\scriptstyle {\rm {DFT}}\displaystyle \{u_{_{N}}\}[k]\cdot \scriptstyle {\rm {DFT}}\displaystyle \{v_{_{N}}\}[k]{\bigg )}\cdot e^{i2\pi {\frac {n}{N}}k}\\&=\ \scriptstyle {\rm {DFT}}^{-1}\displaystyle {\bigg (}\scriptstyle {\rm {DFT}}\displaystyle \{u_{_{N}}\}\cdot \scriptstyle {\rm {DFT}}\displaystyle \{v_{_{N}}\}{\bigg )}.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d1c651d3df13f237865ee17f554975dbd3136b08)