Week 7

The sampling theorem is what relates DT to CT. Consider a system where we multply the input signal $x(t)$ by a pulse train $q(t)$.

%\img{images/sampling/mult/justboxes.ps}
%\img{images/sampling/mult/justfunction.ps}

When we multiply the signals, we get the original signal scaled by the pulse train. The figure below shows the case where $A=1$:

%\img{images/sampling/mult/both.ps}

In essence we are tossing out values from the signal. That is the critical thing that happens when you sample a signal. How much can we afford to throw out and still recover a signal? This is what the sampling theroem tells us. Lets start by looking at the frequency spectrum of this signal when we have a bandlimited input signal given by the following spectra:

%\img{images/triangles/voice/triangle.ps}

We know that multiplication in the time domain corresponds to convolution in the frequency domain:

$$
X_q(\omega) = \frac{1}{2\pi} (X * Q)(\omega)
$$

What is $Q(\omega)$? Why not just plug in $q(t)$ into the CTFT?

\begin{align*}
Q(\omega) &= \int_{-\infty}^{\infty} q(t) e^{-i\omega t}dt \\
\end{align*}

No periodic signal can be plugged in to the analysis equation to get a fourier transform---it doesn't have finite energy and it is not absolutely integrable. So, we have got to go through a round about way. For periodic signals we talk about energy in a period. We have to use something else to figure out what the transform is. In general, no periodic signal can directly go into the CTFT.


To bypass this, we can :


\begin{enumerate}
\item Express $q(t)$ in terms of its fourier series coefficients.

\begin{align*}
q(t) &= \sum \limits_{k\in\Z} Q_k e^{ik\omega_s t} \quad \mbox{where } \omega_s = 2\pi/T \\
\end{align*}

\item Then use the CTFT on these terms.

\begin{align*}
Q(\omega) &= 2\pi \sum \limits_{k\in\Z} Q_k \delta(\omega - k\omega_s) \\
\end{align*}

\end{enumerate}

Lets derive the CTFT for this periodic signal:


We first equate the CFS synthesis with the CTFT synthesis equations:
\begin{align*}
q(t) &= \sum \limits_{k \in \Z} Q_k e^{ik\omega_s t} = \frac{1}{2\pi} \int_{\R} Q(\omega) e^{i\omega t} d\omega \\
\end{align*}

Then we can solve:

\begin{align*}
\sum \limits_{k \in \Z} Q_k e^{ik\omega_s t} &= \frac{1}{2\pi} \int_{\R} Q(\omega) e^{i\omega t} d\omega \\
\sum \limits_{k \in \Z} Q_k e^{ik\omega_s t} &= \frac{1}{2\pi} \int_{\R} \sum \limits_{k\in \Z} A_k \delta(\omega - k\omega_s)  e^{i\omega t} d\omega \\
\sum \limits_{k \in \Z} Q_k e^{ik\omega_s t} &= \sum \limits_{k\in \Z} \frac{A_k}{2\pi} \int_{\R} \delta(\omega - k\omega_s)  e^{i\omega t} d\omega \\
\sum \limits_{k \in \Z} Q_k e^{ik\omega_s t} &= \sum \limits_{k\in \Z} \frac{A_k}{2\pi} e^{ik\omega_s t}  \\
\end{align*}

Now we can equate the coefficients:

\begin{align*}
\sum \limits_{k \in \Z} Q_k e^{ik\omega_s t} &= \sum \limits_{k\in \Z} \frac{A_k}{2\pi} e^{ik\omega_s t}  \\
Q_k &= \frac{A_k}{2\pi} \\
2\pi Q_k &= A_k \\
\end{align*}

This tells us what the fourier transform is:

\begin{align*}
Q(\omega) &= 2\pi \sum \limits_{k\in \Z} Q_k \delta(\omega - k\omega_s) \\
\end{align*}


Now lets find the fourier series coefficients:

\begin{align*}
Q_k &= \frac{1}{T} \int_{\langle T \rangle} q(t) e^{-ik\omega_st}dt \\
Q_k &= \frac{A}{T} \int_{-\Delta/2}^{\Delta/2} e^{-ik\omega_st}dt \\
Q_k &= \frac{A}{T} \left. \frac{e^{-ik\omega_st}}{-ik\omega_s} \right|^{\Delta/2}_{-\Delta/2} \\
Q_k &= \frac{A}{T} \frac{2\sin( k \omega_s \Delta/2)}{k\omega_s} \\
Q_k &= \frac{A\sin( k \omega_s \Delta/2)}{k\pi} \\
\end{align*}

