采样定理

本條目仍然有文字尚未被翻譯成中文，條目是根據其他語言的維基百科內容進行翻譯。 歡迎您積極參與翻譯與修訂。

采样定理(在国外又被称为Nyquist–Shannon-Kotelnikov采样定理或Whittaker–Shannon-Kotelnikov采样定理)是信息论，特别是电信学中的一个重要基本结论.E. T. Whittaker(1915年发表的统计理论),Claude Shannon 与Harry Nyquist都对它作出了重要贡献。另外,V. A. Kotelnikov 也对这个定理做了重要贡献。

采样是将一个信号（即连续时间或空间上的函数）转换成一个数值序列（即离散时间或空间上的函数）。采样定理指出，只有在信号是带限的，并且采样频率高于信号带宽的两倍在何等条件下，可以无损的进行采样，进而能够以此定理将原信号以任意精度重建出来。

带限信号变换的快慢受到它的最高频率分量的限制，也就是说它的离散时刻采样表现信号细节的能力是有限的。采样定理是指，如果信号带宽不到采样频率的一半（即奈奎斯特频率），那么此时这些离散的采样点能够完全表示原信号。高于或处于奈奎斯特频率的频率分量会导致混叠现象。大多数应用都要求避免混叠，混叠问题的严重程度与这些混叠频率分量的相对强度有关。

To formalize these concepts, let represent a real-valued continuous-time signal and let represent its unitary Fourier transform (to the domain of ordinary frequency, Hz). I.e.:

Spectrum of a bandlimited signal as a function of frequency

The figure depicts a bandlimited whose highest frequency is .   I.e.:

Then the condition for alias-free sampling at rate (in samples per second) is:

  (Nyquist rate)

or equivalently:

  (Nyquist frequency)

The time interval between successive samples is a constant, referred to as sampling interval. It is given, in seconds, by:

And the samples of are denoted by:

(integers)

[编辑] 采样简介

从信号处理的角度来看，此采样定理描述了两个过程：其一是采样，这一过程将连续时间信号转换为离散时间信号；其二是信号的重建，这一过程离散信号还原成连续信号。

Let us assume that the continuous signal varies over one way or another. Let us call the elements of this sequence samples. Notice that each sample is associated to the specific point in time where it was measured. Notice also that 1/T can be interpreted as a sampling frequency, which is often represented by the symbol f_s and measured in samples per second, or equivalently, hertz.

Let us also assume that the reconstruction process is done by somehow interpolating a continuous/analog signal from the samples.

A very practical question would be to ask: under what circumstances is it possible to reconstruct the original signal completely and exactly (perfect reconstruction)?

The answer is provided by the sampling theorem. In fact, it states two things:

The normalized sinc function: sin(πx) / (πx)... showing the central location at x= 0, and zero-crossings at the other integer values of x.

• Each sample should be multiplied by a particular function, called a sinc function. The frequency of the zero-crossings of the sinc function is time-scaled to equal , and the location of the sinc-function's central point is shifted to the time of that sample. All of these shifted and scaled functions are then added together to recover the original signal. Recall that a sinc-function is continuous, which means that the result of this operation is indeed a continuous signal. This procedure derives from the Nyquist-Shannon interpolation formula.

• In order to obtain the original signal after this reconstruction process, we must also observe a critical condition on the sampling frequency. It must be greater than twice the highest frequency component of the original signal, also measured in hertz.

Sometimes, the sampling theorem refers only to the last statement, but you need also the first one to put things into the right context.

A few practical conclusions can be drawn from the theorem:

• If it is known that the signal which we sample has a certain highest frequency f_H, the theorem gives us a lower bound on the sampling frequency to assure perfect reconstruction. This minimum value of the sampling frequency is called the critical frequency or Nyquist rate, denoted f_N.

• If instead the sampling frequency is known, the theorem gives us an upper bound for frequency components of the signal to assure perfect reconstruction.

• Both of these cases imply that the signal to be sampled should be bandlimited, i.e., any component of this signal which has a frequency above a certain bound should be zero, or at least sufficiently close to zero to allow us to neglect its influence on the resulting reconstruction. In the first case the condition of bandlimitation of the sampled signal can be accomplished by assuming a model of the signal which can be analysed in terms of the frequency components it contains, e.g., sounds which are made by a speaking human normally contains very small frequency components at or above 5 kHz and it is then sufficient to sample such an audio signal with a sampling frequency of at least 10 kHz. For the second case, we have to assure that the sampled signal is bandlimited such that frequency components at or above half of the sampling frequency can be neglected. This is usually accomplished by means of a suitable low-pass filter.

