Difference between revisions of "Nyquist theorem"

From TORI
Jump to navigation Jump to search
 
m (Text replacement - "\$([^\$]+)\$" to "\\(\1\\)")
 
Line 1: Line 1:
 
[[Nyquist theorem]] refers to representation of a function, continuous at least along the real axis, through the linear combination of equidistantly–displaced functions [[sinc]]:
 
[[Nyquist theorem]] refers to representation of a function, continuous at least along the real axis, through the linear combination of equidistantly–displaced functions [[sinc]]:
   
$\displaystyle
+
\(\displaystyle
 
\mathrm{sinc}(z)=\frac{\sin(z)}{z}
 
\mathrm{sinc}(z)=\frac{\sin(z)}{z}
  +
\)
$
 
   
 
at zero sinc is defined to be unity; then sinc appears to be [[entire function]].
 
at zero sinc is defined to be unity; then sinc appears to be [[entire function]].
Line 9: Line 9:
 
For the [[Nyquist theorem]] it is convenient to scale the argument of the [[sinc]] function, working with function [[sink]] such that
 
For the [[Nyquist theorem]] it is convenient to scale the argument of the [[sinc]] function, working with function [[sink]] such that
   
$\displaystyle \mathrm{sink}(z)=\mathrm{sink}(\pi z)=\frac{\sin(\pi z)}{\pi z}$
+
\(\displaystyle \mathrm{sink}(z)=\mathrm{sink}(\pi z)=\frac{\sin(\pi z)}{\pi z}\)
   
 
The [[Nyquist theorem]] is important tool of the digital signal processing. Unfortunately, in the literature it is presented in a complicated way; it seems, the editors, who had edited the texts about [[Nyquist theorem]], had neither proved it nor used it.
 
The [[Nyquist theorem]] is important tool of the digital signal processing. Unfortunately, in the literature it is presented in a complicated way; it seems, the editors, who had edited the texts about [[Nyquist theorem]], had neither proved it nor used it.
Line 16: Line 16:
 
==Statement==
 
==Statement==
   
Let function $f$ be defined at least for real values of the argument, and let it have restricted spectrum, id est, at least for real $x$, it can be represented as follows:
+
Let function \(f\) be defined at least for real values of the argument, and let it have restricted spectrum, id est, at least for real \(x\), it can be represented as follows:
   
$\displaystyle
+
\(\displaystyle
f(x)=\int_{-\infty}^{\infty} \mathrm d k ~ F_k~ \theta(1\!-\!|2k|)~\exp(2 \pi \mathrm i k x)$
+
f(x)=\int_{-\infty}^{\infty} \mathrm d k ~ F_k~ \theta(1\!-\!|2k|)~\exp(2 \pi \mathrm i k x)\)
   
where $\theta$ is function, that is zero for negative argument and unity for positive argument.
+
where \(\theta\) is function, that is zero for negative argument and unity for positive argument.
   
 
Let
 
Let
   
$\displaystyle
+
\(\displaystyle
u(x)=\sum_m ~f(m\!+\!\varphi) ~\mathrm{sink}(x\!-\!m\!-\!\varphi)$
+
u(x)=\sum_m ~f(m\!+\!\varphi) ~\mathrm{sink}(x\!-\!m\!-\!\varphi)\)
   
be the approximation of function $f$ based on its values at the real equidistant points, diplaced with real constant $\varphi$ from the integer values. Summation here is performed on the set of integer values of $m$.
+
be the approximation of function \(f\) based on its values at the real equidistant points, diplaced with real constant \(\varphi\) from the integer values. Summation here is performed on the set of integer values of \(m\).
   
   
Then, at least for the real values of the argument, $u$ does not depend on $\varphi$ and, for real argument, $u=f$.
+
Then, at least for the real values of the argument, \(u\) does not depend on \(\varphi\) and, for real argument, \(u=f\).
   
 
==Proof==
 
==Proof==
   
The proof is based on the inigueness of the Fourier representaion. It refers to the [[Fourier transform]]s of functions $f$ and $u$:
+
The proof is based on the inigueness of the Fourier representaion. It refers to the [[Fourier transform]]s of functions \(f\) and \(u\):
   
