From 5294c40d558e93a034d43846e98176291fb32692 Mon Sep 17 00:00:00 2001
From: michael-OST <75078383+michael-OST@users.noreply.github.com>
Date: Mon, 24 May 2021 14:28:24 +0200
Subject: update decohnefehler.tex, create decmitfehler.tex

---
 buch/papers/reedsolomon/decmitfehler.tex | 16 ++++++++++++++++
 1 file changed, 16 insertions(+)
 create mode 100644 buch/papers/reedsolomon/decmitfehler.tex

(limited to 'buch/papers/reedsolomon/decmitfehler.tex')

diff --git a/buch/papers/reedsolomon/decmitfehler.tex b/buch/papers/reedsolomon/decmitfehler.tex
new file mode 100644
index 0000000..fead10e
--- /dev/null
+++ b/buch/papers/reedsolomon/decmitfehler.tex
@@ -0,0 +1,16 @@
+%
+% teil3.tex -- Beispiel-File für Teil 3
+%
+% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+\section{Decodierung mit Fehler
+\label{reedsolomon:section:decmitfehler}}
+\rhead{fehlerhafte rekonstruktion}
+moin
+
+
+\subsection{Der Satz von Fermat
+\label{reedsolomon:subsection:fermat}}
+wer ist fermat?
+
+
-- 
cgit v1.2.1


From 60bfb41261f51cf20ce65a9242c2624b31d74e75 Mon Sep 17 00:00:00 2001
From: michael-OST <75078383+michael-OST@users.noreply.github.com>
Date: Mon, 24 May 2021 17:17:56 +0200
Subject: decmitfehler.tex updated

---
 buch/papers/reedsolomon/decmitfehler.tex | 185 ++++++++++++++++++++++++++++++-
 1 file changed, 183 insertions(+), 2 deletions(-)

(limited to 'buch/papers/reedsolomon/decmitfehler.tex')

diff --git a/buch/papers/reedsolomon/decmitfehler.tex b/buch/papers/reedsolomon/decmitfehler.tex
index fead10e..923c1c5 100644
--- a/buch/papers/reedsolomon/decmitfehler.tex
+++ b/buch/papers/reedsolomon/decmitfehler.tex
@@ -6,11 +6,192 @@
 \section{Decodierung mit Fehler
 \label{reedsolomon:section:decmitfehler}}
 \rhead{fehlerhafte rekonstruktion}
-moin
+Im zweiten Teil zur Decodierung betrachten wir den Fall, dass unser Übertragungskanal nicht fehlerfrei ist.
+Wir legen daher den Fehlervektor
+\[
+u = [0, 0, 0, 3, 0, 0, 0, 0, 2, 0]
+\]
+fest, den wir zu unserem Übertragungsvektor als Fehler dazu addieren und somit
 
+\begin{center}
+
+\begin{tabular}{c | c r }
+	$v$ & & $[5,3,6,5,2,10,2,7,10,4]$\\
+	$u$ & $+$ & $[0,0,0,3,0,0,0,0,2,0]$\\
+	\hline
+	$w$ & & $[5,3,6,8,2,10,2,7,1,4]$\\
+\end{tabular}
+
+% alternative design
+%\begin{tabular}{c | c cccccccccccc }
+%	$v$ & & $[$&$5,$&$3,$&$6,$&$5,$&$2,$&$10,$&$2,$&$7,$&$10,$&$4$&$]$\\
+%	$u$ & $+$ & $[$&$0,$&$0,$&$0,$&$3,$&$0,$&$0,$&$0,$&$0,$&$2,$&$0$&$]$\\
+%	\hline
+%	$w$ & & $[$&$5,$&$3,$&$6,$&$8,$&$2,$&$10,$&$2,$&$7,$&$1,$&$4$&$]$\\
+%\end{tabular}
+
+\end{center}
+als Übertragungsvektor auf der Empfängerseite erhalten. 
+
+Wenn wir den Übertragungsvektor jetzt Rücktransformieren wie im vorherigen Kapitel erhalten wir
+\[
+r = [\underbrace{5,7,4,10,}_{Fehlerinfo}5,4,5,7,6,7].
+\]
+Im Vergleich zum vorherigen Kapitel sind die Fehlerkorrekturstellen jetzt $\neq 0$, was bedeutet, dass wir diesen Übertragungsvektor fehlerhaft empfangen haben und sich die Nachricht jetzt nicht mehr so einfach decodieren lässt.
+
+% warum wir die fehler suchen
+Da Reed-Solomon-Codes in der Lage sind, eine Nachricht aus weniger Stellen zu rekonstruieren als wir ursprünglich haben, so müssen wir nur die Fehlerhaften Stellen finden und eliminieren, damit wir unsere Nutzdaten rekonstruieren können.
+Damit stellt sich die Frage, wie wir die Fehlerstellen $e$ finden.
+Dafür wählen wir einen Primitiven Ansatz mit
+\begin{align}
+	m(X) & = 4X^5 + 7X^4 + 2X^3 + 5X^2 + 8X + 1 \\
+	r(X) & = 5X^9 + 7X^8 + 4X^7 + 10X^6 + 5X^5 + 4X^4 + 5X^3 + 7X^2 + 6X + 7 \\
+	e(X) & = r(X) - m(X).
+\end{align}
+Setzen wir jetzt unsere Einheitswurzel für $X$ ein, so erhalten wir
+\begin{center}
+\begin{tabular}{c c c c c c c c c c c}
+	\hline
+	$i$& $0$& $1$& $2$& $3$& $4$& $5$& $6$& $7$& $8$& $9$\\
+	\hline
+	$r(a^{i})$& $5$& $3$& $6$& $8$& $2$& $10$& $2$& $7$& $1$& $4$\\
+	$m(a^{i})$& $5$& $3$& $6$& $5$& $2$& $10$& $2$& $7$& $10$& $4$\\
+	$e(a^{i})$& $0$& $0$& $0$& $3$& $0$& $0$& $0$& $0$& $2$& $0$\\
+	\hline
+\end{tabular}
+\end{center}
+und damit die Information, dass an allen Stellen, die nicht Null sind, Fehler enthalten.
+Um jetzt alle nicht Nullstellen zu finden, wenden wir den Satz von Fermat an. 
 
 \subsection{Der Satz von Fermat
 \label{reedsolomon:subsection:fermat}}