• In practice, neither of the two statements of the sampling theorem described above can be completely satisfied. The reconstruction process which involves the sinc-functions can be described as ideal. It cannot be realized in practice since it implies that each sample contributes to the reconstructed signal at almost all time points. Instead some type of approximations of the sinc-functions which are truncated to limited intervals have to be used. The error which corresponds to the sinc-function approximation is referred to as interpolation error. Furthermore, in practice the sampled signal can never be exactly bandlimited. This means that even if an ideal reconstruction could be made, the reconstructed signal would not be exactly the sampled signal. The error which corresponds to the failure of bandlimitation is referred to as aliasing.

• The sampling theorem implies that someone who is going to design a system which deals with sampling and reconstruction processes needs a thorough understanding of the signal to be sampled, in particular its frequency content, the sampling frequency, how the signal is reconstructed in terms of interpolation, and the requirement for the total reconstruction error, including aliasing and interpolation error. In simple terms, all these properties and parameters have to be carefully tuned in order to obtain a useful system.

[编辑] Aliasing

If the sampling condition is not satisfied, then frequencies will overlap (see the proof below). This overlap is called aliasing.

To prevent aliasing, two things can readily be done

1. Increase the sampling rate
2. Introduce an anti-aliasing filter or make anti-aliasing filter more stringent

The anti-aliasing filter is to restrict the bandwidth of the signal to satisfy the sampling condition. This holds in theory, but is not satisfiable in reality. It is not satisfiable in reality because a signal will have some energy outside of the bandwidth. However, the energy can be small enough that the aliasing effects are negligible.

[编辑] Application to multivariable signals and images

Subsampled image showing a Moiré pattern

See for full size image

The sampling theorem is usually formulated for functions of a single variable. Consequently, the theorem is directly applicable to time-dependent signals and is normally formulated in that context. However, the sampling theorem can be extended in a straightforward way to functions of arbitrarily many variables. Grayscale images, for example, are often represented as two-dimensional arrays (or matrices) of real numbers representing the relative intensity of each pixel located at the intersection of a single row and a single column. As a result, grayscale images require two independent variables, or indices, to specify each pixel uniquely — one for the row, and one for the column.

Color images typically consist of a composite of three separate grayscale images, one to represent each of the three primary colors — red, green, and blue, or RGB for short. So color images actually require three independent indices, the first two specifiy the pixel location, and the third specifies one of the three colors.

Similar to one-dimensional discrete-time signals, images can also suffer from aliasing if the sampling resolution, or pixel density, is inadequate. For example, a digital photograph of a striped shirt with high frequencies (in other words, the distance between the stripes is small), can cause aliasing between the shirt and the camera's sensor array. The aliasing appears as a Moiré pattern. The "solution" to higher sampling in the spatial domain for this case would be to move closer to the shirt or use a higher resolution sensor (for example, a CCD).

Another example is shown to the right in the brick patterns. The top image shows the effects when the sampling theorem is not followed. When software rescales an image (the same process that creates the thumbnail shown in the bottom image) it, in effect, runs the image through a low-pass filter first and then downsamples the image to result in a smaller image that does not exhibit the Moiré pattern. The top image is what happens when the image is downsampled without low-pass filtering and aliasing results.

The top image was created by zooming out in GIMP and then taking a screenshot of it. The likely reason that this causes a banding problem is that the zooming feature simply downsamples without low-pass filtering (probably for performance reasons) since the zoomed image is for on-screen display instead of printing or saving.

The application of the sampling theorem on images should not be made without care. For example, the sampling process in any standard image sensor (CCD or CMOS camera) is relatively far from the ideal sampling which would measure the image intensity at a single point. Instead these devices have a relatively large sensor area at each sample point in order to obtain sufficient amount of light. Also, it is not obvious that the analog image intensity function which is sampled by the sensor device is bandlimited. It should be noted, however, that the non-ideal sampling in itself implies some type of low-pass filtering, although far from one that effectively removes high frequency components. Furthermore, since the intensity function in practice is zero outside the actual sensor chip, it cannot be bandlimited. Despite that images have these problems in relation to the sampling theorem, it can be used to describe the basic aspects of down and up sampling of images, but only sufficiently far from the image boundaries.

[编辑] Downsampling

When a signal is downsampled, the theorem must still be satisfied in order to avoid aliasing. To meet the requirements of the theorem, the signal must pass through a low-pass filter of appropriate cutoff frequency prior to the downsampling operation. The low-pass filter, which prevents aliasing, is called an anti-aliasing filter.

