MATH 414 Lecture 22

« previous | Friday, March 7, 2014 | next »

Discrete Fourier Transform

Find / approximate

Failed to parse (unknown function "\k"): {\displaystyle c_k = \frac{1}{2\pi} \, \int_{0}^{2\pi} f(t) \, \mathrm{e}^{-i \, \k \, t} \,\mathrm{d}t}

given

$y_{j}=f\left({\frac {2\pi \,j}{n}}\right)$

where $n$ is the number of samples, and $f$ is $2\pi$-periodic

Use trapezoial rule:

$c_{k}\approx {\frac {1}{n}}\,\sum _{j=0}^{n-1}y_{i}\,{\overline {\omega }}^{j\,k}$, where $\omega =\mathrm {e} ^{\frac {2\pi \,i}{n}}$

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

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

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

Lemma. $1+z+z^{2}+\dots +z^{n-1}={\begin{cases}n&z=1\\{\frac {z^{n}-1}{z-1}}&z\neq 1\end{cases}}$

Proof.

quod erat demonstrandum

Let $z=\mathrm {e} ^{\frac {2\pi \,i\,\ell }{n}}$.

If $\ell \neq 0$, then $z\neq 1$.

Hence $\mathrm {e} ^{\frac {2\pi \,i\,\ell }{n}}=1$ if and only if $\ell$ is a multiple of $n$

but in the range $\left[-(n-1),n-1\right]$, only $\ell =0$ is a multiple of $n$.

Therefore $\sum _{k=0}^{n-1}\left(\mathrm {e} ^{\frac {2\pi \,i\,\ell }{n}}\right)^{k}={\begin{cases}n&\ell =0\\0&\ell \neq 0\end{cases}}$

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

Proof. Let $Y_{j}={\frac {1}{n}}\,\sum _{k=0}^{n-1}{\hat {y}}_{k}\,\omega ^{j\,k}$ (don't know it's equal to $y_{j}$, but we'll show it.)

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

${\begin{aligned}Y_{j}&={\frac {1}{n}}\,\sum _{k=0}^{n-1}\left(\sum _{\ell =0}^{n-1}y_{\ell }\,{\overline {\omega }}^{\ell \,k}\right)\,\omega ^{j\,k}\\&={\frac {1}{n}}\,\sum _{\ell =0}^{n-1}y_{\ell }\left(\sum _{k=0}^{n-1}{\overline {\omega }}^{\ell \,k}\,\omega ^{j\,k}\right)\\&={\frac {1}{n}}\,\sum _{\ell =0}^{n-1}y_{\ell }\,\sum _{k=0}^{n-1}z^{k}\\&={\frac {1}{n}}\,\sum _{\ell =0}^{n-1}y_{\ell }\,{\begin{pmatrix}n&z=1\\0&z\neq 1\end{pmatrix}}\\&={\frac {1}{n}}\,n\,y_{j}\\&=y_{j}\end{aligned}}$

BUT $z=\mathrm {e} ^{\frac {2\pi \,i\,(\ell -j)}{n}}$

$-(n-1)\leq \ell -j\leq n-1$

Therefore $z=0$ if $j\neq \ell$ and $z=1$ if $j=\ell$.

quod erat demonstrandum

$S_{n}$ is a $n$-periodic sequence: $y\in S_{n}$ implies $y_{j}=y_{j+n}$