-wer ist fermat?
+Der Satz von Fermat besagt, dass für
+\[
+f(X) = X^{q-1} -1 = 0
+\] 
+gilt, egal was wir für $q$ einsetzen.
+
+Für unser Beispiel erhalten wir
+\[
+f(X) = X^{10}-1 = 0 \qquad \text{für } X = \{1,2,3,4,5,6,7,8,9,10\}
+\]
+und können $f(X)$ auch umschreiben in
+\[
+f(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).
+\]
+Zur Überprüfung können wir unsere Einheitswurzel in $a$ einsetzen und werden sehen, dass wir für $f(X) = 0$ erhalten werden.
+Nach der gleichen Überlegung können wir jetzt auch $e(X)$ darstellen als
+\[
+e(X) = (X-a^0)(X-a^1)(X-a^2) \qquad \qquad (X-a^4)(X-a^5)(X-a^6)(X-a^7) \qquad \qquad (X-a^9) \cdot p(x),
+\]
+wobei $p(X)$ das Restpolynom ist und die Fehlerstellen beinhaltet.
+Wenn wir jetzt den grössten gemeinsamen Teiler von $f(X)$ und $e(X)$ berechnen, so erhalten wir mit
+\[
+\operatorname{ggT}(f(X),e(X)) = (X-a^0)(X-a^1)(X-a^2) \qquad \qquad (X-a^4)(X-a^5)(X-a^6)(X-a^7) \qquad \qquad (X-a^9)
+\]
+eine Liste von Nullstellen, an denen es keine Fehler gegeben hat.
+Da wir uns jedoch für eine Liste mit Nullstellen interessieren, an denen es Fehler gegeben hat berechnen wir stattdessen das kgV von $f(X)$ und $e(X)$ als
+\[
+\operatorname{kgV}(f(X),e(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).
+\]
+Wir können das Resultat noch zerlegen in
+\[
+\operatorname{kgV}(f(X),e(X)) = d(X) \cdot e(X).
+\]
+Somit muss $d(X)$ eine Liste von Nullstellen enthalten an denen es Fehler gegeben hat.
+\[
+d(X) = (X-a^3)(X-a^8)
+\]
+
+
+und ist damit unser gesuchtes Lokatorpolynom.
+
+Das einzige Problem was jetzt noch bleibt ist, dass wir $e(X)$ berechnet haben aus
+\[
+e(X) = r(X) - m(X),
+\]
+wobei $m(X)$ auf der Empfängerseite unbekannt ist.
+Es sieht danach aus, das wir diesen Lösungsansatz nicht verwenden können, da uns ein entscheidender Teil fehlt.
+Bei einer näheren Betrachtung von $m(X)$ fällt uns aber auf, dass wir doch etwas über $m(X)$ wissen.
+Wir kennen nämlich die ersten vier Stellen, da diese für die Fehlerkorrektur zuständig sind und daher Null sein müssen.
+\[
+m = [0,0,0,0,?,?,?,?,?,?]
+\]
+An genau diesen Stellen liegt auch die Information, wo unsere Fehlerstellen liegen, was uns ermöglicht, den Teil von $e(X)$ zu berechnen, der uns auch interessiert.
+
+Wir können $e(X)$ also bestimmen als
+\[
+e(X) = 5X^9 + 7X^8 + 4X^7 + 10X^6 + p(X)
+\]
+wobei $p(X)$ wiederum ein unbekanntes Restpolynom ist und
+\[
+f(X) = X^{10} - 1 = X^{10} + 10
+\]
+ist können wir so in einer ersten Instanz den grössten gemeinsamen Teiler von $f(X)$ und $e(X)$ berechnen.
+Dafür nehmen wir uns wiederum den Euklidischen Algorithmus zur Hilfe und berechnen so
+
+\[
+\arraycolsep=1.4pt
+\begin{array}{rcrcrcrcccrcrcrcrcrcrcrcrcr}
+	X^{10}& & & & & & &+& 10& & & & &:&5X^9&+&7X^8&+& 4X^7&+&10X^6&+&p(X)&=&9X&+&5\\
+	X^{10}&+& 8X^9&+& 3X^8&+&2X^7&+& p(X)& &  & & & &   & & & & & &   & &  & & \\ \cline{1-9}
+	&& 3X^9&+& 8X^8&+& 9X^7&+& p(X)& &   & & & & & &   & &  & & \\
+	&& 3X^9&+& 2X^8&+& 9X^7&+& p(X)& &   & & & & & &   & &  & & \\ \cline{3-9}
+	& &    & &6X^8&+&0X^7&+&p(X)& &   & & & & & &   & &  & & \\
+\end{array}
+\]
+
+\[
+\arraycolsep=1.4pt
+\begin{array}{rcrcrcrcccrcrcrcrcrcrcrcrcr}
+	5X^9&+& 7X^8&+& 4X^7&+& 10X^6&+& p(X)& & & & &:&6X^8&+&0X^7& & & & & & &=&10X&+&3\\
+	5X^9&+& 0X^8&+& p(X)& & & & & &  & & & &   & & & & & &   & &  & & \\ \cline{1-5}
+	&& 7X^8&+& p(X)& & & & & &   & & & & & &   & &  & & \\
+\end{array}
+\]
+und erhalten
+\[
+\operatorname{ggT}(f(X),e(X)) = 6X^8
+\]
+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 ???. 
 
+Aus diesem erweiterten Euklidischen Algorithmus erhalten wir 
+\begin{center}
+	
+	\begin{tabular}{| c | c | c c |}
+		\hline
+		$k$ &  $q_i$ & $e_i$ & $f_i$\\
+		\hline 
+		& & $0$& $1$\\
+		$0$& $9X + 5$& $1$& $0$\\
+		$1$& $10X + 3$& $9X+5$& $1$\\
+		$2$& & \textcolor{blue}{$2X^2 + 0X + 5$}& $10X + 3$\\
+		\hline
+	\end{tabular}	
+	
+\end{center}
+und erhalten auf diesem Weg den Faktor
+\[
+d(X) = 2X^2 + 5,
+\]
+den wir in 
+\[
+d(X) = 2(X-5)(X-6)
+\]
+zerlegen können.
+Da die unbekannten Stellen im Lokatorpolynom
+\[
+d(X) = (X-a^i)(X-a^i)
+\]
+sind, müssen wir nur noch $i$ berechnen als
+\begin{center}
+	$a^i = 5 \qquad \Rightarrow \qquad i = 3$
+	
+	$a^i = 6 \qquad \Rightarrow \qquad i = 8$.
+\end{center}
 
+Somit erhalten wir schliesslich
+\[
+d(X) = (X-a^3)(X-a^8)
+\]
+als unser Lokatorpolynom mit den Fehlerhaften Stellen.
\ No newline at end of file
-- 
cgit v1.2.1


From 73d5c3d4df0f73e96c1bac2ae1ce3b4dfcdc9d90 Mon Sep 17 00:00:00 2001
From: michael-OST <75078383+michael-OST@users.noreply.github.com>
Date: Thu, 10 Jun 2021 12:23:57 +0200
Subject: updated a lot

---
 buch/papers/reedsolomon/decmitfehler.tex | 292 +++++++++++++++++++++----------
 1 file changed, 203 insertions(+), 89 deletions(-)

(limited to 'buch/papers/reedsolomon/decmitfehler.tex')

diff --git a/buch/papers/reedsolomon/decmitfehler.tex b/buch/papers/reedsolomon/decmitfehler.tex
index 923c1c5..db6e586 100644
--- a/buch/papers/reedsolomon/decmitfehler.tex
+++ b/buch/papers/reedsolomon/decmitfehler.tex
@@ -3,52 +3,109 @@
 %
 % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
 %
-\section{Decodierung mit Fehler
+\section{Decodierung: Ansatz mit Fehlerkorrektur
 \label{reedsolomon:section:decmitfehler}}
 \rhead{fehlerhafte rekonstruktion}
-Im zweiten Teil zur Decodierung betrachten wir den Fall, dass unser Übertragungskanal nicht fehlerfrei ist.
-Wir legen daher den Fehlervektor
+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 diesem Abschnitt betrachten wir somit die Idee der Fehlerkorrektur und wie wir diese auf unser Beispiel anwenden können.
+Der Übertragungskanal im Beispiel weisst jetzt den Fehlervektor 
 \[
 u = [0, 0, 0, 3, 0, 0, 0, 0, 2, 0]
 \]
-fest, den wir zu unserem Übertragungsvektor als Fehler dazu addieren und somit
+auf.
 
+Senden wir jetzt unser Übertragungsvektor $v$ durch diesen Kanal addiert sich der Fehlervektor $u$ auf unsere Übertragung und wir erhalten 
 \begin{center}
-
-\begin{tabular}{c | c r }
-	$v$ & & $[5,3,6,5,2,10,2,7,10,4]$\\
-	$u$ & $+$ & $[0,0,0,3,0,0,0,0,2,0]$\\
-	\hline
-	$w$ & & $[5,3,6,8,2,10,2,7,1,4]$\\
-\end{tabular}
-
-% alternative design
-%\begin{tabular}{c | c cccccccccccc }
-%	$v$ & & $[$&$5,$&$3,$&$6,$&$5,$&$2,$&$10,$&$2,$&$7,$&$10,$&$4$&$]$\\
-%	$u$ & $+$ & $[$&$0,$&$0,$&$0,$&$3,$&$0,$&$0,$&$0,$&$0,$&$2,$&$0$&$]$\\
+	
+	\begin{tabular}{c | c r }
+		$v$ & & $[5,3,6,5,2,10,2,7,10,4]$\\
+		$u$ & $+$ & $[0,0,0,3,0,0,0,0,2,0]$\\
+		\hline
+		$w$ & & $[5,3,6,8,2,10,2,7,1,4]$\\
+	\end{tabular}
+	
+	% alternative design
+	%\begin{tabular}{c | c cccccccccccc }
+	%	$v$ & & $[$&$5,$&$3,$&$6,$&$5,$&$2,$&$10,$&$2,$&$7,$&$10,$&$4$&$]$\\
+	%	$u$ & $+$ & $[$&$0,$&$0,$&$0,$&$3,$&$0,$&$0,$&$0,$&$0,$&$2,$&$0$&$]$\\
+	%	\hline
+	%	$w$ & & $[$&$5,$&$3,$&$6,$&$8,$&$2,$&$10,$&$2,$&$7,$&$1,$&$4$&$]$\\
+	%\end{tabular}
+	
+\end{center}
+als neuen, fehlerbehafteten Übertragungsvektor $w$ auf der Empfängerseite.
+% Old Text
+%In diesem Abschnitt gehen wir genauer darauf ein, wie der Reed-Solomon-Code eine solche Feherkorrektur vornimt. 
+%
+%In diesem Abschnitt betrachten wir das Problem, dass während der Übertragung des Übertragungsvektors von unserem Beispiel 
+%
+%
+%Zu diesem Zweck wurden Fehler korrigierende Codes entwickelt.
+%
+%Dieser Optimalfall kann jedoch mit keinem Übertragungskanal garantiert werden
+%
+%
+%Im zweiten Teil zur Decodierung betrachten wir den Fall, dass unser Übertragungskanal nicht fehlerfrei ist.
+%Wir legen daher den Fehlervektor
+%\[
+%u = [0, 0, 0, 3, 0, 0, 0, 0, 2, 0]
+%\]
+%fest, den wir zu unserem Übertragungsvektor als Fehler dazu addieren und somit
+%
+%\begin{center}
+%
+%\begin{tabular}{c | c r }
+%	$v$ & & $[5,3,6,5,2,10,2,7,10,4]$\\
+%	$u$ & $+$ & $[0,0,0,3,0,0,0,0,2,0]$\\
 %	\hline
-%	$w$ & & $[$&$5,$&$3,$&$6,$&$8,$&$2,$&$10,$&$2,$&$7,$&$1,$&$4$&$]$\\
+%	$w$ & & $[5,3,6,8,2,10,2,7,1,4]$\\
 %\end{tabular}
-
-\end{center}
-als Übertragungsvektor auf der Empfängerseite erhalten. 
-
-Wenn wir den Übertragungsvektor jetzt Rücktransformieren wie im vorherigen Kapitel erhalten wir
+%
+%% alternative design
+%%\begin{tabular}{c | c cccccccccccc }
+%%	$v$ & & $[$&$5,$&$3,$&$6,$&$5,$&$2,$&$10,$&$2,$&$7,$&$10,$&$4$&$]$\\
+%%	$u$ & $+$ & $[$&$0,$&$0,$&$0,$&$3,$&$0,$&$0,$&$0,$&$0,$&$2,$&$0$&$]$\\
+%%	\hline
+%%	$w$ & & $[$&$5,$&$3,$&$6,$&$8,$&$2,$&$10,$&$2,$&$7,$&$1,$&$4$&$]$\\
+%%\end{tabular}
+%
+%\end{center}
+%als Übertragungsvektor auf der Empfängerseite erhalten. 
+Wir jetzt als Empfänger wissen jedoch nicht, dass der erhaltene Übertragungsvektor jetzt fehlerbehaftet ist und werden dementsprechend den Ansatz aus Abschnitt \ref{reedsolomon:section:decohnefehler} anwenden.
+Wir stellen jedoch recht schnell fest, dass am decodierten Nachrichtenblock
 \[
-r = [\underbrace{5,7,4,10,}_{Fehlerinfo}5,4,5,7,6,7].
+r = [\underbrace{5,7,4,10,}_{\text{Syndrom}}5,4,5,7,6,7].
 \]
-Im Vergleich zum vorherigen Kapitel sind die Fehlerkorrekturstellen jetzt $\neq 0$, was bedeutet, dass wir diesen Übertragungsvektor fehlerhaft empfangen haben und sich die Nachricht jetzt nicht mehr so einfach decodieren lässt.
+etwas nicht in Ordnung ist, denn die vorderen vier Fehlerkorrekturstellen haben nicht mehr den Wert null.
+Der Nachrichtenblock weisst jetzt ein \em Syndrom \em auf, welches anzeigt, dass der Übertragungsvektor fehlerhaft empfangen wurde.
+% Old Text
+%Wenn wir den Übertragungsvektor jetzt Rücktransformieren wie im vorherigen Kapitel erhalten wir
+%\[
+%r = [\underbrace{5,7,4,10,}_{Fehlerinfo}5,4,5,7,6,7].
+%\]
+Jetzt stellt sich natürlich die Frage, wie wir daraus den ursprünglich gesendeten Nachrichtenvektor zurückerhalten sollen. Laut der Definition über die Funktionsweise eines Reed-Solomon-Codes können wir aus den Fehlerkorrekturstellen ein ``Lokatorpolynom'' berechnen, welches die Information enthält, welche stellen innerhalb des empfangenen Übertragungsvektors fehlerhaft sind.
 
-% warum wir die fehler suchen
-Da Reed-Solomon-Codes in der Lage sind, eine Nachricht aus weniger Stellen zu rekonstruieren als wir ursprünglich haben, so müssen wir nur die Fehlerhaften Stellen finden und eliminieren, damit wir unsere Nutzdaten rekonstruieren können.
-Damit stellt sich die Frage, wie wir die Fehlerstellen $e$ finden.
-Dafür wählen wir einen Primitiven Ansatz mit
-\begin{align}
-	m(X) & = 4X^5 + 7X^4 + 2X^3 + 5X^2 + 8X + 1 \\
-	r(X) & = 5X^9 + 7X^8 + 4X^7 + 10X^6 + 5X^5 + 4X^4 + 5X^3 + 7X^2 + 6X + 7 \\
-	e(X) & = r(X) - m(X).
-\end{align}
-Setzen wir jetzt unsere Einheitswurzel für $X$ ein, so erhalten wir
+\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 könnten wir $d$ berechnen mit
+\begin{center}
+\begin{tabular}{r c l}
+	$m(X)$ & $=$ & $4X^5 + 7X^4 + 2X^3 + 5X^2 + 8X + 1$ \\
+	$r(X)$ & $=$ & $5X^9 + 7X^8 + 4X^7 + 10X^6 + 5X^5 + 4X^4 + 5X^3 + 7X^2 + 6X + 7$ \\
+	$d(X)$ & $=$ & $r(X) - m(X)$.
+\end{tabular}
+\end{center}
+TODO (rewrite sentence): Dies wird uns zwar andere sorgen wegen $m(X)$ bereiten, \textcolor{red}{die werden wir jedoch zu einem späteren Zeitpunkt betrachten (todo: verweis auf kapitel?)}.
+Setzen wir jetzt noch unsere Einheitswurzel aus dem Beispiel ein so erhalten wir
+% Old Text
+%\begin{align}
+%	m(X) & = 4X^5 + 7X^4 + 2X^3 + 5X^2 + 8X + 1 \\
+%	r(X) & = 5X^9 + 7X^8 + 4X^7 + 10X^6 + 5X^5 + 4X^4 + 5X^3 + 7X^2 + 6X + 7 \\
+%	e(X) & = r(X) - m(X).
+%\end{align}
+%Setzen wir jetzt unsere Einheitswurzel für $X$ ein, so erhalten wir
 \begin{center}
 \begin{tabular}{c c c c c c c c c c c}
 	\hline
@@ -56,80 +113,137 @@ Setzen wir jetzt unsere Einheitswurzel für $X$ ein, so erhalten wir
 	\hline
 	$r(a^{i})$& $5$& $3$& $6$& $8$& $2$& $10$& $2$& $7$& $1$& $4$\\
 	$m(a^{i})$& $5$& $3$& $6$& $5$& $2$& $10$& $2$& $7$& $10$& $4$\\
-	$e(a^{i})$& $0$& $0$& $0$& $3$& $0$& $0$& $0$& $0$& $2$& $0$\\
+	$d(a^{i})$& $0$& $0$& $0$& $3$& $0$& $0$& $0$& $0$& $2$& $0$\\
 	\hline
 \end{tabular}
 \end{center}
-und damit die Information, dass an allen Stellen, die nicht Null sind, Fehler enthalten.
-Um jetzt alle nicht Nullstellen zu finden, wenden wir den Satz von Fermat an. 
+und damit die Information, dass allen Stellen, die nicht Null sind, Fehler enthalten. 
+Aus der Tabelle lesen wir, das in unserem Beispiel die Fehler an der Stelle drei und acht zu finden sind.
+
+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.
 
-\subsection{Der Satz von Fermat
-\label{reedsolomon:subsection:fermat}}
-Der Satz von Fermat besagt, dass für
+\subsection{Mit dem grössten gemeinsamen Teiler auf Nullstellenjagd
+\label{reedsolomon:subsection:ggT}}
+
+Zuerst betrachten wir mal den Satz von Fermat deren Funktionsweise wir in Abschnitt \ref{buch:section:galoiskoerper} kennengelernt haben. Der besagt, dass für
 \[
 f(X) = X^{q-1} -1 = 0
 \] 
-gilt, egal was wir für $q$ einsetzen.
-
-Für unser Beispiel erhalten wir
+wobei dies für jedes $q$ gilt. Setzen wir also das $q$ von unserem Beispiel ein
 \[
 f(X) = X^{10}-1 = 0 \qquad \text{für } X = \{1,2,3,4,5,6,7,8,9,10\}
 \]
-und können $f(X)$ auch umschreiben in
+und stellen dies als Nullstellenform (\textcolor{red}{richtiger name für die Schreibweise?}) dar. So ergibt sich die Darstellung 
 \[
 f(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).
 \]
 Zur Überprüfung können wir unsere Einheitswurzel in $a$ einsetzen und werden sehen, dass wir für $f(X) = 0$ erhalten werden.
-Nach der gleichen Überlegung können wir jetzt auch $e(X)$ darstellen als
+
+Wir können jetzt auch $d(X)$ nach der gleichen Überlegung darstellen als 
 \[
-e(X) = (X-a^0)(X-a^1)(X-a^2) \qquad \qquad (X-a^4)(X-a^5)(X-a^6)(X-a^7) \qquad \qquad (X-a^9) \cdot p(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) \cdot p(x),
 \]
-wobei $p(X)$ das Restpolynom ist und die Fehlerstellen beinhaltet.
-Wenn wir jetzt den grössten gemeinsamen Teiler von $f(X)$ und $e(X)$ berechnen, so erhalten wir mit
+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)$ (\textcolor{red}{eventuell farblich kennzeichnen?}) zusammen.
+Wenn wir jetzt den grössten gemeinsamen Teiler von $f(X)$ und $d(X)$ berechnen, so erhalten wir mit 
 \[
-\operatorname{ggT}(f(X),e(X)) = (X-a^0)(X-a^1)(X-a^2) \qquad \qquad (X-a^4)(X-a^5)(X-a^6)(X-a^7) \qquad \qquad (X-a^9)
+\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)
 \]
 eine Liste von Nullstellen, an denen es keine Fehler gegeben hat.
