The Nyquist-Shannon sampling theorem is the fundamental theorem in
the field of information theory, in particular telecommunications.
It is also known as Whittaker-Nyquist-Kotelnikov-Shannon sampling
theorem.
The theorem states that, when converting from an analog signal to
digital (or otherwise sampling a signal at discrete intervals), the
sampling frequency must be greater than twice the highest frequency
of the input signal in order to be able to reconstruct the original
perfectly from the sampled version.
If the sampling frequency is less than this limit, then frequencies
in the original signal that are above half the sampling rate will
be "aliased" and will appear in the resulting signal as
lower frequencies, therefore audible. If the sampling frequency is
exactly twice the highest frequency of the input signal, then phase
mismatches between the sampler and the signal will distort the signal.
For example, sampling cos(pi * t) at t=0,1,2... will give you the
discrete signal cos(pi*n), as desired. However, sampling the same
signal at t=0.5,1.5,2.5... will give you a constant zero signal -
these samplers, which differ only in phase, not frequency, give dramatically
different results because they sample at exactly the critical frequency.
Therefore, an analog low-pass filter is typically applied before
sampling to ensure that no components with frequencies greater than
half the sample frequency remain. This is called an "anti-aliasing
filter". The quality of analog to digital converters depends
critically upon that filter, which is also one of the most expensive
components to build, since a poor filter causes phase distortion and
other difficulties.The theorem also applies when reducing the sampling
frequency of an existing digital signal.
The theorem was first formulated by Harry Nyquist in 1928 ("Certain
topics in telegraph transmission theory"), but was only formally
proved by Claude E. Shannon in 1949 ("Communication in the presence
of noise"). Mathematically, the theorem is formulated as a statement
about the Fourier transformation.
If a function s(x) has a Fourier transform F[s(x)] = S(f) = 0 for
|f| Ž W, then it is completely determined by giving the value of the
function at a series of points spaced 1/(2W) apart. The values sn
= s(n/(2W)) are called the samples of s(x).
The minimum sample frequency that allows reconstruction of the original
signal, that is 2W samples per unit distance, is known as the Nyquist
frequency, (or Nyquist rate). The time inbetween samples is called
the Nyquist interval.
If S(f) = 0 for |f| > W, then s(x) can be recovered from its samples
by the Nyquist-Shannon interpolation formula.
A well-known consequence of the sampling theorem is that a signal
cannot be both bandlimited and time-limited. To see why, assume that
such a signal exists, and sample it faster than the Nyquist frequency.
These finitely many time-domain coefficients should define the entire
signal. Equivalently, the entire spectrum of the bandlimited signal
should be expressible in terms of the finitely many time-domain coefficients
obtained from sampling the signal. Mathematically this is equivalent
to requiring that a (trigonometric) polynomial can have infinitely
many zeros since the bandlimited signal must be zero on an interval
beyond a critical frequency which has infinitely many points. However,
it is well-known that polynomials do not have more zeros than their
orders due to the fundamental theorem of algebra. This contradiction
shows that our original assumption that a time-limited and bandlimited
signal exists is incorrect.
Undersampling
It has to be noted that even if the concept of "twice the highest
frequency" is the more commonly used idea, it is not absolute.
In fact the theorem stands for "twice the bandwidth", which
is totally different. Bandwidth is related with the range between
the first frequency and the last frequency that represent the signal.
Bandwidth and highest frequency are identical only in baseband signals,
that is, those that go very nearly down to DC. This concept led to
what is called undersampling, that is very used in software-defined
radio.
Imagine that you want to sample all the FM commercial radio stations
that broadcast in a given area. They broadcast in channels that span
from 88 MHz to 108 MHz, giving a signal with bandwidth of 20 MHz.
In the baseband interpretation of the theorem, this would require
a sampling frequency more than 216 MHz. In fact, doing undersampling
one is only required to sample at more than 40 MHz, as long as the
antenna signal is passed by a bandpass filter to keep the signal in
the 88-108 MHz range. Sampling at 44 MHz, the frequency 100 MHz will
be reflected as a 12 MHz digital frequency.
In certain problems, the frequencies of interest are not an interval
of frequencies, but perhaps some more interesting set F of frequencies.
Again, the sampling frequency must be proportional to the size of
F. For instance, certain domain decomposition methods fail to converge
for the 0th frequency (the constant mode) and some medium frequencies.
Then the set of interesting frequencies would be something like 10
Hz to 100 Hz, and 110 Hz to 200 Hz. In this case, one would need to
sample at 360 Hz, not 400 Hz, to fully capture these signals.
References
* H. Nyquist, "Certain topics in telegraph transmission theory,"
Trans. AIEE, vol. 47, pp. 617-644, Apr. 1928.
* C. E. Shannon, "Communication in the presence of noise,"
Proc. Institute of Radio Engineers, vol. 37, no.1, pp. 10-21, Jan.
1949.
de:Nyquist-Shannon-Abtasttheorem nl:Bemonsteringstheorema van Nyquist-Shannon
ja:?????
[From Biography.ms]
