diff options
Diffstat (limited to 'buch/papers')
29 files changed, 441 insertions, 222 deletions
diff --git a/buch/papers/erdbeben/Teil_Fabio.tex b/buch/papers/erdbeben/Teil_Fabio.tex index afb2110..2ab6052 100644 --- a/buch/papers/erdbeben/Teil_Fabio.tex +++ b/buch/papers/erdbeben/Teil_Fabio.tex @@ -1,73 +1,51 @@ \section{Anwendung des Kalman-Filters} \subsection{Ziel} Bis jetzt haben wir gelesen, was das Kalman-Filter bewirkt und wie es funktioniert. -Nun möchten wir mit einem Beispiel herausfinden, ob das Filter unsere gesuchte Grösse $f(t)$ bestimmen kann. +Nun möchten wir mit einem Beispiel herausfinden, +ob das Filter unsere gesuchte Grösse $f(t)$ bestimmen kann. \subsection{Künstliche Erdbebendaten} -Da wir keine Rohdaten über vergangene Erdbeben zur Hand haben, müssen wir mittels Matlab künstliche Daten erzeugen und sie dann in das Filter eingeben. +Da wir keine Rohdaten über vergangene Erdbeben zur Hand haben, müssen wir mittels Matlab künstliche Daten erzeugen und sie dann in das Filter eingeben. Diese Vorgehensweise erlaubt uns das Erdbeben beliebig zu gestalten -und weil es digital simuliert wird, haben wir keine Bauschäden zu beklagen. +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) + 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 -\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,34 +68,37 @@ 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. - -\subsection*{Ergebnis} +Sind nun die benötigten Systemparameter und Varianzen definiert, +erzeugen wir ein Erdbeben mittels Simulation und schauen, +wie gut das Kalman-Filter die äussere Beschleunigung schätzen kann. -Wie wir in Abbildung~\ref{erdbeben:fig:standard-alles} im Positions-Zeit-Diagramm sehen, erzeugen unsere vorher gewählten Parameter eine realistische Erdbebenaufzeichnung. -Leiten wir die Position einmal ab, erhalten wir die Geschwindigkeit. -Die zweite Ableitung ergibt uns die Kraft, die in unserer Aufgabenstellung gesucht ist. +\subsubsection{Ergebnis} -Zoomen wir näher ran, erkennen wir in der Abbildung~\ref{erdbeben:fig:standard-zoom} im Positions-Diagramm eine Überlagerung der Massen-Eigenschwingung mit der Erdbebenschwingung. -Die Masse schwingt mit einer tiefer Frequenz und hoher Amplitude, hingegen das Erdbeben mit einer hohen Frequenz und tiefer Amplitude. +Abbildung~\ref{erdbeben:fig:standard-alles} zeigt zuoberst unsere Messwerte, +also die Position der Masse relativ zum Seismografen. +Wir sehen, dass unsere vorher gewählten Parameter eine realistische Erdbebenaufzeichnung erzeugen. +Leiten wir die Position einmal ab, erhalten wir die Geschwindigkeit, +und die zweite Ableitung ergibt uns die Kraft, welche für unsere Aufgabenstellung relevant ist. +Sehr gut ersichtlich ist die typische Hüllkurve, wie wir sie bei einer gedämpften Schwingung erwarten. -Vergleichen wir nun die Position mit der Kraft, stellen wir fest, dass das Kalman-Filter eine Schätzung wiedergibt, die auch eine Frequenz von \SI{15}{\hertz} hat. -Das Filter war imstande die Eigenfrequenz zu eliminieren und die tatsächliche Kraft des Erdbebens zu wiedergeben. +Die blaue Kurve ist die geschätzte äussere Kraft des Kalman-Filters. +Erst wenn wir näher zoomen, erkennen wir in Abbildung~\ref{erdbeben:fig:standard-zoom}, +wie nahe die Schätzung an der idealen Schwingung liegt. \begin{figure} \begin{center} \includegraphics[width=\linewidth,keepaspectratio]{papers/erdbeben/Standard_alles.PNG} - \caption{Das Position-Zeit-Diagramm zeigt uns die typische Aufzeichnung eines Seismographen während eines Erdbebens. Um die Geschwindigkeit zu erhalten müssen wir die Position einmal ableiten. Ein weiteres Ableiten erzeugt uns die Beschleunigung, respektive die Kraft. Sehr gut ersichtlich ist die Hüllkurve der Amplitude, wie wir sie bei einer gedämpften Schwingung erwarten.} + \caption{Das Position-Zeit-Diagramm zeigt uns die typische Aufzeichnung eines Seismographen während eines Erdbebens. Um die Geschwindigkeit zu erhalten müssen wir die Position einmal ableiten. Ein weiteres Ableiten erzeugt uns die Beschleunigung, respektive die Kraft.} \label{erdbeben:fig:standard-alles} \end{center} \end{figure} @@ -131,21 +112,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 +166,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} @@ -207,8 +192,6 @@ Der Seismograph war fähig die Position der Masse während der Einwirkung des Er $a(t)$ kann zwar nicht mit Sensoren gemessen werden, jedoch erhalten wir $a(t)$ durch zweifaches Ableiten. Da wir so aber die innere Beschleunigung erhalten, mussten wir das Kalman-Filter anwenden. Das Kalman-Filter half uns die äussere Beschleunigung zu schätzen und lieferte erstaunlich genaue Werte. -Ausserdem hat es das Filter geschafft, die Eigenfrequenz der Masse und die Erdbebenfrequenz zu separieren. -Folglich erhielten wir eine Schätzung, die nur das Erdbeben betraf. -Zuletzt haben wir aufgezeigt, das Veränderungen an den System- und Rauschparametern die Genauigkeit und Zuverlässigkeit des Kalman-Filters beeinträchtigen können. +Schlussendlich haben wir aufgezeigt, das Veränderungen an den System- und Rauschparametern die Genauigkeit und Zuverlässigkeit des Kalman-Filters beeinträchtigen. 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/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. |