-Da wir uns jedoch für eine Liste mit Nullstellen interessieren, an denen es Fehler gegeben hat berechnen wir stattdessen das kgV von $f(X)$ und $e(X)$ als
+Dies scheint zuerst nicht sehr hilfreich zu sein, da wir für das Lokatorpolynom ja eine Liste der Nullstellen suchen, an denen es Fehler gegeben hat. Aus diesem Grund berechnen wir im nächsten Schritt das kleinste gemeinsame Vielfache von $f(X)$ und $d(X)$. 
+
+%Wir werden auch feststellen, das unsere Bemühungen bisher nicht umsonst waren.  
+
+\subsection{Mit dem kgV fehlerhafte Nullstellen finden
+	\label{reedsolomon:subsection:kgV}}
+
+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),e(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).
+\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).
 \]
-Wir können das Resultat noch zerlegen in
+ersichtlich ist.
+Aus dem vorherigen Abschnitt wissen wir auch, dass $d(X)$ alle korrekten Nullstellen beinhaltet. Teilen wir das kgV jetzt auf in 
 \[
-\operatorname{kgV}(f(X),e(X)) = d(X) \cdot e(X).
+\operatorname{kgV}(f(X),d(X)) = d(X) \cdot l(X)
 \]
-Somit muss $d(X)$ eine Liste von Nullstellen enthalten an denen es Fehler gegeben hat.
+sollten wir für $l(X)$ eine Liste mit allen fehlerhaften Nullstellen erhalten.
+Somit ist 
 \[
-d(X) = (X-a^3)(X-a^8)
+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ähren 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.
 
+\subsection{Der problematische Nachrichtenvektor $m(X)$
+	\label{reedsolomon:subsection:nachrichtenvektor}}
 
-und ist damit unser gesuchtes Lokatorpolynom.
-
-Das einzige Problem was jetzt noch bleibt ist, dass wir $e(X)$ berechnet haben aus
+In Abschnitt \ref{reedsolomon:section:decmitfehler} haben wir
 \[
-e(X) = r(X) - m(X),
+d(X) = r(X) - m(X)
 \]
-wobei $m(X)$ auf der Empfängerseite unbekannt ist.
-Es sieht danach aus, das wir diesen Lösungsansatz nicht verwenden können, da uns ein entscheidender Teil fehlt.
-Bei einer näheren Betrachtung von $m(X)$ fällt uns aber auf, dass wir doch etwas über $m(X)$ wissen.
-Wir kennen nämlich die ersten vier Stellen, da diese für die Fehlerkorrektur zuständig sind und daher Null sein müssen.
+in Abhängigkeit von $m(X)$ berechnet. 
+Jedoch haben wir ausser acht gelassen, dass $m(X)$ auf der Empfängerseite nicht existiert und somit gänzlich unbekannt ist.
+Es scheint so als würde dieser Lösungsansatz, den wir bisher verfolgt haben, nicht funktioniert.
+Wir könnten uns höchstens noch fragen, ob wir tatsächlich nichts über den Nachrichtenvektor im Beispiel wissen. Wenn wir noch einmal den Vektor betrachten als
 \[
-m = [0,0,0,0,?,?,?,?,?,?]
+m = [0,0,0,0,4,7,2,5,8,1]
 \]
-An genau diesen Stellen liegt auch die Information, wo unsere Fehlerstellen liegen, was uns ermöglicht, den Teil von $e(X)$ zu berechnen, der uns auch interessiert.
-
-Wir können $e(X)$ also bestimmen als
+fällt uns aber auf, dass wir doch etwas über diesen Vektor wissen, nämlich den Wert der ersten 2t (im Beispiel vier) stellen.
+Im Normalfall sollen diese nämlich den Wert null betragen und somit sind nur die letzten k stellen (im Beispiel sechs) für uns unbekannt, dargestellt als
 \[
-e(X) = 5X^9 + 7X^8 + 4X^7 + 10X^6 + p(X)
+m = [0,0,0,0,?,?,?,?,?,?].
 \]
-wobei $p(X)$ wiederum ein unbekanntes Restpolynom ist und
+Wie der Zufall es so will liegt an diesen vier Stellen auch die Information, wo die Fehlerstellen liegen. Daher reicht es auch aus
+% darum werden die stellen auch als fehlerkorrekturstellen bezeichnet
 \[
-f(X) = X^{10} - 1 = X^{10} + 10
+d(X) = 5X^9 + 7X^8 + 4X^7 + 10X^6 + p(X)
 \]
-ist können wir so in einer ersten Instanz den grössten gemeinsamen Teiler von $f(X)$ und $e(X)$ berechnen.
-Dafür nehmen wir uns wiederum den Euklidischen Algorithmus zur Hilfe und berechnen so
+so zu berechnen, dass wir die wichtigen vier Stellen kennen, der Rest des Polynoms jedoch im unbekannten Restpolynom $p(X)$ enthalten ist. 
+
+\textcolor{red}{ist das wechseln zwischen 2t,k aus dem allgemeinfall und vier,sechs aus dem beispiel zu verwirrend?}
+
+\subsection{Die Berechnung der Fehlerstellen
+	\label{reedsolomon:subsection:nachrichtenvektor}}
+
+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}
 