[编辑] Critical frequency

The critical frequency is defined as twice the bandwidth of the continuous-time signal. It should be noted that the sampling frequency must be strictly greater than the critical frequency of the signal. This is equivalent to requiring that the Nyquist frequency be strictly greater than the bandwidth or the signal. If the signal contains a frequency component at precisely the Nyquist frequency then the corresponding component of the sample values cannot have sufficient information to reconstruct the Nyquist component in the continuous-time signal because of phase ambiguity. In such a case, there would be an infinite number of possible and different sinusoids (of varying amplitude and phase) of the Nyquist frequency component that are represented by the discrete samples. This is because

all have samples of alternating -1 and +1 for any θ and there is no way to determine both the amplitude and the phase of the continuous-time sinusoid that x[n] was sampled from. This is the reason for the strict inequality of the sampling condition; why the sampling rate must strictly exceed the critical frequency.

[编辑] Mathematical basis for the theorem

An ideally sampled signal by use of the Dirac comb

The Nyquist-Shannon sampling and reconstruction theorem asserts that, given a bandlimited continuous-time signal, x(t), that is uniformly sampled at a sufficient rate, even if all of the information in the signal between samples is discarded, there remains sufficient information in the samples so that the original continuous-time signal can be mathematically reconstructed from only those samples. To prove this, a mathematical representation of the uniform sampled signal that effectively discards the information between samples must be constructed.

x(t) is the signal before sampling.

x_s(t) is the resulting sampled signal

δ_T(t) is the sampling operator called the Dirac comb and, being periodic with period T, can be expressed as a Fourier series.

f_s = 1/T is the sampling frequency and is the fundamental frequency of the periodic function δ_T(t).

δ(t-kT) is a dirac impulse delayed to time kT.

It is clear that δ_T(t) takes a value of zero except for values of t that are at the sampling instances, kT, for integer k. Equally clear that x_s(t) takes on zero values for all t except for the sampling instances kT. Multiplying x(t) by δ_T(t) effectively discards all of the information between sampling instances and retains information only at the sampling instances kT. x_s(t) can be represented in terms of the samples:

Where x[k] defined to be x(kT) are the samples. An alternative (and equally important representation) of the sampled signal is:

Using the frequency shifting property of the continuous Fourier transform,

where X(f) is the Fourier tranform of x(t). This says that the spectrum of the signal being sampled is shifted and repeated forever at integral multiples of the sampling frequency, f_s. Now constrain x(t) or X(f) to be bandlimited to f_H (i.e. X(f) = 0 for all |f| > f_H) and consider what condition would allow no overlap of the tails of adjacent images X(f):

"right tail of n^th image of X(f)" < "left tail of (n+1)^th image"

With that condition satisfied, there is no overlap of images and X(f) (and thus x(t)) can be reconstructed from X_s(f) (or x_s(t)) by low pass filtering out all of the images of X(f) in X_s(f) except the original image at the baseband (and canceling the scaling factor, 1/T, of the remaining baseband image). To do that, f_s > 2f_H (to prevent overlap) and the frequency response of the reconstruction filter H(f) must be:

The passband gain T is necessary to cancel the scaling factor 1/T of the remaining baseband image in X_s(f). With H(f) so defined, it is clear that

and the spectrum of the original signal that was sampled is recovered from the spectrum of the sampled signal. This means, in the time domain, that the original signal that was sampled is recovered from the sampled signal. This is the sampling half of the Nyquist-Shannon sampling and reconstruction theorem. It says that the sampling frequency, f_s, must be strictly greater than twice the bandwidth, f_H, of the continuous-time signal, x(t), for no information to be lost (or "aliased"). The reconstruction half follows.

The impulse response of the reconstruction filter is the inverse Fourier transform of H(f).

The sinc function is the impulse response of the reconstruction filter that has for its input, the sampled signal x_s(t):

x_s(t) is no more than a collection of dirac impulses, δ(t-kT), each delayed to the time of their sampling instance, kT and weighted by the value of the continuous-time signal that was sampled at that instance, x[k]. Since the reconstruction filter is a linear, time-invariant system, each impulse at time kT generates its own impulse response delayed to the same time and the output of the reconstruction filter is the sum of outputs driven by each weighted impulse separately. For each input impulse, the component of the output is the impulse response delayed by the same delay of that input impulse,h(t-kT), and weighted by the same scaling factor attached to that input impulse, x[k]. That is the output of the reconstruction filter is

