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|\geq \Omega$.

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

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

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

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

Definition:

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

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

${\begin{aligned}{\hat {f}}(\omega )&=\sum _{n=-\infty }^{\infty }c_{n}\,\mathrm {e} ^{{\frac {i\,\pi \,n}{\Omega }}\,\omega }\\c_{n}&={\frac {1}{2\Omega }}\,\int _{-\Omega }^{\Omega }{\hat {f}}(\omega )\,\mathrm {e} ^{-{\frac {i\,\pi \,n\,\omega }{\Omega }}}\,\mathrm {d} \omega \\&={\frac {\sqrt {2\pi }}{2\Omega }}\,{\frac {1}{\sqrt {2\pi }}}\,\int _{-\Omega }^{\Omega }{\hat {f}}(\omega )\,\mathrm {e} ^{i\,\left(-{\frac {n\,\pi }{\Omega }}\right)\omega }\,\mathrm {d} \omega \\&={\frac {\sqrt {2\pi }}{2\Omega }}\,f\left(-{\frac {n\,\pi }{\Omega }}\right)\\\end{aligned}}$

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

${\begin{aligned}{\hat {f}}&=\sum _{n=-\infty }^{\infty }c_{n}\,\mathrm {e} ^{\frac {i\,n\,\pi \,\omega }{\Omega }}\\&=\sum _{j=-\infty }^{\infty }c_{-j}\,\mathrm {e} ^{-{\frac {i\,j\,\pi \,\omega }{\Omega }}}\\&=\sum _{j=-\infty }^{\infty }{\frac {\sqrt {2\pi }}{2\Omega }}\,f\left({\frac {j\,\pi }{\Omega }}\right)\,\mathrm {e} ^{-{\frac {i\,j\,\pi \,\omega }{\Omega }}}\end{aligned}}$

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

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

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=-\infty }^{\infty }c_{n}\,\mathrm {e} ^{i\,n\,t}$, where $c_{n}={\frac {1}{2\pi }}\,\int _{0}^{2\pi }f(t)\,\mathrm {e} ^{-i\,n\,t}$, 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 }}\,\int _{0}^{2\pi }f(t)\,\mathrm {e} ^{-i\,n\,t}\,\mathrm {d} t$, so we need a quadrature formula to approximate

$\int _{a}^{b}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:

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

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}$:

$\int _{a}^{b}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 }}\,\int _{0}^{2\pi }f(t)\,\mathrm {e} ^{-i\,k\,t}\,\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}}\,j\,k}={\frac {1}{n}}\,\sum _{j=0}^{n-1}y_{j}={\overline {\omega }}^{k\,j}$

Where ${\overline {\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}\,{\overline {\omega }}^{j\,k}$

and

$c_{k}\approx {\frac {{\hat {y}}_{j}}{n}}$

Then

$y_{j}={\frac {1}{n}}\,\sum _{k=0}^{n-1}{\hat {y}}_{j}\,\omega ^{j\,k}$