diff options
Diffstat (limited to '')
| -rw-r--r-- | buch/papers/reedsolomon/idee.tex | 88 |
1 files changed, 88 insertions, 0 deletions
diff --git a/buch/papers/reedsolomon/idee.tex b/buch/papers/reedsolomon/idee.tex new file mode 100644 index 0000000..39adbbf --- /dev/null +++ b/buch/papers/reedsolomon/idee.tex @@ -0,0 +1,88 @@ +% +% teil1.tex -- Beispiel-File für das Paper +% +% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil +% +\section{Idee +\label{reedsolomon:section:idee}} +\rhead{Problemstellung} +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. + +\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 +\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. + +\begin{figure} + \centering + %\includegraphics[width=0.5\textwidth]{papers/reedsolomon/images/polynom2} + \input{papers/reedsolomon/images/polynom2.tex} + \caption{Polynom $p(x)$ \eqref{reedsolomon:equation1}} + \label{fig:polynom} +\end{figure} + +\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 } + \hline + Nutzlas & Fehler & Übertragen \\ + \hline + 3 & 2 & 7 Werte eines Polynoms vom Grad 2 \\ + 4 & 2 & 8 Werte eines Polynoms vom Grad 3 \\ + 3 & 3 & 9 Werte eines Polynoms vom Grad 2 \\ + \hline + $k$ & $t$ & $k+2t$ Werte eines Polynoms vom Grad $k-1$ \\ + \hline + \end{tabular} +\end{center} + +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. + |