$\displaystyle
+
\(\displaystyle
 
F_k=\int_{-\infty}^{\infty} \exp(2\pi \mathrm i kx) ~f(x)~\mathrm d x
 
F_k=\int_{-\infty}^{\infty} \exp(2\pi \mathrm i kx) ~f(x)~\mathrm d x
  +
\)
$
 
   
$\displaystyle
+
\(\displaystyle
 
U_k=\int_{-\infty}^{\infty} \exp(2\pi \mathrm i kx) ~u(x)~\mathrm d x
 
U_k=\int_{-\infty}^{\infty} \exp(2\pi \mathrm i kx) ~u(x)~\mathrm d x
  +
\)
$
 
   
 
The last expression can be transformed in the following way:
 
The last expression can be transformed in the following way:
   
$\displaystyle
+
\(\displaystyle
U_k=\int_{-\infty}^{\infty} \exp(2\pi \mathrm i kx) ~\sum_{m} ~f(m\!+\!\varphi)~\mathrm{sink}(x)~\mathrm d x$
+
U_k=\int_{-\infty}^{\infty} \exp(2\pi \mathrm i kx) ~\sum_{m} ~f(m\!+\!\varphi)~\mathrm{sink}(x)~\mathrm d x\)
   
Now I substitute representation of $f$ through its Fourier transform $F$, this gives
+
Now I substitute representation of \(f\) through its Fourier transform \(F\), this gives
   
  +
\(
$
 
 
\displaystyle
 
\displaystyle
 
U_k=\int_{-\infty}^{\infty}
 
U_k=\int_{-\infty}^{\infty}
\exp(2\pi \mathrm i kx) ~\sum_{m} ~ \int_{-\infty}^{\infty}~\mathrm d p F_p \theta(1-|2p|) \exp(-2\pi\mathrm i p (m\!+\!\varphi)) ~\mathrm{sink}(x)~\mathrm d x$
+
\exp(2\pi \mathrm i kx) ~\sum_{m} ~ \int_{-\infty}^{\infty}~\mathrm d p F_p \theta(1-|2p|) \exp(-2\pi\mathrm i p (m\!+\!\varphi)) ~\mathrm{sink}(x)~\mathrm d x\)
   
$=~ \sum_{m} ~f(m\!+\!\varphi) \int_{-\infty}^{\infty} \exp(2\pi \mathrm i kx) ~\mathrm{sink}(x\!-\!m\!-\!\varphi)~\mathrm d x
+
\(=~ \sum_{m} ~f(m\!+\!\varphi) \int_{-\infty}^{\infty} \exp(2\pi \mathrm i kx) ~\mathrm{sink}(x\!-\!m\!-\!\varphi)~\mathrm d x
  +
\)
$
 
   
In the last integral, replace $x$ to $~x\!+\!m\!+\!\varphi ~$; this gives
+
In the last integral, replace \(x\) to \(~x\!+\!m\!+\!\varphi ~\); this gives
   
$\displaystyle
+
\(\displaystyle
U_k= \sum_{m} ~f(m\!+\!\varphi) ~\int_{-\infty}^{\infty} \exp(-2\pi \mathrm i k(x\!+\!m\!+\!\varphi)) ~\mathrm{sink}(x)~\mathrm d x$
+
U_k= \sum_{m} ~f(m\!+\!\varphi) ~\int_{-\infty}^{\infty} \exp(-2\pi \mathrm i k(x\!+\!m\!+\!\varphi)) ~\mathrm{sink}(x)~\mathrm d x\)
   
$\displaystyle
+
\(\displaystyle
U_k= \sum_{m} ~f(m\!+\!\varphi) \exp(-2\pi \mathrm i k(\!m\!+\!\varphi)) ~\int_{-\infty}^{\infty} \exp(-2\pi \mathrm i k x) ~\mathrm{sink}(x)~\mathrm d x$
+
U_k= \sum_{m} ~f(m\!+\!\varphi) \exp(-2\pi \mathrm i k(\!m\!+\!\varphi)) ~\int_{-\infty}^{\infty} \exp(-2\pi \mathrm i k x) ~\mathrm{sink}(x)~\mathrm d x\)
   
