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
|
%
% 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 jeweilige einzelne Fehler erkennen.
Wenn jedoch mehr als nur ein Fehler erkennt 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 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.
Eine weitere Möglichkeit wäre, dass der Empfänger nach einer fehlerhaften Übertragung die selben Daten nochmals auffordert.
Dies führt wieder zu unerwünschten mehrfach Übertragung.
In Anwendungen des Reed-Soöomon-Code \externaldocument{papers/reedsolomon/anwendungen} \ref{reedsolomon:section:anwendung}
ist dies 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.
Weder erkläre noch erläutere ich die Polynominterpolation,
wir brauchen sie als Funktion, die von Punktn ein Polynom errechnet.
Die koeffizente, des rekonstruierten Polynoms, sind dann unsere gesendten Zahlen \textcolor{blue}{2}, \textcolor{blue}{1}, \textcolor{blue}{5}.
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 7 Werte \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}{übertragene Werte} des Polynoms sind grün.
Die grünen Punkte bestimmen die Parabel.
Damit können die Fehler erkannt werden, weil die empfangenen Punktenicht auf der Parabel liegen.
Somit könnendie grauen Punkte auf der Parabel ersetzt werden und sind damit korrigiert.
bis zu wivielen Fehler können wir nun korrigieren im Beispiel korrigieren?
Wir erhöhen nun die Fehleranzahl Schritt für Schritt:
\begin{itemize}
\item Bei \textit{1 Fehler} können konkurenzierende Polynome, zusammen mit zwei originalen Punkten fehlleiten.
Dabei kann aber maximal 3 Punkte auf diesem Konkurrenzpolynom sein.
Da 6 übereinstimende grössser als 3 ist haben wir unser original Polynom gefunden.
\item Bei \textit{2 Fehler} kann ein Fehler mit zwei originalen Punkten ein fehlleitendes 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 originles Polynom mit 5 übereinstimmenden und eine konkurrenzierendes mit 4 Punkten.
Da 5 noch grösser als 4 ist, können wir sagen, welches das original Polynom ist.
\item Bei \textit{3 Fehler} kann genau wie bei 2 Fehler, ein Fehler ein fehlleitendes Polynom mit 2 original 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 Original Polynom kann nicht mehr gefunden werden.
\item Bei \textit{4 Fehler} Es kann noch erkennt weden das 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}
\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, brauchen redundanz.
Gehen wir die Fehleranzahl mit verschiedenen Übertragungsanzahlen durch,
erkennt man almählich ein Muster.
\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}
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 2 ü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.
Nun haben wir für jede rekonstruktion des Polynoms, die Polynominterpolation gebraucht.
Diese Polynoiminterpolation ist leider schwierig und fehleranfällig.
Deshalb finden wir eine alternative im nächsten Abschnitt.
|
