|
m WP:CHECKWIKI errors fixed + general fixes using AWB (8961)
|
m MOS:FRAC / convert special characters found by Wikipedia:Typo Team/moss (via WP:JWB)
|
||
| (41 intermediate revisions by 27 users not shown) | |||
| Line 1: | Line 1: | ||
{{Short description|Signal (re-)construction algorithm}} |
|||
| ⚫ | |||
{{Use American English|date = March 2019}} |
|||
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. |
|||
| ⚫ | |||
| ⚫ | The '''Whittaker–Shannon interpolation formula''' or '''sinc interpolation'''isa method to construct a [[continuous-time]] [[bandlimited]] function from a sequence of real numbers. The formula dates back to the works of [[E. Borel]] in 1898, and [[E. T. Whittaker]] 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'''. |
||
==Definition== |
==Definition== |
||
[[File:Nyquist sampling.gif|500px|thumb|right|In the figure on the left, the gray curve shows a function f(t) in the time domain that is sampled (the black dots) at steadily increasing sample-rates and reconstructed to produce the gold curve. In the figure on the right, the red curve shows the frequency spectrum of the original function f(t), which does not change. The highest frequency in the spectrum is half the width of the entire spectrum. The steadily-increasing pink shading represents the reconstructed function's frequency spectrum, which gradually fills up more of the original function's frequency spectrum as the sampling-rate increases. When the reconstructed function's frequency spectrum encompasses the original function's entire frequency spectrum, it is twice as wide as the highest frequency, and that is when the reconstructed waveform matches the sampled one.]] |
|||
| ⚫ |
The '''interpolation formula''' |
||
Given a sequence of real numbers, ''x''[''n''], the continuous function |
|||
| ⚫ | :<math>x(t) = \sum_{n=-\infty}^{\infty} x[n] \, {\rm sinc}\left(\frac{t - nT}{T}\right)\,</math> |
||
The [[sampling theorem]] states that, under certain ''limiting conditions'', a function ''x''(''t'') can be recovered exactly from its samples,<ref>http://www.stanford.edu/class/ee104/shannonpaper.pdf</ref> ''x''[''n''] = ''x''(''nT''), by the Whittaker–Shannon interpolation formula''':''' |
|||
(where "sinc" denotes the [[normalized sinc function]]) has a [[Fourier transform]], ''X''(''f''), whose non-zero values are confined to the region |''f''| ≤ 1/(2''T''). When the parameter ''T'' has units of seconds, the '''bandlimit''', 1/(2''T''), has units of cycles/sec ([[hertz]]). When the ''x''[''n''] sequence represents time samples, at interval ''T'', of a continuous function, the quantity ''f''<sub>''s''</sub> = 1/''T'' is known as the [[sample rate]], and ''f''<sub>''s''</sub>/2 is the corresponding [[Nyquist frequency]]. When the sampled function has a bandlimit, ''B'', less than the Nyquist frequency, ''x''(''t'') is a '''perfect reconstruction''' of the original function. (See [[Sampling theorem]].) Otherwise, the frequency components above the Nyquist frequency "fold" into the sub-Nyquist region of ''X''(''f''), resulting in distortion. (See [[Aliasing]].) |
|||
| ⚫ |
:<math>x(t) = \sum_{n=-\infty}^{\infty} x[n] \ |
||
==Equivalent formulation: convolution/lowpass filter== |
|||
where ''T'' = 1/''f''<sub>''s''</sub> is the ''sampling interval'', ''f''<sub>''s''</sub> is the ''[[sampling rate]]'', and sinc(''x'') is the normalized [[sinc function]]. |
|||
| ⚫ | The interpolation formula is derived in the [[Nyquist–Shannon sampling theorem]] article, which points out that it can also be expressed as the [[convolution]] of an [[Dirac comb|infinite impulse train]] with a [[sinc function]]: |
||
| ⚫ | :<math> x(t) = \left( \sum_{n=-\infty}^{\infty} T\cdot \underbrace{x(nT)}_{x[n]}\cdot \delta \left( t - nT \right) \right) \circledast |
||
==Validity condition== |
|||
| ⚫ | \left( \frac{1}{T}{\rm sinc}\left(\frac{t}{T}\right) \right). </math> |
||
[[Image:bandlimited.svg|thumb|right|240px|Spectrum of a bandlimited signal as a function of frequency. The two-sided bandwidth ''R''<sub>''N''</sub> = 2''B'' is known as the Nyquist rate for the signal.]] |
|||
This is equivalent to filtering the impulse train with an ideal (''brick-wall'') [[low-pass filter]] with gain of 1 (or 0 dB) in the passband. If the sample rate is sufficiently high, this means that the baseband image (the original signal before sampling) is passed unchanged and the other images are removed by the brick-wall filter. |
|||
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 |
|||
# the function ''x''(''t'') is bandlimited to bandwidth ''B''; that is, it has a [[Fourier transform]] <math>\scriptstyle \mathcal{F} \{x(t) \} = X(f) = 0 \ </math> for |''f''| > ''B''; and |
|||
# the [[sampling rate]], ''f''<sub>''s''</sub>, exceeds the [[Nyquist rate]], twice the bandwidth: ''f''<sub>''s''</sub> > 2''B''. Equivalently''':''' |
|||
::<math>T < \frac{1}{2B}; </math> |
|||
then the interpolation formula will exactly reconstruct the original ''x''(''t'') from its samples. Otherwise, aliasing may occur; that is, frequencies at or above ''f''<sub>''s''</sub>/2 may be erroneously reconstructed. ''See [[Aliasing]] for further discussion on this point.'' |
|||
==Interpolation as convolution sum== |
|||
| ⚫ |
The interpolation formula is derived in the [[Nyquist–Shannon sampling theorem]] article, which points out that it can also be expressed as the [[convolution]] of an [[Dirac comb|infinite impulse train]] with a sinc function |
||
| ⚫ |
:<math> x(t) = \left( \sum_{n=-\infty}^{\infty} x[n]\cdot \delta \left( t - nT \right) \right) |
||
| ⚫ | |||
This is equivalent to filtering the impulse train with an ideal (''brick-wall'') [[low-pass filter]]. |
|||
==Convergence== |
==Convergence== |
||
The interpolation formula always converges [[absolute convergence|absolutely]] and [[uniform convergence|locally |
The interpolation formula always converges [[absolute convergence|absolutely]] and [[uniform convergence|locally uniformly]] as long as |
||
:<math>\sum_{n\in\Z,\,n\ne 0}\left|\frac{x[n]}n\right|<\infty.</math> |
:<math>\sum_{n\in\Z,\,n\ne 0}\left|\frac{x[n]}n\right|<\infty.</math> |
||
By the [[Hölder inequality]] this is satisfied if the sequence <math> |
By the [[Hölder inequality]] this is satisfied if the sequence <math>(x[n])_{n\in\Z}</math> belongs to any of the <math>\ell^p(\Z,\mathbb C)</math> [[Lp space|spaces]] with 1 ≤ ''p'' < ∞, that is |
||
:<math>\sum_{n\in\Z}\left|x[n]\right|^p<\infty.</math> |
:<math>\sum_{n\in\Z}\left|x[n]\right|^p<\infty.</math> |
||
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 <math> |
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 <math>\ell^p(\Z,\mathbb C)</math> space. |
||
==Stationary random processes== |
==Stationary random processes== |
||
If ''x''[''n''] is an infinite sequence of samples of a sample function of a wide-sense [[stationary process]], then it is not a member of any <math> |
If ''x''[''n''] is an infinite sequence of samples of a sample function of a wide-sense [[stationary process]], then it is not a member of any <math>\ell^p</math> or [[Lp space|L<sup>p</sup> 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. |
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. |
||
==See also== |
==See also== |
||
{{cols}} |
|||
* [[Aliasing]], [[Anti-aliasing filter]], [[Spatial anti-aliasing]] |
* [[Aliasing]], [[Anti-aliasing filter]], [[Spatial anti-aliasing]] |
||
* [[Fourier transform]] |
|||
* [[Rectangular function]] |
* [[Rectangular function]] |
||
* [[Sampling (signal processing)]] |
* [[Sampling (signal processing)]] |
||
* [[Signal (electronics)]] |
* [[Signal (electronics)]] |
||
* [[Sinc function]], [[Sinc filter]] |
* [[Sinc function]], [[Sinc filter]] |
||
* [[Lanczos resampling]] |
|||
{{colend}} |
|||
{{Use dmy dates|date= |
{{Use dmy dates|date=May 2014}} |
||
<!-- |
|||
==References== |
==References== |
||
<references /> |
<references /> |
||
*http://www.stanford.edu/class/ee104/shannonpaper.pdf--> |
|||
{{DEFAULTSORT: |
{{DEFAULTSORT:Whittaker-Shannon interpolation formula}} |
||
[[Category:Digital signal processing]] |
[[Category:Digital signal processing]] |
||
[[Category:Signal processing]] |
[[Category:Signal processing]] |
||
[[Category:Fourier analysis]] |
[[Category:Fourier analysis]] |
||
[[Category:E. T. Whittaker]] |
|||
 |
This article needs additional citations for verification. Please help improve this articlebyadding citations to reliable sources. Unsourced material may be challenged and removed.
Find sources: "Whittaker–Shannon interpolation formula" – news · newspapers · books · scholar · JSTOR (March 2013) (Learn how and when to remove this message) |
The Whittaker–Shannon interpolation formulaorsinc interpolation is a method to construct a continuous-time bandlimited function from a sequence of real numbers. The formula dates back to the works of E. Borel in 1898, and E. T. Whittaker in 1915, and was cited from works of J. M. Whittaker in 1935, and in the formulation of the Nyquist–Shannon sampling theorembyClaude 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.
Given a sequence of real numbers, x[n], the continuous function
![{\displaystyle x(t)=\sum _{n=-\infty }^{\infty }x[n]\,{\rm {sinc}}\left({\frac {t-nT}{T}}\right)\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a6fb0ab1bd8507bc90a23bf0435888d2105c7449)
(where "sinc" denotes the normalized sinc function) has a Fourier transform, X(f), whose non-zero values are confined to the region |f| ≤ 1/(2T). When the parameter T has units of seconds, the bandlimit, 1/(2T), has units of cycles/sec (hertz). When the x[n] sequence represents time samples, at interval T, of a continuous function, the quantity fs = 1/T is known as the sample rate, and fs/2 is the corresponding Nyquist frequency. When the sampled function has a bandlimit, B, less than the Nyquist frequency, x(t) is a perfect reconstruction of the original function. (See Sampling theorem.) Otherwise, the frequency components above the Nyquist frequency "fold" into the sub-Nyquist region of X(f), resulting in distortion. (See Aliasing.)
The interpolation formula is derived in the Nyquist–Shannon sampling theorem article, which points out that it can also be expressed as the convolution of an infinite impulse train with a sinc function:
![{\displaystyle x(t)=\left(\sum _{n=-\infty }^{\infty }T\cdot \underbrace {x(nT)} _{x[n]}\cdot \delta \left(t-nT\right)\right)\circledast \left({\frac {1}{T}}{\rm {sinc}}\left({\frac {t}{T}}\right)\right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/16723c2569b9a795930a044fac10f62366e45d08)
This is equivalent to filtering the impulse train with an ideal (brick-wall) low-pass filter with gain of 1 (or 0 dB) in the passband. If the sample rate is sufficiently high, this means that the baseband image (the original signal before sampling) is passed unchanged and the other images are removed by the brick-wall filter.
The interpolation formula always converges absolutely and locally uniformly as long as
![{\displaystyle \sum _{n\in \mathbb {Z} ,\,n\neq 0}\left|{\frac {x[n]}{n}}\right|<\infty .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f0e4d3da54d17a300592674eca9d0a0073488fdc)
By the Hölder inequality this is satisfied if the sequence ![{\displaystyle (x[n])_{n\in \mathbb {Z} }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/441b11182b1244469c5d3f1e72de33f7d3a37892)
![{\displaystyle \sum _{n\in \mathbb {Z} }\left|x[n]\right|^{p}<\infty .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8b3fbde5f7348439d9c959a2e4366295fb65e89b)
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
Ifx[n] is an infinite sequence of samples of a sample function of a wide-sense stationary process, then it is not a member of any 
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.
