aboutsummaryrefslogtreecommitdiffstats
path: root/buch/papers/reedsolomon/idee.tex
diff options
context:
space:
mode:
Diffstat (limited to 'buch/papers/reedsolomon/idee.tex')
-rw-r--r--buch/papers/reedsolomon/idee.tex96
1 files changed, 57 insertions, 39 deletions
diff --git a/buch/papers/reedsolomon/idee.tex b/buch/papers/reedsolomon/idee.tex
index 7620df1..c071b5e 100644
--- a/buch/papers/reedsolomon/idee.tex
+++ b/buch/papers/reedsolomon/idee.tex
@@ -5,60 +5,78 @@
\label{reedsolomon:section:idee}}
\rhead{Problemstellung}
Um beim Datenübertragen Fehler zu erkennen, könnte man die Daten jeweils doppelt senden,
-und so jeweilige Fehler zu erkennen.
+ also immer zwei gleich Werte miteinander und so jeweilige einen Fehler zu erkennen.
+Wenn jedoch mehr als nur ein Fehler erkennt werden soll und sogar noch das orginal rekonstruiert werden soll,
+dann werden die Daten drei oder vierfach versendet.
Doch nur schon um Fehler zu erkennen werden überproportional viele Daten doppelt und dreifach gesendet.
-Der Reed-Solomon-Code macht dies auf eine andere, clevere Weise.
Das Problem liegt darin Informationen, Zahlen,
-zu Übertragen und Fehler zu erkennen.
+ zu Übertragen und Fehler zu erkennen.
Speziell beim Reed-Solomon-Code kann man nicht nur Fehler erkennen,
-man kann sogar einige Fehler korrigieren.
+ man kann sogar einige Fehler korrigieren.
Der Unterschied des Fehler erkennen und korrigiren, ist das beim Erkennen nur die Frage beantwortet wird: Ist die Übertragung fehlerhaft oder nicht?
Beim Korrigieren werden Fehler erkannt und dann zusätzlich noch den original Wert rekonstruieren.
-Auch eine Variante wäre die Daten nach einer Fehlerhaften sendung, nochmals zum senden auffordern(auch hier wird doppelt und dreifach gesendung),
-was bei Reed-Solomon-Code-Anwendungen nicht immer sinnvoll ist.
+Der Reed-Solomon-Code macht dies auf eine andere, clevere Weise.
Anwendungen finden sind im Abschnitt \externaldocument{papers/reedsolomon/anwendungen}
\ref{reedsolomon:section:anwendung} beschrieben.
\subsection{Polynom-Ansatz
\label{reedsolomon:section:polynomansatz}}
\rhead{Polynom-Ansatz}
-Eine Idee ist, aus den Daten ein Polynom zu bilden.
-Diese Polynomfunktion bei bestimmten Werten errechnet und diese Punkte dann überträgt.
-\begin{beispiel} Nehmen wir die Zahlen \textcolor{blue}{2}, \textcolor{blue}{1}, \textcolor{blue}{5},
-welche uns dann das Polynom
+Eine Idee ist, aus den Daten ein Polynom zu bilden.
+In deieser Art arbeitet der Reed-Solomon-Code.
+Von dieser Polynomfunktion wird dann eine Anzahl Werte übertragen.
+\begin{beispiel} Nehmen wir zum Beispiel die Zahlen \textcolor{blue}{2}, \textcolor{blue}{1}, \textcolor{blue}{5},
+ welche uns dann das Polynom
\begin{equation}
p(x)
=
\textcolor{blue}{2}x^2 + \textcolor{blue}{1}x + \textcolor{blue}{5}
\label{reedsolomon:equation1}
\end{equation}
-ergeben.
+ergibt.
+\par
+Ein Polynome zweiten Grades ist durch drei Punkte eindeutig bestimmbar.
+Bei einer fehlerlosen Übertragung, können wir mit 3 übertragene Werte,
+ das Polynom durch Polynominterpolation volständig rekonstruieren.
+Weder erkläre noch erläutere ich die Polynominterpolation,
+ sie kann nachgeschaut werden oder als Funktion angewendet werden.
+Die koeffizente, des rekonstruierten Polynoms, sind dann unsere gesendten Zahlen \textcolor{blue}{2}, \textcolor{blue}{1}, \textcolor{blue}{5}.
+Wie können wir nun Fehler erkennen oder sogar korrigieren?
+Versuchen wir doch mehr Werte zu Übertragen, wir nehmen im Beispiel 7 Werte.
Übertragen werden nun die \textcolor{darkgreen}{grünen Werte}
-dieses \textcolor{blue}{blauen Polynomes} an den Stellen 1, 2, 3\dots 7 dieses Polynomes.
+ dieses 7 Werte \textcolor{blue}{blauen Polynomes} an den Stellen 1, 2, 3\dots 7 dieses Polynomes.
Grafisch sieht man dies dann in Abbildung \ref{fig:polynom},
-mit den Punkten, $p(1),p(2),...,p(7) = (\textcolor{darkgreen}{8},
-\textcolor{darkgreen}{15}, \textcolor{darkgreen}{26},
-\textcolor{darkgreen}{41}, \textcolor{darkgreen}{60},
-\textcolor{darkgreen}{83}, \textcolor{darkgreen}{110})$
-Wenn ein Fehler sich in die Übertragung eingeschlichen hat, muss der Leser/Empfänger diesen erkennen und das Polynom rekonstruieren.
-Der Leser/Empfänger weiss, den Grad des Polynoms und dessen \textcolor{darkgreen}{Werte} übermittelt wurden.
-Die Farbe blau brauchen wir für die \textcolor{blue}{Daten} welche wir mit der Farbe grün \textcolor{darkgreen}{Übermitteln}.
-\end{beispiel}
-
-\begin{beispiel}
-Ein Polynome zweiten Grades ist durch drei Punkte eindeutig bestimmbar.
-Hat es Fehler in der Übertragunge gegeben,in der Abbilbung \ref{fig:polynom} die \textcolor{red}{roten Punkte}).
-Erkennt man diese Fehler, da alle korrekten Punkte auf der Parabel liegen müssen.
-Die \textcolor{darkgreen}{grünen Punkte} bestimmen die Parabel, und die Fehler können zu den
-\textcolor{gray}{Orginalpunkte} rekonstruiert werden.
-Ab wie vielen Fehler ist das Polynom nicht mehr erkennbar beim Übertragen von 7 Punkten?
-Bei 2 Fehlern kann man noch eindeutig bestimmen, dass das Polynom mit 4 Punkten,
-gegenüber dem mit 5 Punkten falsch liegt. \ref{fig:polynom}
-Werden es mehr Fehler kann nur erkannt werden, dass das Polynom nicht stimmt.
-Das orginale Polynom kann aber nicht mehr gefunden werden.
-Da andere Polynome oder das Konkurrenzpolynom, grau gestrichelt in Abbildung \ref{fig:polynom}, das orginal fehlleitet.
-Um das Konkurrenzpolynom auszuschliessen, währen mehr \textcolor{darkgreen}{Übertragungspunkte} nötig.
-\end{beispiel}
+ mit den Punkten, $p(1),p(2),...,p(7) = (\textcolor{darkgreen}{8},
+ \textcolor{darkgreen}{15}, \textcolor{darkgreen}{26},
+ \textcolor{darkgreen}{41}, \textcolor{darkgreen}{60},
+ \textcolor{darkgreen}{83}, \textcolor{darkgreen}{110})$
+Nun wird durch drei der 7 Punkte das Polynom eindeutig bestimmbar und
+ alle anderen müssen auf diesem Polynom liegen.
+Dabei gingen wir von keinem Fehler aus,
+ hat es Fehler in der Übertragunge gegeben.
+Wir erhöhen nun die Fehleranzahl Schritt für Schritt:
+\begin{enumerate}
+ \item \textit{Fehler} können konkurenzierende Polynome, zusammen mit zwei originalen Punkten fehlleiten.
+ Dabei kann aber maximal 3 Punkte auf diesem Konkurrenzpolynom sein,
+ ansonsten ist der Fehler ein Orginalpunkt und somit kein Fehler.
+ Da 6 übereinstimende grössser als 3 ist haben wir unser original Polynom gefunden.
+ \par Orginal mit 6 Punkte > 3 Punkte Konkurrenzpolynom, Original Polynom gefunden
+ Damit ist klar das unser Polynom mit 6 Punkten richtig ist und unser Fehler kann rekonstruiert werden.
+ \item \textit{Fehler} kann ein Fehler mit zwei originalen Punkten ein fehlleitendes Konkurrenzpolynom bilden.
+ Da der zweite Fehler frei wählbar ist kann dieser auch auf dem Konkurrenzpolynom liegen, wie in der Abbilbung \ref{fig:polynom}.
+ Nun haben wir, wie in unserer Grafik \ref{fig:polynom}, ein Polynom mit 5 übereinstimmenden und eines mit 4 Punkten.
+ Da 5 noch grösser als 4 ist, können wir sagen welches das original Polynom ist.
+ \par Orginal mit 5 Punkte > 4 Punkte Konkurrenzpolynom, Original Polynom gefunden
+ \item \textit{Fehler} kann genau wie bei 2 Fehler, ein Fehler ein fehlleitendes Polynom mit 2 original Punkten bestimmen werden.
+ Auch hier sind die anderen Fehler frei wählbar und liegen auf dem Konkurrenzpolynom.
+ Nun ist es so das 5 Punkte auf diesem konkurenzierenden Polynom und 4 Punkte auf dem Originalen.
+ Das Original Polynom kann nicht mehr gefunden werden.
+ \par Orginal mit 5 Punkte > 4 Punkte Konkurrenzpolynom, Original Polynom nicht gefunden
+ \item \textit{Fehler} Es kann noch erkennt weden das Fehler statt gefunden haben, da 3 orginale Punkte das ursprüngliche Polynom ergeben.
+ Somit haben wir mindestens 2 verschieden Polynome, dass bedeutet Fehler sind entstanden.
+ \item \textit{Fehler} Mit den 2 originalen Punkte kann das Originale Polynom nicht mehr erkannt werden und
+ somit auch keine Aussgae gemacht werden ob Fehler statt gefunden haben oder nicht.
+\end{enumerate}
\begin{figure}%[!ht]
\centering
@@ -71,13 +89,13 @@ Um das Konkurrenzpolynom auszuschliessen, währen mehr \textcolor{darkgreen}{Üb
\section{Fehlerkorekturstellen bestimmen
\label{reedsolomon:section:Fehlerkorrekturstellen}}
Um zu bestimmen wieviel zusätzliche \textcolor{darkgreen}{Übertragungspunkte} notwendig sind, um die Fehler zu korrigieren,
-muss man zuerst wissen, wieviel \textcolor{blue}{Daten} gesendet und wieviel \textcolor{red}{Fehler} erkennt werden sollen.
+ muss man zuerst wissen, wieviel \textcolor{blue}{Daten} gesendet und wieviel \textcolor{red}{Fehler} erkennt werden sollen.
Die Anzahl \textcolor{blue}{Daten} (ab hier verwenden wir das Wort Nutzlast), die als Polynomkoeffizente $k$ übergeben werden,
-brauchen die gleiche Anzahl an Polynomkoeffizententräger, beginnend bei Grad 0 somit ergibt sich der Polynomgrad mit $k-1$.
+ brauchen die gleiche Anzahl an Polynomkoeffizententräger, beginnend bei Grad 0 somit ergibt sich der Polynomgrad mit $k-1$.
Für die Anzahl der Fehler $t$, welche korrigiert werden können, gehen wir zum Beispiel.
\begin{beispiel} von den Polynom \ref{reedsolomon:equation1} in, welchem wir \textcolor{darkgreen}{7 Übertragungspunkte} senden.
Durch 3 Punkte wird das Polyom eindeutig bestimmt, nun haben wir mehrere Konkurrenzpolynome, doch mit maximal 2 Fehler liegen auf einem Konkurrenzpolynom,
-maximal 4 Punkte und auf unserem orginal 5 Punkte. Ansonsten hatt es mehr Fehler oder unser Konkurrenzpolynom ist das gleiche wie das Original.
+ maximal 4 Punkte und auf unserem orginal 5 Punkte. Ansonsten hatt es mehr Fehler oder unser Konkurrenzpolynom ist das gleiche wie das Original.
Somit können wir nun bestimmen, dass von den \textcolor{darkgreen}{7 Übertragungspunkten$u$} bis zu 2 Fehler korrigiert werden können und 4 Übertragungspunkte zusätzlich gesendet werden müssen.
\end{beispiel}
Man könnte auch dies in der Tabelle \ref{tab:fehlerkorrekturstellen} erkennen, doch mit dieser Gleichung
@@ -86,7 +104,7 @@ Man könnte auch dies in der Tabelle \ref{tab:fehlerkorrekturstellen} erkennen,
=2
\label{reedsolomon:equation2}
\end{equation}
-zeigt sich, dass es $k+2t$ Übertragungspunkte braucht.
+ zeigt sich, dass es $k+2t$ Übertragungspunkte braucht.
\begin{table}
\centering