# 2: The Sampling Theorem

- Page ID
- 96270

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)

( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)

\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)

\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

\( \newcommand{\Span}{\mathrm{span}}\)

\( \newcommand{\id}{\mathrm{id}}\)

\( \newcommand{\Span}{\mathrm{span}}\)

\( \newcommand{\kernel}{\mathrm{null}\,}\)

\( \newcommand{\range}{\mathrm{range}\,}\)

\( \newcommand{\RealPart}{\mathrm{Re}}\)

\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

\( \newcommand{\Argument}{\mathrm{Arg}}\)

\( \newcommand{\norm}[1]{\| #1 \|}\)

\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)

\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)

\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)

\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vectorC}[1]{\textbf{#1}} \)

\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)

\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)

\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)- Converting between a signal and numbers.

## Analog-to-Digital Conversion

Because of the way computers are organized, signal must be represented by a finite number of bytes. This restriction means that **both** the time axis and the amplitude axis must be **quantized**: They must each be a multiple of the integers. ** ^{1}** Quite surprisingly, the Sampling Theorem allows us to quantize the time axis

**without error**for some signals. The signals that can be sampled without introducing error are interesting, and as described in the next section, we can make a signal "samplable" by filtering. In contrast, no one has found a way of performing the amplitude quantization step without introducing an unrecoverable error. Thus, a signal's value can no longer be any real number. Signals processed by digital computers must be

**discrete-valued**: their values must be proportional to the integers. Consequently,

**analog-to-digital conversion introduces error**.

