Theorem in mathematics
In
pointwise 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 .
Functions of a continuous variable
Consider two functions
u
(
x
)
{\displaystyle u(x)}
and
v
(
x
)
{\displaystyle v(x)}
with Fourier transforms
U
{\displaystyle U}
and
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}}}
denotes the 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 }}}
) will appear in the convolution theorem below. The convolution of
u
{\displaystyle u}
and
v
{\displaystyle v}
is defined by:
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 }
is sometimes used instead.
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},}
produces the corollary: [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 Lp -space
L
1
(
R
n
)
,
{\displaystyle L^{1}(\mathbb {R} ^{n}),}
with Fourier transforms
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}
indicates the 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},}
and
d
x
=
∏
j
=
1
n
d
x
j
.
{\displaystyle dx=\prod _{j=1}^{n}dx_{j}.}
The convolution of
u
{\displaystyle u}
and
v
{\displaystyle v}
is defined by:
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})}
so its Fourier transform
R
{\displaystyle R}
is defined by the integral formula:
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 )|,}
Hence by the argument above we may apply Fubini's theorem again (i.e. interchange the order of integration):
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
.
Periodic convolution (Fourier series coefficients)
Consider
P
{\displaystyle P}
-periodic functions
u
P
{\displaystyle u_{_{P}}}
and
v
P
,
{\displaystyle v_{_{P}},}
which can be expressed as periodic summations :
u
P
(
x
)
≜
∑
m
=
−
∞
∞
u
(
x
−
m
P
)
{\displaystyle u_{_{P}}(x)\ \triangleq \sum _{m=-\infty }^{\infty }u(x-mP)}
and
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}
and
v
{\displaystyle v}
are often limited to duration
P
,
{\displaystyle P,}
but nothing in the theorem requires that.
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}}}
denotes the Fourier series integral .
The pointwise product:
u
P
(
x
)
⋅
v
P
(
x
)
{\displaystyle u_{_{P}}(x)\cdot v_{_{P}}(x)}
is also
P
{\displaystyle P}
-periodic, and its Fourier series coefficients are given by the discrete convolution of the
U
{\displaystyle U}
and
V
{\displaystyle V}
sequences:
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, and is called a
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}}}
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
F
{\displaystyle {\mathcal {F}}}
denotes the discrete-time Fourier transform (DTFT) operator. Consider two sequences
u
[
n
]
{\displaystyle u[n]}
and
v
[
n
]
{\displaystyle v[n]}
with transforms
U
{\displaystyle U}
and
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}
and
v
{\displaystyle v}
is defined by:
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 for discrete sequences is: [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
U
(
f
)
{\displaystyle U(f)}
and
V
(
f
)
,
{\displaystyle V(f),}
as defined above, are periodic, with a period of 1. Consider
N
{\displaystyle N}
-periodic sequences
u
N
{\displaystyle u_{_{N}}}
and
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]}
and
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}
and
V
{\displaystyle V}
at intervals of
1
/
N
{\displaystyle 1/N}
and performing an inverse discrete Fourier transform (DFT) on
N
{\displaystyle N}
samples (see § 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, and is called a
periodic convolution
. Redefining the
F
{\displaystyle {\mathcal {F}}}
operator as the
N
{\displaystyle N}
-length DFT, the corresponding theorem is:[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}
-length sequence to contain a distortion-free segment of a
u
∗
v
{\displaystyle u*v}
convolution. But when the non-zero portion of the
u
(
n
)
{\displaystyle u(n)}
or
v
(
n
)
{\displaystyle v(n)}
sequence is equal or longer than
N
,
{\displaystyle N,}
some distortion is inevitable. Such is the case when the
V
(
k
/
N
)
{\displaystyle V(k/N)}
sequence is obtained by directly sampling the DTFT of the infinitely long § Discrete Hilbert transform impulse response.[A]
For
u
{\displaystyle u}
and
v
{\displaystyle v}
sequences whose non-zero duration is less than or equal to
N
,
{\displaystyle N,}
a final simplification is:
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]
that any linear transform that turns convolution into pointwise product is the DFT (up to a permutation of coefficients).
Derivations of Eq.4
A time-domain derivation proceeds as follows:
D
F
T
{
u
N
∗
v
}
[
k
]
≜
∑
n
=
0
N
−
1
(
∑
m
=
0
N
−
1
u
N
[
m
]
⋅
v
N
[
n
−
m
]
)
e
−
i
2
π
k
n
/
N
=
∑
m
=
0
N
−
1
u
N
[
m
]
(
∑
n
=
0
N
−
1
v
N
[
n
−
m
]
⋅
e
−
i
2
π
k
n
/
N
)
=
∑
m
=
0
N
−
1
u
N
[
m
]
⋅
e
−
i
2
π
k
m
/
N
(
∑
n
=
0
N
−
1
v
N
[
n
−
m
]
⋅
e
−
i
2
π
k
(
n
−
m
)
/
N
)
⏟
D
F
T
{
v
N
}
[
k
]
due to periodicity
=
(
∑
m
=
0
N
−
1
u
N
[
m
]
⋅
e
−
i
2
π
k
m
/
N
)
⏟
D
F
T
{
u
N
}
[
k
]
(
D
F
T
{
v
N
}
[
k
]
)
.
{\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}}}
A frequency-domain derivation follows from
§ Periodic data
, which indicates that the DTFTs can be written as:
F
{
u
N
∗
v
}
(
f
)
=
1
N
∑
k
=
−
∞
∞
(
D
F
T
{
u
N
∗
v
}
[
k
]
)
⋅
δ
(
f
−
k
/
N
)
.
(
E
q
.5
a
)
{\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)}}}
F
{
u
N
}
(
f
)
=
1
N
∑
k
=
−
∞
∞
(
D
F
T
{
u
N
}
[
k
]
)
⋅
δ
(
f
−
k
/
N
)
.
{\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).}
The product with
V
(
f
)
{\displaystyle V(f)}
is thereby reduced to a discrete-frequency function:
F
{
u
N
∗
v
}
(
f
)
=
G
N
(
f
)
V
(
f
)
=
1
N
∑
k
=
−
∞
∞
(
D
F
T
{
u
N
}
[
k
]
)
⋅
V
(
f
)
⋅
δ
(
f
−
k
/
N
)
=
1
N
∑
k
=
−
∞
∞
(
D
F
T
{
u
N
}
[
k
]
)
⋅
V
(
k
/
N
)
⋅
δ
(
f
−
k
/
N
)
=
1
N
∑
k
=
−
∞
∞
(
D
F
T
{
u
N
}
[
k
]
)
⋅
(
D
F
T
{
v
N
}
[
k
]
)
⋅
δ
(
f
−
k
/
N
)
,
(
E
q
.5
b
)
{\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}}}
where the equivalence of
V
(
k
/
N
)
{\displaystyle V(k/N)}
and
(
D
F
T
{
v
N
}
[
k
]
)
{\displaystyle \left(\scriptstyle {\rm {DFT}}\displaystyle \{v_{_{N}}\}[k]\right)}
follows from
§ Sampling the DTFT
. Therefore, the equivalence of (5a) and (5b) requires:
D
F
T
{
u
N
∗
v
}
[
k
]
=
(
D
F
T
{
u
N
}
[
k
]
)
⋅
(
D
F
T
{
v
N
}
[
k
]
)
.
{\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).}
We can also verify the inverse DTFT of (5b):
(
u
N
∗
v
)
[
n
]
=
∫
0
1
(
1
N
∑
k
=
−
∞
∞
D
F
T
{
u
N
}
[
k
]
⋅
D
F
T
{
v
N
}
[
k
]
⋅
δ
(
f
−
k
/
N
)
)
⋅
e
i
2
π
f
n
d
f
=
1
N
∑
k
=
−
∞
∞
D
F
T
{
u
N
}
[
k
]
⋅
D
F
T
{
v
N
}
[
k
]
⋅
(
∫
0
1
δ
(
f
−
k
/
N
)
⋅
e
i
2
π
f
n
d
f
)
⏟
0, for
k
∉
[
0
,
N
)
=
1
N
∑
k
=
0
N
−
1
(
D
F
T
{
u
N
}
[
k
]
⋅
D
F
T
{
v
N
}
[
k
]
)
⋅
e
i
2
π
n
N
k
=
D
F
T
−
1
(
D
F
T
{
u
N
}
⋅
D
F
T
{
v
N
}
)
.
{\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}}}
Convolution theorem for inverse Fourier transform
There is also a convolution theorem for the inverse Fourier transform:
Here, "
⋅
{\displaystyle \cdot }
" represents the Hadamard product , and "
∗
{\displaystyle *}
" represents a convolution between the two matrices.
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
The convolution theorem extends to tempered distributions .
Here,
v
{\displaystyle v}
is an arbitrary tempered distribution:
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 \}}
must be "rapidly decreasing" towards
−
∞
{\displaystyle -\infty }
and
+
∞
{\displaystyle +\infty }
in order to guarantee the existence of both, convolution and multiplication product. Equivalently, if
α
=
F
−
1
{
u
}
{\displaystyle \alpha =F^{-1}\{u\}}
is a smooth "slowly growing" ordinary function, it guarantees the existence of both, multiplication and convolution product.[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}
are smooth "slowly growing" ordinary functions. If, for example,
v
≡
Ш
{\displaystyle v\equiv \operatorname {\text{Ш}} }
is the Dirac comb both equations yield the Poisson summation formula and if, furthermore,
u
≡
δ
{\displaystyle u\equiv \delta }
is the Dirac delta then
α
≡
1
{\displaystyle \alpha \equiv 1}
is constantly one and these equations yield the Dirac comb identity .
See also
Notes
References
^
McGillem, Clare D.; Cooper, George R. (1984). Continuous and Discrete Signal and System Analysis (2 ed.). Holt, Rinehart and Winston. p. 118 (3–102). .
^ 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 (3 ed.), New Jersey: Prentice-Hall International, p. 297, , sAcfAQAAIAAJ
^ a b
.
^
.
.
^ 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.
Further reading
Katznelson, Yitzhak (1976), An introduction to Harmonic Analysis , Dover,
Li, Bing; Babu, G. Jogesh (2019), "Convolution Theorem and Asymptotic Efficiency", A Graduate Course on Statistical Inference , New York: Springer, pp. 295–327,
Crutchfield, Steve (October 9, 2010), "The Joy of Convolution" , Johns Hopkins University , retrieved November 19, 2010
Additional resources
For a visual representation of the use of the convolution theorem in signal processing , see: