diff options
Diffstat (limited to 'buch/papers/reedsolomon/idee.tex')
| -rw-r--r-- | buch/papers/reedsolomon/idee.tex | 139 |
1 files changed, 74 insertions, 65 deletions
diff --git a/buch/papers/reedsolomon/idee.tex b/buch/papers/reedsolomon/idee.tex index 41e0d4c..6ee42ef 100644 --- a/buch/papers/reedsolomon/idee.tex +++ b/buch/papers/reedsolomon/idee.tex @@ -4,61 +4,69 @@ \section{Idee \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. +Um Fehler in einer Datenübertragung zu erkennen, könnte man die Daten jeweils doppelt senden, + also immer zwei gleich Werte miteinander und so jeweils einzelne Fehler erkennen. +Wenn jedoch mehr als nur ein Fehler erkannt 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. -Speziell beim Reed-Solomon-Code kann man nicht nur Fehler erkennen, -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. -Anwendungen finden sind im Abchnitt \externaldocument{papers/reedsolomon/anwendungen} -\ref{reedsolomon:section:anwendung} beschrieben. + zu Übertragen und Fehler zu erkennen und zu korrigieren. +Der Unterschied des Fehler Erkennens und Korrigirens, 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 die Originalwerte rekonstruiert. +Eine weitere Möglichkeit wäre, dass der Empfänger nach einer fehlerhaften Übertragung die selben Daten nochmals anfordert. +Dies führt wieder zu unerwünschten mehrfachen Übertragung. +In Anwendungen des Reed-Solomon-Codes Abschnitt \externaldocument{papers/reedsolomon/anwendungen} \ref{reedsolomon:section:anwendung} + ist diese vom Empfänger gesteuerte erneute Übertragen meistens nicht sinnvoll oder sogar unmöglich. +Der Reed-Solomon-Code macht dies Übertragung auf eine andere, clevere Weise. \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. +Eine zentrale Idee des Reed-Solomon-Code ist, aus den Daten ein Polynom zu bilden. +Von dieser Polynomfunktion wird dann eine Anzahl Werte übertragen. \begin{beispiel} Nehmen wir die Zahlen \textcolor{blue}{2}, \textcolor{blue}{1}, \textcolor{blue}{5}, -welche uns dann das Polynom + welche übertragen werden sollen. Daraus bilden wir das Polynom \begin{equation} p(x) = \textcolor{blue}{2}x^2 + \textcolor{blue}{1}x + \textcolor{blue}{5} \label{reedsolomon:equation1} -\end{equation} -ergeben. +\end{equation}. +\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. +Wir brauchen Polynominterpolation als Methode, um aus Punkte wieder Polynom zu berechnen. +Die Koeffizente des rekonstruierten Polynoms sind dann unsere gesendeten Zahlen \textcolor{blue}{2}, \textcolor{blue}{1}, \textcolor{blue}{5}. +\par +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. -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} + dieses \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. +Die grünen Punkte bestimmen die Parabel. +Damit können die Fehler erkannt werden, weil die empfangenen Punkte nicht auf der Parabel liegen. +Somit können die grauen Punkte auf der Parabel ersetzt werden und sind damit korrigiert. +Bis zu wievielen Fehler können wir nun im Beispiel korrigieren? +Wir erhöhen nun 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 3 Punkte auf diesem Konkurrenzpolynom sein. + Da 6 > 3 ist haben wir unser original 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}. + Nun haben wir, ein \textcolor{blue}{originales Polynom} mit \textcolor{darkgreen}{5} übereinstimmenden und eine konkurrenzierendes mit 4 Punkten. + Da 5 noch grösser als 4 ist, können wir sagen, welches das Originalpolynom ist. + \item[\textit{3 Fehler}:] Bei Drei kann genau wie bei 2 oder 1 Fehler, ein konkurenzierendes Polynom mit einem Fehler und zwei originalen 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 Originalpolynom kann nicht mehr gefunden werden. + \item[\textit{4 Fehler}:] Bei Vier, kann es noch erkannt werden, dass 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{5 Fehler}] Bei Fünf, kann mit den 2 originalen Punkte das Originale Polynom nicht mehr erkannt werden und + somit auch keine Aussgae gemacht werden ob Fehler statt gefunden haben oder nicht. +\end{itemize} \begin{figure}%[!ht] \centering @@ -67,28 +75,18 @@ Um das Konkurrenzpolynom auszuschliessen, währen mehr \textcolor{darkgreen}{Üb \caption{Polynom $p(x)$ von der Gleichung\eqref{reedsolomon:equation1}} \label{fig:polynom} \end{figure} - -\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. -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$. -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. -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. +\qedhere \end{beispiel} -Man könnte auch dies in der Tabelle \ref{tab:fehlerkorrekturstellen} erkennen, doch mit dieser Gleichung -\begin{equation} - \frac{\textcolor{darkgreen}{u}-\textcolor{blue}{k}}{\textcolor{red}{t}} - =2 - \label{reedsolomon:equation2} -\end{equation} -zeigt sich, dass es $k+2t$ Übertragungspunkte braucht. -\begin{table} +\section{Anzahl Übertragungswerte 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}{Datenwerte} gesendet und wieviel \textcolor{red}{Fehler} erkennt werden sollen. +Die Anzahl Datenwerte, ergeben die Anzahl Polynomkoeffizente \textcolor{blue}{$k$} und somit den Grad $k-1$. +Die Bestimmung der Anzahl der Fehler \textcolor{red}{$t$}, welche korrigiert werden können, braucht Redundanz. +Gehen wir die Fehleranzahl mit verschiedenen Übertragungsanzahlen durch, + erkennt man almählich ein Muster. +\begin{table}%[!ht] \centering \begin{tabular}{ c c | c} \hline @@ -104,8 +102,19 @@ zeigt sich, dass es $k+2t$ Übertragungspunkte braucht. \caption{ Fehlerkorrekturstellen Bestimmung.} \label{tab:fehlerkorrekturstellen} \end{table} +\par +Es müssen mehr Punkte auf dem \textcolor{blue}{originalen Polynom} liegen, als auf dem konkurenzierenden. +Somit braucht man für die Übertragung pro \textcolor{red}{Fehler} zwei Übertragungspunkte mehr. +Wie in der Tabelle ergibt sich diese \textcolor{darkgreen}{Übertragungsanzahl} +\begin{equation} + \textcolor{darkgreen}{u}= + \textcolor{blue}{k}+2\textcolor{red}{t}. + \label{reedsolomon:equation2} +\end{equation} -Ein Nebeneffekt ist, dass dadurch auch $2t$ Fehler erkannt werden können, nicht aber korrigiert. -Um aus den übertragenen Zahlen wieder die Nutzlastzahlen zu bekommen könnte man eine Polynominterpolation anwenden, -doch die Punkte mit Polynominterpolation zu einem Polynom zu rekonstruieren ist schwierig und fehleranfällig. +Ein Nebeneffekt ist, dass auch $2t$ Fehler erkannt werden können, nicht aber korrigiert. +Für die Polynomkoeffizente nach der Übertragung zu rekonstruieren, + haben wir jedes mal die Polynominterpolationmethode angewendet. +Diese Polynoiminterpolation ist leider schwierig und fehleranfällig. +Deshalb finden wir eine alternative im nächsten Abschnitt. |