Namespaces
Variants
Actions

Shannon sampling theorem

From Encyclopedia of Mathematics
Revision as of 07:01, 19 March 2024 by Chapoton (talk | contribs) (→‎References)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Every signal function $f(t)$ that is band-limited to $[-\pi W,\pi W]$ for some $W>0$ can be completely reconstructed from its sample values $f(k/W)$, taken at nodes $k/W$, $k\in Z$, equally spaced apart on the real axis $\mathbf{R}$, in the form

\begin{equation}\label{eq1}f(t)=\sum_{k=-\infty}^{\infty}f\bigg(\frac{k}{W}\bigg)\frac{\sin\pi(Wt-k)}{\pi(Wt-k)},\end{equation}

the series being absolutely and uniformly convergent on $\mathbf{R}$. The latter series will be denoted by $(S_Wf)(t)$. Here, band-limited means that $f$ contains no frequencies higher than $\pi W$ or, in mathematical terms, that $f$ is continuous, square-integrable on $\mathbf{R}$ (i.e., of finite energy) and that its $L_2(\mathbf{R})$-Fourier transform $\hat{f}(v)=(1/\sqrt{2\pi})\int_{-\infty}^{\infty}f(u)e^{-iuv}du$ vanishes outside $[-\pi W,\pi W]$ (see [a13], [a10], p. 51, [a8], [a5], [a14]).

The theorem is also associated with the names of E.T. Whittaker, K. Ogura, V.A. Kotel'nikov, H.P. Raabe, and I. Someya.

Band-limited signals suffer under severe restrictions, since, by the Paley–Wiener theorem, they can be extended to an entire function on the whole complex plane $\mathbf{C}$. Thus, they cannot be simultaneously time-limited. However, both situations are covered by the so-called "approximate sampling" theorem, which is valid for not necessarily band-limited signals. It is due to J.R. Brown [a2] and states that if $f\in L_2(\mathbf{R})\cap C(\mathbf{R})$ and $\hat{f}\in L_1(\mathbf{R})$, then for the aliasing error $(R_Wf)(t)=f(t)-(S_Wf)(t)$ one has the estimate

\begin{equation}\sup_{t\in R}|R_Wf(t)|\leq \sqrt{\frac{2}{\pi}}\int_{|v|>\pi W}|\hat{f}(v)|dv,\end{equation}

so that $\lim_{W\to \infty}(S_Wf)(t)=f(t)$ uniformly in $t\in R$. In particular, if $f$ is band-limited to $[-\pi W,\pi W]$, then $f(t)=(S_Wf)(t)$ for $t\in \mathbf{R}$.

In essence, the sampling theorem is equivalent (in the sense that each can be deduced from the others) to five fundamental theorems in four different fields of mathematics. In fact, for band-limited functions the sampling theorem (including sampling of derivatives) is equivalent to the famous Poisson summation formula (Fourier analysis) and the Cauchy integral formula (complex analysis, cf. Cauchy integral theorem). Further, the approximate sampling theorem is equivalent to the general Poisson summation formula, the Euler–MacLaurin formula, the Abel–Plana summation formula (numerical mathematics), and to the basic functional equation for the Riemann zeta-function (number theory). The Poisson summation formula can also be interpreted as a trace formula [a15], p. 48. Two final connections are that the series $(S_Wf)(t)$ can also be regarded as a limiting case of the Lagrange interpolation formula (as the number of nodes tends to infinity), while the Gauss summation formula of special function theory is a particular case of Shannon's theorem. See, e.g., [a7], [a4] and the references therein.

There are several types of errors that may influence the accuracy of the reconstruction of a signal function from its sample values; namely, the truncation error, which arises if only a finite number of samples is taken into account, the amplitude error, also called quantization error, which arises when instead of the exact values $f(k/W)$ only approximate values are available, and the time jitter error, which arises when the sample points are not met correctly but might differ by some $\delta$. All such errors (including the aliasing error) can occur in combination (see, e.g., [a8]).