Due to the properties of function [[sink]], the last integral gives $\theta(1-|2k|)$; so, the expression can be rewritten as
+
Due to the properties of function [[sink]], the last integral gives \(\theta(1-|2k|)\); so, the expression can be rewritten as
   
$\displaystyle
+
\(\displaystyle
 
U_k= \sum_{m} ~f(m\!+\!\varphi) ~ \exp(-2\pi \mathrm i k(\!m\!+\!\varphi)) ~ \theta(1-|2k|)
 
U_k= \sum_{m} ~f(m\!+\!\varphi) ~ \exp(-2\pi \mathrm i k(\!m\!+\!\varphi)) ~ \theta(1-|2k|)
  +
\)
$
 
   
Now, substitute in the expression the representaiton of $f$ through its courier-transform $F$; this gives
+
Now, substitute in the expression the representaiton of \(f\) through its courier-transform \(F\); this gives
   
$\displaystyle U_k=\sum_{m} ~\int_{-\infty}^{\infty} \mathrm d p~F_p ~\theta(1-|2p|)~\exp(2\pi \mathrm i p(\!m\!+\!\varphi))
+
\(\displaystyle U_k=\sum_{m} ~\int_{-\infty}^{\infty} \mathrm d p~F_p ~\theta(1-|2p|)~\exp(2\pi \mathrm i p(\!m\!+\!\varphi))
~\exp(-2\pi \mathrm i k(\!m\!+\!\varphi)) ~ \theta(1-|2k|)$
+
~\exp(-2\pi \mathrm i k(\!m\!+\!\varphi)) ~ \theta(1-|2k|)\)
   
$\displaystyle U_k=\int_{-\infty}^{\infty} \mathrm d p~F_p ~\theta(1-|2p|)~ \theta(1-|2k|)~\sum_{m} ~\exp(2\pi \mathrm i (p\!-\!k)(\!m\!+\!\varphi))
+
\(\displaystyle U_k=\int_{-\infty}^{\infty} \mathrm d p~F_p ~\theta(1-|2p|)~ \theta(1-|2k|)~\sum_{m} ~\exp(2\pi \mathrm i (p\!-\!k)(\!m\!+\!\varphi))
  +
\)
$
 
   
The last sum gives $\delta(p\!-\!k)$.
+
The last sum gives \(\delta(p\!-\!k)\).
 
The integration gives the identity
 
The integration gives the identity
   
$U_k=F_k$
+
\(U_k=F_k\)
   
This leads to the equality of their inverse Fourier transforms, $u=f$.
+
This leads to the equality of their inverse Fourier transforms, \(u=f\).
   
 
(End of proof)
 
(End of proof)
   
In such a way, the set of equidistant samples allows to recover the function, and the recovered function does not depend on the constant displacement $\mathrm \phi$ of the equidistant points of the evaluation.
+
In such a way, the set of equidistant samples allows to recover the function, and the recovered function does not depend on the constant displacement \(\mathrm \phi\) of the equidistant points of the evaluation.
   
 
==Application==
 
==Application==
   
Function $f$ with restricted spectrum (that satisfies the conditions of the
+
Function \(f\) with restricted spectrum (that satisfies the conditions of the
[[Nyquist theorem]]) can be prepared from any bounded function $g$, even for that defied as set of delta–function with displaced argument, by the appropriate filtration of the Fourier–transform:
+
[[Nyquist theorem]]) can be prepared from any bounded function \(g\), even for that defied as set of delta–function with displaced argument, by the appropriate filtration of the Fourier–transform:
   
$\displaystyle
+
\(\displaystyle
 
G_k=\int_{-\infty}^{\infty} \exp(2\pi \mathrm i kx) ~g(x)~\mathrm d x
 
G_k=\int_{-\infty}^{\infty} \exp(2\pi \mathrm i kx) ~g(x)~\mathrm d x
  +
\)
$
 
   
  +