% image of Q_k as  kronecker deltas
%\img{images/sampling/samples/qk/graph.ps}

Now that we know $Q_k$, we can determine $Q(\omega)$:

\begin{align*}
Q(\omega) &= 2\pi \sum \limits_{k\in\Z} Q_k \delta(\omega - k\omega_s) \\
Q(\omega) &= 2\pi \sum \limits_{k\in\Z} \frac{A\sin( k \omega_s \Delta/2)}{k\pi} \delta(\omega - k\omega_s) \\
\end{align*}


% image of Q(\omega) as dirac deltas  spaces by \omega_s
% \img{images/sampling/samples/qw/graph.ps}

\psset{unit=1cm}
\begin{center}
\begin{pspicture}(-5,-1)(5,3)
    
\rput(4,1.79990000199998){$Q(\omega)$}

% x-axis
\psline{->}(-4.6, 0)(4.4, 0)
\rput(4.4,-0.3){$\omega$}

% begin x-axis labels:
\psline(-4.2, -0.1)(-4.2, 0.1)
\rput(-4.2, -0.3){$-7\omega_s$}
\psline(-3.6, -0.1)(-3.6, 0.1)
\rput(-3.6, -0.3){$-6\omega_s$}
\psline(-3, -0.1)(-3, 0.1)
\rput(-3, -0.3){$-5\omega_s$}
\psline(-2.4, -0.1)(-2.4, 0.1)
\rput(-2.4, -0.3){$-4\omega_s$}
\psline(-1.8, -0.1)(-1.8, 0.1)
\rput(-1.8, -0.3){$-3\omega_s$}
\psline(-1.2, -0.1)(-1.2, 0.1)
\rput(-1.2, -0.3){$-2\omega_s$}
\psline(-0.6, -0.1)(-0.6, 0.1)
\rput(-0.6, -0.3){$-\omega_s$}
\psline(0, -0.1)(0, 0.1)
\rput(0, -0.3){$0$}
\psline(0.6, -0.1)(0.6, 0.1)
\rput(0.6, -0.3){$\omega_s$}
\psline(1.2, -0.1)(1.2, 0.1)
\rput(1.2, -0.3){$2\omega_s$}
\psline(1.8, -0.1)(1.8, 0.1)
\rput(1.8, -0.3){$3\omega_s$}
\psline(2.4, -0.1)(2.4, 0.1)
\rput(2.4, -0.3){$4\omega_s$}
\psline(3, -0.1)(3, 0.1)
\rput(3, -0.3){$5\omega_s$}
\psline(3.6, -0.1)(3.6, 0.1)
\rput(3.6, -0.3){$6\omega_s$}
% end x-axis labels:


\fileplot[linewidth=1.0pt,linestyle=dashed,linecolor=blue!40]{sinc.dat}

%dirac
\psline[linewidth=1.25pt]{->}(-3.6, 0)(-3.6, 0.16534747163524)

%dirac
\psline[linewidth=1.25pt]{->}(-3, 0)(-3, -0.0698538745497315)

%dirac
\psline[linewidth=1.25pt]{->}(-2.4, 0)(-2.4, -0.3113014402612)

%dirac
\psline[linewidth=1.25pt]{->}(-1.8, 0)(-1.8, -0.184383518039522)

%dirac
\psline[linewidth=1.25pt]{->}(-1.2, 0)(-1.2, 0.422164487844469)

%dirac
\psline[linewidth=1.25pt]{->}(-0.6, 0)(-0.6, 1.16504885745903)

%dirac
\psline[linewidth=1.25pt]{->}(0, 0)(0, 1.49990000199998)
\rput(0, 1.7){$(2\pi Q_0)$}

%dirac
\psline[linewidth=1.25pt]{->}(0.6, 0)(0.6, 1.16504885745903)

%dirac
\psline[linewidth=1.25pt]{->}(1.2, 0)(1.2, 0.422164487844469)

%dirac
\psline[linewidth=1.25pt]{->}(1.8, 0)(1.8, -0.184383518039522)

%dirac
\psline[linewidth=1.25pt]{->}(2.4, 0)(2.4, -0.3113014402612)

%dirac
\psline[linewidth=1.25pt]{->}(3, 0)(3, -0.0698538745497315)

