MATH 414 Lecture 23

« previous | Monday, March 17, 2014 | next »

Discrete Fourier Transform

Recall that $c_{k}={\frac {1}{2\pi }}\,\int _{0}^{2\pi }f(t)\,\mathrm {e} ^{-i\,k\,t}\,\mathrm {d} t\approx {\frac {1}{n}}\,\sum _{j=0}^{n-1}f\left({\frac {2\pi }{n}}\,j\right)\,\mathrm {e} ^{-{\frac {2\pi }{n}}\,i\,j\,k}$

For simplicity, we write

• $y_{j}=f\left({\frac {2\pi }{n}}\,j\right)$
• $\omega =\mathrm {e} ^{{\frac {2\pi }{n}}\,i}$
• ${\overline {\omega }}=\mathrm {e} ^{-{\frac {2\pi }{n}}\,i}$
• ${\hat {y}}_{k}=\sum _{j=0}^{n-1}y_{j}\,{\overline {\omega }}^{j\,k}$ (this is the fourier transform)

Then $c_{k}={\frac {1}{n}}\,{\hat {y}}_{k}$

${\begin{aligned}{\mathcal {F}}_{n}\left[y\right]_{k}&=\sum _{j=0}^{n-1}y_{j}\,{\overline {\omega }}^{j\,k}\\{\mathcal {F}}_{n}^{-1}\left[{\hat {y}}\right]_{j}&={\frac {1}{n}}\sum _{k=0}^{n-1}{\hat {y}}_{k}\,\omega ^{j\,k}\end{aligned}}$

Properties

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

${\begin{aligned}{\hat {y}}_{k+n}&=\sum _{j=0}^{n-1}y_{j}\,{\overline {\omega }}^{j\,\left(k+n\right)}\\&=\sum _{j=0}^{n-1}y_{j}\,{\overline {\omega }}^{j\,k}\,{\cancel {{\overline {\omega }}^{j\,n}}}\\&={\hat {y}}_{k}\end{aligned}}$

Then ${\hat {y}}_{k+n}={\hat {y}}_{k}$ implies ${\hat {y}}_{k}$ is $n$-periodic. What about $y_{j}$

${\begin{aligned}y_{j+n}&={\frac {1}{n}}\,\sum _{j=0}^{n-1}{\hat {y_{k}}}\,\omega ^{k\,\left(j+n\right)}&=y_{j}\end{aligned}}$

Therefore $y_{j}$ is $n$-periodic.

Sequence

Let $S_{n}$ be the set of all $n$-periodic sequences $s=\left\{\ldots ,x_{-3},x_{-2},x_{-1},x_{0},x_{1},x_{2},x_{3},\ldots \right\}$ with $x_{\ell }=x_{\ell +n}$ is an $n$-periodic sequence.

We take a "template sample" that is $n$ "positions" wide. The entire sequence is nothing more than this template repeated indefinitely in ether direction.

