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
112
113
114
115
116
117
118
119
|
%
% 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 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 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}.
\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 Bei \textit{1 Fehler} können konkurrenzierende 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 Bei \textit{2 Fehlern} kann ein Fehler mit zwei originalen Punkten ein Konkurrenzpolynom bilden.
Da der zweite Fehler frei wählbar ist, kann dieser auch auf dem Konkurrenzpolynom liegen, wie in der Abbilbung \ref{fig:polynom}.
Nun haben wir, ein originales Polynom mit 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 Bei \textit{3 Fehlern} 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 Bei \textit{4 Fehlern} Es kann 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 Bei \textit{5 Fehler} Mit den 2 originalen Punkte kann 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}%[!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}
\qedhere
\end{beispiel}
\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 \textcolor{blue}{Datenwerte}, ergeben die Anzahl Polynomkoeffizente $k$ und somit den Grad $k-1$.
Die Bestimmung der Anzahl der Fehler $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
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}
Es müssen mehr Punkte auf dem \textcolor{blue}{originalen Polynom} liegen, als auf dem konkurenzierenden.
Somit braucht man für die Übertragung pro Fehler zwei Übertragungspunkte mehr.
Wie in der Tabelle ergibt sich diese Übertragungsanzahl
\begin{equation}
\textcolor{darkgreen}{u}=
\textcolor{blue}{k}+2\textcolor{red}{t}.
\label{reedsolomon:equation2}
\end{equation}
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.
|