%dirac
\psline[linewidth=1.25pt]{->}(3.6, 0)(3.6, 0.16534747163524)

\end{pspicture}
\end{center}


Now we are ready to perform the convolution:

$$
X_q(\omega) = \frac{1}{2\pi} (X * Q)(\omega)
$$

Recall that the spectrum of our input signal was a triangle. What happens when the triangle is convolved with scaled and shifted impulses? We get scaled and shifted triangles:

% image of X_q(\omega) with the signal X convolved with Q
%\img{images/sampling/samples/xq/axis.ps}

Recoverability is based on not overlapping replicated spectra. The sampling frequency $\omega_s$ is sufficiently large such that when I replicate the triangle on adjacent multiples of fundamental frequencies they don't overlap.

%\img{images/sampling/impulse/triangles/zoom2/impulse.ps}
%\img{images/sampling/impulse/triangles/zoom/threetris2.ps}

Notice that $D \leq \omega_s - D \Rightarrow \omega_s \leq 2D$, where $2D$ is the bandwidth of the spectra. We refer to bandwidth in this course as the total footprint of the signal on the omega axis. Some books use half of this value. They would say you need two times the bandwidth to recover the original signal. Note that $2D \leq \omega_s$ is sufficient, but not necessary. Compressed sampling is an area of research that studies this concept.

Sampling using a pulse train

What if we multiply with an impulse train instead of a pulse train? Not that this is ideal because in real life you cannot generate these impulses. Normally, signals that can be generated approximate the pulse trains. Consider a system where we multply the input signal $x(t)$ by an impulse train $g(t)$.


% \img{images/sampling/impulse/impulse/impuls.eps}

\psset{unit=1cm}
\begin{center}
\begin{pspicture}(-5,-1)(5,3)
    
% function name
\rput(4,1.7){$g(t) = \sum \limits_{k=-\infty}^{\infty} \delta(t-kT)$}

\rput(-4.4, 0.5){$\cdots$}
\rput(4.4, 0.5){$\cdots$}

%dirac
\psline[linewidth=1.25pt]{->}(-4, 0)(-4, 1)

%dirac
\psline[linewidth=1.25pt]{->}(-3, 0)(-3, 1)

%dirac
\psline[linewidth=1.25pt]{->}(-2, 0)(-2, 1)

%dirac
\psline[linewidth=1.25pt]{->}(-1, 0)(-1, 1)

%dirac
\psline[linewidth=1.25pt]{->}(0, 0)(0, 1)
\rput(0,1.3){(1)}

%dirac
\psline[linewidth=1.25pt]{->}(1, 0)(1, 1)

%dirac
\psline[linewidth=1.25pt]{->}(2, 0)(2, 1)

%dirac
\psline[linewidth=1.25pt]{->}(3, 0)(3, 1)

%dirac
\psline[linewidth=1.25pt]{->}(4, 0)(4, 1)


% x-axis
\psline{->}(-4.4, 0)(4.9, 0)
\rput(4.4,-0.3){$t$}

% begin x-axis labels:
\psline(-4, -0.1)(-4, 0.1)
\rput(-4, -0.3){$-4T$}
\psline(-3, -0.1)(-3, 0.1)
\rput(-3, -0.3){$-3T$}
\psline(-2, -0.1)(-2, 0.1)
\rput(-2, -0.3){$-2T$}
\psline(-1, -0.1)(-1, 0.1)
\rput(-1, -0.3){$-T$}
\psline(0, -0.1)(0, 0.1)
\rput(0, -0.3){$0$}
\psline(1, -0.1)(1, 0.1)
\rput(1, -0.3){$T$}
\psline(2, -0.1)(2, 0.1)
\rput(2, -0.3){$2T$}
\psline(3, -0.1)(3, 0.1)
\rput(3, -0.3){$3T$}
\psline(4, -0.1)(4, 0.1)
\rput(4, -0.3){$4T$}
% end x-axis labels:
\end{pspicture}
\end{center}

How does this impules train $g(t)$ relate to pulse train $q(t)$? 

$$
g(t) = \lim_{\Delta \to 0} q(t)
$$

% \img{images/sampling/impulse/multiplied/impulse.ps}

%% image of multiplication


%%% graph of x_g(t) and x(t)

What is the fourier transform of the impulse train?

%% image of impulse train
%% image of new impulse train

