prb8.tex (6470B)
1 \include{preamble.tex} 2 3 \begin{document} 4 \maketitle 5 \tableofcontents 6 7 \section{Sheet 8} 8 \subsection{Finite Discrete Fourier Transform (FDFT)} 9 Consider the vector $\begin{pmatrix}a & b & c & d\end{pmatrix}^T \in 10 \mathbb{C}^4$ with a FDFT $\begin{pmatrix}A & B & C & D\end{pmatrix}^T$. We 11 can show that the vector 12 \begin{align} 13 \begin{pmatrix}a & 0 & b & 0 & c & 0 & d & 0\end{pmatrix}^T, 14 \end{align} 15 has the FDFT of 16 \begin{align} 17 \frac{1}{2}\begin{pmatrix}A & 0 & B & 0 & C & 0 & D & 0\end{pmatrix}^T. 18 \end{align} 19 For the $N=4$, $n\in\{0,\dots,3\}$ the coefficients $a, b, c, d$ are denoted in 20 $f[n]$. The FDFT is 21 \begin{align} 22 \hat{f}[k] &= \frac{1}{4} * \sum_{n=0}^3 f[n] e^{-2\pi i \frac{n}{4}k} \\ 23 &=\frac{1}{4}\left( 24 a + be^{-\pi i \frac{k}{2}} 25 + ce^{-\pi i k}+ de^{-\frac{3\pi i k}{2}} 26 \right) = \\ 27 (&=\begin{pmatrix}A & B & C & D\end{pmatrix}^T) 28 \end{align} 29 for $k \in \{0,\dots, 3\}$ accordingly. For the $N=8$, $\mathbb{C}^8$ case 30 we have $f_2[n]$ for $n \in \{0,\dots 7\}$, 31 \begin{align} 32 \hat{f}_2[k] &= \frac{1}{8} * \sum_{n=0}^7 f_2[n] e^{-2\pi i \frac{n}{8}k} \\ 33 &=\frac{1}{2}\frac{1}{4}\left( 34 a + be^{-\pi i \frac{k}{2}} 35 + ce^{-\pi i k}+ de^{-\frac{3\pi i k}{2}} 36 \right) = \\ 37 (&=\frac{1}{2}\begin{pmatrix}A & B & C & D & A & B & C & D\end{pmatrix}^T) 38 \end{align} 39 for $k \in \{0,\dots, 7\}$ accordingly. We may generalize now for 40 $\mathbb{C}^{4N}$, and the sequence for $a, b, c, d, 0$ represented by the 41 function $g[n]$ for $n \in \{0,\dots, 4N-1\}$, 42 \begin{align} 43 g[n] =\begin{cases} 44 f[n] \qquad n\in \{0, N, 2N, 3N\}\\ 45 0 \qquad \text{else} 46 \end{cases}. 47 \end{align} 48 Now we can compute the FDFT for $k \in \{0,\dots, 4N-1\}$ 49 \begin{align} 50 \hat{g}[k] &= \frac{1}{4N}\sum_{n=0}^{4N-1} g[n]e^{-2\pi i 51 \frac{n}{4N}k}\\ 52 &=\frac{4}{N}\sum_{n=0}{3}f[n]e^{-2\pi i \frac{n}{4}k}\\ 53 &=\frac{1}{N}\left(\frac{1}{4}\sum_{n=0}^3 f[n] e^{-2\pi i 54 \frac{n}{4}k} \right) \\ 55 &= \frac{1}{N} \underbrace{\begin{pmatrix}A & B & C & D & \dots & 56 \dots & A & B & C & D\end{pmatrix}^T)}_{\text{$4N$ entries, $N$ 57 sequences}}. 58 \end{align} 59 \subsection{More FDFT} 60 Consider the discrete complex exponential with frequency of $1Hz$ in 61 $\mathbb{C}^8$, for $n \in \{0, \dots , 7\}$, 62 \begin{align} 63 \exp[n] = e^{2\pi i n/8}. 64 \end{align} 65 The FDFT for $k \in \{0, \dots, 7\}$ is 66 \begin{align} 67 \hat{\exp}[k] &= \frac{1}{8}\sum_{n=0}^7 e^{2\pi i \frac{n}{8}}e^{-2\pi i 68 n \frac{k}{8}} \\ 69 &= \frac{1}{8} \sum_{n=0}^7e^{-2\pi i (k-1)\frac{n}{8}}\\ 70 &= 71 \begin{cases} 72 1\quad k=1\\ 73 0 \qquad k\neq 1 74 \end{cases}. 75 \end{align} 76 \begin{figure}[H] 77 \centering 78 \includegraphics[width=0.49\textwidth]{./figures/fdft.png} 79 \includegraphics[width=0.49\textwidth]{./figures/normal.png} 80 \caption{Test in Julia} 81 \end{figure} 82 \subsection{Sampling Sinusoids} 83 Consider the following continuous signal 84 \begin{align} 85 f(t) = sin(20\pi t) + sin(40\pi t) 86 \end{align} 87 with frequencies $\omega = 2\pi \nu$, $\nu_1 = 10\ \text{Hz}$ and $\nu_2 = 20\ 88 \text{Hz}$. Sketching its Fourier transform would be something like this 89 \begin{figure}[H] 90 \centering 91 \begin{tikzpicture}[ 92 axisline/.style={very thick, -stealth}, 93 xscale = 1.5, 94 yscale = 1.5 95 ] 96 \draw[axisline] (-3,0)--(3,0) node[right]{$\nu$}; 97 \draw[axisline] (0,-1.5)--(0,1.5) node[above]{$\hat{f}$}; 98 \draw[->] (-1,0) -- (-1, -1) node[below] {$-\delta(\nu - 10)$}; 99 \draw[->] (-2,0) -- (-2, 1) node[above] {$\delta(\nu - 20)$}; 100 \draw[->] (1,0) -- (1, 1) node[above] {$\delta(\nu - 10)$}; 101 \draw[->] (2,0) -- (2, 1) node[above] {$\delta(\nu - 20)$}; 102 \end{tikzpicture} 103 \end{figure} 104 The Nyquist frequency for sampling would be 105 \begin{align} 106 \nu_{\text{Nyquist}} = 2\nu_\text{max} = 2\nu_2 = 40\ \text{Hz}, 107 \end{align} 108 If we choose $50\ \text{Hz}$ for sampling we would get aliasing with the 109 following frequencies 110 \begin{align} 111 n \cdot 50\ \text{Hz} - 20\ \text{Hz} = 30\ \text{Hz},80\ \text{Hz}, 130\ 112 \text{Hz}, \dots 113 \end{align} 114 \subsection{Short-Time Fourier Transform (STFT)} 115 The Definition of the STFT is 116 \begin{align} 117 \text{STFT}\{f\} &= S_\varphi f(\tau, \omega) = \int_\mathbb{R} f(t) 118 \overline{\text{M}_\omega \text{T}_\tau \varphi}dt \\ 119 &=\int_\mathbb{R} f(t) 120 \bar{\varphi}(t - \tau)e^{-2\pi i \omega t}\ dt \\ 121 \end{align} 122 Then we have the following identity 123 \begin{align} 124 S_\varphi(\text{T}_u\text{M}_\eta f)(x,\omega) 125 &= \int_\mathbb{R} 126 \left(\text{T}_u \text{M}_\eta f(t)\right) \bar{\varphi}(t-x) e^{-2\pi i 127 \omega t}\ dt\\ 128 &= \int_\mathbb{R} e^{2\pi i \eta(t-u)}f(t-u) e^{-2\pi i \omega 129 t}\bar{\varphi}(t-x)\ dt \qquad \text{(sub: $s = t-u$)}\\ 130 &= \int_\mathbb{R} f(s)\bar{\varphi}(s-(x-u))e^{2\pi i \eta s}e^{-2\pi i 131 \omega s} e^{-2\pi i \omega u}\ ds \\ 132 &=e^{-2\pi i \omega u}\int_\mathbb{R} f(s) \bar{\varphi}(s-(x-u))e^{-2\pi i 133 (\omega - \eta)s}\ ds\\ 134 &=e^{-2\pi i \omega u}\int_\mathbb{R} 135 f(s)\overline{ \text{M}_{(\omega-\eta)} \text{T}_{(x-u)}\varphi(s)}\ ds\\ 136 &=e^{-2\pi i \omega u} S_\varphi f\left(x-u,\ \omega -\eta\right). 137 \end{align} 138 The second identity we can show 139 \begin{align} 140 S_\varphi f(x, \omega) 141 &= \langle f, \overline{\text{M}_\omega \text{T}_x \varphi}\rangle \\ 142 &= \langle\mathcal{F} f, \mathcal{F} \overline{\text{M}_\omega \text{T}_x \varphi}\rangle \\ 143 &= \int_\xi \hat{f}(\xi)\int_t \overline{\text{M}_\omega \text{T}_x 144 \varphi}(t) e^{-2\pi i \xi t}\ dt\ d\xi \\ 145 &= \int_\xi \hat{f}(\xi)\int_t \hat{\bar{\varphi}}(t-x) e^{2\pi i \omega 146 t} e^{-2\pi i \xi t}\ dt\ d\xi \\ 147 &= \int_\xi \hat{f}(\xi)\int_t \hat{\bar{\varphi}}(t-x)e^{-2\pi i (\xi 148 -\omega)t}\ dt\ d\xi \qquad \text{sub $u=t-x$}\\ 149 &= \int_\xi \hat{f}(\xi)\int_t \hat{\bar{\varphi}}(u)e^{-2\pi i (\xi 150 -\omega)u}e^{-2\pi i (\xi -\omega)x} \ dt\ d\xi\\ 151 &= \int_\xi \hat{f}(\xi)e^{-2\pi i (\xi -\omega)x}\int_t 152 \hat{\varphi}(u)e^{-2\pi i (\xi -\omega)u} \ dt\ d\xi\\ &= e^{2\pi i 153 \omega x}\int_\xi \hat{f}(\xi) \hat{\bar{\varphi}}(\xi - \omega) e^{-2\pi 154 i \xi x}d\xi\\ 155 &= e^{2\pi i \omega x} S_{\hat{\varphi}} \hat{f}(\omega, -x). 156 \end{align} 157 % printbibliography 158 \end{document}