MATH 414 Lecture 21

« previous | Wednesday, March 5, 2014 | next »

Sampling Theorem

Band-limited function $f(t)$ (this means that $\hat{f}(\lambda )=0$ for $\left|\lambda \right|\ge \mathrm{\Omega }$.

$f(t)=\frac{1}{\sqrt{2\pi }}\underset{-\mathrm{\Omega }}{\overset{\mathrm{\Omega }}{\int }}\hat{f}(\omega ){\mathrm{e}}^{i\omega t}\mathrm{d}\omega$

• $\mathrm{\Omega }$ is the angular frequency
• ${\nu }_f=\frac{\mathrm{\Omega }}{2\pi }$ is the natural frequency (measured in Hertz)
• ${\nu }_{Ny}=\frac{\mathrm{\Omega }}{\pi }=2{\nu }_f$ is the Nyquist rate (or sampling rate)

Note $\frac{j\pi }{\mathrm{\Omega }}=\frac{j}{{\nu }_{Ny}}$

Theorem. If $f(t)$ is band-limited, with $\hat{f}(\omega )=0$ for $\left|\omega \right|\ge \mathrm{\Omega }$, then $f(t)=\sum _{j=-\mathrm{\infty }}^{\mathrm{\infty }}f\left(\frac{j\pi }{\mathrm{\Omega }}\right)\frac{\sin (\mathrm{\Omega }t-j\pi )}{\mathrm{\Omega }t-j\pi }$

Definition:

$f(t)=\frac{1}{\sqrt{2\pi }}\underset{-\mathrm{\Omega }}{\overset{\mathrm{\Omega }}{\int }}\hat{f}(\omega ){\mathrm{e}}^{i\omega t}\mathrm{d}\omega$

Proof. Expand $\hat{f}(\omega )$ in a Fourier Series on $[-\mathrm{\Omega },\mathrm{\Omega }]$:

$\begin{array}{rl}\hat{f}(\omega )& =\sum _{n=-\mathrm{\infty }}^{\mathrm{\infty }}{c}_n{\mathrm{e}}^{\frac{i\pi n}{\mathrm{\Omega }}\omega }\\ c_n& =\frac{1}{2\mathrm{\Omega }}\underset{-\mathrm{\Omega }}{\overset{\mathrm{\Omega }}{\int }}\hat{f}(\omega ){\mathrm{e}}^{-\frac{i\pi n\omega }{\mathrm{\Omega }}}\mathrm{d}\omega \\ & =\frac{\sqrt{2\pi }}{2\mathrm{\Omega }}\frac{1}{\sqrt{2\pi }}\underset{-\mathrm{\Omega }}{\overset{\mathrm{\Omega }}{\int }}\hat{f}(\omega ){\mathrm{e}}^{i(-\frac{n\pi }{\mathrm{\Omega }})\omega }\mathrm{d}\omega \\ & =\frac{\sqrt{2\pi }}{2\mathrm{\Omega }}f(-\frac{n\pi }{\mathrm{\Omega }})\\ \end{array}$

Use this definition of $c_n$ in the series expansion of $\hat{f}$:

$\begin{array}{rl}\hat{f}& =\sum _{n=-\mathrm{\infty }}^{\mathrm{\infty }}{c}_n{\mathrm{e}}^{\frac{in\pi \omega }{\mathrm{\Omega }}}\\ & =\sum _{j=-\mathrm{\infty }}^{\mathrm{\infty }}{c}_{-j}{\mathrm{e}}^{-\frac{ij\pi \omega }{\mathrm{\Omega }}}\\ & =\sum _{j=-\mathrm{\infty }}^{\mathrm{\infty }}\frac{\sqrt{2\pi }}{2\mathrm{\Omega }}f\left(\frac{j\pi }{\mathrm{\Omega }}\right){\mathrm{e}}^{-\frac{ij\pi \omega }{\mathrm{\Omega }}}\end{array}$

Put the series back into the definition and interchange sum & integral (takes a lot of work)

$\begin{array}{rl}f(t)& =\frac{1}{\sqrt{2\pi }}\underset{-\mathrm{\Omega }}{\overset{\mathrm{\Omega }}{\int }}\left(\left(\sum _{j=-\mathrm{\infty }}^{\mathrm{\infty }}\frac{\sqrt{2\pi }}{2\mathrm{\Omega }}f\left(\frac{j\pi }{\mathrm{\Omega }}\right){\mathrm{e}}^{-\frac{j\pi \omega }{\mathrm{\Omega }}}\right){\mathrm{e}}^{i\omega t}\right)\mathrm{d}\omega \\ & =\sum _{j=-\mathrm{\infty }}^{\mathrm{\infty }}\frac{\sqrt{2\pi }}{2\mathrm{\Omega }}f\left(\frac{j\pi }{\mathrm{\Omega }}\right)\underset{-\mathrm{\Omega }}{\overset{\mathrm{\Omega }}{\int }}{\mathrm{e}}^{i(t-\frac{j\pi \omega }{\mathrm{\Omega }})\omega }\mathrm{d}\omega \\ & =\sum _{j=-\mathrm{\infty }}^{\mathrm{\infty }}\frac{\sqrt{2\pi }}{2\mathrm{\Omega }}f\left(\frac{j\pi }{\mathrm{\Omega }}\right)\frac{\sin (\mathrm{\Omega }t-j\pi )}{\mathrm{\Omega }t-j\pi }\end{array}$

This recovers $f$ from its samples at $\frac{j}{{\nu }_{Ny}}$.

quod erat demonstrandum

Discrete Fourier Transform

Way of computing an approximation to coefficients in the Fourier Series $f(t)=\sum _{n=-\mathrm{\infty }}^{\mathrm{\infty }}{c}_n{\mathrm{e}}^{int}$, where $c_n=\frac{1}{2\pi }\underset{0}{\overset{2\pi }{\int }}f(t){\mathrm{e}}^{-int}$, given samples at $t={\left\{\frac{2\pi }{n}j\right\}}_{j=1}^n$.

We know $y_j=f\left(\frac{2\pi j}{n}\right)$.

We want $c_n=\frac{1}{2\pi }\underset{0}{\overset{2\pi }{\int }}f(t){\mathrm{e}}^{-int}\mathrm{d}t$, so we need a quadrature formula to approximate

$\underset{a}{\overset{b}{\int }}f(t)\mathrm{d}t=\sum _{j=0}^n{q}_{j}f\left(\frac{2\pi j}{n}\right)=\sum _{j=0}^n{q}_j{y}_j$

We shall use the composite trapezoidal rule:

$\underset{a}{\overset{b}{\int }}f(t)\mathrm{d}t\approx \frac{b-a}{n}(\frac{1}{2}{y}_0+\frac{1}{2}{y}_n+\sum _{j=1}^{n-1}f(a+\frac{b-a}{n}j))$

Suppose $f$ is $2\pi$-periodic (and continuous): $a=0$, $b=2\pi$, and $f(t)=f(t+2\pi )$. Then $y_0=f(0)$ and $y_n=f(2\pi )$, so $y_0=y_n$:

$\underset{a}{\overset{b}{\int }}f(t)\mathrm{d}t\approx \frac{2\pi }{n}\sum _{j=0}^{n-1}f\left(\frac{2\pi }{n}j\right)$

Back to the original problem, we wish to evaluate $c_k=\frac{1}{2\pi }\underset{0}{\overset{2\pi }{\int }}f(t){\mathrm{e}}^{-ikt}\mathrm{d}t\approx \frac{1}{2\pi }\left(\frac{2\pi }{n}\right)\sum _{j=0}^{n-1}f\left(\frac{2\pi }{n}j\right){\mathrm{e}}^{-i\frac{2\pi }{n}jk}=\frac{1}{n}\sum _{j=0}^{n-1}{y}_j=\stackrel{kj}{\bar{\omega }}$

Where $\bar{\omega }={\mathrm{e}}^{-i\frac{2\pi }{n}}$ is the complex conjugate of $\omega ={\mathrm{e}}^{i\frac{2\pi }{n}}$.

We get a nice inversion formula as well:

${\hat{y}}_k:=\sum _{j=0}^{n-1}{y}_j\stackrel{jk}{\bar{\omega }}$

and

$c_k\approx \frac{{\hat{y}}_j}{n}$

Then

$y_j=\frac{1}{n}\sum _{k=0}^{n-1}{\hat{y}}_j{\omega }^{jk}$