\(
$
 
 
F_k=(1-\theta(2k)) G(k)
 
F_k=(1-\theta(2k)) G(k)
  +
\)
$
 
   
Then we may reconstruct $f$ from $F$ by the inverse Fourier transform operation.
+
Then we may reconstruct \(f\) from \(F\) by the inverse Fourier transform operation.
No preliminary smoothing of function $g$ is necessary for such a filtration.
+
No preliminary smoothing of function \(g\) is necessary for such a filtration.
   
The coordinate $x$ in the formulas above may have sense of time.
+
The coordinate \(x\) in the formulas above may have sense of time.
 
Practically, the oscilloscope cannot provide the unlimited set of data; some moment the registration is swithced on and some moment the registration is switched out. Often, the number of data does not exceed a million. However, one may assume, that the registration begins well before the interesting process begins, and ends well after the interesting process stops. The "missed" data may be set to zero; this allows the numerical approximations of the formulas above with finite number of operations. Finiteness of the number of operation is important quality of every computational algorithm.
 
Practically, the oscilloscope cannot provide the unlimited set of data; some moment the registration is swithced on and some moment the registration is switched out. Often, the number of data does not exceed a million. However, one may assume, that the registration begins well before the interesting process begins, and ends well after the interesting process stops. The "missed" data may be set to zero; this allows the numerical approximations of the formulas above with finite number of operations. Finiteness of the number of operation is important quality of every computational algorithm.
   

Latest revision as of 18:48, 30 July 2019

Nyquist theorem refers to representation of a function, continuous at least along the real axis, through the linear combination of equidistantly–displaced functions sinc:

\(\displaystyle \mathrm{sinc}(z)=\frac{\sin(z)}{z} \)

at zero sinc is defined to be unity; then sinc appears to be entire function.

For the Nyquist theorem it is convenient to scale the argument of the sinc function, working with function sink such that

\(\displaystyle \mathrm{sink}(z)=\mathrm{sink}(\pi z)=\frac{\sin(\pi z)}{\pi z}\)

The Nyquist theorem is important tool of the digital signal processing. Unfortunately, in the literature it is presented in a complicated way; it seems, the editors, who had edited the texts about Nyquist theorem, had neither proved it nor used it. For this reason, this theorem is loaded to TORI

Statement

Let function \(f\) be defined at least for real values of the argument, and let it have restricted spectrum, id est, at least for real \(x\), it can be represented as follows:

\(\displaystyle f(x)=\int_{-\infty}^{\infty} \mathrm d k ~ F_k~ \theta(1\!-\!|2k|)~\exp(2 \pi \mathrm i k x)\)

where \(\theta\) is function, that is zero for negative argument and unity for positive argument.

Let

\(\displaystyle u(x)=\sum_m ~f(m\!+\!\varphi) ~\mathrm{sink}(x\!-\!m\!-\!\varphi)\)

be the approximation of function \(f\) based on its values at the real equidistant points, diplaced with real constant \(\varphi\) from the integer values. Summation here is performed on the set of integer values of \(m\).


Then, at least for the real values of the argument, \(u\) does not depend on \(\varphi\) and, for real argument, \(u=f\).

Proof

The proof is based on the inigueness of the Fourier representaion. It refers to the Fourier transforms of functions \(f\) and \(u\):

\(\displaystyle F_k=\int_{-\infty}^{\infty} \exp(2\pi \mathrm i kx) ~f(x)~\mathrm d x \)

\(\displaystyle U_k=\int_{-\infty}^{\infty} \exp(2\pi \mathrm i kx) ~u(x)~\mathrm d x \)

The last expression can be transformed in the following way:

\(\displaystyle U_k=\int_{-\infty}^{\infty} \exp(2\pi \mathrm i kx) ~\sum_{m} ~f(m\!+\!\varphi)~\mathrm{sink}(x)~\mathrm d x\)

Now I substitute representation of \(f\) through its Fourier transform \(F\), this gives

