MATH 414 Lecture 23

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

Discrete Fourier Transform

Recall that $c_k=\frac{1}{2\pi }\underset{0}{\overset{2\pi }{\int }}f(t){\mathrm{e}}^{-ikt}\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}ijk}$

For simplicity, we write

• $y_j=f\left(\frac{2\pi }{n}j\right)$
• $\omega ={\mathrm{e}}^{\frac{2\pi }{n}i}$
• $\bar{\omega }={\mathrm{e}}^{-\frac{2\pi }{n}i}$
• ${\hat{y}}_k=\sum _{j=0}^{n-1}{y}_j\stackrel{jk}{\bar{\omega }}$ (this is the fourier transform)

Then $c_k=\frac{1}{n}{\hat{y}}_k$

$\begin{array}{rl}{{ℱ}}_n{\left[y\right]}_k& =\sum _{j=0}^{n-1}{y}_j\stackrel{jk}{\bar{\omega }}\\ {{ℱ}}_n^{-1}{\left[\hat{y}\right]}_j& =\frac{1}{n}\sum _{k=0}^{n-1}{\hat{y}}_k{\omega }^{jk}\end{array}$

Properties

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

$\begin{array}{rl}{\hat{y}}_{k+n}& =\sum _{j=0}^{n-1}{y}_j\stackrel{j(k+n)}{\bar{\omega }}\\ & =\sum _{j=0}^{n-1}{y}_j\stackrel{jk}{\bar{\omega }}\cancel{\stackrel{jn}{\bar{\omega }}}\\ & ={\hat{y}}_k\end{array}$

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

$\begin{array}{rlr}{y}_{j+n}& =\frac{1}{n}\sum _{j=0}^{n-1}\widehat{y_k}{\omega }^{k(j+n)}& =y_j\end{array}$

Therefore $y_j$ is $n$-periodic.

Sequence

Let $S_n$ be the set of all $n$-periodic sequences $s=\{\dots ,x_{-3},x_{-2},x_{-1},x_0,x_1,x_2,x_3,\dots \}$ 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 ${{ℱ}}_n:S_n\to S_n$ is linear:

$\begin{array}{rl}{{ℱ}}_n[y+z]& ={{ℱ}}_n\left[y\right]+{{ℱ}}_n\left[z\right]\\ {{ℱ}}_n\left[\alpha y\right]& =\alpha {{ℱ}}_n\left[y\right]\end{array}$

The inverse discrete fourier transform ${{ℱ}}_n^{-1}{\left[\hat{y}\right]}_j$ is also linear.

Hence ${{ℱ}}_n$ and ${{ℱ}}_n^{-1}$ are linear transformations from $S_n$ to $S_n$.

Shifts

If $(\dots ,y_{-1},y_0,y_1,y_2,\dots )\in S_n$, then let $z_j:=y_{j+1}$ (left translation of $y$ by one unit)

${{ℱ}}_n{\left[z\right]}_k={\omega }^k{ℱ}{\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 }}\underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}f(t){\mathrm{e}}^{-i\lambda t}\mathrm{d}t$

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

Then $\hat{f}(\lambda )=\frac{1}{\sqrt{2\pi }}\underset{a}{\overset{b}{\int }}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 }\underset{0}{\overset{2\pi }{\int }}f(a+\frac{b-a}{2\pi }\theta ){\mathrm{e}}^{-i\lambda (\frac{b-a}{2\pi }\theta +a)}\mathrm{d}\theta$

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

$\hat{f}(\lambda )=\frac{{\mathrm{e}}^{-i\lambda a}}{\sqrt{2\pi }\cdot 2\pi }(b-a)\underset{0}{\overset{2\pi }{\int }}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 }}\underset{0}{\overset{2\pi }{\int }}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 }}\underset{0}{\overset{2\pi }{\int }}F(\theta ){\mathrm{e}}^{ik\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{array}{rl}{\hat{y}}_k=\sum _{j=0}^{n-1}{y}_j\stackrel{jk}{\bar{\omega }}& =\sum _{j=0}^{n-1}F\left(\frac{2\pi }{n}j\right)\stackrel{jk}{\bar{\omega }}\\ & =\sum _{j=0}^{n-1}f(a+\frac{b-a}{2\pi }\cdot \frac{2\pi }{n}j)\stackrel{jk}{\bar{\omega }}\\ & =\sum _{j=0}^{n-1}f(a+\frac{b-a}{n}j)\stackrel{jk}{\bar{\omega }}\\ & =y_j\end{array}$

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:

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