Nyquist–Shannon sampling theorem

related topics
{math, number, function}
{system, computer, user}
{rate, high, increase}
{math, energy, light}
{work, book, publish}
{black, white, people}
{@card@, make, design}
{language, word, form}

The Nyquist–Shannon sampling theorem, which has been named 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 (for example, a function of continuous time or space) into a numeric sequence (a function of discrete time or space). Shannon's version of the theorem states:[1]

If a function x(t) contains no frequencies higher than B hertz, it is completely determined by giving its ordinates at a series of points spaced 1/(2B) seconds apart.

The theorem is commonly called the Nyquist sampling theorem; since it was also discovered independently by E. T. Whittaker, by Vladimir Kotelnikov, and by others, it is also known as Nyquist–Shannon–Kotelnikov, Whittaker–Shannon–Kotelnikov, Whittaker–Nyquist–Kotelnikov–Shannon, WKS, etc., sampling theorem, as well as the Cardinal Theorem of Interpolation Theory. It is often referred to simply as the sampling theorem.

In essence, the theorem shows that a bandlimited analog signal that has been sampled can be perfectly reconstructed from an infinite sequence of samples if the sampling rate exceeds 2B samples per second, where B is the highest frequency in the original signal. If a signal contains a component at exactly B hertz, then samples spaced at exactly 1/(2B) seconds do not completely determine the signal, Shannon's statement notwithstanding. This sufficient condition can be weakened, as discussed at Sampling of non-baseband signals below.

More recent statements of the theorem are sometimes careful to exclude the equality condition; that is, the condition is if x(t) contains no frequencies higher than or equal to B; this condition is equivalent to Shannon's except when the function includes a steady sinusoidal component at exactly frequency B.

The theorem assumes an idealization of any real-world situation, as it only applies to signals that are sampled for infinite time; any time-limited x(t) cannot be perfectly bandlimited. Perfect reconstruction is mathematically possible for the idealized model but only an approximation for real-world signals and sampling techniques, albeit in practice often a very good one.

The theorem also leads to a formula for reconstruction of the original signal. The constructive proof of the theorem leads to an understanding of the aliasing that can occur when a sampling system does not satisfy the conditions of the theorem.

The sampling theorem provides a sufficient condition, but not a necessary one, for perfect reconstruction. The field of compressed sensing provides a stricter sampling condition when the underlying signal is known to be sparse. Compressed sensing specifically yields a sub-Nyquist sampling criterion.

Contents

Full article ▸

related documents
Python (programming language)
One-time pad
Subroutine
Artificial neural network
Algorithmic efficiency
Java Platform, Standard Edition
Gray code
Java (programming language)
Garbage collection (computer science)
Obfuscated code
Reed–Solomon error correction
Web crawler
UTF-8
XML
Fuzzy control system
Verilog
RSA
Ruby (programming language)
Fortran
Lua (programming language)
Sequence alignment
Wavelet
Denotational semantics
Complete lattice
Kernel (algebra)
Stone–Čech compactification
Newton's method
Integration by parts
Direct sum of modules
Riemann zeta function