diff options
author | Andreas Müller <andreas.mueller@ost.ch> | 2021-07-17 12:43:47 +0200 |
---|---|---|
committer | GitHub <noreply@github.com> | 2021-07-17 12:43:47 +0200 |
commit | 6a51c847855ef6e62aee94475b5657e8c37e7511 (patch) | |
tree | 225917f4859e3e0febfa9d65d92a2ba096d1f448 /buch/papers/reedsolomon/idee.tex | |
parent | Merge pull request #35 from Malarius1999/master (diff) | |
parent | start first rows (diff) | |
download | SeminarMatrizen-6a51c847855ef6e62aee94475b5657e8c37e7511.tar.gz SeminarMatrizen-6a51c847855ef6e62aee94475b5657e8c37e7511.zip |
Merge pull request #37 from JODBaer/Baer
Baer erste zeilen
Diffstat (limited to 'buch/papers/reedsolomon/idee.tex')
-rw-r--r-- | buch/papers/reedsolomon/idee.tex | 58 |
1 files changed, 58 insertions, 0 deletions
diff --git a/buch/papers/reedsolomon/idee.tex b/buch/papers/reedsolomon/idee.tex new file mode 100644 index 0000000..4a7716a --- /dev/null +++ b/buch/papers/reedsolomon/idee.tex @@ -0,0 +1,58 @@ +% +% 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 erkenen, +man kann sogar einige Fehler korrigieren. + +\rhead{Polynom-Ansatz} +Eine Idee ist die Daten, +ein Polynom zu bilden und dieses dann mit bestimmten Punkten ü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) += +2x^2 + 1x + 5 +\label{reedsolomon:equation1} +\end{equation} +ergeben. +Übertragen werden nun die stellen 1, 2, 3\dots 7 dieses Polynomes. +Grafisch sieht man dies dann im Abbild //TODO +Wenn ein Fehler sich in die Übertragung eingeschlichen hatt, muss der Leser/Empfänger erkennen, welches das Richtige Polynom ist. +Der Leser/Empfänger weiss, mit welchem Grad das Polynom entwickelt wurde. +\subsection{Beispiel} +Für das Beispeil aus der Gleichung \ref{reedsolomon:equation1}, +ist ein Polynome zweiten Grades durch drei Punkte eindeutig bestimmbar. +Hat es Fehler in der Übertragunge gegeben, kann man diese erkennen, +da alle Punkte, die korrekt sind, auf dem Polynom liegen müssen. +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. +Werden es mehr Fehler kann nur erkennt werden das das Polynom nicht stimmt. +Das Orginale Polynom kann aber nicht mehr gefunden werden. +Dabei sollten mehr Übertragungspunkte gegeben werden. + +\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. +Durch ein klein wenig Überlegung ist klar das die anzahl Zahlen (Daten, ab hier verwenden wir das Wort Nutzlast), +die dan Entschlüsselt werden sollen den Grad des Polynoms minus 1 ergeben. +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, +für das Übertragen $$k+2t$$ Punkte gegben werden müssen. + +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*2 = 4 $$ Punkten falsch liegen +und es wird kein eindeutiges Polynom 2ten Grades erkannt, und somit die Nutzlast Daten als fehlerhaft deklariert. + +Ein Polynom durch Punkt mit Polynom Interpolation zu rekonstruieren ist schwierig und Fehleranfällig. + |