+Wir berechnen den ggT von $f(X)$ und $d(X)$ mit
+\begin{center}
+\begin{tabular}{r c l}
+	$f(X)$ & $=$ & $X^{10} - 1 = X^{10} + 10$ \\
+	$d(X)$ & $=$ & $5X^9 + 7X^8 + 4X^7 + 10X^6 + p(X)$
+\end{tabular}
+\end{center} 
+%
+%
+%
+%Das einzige Problem was jetzt noch bleibt ist, dass wir $e(X)$ berechnet haben aus
+%\[
+%e(X) = r(X) - m(X),
+%\]
+%wobei $m(X)$ auf der Empfängerseite unbekannt ist.
+%Es sieht danach aus, das wir diesen Lösungsansatz nicht verwenden können, da uns ein entscheidender Teil fehlt.
+%Bei einer näheren Betrachtung von $m(X)$ fällt uns aber auf, dass wir doch etwas über $m(X)$ wissen.
+%Wir kennen nämlich die ersten vier Stellen, da diese für die Fehlerkorrektur zuständig sind und daher Null sein müssen.
+%\[
+%m = [0,0,0,0,?,?,?,?,?,?]
+%\]
+%An genau diesen Stellen liegt auch die Information, wo unsere Fehlerstellen liegen, was uns ermöglicht, den Teil von $e(X)$ zu berechnen, der uns auch interessiert.
+%
+%Wir können $e(X)$ also bestimmen als
+%\[
+%e(X) = 5X^9 + 7X^8 + 4X^7 + 10X^6 + p(X)
+%\]
+%wobei $p(X)$ wiederum ein unbekanntes Restpolynom ist und
+%\[
+%f(X) = X^{10} - 1 = X^{10} + 10
+%\]
+%ist können wir so in einer ersten Instanz den grössten gemeinsamen Teiler von $f(X)$ und $e(X)$ berechnen.
+%Dafür nehmen wir uns wiederum den Euklidischen Algorithmus zur Hilfe und berechnen so
+%
 \[
 \arraycolsep=1.4pt
 \begin{array}{rcrcrcrcccrcrcrcrcrcrcrcrcr}
@@ -151,11 +265,16 @@ Dafür nehmen wir uns wiederum den Euklidischen Algorithmus zur Hilfe und berech
 \]
 und erhalten
 \[
-\operatorname{ggT}(f(X),e(X)) = 6X^8
+\operatorname{ggT}(f(X),e(X)) = 6X^8.
 \]
