MATH 414 Lecture 23

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

Discrete Fourier Transform

Recall that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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

• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_j = f \left( \frac{2\pi}{n} \, j \right)}
• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \omega = \mathrm{e}^{ \frac{2\pi}{n} \, i}}
• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \overline{\omega} = \mathrm{e}^{-\frac{2\pi}{n} \, i}}
• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \hat{y}_k = \sum_{j=0}^{n-1} y_j \, \overline{\omega}^{j\,k}} (this is the fourier transform)

Then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c_k = \frac{1}{n} \, \hat{y}_k}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \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{align}}

Properties

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \hat{y}_k = \sum_{j=0}^{n-1} y_j \, \overline{\omega}^{j\,k}}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \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{align}}

Then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \hat{y}_{k+n} = \hat{y}_k} implies Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \hat{y}_k} is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} -periodic. What about Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_j}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} y_{j+n} &= \frac{1}{n} \, \sum_{j=0}^{n-1} \hat{y_k} \, \omega^{k \, \left( j+n \right)} &= y_j \end{align}}

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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \hat{f}} .

Connection with Fourier Transforms

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \hat{f}(\lambda) = \frac{1}{\sqrt{2\pi}} \, \int_{-\infty}^{\infty} f(t) \, \mathrm{e}^{-i \, \lambda \, t} \,\mathrm{d}t}

Suppose that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(t) = 0} for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t \not\in \left[ a,b \right]} , and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(a) = f(b)} .

Then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \theta = \frac{2\pi \, (t-a}{b-a}} . Then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \theta(a) = 0} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \theta(b) = 2\pi} with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{d}\theta = \frac{2\pi}{b-a}\,\mathrm{d}t} .

Then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(\theta) = f \left( a + \frac{b-a}{2\pi} \, \theta \right)}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \eta = \frac{b-a}{2\pi} \, \lambda}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \eta} by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} :

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c_k = \hat{f} \left( \frac{2\pi}{b-a} \, k \right)} . We have Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c_k \approx \frac{1}{n} \hat{y}_k} :

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \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{align}}

Where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_j} is a sample of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(t)} at Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t_j = a + \frac{b-a}{n} \, j} . The spacing between samples is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T = \frac{b-a}{n}} , and the Nyquist frequency is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Delta \lambda = \frac{2\pi}{b-a}} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T = \frac{b-a}{n}} .