This shows explicitly how the samples of the original continuous-time function, x[k] = x(kT), are combined to reconstruct that function, x(t), at times that are between the samples when such data was discarded in the sampling process and is known as the Nyquist–Shannon interpolation formula. This completes the reconstruction half of the Nyquist-Shannon sampling and reconstruction theorem.

[编辑] Undersampling

When sampling a non-baseband signal, the theorem must be restated as follows. Let 0 < f_L < f_H be the lower and higher boundaries of a frequency band and W = f_H − f_L be the bandwidth. Then there is a non-negative integer N with

In addition, we define the remainder r as

}-.

Any real-valued signal x(t) with a spectrum limited to this frequency band, that is with

for outside the interval ,

is uniquely determined by its samples obtained at a sampling rate of f_s, if this sampling rate satisfies one of the following conditions:

• for one value of n = { 0, 1, ..., N-1 }

- OR -

• .

If N > 0, then the first conditions result in a sampling rate less than the Nyquist frequency 2f_H obtained from the upper bound of the spectrum. If the so obtained sampling rates are still too high, the intuitive sampling-by-taking-values has to be replaced by sampling-by-taking-scalar-products, as is (implicitly) the case in Frequency-division multiplexing.

Example: Consider FM radio to illustrate the idea of undersampling.

In the US, FM radio operates on the frequency band from f_L = 88 MHz to f_H = 108 MHz. The bandwidth is given by

The sampling conditions are satisfied for

Therefore

N=4, r=8 MHz and n = 0,1,2,3.

The value n = 0 gives the lowest sampling frequencies interval and this is a scenario of undersampling.

Note that when undersampling a real-world signal, the sampling circuit must be fast enough to capture the highest signal frequency of interest. Theoretically, each sample should be taken during an infinitesimally short interval, but this is not practically feasible. Instead, the sampling of the signal should be made in a short enough interval that it can represent the instantaneous value of the signal with the highest frequency. This means that in the FM radio example above, the sampling circuit must be able to capture a signal with a frequency of 108 MHz, not 43.2 MHz. Thus, the sampling frequency may be only a little bit greater than 43.2 MHz, but the input bandwidth of the system must be at least 108 MHz.

If the theorem is misunderstood to mean twice the highest frequency, then the required sampling rate would be assumed to be greater than the Nyquist-frequency 216 MHz.

While this does satisfy the last condition on the sampling rate, it is grossly oversampled.

Note that if the FM radio band is sampled, e.g., at , then a band-pass filter is required for the anti-aliasing filter.

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 a data rate of 360 Hz — i.e. at a sampling rate of 20 Hz with 18 real values in each sample — not 400 Hz, to fully capture these signals.

As we have seen, the normal condition for reversible sampling is that outside the interval:

And the reconstructive interpolation function is .

To accommodate undersampling, the generalized condition is that outside the union

for some .

which includes the normal condition as case N=0.

And the corresponding interpolation function is:

.

[编辑] Historical background

The theorem was first formulated by Harry Nyquist in 1928 ("Certain topics in telegraph transmission theory"), but was only formally proven by Claude E. Shannon in 1949 ("Communication in the presence of noise"). Kotelnikov published in 1933, Whittaker in 1915 (E.T.) and 1935 (J.M.), and Gabor in 1946.

[编辑] See also

• Aliasing
• Anti-aliasing filter: low-pass filter, band-pass filter
• Dirac comb
• Nyquist–Shannon interpolation formula
• Sampling (information theory)
• Signal (information theory)
• Reconstruction from Zero Crossings

[编辑] References

• E. T. Whittaker, "On the Functions Which are Represented by the Expansions of the Interpolation Theory," Proc. Royal Soc. Edinburgh, Sec. A, vol.35, pp.181-194, 1915
• H. Nyquist, "Certain topics in telegraph transmission theory," Trans. AIEE, vol. 47, pp. 617-644, Apr. 1928.
• V. A. Kotelnikov, "On the carrying capacity of the ether and wire in telecommunications," Material for the First All-Union Conference on Questions of Communication, Izd. Red. Upr. Svyazi RKKA, Moscow, 1933 (Russian).
• C. E. Shannon, "Communication in the presence of noise", Proc. Institute of Radio Engineers, vol. 37, no.1, pp. 10-21, Jan. 1949.

[编辑] External links

• Learning by Simulations Interactive simulation of the effects of inadequate sampling
• Undersampling and an application of it
• Sampling Theory For Digital Audio