Whittaker–Shannon interpolation formula

From Wikipedia, the free encyclopedia

The Whittaker–Shannon interpolation formula is a method to reconstruct a continuous-time bandlimited signal from a set of equally spaced samples.

The interpolation formula, as it is commonly called, dates back to works of E. Borel in 1898, and E. T. Whittaker in 1915, and was cited from works of J. M. Whittaker in 1935 in the formulation of the Nyquist–Shannon sampling theorem by Claude Shannon in 1949. It is also commonly called Shannon's interpolation formula and Whittaker's interpolation formula. E. T. Whittaker, who published it in 1915, called it the Cardinal series.

The sampling theorem states that, under certain limiting conditions, a function x(T) can be recovered exactly from its samples,   x[n] = x(nT), by the Whittaker–Shannon interpolation formula:

x(t) = \sum_{n=-\infty}^{\infty} x[n] \cdot {\rm sinc}\left(\frac{t - nT}{T}\right)\,

where T = 1/fs is the sampling interval, fs is the sampling rate, and sinc(x) is the normalized sinc function.

Contents

[edit] Limiting conditions

Spectrum of a bandlimited signal as a function of frequency. The two-sided bandwidth RN = 2B is known as the Nyquist rate for the signal.
Spectrum of a bandlimited signal as a function of frequency. The two-sided bandwidth RN = 2B is known as the Nyquist rate for the signal.

There are two limiting conditions that the function x(t) must satisfy in order for the interpolation formula to be guaranteed to reconstruct it exactly:

  1. x(t) must be bandlimited. In other words, the function must have a Fourier transform \scriptstyle \mathcal{F} \{x(t) \} = X(f) = 0 \ for |f| > B for some maximum frequency, B > 0.
  2. The sampling rate, fs, must exceed twice the bandwidth, 2B. Equivalently:
T < \frac{1}{2B}.

The interpolation formula reconstructs the original signal x(t), as long as these two conditions are met. Otherwise, aliasing occurs; that is, frequencies at or above fs/2 are erroneously reconstructed. See Aliasing for further discussion on this point.

[edit] Interpolation as convolution sum

The interpolation formula is derived in the Nyquist-Shannon sampling theorem article, which points out that it can be also be expressed as the convolution of an infinite impulse train with a sinc function:

x(t) = \left( \sum_{n=-\infty}^{\infty} x[n]\cdot \delta \left( t - nT \right) \right) * {\rm sinc}\left(\frac{t}{T}\right) .

This is equivalent to filtering the impulse train with an ideal (brick-wall) low-pass filter.

[edit] Convergence

The interpolation formula always converges absolutely and locally uniform as long as

\sum_{n\in\Z,\,n\ne 0}\left|\frac{x[n]}n\right|<\infty.

By the Hölder inequality this is satisfied if the sequence \scriptstyle (x[n])_{n\in\Z} belongs to any of the \scriptstyle\ell^p(\Z,\mathbb C) spaces with 1 < p < ∞, that is

\sum_{n\in\Z}\left|x[n]\right|^p<\infty.

This condition is sufficient, but not necessary. For example, the sum will generally converge if the sample sequence comes from sampling almost any stationary process, in which case the sample sequence is not square summable, and is not in any \scriptstyle\ell^p(\Z,\mathbb C) space.

[edit] Stationary random processes

If x[n] is an infinite sequence of samples of a sample function of a wide-sense stationary process, then it is not a member of any \scriptstyle\ell^p or Lp space, with probability 1; that is, the infinite sum of samples raised to a power p does not have a finite expected value. Nevertheless, the interpolation formula converges with probability 1. Convergence can readily be shown by computing the variances of truncated terms of the summation, and showing that the variance can be made arbitrarily small by choosing a sufficient number of terms. If the process mean is nonzero, then pairs of terms need to be considered to also show that the expected value of the truncated terms converges to zero.

Since a random process does not have a Fourier transform, the condition under which the sum converges to the original function must also be different. A stationary random process does have an autocorrelation function and hence a spectral density according to the Wiener–Khinchin theorem. A suitable condition for convergence to a sample function from the process is that the spectral density of the process be zero at all frequencies equal to and above half the sample rate.

[edit] See also