\begin{align*}
G(\omega) &= 2\pi \sum \limits_{k\in\Z} G_k \delta(\omega - k\omega_s) \\
G(\omega) &= 2\pi \sum \limits_{k\in\Z} \frac{1}{T} \delta(\omega - k\omega_s) \\
G(\omega) &= \frac{2\pi}{T} \sum \limits_{k\in\Z} \delta(\omega - k\omega_s) \\
G(\omega) &= \omega_s \sum \limits_{k\in\Z} \delta(\omega - k\omega_s) \\
\end{align*}

% \img{images/sampling/impulse/ftrans/impulse.ps}

\begin{center}
\begin{pspicture}(-5,-1)(5,3)
    
% function name
\rput(3.5,1.7){$G(\omega) = \omega_s \sum \limits_{k=-\infty}^{\infty} \delta(\omega - k\omega_s)$}

\rput(-4.4, 0.5){$\cdots$}
\rput(4.4, 0.5){$\cdots$}

%dirac
\psline[linewidth=1.25pt]{->}(-4, 0)(-4, 1)

%dirac
\psline[linewidth=1.25pt]{->}(-3, 0)(-3, 1)

%dirac
\psline[linewidth=1.25pt]{->}(-2, 0)(-2, 1)

%dirac
\psline[linewidth=1.25pt]{->}(-1, 0)(-1, 1)

%dirac
\psline[linewidth=1.25pt]{->}(0, 0)(0, 1)
\rput(0,1.3){$\left(\frac{2\pi}{T}\right)$}

%dirac
\psline[linewidth=1.25pt]{->}(1, 0)(1, 1)

%dirac
\psline[linewidth=1.25pt]{->}(2, 0)(2, 1)

%dirac
\psline[linewidth=1.25pt]{->}(3, 0)(3, 1)

%dirac
\psline[linewidth=1.25pt]{->}(4, 0)(4, 1)


% x-axis
\psline{->}(-4.4, 0)(4.9, 0)
\rput(4.6,-0.3){$\omega$}

% begin x-axis labels:
\psline(-4, -0.1)(-4, 0.1)
\rput(-4, -0.3){$-4\omega_s$}
\psline(-3, -0.1)(-3, 0.1)
\rput(-3, -0.3){$-3\omega_s$}
\psline(-2, -0.1)(-2, 0.1)
\rput(-2, -0.3){$-2\omega_s$}
\psline(-1, -0.1)(-1, 0.1)
\rput(-1, -0.3){$-\omega_s$}
\psline(0, -0.1)(0, 0.1)
\rput(0, -0.3){$0$}
\psline(1, -0.1)(1, 0.1)
\rput(1, -0.3){$\omega_s$}
\psline(2, -0.1)(2, 0.1)
\rput(2, -0.3){$2\omega_s$}
\psline(3, -0.1)(3, 0.1)
\rput(3, -0.3){$3\omega_s$}
\psline(4, -0.1)(4, 0.1)
\rput(4, -0.3){$4\omega_s$}
% end x-axis labels:

\end{pspicture}
\end{center}


Convolution of a function with a shifted dirac shifts the function by an amount equal to the shift of the dirac and scales it by the strength of the dirac. We have found that periodic signals have impulsive fourier transforms where impulses are uniformly spaced. Note that the strength of the specta is $\frac{2\pi}{T} = \omega_s$, and the periodicity and spacing is $\omega_s$. Recall that the impulse train has coefficients that don't depend on $k$. All frequencies equally contibute. Now we can find the convolution of the original input signal $x(t)$ and $g(t)$:

%% image of X_g(\omega)
% \img{images/sampling/impulse/triangles/impulse.ps}

\psset{unit=1cm}
\begin{center}
\begin{pspicture}(-5,-1)(5,3)
    
% function name
\rput(4,1.7){$X_g(\omega) = \frac{1}{2\pi}(X * G) (\omega)$}

\rput(-4.5, 0.5){$\cdots$}
\rput(4.5, 0.5){$\cdots$}


%fill plot for triangle.dat
\pscustom[fillstyle=solid,fillcolor=blue!40,linestyle=none]{
	\fileplot[linewidth=0pt]{triangle.dat}
}
\fileplot[linewidth=1.5pt]{triangle.dat}

\rput(0,1.4){$\left(\frac{1}{T}\right)$}

% x-axis
\psline{->}(-4.4, 0)(4.9, 0)
\rput(4.6,-0.3){$\omega$}