Figure \(\PageIndex{1}\): Analog to digital signal stages of signal representation. Sasche Spors, Digital Signal Processing - Theory and Computational Examples. Introduction [https://nbviewer.org/github/spatiala...duction.ipynb]

## The Sampling Theorem

Digital transmission of information and digital signal processing all require signals to first be "acquired" by a computer. One of the most amazing and useful results in electrical engineering is that signals can be converted from a function of time into a sequence of numbers **without error**: We can convert the numbers back into the signal with (theoretically) **no** error. Harold Nyquist, a Bell Laboratories engineer, first derived this result, known as the Sampling Theorem, in the 1920s. It found no real application back then. Claude Shannon, also at Bell Laboratories, revived the result once computers were made public after World War II.

The sampled version of the analog signal **s(t)** is **s(nT _{s})**, with

**T**

_{s}known as the

**sampling interval**. Clearly, the value of the original signal at the sampling times is preserved; the issue is how the signal values

**between**the samples can be reconstructed since they are lost in the sampling process. To characterize sampling, we approximate it as the product:

\[x(t)=s(t)P_{T_{s}}(t) \nonumber \]

with **P _{T}_{s}** being the periodic pulse signal. The resulting signal, as shown in Figure 5.3.1 has nonzero values only during the time intervals :

\[\left ( nT_{s}-\frac{\Delta }{2}, nT_{s}+\frac{\Delta }{2}\right ),n\in \left \{ ...,-1,0,1,... \right \} \nonumber \]

For our purposes here, we center the periodic pulse signal about the origin so that its Fourier series coefficients are real (the signal is even).

\[P_{T_{s}}(t)=\sum_{k=-\infty }^{\infty }c_{k}e^{\frac{i2\pi kt}{T_{s}}} \nonumber \]

\[c_{k}=\frac{\sin \left ( \frac{\pi k\Delta }{T_{s}}\right )}{\pi k} \nonumber \]

If the properties of **s(t)** and the periodic pulse signal are chosen properly, we can recover **s(t) **from **x****(t) **by filtering.

To understand how signal values between the samples can be "filled" in, we need to calculate the sampled signal's spectrum. Using the Fourier series representation of the periodic sampling signal,

\[x(t)=\sum_{k=-\infty }^{\infty }c_{k}e^{\frac{i2\pi kt}{T_{s}}}s(t) \nonumber \]

Considering each term in the sum separately, we need to know the spectrum of the product of the complex exponential and the signal. Evaluating this transform directly is quite easy.

\[\int_{-\infty }^{\infty }s(t)e^{\frac{i2\pi kt}{T_{s}}}e^{i2\pi ft}dt=\int_{-\infty }^{\infty }s(t)e^{-\left ( i2\pi \left ( f-\frac{k}{T_{s}} \right )\right )}dt=S\left ( f-\frac{k}{T_{s}} \right ) \nonumber \]

Thus, the spectrum of the sampled signal consists of weighted (by the coefficients **c _{k}**) and delayed versions of the signal's spectrum Figure 5.3.2 below.

\[X(f)=\sum_{-\infty }^{\infty }c_{k}S\left ( f-\frac{k}{T_{s}} \right ) \nonumber \]

In general, the terms in this sum overlap each other in the frequency domain, rendering recovery of the original signal impossible. This unpleasant phenomenon is known as **aliasing**.

If, however, we satisfy two conditions:

- The signal
**s(t)**is**bandlimited**—has power in a restricted frequency range—to**W**Hz - the sampling interval
**T**_{s }is small enough so that the individual components in the sum do not overlap -**Ts <****1/2****W**

Aliasing will not occur. In this delightful case, we can recover the original signal by lowpass filtering **x****(t) **with a filter having a cutoff frequency equal to **W** Hz. These two conditions ensure the ability to recover a bandlimited signal from its sampled version: We thus have the **Sampling Theorem**.

The example below demonstrates the effect of under sampling a signal.

###### Solution

Figure \(\PageIndex{4}\): Aliasing example.

The Sampling Theorem (as stated) does not mention the pulse width **Δ**. What is the effect of this parameter on our ability to recover a signal from its samples (assuming the Sampling Theorem's two conditions are met)?

**Solution**

The only effect of pulse duration is to unequally weight the spectral repetitions. Because we are only concerned with the repetition centered about the origin, the pulse duration has no significant effect on recovering a signal from its samples.

The frequency **1/2T _{s}**, known today as the

**Nyquist frequency**and the

**Shannon sampling frequency**, corresponds to the highest frequency at which a signal can contain energy and remain compatible with the Sampling Theorem. High-quality sampling systems ensure that no aliasing occurs by unceremoniously lowpass filtering the signal (cutoff frequency being slightly lower than the Nyquist frequency) before sampling. Such systems therefore vary the

**anti-aliasing**filter's cutoff frequency as the sampling rate varies. Because such quality features cost money, many sound cards do

**not**have anti-aliasing filters or, for that matter, post-sampling filters. They sample at high frequencies, 44.1 kHz for example, and hope the signal contains no frequencies above the Nyquist frequency (22.05 kHz in our example). If, however, the signal contains frequencies beyond the sound card's Nyquist frequency, the resulting aliasing can be impossible to remove.

If we satisfy the Sampling Theorem's conditions, the signal will change only slightly during each pulse. As we narrow the pulse, making

What is the simplest bandlimited signal? Using this signal, convince yourself that less than __or equal__ two samples/period will not suffice to specify it. If the sampling rate **1/****T**_{s }is not high enough, what signal would your resulting undersampled signal become? For example, let fs_undersampled = 10 (the Nyquist frequency) in Exercise 2.1.

**Solution**

The simplest bandlimited signal is the sine wave. At the Nyquist frequency, exactly two samples/period would occur. Reducing the sampling rate would result in fewer samples/period, and these samples would appear to have arisen from a lower frequency sinusoid.

- We assume that we do not use floating-point A/D converters.

## Continuous-Time Periodic Signals

A continuous-time period signal must meet the following requirement:

\[x(t) = x(t + T), \; -\infty < t < \infty\]

for example

\[x(t) = A \cos(2 \pi F t \; + \; \theta), \; where \; T = 1/F\]

where F may be an irrational floating point number.

## Discrete-Time Periodic Signals

A discrete-time period signal (or sequence) must meet the following requirement:

\[x(n) = x(n + N), \; -\infty < n < -\infty\]

where n and N are integers.

Since n and N must be integers, there an additional requirement for trigonometric functions.

\[x(n) = A \cos(\omega\, n) \]

is a discrete-time periodic signal if

\[\omega \, N = 2 \pi \,k \]

where the period, N, and k are both integer, and the frequency, \(f = \frac{k}{N}\), is a rational fraction.

Is the following function periodic and if so what is the period?

\[x(n) = cos(0.6 \pi n) \]

###### Solution

\[N = \frac{2 \pi k}{\omega} = \frac{2 \pi k}{0.6 \pi} = \frac{10 k}{3} \; \Rightarrow \; \frac{k}{N} = \frac{3}{10} \; \Rightarrow \;N = 10\]

Note the \(\frac{k}{N}\) fraction was reduced to the lowest common denominator.

Figure \(\PageIndex{5}\): Example periodic sequence. Two periods.