Sampling theory can be put in an abstract setting, in which the band-limited function $f$ is represented by a sampling series of the form $f(t)=\sum_kf(\lambda_k)S_k(t)$, where $\{\lambda_k\}$ is a discrete subset of the domain of $f$ and $\{S_k\}$ is a set of appropriate "reconstruction functions" forming a basis or frame for a suitable function space (most often, a Hilbert space with reproducing kernel; cf. also Hilbert space). The methods give some unification of the approaches, and facilitate connections with important principles of sampling theory, including the Nyquist–Landau minimal rate for stable sampling, and sets of stable sampling, interpolation or uniqueness. The approach is flexible, and applies to multi-band (i.e., the support of the Fourier transform is a union of several disjoint intervals), multi-channel (i.e., the samples are not all taken from $f$ itself, but also from a transformed version of $f$), and multi-dimensional sampling. See [a10].

The first study of sampling and reconstruction in an abstract harmonic analysis setting is due to I. Kluvánek (1965). He replaced the time domain $\mathbf{R}$ by a general locally compact Abelian group $G$, and the frequence domain, $\mathbf{R}$ again, by the dual group $\hat{G}$. Instead of sampling at regularly distributed points $\{k/W\}\subset \mathbf{R}$, a function defined on $G$ is now sampled at the points of a discrete subgroup of $G$. See [a1].

When the Fourier transform is replaced by the Mellin transform, with $G=\mathbf{R}_+$, one is led to the exponential sampling theorem of N. Ostrowski and others (1981); see [a6].

References

[a1] M.G. Beaty, M.M. Dodson, "Abstract harmonic analysis and the sampling theorem" J.R. Higgins (ed.) R.L. Stens (ed.) , Sampling Theory in Fourier and Signal Analysis: Advanced Topics , Clarendon Press (1999)
[a2] J.L. Brown Jr., "On the error in reconstructing a non-bandlimited function by means of the bandpass sampling theorem" J. Math. Anal. Appl. , 18 (1967) pp. 75–84
[a3] P.L. Butzer, "A survey of the Whittaker-Shannon sampling theorem and some of its extensions" J. Math. Research Exp. , 3 (1983) pp. 185–212
[a4] P.L. Butzer, M. Hauss, "Applications of sampling theory to combinatorial analysis, Stirling numbers, special functions and the Riemann zeta function" J.R. Higgins (ed.) R.L. Stens (ed.) , Sampling Theory in Fourier and Signal Analysis: Advanced Topics , Clarendon Press (1999)
[a5] P.L. Butzer, J.R. Higgins, R.L. Stens, "Sampling theory of signal analysis 1950-1995" J.P. Pier (ed.) , Development of Mathematics 1950-2000 , Birkhäuser (to appear)
[a6] P.L. Butzer, S. Jansche, "The exponential sampling theorem of signal analysis" Atti Sem. Fis. Univ. Modena , 46 (1998) pp. 99–122 (C. Bardaro and others (eds.): Conf. in Honour of C. Vinti (Perugia, Oct. 1996))
[a7] P.L. Butzer, G. Nasri-Roudsari, "Kramer's sampling theorem in signal analysis and its role in mathematics" J.M. Blackedge (ed.) , Image Processing: Math. Methods and Appl. , Inst. Math. Appl. New Ser. , 61 , Clarendon Press (1997) pp. 49–95
[a8] P.L. Butzer, W. Splettstösser, R.L. Stens, "The sampling theorem and linear prediction in signal analysis" Jahresber. Deutsch. Math. Ver. , 90 (1988) pp. 1–70
[a9] J.R. Higgins, "Five short stories about the cardinal series" Bull. Amer. Math. Soc. , 12 (1985) pp. 45–89
[a10] J.R. Higgins, "Sampling theory in Fourier and signal analysis: Foundations" , Clarendon Press (1996)
[a11] "Sampling theory in Fourier and signal analysis: Advanced topics" J.R. Higgins (ed.) R.L. Stens (ed.) , Clarendon Press (1999)
[a12] A.J. Jerri, "The Shannon sampling theorem: its various extensions and applications: A tutorial review" Proc. IEEE , 65 (1977) pp. 1565–1589
[a13] "Claude Elwood Shannon: Collected papers" N.J.A. Sloane (ed.) A.D. Wyer (ed.) , IEEE (1993)
[a14] A.I. Zayed, "Advances in Shannon's sampling theory" , CRC (1993)
[a15] A. Terras, "Harmonic analysis on symmetric spaces and applications" , 1 , Springer (1985)
How to Cite This Entry:
Shannon sampling theorem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Shannon_sampling_theorem&oldid=55656
This article was adapted from an original article by P.L. Butzer (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article