\( \displaystyle U_k=\int_{-\infty}^{\infty} \exp(2\pi \mathrm i kx) ~\sum_{m} ~ \int_{-\infty}^{\infty}~\mathrm d p F_p \theta(1-|2p|) \exp(-2\pi\mathrm i p (m\!+\!\varphi)) ~\mathrm{sink}(x)~\mathrm d x\)

\(=~ \sum_{m} ~f(m\!+\!\varphi) \int_{-\infty}^{\infty} \exp(2\pi \mathrm i kx) ~\mathrm{sink}(x\!-\!m\!-\!\varphi)~\mathrm d x \)

In the last integral, replace \(x\) to \(~x\!+\!m\!+\!\varphi ~\); this gives

\(\displaystyle U_k= \sum_{m} ~f(m\!+\!\varphi) ~\int_{-\infty}^{\infty} \exp(-2\pi \mathrm i k(x\!+\!m\!+\!\varphi)) ~\mathrm{sink}(x)~\mathrm d x\)

\(\displaystyle U_k= \sum_{m} ~f(m\!+\!\varphi) \exp(-2\pi \mathrm i k(\!m\!+\!\varphi)) ~\int_{-\infty}^{\infty} \exp(-2\pi \mathrm i k x) ~\mathrm{sink}(x)~\mathrm d x\)

Due to the properties of function sink, the last integral gives \(\theta(1-|2k|)\); so, the expression can be rewritten as

\(\displaystyle U_k= \sum_{m} ~f(m\!+\!\varphi) ~ \exp(-2\pi \mathrm i k(\!m\!+\!\varphi)) ~ \theta(1-|2k|) \)

Now, substitute in the expression the representaiton of \(f\) through its courier-transform \(F\); this gives

\(\displaystyle U_k=\sum_{m} ~\int_{-\infty}^{\infty} \mathrm d p~F_p ~\theta(1-|2p|)~\exp(2\pi \mathrm i p(\!m\!+\!\varphi)) ~\exp(-2\pi \mathrm i k(\!m\!+\!\varphi)) ~ \theta(1-|2k|)\)

\(\displaystyle U_k=\int_{-\infty}^{\infty} \mathrm d p~F_p ~\theta(1-|2p|)~ \theta(1-|2k|)~\sum_{m} ~\exp(2\pi \mathrm i (p\!-\!k)(\!m\!+\!\varphi)) \)

The last sum gives \(\delta(p\!-\!k)\). The integration gives the identity

\(U_k=F_k\)

This leads to the equality of their inverse Fourier transforms, \(u=f\).

(End of proof)

In such a way, the set of equidistant samples allows to recover the function, and the recovered function does not depend on the constant displacement \(\mathrm \phi\) of the equidistant points of the evaluation.

Application

Function \(f\) with restricted spectrum (that satisfies the conditions of the Nyquist theorem) can be prepared from any bounded function \(g\), even for that defied as set of delta–function with displaced argument, by the appropriate filtration of the Fourier–transform:

\(\displaystyle G_k=\int_{-\infty}^{\infty} \exp(2\pi \mathrm i kx) ~g(x)~\mathrm d x \)

\( F_k=(1-\theta(2k)) G(k) \)

Then we may reconstruct \(f\) from \(F\) by the inverse Fourier transform operation. No preliminary smoothing of function \(g\) is necessary for such a filtration.

The coordinate \(x\) in the formulas above may have sense of time. Practically, the oscilloscope cannot provide the unlimited set of data; some moment the registration is swithced on and some moment the registration is switched out. Often, the number of data does not exceed a million. However, one may assume, that the registration begins well before the interesting process begins, and ends well after the interesting process stops. The "missed" data may be set to zero; this allows the numerical approximations of the formulas above with finite number of operations. Finiteness of the number of operation is important quality of every computational algorithm.

References

http://redwood.berkeley.edu/bruno/npb261/aliasing.pdf Bruno A. Olshausen. Aliasing. PSC 129 Sensory processes. October 10, 2000.

http://en.wikipedia.org/wiki/Nyquist–Shannon_sampling_theorem

http://whatis.techtarget.com/definition/Nyquist-Theorem

Keywords

Entire function Fourier transform, Sinc, Sink,