diff options
Diffstat (limited to 'buch/papers')
59 files changed, 758 insertions, 404 deletions
diff --git a/buch/papers/clifford/0_ElevatorPitch.tex b/buch/papers/clifford/0_ElevatorPitch.tex index a68ac8f..3d04737 100644 --- a/buch/papers/clifford/0_ElevatorPitch.tex +++ b/buch/papers/clifford/0_ElevatorPitch.tex @@ -1,12 +1,12 @@ -Der Nutzen, welche die Clifford Algebra hat, lässt sich am besten mit den Worten des modernen Begründers derselben erläutern. -\index{Clifford Algebra}% +Der Nutzen, welche die geometrische Algebra hat, lässt sich am besten mit den Worten des modernen +Begründers derselben erläutern. \index{geometrische Algebra}% \begin{quote} -GA [Geometric Algebra i.~a.~W.~Clifford Algebra] +GA [Geometric Algebra] provides a unified language for the whole of physics and for much of mathematics and its applications that is conceptually and computationally superior to alternative mathematical systems in many application domains. \cite{clifford:hestenes_GA} \end{quote} -Im folgenden hoffen wir den Leser von der Nützlichkeit und der geometrischen Schönheit der Clifford Algebra zu überzeugen. +Im folgenden hoffen wir den Leser von der Nützlichkeit und der geometrischen Schönheit der geometrischen Algebra zu überzeugen. diff --git a/buch/papers/clifford/2_QuadratVektoren.tex b/buch/papers/clifford/2_QuadratVektoren.tex index 8916e15..d54b068 100644 --- a/buch/papers/clifford/2_QuadratVektoren.tex +++ b/buch/papers/clifford/2_QuadratVektoren.tex @@ -4,7 +4,7 @@ Was eine Addition von Vektoren bedeutet ist sehr intuitiv und auch leicht geometrisch darzustellen wie in Abbildung \ref{figure:addition}. Was allerdings das Produkt von Vektoren ergibt, mag anfänglich unintuitiv wirken. \begin{figure}[tb] \centering - \begin{tikzpicture} + \begin{tikzpicture}[>=latex] \draw[thin,gray!40] (0,0) grid (4,4); \draw[blue,thick,->] (0,0)--(3.5,2) node[midway,above,sloped] {$\textbf{a}$}; \draw[red,thick,->] (3.5,2)--(1.5,3.8) node[midway,above,sloped] {$\textbf{b}$}; diff --git a/buch/papers/clifford/6_PauliMatrizen.tex b/buch/papers/clifford/6_PauliMatrizen.tex index 70d28ad..c89ad02 100644 --- a/buch/papers/clifford/6_PauliMatrizen.tex +++ b/buch/papers/clifford/6_PauliMatrizen.tex @@ -4,10 +4,10 @@ % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil % \section{Pauli-Matrizen} -\rhead{Pauli-Matrizen} \index{Pauli-Matrizen}% -Was ist der beste Weg um einen Computeralgorithmus für die Rechenoperationen in der Clifford-Algebra zu erstellen? Man könnte versuchen einen textuellen Rechner zu implementieren der für die Elemente $\mathbf{e}_i$ hartkodierte Vereinfachungen ausführt. +Was ist der beste Weg um einen Computeralgorithmus für die Rechenoperationen in der Clifford-Algebra zu erstellen? +Man könnte versuchen, einen textuellen Rechner zu implementieren, der für die Elemente $\mathbf{e}_i$ hartkodierte Vereinfachungen ausführt. \begin{beispiel} Der Algorithmus weiss, dass er $a\mathbf{e}_1\cdot b\mathbf{e}_1$ zu $ab\cdot1$ vereinfachen kann. Dies ermöglicht zum Beispiel die Vereinfachung \begin{equation*} @@ -15,6 +15,7 @@ Was ist der beste Weg um einen Computeralgorithmus für die Rechenoperationen in \qedhere \end{equation*} \end{beispiel} +\rhead{Pauli-Matrizen} Ein textueller Algorithmus ist aber sehr ineffizient. Die Pauli-Matrizen bilden eine elegante und schnellere Alternative, welche für die dreidimensionale Clifford-Algebra verwendet werden können und alle Operationen aus der Clifford-Algebra gleich wie die Matrixoperationen ausführen lassen. \begin{definition} \label{def:defPauli} diff --git a/buch/papers/clifford/7_Reflektion.tex b/buch/papers/clifford/7_Reflektion.tex index 549848c..d4f2c6f 100644 --- a/buch/papers/clifford/7_Reflektion.tex +++ b/buch/papers/clifford/7_Reflektion.tex @@ -9,7 +9,7 @@ Die Spiegelung ist eine grundlegende, geometrische Operation, aus welcher man weitere Operationen, wie beispielsweise die später beschriebene Rotation, ableiten kann. Da die geometrische Algebra für geometrische Anwendungen ausgelegt ist, sollte die Spiegelung auch eine einfache, praktische Formulierung besitzen. \begin{figure} \centering - \begin{tikzpicture} + \begin{tikzpicture}[>=latex] \draw[thin,gray!40] (-3,-1) grid (3,3); \draw[<->] (-3,0)--(3,0) node[right]{$a_1$}; \draw[<->] (0,-1)--(0,3) node[above]{$a_2$}; @@ -92,4 +92,4 @@ Verwendet man für $\mathbf{u}$ nur einen Einheitsvektor $\mathbf{\hat{u}}$, wel \begin{align} \mathbf{v'} = -\mathbf{\hat{u}v\hat{u}} \end{align} -vereinfacht. Im Gegensatz zu den Abbildungen in der linearen Algebra, welche in jeder anderen Dimension, durch andere Matrizen \eqref{Spiegelmatrizen} beschrieben werden müssen, ist es in der geometrischen Algebra immer der gleiche Vorgehensweise. Zudem ist diese kompakte Schreibweise in der linearen Algebra nicht möglich, da bis auf das Vektorprodukt in der dritten Dimension keine Multiplikation von Vektoren definiert ist.
\ No newline at end of file +vereinfacht. Im Gegensatz zu den Abbildungen in der linearen Algebra, welche in jeder anderen Dimension, durch andere Matrizen \eqref{Spiegelmatrizen} beschrieben werden müssen, ist es in der geometrischen Algebra immer der gleiche Vorgehensweise. Zudem ist diese kompakte Schreibweise in der linearen Algebra nicht möglich, da bis auf das Vektorprodukt in der dritten Dimension keine Multiplikation von Vektoren definiert ist. diff --git a/buch/papers/erdbeben/Erdbeben_Standardfall.PNG b/buch/papers/erdbeben/Erdbeben_Standardfall.PNG Binary files differnew file mode 100644 index 0000000..6aed433 --- /dev/null +++ b/buch/papers/erdbeben/Erdbeben_Standardfall.PNG diff --git a/buch/papers/erdbeben/Erdbeben_Standardfall_Zoom.PNG b/buch/papers/erdbeben/Erdbeben_Standardfall_Zoom.PNG Binary files differnew file mode 100644 index 0000000..e3a6286 --- /dev/null +++ b/buch/papers/erdbeben/Erdbeben_Standardfall_Zoom.PNG diff --git a/buch/papers/erdbeben/Messrauschen_geaendert.PNG b/buch/papers/erdbeben/Messrauschen_geaendert.PNG Binary files differnew file mode 100644 index 0000000..f46354d --- /dev/null +++ b/buch/papers/erdbeben/Messrauschen_geaendert.PNG diff --git a/buch/papers/erdbeben/Messrauschen_geaendert_zoom.PNG b/buch/papers/erdbeben/Messrauschen_geaendert_zoom.PNG Binary files differnew file mode 100644 index 0000000..971ee82 --- /dev/null +++ b/buch/papers/erdbeben/Messrauschen_geaendert_zoom.PNG diff --git a/buch/papers/erdbeben/Prozessrauschen_geaendert.PNG b/buch/papers/erdbeben/Prozessrauschen_geaendert.PNG Binary files differnew file mode 100644 index 0000000..aff9ed8 --- /dev/null +++ b/buch/papers/erdbeben/Prozessrauschen_geaendert.PNG diff --git a/buch/papers/erdbeben/Prozessrauschen_geaendert_zoom.PNG b/buch/papers/erdbeben/Prozessrauschen_geaendert_zoom.PNG Binary files differnew file mode 100644 index 0000000..f2c1d3b --- /dev/null +++ b/buch/papers/erdbeben/Prozessrauschen_geaendert_zoom.PNG diff --git a/buch/papers/erdbeben/Standard_F-T.PNG b/buch/papers/erdbeben/Standard_F-T.PNG Binary files differnew file mode 100644 index 0000000..9da5f5e --- /dev/null +++ b/buch/papers/erdbeben/Standard_F-T.PNG diff --git a/buch/papers/erdbeben/Standard_V-T.PNG b/buch/papers/erdbeben/Standard_V-T.PNG Binary files differnew file mode 100644 index 0000000..b511ff4 --- /dev/null +++ b/buch/papers/erdbeben/Standard_V-T.PNG diff --git a/buch/papers/erdbeben/Standard_Zoom.PNG b/buch/papers/erdbeben/Standard_Zoom.PNG Binary files differnew file mode 100644 index 0000000..4f4e770 --- /dev/null +++ b/buch/papers/erdbeben/Standard_Zoom.PNG diff --git a/buch/papers/erdbeben/Standard_Zoom_leicht.PNG b/buch/papers/erdbeben/Standard_Zoom_leicht.PNG Binary files differnew file mode 100644 index 0000000..5885d77 --- /dev/null +++ b/buch/papers/erdbeben/Standard_Zoom_leicht.PNG diff --git a/buch/papers/erdbeben/Standard_alles.PNG b/buch/papers/erdbeben/Standard_alles.PNG Binary files differnew file mode 100644 index 0000000..a678df2 --- /dev/null +++ b/buch/papers/erdbeben/Standard_alles.PNG diff --git a/buch/papers/erdbeben/Systemparameter_geaendert.PNG b/buch/papers/erdbeben/Systemparameter_geaendert.PNG Binary files differnew file mode 100644 index 0000000..84249af --- /dev/null +++ b/buch/papers/erdbeben/Systemparameter_geaendert.PNG diff --git a/buch/papers/erdbeben/Systemparameter_geaendert_2.PNG b/buch/papers/erdbeben/Systemparameter_geaendert_2.PNG Binary files differnew file mode 100644 index 0000000..d4f530e --- /dev/null +++ b/buch/papers/erdbeben/Systemparameter_geaendert_2.PNG diff --git a/buch/papers/erdbeben/Teil_Fabio.tex b/buch/papers/erdbeben/Teil_Fabio.tex index 9f5d092..2ab6052 100644 --- a/buch/papers/erdbeben/Teil_Fabio.tex +++ b/buch/papers/erdbeben/Teil_Fabio.tex @@ -1,202 +1,197 @@ -\section{Kalman-Filter} -\subsection{Was ist ein Erdbeben?} -Für das Verständnis möchten wir zuerst erklären, was ein Erdbeben genau ist. -Das soll uns helfen, eine Verknüpfung zwischen dem Naturphänomen und der mathematischen Problemstellung herzustellen. - - -Unter einem Erdbeben verstehen wir eine Erschütterung des Erdkörpers. -Dabei reiben zwei tektonische Platten aneinander, welche sich durch die Gesteinsverzahnung gegenseitig blockieren. -Aufgrund dieser Haftreibung entstehen Spannungen, die sich immer mehr bis zum Tipping Point aufbauen. -Irgendwann ist der Punkt erreicht, in dem die Scherfestigkeit der Gesteine überwunden wird. -Wenn dies passiert, entlädt sich die aufgebaute Spannung und setzt enorme Energien frei, die wir als Erdbeben wahrnehmen. - -Ein Erdbeben breitet sich vom Erdbebenherd in allen Richtungen gleich aus. -Vergleichbar ist, wenn man einen Stein in einen Teich wirft und die Wellen beobachten kann, die sich ausbreiten. - -Wir möchten nun mittels Kalman-Filter die Erdbebenbeschleunigung herausfinden. -Die Erdbebenbeschleunigung ist in der Praxis zur Entwicklung von Erdbebengefährdungskarten, sowie der Ausarbeitung von Baunormen für erdbebengerechte Bauweise von Bedeutung. - +\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. \subsection{Künstliche Erdbebendaten} -Nun möchten wir anhand eines eigenen Beispiels das Kalman-Filter anwenden. -Da wir keine Rohdaten über vergangene Erdbeben zur Hand haben, müssen wir künstliche Daten erzeugen, um sie in das Filter einzugeben und somit den Prozess starten. -Dafür nehmen wir die Formel für harmonisch gedämpfte Schwingungen, die - +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. + +\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 \sin(\omega t e^{-lambda t}) -\end{equation} - -lautet. - -A ist die Amplitude der Schwingung und beschreibt die Heftigkeit eines Erdbebens, die Magnitude. -Omega repräsentiert die Erdbebenfrequenz, die in der Realität zwischen 1 Hz und 30 Hz beträgt. -Wir wählen als Erwartungswert 15 Herz und für die Standardabweichung 1 Hz. -Lambda ist die Bodendämpfung, für die wir 0.2 wählen. -Wir haben diese Zahl aus der Literatur entnommen, denn sie ist für das Bauwesen bedeutend. -Lambda ist ein Materialparameter von Böden. - -Je grösser Lambda gewählt wird, desto stärker wirkt die Dämpfung der Massenschwingung. -Die Funktion ist zeitabhängig und wir lassen pro Sekunde zehn Messwerte generieren. - -Die Frequenz basiert auf einer random-Funktion, da wir das Erdbeben unberechenbar gestalten möchten. -Mit dem Golay-Filter können wir hohe Frequenz-Anteile in die Berechnung mit einfliessen lassen, anstatt sie abzuschneiden. -Die Bildung eines üblichen Mittelwerts wäre hier weniger geeignet. - -\begin{lstlisting} -freq = sgolayfilt(randn(size(Time)),0,11)*freqstd... -+freqmean; -\end{lstlisting} - -Mit der Frequenz erhalten wir die Winkelbeschleunigung und damit können wir die Amplitude berechnen. - - -\begin{lstlisting} -w = 2 * pi * freq; -a = Amplitude*sin(cumsum(w.*[0;diff(Time)])).*exp(-lambda*Time); -\end{lstlisting} - -Mit der Matlab-Funktion ode45 haben wir eine Funktion gefunden, um die Differentialgleichung aufzulösen. ode45 basiert auf dem Runge-Kutta-Verfahren, einem Einschrittverfahren, bei dem die Lösung ausgehend von einem gegebenen Anfangswert, in einer Näherung gesucht wird. - -\begin{lstlisting} -[T,Y] = ode45(@(t,x)ErzeugteSchwingung(t,x,m,k,d,a,Time),[0 tend], IC, SolverOptions); -\end{lstlisting} - -Grafik einfügen - -In der Grafik erkennen wir in den Sekunden 0 bis 10, dass die Sinuskurve gezackt ist. -Das deutet darauf hin, dass die Frequenz des Erdbebens einen hohen Einfluss auf die Masse des Seismographen hat. -Ab der 10. Sekunde bis zu tend, pendelt sich die Masse in ihre Eigenfrequenz ein und verhält sich unabhängiger vom Erdbeben. - -\subsection{Versuch (bin noch dran)} - -Um den Kalman-Filter auszuprobieren, setzen wir nun Werte ein. -Für die Systemparameter wählen wir m=1.0, D = 0.3 und k = 0.1 und fügen es in die Differentialgleichung - + y = A e^{-\lambda t} \sin(\omega t). +\end{equation} +Dabei ist $A=5$ die anfängliche Amplitude der Schwingung, +die uns die Heftigkeit des Erdebebens beschreibt. +Sie ist vergleichbar mit der Magnitude. +$\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} - m\ddot x + 2k \dot x + Dx = f -\end{equation} + \omega = 2 \pi f +\end{equation} +gegeben, +wobei die Momentanfrequenz $f = \mathcal N(\mu_f, \sigma_f) $ einer Normalverteilung mit +\begin{equation} + \mu_f = \SI{15}{\hertz} + \qquad \text{und} \qquad + \sigma_f = \SI{10}{\hertz} +\end{equation} +folgt. + +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 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. +Eine kurze Recherche zeigt, dass die Masse ein Gewicht von ca.\ \SI{100}{\gram} hat. +Zur Federkonstante D und Dämpfung k konnten wir leider keine brauchbaren Grössen finden und treffen die Annahme, dass $D = 1$ und $k = 0.01$. +Für die Masse definieren wir $m = 0.01$. + +Da unser Seismograph von der Umgebung durch Wind, Temperatur oder menschgemachten Vibrationen beeinflusst wird, müssen wir ein Prozessrauschen definieren. +Die dazugehörige Matrix $Q$ beinhaltet die Standardabweichung für die Position, Geschwindigkeit und äussere Kraft. +Wir nehmen an, dass -ein und erhalten +\begin{equation} + Q = \left( + \begin{array}{ccc} + {\sigma_x }^2& 0& 0 \\ + 0 & {\sigma_v }^2& 0\\ + 0 & 0& {\sigma_f }^2\\ + \end{array}\right)= \left( + \begin{array}{ccc} + {0.00001}^2& 0& 0 \\ + 0 & {0.00001}^2& 0\\ + 0 & 0& {1 }^2\\ + \end{array}\right). +\end{equation} + +Auch für die Messung setzen wir ein Rauschen voraus und definieren \begin{equation} - 1\ddot x + 0.1 \dot x + 0.3x = f -\end{equation} - -\subsection{Matlab Code} - - -\begin{lstlisting} - %% Initialisierte Werte - t0 = 0.00; % Anfangszeit - deltat = 0.01; % Zeitschritt - tend = 50.00; % Endzeit -\end{lstlisting} -Ein natürliches Erdbeben dauert zwischen wenigen Sekunden bis etwa eine Minute an. -50 Sekunden genügen für unsere Daten. -Pro Sekunde erhalten wir 100 Messpunkte, die für den Prozess des Filters eine präzise Anwendung ermöglichen. - -\begin{lstlisting} - % Standard-Abweichungen Prozess - sigmax = 0.05e-3; % Position - sigmav = 0.01e-3; % Geschwindigkeit - sigmaf = 1; % (Äussere) Kraft - - % Standard-Abweichung Messung - sigmam = 0.01e-3; -\end{lstlisting} - -Wir vertrauen dem System und geben kleine Standardabweichungen für die Position, Geschwindigkeit und Kraft ein. -Bei der Messung erwarten wir auch, dass die Sensoren genau funktionieren. -Jedoch hängt das vom Hersteller ab oder muss statistisch ermittelt werden. - - -\begin{lstlisting} - % Systemparameter -m = 1.00; % Masse -D = 0.30; % Federkonstante -k = 0.10; % Dämpfung -\end{lstlisting} -Hier werden die Spezifikationen des Seismographen definiert. - -\begin{lstlisting} -%% Kalmanfilter -% Initialisierung - -% Anfangszustand (Position, Geschwindigkeit, Kraft) -x0 = [0; 0; 0]; - -% Unsicherheit des Anfangszustand -P0 = [0, 0, 0; ... -0, 0, 0; ... -0, 0, 0]; - -% Systemmatrizen -A = [0, 1, 0;... % Dynamikmatrix --D/m, -2*k/m, 1;... -0, 0, 0]; % Ableitungen von f(t) unbekant. Annahme: 0 -A = expm(A * deltat); - -Q = [sigmax^2, 0, 0;... -0, sigmav^2, 0;... -0, 0, sigmaf^2]; % Prozessrauschen (Covarianz) - - -\begin{lstlisting} -% Messprozess -H = [1, 0, 0]; % Messmatrix -R = sigmam^2; % Messrauschen (Könnte durch Versuche bestimmt werden) -\end{lstlisting} -Tritt ein Erdbeben ein, wird die Position der Masse in die Messmatrix eingetragen. - - -I = eye(3); % Identity matrix (Einheitsmatrix) - -\begin{lstlisting} -% Filterprozess - -% Initialisieren der Variablen -N = length(t); % Anzahl Punkte im Einheitsvektor (= Anzahl Messwerte) -xhat = zeros(3, N); % Matrix mit geschätzten Zuständen - -% Index ':' bedeutet: 'alles' -% Index '(1, :)' bedeutet: 'alles aus der 1. Zeile' - -% Anfangszustand setzen -xhat(:, 1) = x0; -P = P0; -\end{lstlisting} - -\begin{lstlisting} - -% Kalman-Matrizen konvergiert. Vorab-Berechnung in 'genügenden' Iterationen -for idx = 1:100 -Ppred = A * P * A' + Q; % Prädizieren der Kovarianz -S = (H * Ppred * H' + R); % Innovationskovarianz -K = Ppred * H' / S; % Filter-Matrix (Kalman-Gain) -P = (I - K * H) * Ppred; % Aktualisieren der Kovarianz -end -\end{lstlisting} - -In diesem Schritt wird die Kovarianz vorhergesagt, mit der Messung verglichen und nach jeder Berechnung aktualisiert. - -\begin{lstlisting} -% Anfangszustand gegeben -% Erster zu berechnender Wert ist der zweite -for idx = 2:N -% Vorhersage -xpred = A * xhat(:, idx-1); % Prädizierter Zustand aus Bisherigem und System -% Ppred = A * P * A' + Q; % Prädizieren der Kovarianz - -% Korrektur -y = xt(idx) - H * xpred; % Messungen/ Kraft aus System - Vohersage -% S = (H * Ppred * H' + R); % Innovationskovarianz -% K = Ppred * H' / S; - -xhat(:, idx) = xpred + K * y; % Aktualisieren des Systemzustands -% P = (I - K * H) * Ppred; % Aktualisieren der Kovarianz -end -\end{lstlisting} - -\subsection{Resultate} -Grafik einfügen -Wir erkennen, dass wir mit dem Kalman-Filter eine gute Methode gefunden haben, die äussere Beschleunigung zu schätzen. Die Schätzung der nächsten Position der Federmasse liegt immer ziemlich nahe der tatsächlichen Messung. Man muss aber auch berücksichtigen, dass die Federschwingung ziemlich kontrolliert verläuft und das Kalman-Filter somit präzise Vorhersagen treffen kann. +R= ({\sigma_x}^2)= +({0.00001}^2). +\end{equation} + +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. + +\subsubsection{Ergebnis} + +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. + +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.} + \label{erdbeben:fig:standard-alles} + \end{center} +\end{figure} + +\begin{figure} + \begin{center} + \includegraphics[width=\linewidth,keepaspectratio]{papers/erdbeben/Standard_Zoom.PNG} + \caption{Erst das Vergrössern an die Datenpunkte zeigt uns auf, wie gut die Schätzung des Kalman-Filters funktioniert.} + \label{erdbeben:fig:standard-zoom} + \end{center} +\end{figure} + +\subsection{Veränderung der Systemparameter} +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 +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 eine langsamere Bewegung der Masse, +das heisst die Frequenz wird kleiner. + +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} + \includegraphics[width=\linewidth,keepaspectratio]{papers/erdbeben/Systemparameter_geaendert_2.PNG} + \caption{Im Geschwindigkeits-Diagramm erkennen wir, dass sich im Vergleich zum Standardfall, die Auslenkung und Frequenz vergrössert hat. Dies wird mit der Erhöhung der Masse und somit der Trägheit begründet. Auch stellen wir fest, dass die Positionsmessung überwiegend die Eigenfrequenz misst.} + \label{erdbeben:fig:systemparameter-geaendert} + \end{center} +\end{figure} + + +\subsection{Verstärkung des Prozessrauschens} +Falls wir unseren Seismographen in der Nähe einer grösseren Stadt aufstellen, so müssen wir aufgrund der Vibrationen mit einem stärkeren Prozessrauschen rechnen. +Dieses Rauschen beeinflusst die Varianzen der Position und Geschwindigkeit in der Matrix $Q$. +Aus diesem Grund erhöhen wir die Standardabweichungen in der Matrix $Q$ um den Faktor $100$. +Die Auswertung in Abbildung~\ref{erdbeben:fig:prozessrauschen-geaendert} zeigt auf, dass das Kalman-Filter die Schätzung der Kraft nur gering an den Messwerten anpasst. + +\begin{figure} + \begin{center} + \includegraphics[width=\linewidth,keepaspectratio]{papers/erdbeben/Prozessrauschen_geaendert.PNG} + \caption{Mit dem Erhöhen des Prozessrauschens gehen wir von einer grösseren Unsicherheit der Systemmatrix aus. Aus diesem Grund folgt das Filter vor allem den Messwerten, was sichtbare Folgen für die Schätzkurve im Kraft-Zeit-Diagramm hat. Hier möchte das Filter auch den Messwerten folgen. Da wir aber für die Kraft keine Messwerte aufzeichnen, erhalten wir eine sehr schwache Kurve} + \label{erdbeben:fig:prozessrauschen-geaendert} + \end{center} +\end{figure} + +\begin{figure} + \begin{center} + \includegraphics[width=\linewidth,keepaspectratio]{papers/erdbeben/Prozessrauschen_geaendert_zoom.PNG} + \caption{Die Position kann immernoch präzise geschätzt werden und die Ableitung zur Geschwindigkeit ergibt gute Resultate. Jedoch ist die Schätzkurve der Kraft sehr weit von der idealen Kurve entfernt und nicht nutzbar.} + \label{erdbeben:fig:prozessrauschen-geaendert-zoom} + \end{center} +\end{figure} + +\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 eine ungenaues Resultat. + +\begin{figure} + \begin{center} + \includegraphics[width=\linewidth,keepaspectratio]{papers/erdbeben/Messrauschen_geaendert.PNG} + \caption{Im Kraft-Zeit-Diagramm erhalten wir nur bis ca. $t = 10$ gute Schätzwerte. Von $t = 10$ bis $t = 30$ wirkt das Messrauschen zu stark und erhalten keine brauchbaren Werte mehr} + \label{erdbeben:fig:messrauschen-geaendert} + \end{center} +\end{figure} + +\begin{figure} + \begin{center} + \includegraphics[width=\linewidth,keepaspectratio]{papers/erdbeben/Messrauschen_geaendert_zoom.PNG} + \caption{Im Position-Zeit-Diagramm erhielten wir bis jetzt immer genaue Schätzungen. Mit einem starken Messrauschen fällt es nun dem Filter schwerer, präzise Werte zu generieren. Die Nahaufnahme im Kraft-Zeit-Diagramm bestätigt uns aber, dass die Messfehler zu gross sind, um ein klares Bild über die äussere Kraft zu erhalten.} + \label{erdbeben:fig:messrauschen-geaendert_zoom} + \end{center} +\end{figure} + +\subsection{Zusammenfassung} +Wir haben uns zum Ziel gesetzt, die äussere Beschleunigung $a(t)$, bzw. die Kraft $f(t)$ eines Erdbebens zu ermitteln. + +Mit der Software Matlab haben wir einen virtuellen Seismographen gebaut und ein künstliches Erdbeben erzeugt. +Der Seismograph war fähig die Position der Masse während der Einwirkung des Erdbebens aufzuzeichnen. +$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. + +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/ifs/teil0.tex b/buch/papers/ifs/teil0.tex index 2a803d6..c37c704 100644 --- a/buch/papers/ifs/teil0.tex +++ b/buch/papers/ifs/teil0.tex @@ -4,7 +4,7 @@ % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil % \section{Einleitung \label{ifs:section:teil0}} -\rhead{Was ist ein Iteriertes Funktionsschema} +\rhead{Was ist ein Iteriertes Funktionsschema?} Mit der Hilfe von iterierten Funktionsschemata (IFS) können mit nur wenigen affinen Funktionen komplexe Bilder beschrieben werden. \index{iterierte Funktionsschemata}% \index{Funktionschemata, iterierte}% diff --git a/buch/papers/ifs/teil2.tex b/buch/papers/ifs/teil2.tex index 360a2c0..042d765 100644 --- a/buch/papers/ifs/teil2.tex +++ b/buch/papers/ifs/teil2.tex @@ -5,7 +5,7 @@ % \section{Fraktale mit IFS \label{ifs:section:teil2}} -\rhead{Teil 2} +\rhead{Fraktale mit iterierten Funktionensystemen} Wollen wir nun eine bestimmte Art anschauen, wie man Fraktale erzeugen kann. Im Beispiel auf Seite \pageref{ifs:trinagle} haben wir ein Dreieck aus 4 skalierten Kopien zusammengefügt. Lässt man die Kopie im Zentrum des Dreiecks weg, entsteht die Grundlage des sogenannten Sierpinski-Dreiecks in Abbildung \ref{ifs:sierpinski10}. diff --git a/buch/papers/mceliece/fazit.tex b/buch/papers/mceliece/fazit.tex index b53328f..3714d31 100644 --- a/buch/papers/mceliece/fazit.tex +++ b/buch/papers/mceliece/fazit.tex @@ -5,7 +5,6 @@ % \section{Fazit \label{mceliece:section:fazit}} -\rhead{Fazit} Ein kurzer Vergleich des McEliece-Systems mit dem oft verwendeten RSA-System soll zeigen, wo dessen Vor- und Nachteile liegen. @@ -16,6 +15,7 @@ wird Redundanz benötigt, weshalb dessen Kanalefizienz (Nutzbits/Übertragungsbits) sinkt. \index{Kanaleffizienz}% +\rhead{Fazit} Die Schlüsselgrösse des McEliece-Systems ist deshalb so riesig, weil es sich um eine zweidimensionale Matrix handelt, währenddem RSA mit nur zwei Skalaren auskommt. \index{Schlüsselgrösse}% Das McEliece-System benötigt dafür weniger Rechenaufwand beim Verschlüsseln/Entschlüsseln, diff --git a/buch/papers/mceliece/funktionsweise.tex b/buch/papers/mceliece/funktionsweise.tex index 4d6c18d..3802820 100644 --- a/buch/papers/mceliece/funktionsweise.tex +++ b/buch/papers/mceliece/funktionsweise.tex @@ -86,8 +86,8 @@ Die Verschlüsselung soll mittels eines numerischen Beispiels demonstriert werde Der verwendete Linear-Code wird im Abschnitt \ref{mceliece:subsection:seven_four} beschrieben. \begin{itemize} \item Daten- und Fehlervektor - \begin{itemize} - \item[] +% \begin{itemize} +% \item[] \[d_4= \begin{pmatrix} 1\\ @@ -107,11 +107,12 @@ Der verwendete Linear-Code wird im Abschnitt \ref{mceliece:subsection:seven_four 0 \end{pmatrix}. \] - \end{itemize} +% \end{itemize} \item Private Matrizen: - \begin{itemize} - \item[] - \[S_4= +\begin{gather*} +% \begin{itemize} +% \item[] + S_4= \begin{pmatrix} 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 1\\ @@ -125,9 +126,8 @@ Der verwendete Linear-Code wird im Abschnitt \ref{mceliece:subsection:seven_four 1 & 1 & 0 & 0\\ 0 & 1 & 0 & 0\\ \end{pmatrix}, - \] - \item[] - \[ + \\ +% \item[] G_{7,4}= \begin{pmatrix} 1 & 0 & 0 & 0\\ @@ -138,9 +138,8 @@ Der verwendete Linear-Code wird im Abschnitt \ref{mceliece:subsection:seven_four 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1 \end{pmatrix}, - \] - \item[] - \[ + \\ +% \item[] P_7= \begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0\\ @@ -162,13 +161,14 @@ Der verwendete Linear-Code wird im Abschnitt \ref{mceliece:subsection:seven_four 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}. - \] - \end{itemize} + \\ +% \end{itemize} +\end{gather*} \item Öffentlicher Schlüssel: \index{Schlüssel, öffentlicher}% -\index{öffentlicher Schlüssel}% - \begin{itemize} - \item[] +\index{offentlicher Schlüssel@öffentlicher Schlüssel}% +% \begin{itemize} +% \item[] \begin{align*} K_{7,4}&=P_{7}\cdot G_{7,4}\cdot S_{4}=\\ \begin{pmatrix} %k @@ -209,10 +209,10 @@ Der verwendete Linear-Code wird im Abschnitt \ref{mceliece:subsection:seven_four \end{pmatrix} . \end{align*} - \end{itemize} +% \end{itemize} \item Verschlüsselung: - \begin{itemize} - \item[] +% \begin{itemize} +% \item[] \begin{align*} c_7&=K_{7,4}\cdot d_4 + e_7=\\ \begin{pmatrix} %c @@ -253,10 +253,10 @@ Der verwendete Linear-Code wird im Abschnitt \ref{mceliece:subsection:seven_four \end{pmatrix} . \end{align*} - \end{itemize} +% \end{itemize} \item Entschlüsselung (Permutation rückgängig machen): - \begin{itemize} - \item[] +% \begin{itemize} +% \item[] \begin{align*} c_{7}''&=P_7^{-1}\cdot c_7=\\ \begin{pmatrix} %c'' @@ -290,10 +290,10 @@ Der verwendete Linear-Code wird im Abschnitt \ref{mceliece:subsection:seven_four \end{pmatrix} . \end{align*} - \end{itemize} +% \end{itemize} \item Entschlüsselung (Bitfehlerkorrektur mit Linearcode): - \begin{itemize} - \item[] +% \begin{itemize} +% \item[] \begin{align*} c_{7}'&=\text{Linear-Code-Decoder($c''_7$)}=\\ \begin{pmatrix} %c' @@ -315,10 +315,10 @@ Der verwendete Linear-Code wird im Abschnitt \ref{mceliece:subsection:seven_four \text{)} . \end{align*} - \end{itemize} +% \end{itemize} \item Entschlüsselung (Umkehrung des $S_4$-Matrix-Effekts): - \begin{itemize} - \item[] +% \begin{itemize} +% \item[] \begin{align*} d'_{4}&=S_{4}^{-1} \cdot c'_4 \,(= d_4)\\ \begin{pmatrix} @@ -343,7 +343,7 @@ Der verwendete Linear-Code wird im Abschnitt \ref{mceliece:subsection:seven_four \end{pmatrix} . \end{align*} - \end{itemize} +% \end{itemize} \end{itemize} \subsection{7/4-Code @@ -368,7 +368,6 @@ Damit diese Multiplikation mit Matrizen ausgeführt werden kann, werden die Poly Auch das Datenpolynom wird mit einem Vektor dargestellt: $P_d = d_0 \cdot x^0 + d_1 \cdot x^1 + d_2 \cdot x^2 + d_3 \cdot x^3 \implies [d_0, d_1, d_2, d_3] = d_4$. Der Vektor $g_4$ wird nun in die sogenannte Generatormatrix $G_{7,4}$ gepackt, sodass die Polynommultiplikation mit $d_4$ mittels Matrixmultiplikation realisiert werden kann: - \[ c_7=G_{7,4} \cdot d_4= \begin{pmatrix} 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/multiplikation/loesungsmethoden.tex b/buch/papers/multiplikation/loesungsmethoden.tex index 2531bbb..578833b 100755 --- a/buch/papers/multiplikation/loesungsmethoden.tex +++ b/buch/papers/multiplikation/loesungsmethoden.tex @@ -517,7 +517,6 @@ Die Hardwareinformationen des verwendeten Computers sind in der Tabelle \ref{mul \end{figure} \section{Fazit} -\rhead{Fazit} Wie man im Abschnitt \ref{multiplikation:section:Implementation} sehen kann, sind die gezeigten Algorithmen trotz der theoretisch geringeren Zeitkomplexitäten den Implementationen der numerischen Bibliotheken klar unterlegen. Ein optimierter Speicherzugriff hat einen weitaus grösseren Einfluss auf die Laufzeit als die Zeitkomplexität des Algorithmus. @@ -528,3 +527,5 @@ Denke man an sehr kleine Mikrocontroller ohne Floatingpoint Recheneinheiten oder Der Overhead der gezeigten Algorithmen ist in allen Fällen grösser als bei der Standardmethode (z.B. sieben rekursive Aufrufe gegenüber drei \texttt{for}-Schleifen). Um diesem entgegenzuwirken muss der Laufzeitunterschied zwischen Addition und Multiplikation gross genug sein. Wenn dies gegeben ist und dazu noch grosse Matritzen multipliziert werden, kann die Verwendung der Algorithmen von Strassen oder Winograd zu einer Senkung der Laufzeit führen. + +\rhead{Fazit} diff --git a/buch/papers/munkres/teil2.tex b/buch/papers/munkres/teil2.tex index e4e968a..9ad64b4 100644 --- a/buch/papers/munkres/teil2.tex +++ b/buch/papers/munkres/teil2.tex @@ -5,13 +5,13 @@ % \section{Schwierigkeit der Lösung \label{munkres:section:teil2}} -\rhead{Schwierigkeit der Lösung} Eine Permutation ist eine Anordnung von Objekten in einer bestimmten Reihenfolge oder eine Umordnung von Objekten aus einer vorgegebenen Reihung. Ist eine optimale Zuordnung gefunden, so steht in jeder Zeile und jeder Spalte der Matrix genau ein Element, das zur optimalen Lösung gehört, eine solche Gruppe von Positionen wird auch als Transversale der Matrix bezeichnet. \index{Transversale einer Matrix}% Die Problemstellung kann auch so formuliert werden, dass man die Zeilen- oder die Spaltenvektoren so umordnet soll, dass die Summe der Elemente in der Hauptdiagonale maximal wird. +\rhead{Schwierigkeit der Lösung} In einer $n\times n$-Matrix gibt es genau so viele Möglichkeiten, die Zeilen- bzw.~Spaltenvektoren zu ordnen, wie es Permutationen von $n$ Elementen gibt, also $n!$. Ausser bei kleinen Matrizen ist es daher nahezu aussichtslos, die optimale Lösung durch Berechnung aller Möglichkeiten zu finden. Schon bei einer $10\times 10$-Matrix gibt es nahezu 3.63 Millionen ($10!=3628800$) zu berücksichtigende Permutationen. diff --git a/buch/papers/munkres/teil3.tex b/buch/papers/munkres/teil3.tex index 500216a..8a0d2cb 100644 --- a/buch/papers/munkres/teil3.tex +++ b/buch/papers/munkres/teil3.tex @@ -5,7 +5,6 @@ % \section{Der Munkres-Algorithmus oder die ungarische Methode \label{munkres:section:teil3}} -\rhead{Ungarische Methode} Mit der ungarischen Methode können also Optimierungsprobleme gelöst werden, die bei gewichteten Zuordnungen in bipartiten Graphen entstehen. @@ -13,6 +12,8 @@ Mit ihr kann die eindeutige Zuordnung von Objekten aus zwei Gruppen so optimiert werden, dass die Gesamtkosten minimiert werden bzw.~der Gesamtgewinn maximiert werden kann. +\rhead{Ungarische Methode} + \subsection{Geschichte \label{munkres:subsection:malorum}} Die Ungarische Methode wurde 1955 von Harold Kuhn entwickelt und veröffentlicht. @@ -20,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/punktgruppen/crystals.tex b/buch/papers/punktgruppen/crystals.tex index 1ba5466..4def071 100644 --- a/buch/papers/punktgruppen/crystals.tex +++ b/buch/papers/punktgruppen/crystals.tex @@ -1,4 +1,5 @@ \section{Kristalle} +\rhead{Kristalle} \index{Kristalle}% Eine nicht allzu häufig gestellte Frage ist, wie ein Kristall definiert ist. Um zu klären, was ein Kristall mit Symmetrien zu tun hat, ist jedoch genau diese Frage äusserst relevant. diff --git a/buch/papers/punktgruppen/intro.tex b/buch/papers/punktgruppen/intro.tex index f11a346..c537f69 100644 --- a/buch/papers/punktgruppen/intro.tex +++ b/buch/papers/punktgruppen/intro.tex @@ -1,5 +1,5 @@ \section{Einleitung} - +\rhead{Einleitung} Es gibt viele Möglichkeiten sich in Kristallen zu verlieren. \index{Kristall}% Auch wenn man nur die mathematischen Betrachtungsweisen berücksichtigt, hat man noch viel zu viele Optionen, sich mit Kristallen zu beschäftigen. diff --git a/buch/papers/punktgruppen/piezo.tex b/buch/papers/punktgruppen/piezo.tex index cc4272b..eddd8a5 100644 --- a/buch/papers/punktgruppen/piezo.tex +++ b/buch/papers/punktgruppen/piezo.tex @@ -1,4 +1,5 @@ \section{Piezoelektrizität} +\rhead{Piezoelektrizität} \index{Piezoelektrizität}% Die Piezoelektrizität ist die spannende Eigenschaft, dass gewisse Kristalle eine elektrische Spannung erzeugen, wenn mechanischer Druck auf sie ausgeübt wird. \index{elektrische Spannung}% diff --git a/buch/papers/punktgruppen/symmetry.tex b/buch/papers/punktgruppen/symmetry.tex index ec06046..dd37ba9 100644 --- a/buch/papers/punktgruppen/symmetry.tex +++ b/buch/papers/punktgruppen/symmetry.tex @@ -1,4 +1,5 @@ \section{Symmetrie} +\rhead{Symmetrie} Das Wort Symmetrie ist sehr alt und hat sich seltsamerweise von seinem ursprünglichen griechischen Wort \(\mathrm{\Sigma\upsilon\mu\mu\varepsilon\tau\rho\iota\alpha}\)\footnote{\emph{Symmetr\'ia}: ein gemeinsames Mass habend, gleichmässig,verhältnismässig} fast nicht verändert. In der Alltagssprache mag es ein locker definierter Begriff sein, in der Mathematik hat Symmetrie jedoch eine sehr präzise Bedeutung. diff --git a/buch/papers/reedsolomon/anwendungen.tex b/buch/papers/reedsolomon/anwendungen.tex index 9bb1d99..12bfe74 100644 --- a/buch/papers/reedsolomon/anwendungen.tex +++ b/buch/papers/reedsolomon/anwendungen.tex @@ -5,18 +5,18 @@ % \section{Anwendungen des Reed-Solomon-Codes \label{reedsolomon:section:anwendung}} -\rhead{Anwendungen} In den vorherigen Abschnitten haben wir betrachtet, wie Reed-Solomon-Codes in der Theorie funktionieren. In diesem Abschnitt werden wir einige Anwendungen vorstellen, bei denen ein Reed-Solomon-Code zum Einsatz kommt. 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. -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. +\rhead{Anwendungen} +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 02484e0..037fba7 100644 --- a/buch/papers/reedsolomon/codebsp.tex +++ b/buch/papers/reedsolomon/codebsp.tex @@ -5,14 +5,14 @@ % \section{Codierung eines Beispiels \label{reedsolomon:section:codebsp}} -\rhead{Codierung eines Beispiels} Um die Funktionsweise eines Reed-Solomon-Codes besser zu verstehen, werden wir die einzelnen Probleme und ihre Lösungen anhand eines Beispiels betrachten. Da wir in endlichen Körpern rechnen, werden wir zuerst solch einen Körper festlegen. Dabei müssen wir die 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} % OLD TEXT %Alle folgenden Berechnungen wurden mit den beiden Restetabellen \ref{reedsolomon:subsection:adtab} und \ref{reedsolomon:subsection:mptab} durchgeführt. %Aus den Tabellen folgt auch, dass uns nur die Zahlen \[\mathbb{F}_{11} = \{0,1,2,3,4,5,6,7,8,9,10\}\] zur Verfügung stehen. @@ -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 4f7fd7b..b714225 100644 --- a/buch/papers/reedsolomon/rekonstruktion.tex +++ b/buch/papers/reedsolomon/rekonstruktion.tex @@ -5,7 +5,6 @@ % \section{Nachricht rekonstruieren \label{reedsolomon:section:rekonstruktion}} -\rhead{Rekonstruktion der Nachricht} Im letzten Abschnitt haben wir eine Möglichkeit gefunden, wie wir die fehlerhaften Stellen lokalisieren können. Mit diesen Stellen soll es uns nun möglich sein, aus dem fehlerhaften empfangenen Nachrichtenvektor wieder unsere Nachricht zu rekonstruieren. Das Lokatorpolynom @@ -17,9 +16,10 @@ 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: \[ \textcolor{gray}{ @@ -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 a098107..ff3f35f 100644 --- a/buch/papers/reedsolomon/zusammenfassung.tex +++ b/buch/papers/reedsolomon/zusammenfassung.tex @@ -5,15 +5,15 @@ % \section{Zusammenfassung \label{reedsolomon:section:zf}} -\rhead{Zusammenfassung} \index{Reed-Solomon-Code, Zusammenfassung}% \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. +\rhead{Zusammenfassung} \subsubsection{Schritt 2: Codierung} Für die Codierung wird die Nachricht als Koeffizienten des Polynoms $m(X)$ geschrieben, anschliessend wird $a^i$ in $m(X)$ eingesetzt. Daraus ergibt sich die Codierungsmatrix diff --git a/buch/papers/spannung/main.tex b/buch/papers/spannung/main.tex index d2aeda9..14bab31 100644 --- a/buch/papers/spannung/main.tex +++ b/buch/papers/spannung/main.tex @@ -4,9 +4,9 @@ % (c) 2020 Hochschule Rapperswil % \chapter{Dreidimensionaler Spannungszustand\label{chapter:spannung}} -\lhead{Dreiachsiger Spannungszustand} +\lhead{Dreidimensionaler Spannungszustand} \begin{refsection} -\chapterauthor{Adrian Schuler und Thomas Reichlin} +\chapterauthor{Thomas Reichlin und Adrian Schuler} % TODO Text diff --git a/buch/papers/spannung/teil0.tex b/buch/papers/spannung/teil0.tex index f9afde0..f708055 100644 --- a/buch/papers/spannung/teil0.tex +++ b/buch/papers/spannung/teil0.tex @@ -9,7 +9,7 @@ Man spricht auch von einem Elementarwürfel. \begin{figure} \centering \includegraphics[width=0.4\linewidth,keepaspectratio]{papers/spannung/Grafiken/Bild2.png} - \caption{Infinitesimales Bodenelement mit den 9 Spannungen} + \caption{Infinitesimales Bodenelement mit den neun Spannungen} \label{fig:Bild2} \end{figure} @@ -27,8 +27,8 @@ Daraus können die äquivalenten Dehnungen $\varepsilon$ mit Hilfe des Hook'sche Daher gibt es auch den entsprechenden Dehnungszustand. -\section{Spannungszustand\label{spannung:section:Spannungsustand}} -\rhead{Spannungszustand} +\section{Einachsiger Spannungszustand\label{spannung:section:Spannungsustand}} +\rhead{Einachsiger Spannungszustand} Im einachsigen Spannungszustand herrscht nur die Normalspannung $\sigma_{11}$ (siehe Abbildung~\ref{fig:Bild1}). Das Hook'sche Gesetz beschreibt genau diesen 1D Spannungszustand. @@ -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 8bf1968..fec0120 100644 --- a/buch/papers/spannung/teil2.tex +++ b/buch/papers/spannung/teil2.tex @@ -4,17 +4,17 @@ Durch komplexe Spannungsausbreitungen im Boden entstehen im 3D-Spannungszustand \begin{figure} \centering \includegraphics[width=0.30\linewidth,keepaspectratio]{papers/spannung/Grafiken/infinitesimalerWuerfel.png} - \caption{Beispiel eines Spannungszustandes; Vergrösserung eines infinitesimalen Bodenteilchen} + \caption{Beispiel eines Spannungszustandes; Vergrösserung eines infinitesimalen Bodenteilchens} \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\} @@ -233,7 +233,7 @@ Die Normalspannung $\sigma_{22}$ lässt sich zum Beispiel als berechnen. \section{Reduzierte Spannungs- und Dehnungsgleichungen} - +\rhead{Reduzierte Spannungs- und Dehnungsgleichungen} Man betrachte nun die Eigenschaften des Elastizitätstensors. Dieser ist quadratisch und symmetrisch, die verschiedenen Einträge wechseln sich aber miteinander ab. Es ergeben sich keine Blöcke mit einheitlichen Einträgen. @@ -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 b809892..f095947 100644 --- a/buch/papers/uebersicht.tex +++ b/buch/papers/uebersicht.tex @@ -10,5 +10,133 @@ Im zweiten Teil kommen die Teilnehmer des Seminars selbst zu Wort. Die im ersten Teil dargelegten mathematischen Methoden und grundlegenden Modelle werden dabei verfeinert, verallgemeinert -und auch numerisch überprüft. +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 +Eigenschaft haben, eine geometrische Realsierung zu besitzen. +Diese führt zu zusätzlichen Einschränkungen, die einen positiven +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 +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. + +Der Reed-Solomon-Code ist ein Klassiker unter den fehlerkorrigierenden +Codes. +Berühmt gemacht durch seine Anwendung in den Voyager-Sonden und in CDs +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 +ist dann nicht mehr schwierig. +Die Analogie wird deutlich, wenn man das Codierungsverfahren und +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 +Bildern ableiten. + +Es gibt zwar noch keine ernstzunehmenden Quantencomputer, aber man weiss +bereits, dass ein leistungsfähriger Quantencomputer viele der heute +im Internet üblichen Verschlüsselungsverfahren, allen voran das RSA-Verfahren, +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. + +Vektoren und Matrizen bilden die Basis vieler geometrischer +Anwendungen. +Doch ist die Beschreibung von Bewegungen im Raum mit Matrizen nicht +immer einfach. +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. +So gibt es zum Beispiel ein Euler-Formel, für Drehungen und Spiegelungen +kann die selbe Abbildungsformel verwendet werden und die Zusammensetzung +von Transformationen ist eine Multiplikation in einer Algebra, die +aus den Vektoren konstruiert worden ist. +In drei Dimensionen ist diese Algebra der Quaternionen zum Beispiel +in der Computergraphik sehr beliebt. + +Man soll sein Haus nicht auf Sand bauen, sagt eine Redensart. +Etwas mathematischer heisst das, dass man den Spannungszustand, +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 +kann man aber auf eine handlichere Beschreibung zurückkommen, +die wieder nur Matrizen verwendet. +Ausserdem ergeben sich daraus spezielle Blockstrukturen der +Matrizen. + +Ein Erdbeben versetzt alles auf der Erdoberfläche in Bewegung und +kann beträchtliche Schäden anrichten. +Daher wird die seismische Aktivität weiltweit überwacht. +Ein Seismograph enthält eine schwingungsfähige Masse, die die Bewegungen +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 +und illustrieren mit Hilfe von Simulationen, wie er funktioniert. + +Eine Matrix kann dazu verwende werden, die Kosten zusammenzustellen, +die die Lösung einzelner Aufgaben durch verschiedene Anbieter +verursachen würden. +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/main.tex b/buch/papers/verkehr/main.tex index 98d0581..7972988 100644 --- a/buch/papers/verkehr/main.tex +++ b/buch/papers/verkehr/main.tex @@ -4,8 +4,10 @@ % (c) 2020 Hochschule Rapperswil % \chapter{Verkehrsfluss und Verkehrsnetze\label{chapter:verkehr}} +\lhead{Verkehrsfluss und Verkehrsnetze} +\rhead{} \begin{refsection} -\chapterauthor{Pascal Andreas Schmid und Robine Luchsinger} +\chapterauthor{Robine Luchsinger und Pascal Andreas Schmid} \input{papers/verkehr/section1.tex} \input{papers/verkehr/section2.tex} diff --git a/buch/papers/verkehr/section1.tex b/buch/papers/verkehr/section1.tex index 4a450f1..cc5893d 100644 --- a/buch/papers/verkehr/section1.tex +++ b/buch/papers/verkehr/section1.tex @@ -8,12 +8,13 @@ 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. \section{Suchalgorithmen} +\rhead{Suchalgorithmen} Inbesondere bei Graphen in Form von Verkehrsnetzen ist das Finden eines kürzesten Weges von Interesse. Mathematisch betrachtet handelt es sich hierbei um ein Optimierungsproblem, bei dem die Summe der Kantengewichte zwischen zwei Knoten minimiert werden soll. Zu diesem Zweck existieren verschiedene Suchalgorithmen. In den folgenden Abschnitten wird auf eine Auswahl davon eingegangen. Zuvor ist es jedoch notwendig, einige Begriffe und Eigenschaften von Suchalgorithmen zu definieren. \index{kürzester Weg}% \index{Optimierungsproblem}% @@ -98,6 +99,7 @@ ermittelt. \section{PageRank-Algorithmus} +\rhead{PageRank-Algorithmus} \index{PageRank-Algorithmus}% \index{Page, Larry}% \index{Brin, Sergey}% diff --git a/buch/papers/verkehr/section2.tex b/buch/papers/verkehr/section2.tex index a0e88b6..90cea3f 100644 --- a/buch/papers/verkehr/section2.tex +++ b/buch/papers/verkehr/section2.tex @@ -7,6 +7,7 @@ Die Anzahl der Knoten im abgesuchten Netzwerk wirkt sich direkt auf die Rechenze \index{Zeitkomplexität}% Für den A*-Algorithmus ist die Zeitkomplexität einerseits abhängig von der verwendeten Heuristik, andererseits aber auch vom vorliegenden Netzwerk selbst. Aus diesem Grund lässt sich keine definitive Angabe zur Zeitkomplexität machen. +\rhead{Versuchsreihe} Die beiden Versuchsreihen unterscheiden sich zudem dahingehend, dass der Start- und Zielknoten bei der ersten Versuchsreihe im Netzwerk diametral gegenüber liegen. Dadurch gehen viele Knoten verloren, welcher \emph{Dijkstra} als uninformierter Suchalgorithmus absuchen würde. In der zweiten Veruschsreihe werden hingegen Start- un Zielpunkt zufällig im Netzwerk ausgewählt. Es wird deshalb erwartet, dass die Unterschiede in der Rechenzeit der beiden Algorithmen in der zweiten Versuchsreihe deutlich ausgeprägter sind. \subsection{Einfluss der Knotenzahl auf die Rechenzeit} diff --git a/buch/papers/verkehr/section3.tex b/buch/papers/verkehr/section3.tex index 50bae2a..76fb3b0 100644 --- a/buch/papers/verkehr/section3.tex +++ b/buch/papers/verkehr/section3.tex @@ -1,4 +1,5 @@ \section{Ausblick} +\rhead{Ausblick} \subsection{Optimierungsprobleme bei Graphen} Das Finden eines kürzesten Pfades, sprich die Minimierung der Summe der Kantengewichte, ist nur eines der Optimierungsprobleme, die sich im Bereich von Graphen aufstellen lassen. Verschiedene, ähnliche Problemstellungen lassen sich teilweise mit denselben Algorithmen lösen. |