... -9 -8 -7 -6 -5 -4 -3 -2 -1  0  1  2  3  4  5  6  7  8  9 ...
...  a  b  c  d  e  a  b  c  d  e  a  b  c  d  e  a  b  c  d ...
...  `-----------'  `-----------'  `-----------'  `--------- ...

Suppose $y_{j}\in S_{n}$, then $y_{j+n}=y_{j}$ and ${\hat {y}}_{k+n}={\hat {y}}_{k}$

Therefore the discrete fourier transform ${\mathcal {F}}_{n}:S_{n}\to S_{n}$ is linear:

${\begin{aligned}{\mathcal {F}}_{n}\left[y+z\right]&={\mathcal {F}}_{n}\left[y\right]+{\mathcal {F}}_{n}\left[z\right]\\{\mathcal {F}}_{n}\left[\alpha \,y\right]&=\alpha \,{\mathcal {F}}_{n}\left[y\right]\end{aligned}}$

The inverse discrete fourier transform ${\mathcal {F}}_{n}^{-1}\left[{\hat {y}}\right]_{j}$ is also linear.

Hence ${\mathcal {F}}_{n}$ and ${\mathcal {F}}_{n}^{-1}$ are linear transformations from $S_{n}$ to $S_{n}$.

Shifts

If $(\ldots ,y_{-1},y_{0},y_{1},y_{2},\ldots )\in S_{n}$, then let $z_{j}:=y_{j+1}$ (left translation of $y$ by one unit)

${\mathcal {F}}_{n}\left[z\right]_{k}=\omega ^{k}\,{\mathcal {F}}\left[y\right]_{k}$ (or equivalently ${\hat {z}}_{k}=\omega ^{k}\,{\hat {y}}_{k}$.

We saw a similar behavior in continuous fourier transforms: multiplications in the time domain $f$ translate to multiplications by a phase change constant in the frequency domain ${\hat {f}}$.

Connection with Fourier Transforms

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

Suppose that $f(t)=0$ for $t\not \in \left[a,b\right]$, and $f(a)=f(b)$.

Then ${\hat {f}}(\lambda )={\frac {1}{\sqrt {2\pi }}}\,\int _{a}^{b}f(t)\,\mathrm {e} ^{-i\,\lambda \,t}\,\mathrm {d} t$.

Perform a change of variables. Let $\theta ={\frac {2\pi \,(t-a}{b-a}}$. Then $\theta (a)=0$ and $\theta (b)=2\pi$ with $\mathrm {d} \theta ={\frac {2\pi }{b-a}}\,\mathrm {d} t$.

Then ${\hat {f}}(\lambda )={\frac {b-a}{{\sqrt {2\pi }}\cdot 2\pi }}\,\int _{0}^{2\pi }f\left(a+{\frac {b-a}{2\pi }}\,\theta \right)\,\mathrm {e} ^{-i\,\lambda \left({\frac {b-a}{2\pi }}\,\theta +a\right)}\,\mathrm {d} \theta$

Let $F(\theta )=f\left(a+{\frac {b-a}{2\pi }}\,\theta \right)$

${\hat {f}}(\lambda )={\frac {\mathrm {e} ^{-i\,\lambda \,a}}{{\sqrt {2\pi }}\cdot 2\pi }}\,\left(b-a\right)\,\int _{0}^{2\pi }F(\theta )\,\mathrm {e} ^{-i\,\lambda \,{\frac {b-a}{2\pi }}\,\theta }\,\mathrm {d} \theta$

Let $\eta ={\frac {b-a}{2\pi }}\,\lambda$

${\hat {f}}\left({\frac {2\pi }{b-a}}\,\eta \right)=\mathrm {e} ^{-i\,\lambda \,a}\,\left({\frac {b-a}{2\pi }}\right)\,{\frac {1}{\sqrt {2\pi }}}\,\int _{0}^{2\pi }F(\theta )\,\mathrm {e} ^{i\,\eta \,\theta }\,\mathrm {d} \theta$

Replace $\eta$ by $k$:

${\hat {f}}\left({\frac {2\pi }{b-a}}\,k\right)=\left({\frac {b-a}{2\pi }}\right)\,{\frac {1}{\sqrt {2\pi }}}\,\int _{0}^{2\pi }F(\theta )\,\mathrm {e} ^{i\,k\,\theta }\,\mathrm {d} \theta$

Something is wrong with the following

Observe that the integral factor is the Fourier Series Coefficient. Let $c_{k}={\hat {f}}\left({\frac {2\pi }{b-a}}\,k\right)$. We have $c_{k}\approx {\frac {1}{n}}{\hat {y}}_{k}$:

${\begin{aligned}{\hat {y}}_{k}=\sum _{j=0}^{n-1}y_{j}\,{\overline {\omega }}^{j\,k}&=\sum _{j=0}^{n-1}F\left({\frac {2\pi }{n}}\,j\right)\,{\overline {\omega }}^{j\,k}\\&=\sum _{j=0}^{n-1}f\left(a+{\frac {b-a}{2\pi }}\cdot {\frac {2\pi }{n}}\,j\right)\,{\overline {\omega }}^{j\,k}\\&=\sum _{j=0}^{n-1}f\left(a+{\frac {b-a}{n}}\,j\right)\,{\overline {\omega }}^{j\,k}\\&=y_{j}\end{aligned}}$

Where $y_{j}$ is a sample of $f(t)$ at $t_{j}=a+{\frac {b-a}{n}}\,j$. The spacing between samples is $T={\frac {b-a}{n}}$, and the Nyquist frequency is $T^{-1}$.

The professor realized the mistake here and promised to fix it next lecture

After some manipulation, we come up with a function with two parameters:

$\Delta \lambda ={\frac {2\pi }{b-a}}$ and $T={\frac {b-a}{n}}$.