% begin x-axis labels:
\psline(-4, -0.1)(-4, 0.1)
\rput(-4, -0.3){$-4\omega_s$}
\psline(-3, -0.1)(-3, 0.1)
\rput(-3, -0.3){$-3\omega_s$}
\psline(-2, -0.1)(-2, 0.1)
\rput(-2, -0.3){$-2\omega_s$}
\psline(-1, -0.1)(-1, 0.1)
\rput(-1, -0.3){$-\omega_s$}
\psline(0, -0.1)(0, 0.1)
\rput(0, -0.3){$0$}
\psline(1, -0.1)(1, 0.1)
\rput(1, -0.3){$\omega_s$}
\psline(2, -0.1)(2, 0.1)
\rput(2, -0.3){$2\omega_s$}
\psline(3, -0.1)(3, 0.1)
\rput(3, -0.3){$3\omega_s$}
\psline(4, -0.1)(4, 0.1)
\rput(4, -0.3){$4\omega_s$}
% end x-axis labels:

\end{pspicture}
\end{center}

We can simply do a low pass filter to recover the signal from its samples. But we cannot over look the fact that we must sample at a certain rate to recover the signal. Lets take a closer look at the signal and its boundaries:

% \img{images/sampling/impulse/triangles/zoom/threetris.ps}

\psset{unit=1cm}
\begin{center}
\begin{pspicture}(-5,-1)(5,3)
    
% function name
\rput(2.5,1.3){$X_g(\omega) = \frac{1}{2\pi}(X * G) (\omega)$}

\rput(-2.6, 0.5){$\cdots$}
\rput(3, 0.5){$\cdots$}


%fill plot for triangle.dat
\pscustom[fillstyle=solid,fillcolor=blue!40,linestyle=none]{
	\fileplot[linewidth=0pt]{1.dat}
	\fileplot[linewidth=0pt]{2.dat}
	\fileplot[linewidth=0pt]{3.dat}
}
\fileplot[linewidth=1.5pt]{1.dat}
\fileplot[linewidth=1.5pt]{2.dat}
\fileplot[linewidth=1.5pt]{3.dat}

\rput(0,1.3){$\left(1/T_s\right)$}

% x-axis
\psline{->}(-2.7, 0)(3, 0)
\rput(3.1,-0.2){$\omega$}

% critical points

\rput(-0.5,-0.2){$-D$}
\rput(0.5,-0.2){$D$}
\psline(-0.5, -0.05)(-0.5, 0.05)
\psline(0.5, -0.05)(0.5, 0.05)

\rput(-2.5,-0.2){$-\omega_s - D$}
\rput(-1.5,-0.2){$-\omega_s + D$}
\psline(-2.5, -0.05)(-2.5, 0.05)
\psline(-1.5, -0.05)(-1.5, 0.05)

\rput(2.5,-0.2){$\omega_s + D$}
\rput(1.5,-0.2){$\omega_s - D$}
\psline(2.5, -0.05)(2.5, 0.05)
\psline(1.5, -0.05)(1.5, 0.05)

% begin x-axis labels:
\psline(-2, -0.05)(-2, 0.05)
\rput(-2, -0.2){$-\omega_s$}
\psline(-1, -0.05)(-1, 0.05)
\psline(0, -0.05)(0, 0.05)
\rput(0, -0.2){$0$}
\psline(1, -0.05)(1, 0.05)
\psline(2, -0.05)(2, 0.05)
\rput(2, -0.2){$\omega_s$}

\end{pspicture}
\end{center}

We must have $D \leq \omega_s - D$. This implies the same condition, $2D \leq \omega_s$. This is called the \emph{Nyquist Criterion}. If you have a bandlimited signal, you can sample it at a rate of the bandwidth or faster and still recover the signal. In conclusion, a set of sufficient conditions to recover a signal $x$ from its samples $x(nT)$ are:

\begin{enumerate}
\item $x$ is bandlimited
\item $\omega_s = \frac{2\pi}{T} \leq 2D$
\end{enumerate}

Note that in reality you want to make room for the rolloff of the low pass filter, since the Nyquist rate assumes an ideal low pass filter. What happens if you don't sample fast enough?

% \img{images/sampling/impulse/triangles/aliased/impulse.ps}

Notice that the higher frequency content gets ``folded'' into the lower frequency range. This phenomenon is called aliasing.

7.1 Sampling