Editing Convolution theorem (section)

== 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 <math>\mathcal{F}</math> denotes the '''[[discrete-time Fourier transform]]''' (DTFT) operator.  Consider two sequences <math>u[n]</math> and <math>v[n]</math> with transforms <math>U</math> and <math>V</math>:

:<math>\begin{align}
U(f) &\triangleq \mathcal{F}\{u\}(f) = \sum_{n=-\infty}^{\infty} u[n]\cdot e^{-i 2\pi f n}\;, \quad f \in \mathbb{R}, \\
V(f) &\triangleq \mathcal{F}\{v\}(f) = \sum_{n=-\infty}^{\infty} v[n]\cdot e^{-i 2\pi f n}\;, \quad f \in \mathbb{R}.
\end{align}</math>

The {{slink|Convolution#Discrete convolution|nopage=y}} of <math>u</math> and <math>v</math> is defined by''':'''

:<math>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].</math>

The [[Convolution#Discrete convolution|'''convolution theorem''']] for discrete sequences is''':'''<ref name=Proakis/><ref name=Oppenheim/>{{rp|p.60 (2.169)}}

{{Equation box 1
|indent=|cellpadding=0|border=0|background colour=white
|equation={{NumBlk|:|
<math>R(f) = \mathcal{F}\{u * v\}(f) =\ U(f) V(f).</math> &nbsp; &nbsp;
|{{EquationRef|Eq.3}} }} }}

=== Periodic convolution ===
<math>U(f)</math> and <math>V(f),</math> as defined above, are periodic, with a period of 1.  Consider <math>N</math>-periodic sequences <math>u_{_N}</math> and <math>v_{_N}</math>''':'''

:<math>u_{_N}[n]\ \triangleq \sum_{m=-\infty}^{\infty} u[n-mN]</math> &nbsp; and &nbsp; <math>v_{_N}[n]\ \triangleq \sum_{m=-\infty}^{\infty} v[n-mN], \quad n \in \mathbb{Z}.</math>

These functions occur as the result of sampling <math>U</math> and <math>V</math> at intervals of <math>1/N</math> and performing an inverse '''[[discrete Fourier transform]]''' (DFT) on <math>N</math> samples  (see {{slink|Discrete-time_Fourier_transform#Sampling_the_DTFT|nopage=y}}).  The discrete convolution''':'''

:<math>\{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]</math>

is also <math>N</math>-periodic, and is called a '''[[periodic convolution]]'''. Redefining the <math>\mathcal{F}</math> operator as the <math>N</math>-length DFT, the corresponding theorem is:<ref name="Rabiner" /><ref name="Oppenheim" />{{rp|p. 548}}

{{Equation box 1
|indent=|cellpadding=0|border=0|background colour=white
|equation={{NumBlk|:|
<math>\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}.</math> &nbsp; &nbsp;
|{{EquationRef|Eq.4a}} }} }}

And therefore''':'''

{{Equation box 1
|indent=|cellpadding=0|border=0|background colour=white
|equation={{NumBlk|:|
<math>\{u_{_N} * v\}[n] =\ \mathcal{F}^{-1}\{\mathcal{F}\{u_{_N}\} \cdot \mathcal{F}\{v_{_N}\}\}.</math> &nbsp; &nbsp;
|{{EquationRef|Eq.4b}} }} }}

Under the right conditions, it is possible for this <math>N</math>-length sequence to contain a distortion-free segment of a <math>u*v</math> convolution.  But when the non-zero portion of the <math>u(n)</math> or <math>v(n)</math> sequence is equal or longer than <math>N,</math> some distortion is inevitable.&nbsp; Such is the case when the <math>V(k/N)</math> sequence is obtained by directly sampling the DTFT of the infinitely long {{slink|Hilbert transform|Discrete Hilbert transform|nopage=y}} [[impulse response]].{{efn-ua
|1=An example is the [[MATLAB]] function, '''[http://www.mathworks.com/help/toolbox/signal/ref/hilbert.html;jsessionid=67ed4e69e9729363548abed31054 hilbert(u,N)]'''.}}

For <math>u</math> and <math>v</math> sequences whose non-zero duration is less than or equal to <math>N,</math> a final simplification is:
{{Equation box 1
|title='''[[Circular convolution]]'''
|indent=|cellpadding=6 |border= |border colour=#0073CF |background colour=#F5FFFA
|equation={{NumBlk|:|
<math>\{u_{_N} * v\}[n] =\ \mathcal{F}^{-1}\{\mathcal{F}\{u\} \cdot \mathcal{F}\{v\}\}.</math> &nbsp; &nbsp;
|{{EquationRef|Eq.4c}} }} }}

This form is often used to efficiently implement numerical convolution by [[computer]].  (see {{slink|Convolution|Fast convolution algorithms|nopage=y}} and {{slink|Circular_convolution|Example|nopage=y}})

As a partial reciprocal, it has been shown <ref>{{cite book |last1=Amiot |first1=Emmanuel |title=Music through Fourier Space |series=Computational Music Science |date=2016 |publisher=Springer |location=Zürich |isbn=978-3-319-45581-5 |page=8 |doi=10.1007/978-3-319-45581-5 |s2cid=6224021 |url=https://link.springer.com/book/10.1007/978-3-319-45581-5 |ref=Theorem 1.11}}</ref>
that any linear transform that turns convolution into a product is the DFT (up to a permutation of coefficients).

{{Collapse top|title=Derivations of Eq.4}}
A time-domain derivation proceeds as follows''':'''

:<math>
\begin{align}
\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^{-i 2\pi kn/N}\\
&= \sum_{m=0}^{N-1} u_{_N}[m] \left(\sum_{n=0}^{N-1} v_{_N}[n-m]\cdot e^{-i 2\pi kn/N}\right)\\
&= \sum_{m=0}^{N-1} u_{_N}[m]\cdot e^{-i 2\pi km/N}
\underbrace{
\left(\sum_{n=0}^{N-1} v_{_N}[n-m]\cdot e^{-i 2\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^{-i 2\pi km/N}\right)}_{\scriptstyle{\rm DFT}\displaystyle\{u_{_N}\}[k]}
\left(\scriptstyle{\rm DFT}\displaystyle\{v_{_N}\}[k]\right).
\end{align}
</math>

A frequency-domain derivation follows from {{slink|DTFT|Periodic data|nopage=y}}, which indicates that the DTFTs can be written as''':'''

:<math>
\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)}
</math>

:<math>
\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).
</math>

The product with <math>V(f)</math> is thereby reduced to a discrete-frequency function''':'''

:<math>
\begin{align}
\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{align}
</math>

where the equivalence of <math>V(k/N)</math> and <math>\left(\scriptstyle{\rm DFT}\displaystyle\{v_{_N}\}[k]\right)</math> follows from {{slink|DTFT|Sampling the DTFT|nopage=y}}.  Therefore, the equivalence of (5a) and (5b) requires:

:<math>\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).</math>

<br>We can also verify the inverse DTFT of (5b)''':'''

:<math>
\begin{align}
(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^{i 2 \pi f n} 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^{i 2 \pi f n} 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^{i 2 \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{align}
</math>
{{Collapse bottom}}