diff options
Diffstat (limited to 'buch/papers/reedsolomon/idee.tex')
| -rw-r--r-- | buch/papers/reedsolomon/idee.tex | 148 |
1 files changed, 90 insertions, 58 deletions
diff --git a/buch/papers/reedsolomon/idee.tex b/buch/papers/reedsolomon/idee.tex index 39adbbf..6ee42ef 100644 --- a/buch/papers/reedsolomon/idee.tex +++ b/buch/papers/reedsolomon/idee.tex @@ -1,72 +1,94 @@ % -% teil1.tex -- Beispiel-File für das Paper -% -% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil +% idee.tex -- Polynom Idee % \section{Idee \label{reedsolomon:section:idee}} \rhead{Problemstellung} +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. Das Problem liegt darin Informationen, Zahlen, -zu Übertragen und Fehler zu erkennen. -Beim Reed-Solomon-Code kann man nicht nur Fehler erkennen, -man kann sogar einige Fehler korrigieren. + 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, ausrechnet und diese Punkte dann überträgt. -Nehmen wir als beisbiel die Zahlen \textcolor{blue}{2}, \textcolor{blue}{1}, \textcolor{blue}{5}, -welche uns dann das Polynom +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 ü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. -Übertragen werden nun die Werte 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{green}{8}, -\textcolor{green}{15}, \textcolor{green}{26}, -\textcolor{green}{41}, \textcolor{green}{60}, -\textcolor{green}{83}, \textcolor{green}{110})$ -Wenn ein Fehler sich in die Übertragung eingeschlichen hatt, muss der Leser/Empfänger diesen erkennen und das Polynom rekonstruieren. -Der Leser/Empfänger weiss, den Grad des Polynoms und dessen Werte übermittelt wurden. - -\subsection{Beispiel} -Für das Beispeil aus der Gleichung \eqref{reedsolomon:equation1}, -ist ein Polynome zweiten Grades durch drei Punkte eindeutig bestimmbar. -Hat es Fehler in der Übertragunge gegeben,(Bei Abbildung \ref{fig:polynom}\textcolor{red}{roten Punkte}) kann man diese erkennen, -da alle Punkte, die korrekt sind, auf dem Polynom liegen müssen. -(Bei Abbildung \ref{fig:polynom}\textcolor{green}{grünen Punkte}) -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 erkennt werden, dass das Polynom nicht stimmt. -Das orginale Polynom kann aber nicht mehr gefunden werden. -Dafür sind mehr übertragene Werte nötig. +\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. +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} +\begin{figure}%[!ht] \centering - %\includegraphics[width=0.5\textwidth]{papers/reedsolomon/images/polynom2} - \input{papers/reedsolomon/images/polynom2.tex} - \caption{Polynom $p(x)$ \eqref{reedsolomon:equation1}} + %\includegraphics[width=\textwidth]{papers/reedsolomon/figures/polynom2} + \input{papers/reedsolomon/tikz/polynomraw.tex} + \caption{Polynom $p(x)$ von der Gleichung\eqref{reedsolomon:equation1}} \label{fig:polynom} \end{figure} +\qedhere +\end{beispiel} -\section{Fehlerbestimmung -\label{reedsolomon:section:Fehlerbestimmmung}} -So wird ein Muster indentifiziert, welches genau vorherbestimmen kann, -wie gross das Polynom sein muss und wie viele Übertragungspunkte gegeben werden müssen. -Um zu bestimmen wie viel Fehler erkennt und korriegiert werden können. -Die Anzahl Zahlen (Daten, ab hier verwenden wir das Wort Nutzlast), -die Entschlüsselt werden sollen, brauchen die gleiche Anzahl an Polynomgraden, beginnend bei Grad 0. ( \( k-1 \) ) -Für die Anzahl an Übertragungspunkte, muss bestimmt werden wieviel Fehler erkennt und korrigiert werden sollen. -Mit Hilfe der Tabelle, sieht man das es bei $t$ Fehlern und $k$ Nutzlast Zahlen, -$k+2t$ Punkte übertragen werden müssen. - -\begin{center} - \begin{tabular}{ c c c } +\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 Nutzlas & Fehler & Übertragen \\ \hline @@ -77,12 +99,22 @@ $k+2t$ Punkte übertragen werden müssen. $k$ & $t$ & $k+2t$ Werte eines Polynoms vom Grad $k-1$ \\ \hline \end{tabular} -\end{center} + \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 toller Nebeneffekt ist das dadurch auch $2t$ Fehler erkannt werden. -Um zurück auf unser Beispiel zu kommen, -können von den 7 Übertragungspunkten bis zu $2t = 2\cdot2 = 4 $ Punkten falsch liegen -und es wird kein eindeutiges Polynom zweiten Grades erkannt, und somit die Nutzlast Daten als fehlerhaft deklariert. -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. |