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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
|
%
% idee.tex -- Polynom Idee
%
\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.
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.
\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.
\begin{beispiel} Nehmen wir 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 \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}
\begin{figure}%[!ht]
\centering
%\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}
\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.
\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}
\centering
\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}
\caption{ Fehlerkorrekturstellen Bestimmung.}
\label{tab:fehlerkorrekturstellen}
\end{table}
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.
|
