diff options
Diffstat (limited to 'buch/papers')
31 files changed, 509 insertions, 323 deletions
diff --git a/buch/papers/erdbeben/Teil_Fabio.tex b/buch/papers/erdbeben/Teil_Fabio.tex index afb2110..fa7d836 100644 --- a/buch/papers/erdbeben/Teil_Fabio.tex +++ b/buch/papers/erdbeben/Teil_Fabio.tex @@ -10,64 +10,40 @@ und weil es digital simuliert wird, haben wir keine Bauschäden zu beklagen. \subsection{Wahl der Schwingung} Wir müssen uns überlegen, mit welcher Schwingung wir ein realitätsnahes Beben erzeugen können. - Mit einer ungedämpften harmonischen Schwingung können wir zwar die meisten Vorgänge in der Physik erklären. Da aber unser Erdbeben irgendwann abklingen muss, wählen wir die gedämpfte harmonische Schwingung. Die dazugehörige Schwingungsgleichung lautet - -\begin{equation} - y = A e^{-\lambda t} \sin(\omega t) -\end{equation} - -Für die Variablen der harmonisch gedämpften Schwingung setzen wir die Werte - \begin{equation} -A = 5 + y = A e^{-\lambda t} \sin(\omega t). \end{equation} - -ein. - -$A$ ist die Amplitude der Schwingung, die uns die Heftigkeit des Erdebebens beschreibt. +Dabei ist $A=5$ die anfängliche Amplitude der Schwingung, +die uns die Heftigkeit des Erdebebens beschreibt. Sie ist vergleichbar mit der Magnitude. - -$\omega$ definiert sich durch - +$\lambda$ bezeichnet die Bodendämpfung, für die wir $0.2$ wählen. +Sie ist dafür verantwortlich, dass unser Erdbeben abklingt +und kreiert die bei gedämpften Schwingungen typische Hüllkurve. +Wir nehmen an, dass $\lambda$ ein Materialparameter von geologischen Böden ist. +Die Kreisfrequenz $\omega$ ist durch \begin{equation} \omega = 2 \pi f \end{equation} - -wobei die Frequenz $f$ mit - +gegeben, +wobei die Momentanfrequenz $f = \mathcal N(\mu_f, \sigma_f) $ einer Normalverteilung mit \begin{equation} - f = E(\mathrm{Frequenz}) + \sigma^2(\mathrm{Frequenz}) + \mu_f = \SI{15}{\hertz} + \qquad \text{und} \qquad + \sigma_f = \SI{10}{\hertz} \end{equation} +folgt. -erzeugt wird. - -Zusätzlich haben wir $f$ mit dem Savitzky-Golay-Filter gefiltert. +Zusätzlich haben wir $f$ mit einem Savitzky-Golay-Filter gefiltert. Das Savitzky-Golay-Filter schaut sich immer eine definierte Anzahl von Datenpunkte an -und bildet ein Polynom $n$-ter Ordnung. -In unserer Anwendung schaut sich das Filter, im Sinne eines verschieblichen Fensters, -jeweils zehn aufeinanderfolgende Datenpunkte an und bildet ein Polynom $0$-ter Ordnung. -Da wir den Grad $0$ gewählt haben, erhalten wir pro zehn Punkte eine Gerade mit der Steigung $0$. -Diese Art von der Filterung nennt sich gleitender Mittelwert. - -Für den Erwartungswert und die Standardabweichung setzen wir die Zahlen - -\begin{equation} -E(f) = \SI{15}{\hertz} -\end{equation} - -und -\begin{equation} -\sigma^2 = \SI{10}{\hertz} -\end{equation} - -ein. - -$\lambda$ ist die Bodendämpfung, für die wir $0.2$ wählen. -Sie ist dafür verantwortlich, dass unser Erdbeben abklingen wird und kreiert bei der gedämpften Schwingung die typische Hüllkurve der Amplitude. -Wir nehmen an, dass $\lambda$ ein Materialparameter von geologischen Böden ist. +und bildet darüber ein Polynom $n$-ter Ordnung. +In unserer Anwendung schaut sich das Filter, im Sinne eines verschiebbaren Fensters, +jeweils elf aufeinanderfolgende Datenpunkte an +und approximiert diese mit ein Polynom $0$-ter Ordnung, +also einer Konstanten. +Somit erhalten wir mit Matlab-Standardfunktionen einen gleitenden Mittelwert. \subsection{Versuch im Standardfall} Im nächsten Schritt müssen wir sinnvolle Systemparameter für unseren Seismographen definieren. @@ -90,14 +66,14 @@ Wir nehmen an, dass {0.00001}^2& 0& 0 \\ 0 & {0.00001}^2& 0\\ 0 & 0& {1 }^2\\ - \end{array}\right) + \end{array}\right). \end{equation} Auch für die Messung setzen wir ein Rauschen voraus und definieren \begin{equation} R= ({\sigma_x}^2)= -({0.00001}^2) +({0.00001}^2). \end{equation} Sind nun die benötigten Systemparameter und das Rauschen definiert, erzeugen wir das Erdbeben und schauen, wie gut das Kalman-Filter die äussere Beschleunigung schätzen kann. @@ -131,21 +107,25 @@ Das Filter war imstande die Eigenfrequenz zu eliminieren und die tatsächliche K \end{figure} \subsection{Veränderung der Systemparameter} -Was wir nun austesten möchten, sind die Auswirkungen wenn z.B. der Seismograph andere Systemparameter aufweist. -Wir nehmen an, dass sich im Vergleich zum Standardfall die Masse erhöht, die Federkonstante schwächer und die Bodendämpfung doppelt so stark wirkt. +Was wir nun testen möchten, sind die Auswirkungen wenn zum Beispiel der Seismograph andere Systemparameter aufweist. +Wir nehmen an, dass sich im Vergleich zum Standardfall die Masse erhöht, die Federkonstante schwächer und die Federdämpfung doppelt so stark wirkt. Somit gilt neu \[ -m = 0.05 -\qquad \qquad +m = 0.05, +\qquad D = 0.5 \qquad \text{und} \qquad k = 0.02. \] -Da wir mit dieser Anpassung die Trägheit des Seismogrammes erhöht haben, erwarten wir sicher eine langsamere Bewegung der Masse, das heisst die Frequenz wird sich reduzieren. +Da wir mit dieser Anpassung die Trägheit des Seismogrammes erhöht haben, +erwarten wir eine langsamere Bewegung der Masse, +das heisst die Frequenz wird kleiner. -Betrachten wir die Abbildung~\ref{erdbeben:fig:systemparameter-geaendert} können wir diese Erwartung bestätigen. -Nebst dem bemerken wir eine grössere Auslenkung der Position, die wir auf die höhere Energie der Masse und geringeren Rücklenkkraft der Feder begründen können. +Betrachten wir Abbildung~\ref{erdbeben:fig:systemparameter-geaendert}, +können wir diese Erwartung bestätigen. +Zudem bemerken wir eine grössere Auslenkung der Position, +die wir mir durch die höhere Energie der Masse und geringeren Rücklenkkraft der Feder erklären können. \begin{figure} \begin{center} @@ -181,7 +161,7 @@ Die Auswertung in Abbildung~\ref{erdbeben:fig:prozessrauschen-geaendert} zeigt a \subsection{Verstärkung des Messrauschens} Als letztes verstärken wir das Messrauschen um den Faktor $100$ und belassen wieder den Rest wie im Standardfall. Wie man eigentlich schon erwarten kann, zeigt uns die Abbildung~\ref{erdbeben:fig:messrauschen-geaendert}, dass das Signal des Messsensors vom Messrauschen gestört wird. -Weil die Messung somit ungenau wird, kann das Kalman-Filter nicht mehr genau arbeiten und produziert einen ungenauen Output. +Weil die Messung somit ungenau wird, kann das Kalman-Filter nicht mehr genau arbeiten und produziert eine ungenaues Resultat. \begin{figure} \begin{center} diff --git a/buch/papers/erdbeben/images/Makefile b/buch/papers/erdbeben/images/Makefile new file mode 100644 index 0000000..3c82cb7 --- /dev/null +++ b/buch/papers/erdbeben/images/Makefile @@ -0,0 +1,15 @@ +# +# Makefile +# +# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +# +all: standard.pdf messrauschen_geaendert.pdf prozessrauschen_geaendert.pdf + +standard.pdf: standard.tex + pdflatex standard.tex + +messrauschen_geaendert.pdf: messrauschen_geaendert.tex + pdflatex messrauschen_geaendert.tex + +prozessrauschen_geaendert.pdf: prozessrauschen_geaendert.tex + pdflatex prozessrauschen_geaendert.tex diff --git a/buch/papers/erdbeben/images/messrauschen_geaendert.pdf b/buch/papers/erdbeben/images/messrauschen_geaendert.pdf Binary files differnew file mode 100644 index 0000000..5056dd0 --- /dev/null +++ b/buch/papers/erdbeben/images/messrauschen_geaendert.pdf diff --git a/buch/papers/erdbeben/images/messrauschen_geaendert.tex b/buch/papers/erdbeben/images/messrauschen_geaendert.tex new file mode 100644 index 0000000..a5a7509 --- /dev/null +++ b/buch/papers/erdbeben/images/messrauschen_geaendert.tex @@ -0,0 +1,61 @@ +% +% messrauschen_geaendert.tex -- Kombination der Messrauschen-Bilder +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{times} +\usepackage{txfonts} +\usepackage{pgfplots} +\usepackage{csvsimple} +\usetikzlibrary{arrows,intersections,math} +\begin{document} +\newboolean{showgrid} +\setboolean{showgrid}{false} +\def\skala{1} +\begin{tikzpicture}[>=latex,thick,scale=\skala] + +\node at (0,0) {\includegraphics[width=14cm]{../Messrauschen_geaendert.PNG}}; + +\def\yten{-2.06} +\def\yfifteen{0.16} + +\def\links{12.2} +\def\rechts{14.2} + +\pgfmathparse{(\yfifteen-(\yten))/5} +\xdef\m{\pgfmathresult} +\xdef\b{\yten} + +\pgfmathparse{\m*(\links-10)+(\b)} +\xdef\Links{\pgfmathresult} + +\pgfmathparse{\m*(\rechts-10)+(\b)} +\xdef\Rechts{\pgfmathresult} + +\begin{scope}[yshift=-9cm] +\node at (0,0) {\includegraphics[width=14cm]{../Messrauschen_geaendert_zoom.PNG}}; +\end{scope} + +\def\breite{7} +\def\hoehe{2} + +% Gitter +\ifthenelse{\boolean{showgrid}}{ +\draw[step=0.1,line width=0.1pt] (-\breite,-\hoehe) grid (\breite, \hoehe); +\draw[step=0.5,line width=0.4pt] (-\breite,-\hoehe) grid (\breite, \hoehe); +\draw (-\breite,-\hoehe) grid (\breite, \hoehe); +\fill (0,0) circle[radius=0.05]; +}{} + +\def\unten{-4.15} + +\draw[line width=0.7pt] (\Links,\unten) rectangle (\Rechts,4.15); +\draw[line width=0.7pt] (\Links,\unten) -- (\Links,{\unten-0.05}) + -- (-6.45,-4.6) -- (-6.45,-4.9); +\draw[line width=0.7pt] (\Rechts,\unten) -- (\Rechts,{\unten-0.05}) + -- (6.86,-4.6) -- (6.86,-4.9); +\end{tikzpicture} +\end{document} + diff --git a/buch/papers/erdbeben/images/prozessrauschen_geaendert.pdf b/buch/papers/erdbeben/images/prozessrauschen_geaendert.pdf Binary files differnew file mode 100644 index 0000000..e0bf605 --- /dev/null +++ b/buch/papers/erdbeben/images/prozessrauschen_geaendert.pdf diff --git a/buch/papers/erdbeben/images/prozessrauschen_geaendert.tex b/buch/papers/erdbeben/images/prozessrauschen_geaendert.tex new file mode 100644 index 0000000..ad4dcf9 --- /dev/null +++ b/buch/papers/erdbeben/images/prozessrauschen_geaendert.tex @@ -0,0 +1,61 @@ +% +% prozessrauschen_geaendert.tex -- Kombination der Prozessrauschen-Bilder +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{times} +\usepackage{txfonts} +\usepackage{pgfplots} +\usepackage{csvsimple} +\usetikzlibrary{arrows,intersections,math} +\begin{document} +\newboolean{showgrid} +\setboolean{showgrid}{false} +\def\skala{1} +\begin{tikzpicture}[>=latex,thick,scale=\skala] + +\node at (0,0) {\includegraphics[width=14cm]{../Prozessrauschen_geaendert.PNG}}; + +\def\yten{-2.1} +\def\yfifteen{0.12} + +\def\links{13.27} +\def\rechts{14.2} + +\pgfmathparse{(\yfifteen-(\yten))/5} +\xdef\m{\pgfmathresult} +\xdef\b{\yten} + +\pgfmathparse{\m*(\links-10)+(\b)} +\xdef\Links{\pgfmathresult} + +\pgfmathparse{\m*(\rechts-10)+(\b)} +\xdef\Rechts{\pgfmathresult} + +\begin{scope}[yshift=-9cm] +\node at (0,0) {\includegraphics[width=14cm]{../Prozessrauschen_geaendert_zoom.PNG}}; +\end{scope} + +% Gitter +\def\breite{7} +\def\hoehe{2} +\ifthenelse{\boolean{showgrid}}{ +\draw[step=0.1,line width=0.1pt] (-\breite,-\hoehe) grid (\breite, \hoehe); +\draw[step=0.5,line width=0.4pt] (-\breite,-\hoehe) grid (\breite, \hoehe); +\draw (-\breite,-\hoehe) grid (\breite, \hoehe); +\fill (0,0) circle[radius=0.05]; +}{} + +\def\unten{-4.15} + +\draw[line width=0.7pt] (\Links,\unten) rectangle (\Rechts,4.18); +\draw[line width=0.7pt] (\Links,\unten) -- (\Links,{\unten-0.05}) + -- (-6.62,-4.6) -- (-6.62,-4.9); +\draw[line width=0.7pt] (\Rechts,\unten) -- (\Rechts,{\unten-0.05}) + -- (6.80,-4.6) -- (6.80,-4.9); + +\end{tikzpicture} +\end{document} + diff --git a/buch/papers/erdbeben/images/standard.pdf b/buch/papers/erdbeben/images/standard.pdf Binary files differnew file mode 100644 index 0000000..f2ca85e --- /dev/null +++ b/buch/papers/erdbeben/images/standard.pdf diff --git a/buch/papers/erdbeben/images/standard.tex b/buch/papers/erdbeben/images/standard.tex new file mode 100644 index 0000000..74ac7a1 --- /dev/null +++ b/buch/papers/erdbeben/images/standard.tex @@ -0,0 +1,64 @@ +% +% standard.tex -- Kombination der Standard-Bilder +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{times} +\usepackage{txfonts} +\usepackage{pgfplots} +\usepackage{csvsimple} +\usetikzlibrary{arrows,intersections,math} +\begin{document} +\newboolean{showgrid} +\setboolean{showgrid}{false} +\def\skala{1} +\begin{tikzpicture}[>=latex,thick,scale=\skala] + +\node at (0,0) {\includegraphics[width=14cm]{../Standard_alles.PNG}}; + +\def\yten{-2.12} +\def\yfifteen{0.1} + +\def\links{12.5} +\def\rechts{13.4} + +\pgfmathparse{(\yfifteen-(\yten))/5} +\xdef\m{\pgfmathresult} +\xdef\b{\yten} + +%\node at (0,7) {$m=\m$}; \node at (0,8) {$b=\b$}; + +\pgfmathparse{\m*(\links-10)+(\b)} +\xdef\Links{\pgfmathresult} + +\pgfmathparse{\m*(\rechts-10)+(\b)} +\xdef\Rechts{\pgfmathresult} + +\begin{scope}[yshift=-9cm] +\node at (0,0) {\includegraphics[width=14cm]{../Standard_Zoom.PNG}}; +\end{scope} + +\def\breite{7} +\def\hoehe{2} + +% Gitter +\ifthenelse{\boolean{showgrid}}{ +\draw[step=0.1,line width=0.1pt] (-\breite,-\hoehe) grid (\breite, \hoehe); +\draw[step=0.5,line width=0.4pt] (-\breite,-\hoehe) grid (\breite, \hoehe); +\draw (-\breite,-\hoehe) grid (\breite, \hoehe); +\fill (0,0) circle[radius=0.05]; +}{} + +\def\unten{-4.15} + +\draw[line width=0.7pt] (\Links,\unten) rectangle (\Rechts,4.18); +\draw[line width=0.7pt] (\Links,\unten) -- (\Links,{\unten-0.05}) + -- (-6.36,-4.6) -- (-6.36,-4.9); +\draw[line width=0.7pt] (\Rechts,\unten) -- (\Rechts,{\unten-0.05}) + -- (6.87,-4.6) -- (6.87,-4.9); + +\end{tikzpicture} +\end{document} + diff --git a/buch/papers/erdbeben/teil0.tex b/buch/papers/erdbeben/teil0.tex index d32b316..f012225 100644 --- a/buch/papers/erdbeben/teil0.tex +++ b/buch/papers/erdbeben/teil0.tex @@ -22,11 +22,19 @@ Stoppt das Erdbeben, schwingt das Gehäuse nicht mehr. Die Masse schwing jedoch in seiner Eigendynamik weiter. Eine 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 einem Gehäuse, an dem zwei Federn und eine Masse befestigt sind. Der Seismograph ist in Abbildung ~\ref{erdbeben:Seismograph} ersichtlich. 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. +Für mehrere Dimensionen $(x,y,z)$ würde der Satz von Pythagoras für das System benötigt. +Da sich der Pythagoras bekanntlich nicht linear verhält, kann kein (lineares) Kalman-Filter implementiert werden. +Einfachheitshalber beschränken wir uns auf den linearen Fall, da dadurch die wesentlichen Punkte bereits aufgezeigt werden. +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. + + \begin{figure} \begin{center} \includegraphics[width=5cm]{papers/erdbeben/Apperatur} @@ -50,6 +58,7 @@ Im Fall unseres Seismographen, handelt es sich um ein Feder-Masse-Pendel. Dieser kann durch die Differentialgleichung zweiter Ordnung einer gedämpften Schwingung am harmonischen Oszillator beschrieben werden. Die Gleichung lautet: \begin{equation} + \label{erdbeben:Systemgleichung} m\ddot s + 2k \dot s + Ds = f. \end{equation} wobei $m$ die Masse, $k$ die Dämpfungskonstante und $D$ die Federkonstante bezeichnet. @@ -66,25 +75,19 @@ Somit entstehen die Gleichungen für die Geschwindigkeit $ \dot s_1(t)$ der Mass und \[ \dot s_2 = -\frac{D}{m} {s_1} -\frac{2k}{m} {s_2} + \frac{f} {m} \] für die Beschleunigung $\dot s_2(t)$ der Masse. -Diese können wir nun in der Form -\[ \ddot f =-\frac{D}{m} {s_1} -\frac{2k}{m} {s_2} + \frac{f} {m} \] -als skalare Gleichung darstellen. Die für uns relevanten Zustände sind die Position der Masse, die Geschwindigkeit der Masse und die äussere Beschleunigung des ganzen Systems. -Unüblich ist nun, dass der Stör-Term $f$ in Gleichung (20.1) gerade das ist, was wir eigentlich bestimmen möchten. +Unüblich ist nun, dass der Stör-Term $f$ in Gleichung~\eqref{erdbeben:Systemgleichung} gerade das ist, was wir eigentlich bestimmen möchten. In unserem Fall wird die äusseren Beschleunigung gesucht, da diese der Erdbebenanregung gleich kommt. Deshalb nehmen wir $f$ als dritte Grösse in den Zustandsvektor auf und definieren: \[ - x = (s_1, s_2, f)^T. +x= \left( \begin{array}{c} {s_1}\\ {s_2}\\{f}\end{array}\right)^T \] -Für die Standard-Form $\dot x = Ax$ brauchen wir als nächstes die Ableitungen aller Elemente von $x$. Für $\dot s_1$ und $\dot s_2$ folgen diese direkt aus Gleichung (20.1), aber über $\dot f$ wissen wir nichts. -Wir müssen also eine Annahme treffen: $\dot f = 0$. Diese Annahme ist im Allgemeinen falsch, aber etwas Besseres haben wir zurzeit nicht zur Verfügung. -Zudem treffen wir die Annahme, das sich die Kraft über die Beobachtungszeit nicht verändert. +Für die Standard-Form $\dot x = Ax$ brauchen wir als nächstes die Ableitungen aller Elemente von $x$. Für $\dot s_1$ und $\dot s_2$ folgen diese direkt aus Gleichung ~\eqref{erdbeben:Systemgleichung}, aber über $\dot f$ wissen wir nichts. +Wir müssen also eine Annahme treffen: $\dot f = 0$, somit verändert sich die Kraft über die Betrachtungszeit nicht. Diese Annahme ist im Allgemeinen falsch, aber etwas Besseres haben wir zurzeit nicht zur Verfügung. Wir werden dies in einem späteren Schritt kompensieren müssen. -Da die Kraft unbekannt ist, wird die letzte Zeile mit Nullen gefüllt, denn genau diese Werte wollen wir. - Durch Rücksubstituion ergibt sich uns folgende Systemgleichung in Matrix schreibweise, wobei $\dot {s_1}= v$ ist. Damit haben wir nun alles, was wir für die Matrix-Darstellung von Gleichung (20.1) benötigen. Diese lautet: \begin{equation} diff --git a/buch/papers/erdbeben/teil1.tex b/buch/papers/erdbeben/teil1.tex index 014b53e..4d6786f 100644 --- a/buch/papers/erdbeben/teil1.tex +++ b/buch/papers/erdbeben/teil1.tex @@ -20,38 +20,30 @@ Da wir die äussere Kraft nicht direkt messen können, benötigen wir ein Werkze Dies ist eine typische Anwendung für das Kalman-Filter. Das Filter schätzt den Zustand eines Systems anhand von Messungen und kann den nächsten Zustand errechnen und aus dieser Schätzung auch eine erwartete Messung herleiten. -Die für das Filter relevante Grösse ist dann nicht mehr die eigentliche Messung, sondern die Differenz aus Messung und Erwartung, da diese Differenz, die Innovation, eine Aussage über die nicht-deterministischen, externen Einflüsse auf das System ermöglicht. Das Filter berücksichtigt dazu nicht nur die Messung und den Zustand, sondern auch die Unsicherheiten dieser beiden Grössen, welche als Parameter in das Modell des Systems einfliessen. 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 mit der Eigendynamik des Systems multipliziert wird. -Die Idee dahinter ist, dass das Kalman-Filter die nicht-deterministische Grösse $f$ anhand der Messung und der Vorhersage zu bestimmen. +Durch Kenntnis über den aktuellen Zustand und der Eigendynamik des Systems berechnen wir eine Vorhersage des nächsten Zustandes. +Die für das Filter relevante Grösse ist dann nicht mehr die eigentliche Messung, sondern die Differenz aus Messung und Vorhersage, da diese Differenz, die Innovation, eine Aussage über die nicht-deterministischen, externen Einflüsse auf das System ermöglicht. -Für mehrere Dimensionen (x,y,z) würde der Satz von Pythagoras für das System benötigt. -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. -Einfachheitshalber beschränken wir uns auf den linearen Fall, da dadurch die wesentlichen Punkte bereits aufgezeigt werden. -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. +Die genau Herleitung des Kalman-Filter befindet sich für Interessierte im Wahrscheinlichkeit und Statistik Skript von A. Müller. +Im folgenden Abschnitt werden die Resultate zitiert. \subsection{Geschichte} Das Kalman-Filter wurde 1960 von Rudolf Emil Kalman entdeckt und direkt von der NASA für die Appollo Mission benutzt. -Das Filter kommt mit wenig Rechenleistung aus und war somit dafür geeignet die Rakete bei der Navigation zu unterstützen.
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. +Das Filter kommt mit wenig Rechenleistung aus und war somit dafür geeignet die Rakete bei der Navigation zu unterstützen. +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. +\subsection{Exkurs Wahrscheinlichkeit} + \label{erdbeben:Wahrscheindlichkeit} +Das Kalman-Filter schätzt den wahrscheinlichsten Wert zwischen Normalverteilungen, in unserem Fall sind dies die Messung und die Vorhersage. 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. -In der Abbildung~\ref{erdbeben: Zwei Normalverteilungen} sind zwei Funktionen dargestellt. +In der Abbildung~\ref{erdbeben:Gauss3} sind zwei Funktionen dargestellt. 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 in Abblidung~\ref{erdbeben: Zwei Normalverteilungen} sehen kann, ist sowohl der geschätzte Zustand als auch der gemessene Zustand normalverteilt und haben dementsprechend unterschiedliche Standardabweichungen $\sigma$ und Erwartungswerte $\mu$. Dies wird in~\cite{erdbeben:aragher_understanding_2012}beschrieben. -\begin{figure} - \begin{center} - \includegraphics[width=5cm]{papers/erdbeben/Gausskurve2.pdf} - \caption{Zwei Normalerteilungen; Die eine Funktion zeigt die Vorhersage, die andere die Messung} - \label{erdbeben: Zwei Normalverteilungen} - \end{center} -\end{figure} +Wie man am Beispiel der Gauss-Verteilungen in Abblidung~\ref{erdbeben:Gauss3} sehen kann, ist sowohl der geschätzte Zustand als auch der gemessene Zustand normalverteilt und haben dementsprechend unterschiedliche Standardabweichungen $\sigma$ und Erwartungswerte $\mu$. Das folgende wird in~\cite{erdbeben:aragher_understanding_2012}beschrieben. + Wir haben eine Vorhersage aus der Systemdynamik und eine Messung des Zustandes. Diese widersprechen sich im Allgemeinen. Jedoch wissen wir die Wahrscheinlichkeiten der beiden Aussagen. @@ -67,14 +59,17 @@ und der Messung: \] Diesen werden nun multipliziert und durch deren Fläche geteilt um sie wieder zu normieren, $\odot$ beschreibt dabei die Multiplikation und die Normierung auf den Flächeninhalt eins : \begin{align*} - {y_f}(x; {\mu_f}, {\sigma_f}) = {y_1}(x;{ \mu_1},{ \sigma_1}) \odot {y_2}(x; {\mu_2}, {\sigma_2}) + {y_f}(x; {\mu_f}, {\sigma_f}) + &= + {y_1}(x;{ \mu_1},{ \sigma_1}) \odot {y_2}(x; {\mu_2}, {\sigma_2}) + \\ &= \frac{1}{\sqrt{2\pi\sigma_1^2}}\quad e^{-\frac{(x-{\mu_1})^2}{2{\sigma_1}^2}} \odot \frac{1}{\sqrt{2\pi\sigma_2^2}}\quad e^{-\frac{(x-{\mu_2})^2}{2{\sigma_2}^2}} \\ &= \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{align*} -Diese Kombination der beiden Verteilungen resultiert wiederum in einer Normalverteilung +Durch geschicktes umformen resultiert aus der Kombination der beiden Verteilungen wiederum in einer Normalverteilung mit Erwartungswert \[ \mu_f = \frac{\mu_1\sigma_2^2 + \mu_2 \sigma_1^2}{\sigma_1^2 + \sigma_2^2} \] und Varianz @@ -83,30 +78,27 @@ und Varianz \] 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. -Somit ist $\mu_f$ ist das gewichtete Mittel der beiden $\mu_{1,2}$, und die Varianzen sind die Gewichte! +Somit ist $\mu_f$ das gewichtete Mittel der beiden $\mu_{1,2}$ und die Varianzen sind die Gewichte. +Das Interessante an $\mu_{f}$ ist, dass ${\mu_2}$ ${\sigma_1}$ beeinflusst. +Somit beeinflusst die Messung die Schätzung und umgekehrt. Die neue Funktion ist die best mögliche Schätzung für zwei Verteilungen, welche den selben Zustand beschreiben. Dies ist in der Abbildung~\ref{erdbeben:Gauss3} anhand der rote Funktion ersichtlich. \begin{figure} \begin{center} \includegraphics[width=5cm]{papers/erdbeben/Gausskurve3.pdf} - \caption{Durch das Multiplizieren der blauen und der orangen Verteilung entsteht die die rote, optimale Funktion} + \caption{Durch das Multiplizieren der blauen Mess- und der orangen Schätz-Verteilung entsteht die die rote, optimale Funktion} \label{erdbeben:Gauss3} \end{center} \end{figure} + Was in zwei 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{Filter-Matrizen} +\subsection{Filter-Matrizen} Da wir nun ein Werkzeug besitzen, dass die Beschleunigung, welche auf das Gehäuse wirkt, ermitteln kann, wird dieses nun Schritt für Schritt erklärt. 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{Fiter-Agorithmus} -Nachdem alle Parameter aufgestellt sind, wird das Filter initialisiert. -Zuerst wird der nächste Zustand der Masse vorhergesagt, danach wird die Messung präzisiert und laufend aktualisiert. -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. Dabei muss genau auf den Index geachtet werden. Nach dem Artikel~\cite{erdbeben:wikipedia} ist die Indexierung so genormt: Der Zeitschritt wird mit $k$ definiert, $k-1$ ist somit ein Zeitschritt vor $k$. Auf der linken Seite von | wird der aktuelle Zustand verlangt, bzw. ausgegeben, auf der rechten Seiten den bisherigen Zustand. @@ -114,79 +106,77 @@ Dies bedeutet, dass die Notation $x_{n|m}$ die Schätzung von $x$ zum Zeitpunkt \subsubsection*{Vorhersage} Im Filterschritt Vorhersage wird der nächste Zustand anhand des Anfangszustand und der Systemmatrix berechnet. -Dies funktioniert mit dem Rechenschritt: +Die Systemmatrix $A$ beschreibt ein kontinuierliches System $\dot x = Ax$. +Wir benötigen jedoch ein Zeit-diskretes System $x_{k+1} = \Phi x_k$. +Die Exponentialfunktion $\exp(At)$ beschreibt die Entwicklung eine Zustandes im Laufe der Zeit. +Die Übergangs-Matrix $\Phi$ erhalten wir folglich aus der Systemdynamikmatrix mittels Exponentialfunktion: +\[\Phi = \exp(A\Delta t). \] +Die Matrix $\Phi$ beschreibt die Übergänge zwischen zeitlich aufeinanderfolgenden Zuständen $x_{k-1}$ und $x_{k}$ anhand folgender Gleichung: \[ {x_{k|k-1}}=\Phi{x_{k-1|k-1}}= \exp(A\Delta t){x_{k-1|k-1}}. \] -Die Kovarianz $P_{k|k-1}$ wird ebenfalls neu berechnet. Zudem 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 + +Im Abschnitt ~\ref{erdbeben:Wahrscheindlichkeit} benötigten wir die Varianzen der Normalverteilungen. +Im mehrdimensionalen Fall übernimmt dies die Kovarinanzmatrix $P$. +Sie wird in jedem Schritt aktualisiert. +Dazu wird noch die Prozessunsicherheit $Q$ addiert, somit entsteht die Gleichung \[ {P_{k|k-1}}=\Phi {P_{k-1|k-1}} {\Phi _{k}}^T + {Q_{k-1}}. \] -Es vergeht genau $\Delta t$ Zeit, und dieser Vorgang wird wiederholt. -Das hochgestellte T bezeichnet die transponierte Matrix. -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. +Es vergeht genau $\Delta t$ Zeit, und dieser Vorgang wird wiederholt. 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. +Aus der Vorhersage des Zustandes $x_{k|k-1}$ und der Messmatrix $H$ erhalten wird eine Vorhersage der Messung. +Die Innovation \[ -{w_{k}}={z_{k}}-{H}{x_{k|k-1}}. +{w_{k}}={z_{k}}-{H}{x_{k|k-1}} \] -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. +beschreibt, wie genau die Vorhersage den aktuellen Messwert $z$ mittels der Systemmatrix $\Phi$ beschreiben kann. +Die Innovation ist der Teil der Messung, der nicht im Modell erfasst ist. +Dies leuchtet ein, eine Innovation von $0$ bedeutet, dass die Messung nichts Neues hervorbrachte. 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 leuchtet ein, 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. -\[ -{S_{k}}={H}{P_{k|k-1}}{H}^T+{R_{k}} -\] +Entsprechende Korrekturen werden dann gross bzw. nur gering ausfallen. \subsubsection*{Aktualisieren} -Im nächsten Schritt kommt nun die Wahrscheinlichkeit dazu. -\[{K_{k}}= {P_{k|k-1}} {H^T}{S_{k}^{-1}}\] -Die Grösse $K$ wird Kalman-Gain genannt. -Das Kalman-Gain gibt dem Zustand die Gewichtung, bzw. wie die Vorhersage auf den Zustand passt. -Vereinfacht gesagt: Es wird das das Verhältnis zwischen der Unsicherheit der Vorhersage $P_k$ zu der zugehörigen Messunsicherheit $R_k$ gebildet. -In unserem Fall wird werden die Elemente der Kalman-Matrix vorweg berechnet, da das Kalman-Gain ohne Messungen auskommt. - -Anhand der Informationen aus der Innovation wird das Kalman-Gain $K$ gebildet. Dabei beschreibt das Kalman-Gain die Wirkung der Innovation auf den geschätzten Zustand. So wird das System aktualisiert. + +Für eine optimale Schätzung des Zustandes muss die Vorhersage entsprechend der Innovation korrigiert werden. +In der Literatur findet man für eine optimales Korrektur die Gleichungen: +\begin{align*} +{S_{k}} &={H}{P_{k|k-1}}{H}^T+{R_{k}} +\\ +{K_{k}} &= {P_{k|k-1}} {H^T}{S_{k}^{-1}} +\end{align*} +Dabei ist $K$ das Kalman-Gain. +Mit dessen Hilfe erhalten wir die optimale Schätzung des nächsten Zustandes \[ -{x_{k|k}}={x_{k|k-1}}+{K_{k}}{w_{k}} +{x_{k|k}}={x_{k|k-1}}+{K_{k}}{w_{k}}. \] -Dabei wird der Unterschied zwischen dem erwarteten, errechneten, Zustand und dem gemessenen Zustand berechnet. - -Dazu kommt eine neue Kovarianz für den nächste Vorhersageschritt: +Dazu kommt eine neue Kovarianz $P$ für den nächste Vorhersageschritt: \[ {P_{k|k}}=(I-{K_{k}}{H}){P_{k|k-1}} \] -Der ganze Algorithmus und beginnt wieder mit der Vorhersage +Der ganze Algorithmus ist nun vollständig und beginnt wieder mit der Vorhersage \[ {x_{k|k-1}}=\Phi{x_{k-1|k-1}}= \exp(A\Delta t){x_{k|k-1}}. \] -\subsection{Anfangsbedingungen} +\subsection{Parameter und 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. \[ {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*{Systemmatrix $A$} +Für unseren Seismographen haben wir die entsprechende Matrixdarstellung in Gleichung ~\eqref{erdbeben:Systemgleichung} bereits gefunden. + \subsubsection*{Anfangsfehler / Kovarianzmatrix $P$} 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. - -Kovarianz: Cov(x, y) und Varianz: Var(x) = Cov(x, x) - 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 Kovarianzmatrix ergibt sich @@ -200,30 +190,9 @@ Als Initialwert für die Kovarianzmatrix ergibt sich \end{array} \right). \] -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$} -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-Matrix lautet daher: -\[ -A = \left( - \begin{array}{ccc} -0 & 1& 0 \\ -- \frac{D}{m} &-\frac{2k}{m} & \frac{1} {m}\\ -0 & 0& 0\\ -\end{array}\right) - \] -Dabei soll der Kalman-Filter in diskreten Zeitschritten $\Delta t$ arbeiten. -$A$ beschreibt ein kontinuierliches System ($\dot x = Ax$), wir benötigen jedoch ein Zeit-diskretes System $x_{k+1} = \Phi x_k$. -Die Übergangs-Matrix erhalten wir aus der Systemdynamikmatrix mittels Exponentialfunktion: -\[\Phi = \exp(A\Delta t). \] -Die Matrix $\Phi$ beschreibt die Übergänge zwischen zeitlich aufeinanderfolgenden Zuständen $x_{k-1}$ und $x_{k}$ \subsubsection*{Prozessrauschkovarianzmatrix $Q$} Die Prozessrauschmatrix teilt dem Filter mit, wie sich der Prozess verändert. @@ -258,43 +227,41 @@ 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{Zusammenfassung } -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 +Das Filter beginnt mit dem Anfangszustand für $k=0$ + +\begin{itemize} +\item Nächster Zustand vorhersagen \[ {x_{k|k-1}}=\Phi{x_{k-1|k-1}}= \exp(A\Delta t){x_{k-1|k-1}}. \] -2. Nächste Fehlerkovarianz vorhersagen + \item Nächste Fehlerkovarianz vorhersagen \[ {P_{k|k-1}}=\Phi {P_{k-1|k-1}} {\Phi _{k}}^T + {Q_{k-1}}. \] -3. Zustand wird gemessen +\item Innovation (= Messung - Vorhersage) \[ {w_{k}}={z_{k}}-{H}{x_{k|k-1}}. \] -4. Innovation (= Messung - Vorhersage) -\[ -{S_{k}}={H}{P_{k|k-1}}{H}^T+{R_{k}} -\] - -5. Das Kalman Filter anwenden -\[ -{K_{k}}= {P_{k|k-1}} {H^T}{S_{k}^{-1}} -\] +\item Das Kalman Filter anwenden +\begin{align*} +{S_{k}} &={H}{P_{k|k-1}}{H}^T+{R_{k}}\\ +{K_{k}} &= {P_{k|k-1}} {H^T}{S_{k}^{-1}} +\end{align*} -6. Schätzung aktualisieren +\item Schätzung aktualisieren \[ {x_{k|k}}={x_{k|k-1}}+{K_{k}}{w_{k}} \] -7. Fehlerkovarianz aktualisieren +\item Fehlerkovarianz aktualisieren \[ {P_{k|k}}=(I-{K_{k}}{H}){P_{k|k-1}} \] -8. Die Outputs von $k$ werden die Inputs für ${k-1}$ und werden wieder im Schritt 1 verwendet +\item Die Outputs von $k$ werden die Inputs für ${k-1}$ und werden wieder im Schritt 1 verwendet +\end{itemize} diff --git a/buch/papers/mceliece/funktionsweise.tex b/buch/papers/mceliece/funktionsweise.tex index 4a8a71f..3802820 100644 --- a/buch/papers/mceliece/funktionsweise.tex +++ b/buch/papers/mceliece/funktionsweise.tex @@ -166,7 +166,7 @@ Der verwendete Linear-Code wird im Abschnitt \ref{mceliece:subsection:seven_four \end{gather*} \item Öffentlicher Schlüssel: \index{Schlüssel, öffentlicher}% -\index{öffentlicher Schlüssel}% +\index{offentlicher Schlüssel@öffentlicher Schlüssel}% % \begin{itemize} % \item[] \begin{align*} diff --git a/buch/papers/multiplikation/einlteung.tex b/buch/papers/multiplikation/einlteung.tex index 3ffc24c..7637854 100755 --- a/buch/papers/multiplikation/einlteung.tex +++ b/buch/papers/multiplikation/einlteung.tex @@ -17,7 +17,7 @@ C_{ij} = \sum_{k=1}^n A_{ik} B_{kj}. \label{multiplikation:eq:MM} \end{equation} Grafisch kann die Matrizenmultiplikation $\mathbf{AB}=\mathbf{C}$ wie in Abbildung \ref{multiplikation:fig:mm_viz} visualisiert werden. -\index{Matrizenmultiplikation}% +\index{Matrixmultiplikation}% \index{Multiplikation, Matrizen-}% Im Fall einer Matrizengr\"osse von $2\times 2$ kann die Matrixgleichung \begin{equation} diff --git a/buch/papers/munkres/teil3.tex b/buch/papers/munkres/teil3.tex index ed8902c..8a0d2cb 100644 --- a/buch/papers/munkres/teil3.tex +++ b/buch/papers/munkres/teil3.tex @@ -21,7 +21,7 @@ Die Ungarische Methode wurde 1955 von Harold Kuhn entwickelt und veröffentlicht Der Name ``Ungarische Methode'' ergab sich, weil der Algorithmus weitestgehend auf den früheren Arbeiten zweier ungarischer Mathematiker basierte: Dénes Kőnig und Jenő Egerváry. -\index{Kőnig, Dénes}% +\index{Konig, Denes@Kőnig, Dénes}% \index{Egerváry, Jenő}% \index{Munkres, James}% James Munkres überprüfte den Algorithmus im Jahr 1957 und stellte fest, diff --git a/buch/papers/reedsolomon/anwendungen.tex b/buch/papers/reedsolomon/anwendungen.tex index 053c608..12bfe74 100644 --- a/buch/papers/reedsolomon/anwendungen.tex +++ b/buch/papers/reedsolomon/anwendungen.tex @@ -12,11 +12,11 @@ In diesem Abschnitt werden wir einige Anwendungen vorstellen, bei denen ein Reed All diese Anwendungen teilen das gleiche Problem: Die Daten können nur durch einen höchstwahrscheinlich fehlerbehafteten Kanal empfangen werden. Es gibt keine andere Methode, an diese Daten zu kommen, als über diesen Kanal. \rhead{Anwendungen} -In der Netzwerktechnik zum Beispiel ist es üblich, dass bei Paketverluste oder beschädigt empfangene Datenpaketen diese einfach noch einmal innert wenigen Millisekunden angefordert werden können. +In der Netzwerktechnik zum Beispiel ist es üblich, dass bei Paketverlusten oder beschädigt empfangenen Datenpaketen diese einfach noch einmal innert weniger Millisekunden angefordert werden können. \index{Paketverluste}% 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. \index{Raumfahrt}% -Diese Daten wiederum brauchen aufgrund der grossen Distanz Stunden bis die Daten beim Empfänger ankommen. +Diese Daten wiederum brauchen aufgrund der grossen Distanz Stunden, bis sie beim Empfänger ankommen. Fehlerhafte Daten können 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. @@ -26,7 +26,7 @@ Bei CDs oder DVDs gibt es zwar kein zeitliches Problem, jedoch erschweren Kratze \index{Digital Video Disk}% Da vor allem Produktionsfehler und Kratzer irreversibel sind und die Disk nicht nach jedem Kratzer ersetzt werden, wird die korrekte Ausgabe der gespeicherten Information durch die Fehlerkorrektur sichergestellt. -Einen ähnlichen Ansatz verfolgen QR-Codes, wobei die Information auch dann noch gelesen werden kann wenn der Code nicht mehr vollständig vorhanden ist. +Einen ähnlichen Ansatz verfolgen QR-Codes, wobei die Information auch dann noch gelesen werden kann, wenn der Code nicht mehr vollständig vorhanden ist. \index{QR-Code}% %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. @@ -39,11 +39,11 @@ Einen ähnlichen Ansatz verfolgen QR-Codes, wobei die Information auch dann noch % 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. +Obwohl all diese Codes nach dem gleichen Prinzip arbeiten, gibt es starke Unterschiede in deren Funktionsweise. +Dies kommt vor allem daher, dass die Codes nur Ressourcen zur Verfügung haben, die von der Hardware bereitgestellt werden, 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. +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. @@ -78,20 +78,20 @@ Um die Fähigkeit eines verwendeten Reed-Solomon-Codes zu beschreiben verwendet \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.} + \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 Jahre mit uns in Kontakt.} \index{Voyager 1 und 2}% \label{fig:voyager} \end{figure} \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 +Obwohl Reed-Solomon-Codes bereits in den 1960er Jahren 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 \index{Voyager Raumsonde}% \index{NASA}% 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. +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, +Ein Faltungscode ist wie ein Reed-Solomon-Code in der Lage, Fehler zu korrigieren, codiert seine Information aber auf eine andere Weise. Aus jedem unterteilten Block wird vor dem Versenden ein Paritätsbit erzeugt und dem Block angehängt. Anhand dieses Paritätsbits überprüft der Empfänger, ob bei der Übertragung der Block beschädigt wurde. Ist dies der Fall, wird der Block bei der Decodierung nicht beachtet. Diese so entstandenen ``Lücken'' im Datenstrom werden wiederum vom Reed-Solomon-Code korrigiert. Dieses Zusammenspiel beider Codes garantiert so eine hohe Robustheit gegenüber Übertragungsfehler. \begin{figure} @@ -102,7 +102,7 @@ codiert seine Information aber auf eine andere Weise. Aus jedem unterteilten Blo \subfigure[]{ \includegraphics[width=0.45\textwidth]{papers/reedsolomon/images/Compact_Disc_zoomed_in} } - \caption{CDs kamen 1982 auf den Markt. Sie funktioniert durch das Einpressen oder Einbrennen von Punkten und Strichen, die die Daten repräsentieren. Gelesen werden diese wiederum durch die Reflektion eines Lasers an diesen Punkten und Strichen.} + \caption{CDs kamen 1982 auf den Markt. Sie funktionieren durch das Einpressen oder 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} % @@ -122,11 +122,11 @@ codiert seine Information aber auf eine andere Weise. Aus jedem unterteilten Blo \subsection{CD/DVD} -Compact discs verwenden sogar zwei ineinander verschachtelte Reed-Solomon-Codes, einen (32,28)-Code und einen (28,24)-Code. +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 wird auch Cross-interleaved Reed-Solomon-Code (CIRC) genannt. \index{CIRC}% \index{Cross-interleaved Reed-Solomon code}% -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. +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.5$mm) 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. @@ -147,7 +147,7 @@ Die Digital Video Disc funktioniert nach dem selben Konzept mit grösseren Codeb % \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.} + \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, dass die Fehlerkorrekturfähigkeit von QR-Codes sich in insgesamt vier Levels aufteilen lassen. Das höchste Fehlerkorrektur-Level, das bei (a) angewendet wurde, ist in der Lage, bis zu 30\% der Daten wiederherzustellen. Das kleinste Level schafft etwa 7\%, das 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} @@ -165,19 +165,19 @@ Die Digital Video Disc funktioniert nach dem selben Konzept mit grösseren Codeb \subfigure[]{ \includegraphics[width=0.4\textwidth]{papers/reedsolomon/images/designer_qrcode} } - \caption{Während (a) noch einen unveränderten 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 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.} + \caption{Während (a) noch einen unveränderten 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 ein Teil des Codes durch ein Logo verdeckt wird, schränkt sich 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} \subsection{QR-Codes} \index{QR-Code}% -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. +Quick Response Codes oder auch QR-Codes funktionieren nach einem sehr ähnlichen Prinzip wie in unserem Beispiel die Abschnitte \ref{reedsolomon:section:codebsp} - \ref{reedsolomon:section:rekonstruktion}, nur der QR-Code in einem $\mathbb{F}_{256}$ Körper arbeitet. Die physische Grösse eines Codes ist stark abhängig von der Menge an codierten Daten sowie dem verwendeten Fehlerkorrektur-Level. -Es ist so auf dem ersten Blick nicht ersichtlich, wie viel Nutzinformationen ein QR-Code enthält. +Es ist so auf den 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. \index{Designed-QR-Code}% -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 in Abbildung \ref{fig:designqr} zu finden. +Dabei wird z.~B.~das Firmenlogo oder ein Schriftzug über den QR-Code gelegt, ohne dass die Funktion des Codes beeinträchtigt wird. Ein Beispiel dazu ist in Abbildung \ref{fig:designqr} zu finden. % diff --git a/buch/papers/reedsolomon/codebsp.tex b/buch/papers/reedsolomon/codebsp.tex index 67f33da..037fba7 100644 --- a/buch/papers/reedsolomon/codebsp.tex +++ b/buch/papers/reedsolomon/codebsp.tex @@ -9,7 +9,7 @@ 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 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. +Zur Hilfestellung beim 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. \rhead{Codierung eines Beispiels} @@ -26,7 +26,7 @@ Der Nachrichtenblock im Beispiel besteht aus \[ n = q - 1 = 10 \text{ Zahlen}, \] -wobei die Null weggelassen wird. Wenn wir versuchen würden, mit der Null zu codieren, so stellen wir fest, dass wir wieder Null an der gleichen Stelle erhalten und somit wäre die Codierung nicht eindeutig. +wobei die Null weggelassen wird. Wenn wir versuchen würden, mit der Null zu codieren, stellen wir fest, dass wir wieder null an der gleichen Stelle erhalten und somit wäre die Codierung nicht eindeutig. % Notes %Da bei allen Codes, die codiert werden wird an der gleichen Stelle eine Nullstelle auftreten. @@ -37,28 +37,28 @@ wobei die Null weggelassen wird. Wenn wir versuchen würden, mit der Null zu cod %n = q - 1 = 10 \text{ Zahlen}. %\] -Im nächsten Schritt bestimmen wir, wie viele Fehler $t$ maximal während der Übertragung auftreten dürfen, damit wir sie noch korrigieren können. +Im nächsten Schritt bestimmen wir, wie viele Fehler $t$ während der Übertragung maximal auftreten dürfen, damit wir sie noch korrigieren können. Unser Beispielcode sollte in der Lage sein \[ t = 2 \] Fehlerstellen korrigieren zu können. -Die Grösse des Nutzdatenteils hängt von der Grösse des Nachrichtenblocks sowie der Anzahl der Fehlerkorrekturstellen ab. Je robuster der Code sein muss, desto weniger Platz für Nutzdaten $k$ bleibt in der Nachricht übrig. -Bei maximal 2 Fehler können wir noch +Die Grösse des Nutzdatenteils hängt von der Grösse des Nachrichtenblocks sowie der Anzahl der Fehlerkorrekturstellen ab. Je robuster der Code sein muss, desto weniger Platz bleibt für Nutzdaten $k$ in der Nachricht übrig. +Bei maximal 2 Fehlern können wir noch \[ k = n - 2t = 6\text{ Zahlen} \] übertragen. -Zusammenfassend haben wir einen Nachrichtenblock mit der Länge von 10 Zahlen definiert, der 6 Zahlen als Nutzlast beinhaltet und in der Lage ist, aus 2 fehlerhafte Stellen im Block die ursprünglichen Nutzdaten zu rekonstruieren. Zudem werden wir im Weiteren feststellen, dass dieser Code maximal vier Fehlerstellen erkennen, diese aber nicht rekonstruieren kann. +Zusammenfassend haben wir einen Nachrichtenblock mit der Länge von 10 Zahlen definiert, der 6 Zahlen als Nutzlast beinhaltet und in der Lage ist, aus 2 fehlerhaften Stellen im Block die ursprünglichen Nutzdaten zu rekonstruieren. Zudem werden wir im Weiteren feststellen, dass dieser Code maximal vier Fehlerstellen erkennen, diese aber nicht rekonstruieren kann. Wir legen nun für das Beispiel die Nachricht \[ m = [0,0,0,0,4,7,2,5,8,1] \] fest, die wir gerne an einen Empfänger übertragen möchten, wobei die vorderen vier Stellen für die Fehlerkorrektur zuständig sind. -Solange diese Stellen vor dem Codieren und nach dem Decodieren den Wert null haben, so ist die Nachricht fehlerfrei übertragen worden. +Solange diese Stellen vor dem Codieren und nach dem Decodieren den Wert null haben, ist die Nachricht fehlerfrei übertragen worden. Da wir in den folgenden Abschnitten mit Polynomen arbeiten, stellen wir die Nachricht auch noch als Polynom \[ @@ -77,7 +77,7 @@ dar. \label{reedsolomon:subsection:diskFT}} Im vorherigen Abschnitt \ref{reedsolomon:section:dtf} haben wir schon einmal die diskrete Fouriertransformation zum Codieren einer Nachricht verwendet. In den endlichen Körpern wird dies jedoch nicht gelingen, da die Eulersche 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. +Wir wählen deshalb eine Zahl $a$, die die gleiche Aufgabe 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\} @@ -119,17 +119,18 @@ in die von $a$ abhängige Schreibweise \index{Einheitswurzel, primitiv}% 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\}$ \\ -$a = 2$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1, 2, 4, 8, 5, 10, 9, 7, 3, 6\}$ & $ = $ & $\mathbb{F}_{11}\setminus\{0\}$ \\ -$a = 3$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1, 3, 9, 5, 4, 1, 3, 9, 5, 4\}$ & $\neq$ & $\mathbb{F}_{11}\setminus\{0\}$ \\ -$a = 4$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1, 4, 5, 9, 3, 1, 4, 5, 9, 3\}$ & $\neq$ & $\mathbb{F}_{11}\setminus\{0\}$ \\ -$a = 5$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1, 5, 3, 4, 9, 1, 5, 3, 4, 9\}$ & $\neq$ & $\mathbb{F}_{11}\setminus\{0\}$ \\ -$a = 6$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1, 6, 3, 7, 9, 10, 5, 8, 4, 2\}$ & $ = $ & $\mathbb{F}_{11}\setminus\{0\}$ \\ -$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\}$. \\ +\def\s{\phantom{0}} +\begin{tabular}{c c c c c c l} +$a = \s1$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1,\s1,\s1,\s1,\s1,\s1,\s1,\s1,\s1,\s1\}$ & $\neq$ & $\mathbb{F}_{11}\setminus\{0\}$ \\ +$a = \s2$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1,\s2,\s4,\s8,\s5,10,\s9,\s7,\s3,\s6\}$ & $ = $ & $\mathbb{F}_{11}\setminus\{0\}$ \\ +$a = \s3$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1,\s3,\s9,\s5,\s4,\s1,\s3,\s9,\s5,\s4\}$ & $\neq$ & $\mathbb{F}_{11}\setminus\{0\}$ \\ +$a = \s4$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1,\s4,\s5,\s9,\s3,\s1,\s4,\s5,\s9,\s3\}$ & $\neq$ & $\mathbb{F}_{11}\setminus\{0\}$ \\ +$a = \s5$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1,\s5,\s3,\s4,\s9,\s1,\s5,\s3,\s4,\s9\}$ & $\neq$ & $\mathbb{F}_{11}\setminus\{0\}$ \\ +$a = \s6$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1,\s6,\s3,\s7,\s9, 10,\s5,\s8,\s4,\s2\}$ & $ = $ & $\mathbb{F}_{11}\setminus\{0\}$ \\ +$a = \s7$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1,\s7,\s5,\s2,\s3,10,\s4,\s6,\s9,\s8\}$ & $ = $ & $\mathbb{F}_{11}\setminus\{0\}$ \\ +$a = \s8$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1,\s8,\s9,\s6,\s4, 10,\s3,\s2,\s5,\s7\}$ & $ = $ & $\mathbb{F}_{11}\setminus\{0\}$ \\ +$a = \s9$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1,\s9,\s4,\s3,\s5,\s1,\s9,\s4,\s3,\s5\}$ & $\neq$ & $\mathbb{F}_{11}\setminus\{0\}$ \\ +$a = 10$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1, 10,\s1,10,\s1, 10,\s1, 10,\s1, 10\}$ & $\neq$ & $\mathbb{F}_{11}\setminus\{0\}$. \\ \end{tabular} \end{center} %\begin{center} @@ -147,15 +148,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} -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$. +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 Einheitswurzeln \em genannt. +Wenden wir diese Vorgehensweise auch für andere endliche Körper an, so werden wir sehen, dass wir immer mindestens zwei solcher Einheitswurzeln finden werden. Somit ist es uns überlassen, eine dieser Einheitswurzeln 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}} \index{Transformationsmatrix}% -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 +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. @@ -164,7 +165,7 @@ Für die Codierung setzen wir alle Zahlen in $\mathbb{F}_{11}\setminus\{0\}$ nac \begin{tabular}{c} $m(8^0) = 4 \cdot 1^5 + 7 \cdot 1^4 + 2 \cdot 1^3 + 5 \cdot 1^2 + 8 \cdot 1^1 + 1 = 5$ \\ $m(8^1) = 4 \cdot 8^5 + 7 \cdot 8^4 + 2 \cdot 8^3 + 5 \cdot 8^2 + 8 \cdot 8^1 + 1 = 3$ \\ - \vdots \\ + \vdots \\[5pt] $m(8^9) = 4 \cdot 7^5 + 7 \cdot 7^4 + 2 \cdot 7^3 + 5 \cdot 7^2 + 8 \cdot 7^1 + 1 = 4$ \end{tabular} \end{center} @@ -175,7 +176,7 @@ als unser Übertragungsvektor. \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. -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: +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: \[ v = A \cdot m \qquad \Rightarrow \qquad v = \begin{pmatrix} 8^0& 8^0& 8^0& 8^0& 8^0& 8^0& 8^0& 8^0& 8^0& 8^0\\ diff --git a/buch/papers/reedsolomon/decmitfehler.tex b/buch/papers/reedsolomon/decmitfehler.tex index 97694ae..6cea758 100644 --- a/buch/papers/reedsolomon/decmitfehler.tex +++ b/buch/papers/reedsolomon/decmitfehler.tex @@ -7,8 +7,8 @@ \label{reedsolomon:section:decmitfehler}} \rhead{Decodierung mit Fehler} Bisher haben wir die Decodierung unter der Bedingung durchgeführt, dass der Übertragungsvektor fehlerlos versendet und empfangen wurde. -In der realen Welt müssen wir uns jedoch damit abfinden, dass kein Übertragungskanal garantiert fehlerfrei ist und das wir früher oder später mit Fehlern rechnen müssen. -Genau für dieses Problem wurden Fehler korrigierende Codes, wie der Reed-Solomon-Code, entwickelt. +In der realen Welt müssen wir uns jedoch damit abfinden, dass kein Übertragungskanal garantiert fehlerfrei ist und dass wir früher oder später mit Fehlern rechnen müssen. +Genau für dieses Problem wurden Fehler korrigierende Codes wie der Reed-Solomon-Code entwickelt. In diesem Abschnitt betrachten wir somit die Idee der Fehlerkorrektur und wie wir diese auf unser Beispiel anwenden können. Der Übertragungskanal im Beispiel weist jetzt den Fehlervektor @@ -79,7 +79,7 @@ Wir stellen jedoch recht schnell fest, dass am decodierten Nachrichtenblock r = [\underbrace{5,7,4,10,}_{\displaystyle\text{Syndrom}}5,4,5,7,6,7] \] etwas nicht in Ordnung ist, denn die vorderen vier Fehlerkorrekturstellen haben nicht mehr den Wert null. -Der Nachrichtenblock weisst jetzt ein {\em Syndrom} auf, welches anzeigt, dass der Übertragungsvektor fehlerhaft empfangen wurde. +Der Nachrichtenblock weist jetzt ein {\em Syndrom} auf, welches anzeigt, dass der Übertragungsvektor fehlerhaft empfangen wurde. \index{Syndrom}% % Old Text %Wenn wir den Übertragungsvektor jetzt Rücktransformieren wie im vorherigen Kapitel erhalten wir @@ -92,7 +92,7 @@ Jetzt stellt sich natürlich die Frage, wie wir daraus den ursprünglich gesende \subsection{Das Fehlerstellenpolynom $d(X)$ \label{reedsolomon:subsection:fehlerpolynom}} Bevor wir unser Lokatorpolynom berechnen können, müssen wir zuerst eine Möglichkeit finden, die fehlerhaften von den korrekten Stellen im Übertragungsvektor unterscheiden zu können. -In einem ersten Versuch berechnen wir die Differenz $d$ des empfangenen und dem gesendeten Übertragungsvektor mit +In einem ersten Versuch berechnen wir die Differenz $d$ des empfangenen und des gesendeten Übertragungsvektors mit %Alle Stellen in $d$, die nicht null sind sind demnach fehler. % %In einem ersten Versuch könnten wir $d$ berechnen mit @@ -107,11 +107,11 @@ und nennen $d(X)$ unser {\em Fehlerstellenpolynom}. \index{Fehlerstellenpolynom}% Dieses Polynom soll uns sagen, welche Stellen korrekt und welche fehlerhaft sind. -Durch das Verwenden von $m(X)$ stossen wir auf weitere Probleme, da wir den Nachrichtenvektor auf der Empfängerseite nicht kennen (unser Ziel ist es ja genau diesen zu finden). Dieses Problem betrachten wir im Abschnitt \ref{reedsolomon:subsection:nachrichtenvektor} genauer. Um die Überlegungen in den folgenden Abschnitten besser zu verstehen sei $m(X)$ bekannt auf der Empfängerseite. +Durch das Verwenden von $m(X)$ stossen wir auf weitere Probleme, da wir den Nachrichtenvektor auf der Empfängerseite nicht kennen (unser Ziel ist es ja, genau diesen zu finden). Dieses Problem betrachten wir in Abschnitt \ref{reedsolomon:subsection:nachrichtenvektor} genauer. Um die Überlegungen in den folgenden Abschnitten besser zu verstehen, sei $m(X)$ bekannt auf der Empfängerseite. %Dies wird uns zwar andere sorgen wegen $m(X)$ bereiten, wir werden werden deshalb erst in Abschnitt \ref{reedsolomon:subsection:nachrichtenvektor} darauf zurückkommen. -Setzen wir jetzt unsere Einheitswurzel aus dem Beispiel ein so erhalten wir +Setzen wir jetzt unsere Einheitswurzel aus dem Beispiel ein, erhalten wir % Old Text %\begin{align} % m(X) & = 4X^5 + 7X^4 + 2X^3 + 5X^2 + 8X + 1 \\ @@ -130,10 +130,10 @@ Setzen wir jetzt unsere Einheitswurzel aus dem Beispiel ein so erhalten wir \hline \end{tabular} \end{center} -und damit die Information, dass allen Stellen, die nicht Null sind, Fehler enthalten. -Aus der Tabelle lesen wir ab, das in unserem Beispiel die Fehler an der Stelle $3$ und $8$ zu finden sind. +und damit die Information, dass alle Stellen, die nicht null sind, Fehler enthalten. +Aus der Tabelle lesen wir ab, dass in unserem Beispiel die Fehler an der Stelle $3$ und $8$ 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. +Für das einfache Bestimmen von Hand mag dies ja noch ausreichen. Wir können jedoch mit diesen Stellen das Lokatorpolynom nicht bestimmen, denn dafür würden wir alle Nullstellen gebrauchen, an denen es Fehler gegeben hat (also sozusagen genau das Umgekehrte). Um dies zu erreichen, wenden wir eine andere Herangehensweise an und nehmen uns den Satz von Fermat sowie den kleinsten gemeinsamen Teiler zu Hilfe. \subsection{Mit dem grössten gemeinsamen Teiler auf Nullstellenjagd \label{reedsolomon:subsection:ggT}} @@ -158,7 +158,7 @@ Wir können jetzt auch $d(X)$ nach der gleichen Überlegung darstellen als d(X) = (X-a^0)(X-a^1)(X-a^2)\textcolor{gray!40}{(X-a^3)}(X-a^4)(X-a^5)(X-a^6)(X-a^7)\textcolor{gray!40}{(X-a^8)}(X-a^9) \cdot p(x), \] wobei diese Darstellung nicht mehr alle Nullstellen umfasst wie es noch in $f(X)$ der Fall war. -Dies liegt daran, dass wir ja zwei Fehlerstellen (grau markiert) haben, die nicht Null sind. Diese fassen wir zum Restpolynom $p(X)$ zusammen. +Dies liegt daran, dass wir ja zwei Fehlerstellen (grau markiert) haben, die nicht null sind. Diese fassen wir zum Restpolynom $p(X)$ zusammen. Wenn wir jetzt den grössten gemeinsamen Teiler von $f(X)$ und $d(X)$ berechnen, so erhalten wir mit \[ \operatorname{ggT}(f(X),d(X)) = (X-a^0)(X-a^1)(X-a^2)\textcolor{gray!40}{(X-a^3)}(X-a^4)(X-a^5)(X-a^6)(X-a^7)\textcolor{gray!40}{(X-a^8)}(X-a^9) @@ -172,7 +172,7 @@ Dies scheint zuerst nicht sehr hilfreich zu sein, da wir für das Lokatorpolynom \label{reedsolomon:subsection:kgV}} \index{kgV}% \index{kleinstes gemeinsames Vielfaches}% -Das kgV hat nämlich die Eigenschaft sämtliche Nullstellen zu finden, also nicht nur die fehlerhaften sondern auch die korrekten, was in +Das kgV hat nämlich die Eigenschaft, sämtliche Nullstellen zu finden, also nicht nur die fehlerhaften, sondern auch die korrekten, was in \[ \operatorname{kgV}(f(X),d(X)) = (X-a^0)(X-a^1)(X-a^2)(X-a^3)(X-a^4)(X-a^5)(X-a^6)(X-a^7)(X-a^8)(X-a^9) \cdot q(X). \] @@ -187,8 +187,8 @@ Somit ist l(X) = (X-a^3)(X-a^8) \] unser gesuchtes Lokatorpolynom. -Es scheint so als müssten wir nur noch an den besagten Stellen den Übertragungsvektor korrigieren und wir wären fertig mit der Fehlerkorrektur. -Jedoch haben wir noch ein grundlegendes Problem, dass zu Beginn aufgetaucht ist, wir aber beiseite geschoben haben. Die Rede ist natürlich vom Nachrichtenvektor $m(X)$, mit dem wir in erster Linie das wichtige Fehlerstellenpolynom $d(X)$ berechnet haben, auf der Empfängerseite aber nicht kennen. +Es scheint so als müssten wir nur noch den Übertragungsvektor an den besagten Stellen korrigieren und wir wären fertig mit der Fehlerkorrektur. +Jedoch haben wir noch ein grundlegendes Problem, das zu Beginn aufgetaucht ist, wir aber beiseite geschoben haben. Die Rede ist natürlich vom Nachrichtenvektor $m(X)$, mit dem wir in erster Linie das wichtige Fehlerstellenpolynom $d(X)$ berechnet haben, auf der Empfängerseite aber nicht kennen. \subsection{Der problematische Nachrichtenvektor $m(X)$ \label{reedsolomon:subsection:nachrichtenvektor}} @@ -198,8 +198,8 @@ 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 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 haben jedoch 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 funktionieren. 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 @@ -211,7 +211,7 @@ Im Normalfall sollen diese nämlich den Wert $0$ haben und somit sind nur die le \[ m = [0,0,0,0,?,?,?,?,?,?]. \] -Nach der Definition des Reed-Solomon-Codes soll an genau diesen vier Stellen auch die Information befinden, wo die Fehlerstellen liegen. Daher reicht es auch aus +Nach der Definition des Reed-Solomon-Codes soll sich an genau diesen vier Stellen auch die Information befinden, wo die Fehlerstellen liegen. Daher reicht es auch aus % darum werden die stellen auch als fehlerkorrekturstellen bezeichnet \[ d(X) = 5X^9 + 7X^8 + 4X^7 + 10X^6 + p(X) @@ -221,7 +221,7 @@ so zu berechnen, dass wir die wichtigen vier Stellen kennen, der Rest des Polyno \subsection{Die Berechnung der Fehlerstellen \label{reedsolomon:subsection:nachrichtenvektor}} \index{Fehlerstellen}% -Um die Fehlerstellen zu berechnen wenden wir die gleiche Vorgehensweise wie zuvor an, also zuerst den ggT, danach berechnen wir das kgV um am Ende das Lokatorpolynom zu erhalten. +Um die Fehlerstellen zu berechnen wenden wir die gleiche Vorgehensweise wie zuvor an, also zuerst den ggT, danach berechnen wir das kgV, um am Ende das Lokatorpolynom zu erhalten. \subsubsection{Schritt 1: ggT} @@ -285,7 +285,7 @@ und erhalten \subsubsection{Schritt 2: kgV} -Mit dem Resultat das wir vom ggT erhalten haben können wir jetzt das kgV berechnen. Dazu können wir jetzt den erweiterten Euklidischen Algorithmus verwenden, den wir in Abschnitt \ref{buch:subsection:daskgv} kennengelernt haben. +Mit dem Resultat, das wir vom ggT erhalten haben, können wir jetzt das kgV berechnen. Dazu können wir jetzt den erweiterten Euklidischen Algorithmus verwenden, den wir in Abschnitt \ref{buch:subsection:daskgv} kennengelernt haben. % %Mit den Resultaten, die wir vom Rechenweg des grössten gemeinsamen Teiler erhalten haben können wir jetzt auch das kleinste Gemeinsame Vielfache berechnen. Eine detailliertere Vorgehensweise findet man in Kapitel ???. % @@ -314,14 +314,14 @@ Unser gesuchtes Lokatorpolynom hat also die Form l(X) = (X-a^i)(X-a^j). \] Also brauchen wir nur noch $i$ und $j$ zu berechnen und wir haben unsere gesuchten Fehlerstellen. -Diese bekommen wir recht einfach mit +Diese erhalten wir recht einfach mit \begin{equation*} \begin{aligned} a^i &= 5 &&\Rightarrow & i &= 3\\ a^j &= 6 &&\Rightarrow & j &= 8. \end{aligned} \end{equation*} -Schlussendlich erhalten wir +Schliesslich erhalten wir \[ d(X) = (X-a^3)(X-a^8) \] diff --git a/buch/papers/reedsolomon/decohnefehler.tex b/buch/papers/reedsolomon/decohnefehler.tex index 2c755f9..bb5656b 100644 --- a/buch/papers/reedsolomon/decohnefehler.tex +++ b/buch/papers/reedsolomon/decohnefehler.tex @@ -7,9 +7,9 @@ \label{reedsolomon:section:decohnefehler}} \rhead{Decodierung ohne Fehler} -In diesem Abschnitt betrachten wie die Überlegung, wie wir auf der Empfängerseite die Nachricht aus dem empfangenen Übertragungsvektor erhalten. Nach einer einfachen Überlegung müssen wir den Übertragungsvektor decodieren, was auf den ersten Blick nicht allzu kompliziert sein sollte, solange wir davon ausgehen können, dass es während der Übertragung keine Fehler gegeben hat. Wir betrachten deshalb den Übertragungskanal als fehlerfrei. +In diesem Abschnitt betrachten wir die Überlegung, wie wir auf der Empfängerseite die Nachricht aus dem empfangenen Übertragungsvektor erhalten. Nach einer einfachen Überlegung müssen wir den Übertragungsvektor decodieren, was auf den ersten Blick nicht allzu kompliziert sein sollte, solange wir davon ausgehen können, dass es während der Übertragung keine Fehler gegeben hat. Wir betrachten deshalb den Übertragungskanal als fehlerfrei. -Der Übertragungsvektor empfangen wir also als +Den Übertragungsvektor empfangen wir also als \[ v = [5,3,6,5,2,10,2,7,10,4]. \] @@ -27,13 +27,13 @@ Nach einem banalen Ansatz ist die Decodierung die Inverse der Codierung. Dank de v = A \cdot m \qquad \Rightarrow \qquad m = A^{-1} \cdot v \] Nur stellt sich jetzt die Frage, wie wir die Inverse von $A$ berechnen. -Dazu können wir wiederum den Ansatz der Fouriertransformation uns zur Hilfe nehmen, +Dazu können wir wiederum den Ansatz der Fouriertransformation zu Hilfe nehmen, jedoch betrachten wir jetzt deren Inverse. 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. \] -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 +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 \index{Korrekturfaktor}% %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$. \[ @@ -47,13 +47,13 @@ Mit einem solchen Problem haben wir uns bereits in Abschnitt \ref{buch:section:e \subsection{Inverse der primitiven Einheitswurzel \label{reedsolomon:subsection:invEinh}} \index{Inverse}% -Die Funktionsweise des euklidischen Algorithmus ist im Abschnitt \ref{buch:section:euklid} ausführlich beschrieben. +Die Funktionsweise des euklidischen Algorithmus ist in Abschnitt \ref{buch:section:euklid} ausführlich beschrieben. Für unsere Anwendung wählen wir die Parameter $a = 8$ und $b = 11$ ($\mathbb{F}_{11}$). Daraus erhalten wir \begin{center} -\begin{tabular}{| c | c c | c | r r |} +\begin{tabular}{| c | r r | c | r r |} \hline $k$ & $a_i$ & $b_i$ & $q_i$ & $c_i$ & $d_i$\\ \hline @@ -106,9 +106,9 @@ Die inverse Transformationsmatrix $A^{-1}$ bilden wir, indem wir jetzt die inver \subsection{Der Faktor $s$ \label{reedsolomon:subsection:sfaktor}} Die diskrete Fouriertransformation benötigt für die Inverse einen Vorfaktor von $\frac{1}{2\pi}$. -Wir müssen also damit rechnen, dass wir für die Inverse Transformationsmatrix ebenfalls einen solchen Vorfaktor 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 @@ -152,7 +152,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. So erhalten wir $10^{-1} = 10$ als 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 index a50a134..587d36c 100644 --- a/buch/papers/reedsolomon/dtf.tex +++ b/buch/papers/reedsolomon/dtf.tex @@ -4,10 +4,10 @@ \section{Übertragung mit Hilfe der diskreten Fourier-Transformation \label{reedsolomon:section:dtf}} \rhead{Fehlerkorrektur mit diskreter Fourier-Transformation} -Die Grundidee eines fehlerkorrigierenden Code ist, dass Informationen eines Datenpunktes -durch die Codierung auf viele übertragene Werte verteilt werden. +Die Grundidee eines fehlerkorrigierenden Codes ist, dass Informationen eines Datenpunktes +durch die Codierung auf viele übertragenen Werte verteilt werden. Die Decodierung ist in der Lage, den ursprünglichen Datenwert zu rekonstruieren, -sogar wenn einzelne wenige übertragene Werte beschädigt worden sind. +sogar wenn einzelne wenig übertragene Werte beschädigt worden sind. \par Die Fourier-Transformation transformiert einen einzelnen Wert, \index{Fourier-Transformation}% @@ -23,7 +23,7 @@ für Codierung und Decodierung zu verwenden. \subsection{Beispiel: Fehlerkorrektur mit Fourier-Transformation \label{reedsolomon:subsection:sendbsp}} Das folgende Beispiel soll zeigen, wie die Idee der Fehlerkorrektur umgesetzt wurde. -Die Fehlererkennung des Reed-Solomon-Codes funktioniert nach einem sehr Ähnlichen Prinzip. +Die Fehlererkennung des Reed-Solomon-Codes funktioniert nach einem sehr ähnlichen Prinzip. \index{Reed-Solomon-Code}% %Das folgende Beispiel soll zeigen, wie Fehlerkorrektur möglich ist. @@ -31,8 +31,8 @@ Die Fehlererkennung des Reed-Solomon-Codes funktioniert nach einem sehr Ähnlich %der später erklärt wird, analog ist. \par Der Auftrag besteht darin, 64 Datenwerte zu übertragen, 32 Fehler erkennen können und bis zu 16 Fehler zu rekonstruieren. -Mit Hilfe der Fourier-Transformation werden die \textcolor{blue}{blauen Datenpunkte} transformiert, -zu den \textcolor{darkgreen}{grünen Übertragungspunkten}. +Mit Hilfe der Fourier-Transformation werden die \textcolor{blue}{blauen Datenpunkte} +zu den \textcolor{darkgreen}{grünen Übertragungspunkten} transformiert. Durch eine Rücktransformation können die \textcolor{blue}{blauen Datenpunkte} wieder rekonstruiert werden. \begin{figure}%[!ht] @@ -45,17 +45,17 @@ Durch eine Rücktransformation können die \textcolor{blue}{blauen Datenpunkte} \label{fig:sendorder} \end{figure} In der Abbildung \ref{fig:sendorder} wird eine Übertragung Schritt für Schritt illustriert. -In der folgenden Aufzählung werden diese einzelne Schritte erklärt und erläutert: +In der folgenden Aufzählung werden diese einzelnen Schritte erklärt und erläutert: \begin{enumerate}[(1)] \item Das Signal besteht aus 64 zufälligen, ganzzahligen Datenwerten zwischen 0 und 10. - Für die Rekonstruktion werden zusätzliche Datenwerte benötigt, wir fügen deshalb 32 Werte hinzu. + Für die Rekonstruktion werden zusätzliche Datenwerte benötigt. Wir fügen deshalb 32 Werte hinzu. Diese setzen wir willkürlich alle auf Null und nennen sie {\em Fehlerkorrekturstellen}. \index{Fehlerkorrekturstellen}% Wir erhalten so einen erweiterten Signalvektor der Länge $N =96$. \index{Signalvektor}% \item Mit der Fourier-Transformation wird der ganze Signalvektor codiert. Dadurch wird jede Informationseinheit auf alle Punkte des Spektrums verteilt. - \item Wir dürfen annehmen, dass bei der Übertragung, nur einzelne übertragene + \item Wir dürfen annehmen, dass bei der Übertragung nur einzelne übertragene Werte durch Fehler verändert werden. \par Im Beispiel sind dies die Werte an den Stellen 6, 20 und 74 (\textcolor{red}{rote Kurve}), @@ -68,10 +68,10 @@ In der folgenden Aufzählung werden diese einzelne Schritte erklärt und erläut \par Sind Übertragungsfehler aufgetreten, werden an diesen Stellen die Werte von Null abweichen. Somit haben wir bereits Fehler erkannt. - \item Die Werte an den Fehlerkorrekturstellen 64--96, die nicht mehr Null sind, nennen wir das {\em Syndrom}. + \item Die Werte an den Fehlerkorrekturstellen 64--96, die nicht mehr null sind, nennen wir das {\em Syndrom}. \index{Syndrom}% Im Syndrom steckt nur Information über die Fehler, sie werden durch die inverse Fourier-Transformation erzeugt. - \item Um die Fehler zu rekonstruieren, kann man versuchen, die Information im Syndrom mit Fourier-Transformation zu transformieren. + \item Um die Fehler zu rekonstruieren kann man versuchen, die Information im Syndrom mit Fourier-Transformation zu transformieren. Da das Syndrom nur ein Teil der Fehlerinformation ist, liefert die Fourier-Transformation eine Approximation der Fehler. Diese Approximation der Fehler ist genau genug, um die Fehlerstellen zu lokalisieren. \end{enumerate} @@ -100,7 +100,7 @@ Die Analogie geht aber noch weiter. Schreibt man \( w = e^{-\frac{2\pi j}{N} k}\) - \label{reedsolomon:DFT_summand}, damit wird aus der Formel + \label{reedsolomon:DFT_summand}, wird aus der Formel \begin{equation} \hat{c}_{k} = \frac{1}{N} \sum_{n=0}^{N-1} @@ -121,12 +121,12 @@ Die Analogie geht aber noch weiter. \label{reedsolomon:DFT_polynom2} \end{equation} für verschiedene \( w = e^{-\frac{2\pi j}{N} k}, k=1, \dots ,N-1\) übermittelt. -Das Syndrom entstand durch die Wahl ${f_{64}}=0$ bis ${f}_{N-1}=0$ (graue Koeffizenten). +Das Syndrom entstand durch die Wahl ${f_{64}}=0$ bis ${f}_{N-1}=0$ (graue Koeffizienten). Die Polynominterpolation und die Fourier-Transformation rechnen beide mit reellen Zahlen. Wenn die Approximation nicht mehr genügend gut ist, um die Fehler zu erkennen und zu rekonstruieren, dann brauchen wir andere Varianten. -Um dieser Approximation zu entkommen, verlassen wir die reellen Zahlen und gehen zu endlichen Körpern, auch Galois-Körper genannt. +Um dieser Approximation zu entkommen verlassen wir die reellen Zahlen und gehen zu endlichen Körper, auch Galois-Körper genannt. \index{endlicher Körper}% \index{Galois-Körper}% \index{Körper, endlich}% diff --git a/buch/papers/reedsolomon/einleitung.tex b/buch/papers/reedsolomon/einleitung.tex index cf46c27..c70f595 100644 --- a/buch/papers/reedsolomon/einleitung.tex +++ b/buch/papers/reedsolomon/einleitung.tex @@ -10,9 +10,10 @@ Der Reed-Solomon-Code wurde von den beiden Mathematikern Irving S. Reed und Gust \index{Reed, Irving S.}% \index{Solomon, Gustave}% Dabei haben sie das Problem der fehlerhaften Datenübertragung gelöst. -In diesem Kapitel wird möglichst verständlich die mathematische Abfolge und -Funktionsweise des Reed-Solomon-Code erklärt. -Es wird jedoch nicht auf die technische Umsetzung oder Implementierung eingegangen, jedoch werden im Abschnitt \ref{reedsolomon:section:anwendung} einige Anwendungen des Reed-Solomon-Codes vorgestellt. +In diesem Kapitel wird die mathematische Abfolge und +Funktionsweise des Reed-Solomon-Code möglichst verständlich erklärt. +Es wird jedoch nicht auf die technische Umsetzung oder Implementierung eingegangen. +In Abschnitt \ref{reedsolomon:section:anwendung} werden jedoch einige Anwendungen des Reed-Solomon-Codes vorgestellt. diff --git a/buch/papers/reedsolomon/endlichekoerper.tex b/buch/papers/reedsolomon/endlichekoerper.tex index 3019dd7..79c3c19 100644 --- a/buch/papers/reedsolomon/endlichekoerper.tex +++ b/buch/papers/reedsolomon/endlichekoerper.tex @@ -14,10 +14,10 @@ Zudem beschränken sich die arithmetischen Rechenoperationen auf das Addieren un Wir können also nur ganze Zahlen als Resultat erhalten. Dies erleichtert auch die Umsetzung auf ein digitales System, da Computer in der Regel lieber mit ganzen als mit gebrochenen oder komplexen Zahlen arbeiten. -Um jetzt eine Nachricht in einem endlichen Körpern zu konstruieren gehen, wir im Grunde gleich vor wie im Beispiel aus dem Abschnitt \ref{reedsolomon:subsection:sendbsp}. +Um jetzt eine Nachricht in einem endlichen Körper zu konstruieren, gehen wir im Grunde gleich vor wie im Beispiel aus dem Abschnitt \ref{reedsolomon:subsection:sendbsp}. Eine Nachricht besteht aus einem Nutzdatenteil und einem Fehlerkorrekturteil. Diese Nachricht wird codiert, übertragen und beim Empfänger wieder decodiert. -In endlichen Körpern können wir jedoch nicht mehr die Fouriertransformation zur Hilfe nehmen. +In endlichen Körpern können wir jedoch nicht mehr die Fouriertransformation zu Hilfe nehmen. Wir müssen also eine Alternative finden, welche die gleichen Eigenschaften wie die Fouriertransformation aufweist, aber im endlichen Körper verwendet werden kann. Auch beim Decodieren müssen wir uns etwas einfallen lassen, wenn die Vorgehensweise mit dem Lokator auch in endlichen Körpern funktionieren soll. Die folgenden Abschnitte widmen sich deshalb der genaueren Betrachtung eines Reed-Solomon-Codes und wie er in endlichen Körpern funktioniert. diff --git a/buch/papers/reedsolomon/hilfstabellen.tex b/buch/papers/reedsolomon/hilfstabellen.tex index 24fabdf..2c8585f 100644 --- a/buch/papers/reedsolomon/hilfstabellen.tex +++ b/buch/papers/reedsolomon/hilfstabellen.tex @@ -7,7 +7,7 @@ \label{reedsolomon:section:hilfstabellen}} \rhead{Hilfstabellen} -Um das rechnen zu erleichtern findet man in diesem Abschnitt die Resultate, die bei der Addition und der Multiplikation in $\mathbb{F}_{11}$ resultieren. +Um das Rechnen zu erleichtern findet man in diesem Abschnitt die Resultate, die bei der Addition und der Multiplikation in $\mathbb{F}_{11}$ resultieren. \subsection{Additionstabelle \label{reedsolomon:subsection:adtab}} diff --git a/buch/papers/reedsolomon/idee.tex b/buch/papers/reedsolomon/idee.tex index b1ab8f6..df8c30d 100644 --- a/buch/papers/reedsolomon/idee.tex +++ b/buch/papers/reedsolomon/idee.tex @@ -5,14 +5,14 @@ \label{reedsolomon:section:idee}} \rhead{Problemstellung} Um Fehler in einer Datenübertragung zu erkennen, könnte man die Daten jeweils doppelt senden, -also den gleiche Wert immer zweimal. -Tritt ein Fehler ein wird sich dies in der Differenz der beiden Werte bemerkbar machen. +also den gleichen Wert immer zweimal. +Tritt ein Fehler ein, wird sich dies in der Differenz der beiden Werte bemerkbar machen. Aber wie erkennen wir, welcher nun der richtige ist? Die Lösung ist simpel: Wir übertragen den Wert einfach dreimal. Wenn jetzt ein Fehler auftritt, kann durch die beiden unveränderten Werte der richtige bestimmt werden. Doch was machen wir, wenn bei dieser Übertragung zwei Fehler auftreten? -Oder noch schlimmer: Was wenn zweimal derselbe Fehler auftritt? Die beiden fehlerhaften Werte überstimmen bei der Evaluierung den gesendeten Datenwert, der dann unwiderruflich verloren geht. +Oder noch schlimmer: Was ist, wenn zweimal derselbe Fehler auftritt? Die beiden fehlerhaften Werte überstimmen bei der Evaluierung den gesendeten Datenwert, der dann unwiderruflich verloren geht. Wir könnten dies noch steigern mit vier, fünf oder mehr gleichen übertragenen Werte. Dies erhöht zwar die Robustheit der gesendeten Daten, führt aber auch dazu, dass wir durch die Mehrfachübertragung nur sehr wenige Nutzdaten versenden können. -Gerade in unserer heutigen Zeit wäre dies ein enorm grosses Problem und aus diesem Grund wurden alternative Ansätze ausgearbeitet um dieses grundlegende Problem zu lösen. +Gerade in der heutigen Zeit wäre dies ein enorm grosses Problem und aus diesem Grund wurden alternative Ansätze ausgearbeitet, um dieses grundlegende Problem zu lösen. % % %Gerade in der heutigen modernen Zeit bei dem hohen bedarf an Daten würden unsere Kommunikationssysteme bei weitem nicht ausreichen um den einen einzigen Datenwert mehrfach zu übertragen @@ -60,7 +60,7 @@ Gerade in unserer heutigen Zeit wäre dies ein enorm grosses Problem und aus die \subsection{Polynom-Ansatz \label{reedsolomon:section:polynomansatz}} \rhead{Polynom-Ansatz} -Eine zentrale Idee des Reed-Solomon-Code ist, aus den Daten ein Polynom zu bilden. +Eine zentrale Idee des Reed-Solomon-Codes ist, aus den Daten ein Polynom zu bilden. Mit dieser Polynomfunktion wird dann eine Anzahl von Werten übertragen. \begin{beispiel} Nehmen wir die Zahlen \textcolor{blue}{2}, \textcolor{blue}{1} und \textcolor{blue}{5}, welche übertragen werden sollen. Daraus bilden wir das Polynom \begin{equation} @@ -71,17 +71,17 @@ p(x) \end{equation} Ein Polynom zweiten Grades ist durch drei Punkte eindeutig bestimmbar. -Bei einer fehlerlosen Übertragung können wir mit drei übertragenen Werten - das Polynom durch Polynominterpolation volständig rekonstruieren. +Bei einer fehlerlosen Übertragung können wir mit drei übertragenen Werte +das Polynom durch Polynominterpolation vollständig rekonstruieren. Wir brauchen Polynominterpolation als Methode, um aus den Punkten wieder ein Polynom zu bilden. -Die Koeffizente des rekonstruierten Polynoms sind dann unsere gesendeten Zahlen \textcolor{blue}{2}, \textcolor{blue}{1} und \textcolor{blue}{5}. +Die Koeffizienten des rekonstruierten Polynoms sind dann unsere gesendeten Zahlen \textcolor{blue}{2}, \textcolor{blue}{1} und \textcolor{blue}{5}. Wie können wir nun Fehler erkennen oder sogar korrigieren? Versuchen wir doch, mehr Werte zu übertragen, wie zum Beispiel sieben Werte. Übertragen werden nun die \textcolor{darkgreen}{grünen Werte} - des \textcolor{blue}{blauen Polynomes} an den Stellen 1, 2, 3, \dots , 7. -In Abbildung \ref{fig:polynom} ist das zu den \textcolor{blue}{Datenpunkten} gehörige Polynom blau dargestellt, -die \textcolor{darkgreen}{übertragenen Werte} des Polynoms sind grün, wobei diese Punkte aufgrund von Übertragungsfehler jetzt eine Parabel darstellen. + des \textcolor{blue}{blauen Polynoms} an den Stellen 1, 2, 3, \dots , 7. +In Abbildung \ref{fig:polynom} ist das zu den \textcolor{blue}{Datenpunkten} gehörende Polynom blau dargestellt, +die \textcolor{darkgreen}{übertragenen Werte} des Polynoms sind grün, wobei diese Punkte aufgrund von Übertragungsfehlern jetzt eine Parabel darstellen. Die fehlerhaften Punkte lassen sich sehr einfach bestimmen, weil diese nicht auf der ursprünglichen Funktion liegen. Somit können die roten Punkte auf der Parabel durch die grauen ersetzt werden und sind damit korrigiert. @@ -97,14 +97,14 @@ Wir erhöhen dazu die Fehleranzahl Schritt für Schritt: \begin{itemize} \item[\textit{1 Fehler}:] Bei einem Fehler können konkurrenzierende, aber falsche Polynome zusammen mit zwei originalen Punkten entstehen. Dabei können aber maximal drei Punkte auf diesem Konkurrenzpolynom sein. - Da 6 > 3 ist haben wir unser originales Polynom gefunden. - \item[\textit{2 Fehler}:] Bei Zwei Fehlern kann ein Fehler mit zwei originalen Punkten ein konkurrenzierendes, aber falsches Polynom bilden. - Da der zweite \textcolor{red}{Fehler} frei wählbar ist, kann dieser auch auf dem \textcolor{gray}{Konkurrenzpolynom} liegen, wie in der Abbilbung \ref{fig:polynom} zu sehen ist. - Nun haben wir, ein \textcolor{blue}{originales Polynom} mit \textcolor{darkgreen}{fünf} übereinstimmenden und ein konkurrenzierendes mit vier Punkten. + Da 6 > 3 ist, haben wir unser originales Polynom gefunden. + \item[\textit{2 Fehler}:] Bei zwei Fehlern kann ein Fehler mit zwei originalen Punkten ein konkurrenzierendes, aber falsches Polynom bilden. + Da der zweite \textcolor{red}{Fehler} frei wählbar ist, kann dieser auch auf dem \textcolor{gray}{Konkurrenzpolynom} liegen, wie in der Abbildung \ref{fig:polynom} zu sehen ist. + Nun haben wir ein \textcolor{blue}{originales Polynom} mit \textcolor{darkgreen}{fünf} übereinstimmenden und ein konkurrenzierendes mit vier Punkten. Da fünf noch grösser als vier ist, können wir sagen, welches das Originalpolynom ist. - \item[\textit{3 Fehler}:] Bei drei kann genau wie bei ein oder zwei Fehler, ein konkurenzierendes Polynom mit einem Fehler und zwei originalen Punkten bestimmt werden. + \item[\textit{3 Fehler}:] Bei drei kann genau wie bei ein oder zwei Fehlern ein konkurrenzierendes Polynom mit einem Fehler und zwei originalen Punkten bestimmt werden. Auch hier sind die anderen Fehler frei wählbar und liegen auf dem Konkurrenzpolynom. - Nun ist es so das fünf Punkte auf diesem konkurenzierenden Polynom und vier Punkte auf dem originalen liegen. + Nun ist es so, dass fünf Punkte auf diesem konkurrenzierenden Polynom und vier Punkte auf dem originalen liegen. Das Originalpolynom kann nicht mehr gefunden werden. \item[\textit{4 Fehler}:] Bei vier kann noch erkannt werden, dass Fehler aufgetreten sind, da drei originale Punkte das ursprüngliche Polynom ergeben. Somit haben wir mindestens zwei verschiedene Polynome, was bedeutet, dass Fehler entstanden sind. @@ -120,10 +120,10 @@ Um zu bestimmen, wie viele zusätzliche \textcolor{darkgreen}{Übertragungspunkt muss man zuerst wissen, wie viele \textcolor{blue}{Datenwerte} gesendet und wie viele \textcolor{red}{Fehler} erkannt werden sollen. Die Anzahl Datenwerte ergibt die Anzahl \textcolor{blue}{$k$} -Polynomkoeffizenten +Polynomkoeffizienten und somit den Grad $k-1$ des Polynoms. Die Bestimmung der Anzahl \textcolor{red}{$t$} der Fehler, welche korrigiert werden können, braucht Redundanz. -Bilden wir verschieden grosse Polynome und untersuchen diese mit unterschiedlich vielen Fehlern erkennt man allmählich ein Muster. +Bilden wir verschieden grosse Polynome und untersuchen diese mit unterschiedlich vielen Fehlern, erkennt man allmählich ein Muster. \begin{table}%[!ht] \centering @@ -138,11 +138,11 @@ Bilden wir verschieden grosse Polynome und untersuchen diese mit unterschiedlich $k$ & $t$ & $k+2t$ Werte eines Polynoms vom Grad $k-1$ \\ \hline \end{tabular} - \caption{ Fehlerkorrekturstellen Bestimmung.} + \caption{Bestimmung der Anzahl Übertragungspunkte in Abhängigkeit von den Fehlern.} \label{tab:fehlerkorrekturstellen} \end{table} \par -Es müssen mehr Punkte auf dem \textcolor{blue}{originalen Polynom} liegen, als auf dem konkurenzierenden. +Es müssen mehr Punkte auf dem \textcolor{blue}{originalen Polynom} liegen als auf dem konkurrenzierenden. Somit braucht man für die Übertragung pro \textcolor{red}{Fehler} zwei Übertragungspunkte mehr. Wie in der Tabelle \ref{tab:fehlerkorrekturstellen} ersichtlich ist ergibt sich die Anzahl @@ -154,7 +154,7 @@ Anzahl von \textcolor{darkgreen}{Punkten} für die Übertragung. Ein Nebeneffekt ist, dass auch $2t$ Fehler erkannt werden können, die aber nicht korrigiert werden können. -Um die Polynomkoeffizenten nach der Übertragung zu rekonstruieren, haben wir jedes mal die Polynominterpolationsmethode angewendet. +Um die Polynomkoeffizienten nach der Übertragung zu rekonstruieren, haben wir jedes mal die Polynominterpolationsmethode angewendet. Diese Polynominterpolation ist leider schwierig zu berechnen und sehr fehleranfällig. Es wäre daher einfacher, wenn wir eine alternative Vorgehensweise finden könnten. diff --git a/buch/papers/reedsolomon/rekonstruktion.tex b/buch/papers/reedsolomon/rekonstruktion.tex index e7bcc5c..b714225 100644 --- a/buch/papers/reedsolomon/rekonstruktion.tex +++ b/buch/papers/reedsolomon/rekonstruktion.tex @@ -16,8 +16,8 @@ markiert dabei diese fehlerhaften Stellen im Übertragungsvektor w = [5,3,6,8,2,10,2,7,1,4]. \] Als Ausgangslage verwenden wir die Matrix, mit der wir den Nachrichtenvektor ursprünglich codiert haben. -Unser Ziel ist es wie auch schon im Abschnitt \ref{reedsolomon:section:decohnefehler} eine Möglichkeit zu finden, wie wir den Übertragungsvektor decodieren können. -Aufgrund der Fehlerstellen müssen wir aber davon ausgehen, das wir nicht mehr den gleichen Weg verfolgen können wie wir im Abschnitt \ref{reedsolomon:section:decohnefehler} angewendet haben. +Unser Ziel ist es, wie auch schon im Abschnitt \ref{reedsolomon:section:decohnefehler}, eine Möglichkeit zu finden, wie wir den Übertragungsvektor decodieren können. +Aufgrund der Fehlerstellen müssen wir aber davon ausgehen, dass wir nicht mehr den gleichen Weg verfolgen können, wie wir ihn in Abschnitt \ref{reedsolomon:section:decohnefehler} angewandt haben. \rhead{Rekonstruktion der Nachricht} Wir stellen also die Matrix auf und markieren gleichzeitig die Fehlerstellen: @@ -49,9 +49,9 @@ 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 weiteren Nutzen. +Die rot markierten Stellen im Übertragungsvektor enthalten Fehler und bringen 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. +Die dazugehörenden Zeilen in der Matrix werden ebenfalls entfernt, da die Matrix gleich viele Zeilen wie im Übertragungsvektor aufweisen muss, damit man ihn decodieren kann. Daraus resultiert \[ @@ -76,8 +76,8 @@ 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. +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, dass die Nachricht aus Nutzdatenteil und Fehlerkorrekturteil besteht, wobei das letztere bekanntlich aus lauter Nullstellen besteht. Wir nehmen die markierten Spalten in \[ \begin{pmatrix} @@ -99,7 +99,7 @@ Wir nehmen die markierten Spalten in 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} \] -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} \\ @@ -141,7 +141,7 @@ Die roten Zeilen können wir aufgrund der Überbestimmtheit ebenfalls entfernen \end{pmatrix} . \] -Nun können wir den Gauss-Algorithmus anwenden um die Matrix zu Invertieren. +Nun können wir den Gauss-Algorithmus anwenden, um die Matrix zu invertieren. \[ \begin{pmatrix} 5 \\ 3 \\ 6 \\ 2 \\ 10 \\ 2 \\ @@ -183,7 +183,7 @@ Multiplizieren wir nun aus, erhalten wir unseren Nutzdatenteil \[ m = [4,7,2,5,8,1] \] -zurück, den wir ursprünglich versendet haben. +zurück, den wir ursprünglich versandt haben. Wir möchten noch anmerken, dass es mehrere Wege für die Rekonstruktion des Nutzdatenteils gibt, diese aber alle auf dem Lokatorpolynom basieren. diff --git a/buch/papers/reedsolomon/zusammenfassung.tex b/buch/papers/reedsolomon/zusammenfassung.tex index 400262d..ff3f35f 100644 --- a/buch/papers/reedsolomon/zusammenfassung.tex +++ b/buch/papers/reedsolomon/zusammenfassung.tex @@ -9,7 +9,7 @@ \index{Zusammenfassung Reed-Solomon-Code}% Dieser Abschnitt beinhaltet eine Übersicht über die Funktionsweise eines Reed-Solomon-Codes für beliebige endliche Körper. -\subsubsection{Schritt 1: primitives Element} +\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. diff --git a/buch/papers/spannung/teil0.tex b/buch/papers/spannung/teil0.tex index 17e1d21..f708055 100644 --- a/buch/papers/spannung/teil0.tex +++ b/buch/papers/spannung/teil0.tex @@ -72,7 +72,8 @@ Es ist praktisch, die relative Dehnung $\varepsilon$ anzugeben und nicht eine ab \caption{1D Spannungszustand aus einer quaderförmigen Bodenprobe} \label{fig:Bild1} \end{figure} -Mithilfe vom Elastizitätsmodul $E$ als Proportionalitätskonstante lässt sich der eindimensionale Fall mit +Mithilfe vom Elastizitätsmodul $E$ (auch Youngscher Modul) als Proportionalitätskonstante lässt sich der eindimensionale Fall mit +\index{Youngscher Modul} \[ \sigma = diff --git a/buch/papers/spannung/teil1.tex b/buch/papers/spannung/teil1.tex index 10f7663..552c1cf 100644 --- a/buch/papers/spannung/teil1.tex +++ b/buch/papers/spannung/teil1.tex @@ -1,23 +1,23 @@ \section{Skalare, Vektoren, Matrizen und Tensoren\label{spannung:section:Skalare,_Vektoren,_Matrizen_und_Tensoren}} \rhead{Skalare, Vektoren, Matrizen und Tensoren} -Der Begriff Tensor kann als Überbegriff der mathematischen Objekte Skalar, Vektor und Matrix, betrachtet werden. +Der Begriff Tensor kann als Überbegriff der mathematischen Objekte Skalar, Vektor und Matrix betrachtet werden. \index{Tensor}% Allerdings sind noch höhere Stufen dieser Objekte beinhaltet. Skalare, Vektoren oder Matrizen sind daher auch Tensoren. Ein Skalar ist ein Tensor 0. Stufe. \index{Stufe}% Mit einem Vektor können mehrere Skalare auf einmal beschrieben werden. -Ein Vektor hat daher die Stufe 1 und ist höherstufig als ein Skalar. +Ein Vektor hat daher die Stufe 1 und ist höherstufiger als ein Skalar. Mit einer Matrix können wiederum mehrere Vektoren auf einmal beschrieben werden. -Eine Matrix hat daher die Stufe 2 und ist noch höherstufig als ein Vektor. +Eine Matrix hat daher die Stufe 2 und ist noch höherstufiger als ein Vektor. Versteht man diese Stufen, so versteht man den Sinn des Begriffs Tensor. Jede Stufe von Tensoren verlangt andere Rechenregeln. So zeigt sich auch der Nachteil von Tensoren mit Stufen höher als 2. Man ist also bestrebt höherstufige Tensoren mit Skalaren, Vektoren oder Matrizen zu beschreiben. -In den 40er Jahren des 19.~Jahrhunderts wurde der Begriff Tensor von Rowan Hamilton in die Mathematik eingeführt. -\index{Hamilton, Rowan}% +In den 40er Jahren des 19.~Jahrhunderts wurde der Begriff Tensor von William Rowan Hamilton in die Mathematik eingeführt. +\index{Hamilton, William Rowan}% James Clerk Maxwell hat bereits mit Tensoren operiert, ohne den Begriff Tensor gekannt zu haben. \index{Maxwell, James Clerk}% Erst Woldemar Voigt hat den Begriff in die moderne Bedeutung von Skalar, Matrix und Vektor verallgemeinert. diff --git a/buch/papers/spannung/teil2.tex b/buch/papers/spannung/teil2.tex index ddd591f..fec0120 100644 --- a/buch/papers/spannung/teil2.tex +++ b/buch/papers/spannung/teil2.tex @@ -8,13 +8,13 @@ Durch komplexe Spannungsausbreitungen im Boden entstehen im 3D-Spannungszustand \label{fig:infinitesimalerWuerfel} \end{figure} Ein Tensor 0.~Stufe, sprich ein Skalar, kann lediglich den 1D-Spannungszustand beschreiben. -Um den 3D-Spannungszustandes als ein mathematisches Objekt darstellen zu können, wird ein Tensor 2.~Stufe, sprich eine Matrix, eingesetzt. +Um den 3D-Spannungszustand als ein mathematisches Objekt darstellen zu können, wird ein Tensor 2.~Stufe, sprich eine Matrix, eingesetzt. Die Spannungen sind durch die zwei Indizes \( i, j\in\left\{1, 2, 3\right\} \) definiert. -Daher ergeben sich die neun Spannungen. +Daher ergeben sich die $9$ Spannungen. Die nachfolgenden Zusammenhänge sind in \cite{spannung:Voigtsche-Notation} beschrieben. Dieser Spannungstensor kann schliesslich mit $3^2$ Einträgen als $3\times3$ Matrix mit \[ @@ -48,7 +48,7 @@ Der Dehnungstensor ist ebenfalls ein Tensor 2.~Stufe und kann somit auch als $3\ \] dargestellt werden und beschreibt den gesamten Dehnungszustand. -Der Spannungs- und Dehnungstensor 2.~Stufe kann je in einen Tensor 1.~Stufe überführt werden, welches ein Spaltenvektor ist. +Der Spannungs- und Dehnungstensor 2.~Stufe kann je in einen Tensor 1.~Stufe überführt werden, welcher ein Spaltenvektor ist. Man darf Zeile um Zeile in eine Spalte notieren, sodass es einen Spaltenvektor ergibt. So ergibt sich der Spannungsvektor @@ -114,8 +114,8 @@ Dieser ist im 1D-Spannungszustand ein Tensor 0.~Stufe und somit ein Skalar, der Dieser Elastizitätstensor 4.~Stufe kann als Tensor 2.~Stufe, sprich als Matrix, dargestellt werden. So wird die Spannungsgleichung stark vereinfacht, da nun eine Matrix auf einen Vektor operiert. -Dieser Tensor muss für eine Spannung jeden Einfluss aus allen neun Dehnungen mit Konstanten erfassen. -Dies bedeutet um eine von neun Spannungen berechnen zu können müssen alle neun Dehnung mit unterschiedlichen Faktoren summiert werden. +Dieser Tensor muss für eine Spannung jeden Einfluss aus allen $9$ Dehnungen mit Konstanten erfassen. +Dies bedeutet um eine von $9$ Spannungen berechnen zu können müssen alle $9$ Dehnung mit unterschiedlichen Faktoren summiert werden. Es ergeben sich $9^2$ Einträge, welches mit den vier Indizes \( i, j, k, l\in\left\{1, 2, 3\right\} @@ -354,14 +354,19 @@ beziehungsweise \sigma_{12} \end{pmatrix} = +%\left( +%\begin{array}{ccc|ccc} \begin{pmatrix} C_{1111} & C_{1122} & C_{1133} & C_{1123} & C_{1113} & C_{1112} \\ C_{2211} & C_{2222} & C_{2233} & C_{2223} & C_{2213} & C_{2212} \\ C_{3311} & C_{3322} & C_{3333} & C_{3323} & C_{3313} & C_{3312} \\ +%\hline C_{2311} & C_{2322} & C_{2333} & C_{2323} & C_{2313} & C_{2312} \\ C_{1311} & C_{1322} & C_{1333} & C_{1323} & C_{1313} & C_{1312} \\ C_{1211} & C_{1222} & C_{1233} & C_{1223} & C_{1213} & C_{1212} \end{pmatrix} +%\end{array} +%\right) \begin{pmatrix} \varepsilon_{11} \\ \varepsilon_{22} \\ @@ -417,14 +422,19 @@ Dies ergibt die Spannungsgleichung, welche weit möglichst vereinfacht ist: \end{pmatrix} = \frac{E}{(1+\nu)(1-2\nu)} -\begin{pmatrix} +\left( +\begin{array}{ccc|ccc} +%\begin{pmatrix} 1- 2\nu & \nu & \nu & 0 & 0 & 0\\ \nu & 1- 2\nu & \nu & 0 & 0 & 0\\ \nu & \nu & 1- 2\nu & 0 & 0 & 0\\ +\hline 0 & 0 & 0 & \frac{1}{2} & 0 & 0\\ 0 & 0 & 0 & 0 & \frac{1}{2} & 0\\ 0 & 0 & 0 & 0 & 0 & \frac{1}{2} -\end{pmatrix} +%\end{pmatrix} +\end{array} +\right) \begin{pmatrix} \varepsilon_{11}\\ \varepsilon_{22}\\ @@ -468,14 +478,19 @@ Durch einige Berechnungsschritte erhält man die Dehnungsgleichung: \end{pmatrix} = \frac{1}{E} -\begin{pmatrix} +\left( +\begin{array}{ccc|ccc} +%\begin{pmatrix} 1 & -\nu & -\nu & 0 & 0 & 0 \\ -\nu & 1 & -\nu & 0 & 0 & 0 \\ -\nu & -\nu & 1 & 0 & 0 & 0 \\ +\hline 0 & 0 & 0 & 2+2\nu & 0 & 0 \\ 0 & 0 & 0 & 0 & 2+2\nu & 0 \\ 0 & 0 & 0 & 0 & 0 & 2+2\nu -\end{pmatrix} +%\end{pmatrix} +\end{array} +\right) \begin{pmatrix} \sigma_{11}\\ \sigma_{22}\\ diff --git a/buch/papers/spannung/teil3.tex b/buch/papers/spannung/teil3.tex index c68c0d1..147fe01 100644 --- a/buch/papers/spannung/teil3.tex +++ b/buch/papers/spannung/teil3.tex @@ -13,7 +13,7 @@ Folglich gilt: \] Dadurch wird der Spannungszustand vereinfacht. Diesen vereinfachten Spannungszustand kann man mit den zwei geotechnischen Invarianten abbilden. -Die erste Invariante ist die volumetrische Spannung +Die erste Invariante ist die volumetrische oder auch hydrostatische Spannung \begin{equation} p = @@ -76,8 +76,8 @@ Die Faktoren mit den Dehnungskomponenten können so als \] eingeführt werden, mit \begin{align*} - \varepsilon_{v} &= \text{Hydrostatische Dehnung [-]} \\ - \varepsilon_{s} &= \text{Deviatorische Dehnung [-].} + \varepsilon_{v} &= \text{hydrostatische Dehnung [-]} \\ + \varepsilon_{s} &= \text{deviatorische Dehnung [-].} \end{align*} Die hydrostatische Dehnung $\varepsilon_{v}$ kann mit einer Kompression und die deviatorische Dehnung $\varepsilon_{s}$ mit einer Verzerrung verglichen werden. @@ -105,6 +105,7 @@ vereinfachen. Diese Spannungsgleichung mit den zwei Einträgen ($p$ und $q$) ist gleichwertig wie die ursprüngliche Spannungsgleichung mit den neun Einträgen ($\sigma_{11}$, $\sigma_{12}$, $\sigma_{13}$, $\sigma_{21}$, $\sigma_{22}$, $\sigma_{23}$, $\sigma_{31}$, $\sigma_{32}$, $\sigma_{33}$). -Mit dieser Formel \eqref{spannung:Matrixschreibweise} lassen sich verschieden Ergebnisse von Versuchen analysieren und berechnen. +Mit dieser Formel \eqref{spannung:Matrixschreibweise} lassen sich Ergebnisse von Versuchen analysieren und berechnen. Ein solcher Versuch, der oft in der Geotechnik durchgeführt wird, ist der Oedometer-Versuch. -Im nächsten Kapitel wird die Anwendung der Matrix an diesem Versuch beschrieben. +In Abschnitt~\ref{spannung:section:Oedometrischer Elastizitätsmodul} +wird die Anwendung der Matrix an diesem Versuch beschrieben. diff --git a/buch/papers/spannung/teil4.tex b/buch/papers/spannung/teil4.tex index 2e0de45..06d67c9 100644 --- a/buch/papers/spannung/teil4.tex +++ b/buch/papers/spannung/teil4.tex @@ -78,5 +78,5 @@ Mit diesen Gleichungen hat man das Gleichungssystem um $E_{\text{OED}}$ und $\si Die Poisson-Zahl muss als Kennwert gemäss der Bodenklasse gewählt werden. Den Versuch kann man auf einem $\sigma$-$\varepsilon$-Diagramm abtragen (siehe Abbildung~\ref{fig:DiagrammOedometer-Versuch}). Durch die Komprimierung nimmt der Boden mehr Spannung auf, und verformt sich zugleich weniger stark. -Mit diesem ermittelten $E_{\text{OED}}$ kann man nun weitere Berechnungen für die Geotechnik durchführen. +Mit diesem ermittelten $E_{\text{OED}}$ kann man nun weitere Berechnungen in der Geotechnik durchführen. diff --git a/buch/papers/uebersicht.tex b/buch/papers/uebersicht.tex index 64b8863..f095947 100644 --- a/buch/papers/uebersicht.tex +++ b/buch/papers/uebersicht.tex @@ -13,6 +13,8 @@ grundlegenden Modelle werden dabei verfeinert, verallgemeinert und auf vielfältige Weise angewandt. Den Anfang machen {\em Robine Luchsinger} und {\em Pascal Andreas Schmid}, +\index{Luchsinger, Robine}% +\index{Schmid, Pascal Andreas}% die zeigen, wie man basierend auf der Adjazenzmatrix Suchalgorithmen für Netzwerke aufbauen kann. Sie konzentrieren sich dabei auf Verkehrsnetze, die die zusätzliche @@ -23,6 +25,7 @@ Einfluss auf die Effizienz der Suchalgorithmen haben können. Die naive Umsetzung der Definition der Matrizenmultiplikation in ein Coputerprogramm ist nicht unbedingt die effizienteste. {\em Michael Schmid} stellt die Algorithmen von Strassen und +\index{Schmid, Michael}% Windograd vor, welche ermöglichen, die Laufzeitkomplexität von $O(n^3)$ auf $O(n^{2.8074})$ oder noch schneller zu verbessern. Allerdings nur unter gewissen Voraussetzungen, die im Paper @@ -31,6 +34,8 @@ ebenfalls diskutiert werden. Eine der schönsten Anwendungen der Gruppentheorie ist die Kristallographie. {\em Naoki Pross} und {\em Tim Tönz} zeigen, wie man mit ihrer +\index{Pross, Naoki}% +\index{Tönz, Tim}% Hilfe Kristalle klassifizieren kann, und sie illustrieren am Beispiel der Piezoelektrizität, dass man auch physikalische Eigenschaften daraus ableiten kann. @@ -42,6 +47,8 @@ und DVDs, begegnet er uns heute auch in den allgegenwärtigen QR-Codes. Ein ganzes Arsenal von algebraischen Methoden ist nötig, um seine Funktionsweise zu verstehen. {\em Joshua Bär} und {\em Michael Steiner} zeigen in vielen Einzelschritten, +\index{Bär, Joshua}% +\index{Steiner, Michael}% wie die man die einzelnen Ideen an vertrauteren Beispielen aus der elementaren Algebra und der Fourier-Theorie verstehen kann. Die Übertragung in einen Polynomring über einem endlichen Körper @@ -52,6 +59,7 @@ die diskrete Fourier-Transformation beide als Matrizen schreibt. Wer glaubt, mit linearen Abbildungen lassen sich nur gradlinige Objekte beschreiben, liegt völlig falsch. Die Arbeit von {\em Alain Keller} zeigt, dass die Iteration von +\index{Keller, Alain}% affinen Abbildungen hochkomplexe Fraktale hervorbringen kann. Solche iterierten Funktionsschemata erzeugen aber nicht nur schöne Bilder, man kann daraus auch eine Idee zur Kompression von @@ -64,6 +72,7 @@ brechen könnte. Das McEliece-Kryptosystem kombiniert verschiedene Arten von Matrizen mit zufälligem Rauschen und einem fehlerkorrigierenden Code. Wie {\em Reto Fritsche} erklärt, kommt dabei ein Verschlüsselungsverfahren +\index{Fritsche, Reto}% heraus, welches nach heutigem Wissensstand gegen Angriffe mit Quantencomputern resistent ist. @@ -75,6 +84,8 @@ In der Ebene kann man die komplexen Zahlen als Modell verwenden, wo Drehungen und Translationen durch einfache arithmetische Operationen mit Zahlen beschrieben werden können. {\em Marius Baumann} und {\em Thierry Schwaller} tauchen in die +\index{Baumann, Marius}% +\index{Schwaller, Thierry}% geometrische Algebra ein, welche diese Idee verallgemeinert. Sie illustrieren, wie sich mit geometrischer Algebra Bewegungen in $\mathbb{R}^n$ einfach beschreiben lassen. @@ -91,6 +102,8 @@ der von einem Gebäude im darunterliegenden Boden aufgebaut wird, im Detail verstehen und modellieren können sollte. Dazu muss man erst eine geeignete Darstellung finden. {\em Thomas Reichlin} und {\em Adrian Schuler} zeigen, wie man +\index{Reichlin, Thomas}% +\index{Schuler, Adrian}% dazu eigentlich über die Welt der Matrizen hinaus gehen muss und sich mit sogenannten Tensoren herumschlagen muss. Dank sinnvollen Annahmen über die reale Situation im Boden @@ -107,6 +120,8 @@ aufzeichen kann. Doch welcher Teil der aufgezeichneten Bewegung kommt vom Erdbeben und welcher Teil ist Eigenschwingung der Messmasse? Dieser Frage gehen {\em Fabio Viecelli} und {\em Lukas Zogg} nach. +\index{Viecelli, Fabio}% +\index{Zogg, Lukas}% Die Antwort gelingt mit einem Klassiker unter den Ingenieur-Methoden: dem Kalman-Filter. Die Autoren stellen die für den Filter nötigen Matrizen zusammen @@ -119,6 +134,7 @@ Doch wie findet man jetzt diejenige Zuteilung der Aufgaben zu den Anbietern, die die Gesamtkosten minimiert. Für dieses klassische Zuordnungsproblem ist die von {\em Marc Kühne} beschriebene ungarische Methode, +\index{Kühne, Marc}% auch als Munkres-Algorithmus bekannt, eine besonders effiziente Lösung. diff --git a/buch/papers/verkehr/section1.tex b/buch/papers/verkehr/section1.tex index 1b4a328..cc5893d 100644 --- a/buch/papers/verkehr/section1.tex +++ b/buch/papers/verkehr/section1.tex @@ -8,7 +8,7 @@ Das Verkehrsnetz besteht aus allen Anlagen, auf oder unter der Erdoberfläche, a 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. \index{Knotenpunkt}% \index{Hinterland}% -\index{Verkehrtsstrom}% +\index{Verkehrsstrom}% 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. \index{Graphentheorie}% Ziel ist aber ein möglichst wirtschaftliches und optimales Verkehrsnetz. |