The Sampling Theorem

One important requirement for signal transmission and storage is the need for discretization of the signal, both in time-index sets and in signal-range sets. The former is called sampling; the latter is called quantization. In the following, we discuss sampling.

The Sampling Theorem

Samplers perform the discretization in the time-index. We discuss a very important theorem in the following.

Sampling of a Continuous-Time (CT) Signal

This is a remarkable result which paves the way to communications, signal processing, and digital control technologies, which are ubiquitous in our daily lives. For example, human voice range is typically about 20 Hz to 20 kHz (female voice typically has a higher frequency band than male voice), but primarily most of the content is between 2 to 4 KHz. The bandwidth allocated for a telephone transmission channel is about 4 kHz. These suggest that one can recover human voice quite well with large enough samples taken: $T = \frac{1}{8000}$ seconds.

The frequency $\frac{1}{2T}$ is called the Nyquist frequency (or Nyquist rate). The theorem says: to perfectly reconstruct a band-limited signal, you must sample at more than twice its highest frequency component. The reconstruction formula is a sinc interpolation -- each sample is "smeared" by a sinc function, and the sum of all these sinc functions recovers the original signal exactly.

Sketch of proof. We now present a sketch of the proof of the result above. Let $x \in \mathcal{S}$: We know that, by Theorem, any $x \in L_2(\mathbb{R};\mathbb{R})$ can be approximated arbitrarily well by a signal in $\mathcal{S}$ and therefore, in the following, we can assume that $x \in \mathcal{S}$ (with an arbitrarily small approximation error in the $\|\cdot\|_2$ norm).

Consider the sampled signal

$x_p(t) = \int x(t)\sum_{k \in \mathbb{Z}}\delta(t - kT), \; t \in \mathbb{R},$

where $\sum_{k \in \mathbb{Z}}\delta(t - kT)$ is called an impulse train. Observe that, the impulse train is a distribution, and recall from the relevant section that the CCFT of a distribution is itself a distribution. We will consider $\hat{x}_p(f)$, which denotes the CCFT of the sampled signal, which now needs to be viewed as a distribution.

Now let us discuss what the CCFT for the impulse train $\sum_{k \in \mathbb{Z}}\delta(t - kT)$ should be.

It then follows that, the $\mathcal{F}_{CC}$ of $\sum_{k\in\mathbb{Z}}\delta(t - kT)$ is another impulse train given as:

$\hat{I}(f) = \frac{1}{T}\sum_k \delta(f - \frac{k}{T}).$

This result is in agreement with an engineering intuition that if one considers $I$ as a periodic signal, and computes its $\mathcal{F}_{CD}$, $\hat{I}(\frac{k}{T}) = \frac{1}{\sqrt{T}}1$ for all $k \in \mathbb{Z}$, this leads to

$I(t) = \sum_k \frac{1}{\sqrt{T}}(\frac{1}{\sqrt{T}})e^{i2\pi\frac{k}{T}t}$

The $\mathcal{F}_{CC}$ of $x_p(t)$ then satisfies, by the properties of convolution in frequency domain corresponding to a time-wise product in time domain, the following:

$\hat{x}_p(f) = (\hat{I} * \hat{x})(f).$

It follows after some analysis the following relation holds

$\hat{x}_p(f) = \frac{1}{T}\sum_{m \in \mathbb{Z}} \hat{x}(f - m\frac{1}{T}),$

which is an addition of shifted versions of $\hat{x}$.

If $T$ is small enough, then the signal

$\hat{\tilde{x}}(f) = T1_{(|f|< \frac{1}{2T})}\hat{x}_p(f),$

is exactly equal to the $\mathcal{F}_{CC}$ of the original signal. Hence, a low-pass filter which takes out the repetitions of the frequency shifted due to the convolution with the impulse sequence, except for the primary component, leads to the reconstruction of the original signal.

Since the rectangular low-pass filter $T1_{(|f|<\frac{1}{2T})}$ corresponds to

