diff options
Diffstat (limited to 'buch/papers/reedsolomon/idee.tex')
| -rw-r--r-- | buch/papers/reedsolomon/idee.tex | 68 |
1 files changed, 36 insertions, 32 deletions
diff --git a/buch/papers/reedsolomon/idee.tex b/buch/papers/reedsolomon/idee.tex index daa2913..b1ab8f6 100644 --- a/buch/papers/reedsolomon/idee.tex +++ b/buch/papers/reedsolomon/idee.tex @@ -5,13 +5,13 @@ \label{reedsolomon:section:idee}} \rhead{Problemstellung} Um Fehler in einer Datenübertragung zu erkennen, könnte man die Daten jeweils doppelt senden, -also den gleiche Wert immer zweimal versenden. -Tritt ein Fehler ein wird sich dies in der Differenz der beiden Werten bemerkbar machen. +also den gleiche Wert immer zweimal. +Tritt ein Fehler ein wird sich dies in der Differenz der beiden Werte bemerkbar machen. Aber wie erkennen wir, welcher nun der richtige ist? Die Lösung ist simpel: Wir übertragen den Wert einfach dreimal. -Wenn jetzt ein Fehler auftritt, kann durch die beiden unveränderten Werten den richtigen bestimmt werden. +Wenn jetzt ein Fehler auftritt, kann durch die beiden unveränderten Werte der richtige bestimmt werden. Doch was machen wir, wenn bei dieser Übertragung zwei Fehler auftreten? -Oder noch schlimmer: Was wenn zweimal derselbe Fehler auftritt? Die beiden Fehlerhaften Werte überstimmen bei der Evaluierung den gesendeten Datenwert, der dann unwiderruflich verloren geht. -Wir könnten dies noch steigern mit vier, fünf oder mehr gleichen Übertragenen Werte. Dies erhöht zwar die Robustheit der gesendeten Daten, führt aber auch dazu, dass wir durch die Mehrfachübertragung nur sehr wenige Nutzdaten versenden können. +Oder noch schlimmer: Was wenn zweimal derselbe Fehler auftritt? Die beiden fehlerhaften Werte überstimmen bei der Evaluierung den gesendeten Datenwert, der dann unwiderruflich verloren geht. +Wir könnten dies noch steigern mit vier, fünf oder mehr gleichen übertragenen Werte. Dies erhöht zwar die Robustheit der gesendeten Daten, führt aber auch dazu, dass wir durch die Mehrfachübertragung nur sehr wenige Nutzdaten versenden können. Gerade in unserer heutigen Zeit wäre dies ein enorm grosses Problem und aus diesem Grund wurden alternative Ansätze ausgearbeitet um dieses grundlegende Problem zu lösen. % % @@ -69,58 +69,60 @@ p(x) \textcolor{blue}{2}x^2 + \textcolor{blue}{1}x + \textcolor{blue}{5}. \label{reedsolomon:equation1} \end{equation} -\par + Ein Polynom zweiten Grades ist durch drei Punkte eindeutig bestimmbar. -Bei einer fehlerlosen Übertragung können wir mit 3 übertragenen Werten +Bei einer fehlerlosen Übertragung können wir mit drei übertragenen Werten das Polynom durch Polynominterpolation volständig rekonstruieren. Wir brauchen Polynominterpolation als Methode, um aus den Punkten wieder ein Polynom zu bilden. Die Koeffizente des rekonstruierten Polynoms sind dann unsere gesendeten Zahlen \textcolor{blue}{2}, \textcolor{blue}{1} und \textcolor{blue}{5}. -\par + Wie können wir nun Fehler erkennen oder sogar korrigieren? -Versuchen wir doch, mehr Werte zu übertragen, wie zum Beispiel 7 Werte. +Versuchen wir doch, mehr Werte zu übertragen, wie zum Beispiel sieben Werte. Übertragen werden nun die \textcolor{darkgreen}{grünen Werte} des \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, wobei diese Punkte aufgrund von Übertragungsfehler jetzt eine Parabel darstellen. -Die Fehlerhaften Punkte lassen sich sehr einfach bestimmen, weil diese nicht auf der ursprünglichen Funktion liegen. +Die fehlerhaften Punkte lassen sich sehr einfach bestimmen, weil diese nicht auf der ursprünglichen Funktion liegen. Somit können die roten Punkte auf der Parabel durch die grauen ersetzt werden und sind damit korrigiert. -Bisher konnten wir von 7 Zahlen zwei Fehler erkennen und korrigieren. Können wir in diesem Beispiel noch mehr Fehler korrigieren? +Bisher konnten wir von sieben Zahlen zwei Fehler erkennen und korrigieren. Können wir in diesem Beispiel noch mehr Fehler korrigieren? Wir erhöhen dazu die Fehleranzahl Schritt für Schritt: +\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}% \begin{itemize} \item[\textit{1 Fehler}:] Bei einem Fehler können konkurrenzierende, aber falsche Polynome zusammen mit zwei originalen Punkten entstehen. - Dabei können aber maximal 3 Punkte auf diesem Konkurrenzpolynom sein. + Dabei können aber maximal drei Punkte auf diesem Konkurrenzpolynom sein. Da 6 > 3 ist haben wir unser originales Polynom gefunden. \item[\textit{2 Fehler}:] Bei Zwei Fehlern kann ein Fehler mit zwei originalen Punkten ein konkurrenzierendes, aber falsches Polynom bilden. Da der zweite \textcolor{red}{Fehler} frei wählbar ist, kann dieser auch auf dem \textcolor{gray}{Konkurrenzpolynom} liegen, wie in der Abbilbung \ref{fig:polynom} zu sehen ist. - Nun haben wir, ein \textcolor{blue}{originales Polynom} mit \textcolor{darkgreen}{5} übereinstimmenden und ein konkurrenzierendes mit 4 Punkten. - Da 5 noch grösser als 4 ist, können wir sagen, welches das Originalpolynom ist. - \item[\textit{3 Fehler}:] Bei Drei kann genau wie bei 1 oder 2 Fehler, ein konkurenzierendes Polynom mit einem Fehler und zwei originalen Punkten bestimmt werden. + Nun haben wir, ein \textcolor{blue}{originales Polynom} mit \textcolor{darkgreen}{fünf} übereinstimmenden und ein konkurrenzierendes mit vier Punkten. + Da fünf noch grösser als vier ist, können wir sagen, welches das Originalpolynom ist. + \item[\textit{3 Fehler}:] Bei drei kann genau wie bei ein oder zwei Fehler, ein konkurenzierendes Polynom mit einem Fehler und zwei originalen Punkten bestimmt 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. + Nun ist es so das fünf Punkte auf diesem konkurenzierenden Polynom und vier Punkte auf dem originalen liegen. Das Originalpolynom kann nicht mehr gefunden werden. - \item[\textit{4 Fehler}:] Bei Vier kann noch erkannt werden, dass Fehler aufgetreten sind, da 3 originale Punkte das ursprüngliche Polynom ergeben. - Somit haben wir mindestens 2 verschieden Polynome, was bedeutet, dass Fehler entstanden sind. - \item[\textit{5 Fehler:}] Bei Fünf kann mit den 2 originalen Punkte das Originale Polynom nicht mehr erkannt werden und + \item[\textit{4 Fehler}:] Bei vier kann noch erkannt werden, dass Fehler aufgetreten sind, da drei originale Punkte das ursprüngliche Polynom ergeben. + Somit haben wir mindestens zwei verschiedene Polynome, was bedeutet, dass Fehler entstanden sind. + \item[\textit{5 Fehler:}] Bei fünf kann mit den zwei originalen Punkten das originale Polynom nicht mehr erkannt werden und somit kann auch keine Aussage mehr gemacht werden, ob Fehler aufgetreten sind 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{itemize} \end{beispiel} \section{Anzahl Übertragungswerte bestimmen \label{reedsolomon:section:Fehlerkorrekturstellen}} -Um zu bestimmen, wie viele zusätzliche \textcolor{darkgreen}{Übertragungspunkte} notwendig sind um die Fehler zu korrigieren, +Um zu bestimmen, wie viele zusätzliche \textcolor{darkgreen}{Übertragungspunkte} notwendig sind, um die Fehler zu korrigieren, muss man zuerst wissen, wie viele \textcolor{blue}{Datenwerte} gesendet und wie viele \textcolor{red}{Fehler} erkannt werden sollen. -Die Anzahl Datenwerte ergeben die Anzahl Polynomkoeffizenten \textcolor{blue}{$k$} und somit den Grad $k-1$ des Polynoms. -Die Bestimmung der Anzahl der Fehler \textcolor{red}{$t$}, welche korrigiert werden können, braucht Redundanz. +Die Anzahl Datenwerte ergibt die Anzahl +\textcolor{blue}{$k$} +Polynomkoeffizenten +und somit den Grad $k-1$ des Polynoms. +Die Bestimmung der Anzahl \textcolor{red}{$t$} der Fehler, welche korrigiert werden können, braucht Redundanz. Bilden wir verschieden grosse Polynome und untersuchen diese mit unterschiedlich vielen Fehlern erkennt man allmählich ein Muster. \begin{table}%[!ht] @@ -142,12 +144,14 @@ Bilden wir verschieden grosse Polynome und untersuchen diese mit unterschiedlich \par Es müssen mehr Punkte auf dem \textcolor{blue}{originalen Polynom} liegen, als auf dem konkurenzierenden. Somit braucht man für die Übertragung pro \textcolor{red}{Fehler} zwei Übertragungspunkte mehr. -Wie in der Tabelle \ref{tab:fehlerkorrekturstellen} ersichtlich ist ergeben sich diese Anzahl an \textcolor{darkgreen}{Punkte} für die Übertragung. +Wie in der Tabelle \ref{tab:fehlerkorrekturstellen} ersichtlich ist ergibt sich die +Anzahl \begin{equation} \textcolor{darkgreen}{u}= \textcolor{blue}{k}+2\textcolor{red}{t}. \label{reedsolomon:equation2} \end{equation} +von \textcolor{darkgreen}{Punkten} für die Übertragung. Ein Nebeneffekt ist, dass auch $2t$ Fehler erkannt werden können, die aber nicht korrigiert werden können. Um die Polynomkoeffizenten nach der Übertragung zu rekonstruieren, haben wir jedes mal die Polynominterpolationsmethode angewendet. |