Whittaker–Shannon interpolation formula
Encyclopedia
The Whittaker–Shannon interpolation formula or sinc interpolation is a method to reconstruct a continuous-time bandlimited
signal from a set of equally spaced samples.
in 1915, and was cited from works of J. M. Whittaker in 1935, and 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:
where T = 1/fs is the sampling interval, fs is the sampling rate
, and sinc(x) is the normalized sinc function.
If the function x(t) is bandlimited, and sampled at a high enough rate, the interpolation formula is guaranteed to reconstruct it exactly. Formally, if there exists some B ≥ 0 such that
then the interpolation formula will exactly reconstruct the original x(t) from its samples. Otherwise, aliasing may occur; that is, frequencies at or above fs/2 may be erroneously reconstructed. See Aliasing
for further discussion on this point.
article, which points out that it can also be expressed as the convolution
of an infinite impulse train
with a sinc function:
This is equivalent to filtering the impulse train with an ideal (brick-wall) low-pass filter
.
By the Hölder inequality this is satisfied if the sequence
belongs to any of the 
spaces
with 1 < p < ∞, that is
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
space.
, then it is not a member of any
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.
Bandlimited
Bandlimiting is the limiting of a deterministic or stochastic signal's Fourier transform or power spectral density to zero above a certain finite frequency...
signal from a set of equally spaced samples.
Definition
The interpolation formula, as it is commonly called, dates back to the works of E. Borel in 1898, and E. T. WhittakerE. T. Whittaker
Edmund Taylor Whittaker FRS FRSE was an English mathematician who contributed widely to applied mathematics, mathematical physics and the theory of special functions. He had a particular interest in numerical analysis, but also worked on celestial mechanics and the history of physics...
in 1915, and was cited from works of J. M. Whittaker in 1935, and in the formulation of the Nyquist–Shannon sampling theorem
Nyquist–Shannon sampling theorem
The Nyquist–Shannon sampling theorem, after Harry Nyquist and Claude Shannon, is a fundamental result in the field of information theory, in particular telecommunications and signal processing. Sampling is the process of converting a signal into a numeric sequence...
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:
where T = 1/fs is the sampling interval, fs is the sampling rate
Sampling rate
The sampling rate, sample rate, or sampling frequency defines the number of samples per unit of time taken from a continuous signal to make a discrete signal. For time-domain signals, the unit for sampling rate is hertz , sometimes noted as Sa/s...
, and sinc(x) is the normalized sinc function.
Validity condition
- the function x(t) is bandlimited to bandwidth B; that is, it has a Fourier transformFourier transformIn mathematics, Fourier analysis is a subject area which grew from the study of Fourier series. The subject began with the study of the way general functions may be represented by sums of simpler trigonometric functions...
for |f| > B; and - the sampling rateSampling rateThe sampling rate, sample rate, or sampling frequency defines the number of samples per unit of time taken from a continuous signal to make a discrete signal. For time-domain signals, the unit for sampling rate is hertz , sometimes noted as Sa/s...
, fs, exceeds the Nyquist rateNyquist rateIn signal processing, the Nyquist rate, named after Harry Nyquist, is two times the bandwidth of a bandlimited signal or a bandlimited channel...
, twice the bandwidth: fs > 2B. Equivalently:
then the interpolation formula will exactly reconstruct the original x(t) from its samples. Otherwise, aliasing may occur; that is, frequencies at or above fs/2 may be erroneously reconstructed. See Aliasing
Aliasing
In signal processing and related disciplines, aliasing refers to an effect that causes different signals to become indistinguishable when sampled...
for further discussion on this point.
Interpolation as convolution sum
The interpolation formula is derived in the Nyquist–Shannon sampling theoremNyquist–Shannon sampling theorem
The Nyquist–Shannon sampling theorem, after Harry Nyquist and Claude Shannon, is a fundamental result in the field of information theory, in particular telecommunications and signal processing. Sampling is the process of converting a signal into a numeric sequence...
article, which points out that it can also be expressed as the convolution
Convolution
In mathematics and, in particular, functional analysis, convolution is a mathematical operation on two functions f and g, producing a third function that is typically viewed as a modified version of one of the original functions. Convolution is similar to cross-correlation...
of an infinite impulse train
Dirac comb
In mathematics, a Dirac comb is a periodic Schwartz distribution constructed from Dirac delta functions...
with a sinc function:
This is equivalent to filtering the impulse train with an ideal (brick-wall) low-pass filter
Low-pass filter
A low-pass filter is an electronic filter that passes low-frequency signals but attenuates signals with frequencies higher than the cutoff frequency. The actual amount of attenuation for each frequency varies from filter to filter. It is sometimes called a high-cut filter, or treble cut filter...
.
Convergence
The interpolation formula always converges absolutely and locally uniform as long asBy the Hölder inequality this is satisfied if the sequence
belongs to any of the spacesLp space
In mathematics, the Lp spaces are function spaces defined using a natural generalization of the p-norm for finite-dimensional vector spaces...
with 1 < p < ∞, that is
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
Stationary process
In the mathematical sciences, a stationary process is a stochastic process whose joint probability distribution does not change when shifted in time or space...
, in which case the sample sequence is not square summable, and is not in any
space.Stationary random processes
If x[n] is an infinite sequence of samples of a sample function of a wide-sense stationary processStationary process
In the mathematical sciences, a stationary process is a stochastic process whose joint probability distribution does not change when shifted in time or space...
, then it is not a member of any
or Lp spaceLp space
In mathematics, the Lp spaces are function spaces defined using a natural generalization of the p-norm for finite-dimensional vector spaces...
, 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
Spectral density
In statistical signal processing and physics, the spectral density, power spectral density , or energy spectral density , is a positive real function of a frequency variable associated with a stationary stochastic process, or a deterministic function of time, which has dimensions of power per hertz...
according to the Wiener–Khinchin theorem
Wiener–Khinchin theorem
The Wiener–Khinchin theorem states that the power spectral density of a wide–sense stationary random process is the Fourier transform of the corresponding autocorrelation function.-History:Norbert Wiener first published the result in...
. 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.
See also
- AliasingAliasingIn signal processing and related disciplines, aliasing refers to an effect that causes different signals to become indistinguishable when sampled...
, Anti-aliasing filterAnti-aliasing filterAn anti-aliasing filter is a filter used before a signal sampler, to restrict the bandwidth of a signal to approximately satisfy the sampling theorem....
, Spatial anti-aliasing - Fourier transformFourier transformIn mathematics, Fourier analysis is a subject area which grew from the study of Fourier series. The subject began with the study of the way general functions may be represented by sums of simpler trigonometric functions...
- Rectangular function
- Sampling (signal processing)Sampling (signal processing)In signal processing, sampling is the reduction of a continuous signal to a discrete signal. A common example is the conversion of a sound wave to a sequence of samples ....
- Signal (electronics)
- Sinc function, Sinc filterSinc filterIn signal processing, a sinc filter is an idealized filter that removes all frequency components above a given bandwidth, leaves the low frequencies alone, and has linear phase...