Namespaces
Variants
Actions

Difference between revisions of "Shannon sampling theorem"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
 
(3 intermediate revisions by 2 users not shown)
Line 1: Line 1:
Every signal function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s1201201.png" /> that is band-limited to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s1201202.png" /> for some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s1201203.png" /> can be completely reconstructed from its sample values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s1201204.png" />, taken at nodes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s1201205.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s1201206.png" />, equally spaced apart on the real axis <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s1201207.png" />, in the form
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s1201208.png" /></td> </tr></table>
+
\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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s1201209.png" />. The latter series will be denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s12012010.png" />. Here, band-limited means that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s12012011.png" /> contains no frequencies higher than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s12012012.png" /> or, in mathematical terms, that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s12012013.png" /> is continuous, square-integrable on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s12012014.png" /> (i.e., of finite energy) and that its <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s12012015.png" />-Fourier transform <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s12012016.png" /> vanishes outside <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s12012017.png" /> (see [[#References|[a13]]], [[#References|[a10]]], p. 51, [[#References|[a8]]], [[#References|[a5]]], [[#References|[a14]]]).
+
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 [[#References|[a13]]], [[#References|[a10]]], p. 51, [[#References|[a8]]], [[#References|[a5]]], [[#References|[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.
 
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|Paley–Wiener theorem]], they can be extended to an [[Entire function|entire function]] on the whole complex plane <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s12012018.png" />. 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 [[#References|[a2]]] and states that if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s12012019.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s12012020.png" />, then for the aliasing error <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s12012021.png" /> one has the estimate
+
Band-limited signals suffer under severe restrictions, since, by the [[Paley–Wiener theorem|Paley–Wiener theorem]], they can be extended to an [[Entire function|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 [[#References|[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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s12012022.png" /></td> </tr></table>
+
\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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s12012023.png" /> uniformly in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s12012024.png" />. In particular, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s12012025.png" /> is band-limited to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s12012026.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s12012027.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s12012028.png" />.
+
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|Poisson summation formula]] (Fourier analysis) and the Cauchy integral formula (complex analysis, cf. [[Cauchy integral theorem|Cauchy integral theorem]]). Further, the approximate sampling theorem is equivalent to the general [[Poisson summation formula|Poisson summation formula]], the [[Euler–MacLaurin formula|Euler–MacLaurin formula]], the Abel–Plana summation formula (numerical mathematics), and to the basic functional equation for the [[Riemann zeta-function|Riemann zeta-function]] (number theory). The Poisson summation formula can also be interpreted as a trace formula [[#References|[a15]]], p. 48. Two final connections are that the series <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s12012029.png" /> can also be regarded as a limiting case of the [[Lagrange interpolation formula|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., [[#References|[a7]]], [[#References|[a4]]] and the references therein.
+
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|Poisson summation formula]] (Fourier analysis) and the Cauchy integral formula (complex analysis, cf. [[Cauchy integral theorem|Cauchy integral theorem]]). Further, the approximate sampling theorem is equivalent to the general [[Poisson summation formula|Poisson summation formula]], the [[Euler–MacLaurin formula|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 [[#References|[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|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., [[#References|[a7]]], [[#References|[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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s12012030.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s12012031.png" />. All such errors (including the aliasing error) can occur in combination (see, e.g., [[#References|[a8]]]).
+
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., [[#References|[a8]]]).
  
Sampling theory can be put in an abstract setting, in which the band-limited function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s12012032.png" /> is represented by a sampling series of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s12012033.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s12012034.png" /> is a discrete subset of the domain of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s12012035.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s12012036.png" /> 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|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s12012037.png" /> itself, but also from a transformed version of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s12012038.png" />), and multi-dimensional sampling. See [[#References|[a10]]].
+
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|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 [[#References|[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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s12012039.png" /> by a general locally compact Abelian group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s12012040.png" />, and the frequence domain, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s12012041.png" /> again, by the dual group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s12012042.png" />. Instead of sampling at regularly distributed points <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s12012043.png" />, a function defined on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s12012044.png" /> is now sampled at the points of a discrete subgroup of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s12012045.png" />. See [[#References|[a1]]].
+
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 [[#References|[a1]]].
  
When the [[Fourier transform|Fourier transform]] is replaced by the [[Mellin transform|Mellin transform]], with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120120/s12012046.png" />, one is led to the exponential sampling theorem of N. Ostrowski and others (1981); see [[#References|[a6]]].
+
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 [[#References|[a6]]].
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  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)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  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)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  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)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  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))</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  P.L. Butzer,  W. Splettstösser,  R.L. Stens,  "The sampling theorem and linera predeiction in signal analysis"  ''Jahresber. Deutsch. Math. Ver.'' , '''90'''  (1988)  pp. 1–70</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  J.R. Higgins,  "Five short stories about the cardinal series"  ''Bull. Amer. Math. Soc.'' , '''12'''  (1985)  pp. 45–89</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  J.R. Higgins,  "Sampling theory in Fourier and signal analysis: Foundations" , Clarendon Press  (1996)</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top">  "Sampling theory in Fourier and signal analysis: Advanced topics"  J.R. Higgins (ed.)  R.L. Stens (ed.) , Clarendon Press  (1999)</TD></TR><TR><TD valign="top">[a12]</TD> <TD valign="top">  A.J. Jerri,  "The Shannon sampling theorem: its various extensions and applications: A tutorial review"  ''Proc. IEEE'' , '''65'''  (1977)  pp. 1565–1589</TD></TR><TR><TD valign="top">[a13]</TD> <TD valign="top">  "Claude Elwood Shannon: Collected papers"  N.J.A. Sloane (ed.)  A.D. Wyer (ed.) , IEEE  (1993)</TD></TR><TR><TD valign="top">[a14]</TD> <TD valign="top">  A.I. Zayed,  "Advances in Shannon's sampling theory" , CRC  (1993)</TD></TR><TR><TD valign="top">[a15]</TD> <TD valign="top">  A. Terras,  "Harmonic analysis on symmetric spaces and applications" , '''1''' , Springer  (1985)</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  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)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  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)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  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)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  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))</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  J.R. Higgins,  "Five short stories about the cardinal series"  ''Bull. Amer. Math. Soc.'' , '''12'''  (1985)  pp. 45–89</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  J.R. Higgins,  "Sampling theory in Fourier and signal analysis: Foundations" , Clarendon Press  (1996)</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top">  "Sampling theory in Fourier and signal analysis: Advanced topics"  J.R. Higgins (ed.)  R.L. Stens (ed.) , Clarendon Press  (1999)</TD></TR><TR><TD valign="top">[a12]</TD> <TD valign="top">  A.J. Jerri,  "The Shannon sampling theorem: its various extensions and applications: A tutorial review"  ''Proc. IEEE'' , '''65'''  (1977)  pp. 1565–1589</TD></TR><TR><TD valign="top">[a13]</TD> <TD valign="top">  "Claude Elwood Shannon: Collected papers"  N.J.A. Sloane (ed.)  A.D. Wyer (ed.) , IEEE  (1993)</TD></TR><TR><TD valign="top">[a14]</TD> <TD valign="top">  A.I. Zayed,  "Advances in Shannon's sampling theory" , CRC  (1993)</TD></TR><TR><TD valign="top">[a15]</TD> <TD valign="top">  A. Terras,  "Harmonic analysis on symmetric spaces and applications" , '''1''' , Springer  (1985)</TD></TR>
 +
</table>

Latest revision as of 07:01, 19 March 2024

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=11459
This article was adapted from an original article by P.L. Butzer (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article