diff options
Diffstat (limited to '')
42 files changed, 1371 insertions, 618 deletions
diff --git a/buch/papers/clifford/10_Quaternionen.tex b/buch/papers/clifford/10_Quaternionen.tex index c2b3b8c..375c6e7 100644 --- a/buch/papers/clifford/10_Quaternionen.tex +++ b/buch/papers/clifford/10_Quaternionen.tex @@ -8,20 +8,20 @@ Wie die komplexen Zahlen eine Erweiterung der reellen Zahlen sind, sind die Quaternionen eine Erweiterung der komplexen Zahlen für den dreidimensionalen Raum. Sie haben, wie die komplexen Zahlen, eine dreh-streckende Eigenschaft. Sie finden beispielsweise in der Computergraphik und in der Robotik Anwendung. -Die Quaternionen werden so definiert. +Die Quaternionen \begin{align} q = w + xi + yj + zk \quad w,x,y,z \in \mathbb{R}\enspace q \in \mathbb{H} \end{align} -Eine Drehstreckung wird dabei mit dieser Formel erreicht. +können dabei eine Drehstreckung mit dieser Formel erreichen \begin{align} \label{QuatRot} \begin{split} &v'' = qvq^{-1};\quad q,v,q^{-1} \in \mathbb{H}\\ &\operatorname{Re}(q) = \operatorname{Re}(q^{-1})\quad \operatorname{Im}(q) = -\operatorname{Im}(q^{-1}) \end{split} \end{align} -Man könnte sich nun fragen wieso es drei imaginäre Einheiten $i,j,k$ gibt und nicht zwei, was doch näherliegender wäre. Der Grund liegt darin, weil es in der dritten Dimension 3 Drehachsen gibt, anstatt nur eine. In der geometrischen Algebra ist es leicht herauszufinden wie viele Imaginärteile für jede weitere Dimension existieren. Dabei muss man nur die Anzahl der unabhängigen Bivektoren ermitteln. In der vierten Dimension würden es beispielsweise durch alle Vektorkombinationen von $\mathbf{e}_1, \mathbf{e}_2,\mathbf{e}_3, \mathbf{e}_4$ insgesamt 8 Bivektoren existieren (Nicht 16, da $\mathbf{e}_{ij} = -\mathbf{e}_{ji}$ nicht unabhängig voneinander sind). +Auffallend ist hier schon die Ähnlichkeit zu dem Kapitel Rotation. Man könnte sich nun fragen wieso es drei imaginäre Einheiten $i,j,k$ gibt und nicht zwei, was doch näherliegender wäre. Der Grund liegt darin, weil es in der dritten Dimension drei Drehachsen gibt, anstatt nur eine. Wie im Kapitel Rotation beschrieben können wir auch hier die drei Drehungen durch Linearkombinationen von drei Bivektoren beschreiben. In der geometrischen Algebra ist es leicht herauszufinden wie viele Imaginärteile für jede weitere Dimension existieren. Dabei muss man nur die Anzahl der unabhängigen Bivektoren ermitteln. In der vierten Dimension würden es beispielsweise durch alle Vektorkombinationen von $\mathbf{e}_1, \mathbf{e}_2,\mathbf{e}_3, \mathbf{e}_4$ insgesamt 8 Bivektoren existieren (Nicht 16, da $\mathbf{e}_{ij} = -\mathbf{e}_{ji}$ nicht unabhängig voneinander sind). -Leider haben wir nun bei der Darstellung der Quaternionen ein kleines Problem. Wir bräuchten insgesamt vier Achsen. Drei für die imaginären Einheiten und eine für die reelle Einheit. Ein weiterer Nachteil in visueller Hinsicht entsteht beim Anwenden eines Quaternion auf einen Vektor. Sie befinden sich nicht im gleichen Raum und müssen zuerst ineinander umgewandelt werden, um damit zu rechnen, wie man bei $v \in \mathbb{H}$ in der Formel (\ref{QuatRot}) sieht. +Ohne die geometrische Algebra, haben wir jetzt aber leider ein kleines Problem. Für die Darstellung der Quaternionen bräuchten wir insgesamt vier Achsen. Drei für die imaginären Einheiten und eine für die reelle Einheit. Ein weiterer Nachteil in visueller Hinsicht entsteht beim Anwenden eines Quaternion auf einen Vektor. Sie befinden sich nicht im gleichen Raum und müssen zuerst ineinander umgewandelt werden, um damit zu rechnen, wie man bei $v \in \mathbb{H}$ in der Formel (\ref{QuatRot}) sieht. \subsection{Geometrische Algebra} Die geometrische Algebra besitzt die Fähigkeit beide Probleme zu lösen. Die Quaternionen können, wie schon im 2 dimensionalen Fall durch die gerade Grade $G_3^+(\mathbb{R}) \cong \mathbb{H}$ dargestellt werden. Da wir uns jetzt aber in $G_3(\mathbb{R})$ befinden haben wir drei Basisvektoren $\mathbf{e}_1, \mathbf{e}_2, \mathbf{e}_3$ und können somit drei Bivektoren bilden $\mathbf{e}_{12}, \mathbf{e}_{23}, \mathbf{e}_{31}$. @@ -33,20 +33,54 @@ Die geometrische Algebra besitzt die Fähigkeit beide Probleme zu lösen. Die Qu \end{definition} Die Probleme werden dadurch gelöst, da wir die Bivektoren im Raum nicht durch einzelne Achsen darstellen müssen, sondern sie als eine orientiere Fläche darstellen können. Anstatt die Vektoren in Quaternionen umzurechnen, können wir jetzt die Vektoren separat im gleichen Raum darstellen. -\\BILD VEKTOR, QUATERNION IN G3\\ +\begin{figure} + \centering + \begin{tikzpicture} + % Koordinatensystem + \draw[thin,gray!40] (-3,-2) grid (3,3); + \draw[<->] (-3,0)--(3,0) node[right]{$a_1$}; + \draw[<->] (0,-2)--(0,3) node[above]{$a_2$}; + \draw[<->] (3,3)--(-2,-2) node[left]{$a_3$}; + + % v Vektor + \draw[line width=2pt,black,-stealth](0,0)--(2,-1) node[anchor=north]{$\boldsymbol{v}$}; + + % q Quaternion + \draw[line width=0,fill=blue!40] (0,0)--(0.75,0)--(0.75,0.75)--(0,0.75) + node[xshift=0.375cm, yshift=-0.5cm, blue]{$x\boldsymbol{e_{12}}$}; + \draw[->] (0.7,0.55) arc (0:310:0.15); + + \draw[line width=0,fill=blue!40] (0,0)--(-1,-1)--(-1,0.71)--(0,1.71) + node[xshift=-0.5cm, yshift=-1.5cm, blue]{$y\boldsymbol{e_{23}}$}; + \draw[->] (-0.1,1.1) arc (0:310:0.15); + + \draw[line width=0,fill=blue!40] (0,0)--(-0.71,-0.71)--(0.29,-0.71)--(1,0) + node[xshift=-0.7cm, yshift=-0.2cm, blue]{$z\boldsymbol{e_{31}}$}; + \draw[->] (0,-0.5) arc (0:310:0.15); + + % Basisvektoren + \draw[line width=1.5pt,gray,-stealth](0,0)--(1,0) node[anchor=south west]{$\boldsymbol{e_1}$}; + \draw[line width=1.5pt,gray,-stealth](0,0)--(0,1) node[anchor=north west, yshift=0.2cm]{$\boldsymbol{e_2}$}; + \draw[line width=1.5pt,gray,-stealth](0,0)--(-0.71,-0.71) node[anchor=south, yshift=0.2cm]{$\boldsymbol{e_3}$}; + \end{tikzpicture} + \caption{Darstellung eines Quaternion $\mathbf{q}$ und eines Vektors $\mathbf{v}$ im selben Raum} + \label{BildQuaternionen} +\end{figure} Wie schon im 2 dimensionalen Fall beschreibt ein Bivektor, um wie viel der um 90 grad gedrehte orginale Vektor gestreckt wird. Dabei dreht jeder Bivektor den Vektor um eine andere Achse. \\BILD?\\ In der Computergraphik und Robotik macht eine Drehstreckung aber nicht viel Sinn. Wieso sollte ein Objekt bei einer Drehung zusätzlich noch grösser werden? Darum verwendet man sogenannte Einheitsquaternionen, welche den Betrag $|q|=1$ haben. Sie rotieren die Objekte bzw. Vektoren lediglich. \begin{definition} Einheitsquaternionen \begin{align} - \mathbf{q} = \cos(\alpha) + sin(\alpha)(x\mathbf{e}_{12} + y\mathbf{e}_{23} + z\mathbf{e}_{31}) + \mathbf{q} = \cos(\alpha) + sin(\alpha)(\tilde{x}\mathbf{e}_{12} + \tilde{y}\mathbf{e}_{23} + \tilde{z}\mathbf{e}_{31}) \end{align} \end{definition} -Dabei ist definiert, dass $x^2+y^2+z^2=1$. Somit beträgt der Betrag von immer $\mathbf{q}$ immer 1. +Dabei ist definiert, dass $\tilde{x}^2+\tilde{y}^2+\tilde{z}^2=1$. Somit beträgt der Betrag von $\mathbf{q}$ immer 1. \begin{align} - |\mathbf{q}| = \sqrt{cos(\alpha)^2 + sin(\alpha)^2(x^2+y^2+z^2) } = \sqrt{cos(\alpha)^2 + sin(\alpha)^2} = 1 + |\mathbf{q}| = \sqrt{cos(\alpha)^2 + sin(\alpha)^2(\tilde{x}^2+\tilde{y}^2+\tilde{z}^2) } = \sqrt{cos(\alpha)^2 + sin(\alpha)^2} = 1 \end{align} +Der Winkel $\alpha$ beschreibt dabei, wie im Bild (...) gezeigt den halben Winkel, um welchen der parallelen Anteil $\mathbf{v_{\perp}}$ des Vektors $\mathbf{v}$ zur kombinierten Bivektorebene $sin(\alpha)^2(\tilde{x}^2+\tilde{y}^2+\tilde{z}^2)$ gedreht wird. + Um einen Vektor zu drehen, verwendet man wieder die gleiche Formel, wie auch schon im zweidimensionalen Fall. \begin{align} \label{QuatRotGA} \begin{split} @@ -54,9 +88,116 @@ Um einen Vektor zu drehen, verwendet man wieder die gleiche Formel, wie auch sch &\operatorname{Re}(\mathbf{q}) = \operatorname{Re}(\mathbf{q}^{-1});\enspace \operatorname{Im}(\mathbf{q}) = -\operatorname{Im}(\mathbf{q}^-1) \end{split} \end{align} -Es ist wichtig bei Quaternionen für eine reine Drehstreckung mit $q$ und $q^{-1}$ beidseitig zu multiplizieren, sonst werden die senkrechten Anteile zu den Bivektorebenen ebenfalls beeinflusst, wie man im Kapitel Rotation bei der Formel (\ref{RotAufPerpPar}) sehen kann -\\BEISPIEL DREHUNG 90 grad um zwei Achsen\\ -\\BILD addition Bivektoren zu Beipsiel?\\ +Es ist wichtig bei Quaternionen für eine reine Drehstreckung mit $q$ und $q^{-1}$ beidseitig zu multiplizieren, sonst werden die senkrechten Anteile zu den Bivektorebenen ebenfalls beeinflusst, wie man im Kapitel Rotation bei der Formel (\ref{RotAufPerpPar}) sehen kann. +\begin{beispiel} + Eine Drehung eines Vektors $\mathbf{v}= 1\mathbf{e}_2$ um 90 Grad um die $\mathbf{e}_1$-Achse und danach 90 Grad um die $\mathbf{e}_2$-Achse. Dafür nehmen wir zuerst einen Einheitsquaternion welcher um die Orientierte Ebene $\mathbf{e}_{23}$ um 90 Grad dreht + \begin{align} + \mathbf{q}_{23} &= \cos(\pi/4) + sin(\pi/4)(1\mathbf{e}_{23}) = e^{(\pi/4)\mathbf{e}_{23}} &= 0.71 + 0.71\mathbf{e}_{23}\\ + \mathbf{q}_{23}^{-1} &&= 0.71 - 0.71\mathbf{e}_{23} + \end{align} + und danach Einheitsquaternion welcher um die Orientierte Ebene $\mathbf{e}_{31}$ um 90 Grad dreht + \begin{align} + \mathbf{q}_{31} &= \cos(\pi/4) + sin(\pi/4)(1\mathbf{e}_{31}) = e^{(\pi/4)\mathbf{e}_{31}} &= 0.71 + 0.71\mathbf{e}_{31}\\ + \mathbf{q}_{31}^{-1} &&= 0.71 - 0.71\mathbf{e}_{31} + \end{align} + Um die vollständige Rotation zu beschreiben können die Einheitsquaternion multipliziert werden, wobei die Reihenfolge der Ausführung beachtet werden muss + \begin{align} \label{FormelBeispielQuaternion} + \mathbf{q} &= \mathbf{q}_{31}\mathbf{q}_{23} = (0.71 + 0.71\mathbf{e}_{31})(0.71 + 0.71\mathbf{e}_{23}) &= 0.5 + 0.5\mathbf{e}_{31} + 0.5 \mathbf{e}_{23} + 0.5 \mathbf{e}_{12}\\ + \mathbf{q}^{-1} &= \mathbf{q}_{23}^{-1}\mathbf{q}_{31}^{-1} = (0.71 - 0.71\mathbf{e}_{23})(0.71 - 0.71\mathbf{e}_{31}) &= 0.5 - 0.5\mathbf{e}_{31} - 0.5 \mathbf{e}_{23} - 0.5 \mathbf{e}_{12} + \end{align} + Wenn wir nun den Quaternion $\mathbf{q}$ auf den Vektor $\mathbf{v}$ anwenden + \begin{align} + \mathbf{v}'' = \mathbf{qvq}^{-1} &= (0.5 + 0.5\mathbf{e}_{31} + 0.5 \mathbf{e}_{23} + 0.5 \mathbf{e}_{12})(1\mathbf{e}_2)(0.5 - 0.5\mathbf{e}_{31} - 0.5 \mathbf{e}_{23} - 0.5 \mathbf{e}_{12})\\ + &= (0.5\mathbf{e}_2 + 0.5 \mathbf{e}_{123} - 0.5 \mathbf{e}_3 + 0.5 \mathbf{e}_1)(0.5 - 0.5\mathbf{e}_{31} - 0.5 \mathbf{e}_{23} - 0.5 \mathbf{e}_{12})\\ + &= (0.25 + 0.25 + 0.25 + 0.25)\mathbf{e}_1 + (0.25 + 0.25 - 0.25 - 0.25)\mathbf{e}_2 +\\ &(-0.25 + 0.25 - 0.25 + 0.25)\mathbf{e}_3 + (0.25 - 0.25 - 0.25 + 0.25)\mathbf{e}_{123}\\ + &= 1e_1 + \end{align} + Anders betrachtet könnte man von der Formel \eqref{FormelBeispielQuaternion} sehen, dass der Drehwinkel + \begin{align} + \alpha = \arccos(w) = \arccos(0.5) = 60° + \end{align} + und die Ebene der kombinierten Bivektoren wie in Abbildung \ref{BildQuaternionBeispiel2} aussieht. + Somit kann man sich ebenfalls Vorstellen, wie der parallele Anteil zur Ebene insgesamt um 120° rotiert wird während der senkrechte Anteil unverändert bleibt +\end{beispiel} + +\begin{figure} + \centering + \begin{tikzpicture} + % Koordinatensystem + \draw[thin,gray!40] (-3,-2) grid (3,3); + \draw[<->] (-3,0)--(3,0) node[right]{$a_1$}; + \draw[<->] (0,-2)--(0,3) node[above]{$a_2$}; + \draw[<->] (3,3)--(-2,-2) node[left]{$a_3$}; + + % q Quaternion + \draw[line width=0,fill=blue!40] (0,0)--(1.41,0)--(1.41,1.41)--(0,1.41) + node[xshift=0.375cm, yshift=-0.5cm, blue]{$x\boldsymbol{e_{12}}$}; + \draw[->] (1.35, 1.2) arc (0:310:0.15); + + \draw[line width=0,fill=blue!40] (0,0)--(-1,-1)--(-1,0.41)--(0,1.41) + node[xshift=-0.5cm, yshift=-1.5cm, blue]{$y\boldsymbol{e_{23}}$}; + \draw[->] (-0.65,-0.5) arc (0:310:0.15); + + \draw[line width=0,fill=blue!40] (0,0)--(-1,-1)--(0.41,-1)--(1.41,0) + node[xshift=-0.7cm, yshift=-0.2cm, blue]{$z\boldsymbol{e_{31}}$}; + \draw[->] (0.4,-0.8) arc (0:310:0.15); + + % Basisvektoren + \draw[line width=1.5pt,gray,-stealth](0,0)--(2,0) node[anchor=south west]{$\boldsymbol{e_1}$}; + \draw[line width=1.5pt,gray,-stealth](0,0)--(0,2) node[anchor=north west, yshift=0.2cm]{$\boldsymbol{e_2}$}; + \draw[line width=1.5pt,gray,-stealth](0,0)--(-1.41,-1.41) node[anchor=south, yshift=0.2cm]{$\boldsymbol{e_3}$}; + + % v Vektor + \draw[line width=2pt,black,-stealth](-0.05,0)--(-0.05,2) node[anchor=east]{$\boldsymbol{v}$}; + % v'' Vektor + \draw[line width=2pt,black,-stealth](0,0.05)--(2,0.05) node[anchor=north]{$\boldsymbol{v}''$}; + \end{tikzpicture} + \caption{Beispiel für Drehung um 90 Grad je um die $\mathbf{e}_1$- und $\mathbf{e}_2$-Achse.} + \label{BildQuaternionBeispiel} +\end{figure} + +\begin{figure} + \centering + \begin{tikzpicture} + % q Quaternion + \draw[line width=0,fill=blue!40] (-0.75,-1)--(1.5,-0.5)--(0.55,1.35)--(-1.5,1) + node[xshift=0.375cm, yshift=-0.5cm, blue]{$\boldsymbol{q}$}; + \draw[->] (-0.7, 0.5) arc (310:0:0.15); + + % Koordinatensystem + \draw[thin,gray!40] (-3,-2) grid (3,3); + \draw[<->] (-3,0)--(3,0) node[right]{$a_1$}; + \draw[<->] (0,-2)--(0,3) node[above]{$a_2$}; + \draw[<->] (3,3)--(-2,-2) node[left]{$a_3$}; + + % Basisvektoren + \draw[line width=1.5pt,gray,-stealth](0,0)--(2,0) node[anchor=south west]{$\boldsymbol{e_1}$}; + \draw[line width=1.5pt,gray,-stealth](0,0)--(0,2) node[anchor=north west, yshift=0.2cm]{$\boldsymbol{e_2}$}; + \draw[line width=1.5pt,gray,-stealth](0,0)--(-1.41,-1.41) node[anchor=south, yshift=0.2cm]{$\boldsymbol{e_3}$}; + + % v Vektor + \draw[line width=2pt,black,-stealth](-0.05,0)--(-0.05,2) node[anchor=east]{$\boldsymbol{v}$}; + % vpar Vektor + \draw[line width=2pt,red,-stealth](0,0)--(-0.33,1.25) node[anchor=east]{$\boldsymbol{v_{\parallel}}$}; + % vperp Vektor + \draw[line width=2pt,green,-stealth](-0.33,1.25)--(0,2) node[anchor=east, xshift = -0.05, yshift = -0.3cm]{$\boldsymbol{v_{\perp}}$}; + % v'' Vektor + \draw[line width=2pt,black,-stealth](0,0.05)--(2,0.05) node[anchor=north, xshift = 0.25cm]{$\boldsymbol{v}''$}; + % vpar'' Vektor + \draw[line width=2pt,red,-stealth](0,0)--(1.66,-0.75) node[anchor=east, yshift = -0.2cm, xshift = -0.1cm]{$\boldsymbol{v_{\parallel}''}$}; + % vperp'' Vektor + \draw[line width=2pt,green,-stealth](1.66,-0.75)--(2,0) node[anchor=east, xshift = 0.5cm, yshift = -0.65cm]{$\boldsymbol{v_{\perp}''}$}; + + \coordinate (A) at (0,0); + \coordinate (B) at (-0.33,1.25); + \coordinate (C) at (1.66,-0.75); + \tikzset{anglestyle/.style={angle eccentricity=2, draw, thick, angle radius=0.75cm, purple}} + \draw pic ["120° $=2\alpha$", anglestyle] {angle = C--A--B}; + \end{tikzpicture} + \caption{Beim Beispiel wird der parallele Anteil um 120° gedreht während der senkrechte Anteil zur kombinierten Ebene (Bivektoraddition) gleich bleibt} + \label{BildQuaternionBeispiel2} +\end{figure} + \subsection{Interpolation} In der Computergrafik wird Interpolation verwendet, um eine flüssige Drehbewegung zu erreichen. Dabei wird die gewünschte Drehbewegungen des Objektes in kleinere aufgeteilt. Man kann dabei mit zwei verschiedenen Systemen arbeiten. \begin{itemize} diff --git a/buch/papers/clifford/6_PauliMatrizen.tex b/buch/papers/clifford/6_PauliMatrizen.tex index 9392285..e41275a 100644 --- a/buch/papers/clifford/6_PauliMatrizen.tex +++ b/buch/papers/clifford/6_PauliMatrizen.tex @@ -6,40 +6,44 @@ \section{Pauli-Matrizen} \rhead{Pauli-Matrizen} -Was ist der beste Weg um einen Computeralgorithmus für die Rechenoperationen in der Clifford-Algebra zu erstellen? Man könnte versuchen ein textueller Rechner zu implementieren der für die Elemente $\mathbf{e}_i$ hartkodierte Vereinfachungen ausführt +Was ist der beste Weg um einen Computeralgorithmus für die Rechenoperationen in der Clifford-Algebra zu erstellen? Man könnte versuchen einen textuellen Rechner zu implementieren der für die Elemente $\mathbf{e}_i$ hartkodierte Vereinfachungen ausführt. \begin{beispiel} - der Algorithmus weiss, dass er $a\mathbf{e}_1\cdot b\mathbf{e}_1$ zu $ab\cdot1$ vereinfachen kann + Der Algorithmus weiss, dass er $a\mathbf{e}_1\cdot b\mathbf{e}_1$ zu $ab\cdot1$ vereinfachen kann. Dies ermöglicht zum Beispiel die Vereinfachung \begin{align} 3\mathbf{e}_1 \cdot 2\mathbf{e}_1 + 3\mathbf{e}_2 \Rightarrow 6 + 3\mathbf{e}_2 \end{align} \end{beispiel} -Dies ist aber sehr ineffizient. Die Pauli-Matrizen bilden eine elegante und schnellere Alternative, welche für die dreidimensionale Clifford-Algebra verwendet werden können und alle Operationen aus der Clifford-Algebra gleich wie die Matrixoperationen ausführen lassen. -\begin{definition} \label{def:defPauli} - vier Pauli-Matrizen ($\mathbf{e}_0$ = Skalare) - \begin{align} +Ein textueller Algorithmus ist aber sehr ineffizient. Die Pauli-Matrizen bilden eine elegante und schnellere Alternative, welche für die dreidimensionale Clifford-Algebra verwendet werden können und alle Operationen aus der Clifford-Algebra gleich wie die Matrixoperationen ausführen lassen. +\begin{definition} \label{def:defPauli} + Die Matrizen + \begin{align} \label{Pauli} \mathbf{e}_0 = E = \begin{pmatrix} 1 & 0 \\ 0 & 1 - \end{pmatrix}\quad + \end{pmatrix},\quad \mathbf{e}_1 = \begin{pmatrix} 0 & 1 \\ 1 & 0 - \end{pmatrix}\quad + \end{pmatrix},\quad \mathbf{e}_2 = \begin{pmatrix} 0 & -j \\ j & 0 - \end{pmatrix}\quad + \end{pmatrix},\quad \mathbf{e}_3 = \begin{pmatrix} 1 & 0 \\ 0 & -1 - \end{pmatrix}\quad + \end{pmatrix} \end{align} - durch normale Matrizenmultiplikation lassen sich die restlichen Basiselemente der dreidimensionalen Clifford-Algebra herleiten - \begin{align} + heissen Pauli-Matrizen ($\mathbf{e}_0$ = Skalare) +\end{definition} +Die Matrix-Multiplikationen der Pauli-Matrizen führt auf die gleichen algebraischen Relationen, wie die Multiplikation der Elemente $\mathbf{e}_0, \mathbf{e}_1, \mathbf{e}_2, \mathbf{e}_3$. So lassen sich auch die restlichen Elemente der Clifford-Algebra erzeugen. +\begin{definition} \label{def:defPauli2} + Die Bivektoren und Trivektoren hergeleitet aus den Pauli-Matrizen sind + \begin{align} \label{Pauli2} \mathbf{e}_{12} = \begin{pmatrix} j & 0 \\ @@ -54,17 +58,17 @@ Dies ist aber sehr ineffizient. Die Pauli-Matrizen bilden eine elegante und schn \begin{pmatrix} 0 & 1 \\ -1 & 0 - \end{pmatrix}\quad + \end{pmatrix}\enspace\text{und}\enspace \mathbf{e}_{123} = \begin{pmatrix} j & 0 \\ 0 & j - \end{pmatrix}\quad + \end{pmatrix}. \end{align} \end{definition} -Dabei ist wichtig, dass sich die Matrizen gleich verhalten, wie es die Clifford-Algebra für die Basiselemente definiert hat. +Dabei ist wichtig, dass sich die Matrizen gleich verhalten, wie es die Clifford-Algebra für die Basiselemente definiert hat. Zum Beispiel gilt in der Clifford-Algebra $\mathbf{e}_1^2=\mathbf{e}_0$ und $\mathbf{e}_{12}^2=-\mathbf{e}_0$, genau die selbe Relation gilt auch für die zugehörigen Matrizen, wie man durch die Matrizenrechnungen \begin{align} - \mathbf{e}_1^2 &= \mathbf{e}_0 = + \mathbf{e}_1^2 &= \begin{pmatrix} 0 & 1 \\ 1 & 0 @@ -72,8 +76,8 @@ Dabei ist wichtig, dass sich die Matrizen gleich verhalten, wie es die Clifford- \begin{pmatrix} 1 & 0 \\ 0 & 1 - \end{pmatrix}\\ - \mathbf{e}_{12}^2 &= -\mathbf{e}_0 = + \end{pmatrix}= \mathbf{e}_0 \quad\text{und}\\ + \mathbf{e}_{12}^2 &= \begin{pmatrix} j & 0 \\ 0 & -j @@ -81,28 +85,44 @@ Dabei ist wichtig, dass sich die Matrizen gleich verhalten, wie es die Clifford- \begin{pmatrix} -1 & 0 \\ 0 & -1 - \end{pmatrix} + \end{pmatrix} = -\mathbf{e}_0 \end{align} -Man kann bei der Definition \ref{def:defPauli} sehen, dass alle Matrizen linear unabhängig voneinander sind. Das bedeutet, dass wenn man die Matrizen der Basiselemente normal addiert und zu einer grossen Matrix zusammenfasst und anschliessend wieder herausgelesen werden können. -\begin{definition} - Multivektor mit Pauli-Matrizen +bestätigt. Man kann bei den Definitionen \ref{def:defPauli} und \ref{def:defPauli2} sehen, dass alle Matrizen linear unabhängig voneinander sind. Das bedeutet, dass wenn man die Matrizen der Basiselemente normal addiert und zu einer Matrix zusammenfasst, kann man anschliessend die einzelnen Anteile der Basiselemente wieder herausgelesen. +\begin{hilfssatz} + Ein beliebiger Multivektor + \begin{align} \label{MultiVektorAllg} + M = a_0\mathbf{e}_0 + a_1\mathbf{e}_1 + a_2\mathbf{e}_3 + a_{12}\mathbf{e}_{12} + a_{23}\mathbf{e}_{23} + a_{31}\mathbf{e}_{31} + a_{123}\mathbf{e}_{123}\\ + \end{align} + erhält durch das einsetzten der Formel Matrizen \eqref{Pauli} und \eqref{Pauli2} die Form \begin{align} - M &= a_0\mathbf{e}_0 + a_1\mathbf{e}_1 + a_2\mathbf{e}_3 + a_{12}\mathbf{e}_{12} + a_{23}\mathbf{e}_{23} + a_{31}\mathbf{e}_{31} + a_{123}\mathbf{e}_{123}\\ - M &= + M = \begin{pmatrix} (a_0+a_3) + (a_{12}+a_{123})j & (a_1+a_{31})+(-a_2+a_{23})j \\ (a_1-a_{31})+(a_2+a_{23})j & (a_0-a_3)+(-a_{12}+a_{123})j - \end{pmatrix} + \end{pmatrix}.\label{MultivektorMatirx} \end{align} -\end{definition} +\end{hilfssatz} +Die Anteile treten zudem immer paarweise auf und können somit immer je durch zwei Gleichungen bestimmt werden. \begin{beispiel} + Die Matrix \begin{align} - M &= \begin{pmatrix} + M &= + \begin{pmatrix} 1 & 0 \\ - 0 & 0 - \end{pmatrix}\\ - &\Rightarrow a_0 + a_3 = 1 \land a_0 - a_3 = 0\\ - &\Rightarrow a_0 = 0.5 \land a_3 = 0.5\\ - M &= 0.5 \mathbf{e}_0 + 0.5 \mathbf{e}_3 + 0 & -1j + \end{pmatrix} + \end{align} + soll als Multivektor in der Form \eqref{MultiVektorAllg} geschrieben werden. Dafür entnehmen wir aus \eqref{MultivektorMatirx} die Gleichungen + \begin{align} + a_0 + a_3 = 1,\quad a_0 - a_3 = 0,\quad a_{12}+a_{123} = 0\enspace\text{und}\enspace -a_{12}+a_{123}=-1 + \end{align} + aus denen man auf + \begin{align} + a_0 = \dfrac{1}{2},\quad a_3 = \dfrac{1}{2},\quad a_{12}=\dfrac{1}{2}\enspace\text{und}\enspace a_{123}=-\dfrac{1}{2} + \end{align} + schliessen kann. Da die restlichen Realteile und Imaginärteile 0 sind, werden die anderen Anteile ebenfalls 0 sein. Daher ist + \begin{align} + M = \dfrac{1}{2} \mathbf{e}_0+ \dfrac{1}{2} \mathbf{e}_3 + \dfrac{1}{2} \mathbf{e}_{12} - \dfrac{1}{2} \mathbf{e}_{123}. \end{align} -\end{beispiel}
\ No newline at end of file +\end{beispiel} +Die Clifford-Algebra ist bei der Darstellung durch Matrizen kein Ausnahmefall. Es lässt sich theoretisch jede algebraische Struktur durch Matrizen darstellen.
\ No newline at end of file diff --git a/buch/papers/clifford/7_Reflektion.tex b/buch/papers/clifford/7_Reflektion.tex index 1c6d590..bdfb4e8 100644 --- a/buch/papers/clifford/7_Reflektion.tex +++ b/buch/papers/clifford/7_Reflektion.tex @@ -3,47 +3,81 @@ % % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil % -\section{Reflexion/ Spiegelung} -\rhead{Reflexion/ Spiegelung} +\section{Spiegelung} +\rhead{Spiegelung} + +Die Spiegelung ist eine grundlegende, geometrische Operation, aus welcher man weitere, wie beispielsweise die später beschriebene Rotation, ableiten kann. Da die geometrische Algebra für geometrische Anwendungen ausgelegt ist, sollte die Spiegelung auch eine einfache, praktische Formulierung besitzen. +\begin{figure} + \centering + \begin{tikzpicture} + \draw[thin,gray!40] (-3,-1) grid (3,3); + \draw[<->] (-3,0)--(3,0) node[right]{$a_1$}; + \draw[<->] (0,-1)--(0,3) node[above]{$a_2$}; + \draw[line width=2pt,black,-stealth](0,0)--(2,2) node[anchor=south east]{$\boldsymbol{v}$}; + \draw[line width=1.5pt,blue,-stealth](0,0)--(0,2.5) node[anchor=south east]{$\boldsymbol{u}$}; + \draw[line width=2pt,black,-stealth](0,0)--(-2,2) node[anchor=south east]{$\boldsymbol{v'}$}; + \draw[line width=1.5pt,gray,-stealth](0,0)--(1,0) node[anchor=north]{$\boldsymbol{e_1}$}; + \draw[line width=1.5pt,gray,-stealth](0,0)--(0,1) node[anchor=north east]{$\boldsymbol{e_2}$}; + \draw[line width=1.5pt,red,-stealth](0,2)--(2,2) node[xshift=-1cm, yshift= + 0.25cm]{$\boldsymbol{v_{\perp u}}$}; + \draw[line width=1.5pt,red,-stealth](-2,2)--(0,2) node[xshift=-1cm, yshift= + 0.25cm]{$\boldsymbol{v_{\perp u}}$}; + \draw[line width=1.5pt,purple,-stealth](0,1.5)--(1,1.5) node[xshift=-0.5cm, yshift=-0.25cm]{$\boldsymbol{\hat{n}}$}; + \end{tikzpicture} + \caption{Spiegelung des Vektors \textbf{v} an Spiegelachse bzw. Vektor \textbf{u}} + \label{BildSpiegelung} +\end{figure} -Die Spiegelung ist eine grundlegende, geometrische Operation, aus welcher man weitere, wie beispielsweise die später beschriebene Rotation, ableiten kann. Da die Geometrische Algebra für geometrische Anwendungen ausgelegt ist, sollte die Reflexion auch eine einfache, praktische Formulierung besitzen. \\HIER BILD \subsection{Linearen Algebra} -Aus der linearen Algebra ist bekannt, dass man eine Spiegelung wie folgt beschreiben kann. +Aus der linearen Algebra ist bekannt, dass man eine Spiegelung an einer Ebene wie folgt beschreiben kann. \begin{definition} - Spiegelungsgleichung in der linearen Algebra + Die Spiegelungsgleichung in der linearen Algebra mit dem Normalenvektor $\mathbf{\hat{n}}$ zur Spiegelebene ist \begin{equation} \label{RefLinAlg} - \mathbf{v^{'}} = \mathbf{v} - 2 \cdot \mathbf{v_{\perp u}} + \mathbf{v^{'}} = \mathbf{v} - 2 \cdot \mathbf{v_{\parallel \hat{n}}} = \mathbf{v} - 2 \cdot \mathbf{v_{\perp u}}. \end{equation} + Per Definition sind $\mathbf{v_{\parallel \hat{n}}} = \mathbf{v_{\perp u}}$. In der geometrischen Algebra verwenden wir aber in den Formeln Vektoren, welche Spiegelachsen, nicht Spiegelebenen, repräsentieren. \end{definition} - -$\mathbf{u}$ repräsentiert die Spiegelachse und $\mathbf{v_{\perp u}}$ senkrecht auf dieser Achse steht und den orthogonalen Anteil von $\mathbf{v}$ zu $\mathbf{u}$ bildet. Es scheint für diese Formel aber umständlich zu sein, weitere Spiegelungen, mit weiteren Spiegelachsen, anzufügen. Man kann die Abbildung des Vektors auf den gespiegelten Vektor auch als Matrix schreiben, welche aus den Komponenten des zu der Spiegelachse orthonormalen Vektors $\mathbf{\hat{n}}$ besteht. -\begin{align} - \mathbf{\hat{n}}\perp \mathbf{u}\quad \land \quad |\mathbf{\hat{n}}| = 1 +Es scheint für diese Formel aber umständlich zu sein, weitere Spiegelungen mit weiteren Spiegelebenen anzufügen. Man kann diese Abbildung aber auch als Matrix schreiben. Sei $\mathbf{\hat{n}}$ ein Normalenvektor auf die Spiegelungs-Achse bzw. -Ebene, also $\mathbf{\hat{n}}\perp \mathbf{u}$, und sei ausserdem normiert $|\mathbf{\hat{n}}| = 1$, dann kann man die Spiegelung durch die Matrix +\begin{align} + S = E - 2\dfrac{1}{|\mathbf{n}|^2}\mathbf{nn}^t \end{align} +beschrieben werden. In der zweiten und dritten Dimension ergibt die Berechnung \begin{align} \label{Spiegelmatrizen} - Spiegelmatrizen... + S_2 = \begin{pmatrix} + 1-2n_1^2 & -2n_1n_2 \\ + -2n_1n_2 & 1-2n_2^2 + \end{pmatrix} \quad + S_3 = \begin{pmatrix} + 1-2n_1^2 & -2n_1n_2 & -2n_1n_3\\ + -2n_1n_2 & 1-2n_2^2 & -2n_2n_3\\ + -2n_1n_3 & -2n_2n_3 & 1-2n_3^2\\ + \end{pmatrix}. \end{align} -Diese Matrizen Spiegelmatrizen gehören der orthogonalen Matrizengruppe $S\in \text{O}(n)$ an. Diese haben die Eigenschaft $S^t S = E$, was bedeutet, dass zweimal eine Spiegelung an der selben Achse keinen Effekt hat. +Diese Spiegelmatrizen gehören der orthogonalen Matrizengruppe $S\in \text{O}(n)$ an. Die Matrizengruppe $\text{O}(n)$ haben die Eigenschaft $S^t S = E$, was bedeutet, dass die Länge und Winkel bei der Abbildung beibehalten bleiben. Zusätzlich sind die Spiegelmatrizen symmetrisch, es gilt $S^t = S$. Somit liefert zweimal dieselbe Spiegelung wieder die identische Abbildung, wie man aus +\begin{align} + S^t S = S^2 = E +\end{align} +schliessen kann. + \subsection{Geometrische Algebra} -Die Geometrische Algebra leitet aus der obigen Formel \eqref{RefLinAlg} eine einfache und intuitive Form her, welche auch für weitere Operationen einfach erweitert werden kann. +Um die folgenden Formeln zu verstehen, definieren wir zuerst die Inverse eines Vektors, welche in dieser Form nicht in der linearen Algebra nicht existiert. \begin{definition} - Spiegelungsgleichung in der geometrischen Algebra - \begin{align}\label{RefGA} - \mathbf{v}' = \mathbf{uvu}^{-1} + Die Inverse eines Vektors wird definiert als + \begin{align} + \mathbf{u}^{-1} = \dfrac{\mathbf{u}}{|\mathbf{u}|^2} \Rightarrow \mathbf{uu}^{-1} = \dfrac{\mathbf{u}^2}{|\mathbf{u}|^2} = 1. \end{align} + Wie schon aus anderen algebraischen Strukturen bekannt, ergibt ein Element, hier $\mathbf{u}$, multipliziert mit dessen Inversen, hier $\mathbf{u}^{-1}$, das neutrale Element der Struktur, hier 1. \end{definition} - -Die Inverse eines Vektors ist dabei so definiert, dass multipliziert mit sich dem Vektor selbst das neutrale Element 1 ergibt. +Die geometrische Algebra leitet aus der obigen Formel \eqref{RefLinAlg} für eine Spiegelung eine einfache und intuitive Form her, welche auch für weitere Operationen erweitert werden kann. \begin{definition} - Inverse eines Vektors - \begin{align} - \mathbf{u}^{-1} = \dfrac{\mathbf{u}}{|\mathbf{u}|^2} \Rightarrow \mathbf{uu}^{-1} = \dfrac{\mathbf{u}^2}{|\mathbf{u}|^2} = 1 + Die Spiegelungsgleichung in der geometrischen Algebra mit der Spiegelachse $\mathbf{u}$ ist definiert als + \begin{align}\label{RefGA} + \mathbf{v}' = \mathbf{uvu}^{-1} \end{align} \end{definition} -verwendet man für $\mathbf{u}$ nur einen Einheitsvektor $\mathbf{\hat{u}}$, welcher die Länge 1 besitzt, wird somit die Formel reduziert zu einer beidseitigen Multiplikation von $\mathbf{\hat{u}}$. +verwendet man für $\mathbf{u}$ nur einen Einheitsvektor $\mathbf{\hat{u}}$, welcher die Länge 1 besitzt, wird die Gleichung zu \begin{align} \mathbf{v'} = \mathbf{\hat{u}v\hat{u}} \end{align} -Im Gegensatz zu den Abbildungen in der linearen Algebra, welche in jeder anderen Dimension, wie bei der Definition \eqref{Spiegelmatrizen} ersichtlich, durch andere Matrizen beschrieben werden müssen, ist es in der geometrischen Algebra immer der gleiche Vorgehensweise. Zudem ist diese kompakte Schreibweise in der linearen Algebra nicht möglich, da bis auf das Vektorprodukt in der dritten Dimension keine Multiplikation von Vektoren definiert ist. -\\BEISPIEL?
\ No newline at end of file +vereinfacht. Im Gegensatz zu den Abbildungen in der linearen Algebra, welche in jeder anderen Dimension, durch andere Matrizen \eqref{Spiegelmatrizen} beschrieben werden müssen, ist es in der geometrischen Algebra immer der gleiche Vorgehensweise. Zudem ist diese kompakte Schreibweise in der linearen Algebra nicht möglich, da bis auf das Vektorprodukt in der dritten Dimension keine Multiplikation von Vektoren definiert ist.
\ No newline at end of file diff --git a/buch/papers/clifford/8_Rotation.tex b/buch/papers/clifford/8_Rotation.tex index 3ef5fbf..6a3251a 100644 --- a/buch/papers/clifford/8_Rotation.tex +++ b/buch/papers/clifford/8_Rotation.tex @@ -6,119 +6,165 @@ \section{Rotation} \rhead{Rotation} -Eine Rotation kann man aus zwei, aufeinanderfolgende Spiegelung bilden. Das war für mich zuerst eine verwirrende Aussage, da man aus den vorherig gezeigten Formeln annehmen könnte, dass die Spiegelung schon für eine Drehung ausreicht. Obwohl sich die Längen, Winkel und Volumen sich bei einer Spiegelung, wie bei einer Rotation, nicht ändert, sind sie doch verschieden, da die Orientierung bei der Spiegelung invertiert wird. Stellt man sich beispielsweise ein Objekt im Dreidimensionalen vor und spiegelt dieses an einer Fläche, dann ist es unmöglich nur durch eine Rotation (egal an welchem Punkt) das ursprüngliche Objekt deckungsgleich auf das Gespiegelte zu drehen. Hingegen ist es wiederum möglich ein zweifach gespiegeltes Objekt durch eine Drehung zu erreichen. Das liegt daran, da die Orientierung zweimal invertiert wurde. -\\BILD +Eine Rotation kann man aus zwei aufeinanderfolgenden Spiegelungen bilden. Das wird für einige zuerst eine verwirrende Aussage sein, da man aus den vorherig gezeigten Formeln annehmen könnte, dass die Spiegelung schon für eine Drehung ausreicht. Obwohl sich die Längen, Winkel und Volumen sich bei einer Spiegelung, wie bei einer Rotation, nicht ändert, sind sie doch verschieden, da die Orientierung bei der Spiegelung invertiert wird. Stellt man sich beispielsweise ein Objekt im Dreidimensionalen vor und spiegelt dieses an einer Fläche, dann ist es unmöglich nur durch eine Rotation (egal an welchem Punkt) das ursprüngliche Objekt deckungsgleich auf das Gespiegelte zu drehen. Hingegen ist es wiederum möglich ein zweifach gespiegeltes Objekt durch eine Drehung zu erreichen. Das liegt daran, da die Orientierung zweimal invertiert wurde. +\\(Hier wird noch ein Bild für das Verständnis eingefügt) + +\begin{figure} + \centering + \begin{tikzpicture} + \draw[thin,gray!40] (-3,-1) grid (3,3); + \draw[<->] (-3,0)--(3,0) node[right]{$a_1$}; + \draw[<->] (0,-1)--(0,3) node[above]{$a_2$}; + \draw[line width=2pt,black,-stealth](0,0)--(2,2) node[anchor=south east]{$\boldsymbol{v}$}; + \draw[line width=1.5pt,blue,-stealth](0,0)--(0,2.5) node[anchor=south east]{$\boldsymbol{u}$}; + \draw[line width=2pt,black,-stealth](0,0)--(-2,2) node[anchor=south east]{$\boldsymbol{v'}$}; + \draw[line width=1.5pt,red,-stealth](0,0)--(-2.31, 0.957) node[anchor=south east]{$\boldsymbol{w}$}; + \draw[line width=2pt,black,-stealth](0,0)--(-2.828,0) node[anchor=south east]{$\boldsymbol{v''}$}; + \draw[line width=1.5pt,gray,-stealth](0,0)--(1,0) node[anchor=north]{$\boldsymbol{e_1}$}; + \draw[line width=1.5pt,gray,-stealth](0,0)--(0,1) node[anchor=north west]{$\boldsymbol{e_2}$}; + + \coordinate (A) at (0,0); + \coordinate (B) at (0,2.5); + \coordinate (C) at (-2.31, 0.957); + \tikzset{anglestyle/.style={angle eccentricity=1.25, draw, thick, angle radius=1.25cm}} + \draw pic ["$\theta$", anglestyle] {angle = B--A--C}; + \end{tikzpicture} + \caption{Rotation des Vektors $\textbf{v}$ um $2\theta$} + \label{BildRotation} +\end{figure} \subsection{Linearen Algebra} -In der linearen Algebra haben wir Drehungen durch die Matrizen der Gruppe $\text{SO}(n)$ beschrieben. Die $\text{SO}(2)$ werden beispielsweise auf diese Weise gebildet. +In der linearen Algebra haben wir Drehungen durch die Matrizen der Gruppe $\text{SO}(n)$ beschrieben. Beispielsweise besteht $\text{SO}(2)$ aus den Matrizen \begin{align} D = \begin{pmatrix} \cos(\alpha) & \sin(\alpha) \\ -\sin(\alpha) & \cos(\alpha) - \end{pmatrix} + \end{pmatrix},\quad + \alpha \in [0, 2\pi). \end{align} -Diese Drehmatrizen gehören der speziellen orthogonalen Matrizengruppe $D\in \text{SO}(n) = \text{SL}_n(\mathbb{R})\enspace \cap \enspace \text{O}(n)$ an. $\text{SL}_n(\mathbb{R})$ beinhaltet die Matrizen mit scherenden Eigenschaften. Diese Drehmatrizen haben die Eigenschaft $D^t D = E \enspace \land \enspace det(D)=1$. Dadurch dass die $det(D) = 1$ und nicht $-1$ sein kann fallen alle Spiegelungen aus der Menge raus. $det(D) = -1$ bedeutet, dass eine Orientierungsinversion stattfindet. -\\BILD Mengen Spezieller Matrizen von Herrn Müller Präsentation +Diese Drehmatrizen gehören der speziellen orthogonalen Matrizengruppe $D\in \text{SO}(n) = \text{SL}_n(\mathbb{R})\enspace \cap \enspace \text{O}(n)$ an. $\text{SL}_n(\mathbb{R})$ beinhaltet die Matrizen mit scherenden Eigenschaften. Diese Drehmatrizen haben die Eigenschaft $D^t D = E \enspace \land \enspace \det(D)=1$. Da $\det(D) = 1$ und nicht $-1$ sein kann fallen alle Spiegelungen aus der Menge heraus. $\det(D) = -1$ bedeutet, dass eine Orientierungsinversion stattfindet. +\\(BILD Mengen Spezieller Matrizen von Herrn Müller Präsentation) \subsection{Geometrische Algebra} Da wir jetzt aus der Geometrie wissen, dass eine Rotation durch zwei Spiegelungen gebildet werden kann, können wir die Rotation mit der Formel \eqref{RefGA} einfach herleiten. -\begin{align} \label{rotGA} - \mathbf{v}'' = \mathbf{wv}'\mathbf{w}^{-1} = \mathbf{w}(\mathbf{uvu}^{-1})\mathbf{w}^{-1} -\end{align} +\begin{satz} + Eine Rotation + \begin{align} \label{rotGA} + \mathbf{v}'' = \mathbf{wv}'\mathbf{w}^{-1} = \mathbf{w}(\mathbf{uvu}^{-1})\mathbf{w}^{-1} = (\mathbf{wu})\mathbf{v}(\mathbf{u}^{-1}\mathbf{w}^{-1}) + \end{align} + lässt sich durch zwei nacheinander auf einen Vektor $\mathbf{v}$ angewendete Spiegelungen beschreiben. +\end{satz} Die Vektoren $\mathbf{w}$ und $\mathbf{u}$ bilden hier wiederum die Spiegelachsen. Diese Formel versuchen wir jetzt noch durch Umstrukturierung zu verbessern. -\subsubsection{Polarform und Exponentialform} -Dazu leiten wir zuerst die Exponentialform her. (Anmerkung: Hier wird eine Rotation auf der $\mathbf{e}_{12}$ Ebene hergeleitet. Weitere Drehungen können in höheren Dimensionen durch Linearkombinationen von Drehungen in den $\mathbf{e}_{ij}, i\not=j$ Ebenen erreicht werden). Dafür verwenden wir die Polarform des Vektors. +\subsubsection{Exponentialform} +Dazu leiten wir zuerst die Exponentialform eines Vektors her. Es wird dabei zur Vereinfachung davon ausgegangen, dass alle Vektoren $\mathbf{w}, \mathbf{u}, \mathbf{v}$ in der $\mathbf{e}_{12}$ Ebene liegen. Weitere Drehungen können in höheren Dimensionen durch Linearkombinationen von Drehungen in den $\mathbf{e}_{ij}, i\not=j$ Ebenen erreicht werden. Für die Herleitung erweitern wir nun als erstes die Polarform \begin{align} \mathbf{w} = |\mathbf{w}| \left(\cos(\theta_w) \mathbf{e}_1 + \sin(\theta_w) \mathbf{e}_2\right) \end{align} -Dabei können wir ausnützen, dass $\mathbf{e}_1^2 = 1$ ist. Was nichts ändert wenn wir es einfügen. Zudem klammern wir dann $\mathbf{e}_1$ aus. +eines Vektors mit $\mathbf{e}_1^2 = 1$ beim Sinus \begin{align}\label{e1ausklammern} - \mathbf{w} = |\mathbf{w}| \left(\cos(\theta_w) \mathbf{e}_1 + \sin(\theta_w) \mathbf{e}_1\mathbf{e}_1\mathbf{e}_2\right) + \mathbf{w} &= |\mathbf{w}| \left(\cos(\theta_w) \mathbf{e}_1 + \sin(\theta_w) \mathbf{e}_1\mathbf{e}_1\mathbf{e}_2\right), \end{align} +um dann $\mathbf{e}_1$ \begin{align} - \mathbf{w} = |\mathbf{w}|\mathbf{e}_1\left(\cos(\theta_w)+ \sin(\theta_w) \mathbf{e}_{12}\right) + \mathbf{w} = |\mathbf{w}|\mathbf{e}_1\left(\cos(\theta_w)+ \sin(\theta_w) \mathbf{e}_{12}\right) \label{ExponentialGA} \end{align} -Durch die Reihenentwicklung der $\sin$ und $\cos$ Funktionen +ausklammern zu können. Die Ähnlichkeit des Klammerausdrucks zu der Eulerschen Formel bei den Komplexen Zahlen ist nun schon gut erkennbar. Versuchen wir nun mithilfe der Reihenentwicklungen \begin{align} \sin(\theta_w)\mathbf{e}_{12}&=\sum _{n=0}^{\infty }(-1)^{n}{\frac {\theta_w^{2n+1}}{(2n+1)!}}\mathbf{e}_{12} =\theta_w\mathbf{e}_{12}-{\frac {\theta_w^{3}}{3!}}\mathbf{e}_{12}+{\frac {\theta_w^{5}}{5!}}\mathbf{e}_{12}-\cdots \\ - cos(\theta_w)&=\sum _{n=0}^{\infty }(-1)^{n}{\frac {\theta_w^{2n}}{(2n)!}} =1-{\frac {\theta_w^{2}}{2!}}+{\frac {\theta_w^{4}}{4!}}-\cdots + \cos(\theta_w)&=\sum _{n=0}^{\infty }(-1)^{n}{\frac {\theta_w^{2n}}{(2n)!}} =1-{\frac {\theta_w^{2}}{2!}}+{\frac {\theta_w^{4}}{4!}}-\cdots \end{align} -ist es uns leicht möglich die $\sin$ und $\cos$ Terme in die Exponentialfunktion umzuwandeln. Dabei verwenden wir zusätzlich noch unsere Erkenntnis, dass $\mathbf{e}_{12}^2=-1, \enspace\mathbf{e}_{12}^3=-\mathbf{e}_{12}, ...$ +den Zusammenhang auch hier herzustellen. Verwenden wir jetzt noch die Eigenschaft, dass $\mathbf{e}_{12}^2=-1, \enspace\mathbf{e}_{12}^3=-\mathbf{e}_{12}, \dots$, bei dem Klammerausdruck in Formel \eqref{ExponentialGA} \begin{align} \cos(\theta_w)+ \sin(\theta_w) \mathbf{e}_{12} &= 1+\theta_w\mathbf{e}_{12}-{\frac {\theta_w^{2}}{2!}}-{\frac {\theta_w^{3}}{3!}}\mathbf{e}_{12}+{\frac {\theta_w^{4}}{4!}}+{\frac {\theta_w^{5}}{5!}}\mathbf{e}_{12}-\cdots\\ - \cos(\theta_w)+ \sin(\theta_w) \mathbf{e}_{12} &= 1 \mathbf{e}_{12}^0+\theta_w\mathbf{e}_{12}^1+{\frac {\theta_w^{2}}{2!}}\mathbf{e}_{12}^2+{\frac {\theta_w^{3}}{3!}}\mathbf{e}_{12}^3+{\frac {\theta_w^{4}}{4!}}\mathbf{e}_{12}^4+{\frac {\theta_w^{5}}{5!}}\mathbf{e}_{12}^5-\cdots\\ + &= 1 \mathbf{e}_{12}^0+\theta_w\mathbf{e}_{12}^1+{\frac {\theta_w^{2}}{2!}}\mathbf{e}_{12}^2+{\frac {\theta_w^{3}}{3!}}\mathbf{e}_{12}^3+{\frac {\theta_w^{4}}{4!}}\mathbf{e}_{12}^4+{\frac {\theta_w^{5}}{5!}}\mathbf{e}_{12}^5+\cdots + \label{ExponentialGA2} \end{align} -Aus der Reihenentwicklung der Exponentialfunktion folgt nun +dann sieht man die Übereinstimmung mit der Reihenentwicklung der Exponentialfunktion \begin{align} &e^{\theta_w\mathbf{e}_{12}}=\sum _{n=0}^{\infty }{\frac {(\theta_w\mathbf{e}_{12})^{n}}{n!}}={\frac {(\theta_w\mathbf{e}_{12})^{0}}{0!}}+{\frac {(\theta_w\mathbf{e}_{12})^{1}}{1!}}+{\frac {(\theta_w\mathbf{e}_{12})^{2}}{2!}}+{\frac {(\theta_w\mathbf{e}_{12})^{3}}{3!}}+\cdots\\ - &\Rightarrow \mathbf{w} = |w|\mathbf{e}_1 e^{\theta_w \mathbf{e}_{12}} = |w|\mathbf{e}_1\left(\cos(\theta_w)+ \sin(\theta_w) \mathbf{e}_{12}\right) + &\Rightarrow \mathbf{w} = |w|\mathbf{e}_1 e^{\theta_w \mathbf{e}_{12}} = |w|\mathbf{e}_1\left(\cos(\theta_w)+ \sin(\theta_w) \mathbf{e}_{12}\right). \end{align} -Man kann es so interpretieren, dass der Einheitsvektor $\mathbf{e}_1$ um die Länge $|\mathbf{w}|$ gestreckt und um $\theta_w$ gedreht wird. +Man kann die Exponentialform des Vektors ähnlich wie die der komplexen Zahlen interpretieren. Der Einheitsvektor $\mathbf{e}_1$ wird um die Länge $|\mathbf{w}|$ gestreckt und um $\theta_w$ gedreht. +Bei den komplexen Zahlen würden man vom Punkt 1 anstatt $\mathbf{e}_1$ ausgehen. \subsubsection{Vektormultiplikation} -Nun werden wir den Effekt von zwei aneinandergereihten Vektoren $\mathbf{wu}$ betrachten. +Nun werden wir das Produkt von zwei Vektoren $\mathbf{wu}$ \begin{align} - \mathbf{wu} = |\mathbf{w}|\mathbf{e}_1 e^{\theta_w \mathbf{e}_{12}}|u|\mathbf{e}_1 e^{\theta_u \mathbf{e}_{12}} + \mathbf{wu} = |\mathbf{w}|\mathbf{e}_1 e^{\theta_w \mathbf{e}_{12}}|\mathbf{u}|\mathbf{e}_1 e^{\theta_u \mathbf{e}_{12}} \end{align} -Um die beiden $\mathbf{e}_1$ zu kürzen, können wir die Reihenfolge des Exponentialterms mit $\mathbf{e}_1$ wechseln, indem man bei der Gleichung \eqref{e1ausklammern}, anstatt mit $\mathbf{e}_1\mathbf{e}_1\mathbf{e}_2$ mit $\mathbf{e}_2\mathbf{e}_1\mathbf{e}_1$ erweitert. +so umformen, dass wir eine bessere Darstellung erhalten. Wir tauschen dafür zuerst beim Vektor $\mathbf{w}$ die Reihenfolge von +$\mathbf{e}_1$ mit dem Exponentialterm $e^{\theta_w \mathbf{e}_{12}}$, indem wir bei der Gleichung \eqref{e1ausklammern}, anstatt mit $\mathbf{e}_1\mathbf{e}_1\mathbf{e}_2$ mit $\mathbf{e}_2\mathbf{e}_1\mathbf{e}_1$ erweitern \begin{align} - \mathbf{w} = |\mathbf{w}|\left(\cos(\theta_w)+ \sin(\theta_w) \mathbf{e}_2\mathbf{e}_1\right)\mathbf{e}_1 + \mathbf{w} &= |\mathbf{w}|\left(\cos(\theta_w)+ \sin(\theta_w) \mathbf{e}_2\mathbf{e}_1\right)\mathbf{e}_1\\ + &= |\mathbf{w}|e^{\theta_w \mathbf{e}_{21}}\mathbf{e}_1\\ + &= |\mathbf{w}|e^{-\theta_w \mathbf{e}_{12}}\mathbf{e}_1 \end{align} -Da $\mathbf{e}_2\mathbf{e}_1 = -\mathbf{e}_1\mathbf{e}_2$ können wir einfach den Winkel negieren und $e_1e_1 = 1$ kürzen. Die Längen können als Skalare beliebig verschoben werden und die Exponentialterme zusammengefasst werden. +und umstrukturiert wieder in die Vektorproduktformel einsetzen \begin{align} - \mathbf{wu} = |\mathbf{w}||\mathbf{u}|e^{-\theta_w \mathbf{e}_{12}}\mathbf{e}_1\mathbf{e}_1 e^{\theta_u \mathbf{e}_{12}} + \mathbf{wu} = |\mathbf{w}||\mathbf{u}|e^{-\theta_w \mathbf{e}_{12}}\mathbf{e}_1\mathbf{e}_1 e^{\theta_u \mathbf{e}_{12}}\\ + \mathbf{wu} = |\mathbf{w}||\mathbf{u}|e^{(\theta_u-\theta_w) \mathbf{e}_{12}}. \end{align} -\begin{align} - \mathbf{wu} = |\mathbf{w}||\mathbf{u}|e^{(\theta_u-\theta_w) \mathbf{e}_{12}} -\end{align} -der Term $\mathbf{u}^{-1}\mathbf{w}^{-1}$ kann durch die selbe Methode zusammengefasst werden. +Der Term $\mathbf{u}^{-1}\mathbf{w}^{-1}$ \begin{align} \mathbf{u}^{-1}\mathbf{w}^{-1} = \dfrac{1}{|\mathbf{w}||\mathbf{u}|}e^{(\theta_w-\theta_u) \mathbf{e}_{12}} \end{align} -Dabei definieren wir den Winkel zwischen den Vektoren $\mathbf{w}$ und $\mathbf{u}$ als $\theta = \theta_w - \theta_u$. +kann durch die selbe Methode zusammengefasst werden. +Wenn wir den Winkel zwischen den Vektoren $\mathbf{w}$ und $\mathbf{u}$ als $\theta = \theta_w - \theta_u$ definieren erhalten wir +\begin{align}\label{wuExpo} + \mathbf{wu} = |\mathbf{w}||\mathbf{u}|e^{-\theta \mathbf{e}_{12}}\\ + \mathbf{u}^{-1}\mathbf{w}^{-1} = \dfrac{1}{|\mathbf{w}||\mathbf{u}|}e^{\theta \mathbf{e}_{12}} \label{wuExpoInv} +\end{align} +die finale Form der Vektorprodukte. \subsubsection{Umstrukturierte Drehungsgleichung} -Setzten wir nun unsere neuen Erkenntnisse in die Gleichung \eqref{rotGA} ein. +Setzten wir nun unsere neuen Erkenntnisse in die Gleichung \eqref{rotGA} ein \begin{align} - \mathbf{v''} = |\mathbf{w}||\mathbf{u}|e^{-\theta \mathbf{e}_{12}} v \dfrac{1}{|\mathbf{w}||\mathbf{u}|}e^{\theta \mathbf{e}_{12}} + \mathbf{v''} = (|\mathbf{w}||\mathbf{u}|e^{-\theta \mathbf{e}_{12}}) \mathbf{v}( \dfrac{1}{|\mathbf{w}||\mathbf{u}|}e^{\theta \mathbf{e}_{12}}), +\end{align} +erhalten wir durch die Kürzungen der Längen die vereinfachte Drehungsgleichung +\begin{align} + \mathbf{v''} = e^{-\theta \mathbf{e}_{12}} v e^{\theta \mathbf{e}_{12}}. \end{align} -\begin{satz} - Vereinfachte Drehungsgleichung in Exponentialschreibweise - \begin{align} - \mathbf{v''} = e^{-\theta \mathbf{e}_{12}} v e^{\theta \mathbf{e}_{12}} - \end{align} -\end{satz} -Wir wissen nun, dass das diese beidseitige Multiplikation die Länge von $\mathbf{v}$ nicht verändert, da sich die Längen von $\mathbf{w}$ und $\mathbf{u}$ kürzen. Betrachten wir nun den Effekt der Exponentialterme auf $\mathbf{v}$. Dabei Teilen wir den Vektor $\mathbf{v}$ auf in einen Anteil $\mathbf{v_\parallel}$, welcher auf der Ebene $\mathbf{e}_{12}$ liegt, und einen Anteil $\mathbf{v_\perp}$, welcher senkrecht zu der Ebene steht. +Wir wissen nun, dass das diese beidseitige Multiplikation die Länge von $\mathbf{v}$ nicht verändert, da sich die Längen von $\mathbf{w}$ und $\mathbf{u}$ kürzen. Betrachten wir nun den Effekt der Exponentialterme auf $\mathbf{v}$. Dabei Teilen wir den Vektor $\mathbf{v}$ auf in einen Anteil $\mathbf{v_\parallel}$, welcher auf der Ebene $\mathbf{e}_{12}$ liegt, und einen Anteil $\mathbf{v_\perp}$, welcher senkrecht zu der Ebene steht. Wir bekommen durch Einsetzten nun diese Form \begin{align} \label{RotAufPerpPar} - \mathbf{v}'' = e^{-\theta \mathbf{e}_{12}} (\mathbf{v_\perp + v_\parallel}) e^{\theta \mathbf{e}_{12}} + \mathbf{v}'' = e^{-\theta \mathbf{e}_{12}} (\mathbf{v_\perp + v_\parallel}) e^{\theta \mathbf{e}_{12}} = e^{-\theta \mathbf{e}_{12}} \mathbf{v_\perp} e^{\theta \mathbf{e}_{12}} + e^{-\theta \mathbf{e}_{12}} \mathbf{v_\parallel} e^{\theta \mathbf{e}_{12}}. \end{align} +Auf eine allgemeine Herleitung wird hier zwar verzichtet, aber man kann zeigen, dass die Reihenfolge so umstrukturiert werden kann \begin{align} - \mathbf{v}'' = e^{-\theta \mathbf{e}_{12}} \mathbf{v_\perp} e^{\theta \mathbf{e}_{12}} + e^{-\theta \mathbf{e}_{12}} \mathbf{v_\parallel} e^{\theta \mathbf{e}_{12}} + \mathbf{v}'' = \mathbf{v_\perp} e^{-\theta \mathbf{e}_{12}} e^{\theta \mathbf{e}_{12}} + \mathbf{v_\parallel} e^{-(-\theta) \mathbf{e}_{12}} e^{\theta \mathbf{e}_{12}}, \end{align} -Auf eine allgemeine Herleitung wird hier zwar verzichtet, aber man kann zeigen, dass die Reihenfolge so vertauscht werden kann. Der Winkel wird dabei beim parallelen Term negiert. -\begin{align} - \mathbf{v}'' = \mathbf{v_\perp} e^{-\theta \mathbf{e}_{12}} e^{\theta \mathbf{e}_{12}} + \mathbf{v_\parallel} e^{-(-\theta) \mathbf{e}_{12}} e^{\theta \mathbf{e}_{12}} -\end{align} -\begin{align} +dass der Winkel beim parallelen Anteil negiert wird. An der Zusammengefassten Gleichung +\begin{align}\label{RotParPerp} \mathbf{v}'' = \mathbf{v_\perp} + \mathbf{v_\parallel} e^{2\theta \mathbf{e}_{12}} \end{align} -Man kann an dieser Gleichung sehen, dass nur der parallele Anteil des Vektors $\mathbf{v}$ auf der Ebene $\mathbf{e}_{12}$ um $2\theta$ gedreht wird. Der senkrechte Anteil bleibt gleich. Wichtig dabei zu sehen ist, dass nur der Winkel zwischen den Vektoren $\mathbf{w}$ und $\mathbf{u}$ von Bedeutung ist. Die Länge und Richtung der einzelnen Vektoren spielt keine Rolle. -\begin{beispiel} +kann man sehen, dass nur der parallele Anteil $\mathbf{v_\parallel}$ des Vektors $\mathbf{v}$ auf der Ebene $\mathbf{e}_{12}$ um $2\theta$ gedreht wird. Der senkrechte Anteil $\mathbf{v_\perp}$ bleibt gleich. Wichtig dabei zu sehen ist, dass nur der Winkel zwischen den Vektoren $\mathbf{w}$ und $\mathbf{u}$ von Bedeutung ist. Die Länge und Richtung der einzelnen Vektoren spielt keine Rolle. Zeigen wir nun diese Eigenschaften an einem Beispiel +\begin{beispiel} + Gegeben sei ein Vektor $\mathbf{v} = 1\mathbf{e}_1 + 2\mathbf{e}_2 + 3\mathbf{e}_3$ mit zur $\mathbf{e}_{12}$-Ebene parallelen Anteil $\mathbf{v_\parallel} = 1\mathbf{e}_1 + 2\mathbf{e}_2$ und senkrechten Anteil $\mathbf{v_\perp} = 3\mathbf{e}_3$. Zusätzlich sind die Spiegelachsen $\mathbf{u} = \mathbf{e}_1$ und $\mathbf{w} = 2\mathbf{e}_2$ gegeben. Gesucht ist der rotierte Vektor $\mathbf{v}''$. Bestimmen wir als erstes das Vektorprodukt $\mathbf{wu}$ + \begin{align} + \mathbf{wu} = (2\mathbf{e}_2)(\mathbf{e}_1) = -2\mathbf{e}_{12} + \end{align} + und das Produkt der Inversen $\mathbf{u}^{-1}\mathbf{w}^{-1}$ \begin{align} - \begin{split} - \mathbf{v} &= 1\mathbf{e}_1 + 2\mathbf{e}_2 + 3\mathbf{e}_3\quad\Rightarrow\quad \mathbf{v_\parallel} = 1\mathbf{e}_1 + 2\mathbf{e}_2 \quad \mathbf{v_\perp} = 3\mathbf{e}_3\\ - \mathbf{wu} &= 1e^{(-\pi/2) \mathbf{e}_{12}} = 1[\cos(-\pi/2)\mathbf{e}_1+\sin(-\pi/2)\mathbf{e}_2] = -\mathbf{e}_2 \\ - \mathbf{u}^{-1}\mathbf{w}^{-1} &= 1e^{(\pi/2) \mathbf{e}_{12}} = \mathbf{e}_2 - \end{split} + \mathbf{u}^{-1}\mathbf{w}^{-1} = (\dfrac{\mathbf{e}_1}{1^2})(\dfrac{2\mathbf{e}_2}{2^2}) = \dfrac{1}{2}\mathbf{e}_{12}. \end{align} + Der rotierte Vektor $\mathbf{v}''$ können wir nun durch das einsetzten und auflösen der Produkte in die Gleichung \eqref{rotGA} \begin{align} - \begin{split} - \mathbf{v}'' = &(\mathbf{wu})\mathbf{v}(\mathbf{u}^{-1}\mathbf{w}^{-1}) \\ - &-\mathbf{e}_2 (1\mathbf{e}_1 + 2\mathbf{e}_2 + 3\mathbf{e}_3) \mathbf{e}_2 \\ - & -1\mathbf{e}_2\mathbf{e}_1\mathbf{e}_2 - 2\mathbf{e}_2\mathbf{e}_2\mathbf{e}_2 - 3\mathbf{e}_2\mathbf{e}_3\mathbf{e}_2 \\ - & 1\mathbf{e}_2\mathbf{e}_2\mathbf{e}_1 - 2\mathbf{e}_2 + 3\mathbf{e}_2\mathbf{e}_2\mathbf{e}_3 \\ - & 1\mathbf{e}_1 - 2\mathbf{e}_2 + 3\mathbf{e}_3 - \end{split} + \mathbf{v}'' = (\mathbf{wu})\mathbf{v}(\mathbf{u}^{-1}\mathbf{w}^{-1}) &= (-2e_{12})(1\mathbf{e}_1 + \mathbf{e}_2 + 1\mathbf{e}_3)(\dfrac{1}{2}\mathbf{e}_{12})\\ + &= (2\mathbf{e}_2-2\mathbf{e}_1-2\mathbf{e}_{123})(\dfrac{1}{2}\mathbf{e}_{12})\\ + &= -1\mathbf{e}_1 - 1\mathbf{e}_2 + 1\mathbf{e}_3 \end{align} -\end{beispiel} -Man sieht, dass sich der Vektor $\mathbf{v_\parallel}$ sich um $2\cdot90^\circ$ gedreht hat und der Vektor $\mathbf{v_\perp}$ unverändert blieb.
\ No newline at end of file + finden. Aus dem Resultat $\mathbf{v}''= -1\mathbf{e}_1 + 1\mathbf{e}_2 + 1\mathbf{e}_3$ können wir bestätigen, dass + \begin{itemize} + \item die Länge $|\mathbf{v}| = \sqrt{3}$ zur Länge $|\mathbf{v}''|=\sqrt{3}$ gleich blieb. + \item sich der parallele Anteil $\mathbf{v_\parallel}'' = -1\mathbf{e}_1 - 1\mathbf{e}_2$ gedreht hat und der senkrechte Anteil $\mathbf{v_\perp}'' = 1\mathbf{e}_3$ unverändert blieb. + \item der parallele Teil sich genau um $2\theta=180$° gedreht hat. $\theta$ kann übrigens durch die Umformung des Produkt $\mathbf{wu}$ in die Exponentialschreibweise + \begin{align} + &\mathbf{wu} = -2\mathbf{e}_{12} = 2(0-1\mathbf{e}_{12})=2(\cos(\dfrac{-\pi}{2} + \sin(\dfrac{-\pi}{2})\mathbf{e}_{12})) = 2e^{(-\pi/2)\mathbf{e}_{12}} + \end{align} + durch einen Vergleich mir der Formel \eqref{wuExpo} + \begin{align} + \theta = -(\dfrac{-\pi}{2}) = \dfrac{\pi}{2} + \end{align} + ausgelesen werden. + \end{itemize} +\end{beispiel}
\ No newline at end of file diff --git a/buch/papers/clifford/9_KomplexeZahlen.tex b/buch/papers/clifford/9_KomplexeZahlen.tex index 120828b..70107da 100644 --- a/buch/papers/clifford/9_KomplexeZahlen.tex +++ b/buch/papers/clifford/9_KomplexeZahlen.tex @@ -6,18 +6,19 @@ \section{Komplexe Zahlen} \rhead{Komplexe Zahlen} -Die komplexen Zahlen finden eine Vielzahl von Anwendungsgebiete in den Ingenieurwissenschaften. Das liegt daran, weil die komplexen Zahlen Rotationen und Schwingungen gut beschreiben können. Nachdem vorherigen Kapitel überrascht es wahrscheinlich nicht viele, dass es möglich ist komplexe Zahlen in der geometrischen Algebra darzustellen. Sie können durch die geraden Grade der 2 Dimensionalen geometrischen Algebra vollständig beschrieben werden: $G_2^+(\mathbb{R}) \cong \mathbb{C}$. Das bedeutet eine komplexe Zahl kann durch ein Skalar (Grad 0) und einem Bivektor (Grad 2) dargestellt werden. Als Abkürzung nehme ich die Bezeichnung $\mathbf{g}_n \in G_2^+(\mathbb{R})$. +Die komplexen Zahlen finden eine Vielzahl von Anwendungsgebiete in den Ingenieurwissenschaften. Das liegt daran, weil die komplexen Zahlen Rotationen und Schwingungen gut beschreiben können. Nach dem vorherigen Kapitel überrascht es wahrscheinlich nicht viele, dass es möglich ist komplexe Zahlen in der geometrischen Algebra darzustellen. Sie können durch die geraden Grade der 2 Dimensionalen geometrischen Algebra vollständig beschrieben werden: $\mathbf{g}_n \in G_2^+(\mathbb{R}) \cong \mathbb{C}$. Das bedeutet eine komplexe Zahl kann durch ein Skalar (Grad 0) und einem Bivektor (Grad 2) dargestellt werden \begin{align} - a_0 + a_1 j \cong a_0 + a_1 \mathbf{e}_{12} = \mathbf{g}_n\quad a_0, a_1 \in \mathbb{R} + a_0 + a_1 j \cong a_0 + a_1 \mathbf{e}_{12} = \mathbf{g}_n\quad a_0, a_1 \in \mathbb{R}\\ + |r|e^{\theta j} \cong |r|e^{\theta \mathbf{e}_{12}} = \mathbf{g}_n; \quad r, \theta \in \mathbb{R} \end{align} -oder in Polarform. +weil $j$ und $\mathbf{e}_{12}$ beide die Eigenschaft besitzen quadriert $-1$ zu ergeben \begin{align} - |r|e^{\theta j} \cong |r|e^{\theta \mathbf{e}_{12}} = \mathbf{g}_n; \quad r, \theta \in \mathbb{R} + j^2 = -1\quad \mathbf{e}_{12}^2 = -1 \end{align} Man beachte, dass wenn wir, wie bei den komplexen Zahlen, Elemente von $G_2^+(\mathbb{R})$ miteinander Multiplizieren, ist es nicht, wie im Kapitel Rotation bei der Formel (\ref{rotGA})beschrieben, eine Multiplikation von zwei $g_n$ mit einem Vektor. Im zweidimensionalen bewirken beide Multiplikationen grundsätzlich das Gleiche (eine Drehstreckung), aber die Multiplikation von mehreren $g_n$ ist kommutativ, wie wir es von den komplexen Zahlen kennen. \begin{align} \mathbf{g}_1\mathbf{g}_2 = \mathbf{g}_2\mathbf{g}_1 \quad&\Leftrightarrow\quad (a + b \mathbf{e}_{12})(f + g \mathbf{e}_{12}) = (f + g \mathbf{e}_{12})(a + b \mathbf{e}_{12})\\ - \mathbf{g}_1\mathbf{v}\mathbf{g}_2\not= \mathbf{g}_2\mathbf{v}\mathbf{g}_1 \quad&\Leftrightarrow\quad(a + b \mathbf{e}_{12})(x\mathbf{e}_1+y\mathbf{e}_2)(f + g \mathbf{e}_{12}) \not= (a + b \mathbf{e}_{12})(f + g \mathbf{e}_{12})(x\mathbf{e}_1+y\mathbf{e}_2) + \mathbf{g}_1\mathbf{v}\not= \mathbf{v}\mathbf{g}_1 \quad&\Leftrightarrow\quad(a + b \mathbf{e}_{12})(x\mathbf{e}_1+y\mathbf{e}_2)\not= (x\mathbf{e}_1+y\mathbf{e}_2)(a + b \mathbf{e}_{12}) \end{align} Um später die Auswirkung der Quaternionen besser zu verstehen, möchte ich kurz darauf eingehen, was ein $g_n$ für eine Auswirkung auf einen Vektor hat. Wir kennen diesen Effekt schon von den komplexen Zahlen. Wenn eine komplexe Zahl $c_1=a+bj$ mit einer zweiten $c_2=f+gj$ multipliziert wird, dann kann man diese so aufteilen. diff --git a/buch/papers/clifford/Bilder/GimbalLock.png b/buch/papers/clifford/Bilder/GimbalLock.png Binary files differnew file mode 100644 index 0000000..733c535 --- /dev/null +++ b/buch/papers/clifford/Bilder/GimbalLock.png diff --git a/buch/papers/clifford/Bilder/Links.txt b/buch/papers/clifford/Bilder/Links.txt new file mode 100644 index 0000000..8e8edfe --- /dev/null +++ b/buch/papers/clifford/Bilder/Links.txt @@ -0,0 +1,3 @@ +MatrizenGruppen: Vorlesung 10 Drehmatrizen Müller +GimbalLock: https://www.thetechgame.com/News/sid=2444/fifa-12-demo-glitches-causing-youtube-stir/start=10.html +RotSpieg: http://www.math.uni-bremen.de/didaktik/ma/ralbers/Veranstaltungen/MaDenken1313/Material/Kap2KonAbb.pdf
\ No newline at end of file diff --git a/buch/papers/clifford/Bilder/MatrizenGruppen.png b/buch/papers/clifford/Bilder/MatrizenGruppen.png Binary files differnew file mode 100644 index 0000000..398de5a --- /dev/null +++ b/buch/papers/clifford/Bilder/MatrizenGruppen.png diff --git a/buch/papers/clifford/Bilder/RotSpieg.pdf b/buch/papers/clifford/Bilder/RotSpieg.pdf Binary files differnew file mode 100644 index 0000000..c4c107d --- /dev/null +++ b/buch/papers/clifford/Bilder/RotSpieg.pdf diff --git a/buch/papers/clifford/Bilder/RotSpieg.png b/buch/papers/clifford/Bilder/RotSpieg.png Binary files differnew file mode 100644 index 0000000..27a5eb2 --- /dev/null +++ b/buch/papers/clifford/Bilder/RotSpieg.png diff --git a/buch/papers/clifford/Bilder/test.png b/buch/papers/clifford/Bilder/test.png Binary files differnew file mode 100644 index 0000000..1633a2e --- /dev/null +++ b/buch/papers/clifford/Bilder/test.png diff --git a/buch/papers/clifford/packages.tex b/buch/papers/clifford/packages.tex index 8fb4bd9..0d354db 100644 --- a/buch/papers/clifford/packages.tex +++ b/buch/papers/clifford/packages.tex @@ -7,3 +7,5 @@ % if your paper needs special packages, add package commands as in the % following example %\usepackage{packagename} + +\usetikzlibrary{calc,angles,quotes,babel}
\ No newline at end of file diff --git a/buch/papers/erdbeben/Teil_Fabio.tex b/buch/papers/erdbeben/Teil_Fabio.tex new file mode 100644 index 0000000..9f5d092 --- /dev/null +++ b/buch/papers/erdbeben/Teil_Fabio.tex @@ -0,0 +1,202 @@ +\section{Kalman-Filter} +\subsection{Was ist ein Erdbeben?} +Für das Verständnis möchten wir zuerst erklären, was ein Erdbeben genau ist. +Das soll uns helfen, eine Verknüpfung zwischen dem Naturphänomen und der mathematischen Problemstellung herzustellen. + + +Unter einem Erdbeben verstehen wir eine Erschütterung des Erdkörpers. +Dabei reiben zwei tektonische Platten aneinander, welche sich durch die Gesteinsverzahnung gegenseitig blockieren. +Aufgrund dieser Haftreibung entstehen Spannungen, die sich immer mehr bis zum Tipping Point aufbauen. +Irgendwann ist der Punkt erreicht, in dem die Scherfestigkeit der Gesteine überwunden wird. +Wenn dies passiert, entlädt sich die aufgebaute Spannung und setzt enorme Energien frei, die wir als Erdbeben wahrnehmen. + +Ein Erdbeben breitet sich vom Erdbebenherd in allen Richtungen gleich aus. +Vergleichbar ist, wenn man einen Stein in einen Teich wirft und die Wellen beobachten kann, die sich ausbreiten. + +Wir möchten nun mittels Kalman-Filter die Erdbebenbeschleunigung herausfinden. +Die Erdbebenbeschleunigung ist in der Praxis zur Entwicklung von Erdbebengefährdungskarten, sowie der Ausarbeitung von Baunormen für erdbebengerechte Bauweise von Bedeutung. + + +\subsection{Künstliche Erdbebendaten} +Nun möchten wir anhand eines eigenen Beispiels das Kalman-Filter anwenden. +Da wir keine Rohdaten über vergangene Erdbeben zur Hand haben, müssen wir künstliche Daten erzeugen, um sie in das Filter einzugeben und somit den Prozess starten. +Dafür nehmen wir die Formel für harmonisch gedämpfte Schwingungen, die + +\begin{equation} + y = A \sin(\omega t e^{-lambda t}) +\end{equation} + +lautet. + +A ist die Amplitude der Schwingung und beschreibt die Heftigkeit eines Erdbebens, die Magnitude. +Omega repräsentiert die Erdbebenfrequenz, die in der Realität zwischen 1 Hz und 30 Hz beträgt. +Wir wählen als Erwartungswert 15 Herz und für die Standardabweichung 1 Hz. +Lambda ist die Bodendämpfung, für die wir 0.2 wählen. +Wir haben diese Zahl aus der Literatur entnommen, denn sie ist für das Bauwesen bedeutend. +Lambda ist ein Materialparameter von Böden. + +Je grösser Lambda gewählt wird, desto stärker wirkt die Dämpfung der Massenschwingung. +Die Funktion ist zeitabhängig und wir lassen pro Sekunde zehn Messwerte generieren. + +Die Frequenz basiert auf einer random-Funktion, da wir das Erdbeben unberechenbar gestalten möchten. +Mit dem Golay-Filter können wir hohe Frequenz-Anteile in die Berechnung mit einfliessen lassen, anstatt sie abzuschneiden. +Die Bildung eines üblichen Mittelwerts wäre hier weniger geeignet. + +\begin{lstlisting} +freq = sgolayfilt(randn(size(Time)),0,11)*freqstd... ++freqmean; +\end{lstlisting} + +Mit der Frequenz erhalten wir die Winkelbeschleunigung und damit können wir die Amplitude berechnen. + + +\begin{lstlisting} +w = 2 * pi * freq; +a = Amplitude*sin(cumsum(w.*[0;diff(Time)])).*exp(-lambda*Time); +\end{lstlisting} + +Mit der Matlab-Funktion ode45 haben wir eine Funktion gefunden, um die Differentialgleichung aufzulösen. ode45 basiert auf dem Runge-Kutta-Verfahren, einem Einschrittverfahren, bei dem die Lösung ausgehend von einem gegebenen Anfangswert, in einer Näherung gesucht wird. + +\begin{lstlisting} +[T,Y] = ode45(@(t,x)ErzeugteSchwingung(t,x,m,k,d,a,Time),[0 tend], IC, SolverOptions); +\end{lstlisting} + +Grafik einfügen + +In der Grafik erkennen wir in den Sekunden 0 bis 10, dass die Sinuskurve gezackt ist. +Das deutet darauf hin, dass die Frequenz des Erdbebens einen hohen Einfluss auf die Masse des Seismographen hat. +Ab der 10. Sekunde bis zu tend, pendelt sich die Masse in ihre Eigenfrequenz ein und verhält sich unabhängiger vom Erdbeben. + +\subsection{Versuch (bin noch dran)} + +Um den Kalman-Filter auszuprobieren, setzen wir nun Werte ein. +Für die Systemparameter wählen wir m=1.0, D = 0.3 und k = 0.1 und fügen es in die Differentialgleichung + +\begin{equation} + m\ddot x + 2k \dot x + Dx = f +\end{equation} + +ein und erhalten + +\begin{equation} + 1\ddot x + 0.1 \dot x + 0.3x = f +\end{equation} + +\subsection{Matlab Code} + + +\begin{lstlisting} + %% Initialisierte Werte + t0 = 0.00; % Anfangszeit + deltat = 0.01; % Zeitschritt + tend = 50.00; % Endzeit +\end{lstlisting} +Ein natürliches Erdbeben dauert zwischen wenigen Sekunden bis etwa eine Minute an. +50 Sekunden genügen für unsere Daten. +Pro Sekunde erhalten wir 100 Messpunkte, die für den Prozess des Filters eine präzise Anwendung ermöglichen. + +\begin{lstlisting} + % Standard-Abweichungen Prozess + sigmax = 0.05e-3; % Position + sigmav = 0.01e-3; % Geschwindigkeit + sigmaf = 1; % (Äussere) Kraft + + % Standard-Abweichung Messung + sigmam = 0.01e-3; +\end{lstlisting} + +Wir vertrauen dem System und geben kleine Standardabweichungen für die Position, Geschwindigkeit und Kraft ein. +Bei der Messung erwarten wir auch, dass die Sensoren genau funktionieren. +Jedoch hängt das vom Hersteller ab oder muss statistisch ermittelt werden. + + +\begin{lstlisting} + % Systemparameter +m = 1.00; % Masse +D = 0.30; % Federkonstante +k = 0.10; % Dämpfung +\end{lstlisting} +Hier werden die Spezifikationen des Seismographen definiert. + +\begin{lstlisting} +%% Kalmanfilter +% Initialisierung + +% Anfangszustand (Position, Geschwindigkeit, Kraft) +x0 = [0; 0; 0]; + +% Unsicherheit des Anfangszustand +P0 = [0, 0, 0; ... +0, 0, 0; ... +0, 0, 0]; + +% Systemmatrizen +A = [0, 1, 0;... % Dynamikmatrix +-D/m, -2*k/m, 1;... +0, 0, 0]; % Ableitungen von f(t) unbekant. Annahme: 0 +A = expm(A * deltat); + +Q = [sigmax^2, 0, 0;... +0, sigmav^2, 0;... +0, 0, sigmaf^2]; % Prozessrauschen (Covarianz) + + +\begin{lstlisting} +% Messprozess +H = [1, 0, 0]; % Messmatrix +R = sigmam^2; % Messrauschen (Könnte durch Versuche bestimmt werden) +\end{lstlisting} +Tritt ein Erdbeben ein, wird die Position der Masse in die Messmatrix eingetragen. + + +I = eye(3); % Identity matrix (Einheitsmatrix) + +\begin{lstlisting} +% Filterprozess + +% Initialisieren der Variablen +N = length(t); % Anzahl Punkte im Einheitsvektor (= Anzahl Messwerte) +xhat = zeros(3, N); % Matrix mit geschätzten Zuständen + +% Index ':' bedeutet: 'alles' +% Index '(1, :)' bedeutet: 'alles aus der 1. Zeile' + +% Anfangszustand setzen +xhat(:, 1) = x0; +P = P0; +\end{lstlisting} + +\begin{lstlisting} + +% Kalman-Matrizen konvergiert. Vorab-Berechnung in 'genügenden' Iterationen +for idx = 1:100 +Ppred = A * P * A' + Q; % Prädizieren der Kovarianz +S = (H * Ppred * H' + R); % Innovationskovarianz +K = Ppred * H' / S; % Filter-Matrix (Kalman-Gain) +P = (I - K * H) * Ppred; % Aktualisieren der Kovarianz +end +\end{lstlisting} + +In diesem Schritt wird die Kovarianz vorhergesagt, mit der Messung verglichen und nach jeder Berechnung aktualisiert. + +\begin{lstlisting} +% Anfangszustand gegeben +% Erster zu berechnender Wert ist der zweite +for idx = 2:N +% Vorhersage +xpred = A * xhat(:, idx-1); % Prädizierter Zustand aus Bisherigem und System +% Ppred = A * P * A' + Q; % Prädizieren der Kovarianz + +% Korrektur +y = xt(idx) - H * xpred; % Messungen/ Kraft aus System - Vohersage +% S = (H * Ppred * H' + R); % Innovationskovarianz +% K = Ppred * H' / S; + +xhat(:, idx) = xpred + K * y; % Aktualisieren des Systemzustands +% P = (I - K * H) * Ppred; % Aktualisieren der Kovarianz +end +\end{lstlisting} + +\subsection{Resultate} +Grafik einfügen +Wir erkennen, dass wir mit dem Kalman-Filter eine gute Methode gefunden haben, die äussere Beschleunigung zu schätzen. Die Schätzung der nächsten Position der Federmasse liegt immer ziemlich nahe der tatsächlichen Messung. Man muss aber auch berücksichtigen, dass die Federschwingung ziemlich kontrolliert verläuft und das Kalman-Filter somit präzise Vorhersagen treffen kann. diff --git a/buch/papers/erdbeben/main.tex b/buch/papers/erdbeben/main.tex index 83ef295..8f9c8d5 100644 --- a/buch/papers/erdbeben/main.tex +++ b/buch/papers/erdbeben/main.tex @@ -29,8 +29,9 @@ Bilden Sie auch für Formeln kurze Zeilen, einerseits der besseren \input{papers/erdbeben/teil0.tex} \input{papers/erdbeben/teil1.tex} -\input{papers/erdbeben/teil2.tex} -\input{papers/erdbeben/teil3.tex} +%\input{papers/erdbeben/teil2.tex} +%\input{papers/erdbeben/teil3.tex} +\input{papers/erdbeben/Teil_Fabio.tex} \printbibliography[heading=subbibliography] \end{refsection} diff --git a/buch/papers/erdbeben/references.bib b/buch/papers/erdbeben/references.bib index aef5de9..56ca24b 100644 --- a/buch/papers/erdbeben/references.bib +++ b/buch/papers/erdbeben/references.bib @@ -1,35 +1,57 @@ -% -% references.bib -- Bibliography file for the paper erdbeben -% -% (c) 2020 Autor, Hochschule Rapperswil -% +%% This BibTeX bibliography file was created using BibDesk. +%% https://bibdesk.sourceforge.io/ + +%% Created for lukas zogg at 2021-07-17 16:48:19 +0200 + + +%% Saved with string encoding Unicode (UTF-8) + + + +@article{aragher_understanding_2012, + author = {Faragher, Ramsey}, + date-added = {2021-07-17 16:44:00 +0200}, + date-modified = {2021-07-17 16:45:54 +0200}, + journal = { Signal Processing Magazine}, + month = {09}, + number = {5}, + pages = {128--132}, + title = {Understanding the Basis of the Kalman Filter Via a Simple and Intuitive Derivation }, + volume = {29}, + year = {2012}, + Bdsk-File-1 = {YnBsaXN0MDDSAQIDBFxyZWxhdGl2ZVBhdGhZYWxpYXNEYXRhXxByLi4vLi4vLi4vLi4vLi4vLi4vRG93bmxvYWRzL1VuZGVyc3RhbmRpbmcgdGhlIEJhc2lzIG9mIHRoZSBLYWxtYW4gRmlsdGVyIFZpYSBhIFNpbXBsZSBhbmQgSW50dWl0aXZlIERlcml2YXRpb24ucGRmTxECbgAAAAACbgACAAAMTWFjaW50b3NoIEhEAAAAAAAAAAAAAAAAAAAAAAAAAEJEAAH/////H1VuZGVyc3RhbmRpbmcgdGhlICNGRkZGRkZGRi5wZGYAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAP////8AAAAAAAAAAAAAAAAABgACAAAKIGN1AAAAAAAAAAAAAAAAAAlEb3dubG9hZHMAAAIAci86VXNlcnM6bHVrYXN6b2dnOkRvd25sb2FkczpVbmRlcnN0YW5kaW5nIHRoZSBCYXNpcyBvZiB0aGUgS2FsbWFuIEZpbHRlciBWaWEgYSBTaW1wbGUgYW5kIEludHVpdGl2ZSBEZXJpdmF0aW9uLnBkZgAOAK4AVgBVAG4AZABlAHIAcwB0AGEAbgBkAGkAbgBnACAAdABoAGUAIABCAGEAcwBpAHMAIABvAGYAIAB0AGgAZQAgAEsAYQBsAG0AYQBuACAARgBpAGwAdABlAHIAIABWAGkAYQAgAGEAIABTAGkAbQBwAGwAZQAgAGEAbgBkACAASQBuAHQAdQBpAHQAaQB2AGUAIABEAGUAcgBpAHYAYQB0AGkAbwBuAC4AcABkAGYADwAaAAwATQBhAGMAaQBuAHQAbwBzAGgAIABIAEQAEgBwVXNlcnMvbHVrYXN6b2dnL0Rvd25sb2Fkcy9VbmRlcnN0YW5kaW5nIHRoZSBCYXNpcyBvZiB0aGUgS2FsbWFuIEZpbHRlciBWaWEgYSBTaW1wbGUgYW5kIEludHVpdGl2ZSBEZXJpdmF0aW9uLnBkZgATAAEvAAAVAAIAEP//AAAACAANABoAJACZAAAAAAAAAgEAAAAAAAAABQAAAAAAAAAAAAAAAAAAAws=}} + +@url{erdbeben:wikipedia, + author = {https://de.wikipedia.org/wiki/Kalman-Filter}, + date-added = {2021-07-17 16:42:22 +0200}, + date-modified = {2021-07-17 16:43:53 +0200}, + title = {Kalmanfilter}, + urldate = {2021-07-0}} @online{erdbeben:bibtex, + date = {2020-02-06}, + day = {6}, + month = {2}, title = {BibTeX}, url = {https://de.wikipedia.org/wiki/BibTeX}, - date = {2020-02-06}, year = {2020}, - month = {2}, - day = {6} -} + Bdsk-Url-1 = {https://de.wikipedia.org/wiki/BibTeX}} @book{erdbeben:numerical-analysis, - title = {Numerical Analysis}, author = {David Kincaid and Ward Cheney}, - publisher = {American Mathematical Society}, - year = {2002}, - isbn = {978-8-8218-4788-6}, inseries = {Pure and applied undegraduate texts}, - volume = {2} -} + isbn = {978-8-8218-4788-6}, + publisher = {American Mathematical Society}, + title = {Numerical Analysis}, + volume = {2}, + year = {2002}} @article{erdbeben:mendezmueller, - author = { Tabea Méndez and Andreas Müller }, - title = { Noncommutative harmonic analysis and image registration }, - journal = { Appl. Comput. Harmon. Anal.}, - year = 2019, - volume = 47, - pages = {607--627}, - url = {https://doi.org/10.1016/j.acha.2017.11.004} -} - + author = {Tabea M{\'e}ndez and Andreas M{\"u}ller}, + journal = {Appl. Comput. Harmon. Anal.}, + pages = {607--627}, + title = {Noncommutative harmonic analysis and image registration}, + url = {https://doi.org/10.1016/j.acha.2017.11.004}, + volume = 47, + year = 2019, + Bdsk-Url-1 = {https://doi.org/10.1016/j.acha.2017.11.004}} diff --git a/buch/papers/erdbeben/teil0.tex b/buch/papers/erdbeben/teil0.tex index 6e89821..8ac5d6d 100644 --- a/buch/papers/erdbeben/teil0.tex +++ b/buch/papers/erdbeben/teil0.tex @@ -2,21 +2,88 @@ % einleitung.tex -- Beispiel-File für die Einleitung % % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil -% +%% \section{Teil 0\label{erdbeben:section:teil0}} -\rhead{Teil 0} -Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam -nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam -erat, sed diam voluptua \cite{erdbeben:bibtex}. -At vero eos et accusam et justo duo dolores et ea rebum. -Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum -dolor sit amet. - -Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam -nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam -erat, sed diam voluptua. -At vero eos et accusam et justo duo dolores et ea rebum. Stet clita -kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit -amet. +\rhead{Erdbeben} +\section{Erdbebenmessung} +\subsection{Was ist ein Erdbeben} +Fabio +\subsection{Funktion eines Seismograph} +Um ein Erdbeben kenntlich zu machen, werden in der Regel Seismographen mit vielen Sensoren verwendet. +Ein Seismograph besteht im Grunde aus einer federgelagerten Masse. Wirkt eine Bodenerregung auf das Gerät ein, bleibt die gekoppelte Masse stehen aber das Gehäuse schwingt mit. +Relativbewegung des Bodens kann damit als Auslenkung im Zeitverlauf gemessen werden. +In modernen Seismographen wird die Bodenbewegung in alle Richtungen gemessen, sowohl Horizontal als auch Vertikal. +Wir konstruieren uns eine einfachere Version eines Seismographen mit eine Gehäuse, an dem zwei Federn und eine Masse befestigt ist. +Ein Sensor unter der Masse misst die Position, bzw. die Auslenkung der Feder und der Masse. +Dies bedeutet unser Seismograph kann nur in eine Dimension Messwerte aufnehmen. + +\begin{figure} + \begin{center} + \includegraphics[width=5cm]{papers/erdbeben/Apperatur} + \caption{Aufbau des Seismographen mit Gehäuse, Masse, Federn und Sensor} + \end{center} +\end{figure} + +\subsection{Ziel} +Unser Seismograph misst nur die Position der Masse über die Zeit. +Wir wollen jedoch die Beschleunigung $a(t)$ des Boden bzw. die Kraft $f(t)$ welche auf das Gehäuse wirkt bestimmten. +Anhand dieser Beschleunigung bzw. der Krafteinwirkung durch die Bodenbewegung wird später das Bauwerk bemessen. +Dies bedeutet, die für uns interessante Grösse $f(t)$ wird nicht durch einen Sensor erfasst. +Jedoch können wir durch zweifaches ableiten der Positionsmessung $s(t)$ die Beschleunigung der Masse berechnen. +Das heisst: Die Messung ist zweifach Integriert die Kraft $f(t)$ + der Eigendynamik der Masse. +Um die Bewegung der Masse zu berechnen, müssen wir Gleichungen für unser System finden. + +\subsection{Systemgleichung} +Im Fall unseres Seismographen, kann die Differentialgleichung zweiter Ordnung einer gedämpften Schwingung am harmonischen Oszillator verwendet werden. +Diese lautet: +\begin{equation} +m\ddot s + 2k \dot s + Ds = f +\end{equation} +mit den Konstanten $m$ = Masse, $k$ = Dämpfungskonstante und $D$ = Federkonstante. +Um diese nun in die Systemmatrix umzuwandeln, wird die Differentialgleichung zweiter Ordnung substituiert: +\[ {x_1}=s \qquad +{x_2}=\dot s, \qquad\] +Somit entstehen die Gleichungenür die Position $s(t)$ der Masse : +\[ \dot {x_1} = {x_2}\] +und +\[ \dot x_2 = -\frac{D}{m} {x_1} -\frac{2k}{m} {x_2} + \frac{f} {m} \] für die Geschwindigkeit $v(t)$ der Masse. + +Diese können wir nun in der Form +\[ {x_3}=-\frac{D}{m} {s_1} -\frac{2k}{m} {s_2} + \frac{f} {m} \] +auch als Matrix-Vektor-Gleichung darstellen. +Dafür wird die Gleichung in die Zustände aufgeteilt. +Die für uns relevanten Zustände sind die Position der Masse, die Geschwindigkeit der Masse und die äussere Beschleunigung des ganzen System. +Dabei muss unterschieden werden, um welche Beschleunigung es sich handelt. +Das System beinhaltet sowohl eine Beschleunigung der Masse (innere Beschleunigung), als auch eine Beschleunigung der ganzen Apparatur (äussere Beschleunigung). +In unserem Fall wird die äusseren Beschleunigung gesucht, da diese der Erdbebenanregung gleich kommt. +\begin{equation} +\frac{d}{dt} \left(\begin{array}{c} {s_1} \\ {s_2} \end{array}\right) = \left( + \begin{array}{ccc} +0 & 1& 0 \\ +- \frac{D}{m} &-\frac{2k}{m} & \frac{1} {m}\\ +\end{array}\right) \left(\begin{array}{c} {s_1} \\ {s_2} \\ {s_3} \end{array}\right). +\end{equation} + +Durch Rücksubstituion ergibt sich: +\begin{equation} +\frac{d}{dt} \left(\begin{array}{c} s(t) \\ v(t) \end{array}\right) = \left( + \begin{array}{ccc} +0 & 1& 0 \\ +- \frac{D}{m} &-\frac{2k}{m} & \frac{1} {m}\\ +\end{array}\right) \left(\begin{array}{c} s(t)\\ v(t)\\ f(t) \end{array}\right). +\end{equation} +Wir wissen nicht wie sich die Kraft verhält. +Deshalb treffen wir die Annahme, das sich die Kraft über die Beobachtungszeit nicht verändert. +Diese unzutreffende Annahme wird später durch einen grossen Systemfehler kompensiert. +Da die Kraft unbekannt ist, wird die letzte Zeile mit Nullen gefüllt, denn genau diese Werte wollen wir. + + + + + + + + + diff --git a/buch/papers/erdbeben/teil1.tex b/buch/papers/erdbeben/teil1.tex index bb3bdd4..52872f6 100644 --- a/buch/papers/erdbeben/teil1.tex +++ b/buch/papers/erdbeben/teil1.tex @@ -7,128 +7,107 @@ % teil2.tex -- Beispiel-File für teil2 % % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil -% +%% -\section{Kalman Filter} -\subsection{Geschichte} -Das Kalman Filter wurde 1960 von Rudolf Emil Kalman entdeckt und direkt von der NASA für die Appollo Mission benutzt. Der Filter kommt mit wenig Rechenleistung aus und war somit dafür geeignet die Rakete bei der Navigation zu unterstützen. Das Filter schätzt den Zustand eines Systems anhand von Messungen und kann den nächsten Zustand errechnen. Typische Anwendungen des Kalman-Filters sind die Glättung von verrauschten Daten und die Schätzung von Parametern und kommt heutzutage in jedem Satellit, Navigationssystem, Smartphones und Videospielen vor. -\subsection{Wahrscheinlichkeit} -Das Kalman-Filter schätzt den wahrscheinlichsten Wert zwischen zwei Normalverteilungen oder auch Gauss-Verteilung. Die eine Kurve zeigt die errechnete Vorhersage des Zustands, bzw. deren Normalverteilung. Die andere Kurve zeigt die verrauschte Messung des nächsten Zustand, bzw. deren Normalverteilung. Wie man am Beispiel dieser zwei Gauss-Verteilungen sehen kann, ist sowohl der geschätzte Zustand als auch der gemessene Zustand verteilt und haben unterschiedliche Standardabweichungen $\sigma$ und Erwartungswerte $\mu$. +\rhead{Kalman-Filter} + +\section{Kalman-Filter} +Da wir die äussere Kraft nicht direkt messen können, benötigen wir ein Werkzeug, welches aus der gemessenen Position, die Krafteinwirkung auf unsere System schätzt. +Dies ist eine Typische Anwendung für den linearen Kalman-Filter. +Unser Ziel ist es, anhand der Messung die eigentlich interessante Grösse $f$ zu bestimmen. +Dabei wird durch eine deterministische Vorhersage, in dem der Zustand * Eigendynamik des Systems gerechnet. +Die Idee dahinter ist, dass das Kalman-Filter die nicht-deterministische Grösse $f$ anhand der Messung und der Vorhersage zu bestimmen. + +Für mehrere Dimensionen (x,y,z) würde der Pythagoras für das System benötigt werden. +Da sich der Pythagoras bekanntlich nicht linear verhält, kann kein lineares Kalman-Filter implementiert werden. +Da das Kalman-Filter besonders effektiv und einfach für lineare Abläufe geeignet ist, würde eine zweidimensionale Betrachtung den Rahmen dieser Arbeit sprengen. +Für ein nicht-lineares System werden Extended Kalman-Filter benötigt, bei denen die System-Matrix (A) durch die Jacobi-Matrix des System ersetzt wird. +Einfachheitshalber beschränken wir uns auf den linearen Fall, da dadurch die wesentlichen Punkte bereits aufgezeigt werden. +\subsection{Geschichte} +Das Kalman-Filter wurde 1960 von Rudolf Emil Kalman entdeckt und direkt von der NASA für die Appollo Mission benutzt. Der Filter kommt mit wenig Rechenleistung aus und war somit dafür geeignet die Rakete bei der Navigation zu unterstützen. Das Filter schätzt den Zustand eines Systems anhand von Messungen und kann den nächsten Zustand errechnen. Eine typische Anwendungen des Kalman-Filters ist Glättung von verrauschten Daten und die Schätzung von Parametern. Dies kommt heutzutage in jedem Satellit, Navigationssystem, Smartphones und Videospielen vor. +\subsection{Wahrscheinlichkeit} +Das Kalman-Filter schätzt den wahrscheinlichsten Wert zwischen Normalverteilungen. +Dies bedeutet, das Filter schätzt nicht nur den Mittelwert, sondern auch die Standartabweichung. +Da Normalverteilungen dadurch vollständig definiert sind, schätzt ein Kalman-Filter die gesamte Verteilungsfunktion des Zustandes. +Die eine Funktion zeigt die errechnete Vorhersage des Zustands, bzw. deren Normalverteilung. +Die andere Funktion zeigt die verrauschte Messung des nächsten Zustand, bzw. deren Normalverteilung. +Wie man am Beispiel der Gauss-Verteilungen unten sehen kann, ist sowohl der geschätzte Zustand als auch der gemessene Zustand normalverteilt und haben dementsprechend unterschiedliche Standardabweichungen $\sigma$ und Erwartungswerte $\mu$. \begin{figure} \begin{center} \includegraphics[width=5cm]{papers/erdbeben/Gausskurve2.pdf} - \caption{System} + \caption{Zwei Normalerteilungen; Die eine Funktion zeigt die Vorhersage, die andere die Messung} \end{center} \end{figure} - -Um eine genauere Schätzung des Zustandes zu machen, wird nun ein Wert zwischen den beiden Verteilungen gesucht. An diesem Punkt wird nun eine Eigenschaft ausgenutzt. Durch das Multiplizieren zweier Normalverteilungen entsteht eine neue Normalverteilung. - +Um eine genauere Schätzung des Zustandes zu machen, wird nun ein Wert zwischen den beiden Verteilungen berechnet. +Nun wird eine Eigenschaft der Normalverteilung ausgenutzt. Durch das Multiplizieren zweier Normalverteilungen entsteht eine neue Normalverteilung. Wir haben eine Normalverteilung der Vorhersage: -\begin{equation} -{y_1}(x;{\mu_1},{\sigma_1})=\frac{1}{\sqrt{2\pi\sigma_1^2}}\quad e^{-\frac{(x-{\mu_1})^2}{2{\sigma_1}^2}} -\end{equation} -und für die Messung: - -\begin{equation} -{y_2}(x;{\mu_2},{\sigma_2})=\frac{1}{\sqrt{2\pi\sigma_2^2}}\quad e^{-\frac{(x-{\mu_2})^2}{2{\sigma_2}^2}}. -\end{equation} - -Diesen werden nun Multipliziert und durch deren Fläche geteilt um sie wieder zu Normieren: -\begin{equation} -{y_f}(x;{\mu_f},{\sigma_f})=\frac{ \frac{1}{\sqrt{2\pi\sigma_1^2}}e^{-\frac{(x-{\mu_1})^2}{2{\sigma_1}^2}} \cdot \frac{1}{\sqrt{2\pi\sigma_2^2}}e^{-\frac{(x-{\mu_2})^2}{2{\sigma_2}^2}}}{\int {y_1}*{y_2} dx\,} -\end{equation} - -Dadurch gleicht sich die neue Kurve den anderen an. Interessant daran ist, dass die fusionierte Kurve sich der genauere Normal-Verteilung anpasst. ist ${\sigma_2}$ klein und ${\sigma_1}$ gross, so wird sich die fusionierte Kurve näher an ${y_2}(x;{\mu_2},{\sigma_2})$ begeben. Sie ist also gewichtet und die best mögliche Schätzung. +\[ {y_1}(x;{\mu_1},{\sigma_1})=\frac{1}{\sqrt{2\pi\sigma_1^2}}\quad e^{-\frac{(x-{\mu_1})^2}{2{\sigma_1}^2}} \] +und der Messung: +\[ {y_2}(x;{\mu_2},{\sigma_2})=\frac{1}{\sqrt{2\pi\sigma_2^2}}\quad e^{-\frac{(x-{\mu_2})^2}{2{\sigma_2}^2}}. \] -\begin{figure} - \begin{center} - \includegraphics[width=5cm]{papers/erdbeben/Gausskurve3.pdf} - \caption{System} - \end{center} -\end{figure} - -Was in 2 Dimensionen erklärt wurde, funktioniert auch in mehreren Dimensionen. Dieses Prinzip mach sich der Kalman Filter zu nutze, und wird von uns für die Erdbeben Berechnung genutzt. +Diesen werden nun Multipliziert und durch deren Fläche geteilt um sie wieder zu Normieren: +\[ +{y_f}(x;{\mu_f},{\sigma_f})=\frac{ \frac{1}{\sqrt{2\pi\sigma_1^2}}e^{-\frac{(x-{\mu_1})^2}{2{\sigma_1}^2}} \cdot \frac{1}{\sqrt{2\pi\sigma_2^2}}e^{-\frac{(x-{\mu_2})^2}{2{\sigma_2}^2}}}{\int {y_1}\cdot{y_2} dx\,} + \] +Diese Kombination der beiden Verteilungen resultiert wiederum in einer Normalverteilung +\[ {y_f}(x; {\mu_f}, {\sigma_f}) = {y_1}(x;{ \mu_1},{ \sigma_1}) {\cdot y_2}(x; {\mu_2}, {\sigma_2}), \] +mit Erwartungswert +\[ \mu_f = \frac{\mu_1\sigma_2^2 + \mu_2 \sigma_1^2}{\sigma_1^2 + \sigma_2^2} \] +und Varianz +\[ \sigma_f^2 = \frac{\sigma_1^2 \sigma_2^2}{\sigma_1^2 + \sigma_2^2}. \] +Dadurch gleicht sich die neue Kurve den anderen an. Interessant daran ist, dass die fusionierte Kurve sich der genauere Normal-Verteilung anpasst. +Ist ${\sigma_2}$ klein und ${\sigma_1}$ gross, so wird sich die fusionierte Kurve näher an ${y_2}(x;{\mu_2},{\sigma_2})$ begeben. +Sie ist also gewichtet und die best mögliche Schätzung. -\section{Aufbau} -Um ein Erdbeben kenntlich zu machen werden in der Regel Seismographen mit vielen Sensoren verwendet. -Ein Seismograph besteht im Grunde aus einer federgelagerten Masse. Wirkt eine Bodenerregung auf das Gerät ein, bleibt die gekoppelte Masse stehen und das Gehäuse schwingt mit.Relativbewegung des Bodens kann damit als Längenänderung im Zeitverlauf gemessen werden. In modernen Seismographen wird die Bodenbewegung in alle Richtungen gemessen, sowohl Horizontal als auch Vertikal. -Wir konstruieren uns eine einfachere Version eines Seismographen, welcher rein mechanisch funktioniert. Zudem kann er nur in eine Dimension Messwerte aufnehmen. Würde das System ausgebaut werden, um alle Horizontalbewegungen aufzunehmen, würde der Verwendung des Kalman-Filters zu kompliziert werden. Für zwei Dimensionen (x,y) würde der Pythagoras für das System benötigt werden. Da sich der Pythagoras bekanntlich nicht linear verhält, kann kein lineares Kalman-Filter implementiert werden. Da das Kalman-Filter besonders effektiv und einfach für lineare Abläufe geeignet ist, würde eine Zweidimensionale Betrachtung den Rahmen dieser Arbeit sprengen. Für ein nicht-lineares System werden Extended Kalman-Filter benötigt, bei denen die System-Matrix (A) durch die Jacobi-Matrix des System ersetzt wird. Einfachheitshalber beschränken wir uns aber auf den linearen Fall, da dadurch die wesentlichen punkte bereits aufgezeigt werden. \begin{figure} \begin{center} - \includegraphics[width=5cm]{papers/erdbeben/Apperatur} - \caption{System} + \includegraphics[width=5cm]{papers/erdbeben/Gausskurve3.pdf} + \caption{Durch das Multiplizieren der blauen und der orangen Verteilung entsteht die die rote, optimale Funktion} \end{center} \end{figure} +Was in 2 Dimensionen erklärt wurde, funktioniert auch in mehreren Dimensionen. +Dieses Prinzip mach sich das Kalman Filter zu nutze, und wird von uns für die Erdbeben Berechnung genutzt. -\section{Systemgleichung} -Da das Kalman-Filter zum Schätzen des nächsten Zustand verwendet wird, benötigt das Kalman-Filter eine Beschreibung der Systemdynamik. Im Fall unseres Seismographen, kann die Differentialgleichung zweiter Ordnung einer gedämpften Schwingung am harmonischen Oszillator verwendet werden. Diese lautet: -\begin{equation} -m\ddot x + 2k \dot x + Dx = f -\end{equation} -mit den Konstanten $m$ = Masse, $k$ = Dämpfungskonstante und $D$ = Federkonstante. - -Um diese nun in die Systemmatrix umzuwandeln, wird aus der Differentialgleichung zweiter Ordnung durch die Substitution
\[ {x_1}=x, \qquad -{x_2}=\dot x, \qquad -{x_3}=\ddot x\qquad\]
erhalten wir die Differentialgleichung
\[ m{x_3}+ 2k{x_2} + D{x_1} = f.\]
Diese können wir nun in der Form
\[ {x_3}=-\frac{D}{m} {x_1} -\frac{2k}{m} {x_2} + \frac{f} {m} \]
auch als Matrix-Vektor-Gleichung darstellen.
- - -Dafür wird die Gleichung in die Zustände aufgeteilt. Die für uns relevanten Zustände sind die Position der Masse, die Geschwindigkeit der Masse und die äussere Beschleunigung des ganzen System. Dabei muss unterschieden werden, um welche Beschleunigung es sich handelt. Das System beinhaltet sowohl eine Beschleunigung der Masse bzw. Feder (innere Beschleunigung), als auch eine Beschleunigung der ganzen Apparatur (äussere Beschleunigung). In unserem Fall wird die äusseren Beschleunigung gesucht, da diese der Erdbeben Anregung gleich kommt. - - -\begin{equation} -\frac{d}{dt} \left(\begin{array}{c} {x_1} \\ {x_2} \end{array}\right) = \left( - \begin{array}{ccc} -0 & 1& 0 \\ -- \frac{D}{m} &-\frac{2k}{m} & \frac{1} {m}\\ -\end{array}\right) \left(\begin{array}{c} {x_1} \\ {x_2} \\ {x_3} \end{array}\right). -\end{equation} - -Durch die Rücksubstituion ergibt sich: -\begin{equation} -\frac{d}{dt} \left(\begin{array}{c} x(t) \\ v(t) \end{array}\right) = \left( - \begin{array}{ccc} -0 & 1& 0 \\ -- \frac{D}{m} &-\frac{2k}{m} & \frac{1} {m}\\ -\end{array}\right) \left(\begin{array}{c} x(t)\\ v(t)\\ f(t) \end{array}\right). -\end{equation} - - -Da die Kraft unbekannt ist, wird die letzte Zeile später mit Nullen bestückt, denn genau diese Werte wollen wir. - -\section{Kalman Filter} -Um den Kalman Filter zu starten, müssen gewisse Bedingungen definiert werden. In diesem Abschnitt werden die einzelnen Parameter/Matrizen erläutert und Erklärt, wofür sie nützlich sind. - +\section{Filter-Matrizen} +Um den Kalman Filter zu starten, müssen gewisse Bedingungen definiert werden. +In diesem Abschnitt werden die einzelnen Parameter und Matrizen erklärt und erläutert, wofür sie nützlich sind. \subsection{Anfangsbedingungen} \subsubsection*{Anfangszustand $x$} -Das Filter benötigt eine Anfangsbedingung. In unserem Fall ist es die Ruhelage, die Masse bewegt sich nicht. Zudem erfährt die Apparatur keine äussere Kraft. +Das Filter benötigt eine Anfangsbedingung. +In unserem Fall ist es die Ruhelage, die Masse bewegt sich nicht. +Zudem erfährt die Apparatur keine äussere Kraft. + -\begin{equation} -{x_0 }= \left( \begin{array}{c} 0\\ 0\\ 0\end{array}\right) -\end{equation} +\[ {x_0 }= \left( \begin{array}{c} {s_0}\\ {v_0}\\{f_0}\end{array}\right) = \left( \begin{array}{c} 0\\ 0\\ 0\end{array}\right) \] \subsubsection*{Anfangsfehler / Kovarianzmatrix $P$} -Da auch der Anfangszustand fehlerhaft sein kann, wird für den Filter einen Anfangsfehler eingeführt. Auf der Diagonalen werden die Varianzen eingesetzt, in den restlichen Felder stehen die Kovarianzen. -Zur Erinnerung: Die Varianz ist ein Mass für die Streuung eines Wertes, die Kovarianz hingegen beschreibt die Abhängigkeit der Streuungen zweier Werte.
Kovarianz: Cov(x, y) undVarianz: Var(x) = Cov(x, x) +Da auch der Anfangszustand fehlerhaft sein kann, wird für das Filter ein Anfangsfehler verwendet. +Auf der Diagonalen werden die Varianzen eingesetzt, in den restlichen Felder stehen die Kovarianzen. +Zur Erinnerung: Die Varianz ist ein Mass für die Streuung eines Wertes, die Kovarianz hingegen beschreibt die Abhängigkeit der Streuungen zweier Werte. -In unserem Fall ist der Anfangszustand gut bekannt. Wir gehen davon aus, dass das System in Ruhe und in Abwesenheit eines Erdbeben startet, somit kann die Matrix mit Nullen bestückt werden. Somit ergibt sich für die Kovarianzmatrix +Kovarianz: Cov(x, y) und Varianz: Var(x) = Cov(x, x) -\begin{equation} +In unserem Fall ist der Anfangszustand gut bekannt. +Wir gehen davon aus, dass das System in Ruhe und in Abwesenheit eines Erdbeben startet, somit kann die Matrix mit Nullen bestückt werden. +Als Initialwert für die für die Kovarianzmatrix ergibt sich + +\[ {P_0 }= \left( \begin{array}{ccc} @@ -137,232 +116,150 @@ In unserem Fall ist der Anfangszustand gut bekannt. Wir gehen davon aus, dass da 0 & 0 &0 \\ \end{array} \right). -\end{equation} -Diese Matrix beschreibt die Unsicherheit des geschätzten Zustandes und wird sowohl für die Vorhersage als auch die Korrektur benötigt. Sie wird nach jeder Schätzung aktualisiert.. Für einen gut bekannten Zustandsvektor können kleine Werte eingesetzt werden, für ungenaue Anfangsbedingungen sollten grosse Werte (1 Million) verwendet werden. Grosse Werte ermöglichen dem Filter sich schnell einzupendeln. - + \] +Diese Matrix beschreibt die Unsicherheit des geschätzten Zustandes und wird sowohl für die Vorhersage als auch die Korrektur benötigt. +Sie wird nach jeder Schätzung aktualisiert. +Für einen gut bekannten Zustandsvektor können kleine Werte eingesetzt werden, für ungenaue Anfangsbedingungen sollten grosse Werte verwendet werden. +Grosse Werte ermöglichen dem Filter sich schnell einzupendeln. \subsubsection*{Dynamikmatrix $A$} -Die Dynamikmatrix bildet den Kern des Filters. Diese wurde weiter oben Bereits beschrieben. Dabei wollen wird die äussere Kraft des Systems ermitteln. -Da nichts über die äussere Kraft bekannt ist, müssen wir annehmen das deren Ableitung 0 ist. +Das Kalman-Filter benötigt für die Vorhersage des nächsten Zustandes eine Beschreibung der Systemdynamik. +Die Dynamikmatrix bildet den Kern des Filters. Diese wurde weiter oben bereits beschrieben. +Dabei wollen wird die äussere Kraft des Systems ermitteln. +Da nichts über die äussere Kraft bekannt ist, müssen wir annehmen das deren Ableitung 0 ist. Die System Vektor-Gleichung lautet daher: - - -\begin{equation} +\[ A = \left( \begin{array}{ccc} 0 & 1& 0 \\ - \frac{D}{m} &-\frac{2k}{m} & \frac{1} {m}\\ 0 & 0& 0\\ \end{array}\right) -\end{equation} + \] +Dabei soll der Kalman-Filter in diskreten Zeitschritten $\Delta t$ arbeiten. +Die Übergangs-Matrix erhalten wir aus der Systemdynamikmatrix mittels Exponentialfunktion: +\[\Phi = \exp(A\Delta t). \] \subsubsection*{Prozessrauschkovarianzmatrix $Q$} -Die Prozessrauschmatrix teilt dem Filter mit, wie sich der Systemzustand verändert. Kalman-Filter berücksichtigen Unsicherheiten wie Messfehler und -rauschen. Bei unserem Modell könnte das beispielsweise ein Windstoss an die Masse sein. Für uns wäre dies: -\begin{equation} +Die Prozessrauschmatrix teilt dem Filter mit, wie sich der Prozess verändert. +Kalman-Filter berücksichtigen Unsicherheiten wie Messfehler und -rauschen. +Bei unserem Modell könnte das beispielsweise ein Windstoss an die Masse sein. +Für uns wäre dies: +\[ Q = \left( \begin{array}{ccc} -{\sigma_x }^2& 0& 0 \\ +{\sigma_s }^2& 0& 0 \\ 0 & {\sigma_v }^2& 0\\ 0 & 0& {\sigma_f }^2\\ \end{array}\right) -\end{equation} + \] -Die Standabweichungen müssten Statistisch ermittelt werden, da der Fehler nicht vom Sensor kommt und somit nicht vom Hersteller gegeben ist. Das Bedeutet wiederum dass $Q$ die Unsicherheit des Prozesses beschreibt, und die der Messung. +Die Standabweichungen müssten statistisch ermittelt werden, da der Fehler nicht vom Sensor kommt und somit nicht vom Hersteller gegeben ist. +Das Bedeutet wiederum dass $Q$ die Unsicherheit des Prozesses beschreibt und nicht die der Messung. \subsubsection*{Messmatrix $H$} -Die Messmatrix gibt an, welche Parameter gemessen werden soll. In unserem Falle ist es nur die Position der Massen. +Die Messmatrix gibt an, welche Parameter gemessen werden +In unserem Falle ist es die Position der Massen. \[ H = (1, 0, 0) \] - \subsubsection*{Messrauschkovarianz $R$} -Die Messrauschkovarianzmatrix beinhaltet, wie der Name es schon sagt, das Rauschen der Positionssensoren. In unserem Fall wird nur die Position der Masse gemessen. Da wir keine anderen Sensoren haben ist $R$ lediglich: -\begin{equation} -R= ({\sigma_x}^2). -\end{equation} -Diese Messrauchen wird meistens vom Sensorhersteller angegeben. Für unsere Theoretische Apparatur wird hier ein kleiner Fehler eingesetzt. - -\subsection{Fiter Algorithmus} -Nachdem alle Parameter aufgestellt sind, wird der Filter initialisiert und wird den Zustand der Feder vorherzusagen, die Messung zu präzisieren und laufend zu aktualisieren. Das Filter berechnet aufgrund der aktuellen Schätzung eine Vorhersage. Diese wird, sobald verfügbar, mit der Messung verglichen. Aus dieser Differenz und den Unsicherheiten des Prozesses ($Q$) und der Messung ($R$) wird der wahrscheinlichste, neue Zustand geschätzt. - +Die Messrauschkovarianzmatrix beinhaltet, wie der Name es schon sagt, das Rauschen der Positionsmessung. +In unserem Fall wird nur die Position der Masse gemessen. Da wir keine anderen Sensoren haben ist $R$ lediglich: +\[ R= ({\sigma_{sensor}}^2). + \] +Diese Messrauchen wird meistens vom Sensorhersteller angegeben. +Für unsere Theoretische Apparatur wird hier ein kleiner Fehler eingesetzt da heutige Sensoren sehr genau messen können. + +\subsection{Fiter-Agorithmus} +Nachdem alle Parameter aufgestellt sind, wird das Filter initialisiert. +Zuerst wird der nächste Zustand der Feder vorhergesagt, danach wird die Messung präzisiert und laufend zu aktualisieren. +Das Filter berechnet aufgrund der aktuellen Schätzung eine Vorhersage. +Diese wird, sobald verfügbar, mit der Messung verglichen. +Aus dieser Differenz und den Unsicherheiten des Prozesses ($Q$) und der Messung ($R$) wird der wahrscheinlichste, neue Zustand geschätzt. \subsubsection*{Vorhersage} -Im Filterschritt Vorhersage wird der nächste Zustand anhand des Anfangszustand und der Systemmatrix berechnet. Dies funktioniert mit dem Rechenschritt: -\begin{equation} -{x_{t+1}}=A\cdot{x_t}. -\end{equation} +Im Filterschritt Vorhersage wird der nächste Zustand anhand des Anfangszustand und der Systemmatrix berechnet. +Dies funktioniert mit dem Rechenschritt: +\[ +{x_{k|k-1}}=\Phi \cdot {x_{k-1|k-1}}= \exp(A\Delta t)\cdot{x_{k|k-1}}. + \] + +Die Kovarianz $P_{pred}$ wird ebenfalls neu berechnet. Da wir ein mehrdimensionales System haben, kommt noch die Prozessunsicherheit $Q$ dazu, so dass die Unsicherheit des Anfangsfehlers $P$ laufend verändert. +Dies funktioniert durch multiplizieren der Systemmatrix mit dem aktualisierten Anfangsfehler. +Dazu wird noch die Prozessunsicherheit addiert, somit entsteht die Gleichung +\[ {P_{k|k-1}} = {\Phi_k} {P_{k-1|k-1}} {\Phi_k} ^T + {Q_{k-1}} .\] +Es vergeht genau $dt$ Zeit, und dieser Vorgang wird wiederholt. +Dabei wird in den späteren Schritten überprüft, wie genau die letzte Anpassung von $P$ zur Messung stimmt. +Ist der Unterschied klein, wird die Kovarianz $P$ kleiner, ist der Unterschied gross, wird auch die Kovarianz grösser. +Das Filter passt sich selber an und korrigiert sich bei grosser Abweichung. +\subsubsection*{Messen} +Der Sensor wurde noch nicht benutz, doch genau der liefert Werte für das Filter. +Die aktuellen Messwerte $z$ werden die Innovation $w$ mit dem Zustandsvektor $x$ und der Messmatrix $H$ zusammengerechnet. +Hier bei wird lediglich die Messung mit dem Fehler behaftet, und die Messmatrix $H$ mit der Vorhersage multipliziert -Die Kovarianz $P_{pred}$ wird ebenfalls neu berechnet. Da wir ein mehrdimensionales System haben, kommt noch die Prozessunsicherheit $Q$ dazu, so dass die Unsicherheit des Anfangsfehlers $P$ laufend verändert. Dies funktioniert durch multiplizieren der Systemmatrix mit dem aktualisierten Anfangsfehler. Dazu wird noch die Prozessunsicherheit addiert, somit entsteht die Gleichung -\[ P_\mathrm{pred} = A P A^T + Q . \] - -wird dieser Vorgang wiederholt, schaut der Filter wie genau die letzte Anpassung von $P$ zur Messung stimmt. Ist der Unterschied klein, wird die Kovarianz $P$ kleiner, ist der Unterschied gross, wird auch die Kovarianz grösser. Das Filter passt sich selber an und korrigiert sich bei grosser Abweichung. +\[{w_{k}}={z_{k}}-{H_{k}}\cdot{x_{k|k-1}}.\] -\subsubsection*{Messen} -Der Sensor wurde noch nicht benutz, doch genau der liefert Werte für den Filter. Die aktuellen Messwerte $z$ werden die Innovation $w$ mit dem Zustandsvektor $x$ und der Messmatrix $H$ zusammengerechnet. -Hier bei wird lediglich die Messung mit dem Fehler behaftet, und die Messmatrix $H$ -\begin{equation} -w=Z-(H\cdot x) -\end{equation} -Die Innovation ist der Teil der Messung, die nicht durch die Systemdynamik erklärt werden kann. Die Hilfsgröße Innovation beschreibt, wie genau der vorhergesagte Mittelwert den aktuellen Messwert mittels der Beobachtungsgleichung beschreiben kann. Für eine schlechte Vorhersage wird die dazugehörige Innovation gross, für eine genaue Vorhersage dagegen klein sein. Entsprechende Korrekturen müssen dann gross bzw. nur gering ausfallen. Innovation = Messung - Vorhersage. Dies ist intuitiv logisch, eine Innovation von 0 bedeutet, dass die Messung nichts Neues hervorbrachte. +Die Innovation ist der Teil der Messung, die nicht durch die Systemdynamik erklärt werden kann. +Die Hilfsgröße Innovation beschreibt, wie genau die Vorhersage den aktuellen Messwert mittels der Systemmatrix $\phi$ beschreiben kann. +Für eine schlechte Vorhersage wird die dazugehörige Innovation gross, für eine genaue Vorhersage dagegen klein sein. +Entsprechende Korrekturen müssen dann gross bzw. nur gering ausfallen. +Innovation = Messung - Vorhersage. Dies ist intuitiv logisch, eine Innovation von 0 bedeutet, dass die Messung nichts Neues hervorbrachte. Im nächsten Schritt wir analysiert, mit welcher Kovarianz weiter gerechnet wird. Hierbei wird die Unsicherheit $P$, die Messmatrix $H$ und die Messunsicherheit $R$ miteinander verrechnet. -\begin{equation} -S=Z-(H\cdot P\cdot H`+R) -\end{equation} - +\[ +{S_{k}}={H_{k}}{P_{k|k-1}}{H_{k}}^T+{R_{k}} + \] \subsubsection*{Aktualisieren} Im nächsten Schritt kommt nun die Wahrscheinlichkeit nach Gauss dazu. - -\begin{equation} -K= \frac{P \cdot H`}S -\end{equation} -Dieser Vorgang wird Kalman-Gain genannt. Er sagt aus, welcher Kurve mehr Vertraut werden soll, dem Messwert oder der Systemdynamik. -Das Kalman-Gain wird geringer wen der Messwert dem vorhergesagten Systemzustand entspricht. Sind die Messwerte komplett anders als die Vorhersage, wo werden die Elemente in der Matrix $K$ grösser. - +\[ +{K_{k}}= {{P_{k|k-1}} \cdot {H_{k}^T}}\cdot {S_{k}}^{-1} + \] +Dieser Vorgang wird Kalman-Gain genannt. +Er sagt aus, welcher Kurve mehr Vertraut werden soll, dem Messwert oder der Systemdynamik. +Das Kalman-Gain wird geringer wen der Messwert dem vorhergesagten Systemzustand entspricht. +Sind die Messwerte komplett anders als die Vorhersage, wo werden die Elemente in der Matrix $K$ grösser. Anhand der Informationen aus dem Kalman-Gain $K$ wird das System geupdated. -\begin{equation} -x=x+(K \cdot w) -\end{equation} +\[ +{x_{k|k}}={x_{k|k-1}}+({K_{k}}\cdot {w_{k}}) + \] Dazu kommt eine neue Kovarianz für den nächste Vorhersageschritt: -\begin{equation} -P=(I-(K \cdot H)) \cdot P -\end{equation} +\[ +{P_{k|k}}=(I-({K_{k}} \cdot {H_{k}})) \cdot {P_{k|k-1}} + \] Der ganze Ablauf wird nun zum Algorithmus und beginnt wieder mit der Vorhersage -\begin{equation} -{x_{t+1}}=e^{A\Delta t}{ x_t}. -\end{equation} +\[ +{x_{k|k-1}}=\Phi \cdot {x_{k-1|k-1}}= \exp(A\Delta t)\cdot{x_{k|k-1}}. + \] \subsection{Zusammenfassung } -Zusammenfassend kann das Kalman-Filter in offizieller Typus dargestellt werden. Dabei beginnt das Filter mit dem Anfangszustand für $k=0$ +Zusammenfassend kann das Kalman-Filter in offizieller Typus dargestellt werden. +Dabei beginnt das Filter mit dem Anfangszustand für $k=0$ 1. Nächster Zustand vorhersagen -\begin{equation} -{x_{k|k-1}}={A_{k-1}}{x_{k-1}}+{B_{k-1}}{u_{k-1}} -\end{equation} +\[{x_{k|k-1}}=\Phi \cdot {x_{k-1|k-1}}= \exp(A\Delta t)\cdot{x_{k|k-1}}.\] 2. Nächste Fehlerkovarianz vorhersagen -\begin{equation} -{P_{k|k-1}}={A_{k-1}}{P_{k-1}}{A_{k-1}^T}+{Q_{k-1}} -\end{equation} - +\[{P_{k|k-1}}={\Phi _{k}} {P_{k-1|k-1}} {\Phi _{k}}^T + {Q_{k-1}}.\] 3. Das Kalman Filter anwenden -\begin{equation} -{K_k}={P_{k-1}}{H_{k}^T({H_k}{P_{k|k-1}}{H_k}^T}+{R_k})^{-1} -\end{equation} +\[{K_{k}}= {P_{k|k-1}} \cdot {H_{k}^T}\cdot {S_{k}^{-1}}\] 4. Schätzung aktualisieren -\begin{equation} -{x_k}={x_{k|k-1}}+{K_k}({z_k}-{H_k}{x_{k|k-1}}) -\end{equation} +\[{x_{k|k}}={x_{k|k-1}}+({K_{k}}\cdot {w_{k}}) \] 5. Fehlerkovarianz aktualisieren -\begin{equation} -{P_k}=(I-{K_k}{H_k}){P_{k|k-1}} -\end{equation} - -6. Die Outputs von $k$ werden die Inputs für ${k-1}$ und werden wieder im Schritt 1 verwendet - - -\section{Matlab-Code} -Um das simulierte Erdbeben auf die theoretische Apparatur zu bringen und mit dem Kalman-Filter Resultate zu generieren, wurde in Matlab der Algorithmus programmiert. -\begin{lstlisting} -%% Initialisierte Werte -t0 = 0.00; % Anfangszeit -deltat = 0.01; % Zeitschritt -tend = 50.00; % Endzeit - -% Standard-Abweichungen Prozess -sigmax = 0.05e-3; % Position -sigmav = 0.01e-3; % Geschwindigkeit -sigmaf = 1; % (Äussere) Kraft - -% Standard-Abweichung Messung -sigmam = 0.01e-3; - -% Systemparameter -m = 1.00; % Masse -D = 0.30; % Federkonstante -k = 0.10; % Dämpfung - - -%% Kalmanfilter -% Initialisierung - - -% Anfangszustand (Position, Geschwindigkeit, Kraft) -x0 = [0; 0; 0]; - -% Unsicherheit des Anfangszustand -P0 = [0, 0, 0; ... - 0, 0, 0; ... - 0, 0, 0]; - -% Systemmatrizen -A = [0, 1, 0;... % Dynamikmatrix - -D/m, -2*k/m, 1;... - 0, 0, 0]; % Ableitungen von f(t) unbekant. Annahme: 0 -A = expm(A * deltat); - -Q = [sigmax^2, 0, 0;... - 0, sigmav^2, 0;... - 0, 0, sigmaf^2]; % Prozessrauschen (Covarianz) - -% Messprozess -H = [1, 0, 0]; % Messmatrix -R = sigmam^2; % Messrauschen (Könnte durch Versuche bestimmt werden) - -I = eye(3); % Identity matrix (Einheitsmatrix) - -% Filterprozess - -% Initialisieren der Variablen -N = length(t); % Anzahl Punkte im Einheitsvektor (= Anzahl Messwerte) -xhat = zeros(3, N); % Matrix mit geschätzten Zuständen - -% Index ':' bedeutet: 'alles' -% Index '(1, :)' bedeutet: 'alles aus der 1. Zeile' - -% Anfangszustand setzen -xhat(:, 1) = x0; -P = P0; - -% Kalman-Matrizen konvergiert. Vorab-Berechnung in 'genügenden' Iterationen -for idx = 1:100 - Ppred = A * P * A' + Q; % Prädizieren der Kovarianz - S = (H * Ppred * H' + R); % Innovationskovarianz - K = Ppred * H' / S; % Filter-Matrix (Kalman-Gain) - P = (I - K * H) * Ppred; % Aktualisieren der Kovarianz -end - -% Anfangszustand gegeben -% Erster zu berechnender Wert ist der zweite -for idx = 2:N - % Vorhersage - xpred = A * xhat(:, idx-1); % Prädizierter Zustand aus Bisherigem und System - % Ppred = A * P * A' + Q; % Prädizieren der Kovarianz - - % Korrektur - y = xt(idx) - H * xpred; % Messungen/ Kraft aus System - Vohersage - % S = (H * Ppred * H' + R); % Innovationskovarianz - % K = Ppred * H' / S; - - xhat(:, idx) = xpred + K * y; % Aktualisieren des Systemzustands - % P = (I - K * H) * Ppred; % Aktualisieren der Kovarianz -end -\end{lstlisting} - - - +\[{P_{k|k}}=(I-({K_{k}}\cdot {H_{k}})) \cdot {P_{k|k-1}} \] +6. Die Outputs von $k$ werden die Inputs für ${k-1}$ und werden wieder im Schritt 1 verwendet diff --git a/buch/papers/reedsolomon/anwendungen.tex b/buch/papers/reedsolomon/anwendungen.tex new file mode 100644 index 0000000..c03b1a4 --- /dev/null +++ b/buch/papers/reedsolomon/anwendungen.tex @@ -0,0 +1,159 @@ +% +% anwendungen.tex -- Anwendungen des Reed-Solomon-Codes +% +% (c) 2021 Michael Steiner, Hochschule Rapperswil +% +\section{Anwendungen des Reed-Solomon-Codes + \label{reedsolomon:section:anwendung}} +\rhead{Anwendungen} + +In den vorherigen Abschnitten haben wir betrachtet, wie Reed-Solomon-Codes in der Theorie Funktionieren. +In diesem Abschnitt werden wir einige Anwendungen vorstellen, bei denen ein Reed-Solomon-Code zum Einsatz kommt. + +Dabei teilen all diese Anwendungen das gleiche Problem: Die Daten können nur durch einen (höchst Wahrscheinlichen) fehlerbehafteten Kanal empfangen werden. Es gibt keine andere Methode an diese Daten zu kommen als über diesen Kanal. + + +In der Netzwerktechnik zum Beispiel ist es üblich, dass bei Paketverluste oder beschädigt empfangene Datenpakete diese einfach noch einmal inert wenigen Millisekunden angefordert werden können. +In der Raumfahrt ist dies nicht möglich, da aufgrund der beschränkten Speichermöglichkeit die gesammelten Daten so rasch wie möglich zur Erde gesendet werden. +Diese Daten wiederum brauchen aufgrund der grossen Distanz Stunden bis die Daten beim Empfänger ankommen. +Fehlerhafte Daten kann also auf Grund der Zeitverzögerung nicht mehr angefordert werden. + +Bei CDs oder DVDs gibt es zwar kein Zeitliches Problem, jedoch erschweren Kratzer, Verschmutzungen oder Produktionsfehler das Lesen einer solchen Disk. +Da vor allem Produktionsfehler und Kratzer irreversibel sind und die Disk nicht nach jedem Kratzer ersetzt werden muss, so wird die korrekte Ausgabe der gespeicherten Information durch die Fehlerkorrektur sichergestellt. + +Ein ähnlicher Ansatz verfolgen QR-Codes, wobei die Information auch dann noch gelesen werden kann wenn der Code nicht mehr vollständig vorhanden ist. + +%Wie man sieht, eignen sich Reed-Solomon-Codes vor allem für Anwendungen, bei der die Informationen nicht auf einen Anderen Weg beschafft werden kann. +% +% +%, bei denen die Wahrscheinlichkeit hoch ist, dass während der Übertragung +% +%Es ist deshalb umso wichtiger die Daten Codiert zu lesen um so gleich die Lesefehler zu korrigieren. +% +% da aufgrund der grossen Distanz Stunden vergehen können bis gesendete Daten auf der Erde empfangen werden kann. +% + + +Obwohl alle diese Codes nach dem gleichen Prinzip arbeiten gibt es starke Unterschiede in deren Funktionsweise. +Dies kommt vor allem daher, da die Codes nur Ressourcen zur Verfügung haben, die von der Hardware bereitstellt wird, auf denen die Codes implementiert wurden. +Diese Codes bedienen sich daher verschiedener Tricks und Optimierungen um möglichst effizient zu arbeiten. + +Um die Fähigkeit eines verwendeten Reed-Solomon-Codes zu beschreiben verwendet man die Notation ($n$,$k$), wobei $n$ die Grösse des Nachrichtenblocks angibt und $k$ die Anzahl der Stellen, die für Nutzdaten gebraucht werden können. + +%Dies kommt vor allem daher, da diese Codes an ihre Hardware gebunden sind, auf denen sie implementiert worden sind. +%Deshalb wurden diese Codes stark optimiert damit sie möglichst Effizient arbeiten können. +% +%Um diese Hardware möglichst effizient zu nutzen wurden gewisse mathematische tricks angewendet um den Code möglichst effizient zu nutzen. +% +% um mit maximaler Effizienz zu arbeiten. +%Es überrascht daher nicht, dass vor allem ältere Codes im binären Körper $\mathbb{F}_{2}$ arbeiten. +% +% um den Code mit maximaler Effizienz zu nutzen. +% +%Alle diese Anwendungen verfügen über eigene spezifizierten Eigenschaften. +% +%, wobei bei allen dieser Anwendungen jeweils eine unterschiedliche Version des Codes implementiert wurden. +% +%Dies kommt vor allem daher, da diese Codes immer an ihre dementsprechende Hardware gebunden sind, auf denen sie implementiert wurden um den Code mit maximaler Effizienz zu nutzen. +% +% eigene Version des Codes implementiert haben. +% +%Bei einer Technischen Umsetzung eines solchen Codes werden wir auf eine reihe neuer Probleme stossen wie Ressourceneffizienz, Laufzeitoptimierung, usw. +% +%Hinzu kommt, dass für verschiedene Anwendungen verschiedene Versionen des Reed-Solomon-Codes zur Anwendung kommen. +% +%Nachfolgend werden wir ein paar dieser Anwendungen Vorstellen, da sich herausstellt, dass Reed-Solomon-Code sehr +% +%Als letzte Frage stellt sich jetzt nur noch, wo diese Codes eingesetzt werden. +% +%Bisher haben wir +% +%In den letzten abschnitten haben wir uns ausführlich die Funktionsweise des Reed-Solomon-Codes angeschaut. In diesem Abschnitt möchten wir dem Leser ein paar bekannte beispiele vorstellen, in denen Reed-Solomon-Codes zum einsatz kommen. Es sei jedoch angemerkt, dass diese Anwendungen in der Umsetzung oft ein wenig anderst funktionieren als hier vorgestellt. Dies wurde vor allem wegen technischen optimierungen realisiert. (technische tricks und finessen), von der logik jedoch sehr stark an unserem Beispiel orientieren + +\subsection{Raumfahrt} +Obwohl Reed-Solomon-Codes bereits in den 1960er entwickelt wurden fanden sie erstmals Anwendung in der Voyager Raumsonde der NASA. Die Daten der zwei im Jahre 1977 gestarteten Sonden (siehe Abbildung \ref{fig:voyager}) werden mit einem ($255$,$233$)-Code +Codiert. +Der Nachrichtenblock hat somit eine Länge von $255$ Zahlen, wovon $233$ als Nutzlast zur Verfügung stehen. +Damit ist es möglich bis zu $11$ Fehler im Nachrichtenblock zu korrigieren. +Der Codierte Nachrichtenblock wird in kleinere Blöcke aufgeteilt, mit einem Faltungscode erneut Codiert und anschliessend gesendet. Ein Faltungscode ist wie ein Reed-Solomon-Code in der Lage Fehler zu korrigieren, Funktioniert aber nach einem ganz anderen Prinzip. +Durch diese doppelte Codierung wird eine äusserst hohe Übertragungssicherheit garantiert. +% +%Dabei steht die Zahl 255 für grösse des Nachrichtenblocks, der die Anzahl 233 +% +% +% \textcolor{red}{benötigt das weitere Erklärungen, wie z.b. 255: grösse Nachrichtenblock, 233: anzahl der nutzbaren daten ?} zusammen mit einem konventionellen Faltungscode übertragen. Eine von der Sonde gesendete Nachricht hat eine Blockgrösse von 255 Zeichen, wovon 233 für die Nutzdaten gebraucht werden können. Dieser Code ist somit in der Lage 11 Fehler in einem Nachrichtenblock zu korrigieren. +% +% Die zwei im Jahre 1977 gestarteten Sonden senden Daten mit der Hilfe eines RS(255,233)-Code für die digitalen Bilder sowie einem konventionellen Faltungscode. +% +% +%mit der Erde mit einem RS(255,233)-Code für die digitalen Bilder sowie einem konventionellen Faltungscode. + +\begin{figure} + \centering + \includegraphics[width=0.5\textwidth]{papers/reedsolomon/images/Voyager_Sonde} + \caption{Mit einer Entfernung von über 22.8 Milliarden Kilometer ist die Voyager 1 Raumsonde das am weitesten entfernte, von Menschen erschaffene Objekt. Obwohl ihre Schwestersonde Voyager 2 zuerst ins All gestartet wurde befindet Sie sich ``nur'' 19 Milliarden Kilometer weit weg von der Erde. Aufgrund abnehmender Batterieleistung werden die beiden Sonden ihre wissenschaftlichen Aktivitäten etwa 2025 einstellen, bleiben aber bis in die 2030er mit uns in Kontakt.} + \label{fig:voyager} +\end{figure} + +\subsection{CD/DVD} +Compact discs verwenden sogar zwei ineinander verschachtelte Reed-Solomon-Codes, einen (32,28)-Code und einen (28,24)-Code. +Beide Codes sind in der Lage, Fehler aus dem jeweils anderen gelesenen Block zu korrigieren. Dieses spezielle Zusammenspielen dieser beiden Codes werden auch Cross-interleaved Reed-Solomon-Codes (CIRC) genannt. +Diese Vorgehensweise erzielt eine hohe Robustheit gegenüber Produktionsfehlern oder Verschmutzung auf der Disc. Bei CDs sind diese in der Lage, bis zu 4000 fehlerhafte Bits am Stück (ca. $2.5mm$) zu erkennen und zu korrigieren. + +Die Digital Video Disc funktioniert nach dem selben Konzept mit grösseren Codeblöcken. Die DVD verwendet einen (208,192)-Code und einen (182,172)-Code. + +%Beide lesen +% wobei beide Codes auch Fehler aus dem jeweiligen anderen Block korrigieren + +\begin{figure} + \centering + \includegraphics[width=0.5\textwidth]{papers/reedsolomon/images/Compact_Disc} + \caption{CDs kamen 1982 auf den Markt. Sie funktioniert durch das ``einbrennen'' von Punkten und Strichen, die die Daten repräsentieren. Gelesen werden diese wiederum durch die Reflektion eines Lasers an diesen Punkten und Strichen.} + \label{fig:cd} +\end{figure} + +\subsection{QR-Codes} +Quick Response Codes oder auch QR-Codes funktionieren nach einem sehr ähnlichen Prinzip wie in unserem Beispiel der Abschnitte \ref{reedsolomon:section:codebsp} - \ref{reedsolomon:section:rekonstruktion} nur das QR-Codes in einem $\mathbb{F}_{256}$ Körper arbeiten. Die Physische Grösse eines Codes ist stark abhängig von der Grösse der Codierung sowie dem Fehlerkorrektur-Level. Es ist so auf dem ersten Blick nicht ersichtlich, wie viel Nutzinformationen ein Qr-Code enthält. Die QR-Codes in Abbildung \ref{fig:qr} zeigen jeweils die Gleiche Information mit unterschiedlichem Fehlerkorrektur-Level. Codes mit einem höheren Korrektur-Level können auch für Designer-Codes Zweckentfremdet werden. Dabei wird z.B. das Firmenlogo oder einen Schriftzug über den Qr-Code gelegt, ohne das die Funktion des Codes beeinträchtigt wird. Ein Beispiel dazu ist unter Abbildung \ref{fig:designqr} zu finden. + +% + +%So kann auf den ersten Blick nicht +% +% +% funktionieren nach einem sehr ähnlichen Prinzip wie in unserem Beispiel, nur dass QR-Codes in einem $\mathbb{F}_{256}$ Körper arbeiten. Je nach grösse der Codierung ist der QR-Code im Endeffekt robuster gegen Beschädigungen. Bei Low Level Codes können 7\% der Daten Wiederhergestellt werden, beim High Level Code sind das sogar 30\%. + +\begin{figure} + \centering + \subfigure[]{ + \includegraphics[width=0.4\textwidth]{papers/reedsolomon/images/qrcode_h} + } + \subfigure[]{ + \includegraphics[width=0.4\textwidth]{papers/reedsolomon/images/qrcode_l} + } +% \subfigure[]{ +% \includegraphics[width=0.4\textwidth]{papers/reedsolomon/images/designer_qrcode_ohnelogo} +% } +% \subfigure[]{ +% \includegraphics[width=0.4\textwidth]{papers/reedsolomon/images/designer_qrcode} +% } + \caption{Anhand der grösse würde man darauf schliessen, dass bei (a) mehr Informationen Codiert sind als bei (b). Tatsächlich aber beinhalten beide Codes die gleiche Information. Das liegt daran, da die Fehlerkorrekturfähigkeit von QR-Codes sich in insgesamt vier Levels aufteilen lassen. Der höchste Fehlerkorrektur-Level, der bei (a) angewendet wurde, ist in der Lage, bis zu 30\% der Daten wiederherzustellen. Der kleinste Level schafft etwa 7\%, der in (b) veranschaulicht wird. Da die Grösse also nichts über die Menge an Daten aussagt, könnte es sich bei (a) auch um einen Code mit viel Nutzdaten und kleinem Fehlerkorrektur-Level handeln. Der Unterschied ist von Auge nicht sichtbar.} + \label{fig:qr} +\end{figure} + +\begin{figure} + \centering +% \subfigure[]{ +% \includegraphics[width=0.4\textwidth]{papers/reedsolomon/images/qrcode_h} +% } +% \subfigure[]{ +% \includegraphics[width=0.4\textwidth]{papers/reedsolomon/images/qrcode_l} +% } + \subfigure[]{ + \includegraphics[width=0.4\textwidth]{papers/reedsolomon/images/designer_qrcode_ohnelogo} + } + \subfigure[]{ + \includegraphics[width=0.4\textwidth]{papers/reedsolomon/images/designer_qrcode} + } + \caption{Während (a) noch ein unveränderter QR-Code repräsentiert, handelt es sich bei (b) nun um einen Designer-QR-Code. Beide Codes verfügen über einen mittleren Fehlerkorrektur-Level von theoretisch 15\%. Da bei (b) jetzt einen Teil des Codes durch ein Logo verdeckt wird, schränkt sich dadurch die Fehlerkorrekturfähigkeit je nach grösse des verdeckten Teils mehr oder weniger stark ein. Unser Designer-Code in (b) ist nur noch in der Lage etwa 9\% des Codes zu rekonstruieren.} + \label{fig:designqr} +\end{figure}
\ No newline at end of file diff --git a/buch/papers/reedsolomon/codebsp.tex b/buch/papers/reedsolomon/codebsp.tex index 0339d9c..8430ebd 100644 --- a/buch/papers/reedsolomon/codebsp.tex +++ b/buch/papers/reedsolomon/codebsp.tex @@ -1,17 +1,16 @@ % -% teil3.tex -- Beispiel-File für Teil 3 +% codebsp.tex -- Codierung eines Beispiels % -% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil +% (c) 2021 Michael Steiner, Hochschule Rapperswil % \section{Codierung eines Beispiels \label{reedsolomon:section:codebsp}} \rhead{Codierung eines Beispiels} -Um die Funktionsweise eines Reed-Solomon-Codes besser zu verstehen werden wir die einzelnen Probleme und ihre Lösungen anhand eines Beispiels betrachten. -Da wir in endlichen Körpern rechnen, werden wir zuerst solch einen Körper festlegen. Dabei müssen wir die \textcolor{red}{Definition 4.6 (verweis auf eine Definition im Buch ohne label)} berücksichtigen, die besagt, dass nur Primzahlen für endliche Körper in Frage kommen. +Um die Funktionsweise eines Reed-Solomon-Codes besser zu verstehen, werden wir die einzelnen Probleme und ihre Lösungen anhand eines Beispiels betrachten. +Da wir in endlichen Körpern rechnen, werden wir zuerst solch einen Körper festlegen. Dabei müssen wir die Definition \ref{buch:endlichekoerper:def:galois-koerper} berücksichtigen, die besagt, dass nur Primzahlen für endliche Körper in Frage kommen. Wir legen für unser Beispiel den endlichen Körper $\mathbb{F}_{q}$ mit $q = 11$ fest. -Zur Hilfestellung können dazu die beiden Tabellen \ref{reedsolomon:subsection:adtab} und -\ref{reedsolomon:subsection:mptab} hinzugezogen werden. Diese Tabellen enthalten die Resultate der arithmetischen Operationen im Körper $\mathbb{F}_{11}$, die durchgeführt werden können. +Zur Hilfestellung zum Rechnen in $\mathbb{F}_{11}$ können die beiden Tabellen \ref{reedsolomon:subsection:adtab} und \ref{reedsolomon:subsection:mptab} hinzugezogen werden. Diese Tabellen enthalten die Resultate der arithmetischen Operationen im Körper $\mathbb{F}_{11}$, die durchgeführt werden können. Aus der Definition der endlichen Körper (ersichtlich auch in den Tabellen) folgt, dass uns nur die Zahlen \[\mathbb{F}_{11} = \{0,1,2,3,4,5,6,7,8,9,10\}\] zur Verfügung stehen und somit $11 = 0$ gelten muss. % OLD TEXT @@ -78,15 +77,16 @@ dar. \label{reedsolomon:subsection:diskFT}} In einem vorherigen Abschnitt \textcolor{red}{(???)} haben wir schon einmal die diskrete Fouriertransformation zum Codieren einer Nachricht verwendet. In den endlichen Körpern wird dies jedoch nicht gelingen, da die Eulerische Zahl $e$ in endlichen Körpern nicht existiert. -Wir wählen deshalb eine Zahl $a$, die die gleichen Aufgaben haben soll wie $e^{\frac{j}{2 \pi}}$ in der diskreten Fouriertransformation, nur mit dem Unterschied, dass $a$ in $\mathbb{F}_{11}$ ist. Dazu soll die Potenz von $a$ den gesamten Zahlenbereich von $\mathbb{F}_{11}$ abdecken, um +Wir wählen deshalb eine Zahl $a$, die die gleichen Aufgaben haben soll wie $e^{\frac{j}{2 \pi}}$ in der diskreten Fouriertransformation, nur mit dem Unterschied, dass $a$ in $\mathbb{F}_{11}$ ist. Dazu soll die Potenz von $a$ den gesamten Zahlenbereich von $\mathbb{F}_{11}$ abdecken. +Dazu ändern wir die Darstellung von \[ \mathbb{F}_{11} = \{0,1,2,3,4,5,6,7,8,9,10\} \] -in +in die von $a$ abhängige Schreibweise \[ \mathbb{Z}_{11}\setminus\{0\} = \{a^0, a^1, a^2, a^3, a^4, a^5, a^6, a^7, a^8, a^9\}. \] -umzuschreiben. +%Jetzt brauchen wir nur noch eine geeignete Zahl für $a$ zu finden. % Old Text %Wir suchen also eine Zahl $a$, die in endlichen Körpern existiert und den gesamten Zahlenbereich von $\mathbb{F}_{11}$ abdecken kann. %Dazu schreiben wir @@ -116,7 +116,7 @@ umzuschreiben. \subsubsection{Die primitiven Einheitswurzeln \label{reedsolomon:subsection:primsqrt}} -Wenn wir jetzt sämtliche Zahlen von $\mathbb{F}_{11}$ in $a$ einsetzen +Wenn wir jetzt Zahlen von $\mathbb{F}_{11}$ an Stelle von $a$ einsetzen, erhalten wir \begin{center} \begin{tabular}{c c c c c c c} $a = 1$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1, 1, 1, 1, 1, 1, 1, 1, 1, 1\}$ & $\neq$ & $\mathbb{F}_{11}\setminus\{0\}$ \\ @@ -128,7 +128,7 @@ $a = 6$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1, 6, 3, 7, 9, 1 $a = 7$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1, 7, 5, 2, 3, 10, 4, 6, 9, 8\}$ & $ = $ & $\mathbb{F}_{11}\setminus\{0\}$ \\ $a = 8$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1, 8, 9, 6, 4, 10, 3, 2, 5, 7\}$ & $ = $ & $\mathbb{F}_{11}\setminus\{0\}$ \\ $a = 9$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1, 9, 4, 3, 5, 1, 9, 4, 3, 5\}$ & $\neq$ & $\mathbb{F}_{11}\setminus\{0\}$ \\ -$a = 10$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1, 10, 1, 10, 1, 10, 1, 10, 1, 10\}$ & $\neq$ & $\mathbb{F}_{11}\setminus\{0\}$ \\ +$a = 10$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1, 10, 1, 10, 1, 10, 1, 10, 1, 10\}$ & $\neq$ & $\mathbb{F}_{11}\setminus\{0\}$. \\ \end{tabular} \end{center} %\begin{center} @@ -146,13 +146,15 @@ $a = 10$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1, 10, 1, 10, 1 %$a = 10 :$& $\qquad \mathbb{Z}_{11}\setminus\{0\}$ &$=$& $\{1, 10, 1, 10, 1, 10, 1, 10, 1, 10\}$ %\end{tabular} %\end{center} -so fällt uns auf, dass für $a$ die Zahlen $2,6,7,8$ erhalten, die tatsächlich den gesamten Zahlenraum von $\mathbb{F}_{11}$ abbilden. Solche Zahlen werden \em primitive Einheitswurzel \em genannt. +Es fällt auf, dass wir für $a$ die Zahlen $2,6,7,8$ Mengen erhalten, die tatsächlich den gesamten Zahlenraum von $\mathbb{F}_{11}$ abbilden. Solche Zahlen werden \em primitive Einheitswurzel \em genannt. Wenden wir diese Vorgehensweise auch für andere endliche Körper an, so werden wir sehen, dass wir immer mindestens zwei solcher Einheitswurzel finden werden. Somit ist es uns überlassen, eine dieser Einheitswurzel auszuwählen, mit der wir weiter rechnen wollen. Für das Beispiel wählen wir die Zahl $a = 8$. \subsubsection{Bildung einer Transformationsmatrix \label{reedsolomon:subsection:transMat}} -Mit der Wahl einer Einheitswurzel ist es uns jetzt möglich, unsere Nachricht zu Codieren. Daraus sollen wir dann einen Übertragungsvektor $v$ erhalten, den wir an den Empfänger schicken können. Für die Codierung müssen wir alle $a^i$ in das Polynom $m(X)$ einsetzen. Da wir $a^i = 8^i$ gewählt haben, ergibt sich daraus +Mit der Wahl einer Einheitswurzel ist es uns jetzt möglich, unsere Nachricht zu Codieren. Daraus sollen wir dann einen Übertragungsvektor $v$ erhalten, den wir an den Empfänger schicken können. +Für die Codierung setzen wir alle Zahlen in $\mathbb{F}_{11}\setminus\{0\}$ nacheinander in $m(X)$ ein. Da wir zuvor eine von $a$ abhängige Schreibweise gewählt haben setzen wir stattdessen $a^i$ ein mit $a = 8$ als die von uns gewählten primitiven Einheitswurzel. Daraus ergibt sich +%Für die Codierung müssen wir alle $a^i$ in das Polynom $m(X)$ einsetzen. Da wir $a^i = 8^i$ gewählt haben, ergibt sich daraus % %Damit wir unsere Nachricht codieren können, müssen wir $8^i$ in $m(X)$ einsetzen. % @@ -168,7 +170,7 @@ als unser Übertragungsvektor. \subsection{Allgemeine Codierung \label{reedsolomon:subsection:algCod}} -Um das Ganze noch ein wenig übersichtlicher zu gestalten können wir die Polynome zu einer Matrix zusammenfassen, die unsere Transformationsmatrix $A$ bildet. +Um das Ganze noch ein wenig übersichtlicher zu gestalten, können wir die Polynome zu einer Matrix zusammenfassen, die unsere Transformationsmatrix $A$ bildet. Für die allgemeine Codierung benötigen wir die Nachricht $m$, die codiert werden soll, sowie die Transformationsmatrix $A$. Daraus erhalten wir den Übertragungsvektor $v$. Setzen wir die Zahlen aus dem Beispiel ein erhalten wir folgende Darstellung: \[ diff --git a/buch/papers/reedsolomon/decmitfehler.tex b/buch/papers/reedsolomon/decmitfehler.tex index a46d7da..598cf68 100644 --- a/buch/papers/reedsolomon/decmitfehler.tex +++ b/buch/papers/reedsolomon/decmitfehler.tex @@ -1,7 +1,7 @@ % -% teil3.tex -- Beispiel-File für Teil 3 +% decmitfehler.tex -- Decodierung mit Fehler % -% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil +% (c) 2021 Michael Steiner, Hochschule Rapperswil % \section{Decodierung: Ansatz mit Fehlerkorrektur \label{reedsolomon:section:decmitfehler}} @@ -16,7 +16,7 @@ Der Übertragungskanal im Beispiel weisst jetzt den Fehlervektor u = [0, 0, 0, 3, 0, 0, 0, 0, 2, 0] \] auf. -Senden wir jetzt unser Übertragungsvektor $v$ durch diesen Kanal addiert sich der Fehlervektor $u$ auf unsere Übertragung und wir erhalten +Senden wir jetzt unser Übertragungsvektor $v$ durch diesen Kanal, addiert sich der Fehlervektor $u$ auf unsere Übertragung und wir erhalten \begin{center} \begin{tabular}{c | c r } @@ -127,7 +127,7 @@ Setzen wir jetzt unsere Einheitswurzel aus dem Beispiel ein so erhalten wir \end{tabular} \end{center} und damit die Information, dass allen Stellen, die nicht Null sind, Fehler enthalten. -Aus der Tabelle lesen wir, das in unserem Beispiel die Fehler an der Stelle drei und acht zu finden sind. +Aus der Tabelle lesen wir ab, das in unserem Beispiel die Fehler an der Stelle drei und acht zu finden sind. Für das einfache Bestimmen von Hand mag dies ja noch ausreichen, jedoch können wir mit diesen Stellen nicht das Lokatorpolynom bestimmen, denn dafür bräuchten wir alle Nullstellen, an denen es Fehler gegeben hat (also sozusagen genau das umgekehrte). Um dies zu erreichen wenden wir eine andere Herangehensweise und nehmen uns den Satz von Fermat sowie den kleinsten gemeinsamen Teiler zur Hilfe. @@ -140,7 +140,7 @@ f(X) = X^{q-1} -1 = 0 \] gilt für jedes $X$. Setzen wir das $q$ von unserem Beispiel ein \[ -f(X) = X^{10}-1 = 0 \qquad \text{für } X = \{1,2,3,4,5,6,7,8,9,10\} +f(X) = X^{10}-1 = 0 \qquad \text{für } X \in \{1,2,3,4,5,6,7,8,9,10\} \] und stellen dies als Faktorisierung dar. So ergibt sich die Darstellung \[ @@ -173,7 +173,7 @@ Das kgV hat nämlich die Eigenschaft sämtliche Nullstellen zu finden, also nich ersichtlich ist. Aus dem vorherigen Abschnitt wissen wir auch, dass $d(X)$ alle korrekten Nullstellen beinhaltet. Teilen wir das kgV jetzt auf in \[ -\operatorname{kgV}(f(X),d(X)) = d(X) \cdot l(X) +\operatorname{kgV}(f(X),d(X)) = d(X) \cdot l(X), \] sollten wir für $l(X)$ eine Liste mit allen fehlerhaften Nullstellen erhalten. Somit ist @@ -192,14 +192,16 @@ In Abschnitt \ref{reedsolomon:section:decmitfehler} haben wir d(X) = r(X) - m(X) \] in Abhängigkeit von $m(X)$ berechnet. -Jedoch haben wir ausser acht gelassen, dass $m(X)$ auf der Empfängerseite nicht existiert und somit gänzlich unbekannt ist. +Jedoch haben wir ausser acht gelassen, dass $m(X)$ auf der Empfängerseite nicht verfügbar und somit gänzlich unbekannt ist. Es scheint so als würde dieser Lösungsansatz, den wir bisher verfolgt haben, nicht funktioniert. -Wir könnten uns höchstens noch fragen, ob wir tatsächlich nichts über den Nachrichtenvektor im Beispiel wissen. Wenn wir noch einmal den Vektor betrachten als +Wir könnten uns höchstens noch fragen, ob wir tatsächlich nichts über den Nachrichtenvektor im Beispiel wissen. + +Wenn wir noch einmal den Vektor betrachten als \[ m = [0,0,0,0,4,7,2,5,8,1] \] -fällt uns aber auf, dass wir doch etwas über diesen Vektor wissen, nämlich den Wert der ersten $2t$ (im Beispiel vier) stellen. -Im Normalfall sollen diese nämlich den Wert null betragen und somit sind nur die letzten $k$ stellen (im Beispiel sechs) für uns unbekannt, dargestellt als +fällt uns aber auf, dass wir doch etwas über diesen Vektor wissen, nämlich den Wert der ersten $2t$ (im Beispiel vier) Stellen. +Im Normalfall sollen diese nämlich den Wert $0$ haben und somit sind nur die letzten $k$ Stellen (im Beispiel sechs) für uns unbekannt, dargestellt als \[ m = [0,0,0,0,?,?,?,?,?,?]. \] diff --git a/buch/papers/reedsolomon/decohnefehler.tex b/buch/papers/reedsolomon/decohnefehler.tex index 0470db0..50bd8d6 100644 --- a/buch/papers/reedsolomon/decohnefehler.tex +++ b/buch/papers/reedsolomon/decohnefehler.tex @@ -1,7 +1,7 @@ % -% teil3.tex -- Beispiel-File für Teil 3 +% decohnefehler.tex -- Decodierung ohne Fehler % -% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil +% (c) 2021 Michael Steiner, Hochschule Rapperswil % \section{Decodierung: Ansatz ohne Fehler \label{reedsolomon:section:decohnefehler}} @@ -33,11 +33,12 @@ Definiert ist sie als \[ F(\omega) = \int_{-\infty}^{\infty} f(t) \mathrm{e}^{-j\omega t} dt \qquad \Rightarrow \qquad \mathfrak{F}^{-1}(F(\omega)) = f(t) = \frac{1}{2 \pi} \int_{-\infty}^{\infty} F(\omega) \mathrm{e}^{j \omega t} d\omega. \] -Damit beschäftigen wir uns im Abschnitt \ref{reedsolomon:subsection:sfaktor} weiter, konkret suchen wir momentan aber eine Inverse für unsere primitive Einheitswurzel $a$. +Im wesentlichen ändert sich bei der inversen diskreten Fouriertransformation $e^{j/2\pi}$ zu $e^{-j/2\pi}$. Zusätzlich benötigt die inverse noch einen Korrekturfaktor $1/n$. Wir erwarten daher, dass wir auch im endlichen Körper $A$ die Zahl $a$ durch $a^{-1}$ ersetzen können. Mit der primitiven Einheitswurzel ergibt das +%Damit beschäftigen wir uns im Abschnitt \ref{reedsolomon:subsection:sfaktor} weiter, konkret suchen wir momentan aber eine Inverse für unsere primitive Einheitswurzel $a$. \[ -8^1 \qquad \rightarrow \qquad 8^{-1} +8^1 \qquad \rightarrow \qquad 8^{-1}. \] -Mit einem solchen Problem haben wir uns bereits in Abschnitt \ref{buch:section:euklid} befasst und so den euklidischen Algorithmus kennengelernt, den wir auf unseren Fall anwenden können. +Mit einem solchen Problem haben wir uns bereits in Abschnitt \ref{buch:section:euklid} befasst und so den euklidischen Algorithmus kennengelernt, den wir auf diesen Fall anwenden können. % Old Text %Im Abschnitt \textcolor{red}{4.1} haben wir den euklidischen Algorithmus kennengelernt, den wir auf unseren Fall anwenden können. @@ -76,7 +77,9 @@ Daraus erhalten wir \end{tabular} \end{center} -als Inverse der primitiven Einheitswurzel. Die inverse Transformationsmatrix $A^{-1}$ bilden wir, indem wir jetzt die inverse primitive Einheitswurzel anstelle der primitiven Einheitswurzel in die Matrix einsetzen: +als Inverse der primitiven Einheitswurzel. +Alternativ können wir das Resultat auch aus der Tabelle \ref{reedsolomon:subsection:mptab} ablesen. +Die inverse Transformationsmatrix $A^{-1}$ bilden wir, indem wir jetzt die inverse primitive Einheitswurzel anstelle der primitiven Einheitswurzel in die Matrix einsetzen: \[ \begin{pmatrix} 8^0 & 8^0 & 8^0 & 8^0 & \dots & 8^0 \\ @@ -102,9 +105,9 @@ als Inverse der primitiven Einheitswurzel. Die inverse Transformationsmatrix $A^ \subsection{Der Faktor $s$ \label{reedsolomon:subsection:sfaktor}} Die diskrete Fouriertransformation benötigt für die Inverse einen Vorfaktor von $\frac{1}{2\pi}$. -Primitiv nehmen wir an, dass wir für die Inverse Transformationsmatrix ebenfalls einen benötigen. +Wir müssen also damit rechnen, dass wir für die Inverse Transformationsmatrix ebenfalls einen solchen Vorfaktor benötigen. Nur stellt sich jetzt die Frage, wie wir diesen Vorfaktor in unserem Fall ermitteln können. -Dafür betrachten wir eine Regel aus der Linearen Algebra, nämlich dass +Dafür betrachten wir eine Regel aus der linearen Algebra, nämlich dass \[ A \cdot A^{-1} = E @@ -148,7 +151,7 @@ Aus der letzten Matrix folgt, dass wir \[ s = \dfrac{1}{10} \] -als unseren Vorfaktor setzen müssen um die Gleichung \ref{reedsolomon:equation:sfaktor} zu erfüllen. Da wir in $\mathbb{F}_{11}$ nur mit ganzen Zahlen arbeiten schreiben wir $\frac{1}{10}$ in $10^{-1}$ um und bestimmen diese Inverse erneut mit dem euklidischen Algorithmus und erhalten für $10^{-1} = 10$ als unseren Vorfaktor in $\mathbb{F}_{11}$. +als unseren Vorfaktor setzen müssen um, die Gleichung \ref{reedsolomon:equation:sfaktor} zu erfüllen. Da wir in $\mathbb{F}_{11}$ nur mit ganzen Zahlen arbeiten, schreiben wir $\frac{1}{10}$ in $10^{-1}$ um und bestimmen diese Inverse erneut mit dem euklidischen Algorithmus. So erhalten wir $10^{-1} = 10$ als Vorfaktor in $\mathbb{F}_{11}$. % %erfüllt wird. Wir schreiben den Bruch um in $\frac{1}{10} = 10^{-1}$ und wenden darauf erneut den euklidischen Algorithmus an und erhalten somit den Vorfaktor $10^{-1} = 10 = s$ in $\mathbb{F}_{11}$. % diff --git a/buch/papers/reedsolomon/dtf.tex b/buch/papers/reedsolomon/dtf.tex new file mode 100644 index 0000000..025be3a --- /dev/null +++ b/buch/papers/reedsolomon/dtf.tex @@ -0,0 +1,30 @@ +% +% teil3.tex -- Beispiel-File für Teil 3 +% +% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil +% +\section{Diskrete Fourien Transformation +\label{reedsolomon:section:dtf}} +\rhead{Umwandlung mit DTF} +Um die Polynominterpolation zu umgehen, gehen wir nun über in die Fourientransformation. +Dies wird weder eine erklärung der Forientransorfmation noch ein genauer gebrauch +für den Reed-Solomon-Code. Dieser Abschnitt zeigt nur wie die Fourientransformation auf Fehler reagiert. +wobei sie dann bei späteren Berchnungen ganz nütlich ist. + +\subsection{Übertragungsabfolge +\label{reedsolomon:subsection:Übertragungsabfolge}} +Das Signal.... sind die Daten, Zahlen welche übertragen werden sollen. +Das speziell ist das wir 100 Punkte übertragen und von 64 bis 100, +werden nur Null Punkte übertragen, dies weiss auch unser Empfänger. +Nun wird das Signal in Abbildung... codiert... +Somit wird die Information jedes Punktes auf das ganze spektrum von 0 bis 100 übertragen. +Kommen nuun drei Fehler... hinzu zu diesem codierten Signal sind diese nicht zu erkennen. +Nach dem Empfangen... und decodieren ... erkennt man die fehlerhafte information in den Punkten 64 bis 100. +Filtert man nur diese Punkte heraus und Transformiert sie mit Fourier erhält man die stellen an denen die Fehler sich eingeschlichen haben. + +\subsection{Diskrete Fourientransformation Zusamenhang +\label{reedsolomon:subsection:dtfzusamenhang}} +Die Diskrete Fourientransformation ist definiert als +.... + + diff --git a/buch/papers/reedsolomon/einleitung.tex b/buch/papers/reedsolomon/einleitung.tex new file mode 100644 index 0000000..3d40db1 --- /dev/null +++ b/buch/papers/reedsolomon/einleitung.tex @@ -0,0 +1,19 @@ +% +% einleitung.tex -- Beispiel-File für die Einleitung +% +% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil +% +\section{Einleitung +\label{reedsolomon:section:einleitung}} +\rhead{Einleitung} +Der Reed-Solomon-Code ist entstaden im ... vom .. um, +das Problem der Daten Übertragung zu lösen. +In deiesem Abschnitt wird möglichst verständlich die mathematische Abfolge, Funktion oder Algorithmus erklärt. +Es wird jedoch nicht auf die technische Umsetzung oder Implementierung eingegangen. +Um beim Daten Übertragen fehler zu erkennen könnte man die Daten jeweils doppelt senden, +und so jeweilige Fehler zu erkennen. +Doch dies braucht schnell unmengen an Daten, wenn man nach vielen Fehler absichern möchte. +Der Reed-Solomon-Code macht dies auf eine andere, clevere Weise. + + + diff --git a/buch/papers/reedsolomon/endlichekoerper.tex b/buch/papers/reedsolomon/endlichekoerper.tex index 19e5dd4..1d196fd 100644 --- a/buch/papers/reedsolomon/endlichekoerper.tex +++ b/buch/papers/reedsolomon/endlichekoerper.tex @@ -1,7 +1,7 @@ % -% teil1.tex -- Beispiel-File für das Paper +% endlichekoerper.tex -- endliche Körper % -% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil +% (c) 2021 Michael Steiner, Hochschule Rapperswil % \section{Reed-Solomon in Endlichen Körpern \label{reedsolomon:section:endlichekoerper}} diff --git a/buch/papers/reedsolomon/hilfstabellen.tex b/buch/papers/reedsolomon/hilfstabellen.tex index b006f21..24fabdf 100644 --- a/buch/papers/reedsolomon/hilfstabellen.tex +++ b/buch/papers/reedsolomon/hilfstabellen.tex @@ -1,8 +1,7 @@ % -% hilfstabellen.tex -% Autor: Michael Steiner +% hilfstabellen.tex -- Hilfstabellen % -% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil +% (c) 2021 Michael Steiner, Hochschule Rapperswil % \section{Hilfstabellen für $\mathbb{F}_{11}$ \label{reedsolomon:section:hilfstabellen}} diff --git a/buch/papers/reedsolomon/idee.tex b/buch/papers/reedsolomon/idee.tex new file mode 100644 index 0000000..4a7716a --- /dev/null +++ b/buch/papers/reedsolomon/idee.tex @@ -0,0 +1,58 @@ +% +% teil1.tex -- Beispiel-File für das Paper +% +% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil +% +\section{Idee +\label{reedsolomon:section:idee}} +\rhead{Problemstellung} +Das Problem liegt darin Informationen, Zahlen, +zu Übertragen und Fehler zu erkennen. +Beim Reed-Solomon-Code kann man nicht nur Fehler erkenen, +man kann sogar einige Fehler korrigieren. + +\rhead{Polynom-Ansatz} +Eine Idee ist die Daten, +ein Polynom zu bilden und dieses dann mit bestimmten Punkten überträgt. +Nehmen wir als beisbiel die Zahlen \textcolor{blue}{2}, \textcolor{blue}{1}, \textcolor{blue}{5}, +welche uns dann das Polynom +\begin{equation} +p(x) += +2x^2 + 1x + 5 +\label{reedsolomon:equation1} +\end{equation} +ergeben. +Übertragen werden nun die stellen 1, 2, 3\dots 7 dieses Polynomes. +Grafisch sieht man dies dann im Abbild //TODO +Wenn ein Fehler sich in die Übertragung eingeschlichen hatt, muss der Leser/Empfänger erkennen, welches das Richtige Polynom ist. +Der Leser/Empfänger weiss, mit welchem Grad das Polynom entwickelt wurde. +\subsection{Beispiel} +Für das Beispeil aus der Gleichung \ref{reedsolomon:equation1}, +ist ein Polynome zweiten Grades durch drei Punkte eindeutig bestimmbar. +Hat es Fehler in der Übertragunge gegeben, kann man diese erkennen, +da alle Punkte, die korrekt sind, auf dem Polynom liegen müssen. +Ab wie vielen Fehler ist das Polynom nicht mehr erkennbar beim Übertragen von 7 Punkten? +Bei 2 Fehlern kann man noch eindeutig bestimmen, dass das Polynom mit 4 Punkten, +gegenüber dem mit 5 Punkten falsch liegt. +Werden es mehr Fehler kann nur erkennt werden das das Polynom nicht stimmt. +Das Orginale Polynom kann aber nicht mehr gefunden werden. +Dabei sollten mehr Übertragungspunkte gegeben werden. + +\section{Fehlerbestimmung +\label{reedsolomon:section:Fehlerbestimmmung}} +So wird ein Muster indentifiziert, welches genau vorherbestimmen kann, +wie gross das Polynom sein muss und wie viele Übertragungspunkte gegeben werden müssen. +Durch ein klein wenig Überlegung ist klar das die anzahl Zahlen (Daten, ab hier verwenden wir das Wort Nutzlast), +die dan Entschlüsselt werden sollen den Grad des Polynoms minus 1 ergeben. +Für die Anzahl an Übertragungspunkte, muss bestimmt werden wieviel Fehler erkennt und korrigiert werden sollen. +Mit Hilfe der Tabelle.... sieht man das es bei $$t$$ Fehlern und $$k$$ Nutzlast, +für das Übertragen $$k+2t$$ Punkte gegben werden müssen. + +Ein toller Nebeneffekt ist das dadurch auch $$2t$$ Fehler erkannt werden. +um zurück auf unser Beispiel zu kommen, +können von den 7 Übertragungspunkten bis zu $$2t = 2*2 = 4 $$ Punkten falsch liegen +und es wird kein eindeutiges Polynom 2ten Grades erkannt, und somit die Nutzlast Daten als fehlerhaft deklariert. + +Ein Polynom durch Punkt mit Polynom Interpolation zu rekonstruieren ist schwierig und Fehleranfällig. + diff --git a/buch/papers/reedsolomon/images/Compact_Disc.png b/buch/papers/reedsolomon/images/Compact_Disc.png Binary files differnew file mode 100644 index 0000000..7e3f870 --- /dev/null +++ b/buch/papers/reedsolomon/images/Compact_Disc.png diff --git a/buch/papers/reedsolomon/images/Voyager_Sonde.png b/buch/papers/reedsolomon/images/Voyager_Sonde.png Binary files differnew file mode 100644 index 0000000..e4dc400 --- /dev/null +++ b/buch/papers/reedsolomon/images/Voyager_Sonde.png diff --git a/buch/papers/reedsolomon/images/designer_qrcode.png b/buch/papers/reedsolomon/images/designer_qrcode.png Binary files differnew file mode 100644 index 0000000..a9e0505 --- /dev/null +++ b/buch/papers/reedsolomon/images/designer_qrcode.png diff --git a/buch/papers/reedsolomon/images/designer_qrcode_ohnelogo.png b/buch/papers/reedsolomon/images/designer_qrcode_ohnelogo.png Binary files differnew file mode 100644 index 0000000..fe4251d --- /dev/null +++ b/buch/papers/reedsolomon/images/designer_qrcode_ohnelogo.png diff --git a/buch/papers/reedsolomon/images/qrcode_h.png b/buch/papers/reedsolomon/images/qrcode_h.png Binary files differnew file mode 100644 index 0000000..4dc5779 --- /dev/null +++ b/buch/papers/reedsolomon/images/qrcode_h.png diff --git a/buch/papers/reedsolomon/images/qrcode_l.png b/buch/papers/reedsolomon/images/qrcode_l.png Binary files differnew file mode 100644 index 0000000..69f807f --- /dev/null +++ b/buch/papers/reedsolomon/images/qrcode_l.png diff --git a/buch/papers/reedsolomon/main.tex b/buch/papers/reedsolomon/main.tex index 4e2fd60..a400508 100644 --- a/buch/papers/reedsolomon/main.tex +++ b/buch/papers/reedsolomon/main.tex @@ -28,10 +28,10 @@ Bilden Sie auch für Formeln kurze Zeilen, einerseits der besseren \end{itemize} % Joshua -\input{papers/reedsolomon/teil0.tex} -\input{papers/reedsolomon/teil1.tex} +\input{papers/reedsolomon/einleitung.tex} +\input{papers/reedsolomon/idee.tex} \input{papers/reedsolomon/teil2.tex} -\input{papers/reedsolomon/teil3.tex} +\input{papers/reedsolomon/dtf.tex} % Michael \input{papers/reedsolomon/endlichekoerper} @@ -40,11 +40,17 @@ Bilden Sie auch für Formeln kurze Zeilen, einerseits der besseren \input{papers/reedsolomon/decmitfehler} \input{papers/reedsolomon/rekonstruktion} \input{papers/reedsolomon/zusammenfassung} -%\input{papers/reedsolomon/anwendungen} -> geplant +\input{papers/reedsolomon/anwendungen} \input{papers/reedsolomon/hilfstabellen} \nocite{reedsolomon:weitz} \nocite{reedsolomon:informationkommunikation} +\nocite{reedsolomon:voyager_programm} +\nocite{reedsolomon:voyager} +\nocite{reedsolomon:cd_wiki} +\nocite{reedsolomon:cd} +\nocite{reedsolomon:qr_wiki} +\nocite{reedsolomon:qr} %\nocite{reedsolomon:mendezmueller} \printbibliography[heading=subbibliography] diff --git a/buch/papers/reedsolomon/references.bib b/buch/papers/reedsolomon/references.bib index 731bd35..e0a75a8 100644 --- a/buch/papers/reedsolomon/references.bib +++ b/buch/papers/reedsolomon/references.bib @@ -23,3 +23,56 @@ volume = {1} } +@online{reedsolomon:voyager_programm, + title = {Information über das Voyager Programm}, + url = {https://de.wikipedia.org/wiki/Voyager-Programm}, + date = {2021-07-19}, + year = {2021}, + month = {7}, + day = {19} +} + +@online{reedsolomon:voyager, + title = {Bild der Voyager Raumsonde}, + url = {https://en.wikipedia.org/wiki/Voyager_1}, + date = {2021-07-19}, + year = {2021}, + month = {7}, + day = {19} +} + +@online{reedsolomon:cd_wiki, + title = {Alles über die CD}, + url = {https://de.wikipedia.org/wiki/Compact_Disc}, + date = {2021-07-19}, + year = {2021}, + month = {7}, + day = {19} +} + +@online{reedsolomon:cd, + title = {Funktionsweise des QR-Codes}, + url = {https://www.stickpng.com/img/electronics/compact-discs/stack-compact-disc}, + date = {2021-07-19}, + year = {2021}, + month = {7}, + day = {19} +} + +@online{reedsolomon:qr_wiki, + title = {Funktionsweise des QR-Codes}, + url = {https://de.wikipedia.org/wiki/QR-Code}, + date = {2021-07-19}, + year = {2021}, + month = {7}, + day = {19} +} + +@online{reedsolomon:qr, + title = {Tool zum erstellen von QR-Codes}, + url = {https://www.qrcode-generator.ch}, + date = {2021-07-19}, + year = {2021}, + month = {7}, + day = {19} +}
\ No newline at end of file diff --git a/buch/papers/reedsolomon/rekonstruktion.tex b/buch/papers/reedsolomon/rekonstruktion.tex index 04e748c..b099e68 100644 --- a/buch/papers/reedsolomon/rekonstruktion.tex +++ b/buch/papers/reedsolomon/rekonstruktion.tex @@ -1,10 +1,9 @@ % -% rekonstruktion.tex -% Autor: Michael Steiner +% rekonstruktion.tex -- Rekonstruktion % -% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil +% (c) 2021 Michael Steiner, Hochschule Rapperswil % -\section{Nachricht Rekonstruieren +\section{Nachricht rekonstruieren \label{reedsolomon:section:rekonstruktion}} \rhead{Rekonstruktion der Nachricht} Im letzten Abschnitt haben wir eine Möglichkeit gefunden, wie wir die fehlerhaften Stellen lokalisieren können. @@ -49,7 +48,7 @@ Wir stellen also die Matrix auf und markieren gleichzeitig die Fehlerstellen: \end{pmatrix} . \] -Die rot markierten Stellen im Übertragungsvektor enthalten Fehler und bringt uns daher keinen weiterer Nutzen. +Die rot markierten Stellen im Übertragungsvektor enthalten Fehler und bringt uns daher keinen weiteren Nutzen. Aus diesem Grund werden diese Stellen aus dem Vektor entfernt, was wir hier ohne Probleme machen können, da dieser Code ja über Fehlerkorrekturstellen verfügt, deren Aufgabe es ist, eine bestimmte Anzahl an Fehler kompensieren zu können. Die dazugehörigen Zeilen in der Matrix werden ebenfalls entfernt, da die Matrix gleich viele Zeilen wie im Übertragungsvektor aufweisen muss, damit man ihn decodieren kann. @@ -78,6 +77,7 @@ Daraus resultiert Die Matrix ist jedoch nicht mehr quadratisch, was eine Rekonstruktion durch Inversion ausschliesst. Um die quadratische Form wieder herzustellen müssen wir zwei Spalten aus der Matrix entfernen. Wir kennen aber das Resultat aus den letzten vier Spalten, da wir wissen, das die Nachricht aus Nutzdatenteil und Fehlerkorrekturteil besteht, wobei der letzteres bekanntlich aus lauter Nullstellen besteht. +Wir nehmen die markierten Spalten in \[ \begin{pmatrix} 5 \\ 3 \\ 6 \\ 2 \\ 10 \\ 2 \\ 7 \\ 4 \\ @@ -98,7 +98,7 @@ Wir kennen aber das Resultat aus den letzten vier Spalten, da wir wissen, das di m_0 \\ m_1 \\ m_2 \\ m_3 \\ m_4 \\ m_5 \\ \textcolor{darkgreen}{m_6} \\ \textcolor{darkgreen}{m_7} \\ \textcolor{darkgreen}{m_8} \\ \textcolor{darkgreen}{m_9} \\ \end{pmatrix} \] -Wir nehmen die entsprechenden Spalten aus der Matrix heraus und erhalten so das Überbestimmte Gleichungssystem +aus der Matrix heraus und erhalten so das Überbestimmte Gleichungssystem \[ \begin{pmatrix} 5 \\ 3 \\ 6 \\ 2 \\ 10 \\ 2 \\ \textcolor{red}{7} \\ \textcolor{red}{4} \\ diff --git a/buch/papers/reedsolomon/restetabelle1.tex b/buch/papers/reedsolomon/restetabelle1.tex index 3969ef2..b9a0e59 100644 --- a/buch/papers/reedsolomon/restetabelle1.tex +++ b/buch/papers/reedsolomon/restetabelle1.tex @@ -1,6 +1,8 @@ -% created by Michael Steiner % -% Restetabelle von F_11: Addition +% restetabelle1.tex -- Restetabelle von F_11: Addition +% +% (c) 2021 Michael Steiner, Hochschule Rapperswil +% % alternatives design %\begin{figure} diff --git a/buch/papers/reedsolomon/restetabelle2.tex b/buch/papers/reedsolomon/restetabelle2.tex index 1a9815c..3b13ea2 100644 --- a/buch/papers/reedsolomon/restetabelle2.tex +++ b/buch/papers/reedsolomon/restetabelle2.tex @@ -1,6 +1,8 @@ -% created by Michael Steiner % -% Restetabelle von F_11: Multiplikation +% restetabelle2.tex -- Restetabelle von F_11: Multiplikation +% +% (c) 2021 Michael Steiner, Hochschule Rapperswil +% % alternatives design %\begin{figure} diff --git a/buch/papers/reedsolomon/teil0.tex b/buch/papers/reedsolomon/teil0.tex deleted file mode 100644 index b7ae971..0000000 --- a/buch/papers/reedsolomon/teil0.tex +++ /dev/null @@ -1,22 +0,0 @@ -% -% einleitung.tex -- Beispiel-File für die Einleitung -% -% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil -% -\section{Teil 0\label{reedsolomon:section:teil0}} -\rhead{Teil 0} -Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam -nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam -erat, sed diam voluptua \cite{reedsolomon:bibtex}. -At vero eos et accusam et justo duo dolores et ea rebum. -Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum -dolor sit amet. - -Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam -nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam -erat, sed diam voluptua. -At vero eos et accusam et justo duo dolores et ea rebum. Stet clita -kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit -amet. - - diff --git a/buch/papers/reedsolomon/teil1.tex b/buch/papers/reedsolomon/teil1.tex deleted file mode 100644 index 0aa9b41..0000000 --- a/buch/papers/reedsolomon/teil1.tex +++ /dev/null @@ -1,55 +0,0 @@ -% -% teil1.tex -- Beispiel-File für das Paper -% -% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil -% -\section{Teil 1 -\label{reedsolomon:section:teil1}} -\rhead{Problemstellung} -Sed ut perspiciatis unde omnis iste natus error sit voluptatem -accusantium doloremque laudantium, totam rem aperiam, eaque ipsa -quae ab illo inventore veritatis et quasi architecto beatae vitae -dicta sunt explicabo. -Nemo enim ipsam voluptatem quia voluptas sit aspernatur aut odit -aut fugit, sed quia consequuntur magni dolores eos qui ratione -voluptatem sequi nesciunt -\begin{equation} -\int_a^b x^2\, dx -= -\left[ \frac13 x^3 \right]_a^b -= -\frac{b^3-a^3}3. -\label{reedsolomon:equation1} -\end{equation} -Neque porro quisquam est, qui dolorem ipsum quia dolor sit amet, -consectetur, adipisci velit, sed quia non numquam eius modi tempora -incidunt ut labore et dolore magnam aliquam quaerat voluptatem. - -Ut enim ad minima veniam, quis nostrum exercitationem ullam corporis -suscipit laboriosam, nisi ut aliquid ex ea commodi consequatur? -Quis autem vel eum iure reprehenderit qui in ea voluptate velit -esse quam nihil molestiae consequatur, vel illum qui dolorem eum -fugiat quo voluptas nulla pariatur? - -\subsection{De finibus bonorum et malorum -\label{reedsolomon:subsection:finibus}} -At vero eos et accusamus et iusto odio dignissimos ducimus qui -blanditiis praesentium voluptatum deleniti atque corrupti quos -dolores et quas molestias excepturi sint occaecati cupiditate non -provident, similique sunt in culpa qui officia deserunt mollitia -animi, id est laborum et dolorum fuga \eqref{000tempmlate:equation1}. - -Et harum quidem rerum facilis est et expedita distinctio -\ref{reedsolomon:section:loesung}. -Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil -impedit quo minus id quod maxime placeat facere possimus, omnis -voluptas assumenda est, omnis dolor repellendus -\ref{reedsolomon:section:folgerung}. -Temporibus autem quibusdam et aut officiis debitis aut rerum -necessitatibus saepe eveniet ut et voluptates repudiandae sint et -molestiae non recusandae. -Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis -voluptatibus maiores alias consequatur aut perferendis doloribus -asperiores repellat. - - diff --git a/buch/papers/reedsolomon/teil3.tex b/buch/papers/reedsolomon/teil3.tex deleted file mode 100644 index 91a8d4e..0000000 --- a/buch/papers/reedsolomon/teil3.tex +++ /dev/null @@ -1,40 +0,0 @@ -% -% teil3.tex -- Beispiel-File für Teil 3 -% -% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil -% -\section{Teil 3 -\label{reedsolomon:section:teil3}} -\rhead{Teil 3} -Sed ut perspiciatis unde omnis iste natus error sit voluptatem -accusantium doloremque laudantium, totam rem aperiam, eaque ipsa -quae ab illo inventore veritatis et quasi architecto beatae vitae -dicta sunt explicabo. Nemo enim ipsam voluptatem quia voluptas sit -aspernatur aut odit aut fugit, sed quia consequuntur magni dolores -eos qui ratione voluptatem sequi nesciunt. Neque porro quisquam -est, qui dolorem ipsum quia dolor sit amet, consectetur, adipisci -velit, sed quia non numquam eius modi tempora incidunt ut labore -et dolore magnam aliquam quaerat voluptatem. Ut enim ad minima -veniam, quis nostrum exercitationem ullam corporis suscipit laboriosam, -nisi ut aliquid ex ea commodi consequatur? Quis autem vel eum iure -reprehenderit qui in ea voluptate velit esse quam nihil molestiae -consequatur, vel illum qui dolorem eum fugiat quo voluptas nulla -pariatur? - -\subsection{De finibus bonorum et malorum -\label{reedsolomon:subsection:malorum}} -At vero eos et accusamus et iusto odio dignissimos ducimus qui -blanditiis praesentium voluptatum deleniti atque corrupti quos -dolores et quas molestias excepturi sint occaecati cupiditate non -provident, similique sunt in culpa qui officia deserunt mollitia -animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis -est et expedita distinctio. Nam libero tempore, cum soluta nobis -est eligendi optio cumque nihil impedit quo minus id quod maxime -placeat facere possimus, omnis voluptas assumenda est, omnis dolor -repellendus. Temporibus autem quibusdam et aut officiis debitis aut -rerum necessitatibus saepe eveniet ut et voluptates repudiandae -sint et molestiae non recusandae. Itaque earum rerum hic tenetur a -sapiente delectus, ut aut reiciendis voluptatibus maiores alias -consequatur aut perferendis doloribus asperiores repellat. - - diff --git a/buch/papers/reedsolomon/zusammenfassung.tex b/buch/papers/reedsolomon/zusammenfassung.tex index 3624f16..c24fcf3 100644 --- a/buch/papers/reedsolomon/zusammenfassung.tex +++ b/buch/papers/reedsolomon/zusammenfassung.tex @@ -1,15 +1,66 @@ +% +% zusammenfassung.tex -- Zusammenfassung +% +% (c) 2021 Michael Steiner, Hochschule Rapperswil +% \section{Zusammenfassung \label{reedsolomon:section:zf}} \rhead{Zusammenfassung} Dieser Abschnitt beinhaltet eine Übersicht über die Funktionsweise eines Reed-Solomon-Codes für beliebige endliche Körper. -TODO: - \subsubsection{Schritt 1: primitives Element} +Zu Beginn soll entschieden werden, in welchem endlichen Körper $\mathbb{F}_{q}$ gerechnet werden soll. +Ausserdem muss im gewählten Körper eine primitive Einheitswurzel gefunden, bzw. bestimmt werden. \subsubsection{Schritt 2: Codierung} +Für die Codierung wird die Nachricht als Koeffizienten des Polynoms $m(X)$ geschrieben, anschliessend wird $a^i$ in $m(X)$ eingesetzt. +Daraus ergibt sich die Codierungsmatrix +\[ +A(a) = +\begin{pmatrix} +a^0 & a^0 & a^0 & \dots \\ +a^0 & a^1 & a^2 & \dots \\ +a^0 & a^2 & a^4 & \dots \\ +\vdots&\vdots&\vdots&\ddots +\end{pmatrix} +. +\] +Mit dieser Matrix können wir den Nachrichtenblock zum Übertragungsvektor codieren. \subsubsection{Schritt 3: Decodierung ohne Fehler} +Im ersten Schritt zur Decodierung muss geprüft werden, ob der Übertragungsvektor Fehler beinhaltet. +Ist dies nicht der Fall, so kann die Matrix $A(a)$ invertiert werden mit +\[ +A(a)^{-1} = \frac{1}{q-1} \cdot A(a^{-1}). +\] +Die Codierungsmatrix ändert sich somit zur Decodierungsmatrix +\[ +\begin{pmatrix} + a^0 & a^0 & a^0 & \dots \\ + a^0 & a^1 & a^2 & \dots \\ + a^0 & a^2 & a^4 & \dots \\ + \vdots&\vdots&\vdots &\ddots +\end{pmatrix} += +\frac{1}{q-1} +\cdot +\begin{pmatrix} + a^0 & a^0 & a^0 & \dots \\ + a^0 & a^{-1} & a^{-2} & \dots \\ + a^0 & a^{-2} & a^{-4} & \dots \\ + \vdots&\vdots&\vdots&\ddots +\end{pmatrix} +. +\] +Daraus lässt sich der Nachrichtenblock aus dem Übertragungsvektor rekonstruieren. \subsubsection{Schritt 4: Decodierung mit Fehler} - +Sollte der Übertragungsvektor fehlerhaft empfangen werden, so kann der Nachrichtenblock nicht durch invertieren der Matrix rekonstruiert werden. +Zur Lokalisierung der Fehlerstellen nehmen wir das Polynom $f(X)$ zur Hilfe, welches wir über den Satz von Fermat bestimmt haben. +Berechnen wir daraus das $\operatorname{kgV}$ von $f(X)$ und $d(X)$, so erhalten wir ein Lokatorpolynom. +Durch das bestimmen der Exponenten erhalten wir die Fehlerhaften Stellen im Übertragungsvektor. +Für die Rekonstruktion stellen wir ein Gleichungssystem auf und entfernen daraus die Fehlerhaften Zeilen. +Im Anschluss kann das verkleinerte Gleichungssystem gelöst werden. +Als Resultat erhalten wir die fehlerfreie Nachricht. +%Aus diesem Grund suchen wir nach einem Lokatorpolynom, welches uns die Fehlerhaften Stellen im Übertragungsvektor anzeigt. +%Dazu nehmen wir das Polynom $f(X)$, welches wir durch den Satz von Fermat erhalten, und berechnen so das $\operatorname{kgV}(f(X),d(X))$ und kommen so auf das Lokatorpolynom $l(X)$. Durch das bestimmen von den Exponenten erhalten wir die Fehlerstellen, welche wir aus dem Gleichungssystem entfernen müssen. Übrig bleibt das berechnen dieses Gleichungssystems. diff --git a/buch/papers/verkehr/section1.tex b/buch/papers/verkehr/section1.tex index 6a5dc28..d96d450 100644 --- a/buch/papers/verkehr/section1.tex +++ b/buch/papers/verkehr/section1.tex @@ -2,35 +2,83 @@ \label{section:verkehr/einfuehrung} \subsection{Verkehrsnetze} -Das Verkehrsnetz besteht aus allen Anlagen, auf oder unter der Erdoberfläche, auf denen eine räumliche Fortbewegung von Personen oder auch Gütern stattfindet. Verkehrsnetze sind ein Bestandteil der Verkehrsinfrastruktur, die auf topografischen Karten festgehalten werden. Sie umfassen den Schienenverkehr, alle Strassen und Wege, wie auch Flugplätze und alle dazugehörigen Bauwerke. +Das Verkehrsnetz besteht aus allen Anlagen, auf oder unter der Erdoberfläche, auf denen eine räumliche Fortbewegung von Personen oder auch Gütern stattfindet. Verkehrsnetze sind ein Bestandteil der Verkehrsinfrastruktur, die auf topografischen Karten festgehalten werden. Sie umfassen den Schienenverkehr, alle Strassen und Wege, wie auch Flugplätze und alle dazugehörigen Bauwerke. Aus verkehrsgeografischer Sicht besteht das Verkehrsnetz aus Kanten, Knotenpunkten und dem Hinterland. Die Knotenpunkte werden auch hier durch die Kanten verbunden, die den Verkehrsstrom aufnehmen, wobei das Hinterland durch einzelne Knoten versorgt wird. Die Aufteilung in Kanten und Knotenpunkte ermöglicht eine Vereinfachung komplexer Verkehrsnetze, damit sie mittels der Graphentheorie untersucht werden können. -Grundsätzlich können kurze Wege zwischen den Knotenpunkten das Ziel beim -Aufbau eines Verkehrsnetzes sein. Es kann aber auch versucht werden, die Bau- und Unterhaltskosten des Verkehrsnetzes in einem gewissen Rahmen zu halten. Aus diesen Vorgaben ergibt sich dann, je nach dem was gewünscht wird, eine grob- oder feinmaschige Struktur des Netzes. +Grundsätzlich können kurze Wege zwischen den Knotenpunkten das Ziel beim Aufbau eines Verkehrsnetzes sein. Es kann aber auch versucht werden, die Bau- und Unterhaltskosten des Verkehrsnetzes in einem gewissen Rahmen zu halten. Aus diesen Vorgaben ergibt sich dann, je nach dem was gewünscht wird, eine grob- oder feinmaschige Struktur des Netzes. Ziel ist aber ein möglichst wirtschaftliches und optimales Verkehrsnetz. \subsection{Suchalgorithmen} \subsubsection{Dijkstra-Algorithmus} Der Algorithmus von Dijkstra ist benannt nach seinem Erfinder dem Mathematik- und Infomratikprofessor Edsger Dijkstra. Den Algorithmus hat er im Jahr 1959 erfunden. -Der Algorithmus von Dijkstra ist ein Greedy-Algorithmus (gieriger Algorithmus), der schrittweise einen Folgezustand auswählt, damit beim Zeitpunkt der Wahl der grösste Gewinn bzw. das beste Ergebnis erzielt werden kann. +Der Algorithmus von Dijkstra ist ein Greedy-Algorithmus (gieriger Algorithmus), der schrittweise einen Folgezustand auswählt, damit beim Zeitpunkt der Wahl der grösste Gewinn bzw. das beste Ergebnis erzielt werden kann. Trotz der Schnelligkeit der Greedy-Algorithmen, können viele Probleme nicht optimal gelöst werden. Vereinfacht wird beim Dijkstra-Algorithmus, ausgehend von einem Startknoten so lange dem kürzesten Pfad gefolgt, bis der Zielknoten erreicht wird. Dabei muss für jeden besuchten Knoten die Kostenfunktion als auch der Pfad dahin (vorheriger Knoten) gespeichert werden. Dadurch wird hingegen garantiert, dass, wenn der Zielknoten erreicht wird, auch der kürzeste Pfad gefunden wurde. Grundlegende Voraussetzung für den Dijkstra-Algorithmus ist die strikte Positivität der Kantengewichte. Andernfalls würde ein wiederholtes Ablaufen einer Kante mit negativem Gewicht zu einer stetigen Reduktion der Kostenfunktion führen, was zu einer unendlichen Schlaufe führen würde. +Gegeben sei ein Netzwerk mit $n$ Knoten und dem Startknoten $a$. +Alle Kanten sind mit $k(i, j)$ bewertet. +Gesucht wird der kürzeste Pfad zwischen dem Startknoten und allen übrigen Knoten im Netz. +$D(i)$ ist die kürzeste Distanz vom Startknoten $a$ zum Knoten $i, V(i)$ ist der unmittelbare Vorgängerknoten vom Knoten $i$ auf dem kürzesten Weg vom Startknoten $a$ zum Konten $i$ und die Menge $M$ ist die Menge einer bestimmten Auswahl an Knoten. + +Dabei gilt +\begin{equation}M={a}\end{equation} +\begin{equation}D(a)=0\end{equation} wobei +\begin{equation}D(i)=\infty\end{equation} und +\begin{equation}i \neq a \end{equation} +Ausserdem gilt \begin{equation}V(i)=(-) \text{für alle Knoten $i$}\end{equation}\\ + +%THEORIE... +Iteration + +1. Auswahl eines Knotens \begin{equation} K\in M \text{mit} D(K)=D(i);i\in M\end{equation} + +2. Für alle Nachfolger $N(j)$ vom Knoten $K$ gilt: +\begin{equation}D(K) + k_Kj < D(j)\end{equation} dann wird \begin{equation}D(j) = D(K) + k_Kj, V(j) = K\end{equation} gesetzt und somit wird der Knoten $j$ in die Menge $M$ aufgenommen. + +3. Der ausgewählte Knoten \begin{equation}K\in M\text{wird aus der Menge herausgelöscht}\end{equation}\\ +Diese drei Schritte werden so lange wiederholt bis gilt +\begin{equation}M=\{\}\end{equation} + \subsubsection{A*-Algorithmus} Suchalgorithmen werden nach einfachen (uninformierte) und heuristischen (informierten) Algorithmen unterschieden. Während einfache Algorithmen den Suchraum intuitiv durchsuchen, beziehen heuristische Algorithmen Wissen über den Suchraum mit ein. Der A*-Algorithmus geht auf seine Erfinder Peter Hart, Nils Nilsson und Bertram Raphael zurück, die den Algorithmus erstmals im Jahr 1968 beschrieben. Der A*-Algorithmus ist ein heuristischer Suchalgorithmus, der den kürzesten Pfad zwischen zwei Knoten in einem Graphen mit positiven Kantengewichten berechnet. -Im Gegensatz zu einfachen Suchalgorithmen, wird beim A*-Algorithmus eine Schätzfunktion, die sogenannte Heuristik, verwendet. Dies ermöglicht ein zielgerichtetes Suchen und gleichzeitig wird die Laufzeit verringert. +Im Gegensatz zu einfachen Suchalgorithmen, wird beim A*-Algorithmus eine Schätzfunktion, die sogenannte Heuristik, verwendet. Dies ermöglicht ein zielgerichtetes Suchen und gleichzeitig wird die Laufzeit verringert. Ausserdem findet der A*-Algorithmus immer eine optimale Lösung, sofern eine vorhanden ist. -Der A*-Algorithmus wird als Verallgemeinerung gehandhabt und gilt als Erweiterung des Dijkstra-Algorithmus. -======= +Der A*-Algorithmus wird als Verallgemeinerung gehandhabt und gilt als Erweiterung des Dijkstra-Algorithmus. + +\subsubsection{Anwendung A*-Algorithmus} +Wie oben erwähnt basiert der A*-Algorithmus auf dem Shortest-Path-Algorithmus von Dijkstra. Gemäss dem Algorihtmus von Dijkstra werden von einem Startknoten aus die jeweiligen Nachbarknoten, die Nachbarknoten der Nachbarknoten usw. verarbeitet. Die Kantengewichte werden dabei aufsummiert und die Priorität wird auf die Kante gelegt, die das geringste Gewicht aufweist. Mit diesem Verfahren wird sichergestellt, dass die erste gefundene Lösung auch die optimalste Lösung darstellt.\\ + +Die Kantengewichte werden für jeden Knoten in Form einer Funktion dargestellt +\begin{equation}f(n)=g(n)\end{equation} mit +\begin{equation}g(n)=\text{Summe aller Kantengewichte vom Startknoten bis n}\end{equation}\\ +Der A*-Algorithmus erweitert die Vorgehensweise des Algorithmus von Dijkstra um die Heuristik $h(n)$, die für jeden Knoten $n$ die geschätzte Entfernung zum Zielknoten beschreibt. +Somit gilt: +\begin{equation}f(n)=g(n)+h(n)\end{equation}\\ +Wie auch der Algorithmus von Dijkstra findet der A*-Algorithmus die optimalste Lösung. \subsubsection{Floyd-Warshall-Algorithmus} -Der Floyd-Warshall-Algorithmus wurde erstmals im Jahr 1962 von seinen Namensgebern Robert Floyd und Stephen Warshall vorgestellt. -Der Floyd-Warshall-Algorithmus sucht kürzeste Wege innerhalb eines Graphen. Er ermittelt aber nicht nur die Distanz zwischen zwei Knoten, sondern berechnet die kürzesten Wege zwischen allen Knotenpaaren eines gewichteten Graphen. Somit werden die kürzesten , beziehungsweise die optimalsten Wege zwischen allen Paaren von Knoten berechnet, sofern der Graph keinen negativen Kreis (Zyklus) aufweist. -Ein Kreis in einem Graphen ist ein Weg, bei dem Start- und Endpunkt den gleichen Knoten aufweisen. Dieser wird negativ, wenn die Summe der gewichteten Kanten kleiner als Null wird. +Der Floyd-Warshall-Algorithmus, auch Tripel-Algorithmus genannt, wurde erstmals im Jahr 1962 von seinen Namensgebern Robert Floyd und Stephen Warshall vorgestellt. +Der Floyd-Warshall-Algorithmus sucht kürzeste Wege innerhalb eines Graphen. Er ermittelt aber nicht nur die Distanz zwischen zwei Knoten, sondern berechnet die kürzesten Wege zwischen allen Knotenpaaren eines gewichteten Graphen. Somit werden die kürzesten , beziehungsweise die optimalsten Wege zwischen allen Paaren von Knoten berechnet. Der Floyd-Warhshall-Algrithmus kann ausserdem mit negativen Kantengewichten umgehen, sofern der Graph aber keinen negativen Kreis (Zyklus) aufweist. Ist dies der Fall, führt der Algorithmus zu einem falschen Ergebnis. +Ein Kreis (Zyklus) in einem Graphen ist ein Weg, bei dem Start- und Endpunkt den gleichen Knoten aufweisen. Dieser wird negativ, wenn die Summe der gewichteten Kanten kleiner als Null wird.\\ +Der Floyd-Warshall-Algorithmus besteht grundsätzlich aus Floyd's Berechnung der kürzesten Distanzen zwischen zwei Knoten und Warshall's Konstruktion der kürzesten Wege. Werden diese beiden Teilgebiete zusammengefügt, ergibt sich der Floyd-Warshall-Algorithmus. + +\subsubsection{Anwendung Floyd-Warshall-Algorithmus} + +Wie oben erwähnt, besteht der Floyd-Warshall-Algorithmus aus dem Teil von Floyd zur Berechnung der kürzesten Pfade und dem Teil von Warshall zur Konstruktion der kürzesten Pfade. + +%THEORIE... +Als erstes wird eine Gewichtsmatrix $W$ mit den Matrixeinträgen $W[i, j]$ erstellt. +Der Algorithmus berechnet danach in einer Hauptschleife alle Knoten $k$ von 1 bis $n$. +Dabei versucht er in jeder Iteration alle Wege von $i$ nach $j$ durch die Wege $(i, k)$ und $(k, j)$ zu verbessern. +Falls dieser mögliche Umweg zu einer Verbesserung führt, wird der Algorithmus aktualisiert. + +Die aktuelle Gewichtung der Pfade wird mit +\begin{equation}d[i, j]=min[d[i,j], d[i,k] + d[k,i]]\end{equation} +ermittelt. \subsubsection{Euklidische Heuristik} Bei Verkehrsnetzen ist die euklidische Distanz eine gängige und zuverlässige Heurstik. Dabei wird zu den effektiven Reisekosten zum aktuellen Knoten die euklidische Distanz bis zum Zielknoten hinzuaddiert. Dadurch wird die Kostenfunktion konsequent nie überschätzt. Dies stellt eine Voraussetzung an eine zulässige Heuristik dar. @@ -40,7 +88,7 @@ Was bei einem physischen Verkehrsnetz einfach zu bewältigen ist, da Koordinaten Der PageRank-Algorithmus wurde von den Gründern von Google, Larry Page und Sergey Brin im Jahr 1996 entwickelt und zum Patent angemeldet. Zwei Jahre später gründeten sie ihr Unternehmen Google Inc.. Beim PageRank-Algorithmus handelt es sich um den Algorithmus von Google, aus dem die Google-Matrix abgeleitet wird. Die Google-Matrix ist eine immens grosse Matrix mit Millionen Zeilen und Spalten, die für die schnelle und vor allem exakte Bestimmung der PageRanks (Gewichtung) eine grosse Bedeutung hat. -Der PageRank-Algorithmus analysiert und gewichtet beispielsweise die Verlinkungsstruktur verschiedener Websites des World Wide Web anhand ihrer Struktur. +Der PageRank-Algorithmus analysiert und gewichtet beispielsweise die Verlinkungsstruktur verschiedener Websites des World Wide Web anhand ihrer Struktur. Der PageRank wird umso höher, je mehr hochwertige Links auf eine Webseite verweisen und je höher die Gewichtung einer Webseite ist, desto grösser ist der Effekt.\\ Dabei handelt es sich um einen iterativen Prozess. Ausgegangen wird von der Adjazenz-Matrix $A$, für welche gilt. @@ -49,7 +97,7 @@ Grundsätzlich setzt sich der PageRank Algorithmus mit der Fragestellung auseina \begin{equation} A_{i,j}=\left\{ \begin{matrix} -1 & \text{Kante von $j$ nach $i$} \\ 0 & \text{keine Kante von $j$ nach $i$} +1 & \text{Kante von $j$ nach $i$} \\ 0 & \text{keine Kante von $j$ nach $i$} \end{matrix} \right. \label{verkehr:Adja} |
