====KW43: Fourier==== Stell dir vor, du hast ein Signal $x(t)=\hat{x}\cdot \sin(\omega t + \varphi) +x_0$. Du musst dieses Signal in eine Datei abspeichern. Was machst du? ===Zwei Möglichkeiten=== Ein Möglichkeit besteht darin, zu verschiedenen Zeitpunkunten $t_i$ mit einem konstanten Zeitabstand $\Delta t = t_{i}-t_{_i-1}$ (äquidistant) den Funktionswert zu bestimmen (messen) und abzuspeichern. Machen wir dazu ein Rechenbeispiel: * $\Delta t = 2.27\mu s$, dass entspricht einer Abtastfrequenz $f_s=44.1kHz$, d.h. CD Qualität. * Jeder Wert $x(t)$ wird 16 Bit gewandelt, d.h. braucht 2 Byte Speicherplatz pro Messwert. * Das Signal (Lied) dauert 3 Minuten und 40 Sekunden. Alles zusammen ergibt $$44100\frac{\text{Sample}}{sec.}\cdot \frac{2\;Byte}{\text{Sample}}\cdot 220\sec.=19.4 MByte$$ Eine andere Möglichkeit wäre: * Amplitude abspeichern ergibt 2 Byte * Phasenlange abspeichern ergibt 2 Byte * Kreisfrequenz abspeichern ergibt 2 Byte * Startzeitpunkt und Endzeitpunkt abspeichern ergibt 2 mal 2 Byte, also 4 Byte Alles zusammen ergibt dies $$10\; Byte$$ Speicherplatz und dies bei mit einer viel höheren Auflösung, da eine Sinusfunktion eine beliebige Auflösung hat! Die zweite Möglichkeit braucht viel weniger Speicherplatz und ist daher zu bevorzugen. ===Bemerkungen=== * Bei der ersten Möglichkeit haben wir Funktionswerte im **Zeit**bereich abgespeichert. * Bei der zweiten Möglichkeit haben wir einen Funktionswert im **Frequenz**bereich abgespeichert. ===2-$\pi$-periodische Funktionen=== Mit den Basisfunktionen $\sin$ und $\cos$ lässt sich ein reelles trigonometrisches Polynom $T_n$ definieren. Es gilt: $$T_n(t)=\frac{a_0}{2}+\sum_{k=1}^n \left(a_k\cos(kt)+b_k\sin(kt) \right) $$ Mit den reellen Fourierkoeffizienten $$a_k=\frac{1}{\pi}\int_0^{2\pi}T_n(t)cos(kt)dt, \qquad k=0,1,...,n $$ und $$b_k=\frac{1}{\pi}\int_0^{2\pi}T_n(t)sin(kt)dt, \qquad k=1,2,...,n $$ Es lässt sich zeigen, dass mit einem trigonometrischen Polynom $T_n(t)$ eine stetig differenzierbare $2\pi$-periodische Funktion $f(t)$ beliebig genau approximiert werden kann. D.h. $$T_n(t)\approx f(t)$$ für den Grenzübergang gilt sogar Gleichheit, d.h. $$ f(t)=\lim_{n\to\infty}T_n(t)$$ Eine Begründung für die obigen Aussagen liefern die Orthogonalitätsbeziehungen. ====Orthogonalitätsbeziehungen==== Es sei $m,n\in\mathbb{Z}$ und $a\in\mathbb{R}$, dann gelten folgende Orthogonalitätsbeziehungen: \begin{eqnarray} (1)&\qquad \frac{1}{2\pi}\int_a^{a+2\pi}\exp(imt)\exp(-int)dt & = &\begin{cases} 0, \quad \text{falls }m\neq n\\ 1, \quad \text{falls } m=n\end{cases} \\ (2)&\qquad \frac{1}{\pi}\int_a^{a+2\pi}\sin(mt)\sin(nt)dt & = &\begin{cases} 0, \quad \text{falls }m\neq n\\ 1, \quad \text{falls } m=n\end{cases} \\ (3)&\qquad \frac{1}{\pi}\int_a^{a+2\pi}\cos(mt)\cos(nt)dt & = &\begin{cases} 0, \quad \text{falls }m\neq n\\ 1, \quad \text{falls } m=n \\ 2, \quad \text{falls } m=n=0 \end{cases} \\ (4)&\qquad \int_a^{a+2\pi}\cos(mt)\sin(nt)dt & = & 0 \end{eqnarray} **Aufgabe 1** Beweise min. eine dieser vier Aussagen. Dafür brauchst du die Additionstheoreme. \begin{eqnarray} (1) & \qquad\sin(x+y) & = & \sin(x)\cos(y)+\sin(y)\cos(x) \\ (2) & \qquad\sin(x-y) & = & \sin(x)\cos(y)-\sin(y)\cos(x) \\ (3) & \qquad\cos(x+y) & = & \cos(x)\cos(y)-\sin(x)\sin(y) \\ (4) & \qquad\cos(x-y) & = & \cos(x)\cos(y)+\sin(x)\sin(y) \end{eqnarray} ====Fourier Koeffizienten==== Mit den Orthogonalitätsbeziehungen lässt sich die Korrektheit der obigen Definition der Fourierkoeffizienten $a_k$ und $b_k$ beweisen. Wir setzen ein und rechnen nach. \begin{eqnarray} a_k & = & \frac{1}{\pi}\int_0^{2\pi}T_n(t)\cos(kt)dt \\ & = & \frac{1}{\pi}\int_0^{2\pi}\left( \frac{a_0}{2}+\sum_{m=1}^n \left(a_m\cos(mt)+b_m\sin(mt) \right) \right)\cos(kt)dt\\ & & …\\ & = &a_k \end{eqnarray} und \begin{eqnarray} b_k & = & \frac{1}{\pi}\int_0^{2\pi}T_n(t)\sin(kt)dt \\ & = & \frac{1}{\pi}\int_0^{2\pi}\left( \frac{a_0}{2}+\sum_{m=1}^n \left(a_m\cos(mt)+b_m\sin(mt) \right) \right)\sin(kt)dt\\ & & …\\ & = &b_k \end{eqnarray} **Aufgabe 2** Rechne $a_k$ vollständig durch. ====Anwendung Datenkomprimierung von Linienzeichnungen==== **Aufgabe 3** Analysiere folgendes Programm. Was ist neu? from gpanel import * import math import cmath import time def onMousePressed(x, y): move(x,y) def onMouseDragged(x, y): draw(x,y) Koordinaten.append([x,y]) f.write(str(x) + "," + str(y) + "\n") makeGPanel(0,100,0,100, mousePressed = onMousePressed, mouseDragged = onMouseDragged) nameD=time.strftime("Daten_%Y_%m_%d_%H_%M_%S.txt") nameF=time.strftime("Fourier_%Y_%m_%d_%H_%M_%S.txt") Koordinaten=[] f=open(nameD,"w") fopen=1; while fopen==1: key = getKeyCodeWait() if key==27: f.close() fopen=0 print("Daten erfasst") ===Konventionen und Anpassungen für die Datenkomprimierung=== Sei $f$ eine 1-periodische Funktion, welche unser Bild beschreibt. $$ f: \; \left[0,1\right] \; \rightarrow \; \mathbb{C}, \quad t \;\mapsto z=x+i\cdot y $$ D.h. wir fassen die Bildpunkte $P(x|y)$ als Punkte in der komplexen Zahlenebene auf. Der erste Punkt $P_0(x_0|y_0)$ ist $f(0)=x_0+i\cdot y_0$, der letzte Punkt $P_n(x_n|y_n)$ ist $f(1)=x_n+i\cdot y_n$, dazwischen wird linear interpoliert, d.h. mit $$\Delta t = \frac{1}{n-1}$$ folgt dann für ein $k\in \{1,2,3,...,n\}$, dass $P_k(x_k|y_k)$ als $f((k-1)\Delta t)=x_k+i\cdot y_k$ interpretiert wird. Wir wollen unser $f$ welches wir nun anhand von einer endlichen Anzahl von Punkten kennen mit einem komplexen Fourierreihe approximieren, darstellen. $$f(t)=\sum_{k=-\infty}^{\infty}c_k \cdot e^{ikt} \approx \sum_{k=-n}^{n}c_k \cdot e^{ikt}$$ Für den komplexen Fourierkoeffizienten $c_k$ gilt: $$c_k=\frac{1}{2\pi}\int_0^{2\pi} f(t)\cdot e^{-ikt}dt $$ Aufgrund unserer Anpassung, d.h. weil $f$ 1-periodisch ist ergibt sich folgende Vereinfachung. $$c_k=\int_0^1 f(t)\cdot e^{-2\pi ikt}dt $$ Das Integral berechnen wir über eine "Riemann"-Summe, d.h. $$c_k=\int_0^1 f(t)\cdot e^{-ikt}dt \approx \sum_{j=0}^{n-1}f(j\cdot \Delta t)\cdot e^{-2\pi ikj\cdot \Delta t}\cdot \Delta t$$ **Aufgabe 4** Ergänze das obige Programm so, dass * die komplexen Fourierkoeffizienten $c_k$ berechnet werden und * diese in einem File abgespeichert werden. Pro Zeile soll nur ein Fourierkoeffizient stehen.