$h(t) = \frac{\sin(\pi\frac{t}{T})}{\pi\frac{t}{T}},$

the reconstruction can then be written as:

$\tilde{x}(t) = \sum_{n \in \mathbb{Z}} \hat{x}_p(nT)\frac{\sin(\pi\frac{t-nT}{T})}{\pi\frac{t-nT}{T}}.$

It also follows that if $T > \frac{1}{2B}$, the exact reconstruction will not be possible since the shifted frequency components will overlap with each other. This is known as aliasing. When there is aliasing, one can compute the error in the reconstruction via Parseval's theorem (see Theorem).

Sampling of a Discrete-Time (DT) Signal

A similar discussion applies to DT signals. Let $\{x(n)\}$ be a DT signal. If this signal has a finite bandwidth as $B$, that is if

$\hat{x}(f) = 0, \quad |f| > B, \quad f \in [0, 1),$

then it is possible to reconstruct exactly this signal by samples of this signal, where the sampling period $N$ that allows this satisfies:

$\frac{1}{2N} > B$

As in the CT-case, the function that we use for sampling is the discrete-time impulse train given by.

$w_N(n) = \sum_{k \in \mathbb{Z}}\delta(n - kN)$

We can take the truncated sum

$w_N^{(M)}(n) := \sum_{k=-M}^{M}\delta(n - kN)$

and work with this signal instead of the impulse train, which is in $l_2(\mathbb{Z};\mathbb{R})$ and construct an approximate signal (via Parseval's theorem after reconstruction of the signal via the low-pass filter) and then take $M \to \infty$.

This will give rise to the idealized analysis noted in the following: As earlier, using the fact that $\sum_{-M}^{M}e^{-i2\pi fkN}$, converges as a distribution, as $M \to \infty$, to an impulse train; the DCFT of $w_N$ is equal to the distribution represented by:

$\hat{w}_N(f) = \frac{1}{N}\sum_{k \in \mathbb{Z}}\delta(f - \frac{k}{N})$

Therefore, let $x_N(n) = x(n) \times w_N(n)$. It follows that

$\hat{x}_N(f) = \frac{1}{N}\sum_{k \in \mathbb{Z}} \hat{x}(f - \frac{k}{N})$

Thus, the same discussion we had above for the CT case applies here also.

Applying a low-pass filter with Fourier transform given by $N1_{(|f|<\frac{1}{2N})}$, whose inverse Fourier is the kernel

$h(n) = \frac{\sin(\frac{\pi n}{N})}{\frac{\pi n}{N}}$

leads to the reconstruction to be written as:

$\tilde{x}(n) = \sum_{k \in \mathbb{Z}} x(kN)\frac{\sin(\pi\frac{n-kN}{N})}{\pi\frac{n-kN}{N}}.$

One further remark follows: When a signal is sampled, the unsampled components become zero. Since it is already known that these values are zero, they can be taken out. This is known as decimation. Decimation has the effect of enlarging the bandwidth of the sampled signal, but it does not lead to an information loss. That is, let $x_d(n) = x_N(nN) = x(nN)$ for all $N$ where $x$ satisfies the conditions noted above to allow for recovery from its samples. Then, we have

$\tilde{x}(n) = \sum_{k \in \mathbb{Z}} x_d(k)\frac{\sin(\pi\frac{n-kN}{N})}{\pi\frac{n-kN}{N}}.$

Furthermore, we have that

$\hat{x}_d(f) = \sum_{n \in \mathbb{Z}} x_d(n)e^{-i2\pi fn} = \sum_{n \in \mathbb{Z}} x_N(nN)e^{-i2\pi fn} = \sum_{k \in \mathbb{Z}} x_N(k)e^{-i2\pi\frac{f}{N}k} = \hat{x}_N(\frac{f}{N}),$

since $x_N(k) = 0$ for $k$ not divisible by $N$.

---

Exercises