1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
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.
|