-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 ???. 
 
-Aus diesem erweiterten Euklidischen Algorithmus erhalten wir 
+\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 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 ???. 
+%
+%Aus diesem erweiterten Euklidischen Algorithmus erhalten wir 
 \begin{center}
 	
 	\begin{tabular}{| c | c | c c |}
@@ -170,28 +289,23 @@ Aus diesem erweiterten Euklidischen Algorithmus erhalten wir
 	\end{tabular}	
 	
 \end{center}
-und erhalten auf diesem Weg den Faktor
+Daraus erhalten wir die Faktoren
 \[
-d(X) = 2X^2 + 5,
+l(X) = 2X^2 + 5 \qquad \rightarrow \qquad l(X) = 2(X-5)(X-6).
 \]
-den wir in 
+Unser gesuchtes Lokatorpolynom hat also die Form
 \[
-d(X) = 2(X-5)(X-6)
+l(X) = (X-a^i)(X-a^j).
 \]
-zerlegen können.
-Da die unbekannten Stellen im Lokatorpolynom
-\[
-d(X) = (X-a^i)(X-a^i)
-\]
-sind, müssen wir nur noch $i$ berechnen als
+Also brauchen wir nur noch $i$ und $j$ zu berechnen und wir haben unsere gesuchten Fehlerstellen.
+Diese bekommen wir recht einfach mit
 \begin{center}
 	$a^i = 5 \qquad \Rightarrow \qquad i = 3$
 	
