MATH 414 Lecture 32

« previous | Monday, April 7, 2014 | next »

End Exam 2 content

Exam Review

Sampling Theorem

given band-limited 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)} , the support of ${\hat {f}}$ is a subset of $\left[-\Omega ,\Omega \right]$.

• $\Omega$ is the angular frequency (in radians / sec)
• ${\frac {\Omega }{2\pi }}$ is the natural frequency, the highest frequency in the singal (in hertz)
• In the theorem below, 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 \frac{\pi}{\Omega}} is the sampling interval (in seconds; time between samples)
• 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 \frac{\omega}{\pi}} (twice the natural frequency) is the Nyquist rate

Theorem. 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 \sum_{j=-\infty}^\infty f \left( \frac{j\,\pi}{\Omega} \right) \, \frac{\sin{ \left( \Omega \, t - j \, \pi \right)}}{\Omega \, t - j \, \pi}}

Proof. [omitted]

quod erat demonstrandum

Sampling at anything lower than the nyquist frequency results in lost information (not enough to see the full ups and downs of the waves)

Discrete Fourier Transforms of Periodic Sequnecs

Given two 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 sequences 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, z \in S_n} , show 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 \hat{z}_k = w^k \, \hat{y}_k} , 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 w = \mathrm{e}^{ \frac{2\pi\,i}{n} }}

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{w}^{j\,k} \\ \hat{z}_k &= \sum_{j=0}^{n-1} z_j \, \overline{w}^{j\,k} \\ &= \sum_{j=0}^{n-1} y_{k+1} \, \overline{w}^{j\,k} \\ &= \sum_{\ell=1}^{n} y_{\ell} \, \overline{w}^{(\ell-1)\,k} \\ &= \overline{w}^{-k} \, \sum_{\ell=1}^n y_{\ell} \, \overline{w}^{\ell \, k} \\ &= w^{k} \, \sum_{\ell=1}^n \, y_{\ell} \, \overline{w}^{\ell \, k} \\ &= w^{k} \, \left( \sum_{\ell = 1}^{n-1} \, y_{\ell} \, \overline{w}^{\ell \, k} + y_n \, \overline{w}^{n \, k} \right) \\ &= w^{k} \, \left( \sum_{\ell = 1}^{n-1} \, y_{\ell} \, \overline{w}^{\ell \, k} + y_0 \cdot 1 \right) \\ &= w^{k} \, \sum_{\ell = 0}^{n-1} \, y_{\ell} \, \overline{w}^{\ell \, k} \\ &= w^{k} \, \hat{y}_k \end{align}}

Proof of Haar Decomposition

Given 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_j = \sum_{k = -\infty}^\infty a_k^j \, \phi(2^j \, x - k)} , the projection 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_j} onto 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 V_{j-1}} is given 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 \mathrm{proj}_{V_{j-1}}{(f_j)} = \sum_{k=-\infty}^{\infty} a_k^{j-1} \, \phi(2^{j-1} \, x - k)}

Prove 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 a_k^{j-1} = \frac{1}{2} \, \left( a_{2k}^j + a_{2k+1}^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 \begin{align} a_k^{j-1} &= 2^{j-1} \, \int_{-\infty}^\infty f_j (x) \, \phi(2^{j-1} \, x - k) \, \mathrm{d}x \\ \phi(2^{j-1} \, x - k) &= \phi(2(2^{j-1} \, x - k)) + \phi(2(2^{j-1} \, x - k) - 1) \\ &= \phi(2^j \, x - 2 k) + \phi(2^j \, x - 2k - 1) \\ &= 2^{j-1} \, \int_{-\infty}^\infty f_j(x) \, \phi(2^j \, x - 2k) \,\mathrm{d}x + 2^{j-1} \, \int_{-\infty}^{\infty} f_j(x) \, \phi(2^j\,x - 2k-1) \,\mathrm{d}x \\ &= 2^{j-1} \, \left( 2^{-j} a_{2k}^j \right) + 2^{j-1} \, \left( 2^{-j} \, a_{2k+1}^j \right) \\ &= 2^{-1} \, \left( a_{2k}^j + a_{2k+1}^j \right) \end{align}}

Fast Fourier Transform

Given data 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 = \left\{ y_0, y_1, y_2, \ldots, y_{2N-1} \right\}} , 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 N = 2^{L-1}} 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 L \in \mathbb{N}} .

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 \mathcal{F}_{2N}\left[ y \right] = \mathcal{F}_{N}\left[ y_0, y_2, \ldots, y_{2N-2} \right]_k + \overline{W}^k \, \mathcal{F}_N \left[ y_1, y_3, \ldots, y_{2N-1} \right]}

How many multiplications does it take to compute 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 \mathcal{F}_{2N}} ?

• 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_L = 2K_{L-1} + 2^L}
• 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_L \sim N \, \log{N}}