Nyquist theorem

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,