-	$a^i = 6 \qquad \Rightarrow \qquad i = 8$.
+	$a^j = 6 \qquad \Rightarrow \qquad j = 8$.
 \end{center}
-
-Somit erhalten wir schliesslich
+Schlussendlich erhalten wir
 \[
 d(X) = (X-a^3)(X-a^8)
 \]
-als unser Lokatorpolynom mit den Fehlerhaften Stellen.
\ No newline at end of file
+als unser Lokatorpolynom mit den fehlerhaften Stellen.
-- 
cgit v1.2.1


From d15eaa234f3f1622289e2486db54fe0ce7309b8f Mon Sep 17 00:00:00 2001
From: michael-OST <75078383+michael-OST@users.noreply.github.com>
Date: Thu, 10 Jun 2021 18:22:35 +0200
Subject: nachschlagewerk created

---
 buch/papers/reedsolomon/decmitfehler.tex | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

(limited to 'buch/papers/reedsolomon/decmitfehler.tex')

diff --git a/buch/papers/reedsolomon/decmitfehler.tex b/buch/papers/reedsolomon/decmitfehler.tex
index db6e586..feaa027 100644
--- a/buch/papers/reedsolomon/decmitfehler.tex
+++ b/buch/papers/reedsolomon/decmitfehler.tex
@@ -97,7 +97,8 @@ Bevor wir unser Lokatorpolynom berechnen können, müssen wir zuerst eine Mögli
 	$d(X)$ & $=$ & $r(X) - m(X)$.
 \end{tabular}
 \end{center}
-TODO (rewrite sentence): Dies wird uns zwar andere sorgen wegen $m(X)$ bereiten, \textcolor{red}{die werden wir jedoch zu einem späteren Zeitpunkt betrachten (todo: verweis auf kapitel?)}.
+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 noch unsere Einheitswurzel aus dem Beispiel ein so erhalten wir
 % Old Text
 %\begin{align}
-- 
cgit v1.2.1

