The Nyquist–Shannon sampling theorem is a theorem in the field of
signal processing
Signal processing is an electrical engineering subfield that focuses on analyzing, modifying and synthesizing '' signals'', such as sound, images, and scientific measurements. Signal processing techniques are used to optimize transmissions, ...
which serves as a fundamental bridge between
continuous-time signal
In mathematical dynamics, discrete time and continuous time are two alternative frameworks within which variables that evolve over time are modeled.
Discrete time
Discrete time views values of variables as occurring at distinct, separate "po ...
s and
discrete-time signal
In mathematical dynamics, discrete time and continuous time are two alternative frameworks within which variables that evolve over time are modeled.
Discrete time
Discrete time views values of variables as occurring at distinct, separate "po ...
s. It establishes a sufficient condition for a
sample rate that permits a discrete sequence of ''samples'' to capture all the information from a continuous-time signal of finite
bandwidth.
Strictly speaking, the theorem only applies to a class of
mathematical functions having a
Fourier transform
A Fourier transform (FT) is a mathematical transform that decomposes functions into frequency components, which are represented by the output of the transform as a function of frequency. Most commonly functions of time or space are transformed ...
that is zero outside of a finite region of frequencies. Intuitively we expect that when one reduces a continuous function to a discrete sequence and
interpolates
In the mathematical field of numerical analysis, interpolation is a type of estimation, a method of constructing (finding) new data points based on the range of a discrete set of known data points.
In engineering and science, one often has ...
back to a continuous function, the fidelity of the result depends on the density (or
sample rate) of the original samples. The sampling theorem introduces the concept of a sample rate that is sufficient for perfect fidelity for the class of functions that are
band-limited
Bandlimiting is the limiting of a signal's frequency domain representation or spectral density to zero above a certain finite frequency.
A band-limited signal is one whose Fourier transform or spectral density has bounded support.
A bandli ...
to a given bandwidth, such that no actual information is lost in the sampling process. It expresses the sufficient sample rate in terms of the bandwidth for the class of functions. The theorem also leads to a formula for perfectly reconstructing the original continuous-time function from the samples.
Perfect reconstruction may still be possible when the sample-rate criterion is not satisfied, provided other constraints on the signal are known (see below and
compressed sensing). In some cases (when the sample-rate criterion is not satisfied), utilizing additional constraints allows for approximate reconstructions. The fidelity of these reconstructions can be verified and quantified utilizing
Bochner's theorem.
The name ''Nyquist–Shannon sampling theorem'' honours
Harry Nyquist
Harry Nyquist (, ; February 7, 1889 – April 4, 1976) was a Swedish-American physicist and electronic engineer who made important contributions to communication theory.
Personal life
Nyquist was born in the village Nilsby of the parish Stora ...
and
Claude Shannon
Claude Elwood Shannon (April 30, 1916 – February 24, 2001) was an American mathematician, electrical engineer, and cryptographer known as a "father of information theory".
As a 21-year-old master's degree student at the Massachusetts I ...
, but the theorem was also previously discovered by
E. T. Whittaker (published in 1915) and Shannon cited Whittaker's paper in his work. The theorem is thus also known by the names ''Whittaker–Shannon sampling theorem'', ''Whittaker–Shannon'', and ''Whittaker–Nyquist–Shannon'', and may also be referred to as the ''cardinal theorem of interpolation''.
Introduction
Sampling is a process of converting a signal (for example, a function of continuous time or space) into a sequence of values (a function of discrete time or space).
Shannon's version of the theorem states:
[Reprint as classic paper in: ''Proc. IEEE'', Vol. 86, No. 2, (Feb 1998)]
A sufficient sample-rate is therefore anything larger than
samples per second. Equivalently, for a given sample rate
, perfect reconstruction is guaranteed possible for a bandlimit
.
When the bandlimit is too high (or there is no bandlimit), the reconstruction exhibits imperfections known as
aliasing
In signal processing and related disciplines, aliasing is an effect that causes different signals to become indistinguishable (or ''aliases'' of one another) when sampled. It also often refers to the distortion or artifact that results when ...
. Modern statements of the theorem are sometimes careful to explicitly state that
must contain no
sinusoidal
A sine wave, sinusoidal wave, or just sinusoid is a mathematical curve defined in terms of the '' sine'' trigonometric function, of which it is the graph. It is a type of continuous wave and also a smooth periodic function. It occurs often i ...
component at exactly frequency
or that
must be strictly less than ½ the sample rate. The threshold
is called the
Nyquist rate
In signal processing, the Nyquist rate, named after Harry Nyquist, is a value (in units of samples per second or hertz, Hz) equal to twice the highest frequency ( bandwidth) of a given function or signal. When the function is digitized at a hi ...
and is an attribute of the continuous-time input
to be sampled. The sample rate must exceed the Nyquist rate for the samples to suffice to represent
The threshold
is called the
Nyquist frequency
In signal processing, the Nyquist frequency (or folding frequency), named after Harry Nyquist, is a characteristic of a sampler, which converts a continuous function or signal into a discrete sequence. In units of cycles per second ( Hz), it ...
and is an attribute of the
sampling equipment. All meaningful frequency components of the properly sampled
exist below the Nyquist frequency. The condition described by these inequalities is called the ''Nyquist criterion'', or sometimes the ''Raabe condition''. The theorem is also applicable to functions of other domains, such as space, in the case of a digitized image. The only change, in the case of other domains, is the units of measure attributed to
and
The symbol
is customarily used to represent the interval between samples and is called the ''sample period'' or ''sampling interval''. The samples of function
are commonly denoted by
(alternatively
in older signal processing literature), for all integer values of
Another convenient definition is
which preserves the energy of the signal as
varies.
A mathematically ideal way to interpolate the sequence involves the use of
sinc function
In mathematics, physics and engineering, the sinc function, denoted by , has two forms, normalized and unnormalized..
In mathematics, the historical unnormalized sinc function is defined for by
\operatornamex = \frac.
Alternatively, the u ...
s. Each sample in the sequence is replaced by a sinc function, centered on the time axis at the original location of the sample
with the amplitude of the sinc function scaled to the sample value,
Subsequently, the sinc functions are summed into a continuous function. A mathematically equivalent method uses the
Dira comb and proceeds by
convolving one sinc function with a series of
Dirac delta pulses, weighted by the sample values. Neither method is numerically practical. Instead, some type of approximation of the sinc functions, finite in length, is used. The imperfections attributable to the approximation are known as ''interpolation error''.
Practical
digital-to-analog converter
In electronics, a digital-to-analog converter (DAC, D/A, D2A, or D-to-A) is a system that converts a digital signal into an analog signal. An analog-to-digital converter (ADC) performs the reverse function.
There are several DAC archit ...
s produce neither scaled and delayed
sinc function
In mathematics, physics and engineering, the sinc function, denoted by , has two forms, normalized and unnormalized..
In mathematics, the historical unnormalized sinc function is defined for by
\operatornamex = \frac.
Alternatively, the u ...
s, nor ideal
Dirac pulse
In mathematics, the Dirac delta distribution ( distribution), also known as the unit impulse, is a generalized function or distribution over the real numbers, whose value is zero everywhere except at zero, and whose integral over the entire ...
s. Instead they produce a
piecewise-constant
In mathematics, a function on the real numbers is called a step function if it can be written as a finite linear combination of indicator functions of intervals. Informally speaking, a step function is a piecewise constant function having only ...
sequence of scaled and delayed
rectangular pulses (the
zero-order hold
The zero-order hold (ZOH) is a mathematical model of the practical signal reconstruction done by a conventional digital-to-analog converter (DAC). That is, it describes the effect of converting a discrete-time signal to a continuous-time sign ...
), usually followed by a
lowpass filter (called an "anti-imaging filter") to remove spurious high-frequency replicas (images) of the original baseband signal.
Aliasing
When
is a function with a
Fourier transform
A Fourier transform (FT) is a mathematical transform that decomposes functions into frequency components, which are represented by the output of the transform as a function of frequency. Most commonly functions of time or space are transformed ...
:
:
the
Poisson summation formula indicates that the samples,
, of
are sufficient to create a
periodic summation of
. The result is:
:
()
which is a periodic function and its equivalent representation as a
Fourier series
A Fourier series () is a summation of harmonically related sinusoidal functions, also known as components or harmonics. The result of the summation is a periodic function whose functional form is determined by the choices of cycle length (or '' ...
, whose coefficients are
This function is also known as the
discrete-time Fourier transform
In mathematics, the discrete-time Fourier transform (DTFT) is a form of Fourier analysis that is applicable to a sequence of values.
The DTFT is often used to analyze samples of a continuous function. The term ''discrete-time'' refers to the ...
(DTFT) of the sample sequence.
As depicted, copies of
are shifted by multiples of the sampling rate
and combined by addition. For a band-limited function
and sufficiently large
it is possible for the copies to remain distinct from each other. But if the Nyquist criterion is not satisfied, adjacent copies overlap, and it is not possible in general to discern an unambiguous
Any frequency component above
is indistinguishable from a lower-frequency component, called an ''alias'', associated with one of the copies. In such cases, the customary interpolation techniques produce the alias, rather than the original component. When the sample-rate is pre-determined by other considerations (such as an industry standard),
is usually filtered to reduce its high frequencies to acceptable levels before it is sampled. The type of filter required is a
lowpass filter, and in this application it is called an
anti-aliasing filter
An anti-aliasing filter (AAF) is a filter used before a signal sampler to restrict the bandwidth of a signal to satisfy the Nyquist–Shannon sampling theorem over the band of interest. Since the theorem states that unambiguous reconstruct ...
.
Derivation as a special case of Poisson summation
When there is no overlap of the copies (also known as "images") of
, the
term of can be recovered by the product:
:
where:
:
The sampling theorem is proved since
uniquely determines
All that remains is to derive the formula for reconstruction.
need not be precisely defined in the region