Part 7 - Nyquist-Shannon sampling theorem
Introduction
In this part we’ll cover the important Nyquist-Shannon sampling theorem. This is a fundamental theorem within digital signal processing.
However, to understand the theorem, we firstly need to understand filters.
Transfer function
Say we have a system which can be modeled as: $$ y(t) = f(t) * h(t) $$
The same system, but in the frequency domain is therefore: $$ Y(\omega) = F(\omega)\ H(\omega) $$
Just as we call, $h(t)$, the system response function, we call $H(\omega)$ for the spectral response of the system.
Since, in the most general case, we view our frequency functions as complex functions. We can say that
An input signals spectral component of frequency, $\omega$, is modified in amplitude by a factor of, $|H(\omega)|$ and shifted in phase by an angle of $\angle H(\omega)$
However, since we modify the phase, this means that our output signal may have a different waveform than our input.
Distortionless transmission
Say we just want to amplify and shift a given signal, the output waveform should be a replica of the input waveform, only amplified and shifted.
$$ y(t) = k f(t - t_d) $$
$$ Y(\omega) = kF(\omega)e^{-j\omega t_d} $$
$$ Y(\omega) = F(\omega) H(\omega) $$
$$ H(\omega) = ke^{-j\omega t_d} $$
$$ |H(\omega)| = k $$
$$ \angle H(\omega) = -\omega t_d $$
$$ t_d = - \dfrac{d}{d\omega} \angle H(\omega) $$
If the slope $\angle H(\omega)$ is constant, all frequency components are delayed by the same time delay, $t_d$. Meaning that we remain the original waveform.
If it is not constant, the time delay, $t_d$, will vary with frequency. Meaning that our components can get misaligned and, we do not preserve the original waveform.
Filters
The idea with filters are quite intuitive, we want to remove unwanted components from a signal.
An ideal filter would be:
-
Allows for distortionless transmission of a certain interval of frequency.
-
Suppresses all remaining, unwanted frequencies.
Since, in this series we won’t design filters, we won’t get that technical.
The most usual filters are high-pass and low-pass filters. In short, a high-pass filter allows signals with a frequency higher than a certain cutoff frequency and attenuates lower frequencies.
A low-pass filter allows signals with a frequency lower than our cutoff frequency and attenuates higher frequencies.
This is in the ideal case, in real systems these cutoffs can not be instantaneous of course, they gradually filter out the frequencies.
For a physically realizable system (which means casual): $$ h(t) = 0 \ | \ t < 0 $$
In the frequency domain, we have the Paley-Wiener criterion: $$ \int_{-\infty}^{\infty} \dfrac{|ln |H(\omega)||}{1 + \omega^2}+ d\omega < \infty $$
So, what we usually need to do, is to cut the tail of $h(t)$ for $t < 0$: $$ \hat{h} = h(t)u(t) $$
Sampling
Okay, now that we understand filters, let’s try to understand the approach to Nyquist-Shannon’s theorem.
In physical systems, signals are continuous-time signals, however, in our digital representations of signals we need to quantize.
We can sample the signal by taking the value, $f(t)$ at specified instants of time.
This yields us a sequence of numbers, $f(t_1), f(t_2), f(t_3), \ldots$ where $t_i$ are the time instants we have sampled.
We take these samples at equal increments of time, we call this the sample period, $T$. The inverse of the sample period is the sample frequency or sampling rate denoted by $\mathcal{F}_s$.
The sampling frequency has to be sufficiently high so that we can recover our original continuous-time signal without (much) error.
Nyquist-Shannon sampling theorem
A real signal whose bandwidth is limited to $B$ Hz can be reconstructed exactly from its samples if the sampling frequency is $\mathcal{F}_s > 2B$.
Proof
Let $f(t)$ be a band-limited signal, meaning we have a non-infinite bandwidth, in other words $F(\omega) = 0$ for $|\omega| > \omega_B$, where $\omega_B = 2\pi B$.
Sampling $f(t)$ at intervals of $T$ seconds ($\mathcal{F}_s = \dfrac{1}{T}$), is equivalent to multiplying $f(t)$ with a sequence of delta functions.
Let’s denote this sequence as: $$ s(t) = \sum_{n = -\infty}^{\infty} \delta(t - nT) $$
Let $f_s(t)$ be our sampled signal, therefore: $$ f_s(t) = f(t) s(t) $$
In the frequency domain, this product will of course become a convolution.
Let $f_s(t) \iff F(\omega)$
Let $s(t) \iff S(\omega)$. The Fourier transform is a train of delta functions in the frequency domain, spaced $\omega_s$ apart, where $\omega_s = 2\pi \mathcal{F}_s$.
$$ S(\omega) = \dfrac{2\pi}{T} \sum_{n = -\infty}^{\infty} \delta(\omega - n\omega_s) $$
The convolution: $$ F_s(\omega) = \dfrac{1}{2\pi} F(\omega) * S(\omega) \newline F_s(\omega) = \dfrac{1}{T} \sum_{n = -\infty}^{\infty} F(\omega - n\omega_s) $$
This means we get replicas of our original signal, $F(\omega)$ centered around integer multiples of our sampling frequency, $\omega_s$.
For perfect reconstruction, these replicas must not overlap. The first replica is centered around 0 Hz and has a bandwidth from $-\omega_B$ to $\omega_B$. The next replica is centered around $\omega_s$.
For no overlap, the start of the next replica at $\omega_s - \omega_b$ must be greater than the end of the first replica at $\omega_b$, in other words: $$ \omega_s - \omega_b > \omega_b \newline \omega_s > 2 \omega_b \newline $$
Using that $\omega_s = 2\pi \mathcal{F}$ and $\omega_b = 2\pi B$: $$ 2\pi \mathcal{F} > 2(2 \pi B) \newline 2\pi \mathcal{F} > 4 \pi B \newline \boxed{\mathcal{F} > 2B} $$