Sampling—50 Years After Shannon

MICHAEL UNSER, FELLOW, IEEE

This paper presents an account of the current state of sampling, 50 years after Shannon’s formulation of the sampling theorem. The emphasis is on regular sampling, where the grid is uniform. This topic has benefited from a strong research revival during the past few years, thanks in part to the mathematical connections that were made with wavelet theory. To introduce the reader to the modern,

Hilbert-space formulation, we reinterpret Shannon’s sampling procedure as an orthogonal projection onto the subspace of band-limited functions. We then extend the standard sampling paradigm for a representation of functions in the more general class of “shift-invariant” functions spaces, including splines and wavelets. Practically, this allows for simpler—and possibly more realistic—interpolation models, which can be used in conjunction with a much wider class of (anti-aliasing) prefilters that are not necessarily ideal low-pass. We summarize and discuss the results available for the determination of the approximation error and of the sampling rate when the input of the system is essentially arbitrary; e.g., nonbandlimited. We also review variations of sampling that can be understood from the same unifying perspective. These include wavelets, multiwavelets, Papoulis generalized sampling, finite elements, and frames. Irregular sampling and radial basis functions are briefly mentioned.

Keywords—Band-limited functions, Hilbert spaces, interpolation, least squares approximation, projection operators, sampling, sampling theorem, Shannon, splines, wavelets.

I. INTRODUCTION

In 1949, Shannon published the paper “Communication in the Presence of Noise,” which set the foundation of information theory [105], [106]. This paper is a masterpiece; both in terms of achievement and conciseness. It is undoubtedly one of the theoretical works that has had the greatest impact on modern electrical engineering [145]. In order to formulate his rate/distortion theory, Shannon needed a general mechanism for converting an analog signal into a sequence of numbers.

This led him to state the classical sampling theorem at the very beginning of his paper in the following terms.

Theorem 1 [Shannon]: If a function contains no frequencies higher than (in radians per second), it is completely determined by giving its ordinates at a series of points spaced seconds apart.

Manuscript received September 17, 1999; revised January 4, 2000.

The author is with the Biomedical Imaging Group, Swiss Federal Institute of Technology Lausanne CH-1015 Lausanne EPFL, Switzerland (e-mail:

Michael.Unser@epfl.ch).

Publisher Item Identifier S 0018-9219(00)02874-7.

While Shannon must get full credit for formalizing this result and for realizing its potential for communication theory and for signal processing, he did not claim it as his own. In fact, just below the theorem, he wrote: “this is a fact which is common knowledge in the communication art.” He was also well aware of equivalent forms of the theorem that had appeared in the mathematical literature; in particular, the work of Whittaker [144]. In the Russian literature, this theorem was introduced to communication theory by Kotel’nikov [67], [68].

The reconstruction formula that complements the sampling theorem is (1) in which the equidistant samples of may be interpreted as coefficients of some basis functions obtained by appropriate shifting and rescaling of the sinc-function: sinc . Formula (1) is exact if is bandlimited to ; this upper limit is the Nyquist frequency, a term that was coined by Shannon in recognition of Nyquist’s important contributions in communication theory [88]. In the mathematical literature, (1) is known as the cardinal series expansion; it is often attributed to Whittaker in 1915 [26], [143] but has also been traced back much further [14], [58].

Shannon’s sampling theorem and its corresponding reconstruction formula are best understood in the frequency domain, as illustrated in Fig. 1. A short reminder of the key sampling formulas is provided in Appendix A to make the presentation self-contained.

Nowadays the sampling theorem plays a crucial role in signal processing and communications: it tells us how to convert an analog signal into a sequence of numbers, which can then be processed digitally—or coded—on a computer.

While Shannon’s result is very elegant and has proven to be extremely fruitful, there are several problems associated with it. First, it is an idealization: real world signals or images are never exactly bandlimited [108]. Second, there is no such device as an ideal (anti-aliasing or reconstruction) low-pass filter. Third, Shannon’s reconstruction formula is rarely used in practice (especially with images) because of the slow decay of the sinc function [91]. Instead, practitioners typically rely on much simpler techniques such as 0018–9219/00$10.00 © 2000 IEEE

PROCEEDINGS OF THE IEEE, VOL. 88, NO. 4, APRIL 2000 569

Fig. 1. Frequency interpretation of the sampling theorem: (a)

Fourier transform of the analog input signal f(x), (b) the sampling process results in a periodization of the Fourier transform, and (c) the analog signal is reconstructed by ideal low-pass filtering; a perfect recovery is possible provided that ! =T . linear interpolation. Despite these apparent mismatches with the physical world, we will show that a reconciliation is possible and that Shannon’s sampling theory, in its modern and extended versions, can perfectly handle such “nonideal” situations.

Ten to 15 years ago, the subject of sampling had reached what seemed to be a very mature state [26], [62]. The research in this area had become very mathematically oriented, with less and less immediate relevance to signal processing and communications. Recently, there has been strong revival of the subject, which was motivated by the intense activity taking place around wavelets (see [7], [35], [80], and [85]).