aboutsummaryrefslogtreecommitdiffstats
path: root/buch/papers/reedsolomon
diff options
context:
space:
mode:
Diffstat (limited to 'buch/papers/reedsolomon')
-rw-r--r--buch/papers/reedsolomon/dtf.tex156
-rw-r--r--buch/papers/reedsolomon/idee.tex98
-rw-r--r--buch/papers/reedsolomon/standalone/standalone.pdfbin1835758 -> 1830948 bytes
-rw-r--r--buch/papers/reedsolomon/tikz/plotfft.tex38
-rw-r--r--buch/papers/reedsolomon/tikz/plotfftraw.tex1
-rw-r--r--buch/papers/reedsolomon/tikz/tikz/codiert.txt96
-rw-r--r--buch/papers/reedsolomon/tikz/tikz/decodiert.txt96
-rw-r--r--buch/papers/reedsolomon/tikz/tikz/empfangen.txt96
-rw-r--r--buch/papers/reedsolomon/tikz/tikz/fehler.txt96
-rw-r--r--buch/papers/reedsolomon/tikz/tikz/locator.txt96
-rw-r--r--buch/papers/reedsolomon/tikz/tikz/signal.txt96
-rw-r--r--buch/papers/reedsolomon/tikz/tikz/syndrom.txt96
12 files changed, 853 insertions, 112 deletions
diff --git a/buch/papers/reedsolomon/dtf.tex b/buch/papers/reedsolomon/dtf.tex
index 4552bed..a975da8 100644
--- a/buch/papers/reedsolomon/dtf.tex
+++ b/buch/papers/reedsolomon/dtf.tex
@@ -1,85 +1,125 @@
%
% dtf.tex -- Idee mit DFT
%
-\section{Übertragung mit Hilfe der Diskrten Fourientransformation
+\section{Übertragung mit Hilfe der Diskrten Fourier-Transformation
\label{reedsolomon:section:dtf}}
\rhead{Umwandlung mit DTF}
-Um die Polynominterpolation zu umgehen, gehen wir nun über in die Fourietransformation.
-Dies wird weder eine Erklärung der Forientransorfmation, noch ein genauer gebrauch für den Reed-Solomon-Code.
-Dieser Abschnitt zeigt nur wie die Fourietransformation auf Fehler reagiert.
-Das ganze zeigen wir mit einem Beispiel einer Übertragung von Zahlen mit Hilfe der Fourietransformation.
+Die Grundidee eines fehlerkorrigierenden Code ist, dass Informationen eines Datenpunkt,
+durch die Codierung, auf viele übertragene Werte verteilt werden.
+Die Decodierung ist in der Lage, den ursprünglichen Datenwert zu rekonstruieren,
+sogar wenn einzelne wenige übertragene Werte beschädigt worden sind.
+\par
+Die Fourier-Transformation transformiert einen einzelnen Wert,
+eine Dirac-Funktion, auf ein Spektrum, welches sich über die ganze Frequenzachse erstreckt.
+Aus der Filtertheorie ist bekannt, dass der ursprüngliche Impuls mehr oder weniger rekonstruierbar ist.
+Forausgestzt, es gehen nicht zu viele Frequenzen bei der Übertragung verloren.
+\par
+Es liegt daher nahe zu versuchen, die Fourier-Transformation
+für Codierung und Decodierung zu verwenden.
-\subsection{Diskrete Fourietransformation Zusamenhang
-\label{reedsolomon:subsection:dtfzusamenhang}}
-Mit hilfe der Fourietransformation werden die \textcolor{blue}{blauen Datenpunkte} transformiert,
+\subsection{Beispiel mit Fehlerkorrektur mit Fourier-Transformation
+\label{reedsolomon:subsection:sendbsp}}
+
+Das folgende Beispiel soll zeigen, wie Fehlerkorrektur möglich ist.
+Dieses auf eine Art, die der Funktionsweise des Reed-Solomon-Codes,
+der später erklärt wird, analog ist.
+\par
+Der Auftrag ist nun 64 Daten zu übertragen, 32 Fehler erkennen und 16 Fehler rekonstruieren.
+Mit hilfe der Fourier-Transformation werden die \textcolor{blue}{blauen Datenpunkte} transformiert,
zu den \textcolor{darkgreen}{grünen Übertragungspunkten}.
Durch eine Rücktransformation könnnen die \textcolor{blue}{blauen Datenpunkte} wieder rekonstruiert werden.
-
-\subsubsection{Beispiel einer Übertragung
-\label{reedsolomon:subsection:Übertragungsabfolge}}
-Der Auftrag ist nun 64 Daten zu übertragen und nach 32 Fehler abzusicheren,
-16 Fehler erkennen und rekonstruieren.
-
-Dieser Auftrag soll mittels Fouriertransformation bewerkstelligt werden.
-In der Abbildung \ref{reedsolomon:subsection:Übertragungsabfolge} sieht man dies Schritt für Schritt,
-und hier werden die einzelne Schritte erklärt:
-\begin{enumerate}[(1)]
- \item Das Signal hat 64 die Daten $k$, hier zufällige Zahlen, welche übertragen werden sollen.
- Zusätzlich soll nach 16 Fehler $t$, die rekonstruierbar sind abgesichert werden.
- Das macht dann insgesamt $k + 2t =
- 64 +2 \cdot 16= 96$ Übertragungszahlen.
- (siehe Abschnitt \externaldocument{papers/reedsolomon/idee}\ref{reedsolomon:section:Fehlerkorrekturstellen})
- Die 32 Fehlerkorrekturstellen werden als Nullzahlen Übertragen.
- \item Nun werden mittels der diskreten Fourietransformation diese 96 codiert, transformiert.
- Das heisst alle Informationen ist in alle Zahlenvorhanden, auch die Fehlerkorrekturstellen Nullzahlen.
- \item Nun kommen drei Fehler dazu an den Übertragungsstellen 7, 21 und 75.
- Die Fehler können auf den ganzen 96 Übertragungswerten liegen, wie die 75 zeigt.
-Zu Beachten ist auch noch, dass der Fehler um das 20- bis 150-Fache kleiner ist.Die Fehlerskala ist rechts.
- \item Dieses wird nun Empfangen, man kann keine Fehler erkennen, da diese soviel kleiner sind.
- Für das Decodieren wird die Inverse Fourietransformation angewendet, und alle Fehler werden mittransformiert.
- \item Nun sieht man die Fehler im decodierten Signal in den Übertragungszahlen.
- Von den Übertragungsstellen 64 bis 96 erkennt man, das diese nicht mehr Null sind.
- \item Diese Fehlerkorrekturstellen 64 bis 96, dies definieren wir als Syndrom.
- In diesem Syndrom ist die Fehlerinformation gespeichert und muss nur noch transformiert werden.
- \item Hier sieht man genau wo die Fehler stattgefunden haben.
- Leider nicht mehr mit der Qualtiätt der Ursprünglichen Fehler, sie sind nur noch 0.6 oder 0.4 gross.
- Obwohl der Fehler um das 20Fache kleiner ist erkennt man im Locator die Fehlerstellen wieder.
- \end{enumerate}
- Nun haben wir mit Hilfe der Fourietransformation die 3 Fehlerstellen durch das Syndrom lokalisiert,
- jetzt gilt es nur noch diese zu korrigieren und wir haben unser originales Signal wieder.
+\par
\begin{figure}
\centering
- \resizebox{1.1\textwidth}{!}{
+ \resizebox{\textwidth}{!}{
\includegraphics[width=\textwidth]{papers/reedsolomon/figures/plotfft}
%\input{papers/reedsolomon/tikz/plotfftraw.tex}
}
- \caption{Übertragungsabfolge \ref{reedsolomon:subsection:Übertragungsabfolge}}
+ \caption{Übertragungsabfolge \ref{reedsolomon:subsection:sendbsp}}
\label{fig:sendorder}
\end{figure}
+In der Abbildung \ref{fig:sendorder} wird eine Übertragung Schritt für Schritt illustriert.
+In der folgenden Aufzählung werden diese einzelne Schritte erklärt und erläutert:
+\begin{enumerate}[(1)]
+ \item Das Signal ist mit 64 zufälligrn, ganzzahligen Datenwerten, zwischen 0 und 10.
+ Für die Rekonstruktion werden zusäzlich Datenwert benötigt, wir fügen deshalb 32 Werte hinzu.
+ Diese setzen wir willkürlich auf Null und nennen sie Fehlerkorrekturstellen
+ \externaldocument{papers/reedsolomon/idee}\ref{reedsolomon:section:Fehlerkorrekturstellen}.
+ Wir erhalten so einen erweiterten Signalvektor der länge $N =96$.
+ \item Mit der Fourier-Transformation wird der ganze Signalvektor codiert.
+ Dadurch wird jede Informationseinheit auf alle Punkte des Spektrums verteilt.
+ \item Wir dürfen annehmen, dass bei der Übertragung, nur einzelne übertragene Werte durch Fehler,
+ verändert werden.
+ \par
+ Im Beispiel sind dies die Werte an den Stellen 7, 21 und 75(\textcolor{red}{rote Kurve}),
+ die um einen Betrag verändert werden.
+ Dieser ist bis zu 150-mal kleiner, als die ursprünglichen codierte Werte.
+ Der Empfänger kennt daher im allgemeinen nicht, ob und wo Übertragungsfehler aufgetreten sind.
+ \item Ohne Übertragungsfehler kann der Signalvektor durch Inverse Fourier-Transformation vollständig
+ wiederhergestellt werden.
+ Dazu gehören auch die Nullen an den Fehlerkorrekturstellen 64 - 96.
+ \par
+ Sind Übertragungsfehler aufgetreten, werden an diesen Stellen, Werte abweichend von Null, auftreten.
+ Somit haben wir bereits Fehler erkannt.
+ \item Die Werte an den Fehlerkorrekturstellen 64 - 96, die nicht mehr Null sind, nennenwir das Syndrom.
+ Im Syndrom steckt nur Information über die Fehler, sie werden durch die Inverse Fourier-Transformation erzeugt.
+ \item Um die Fehler zu rekonstruieren, ann man versuchen, die Information im Syndrom mit Fourier-Transformation zu transformieren.
+ Da das Syndrom nur ein Teil der Fehlerinformation ist, liefert die Fourier-Transformation eine Approximation der Fehler.
+ Diese Approximation der Fehler ist genau genug, um die Fehlerstellen zu localisieren.
+\end{enumerate}
+Im Beispiel haben wir mit dem Syndrom nur etwa ein Drittel der Fehlerinformation, es ist daher zu erwarten,
+dass die Fehlerwerte auch nur ein drittel so gross sind.
+\par
+Damit können die Fehler korrigiert und die Orginaldaten wiederhergestellt werden.
+Der Rekonstruktionsauftrag ist damit erfolgreich ausgeführt.
-Nun zur Definition der Diskrete Fourietransformation, diese ist definiert als
+\subsection{Fourier-Transformation und Polynome\label{reedsolomon:subsection:ftandpolynom}}
+Im Abschnitt \externaldocument{papers/reedsolomon/idee}\ref{reedsolomon:section:polynomansatz}
+wurden Werte eines Polynoms zur Codierung verwendet.
+Die 7 Übertragungspunkte könnten ein Polynom
+\begin{equation}
+ \textcolor{darkgreen}{p(x)}
+ =
+ \textcolor{blue}{a_0} + \textcolor{blue}{a_1}x + \textcolor{blue}{a_2}x^2 +
+ \textcolor{gray}{a_3}x^3 + \textcolor{gray}{a_4}x^4 + \textcolor{gray}{a_5}x^5 +
+ \textcolor{gray}{a_6}x^6
+\label{reedsolomon:equationpoly}
+\end{equation}
+sechsten Grades bestimmen.
+Durch die Wahl von $\textcolor{gray}{a_3=0}$, $\textcolor{gray}{a_4=0}$, $\textcolor{gray}{a_5=0}$, $\textcolor{gray}{a_6=0}$
+erzeugen wir die, für die Fehlerkorrektur,
+nötige Redundanz, ganz analog zum Schritt (1) im Beispiel.
+\par
+Die Analogie geht aber noch weiter.
+ Schreibt man
+ \( w =
+ e^{-\frac{2\pi j}{N} k}\)
+ \label{reedsolomon:DFT_summand}, damit wird aus der Formel
\begin{equation}
\hat{c}_{k}
= \frac{1}{N} \sum_{n=0}^{N-1}
- {f}_n \cdot e^{-\frac{2\pi j}{N} \cdot kn}.
+ {f}_n \cdot e^{-\frac{2\pi j}{N} \cdot kn}
,\label{reedsolomon:DFT}
\end{equation}
- Wenn man nun
+ für die Diskrte-Fourier-Transformation das Polynom
\begin{equation}
- w =
- e^{-\frac{2\pi j}{N} k}
- \label{reedsolomon:DFT_summand}
+ q(w)=
+ \frac{{f}_0}{N} + \frac{{f}_1}{N} w^1 + \frac{{f}_2}{N} w^2 + \dots + \frac{{f}_{N-1}}{N} w^{N-1}
+ \label{reedsolomon:DFT_polynom}
\end{equation}
- ersetzte, und $N$ konstantbleibt, erhält man
+ Im Beispiel werden aber Werte des des Polynoms $q(w)$ für verschieden
+ \( w = e^{-\frac{2\pi j}{N} k}, k=1, \dots , k=N-1\) übermittelt.
\begin{equation}
- \hat{c}_{k}=
- \frac{1}{N}( {f}_0 w^0 + {f}_1 w^1 + {f}_2 w^2 + \dots + {f}_{N-1} w^N)
- \label{reedsolomon:DFT_polynom}
+ \textcolor{darkgreen}{q(w)}=
+ \frac{\textcolor{blue}{{f}_0}}{N} + \frac{\textcolor{blue}{{f}_1}}{N} w^1 + \frac{\textcolor{blue}{{f}_2}}{N} w^2 + \dots +
+ \frac{\textcolor{blue}{{f}_{63}}}{N} w^{63} + \frac{\textcolor{gray}{{f}_{64}}}{N} w^{64} + \textcolor{gray}{\dots} + \frac{\textcolor{gray}{{f}_{N-1}}}{N} w^{N-1}
+ \label{reedsolomon:DFT_polynom2}
\end{equation}
- was überaust ähnlich zu unserem Polynomidee ist.
-Die Polynominterpolation und die Fourietransformation rechnen beide mit reelen Zahlen.
-Wenn die Fehlerabweichung sehr sehr klein ist, erkennt man diese irgendwann nicht mehr.
-Zusätzlich muss mann immer Grenzen bestimmen auf wieviel Stellen gerechnet wird und wie die Fehler erkannt werden im Locator.
-Deshalb haben Mathematiker einen neuen Körper gesucht und ihn in der Endlichkeit gefunden,
+Das syndrom entstand durch die Wahl ${f_{64}}=0$ bis ${f}_{N-1}=0$.(graue koeffizenten)
+\par
+Die Polynominterpolation und die Fourier-Transformation rechnen beide mit reelen Zahlen.
+Wenn die Approximation nicht mehr genügend gut ist um die Fehler zu erkennen und rekonstruieren,
+dann müssen wir von den Reelen-Zahlen weg und zum endlichen Körpern, oder auch Galios-Körper genannt.
+Deshalb haben die Mathematiker einen neuen Körper gesucht und ihn in der Endlichkeit gefunden,
dies wird nun im nächsten Abschnitt genauer erklärt.
diff --git a/buch/papers/reedsolomon/idee.tex b/buch/papers/reedsolomon/idee.tex
index 41e0d4c..c071b5e 100644
--- a/buch/papers/reedsolomon/idee.tex
+++ b/buch/papers/reedsolomon/idee.tex
@@ -5,60 +5,78 @@
\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.
+ also immer zwei gleich Werte miteinander und so jeweilige einen Fehler zu 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.
-Der Reed-Solomon-Code macht dies auf eine andere, clevere Weise.
Das Problem liegt darin Informationen, Zahlen,
-zu Übertragen und Fehler zu erkennen.
+ zu Übertragen und Fehler zu erkennen.
Speziell beim Reed-Solomon-Code kann man nicht nur Fehler erkennen,
-man kann sogar einige Fehler korrigieren.
+ 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}
+Der Reed-Solomon-Code macht dies auf eine andere, clevere Weise.
+Anwendungen finden sind im Abschnitt \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
+Eine Idee ist, aus den Daten ein Polynom zu bilden.
+In deieser Art arbeitet der Reed-Solomon-Code.
+Von dieser Polynomfunktion wird dann eine Anzahl Werte übertragen.
+\begin{beispiel} Nehmen wir zum Beispiel 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.
+ergibt.
+\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,
+ sie kann nachgeschaut werden oder als Funktion angewendet werden.
+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 \textcolor{blue}{blauen Polynomes} an den Stellen 1, 2, 3\dots 7 dieses Polynomes.
+ dieses 7 Werte \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}
+ 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})$
+Nun wird durch drei der 7 Punkte das Polynom eindeutig bestimmbar und
+ alle anderen müssen auf diesem Polynom liegen.
+Dabei gingen wir von keinem Fehler aus,
+ hat es Fehler in der Übertragunge gegeben.
+Wir erhöhen nun die Fehleranzahl Schritt für Schritt:
+\begin{enumerate}
+ \item \textit{Fehler} können konkurenzierende Polynome, zusammen mit zwei originalen Punkten fehlleiten.
+ Dabei kann aber maximal 3 Punkte auf diesem Konkurrenzpolynom sein,
+ ansonsten ist der Fehler ein Orginalpunkt und somit kein Fehler.
+ Da 6 übereinstimende grössser als 3 ist haben wir unser original Polynom gefunden.
+ \par Orginal mit 6 Punkte > 3 Punkte Konkurrenzpolynom, Original Polynom gefunden
+ Damit ist klar das unser Polynom mit 6 Punkten richtig ist und unser Fehler kann rekonstruiert werden.
+ \item \textit{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, wie in unserer Grafik \ref{fig:polynom}, ein Polynom mit 5 übereinstimmenden und eines mit 4 Punkten.
+ Da 5 noch grösser als 4 ist, können wir sagen welches das original Polynom ist.
+ \par Orginal mit 5 Punkte > 4 Punkte Konkurrenzpolynom, Original Polynom gefunden
+ \item \textit{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.
+ \par Orginal mit 5 Punkte > 4 Punkte Konkurrenzpolynom, Original Polynom nicht gefunden
+ \item \textit{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 \textit{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{enumerate}
\begin{figure}%[!ht]
\centering
@@ -71,13 +89,13 @@ Um das Konkurrenzpolynom auszuschliessen, währen mehr \textcolor{darkgreen}{Üb
\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.
+ 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$.
+ 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.
+ 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
@@ -86,7 +104,7 @@ Man könnte auch dies in der Tabelle \ref{tab:fehlerkorrekturstellen} erkennen,
=2
\label{reedsolomon:equation2}
\end{equation}
-zeigt sich, dass es $k+2t$ Übertragungspunkte braucht.
+ zeigt sich, dass es $k+2t$ Übertragungspunkte braucht.
\begin{table}
\centering
diff --git a/buch/papers/reedsolomon/standalone/standalone.pdf b/buch/papers/reedsolomon/standalone/standalone.pdf
index 4a44333..2666d1e 100644
--- a/buch/papers/reedsolomon/standalone/standalone.pdf
+++ b/buch/papers/reedsolomon/standalone/standalone.pdf
Binary files differ
diff --git a/buch/papers/reedsolomon/tikz/plotfft.tex b/buch/papers/reedsolomon/tikz/plotfft.tex
index bb74dfb..77c4dc3 100644
--- a/buch/papers/reedsolomon/tikz/plotfft.tex
+++ b/buch/papers/reedsolomon/tikz/plotfft.tex
@@ -10,6 +10,7 @@
\usepackage{filecontents}
+
\begin{document}
\begin{tikzpicture}[]
@@ -28,12 +29,13 @@
\node(codiert) [] {
\begin{tikzpicture}[]
- \begin{axis}[ title = {\Large {Codiert \space + \space Fehler}},
- xtick={0,40,60,100}, axis y line*=left]
- \addplot[green] table[col sep=comma] {tikz/codiert.txt};
+ % Beschriftung Rechts
+ \begin{axis}[axis x line= none, axis y line*=right,ytick={0}]
+ \addplot[color=white] {0};
\end{axis}
- \begin{axis}[xtick={7,21,75}, axis y line*=right]
- \addplot[red] table[col sep=comma] {tikz/fehler.txt};
+
+ \begin{axis}[ title = {\Large {Codiert}}, axis y line*=left]
+ \addplot[color=black!60!green] table[col sep=comma] {tikz/codiert.txt};
\end{axis}
\end{tikzpicture}}; \\
@@ -46,8 +48,12 @@
\node(empfangen) [] {
\begin{tikzpicture}
- \begin{axis}[title = {\Large {Empfangen}}]
- \addplot[green] table[col sep=comma] {tikz/empfangen.txt};
+ \begin{axis}[title = {\Large {Empfangen \space + \space Fehler}},
+ xtick={0,40,60,100}, axis y line*=left]
+ \addplot[color=black!60!green] table[col sep=comma] {tikz/empfangen.txt};
+ \end{axis}
+ \begin{axis}[xtick={7,21,75}, axis y line*=right]
+ \addplot[red] table[col sep=comma] {tikz/fehler.txt};
\end{axis}
\end{tikzpicture}};\\
@@ -60,7 +66,12 @@
\node(locator) [] {
\begin{tikzpicture}
- \begin{axis}[title = {\Large {Locator}}]
+ % Beschriftung Rechts
+ \begin{axis}[axis x line= none, axis y line*=right, ytick={0.3}];
+ \addplot[color=black!60] {0.3};
+ \end{axis}
+
+ \begin{axis}[title = {\Large {Locator}},axis y line*=left]
\addplot[gray] table[col sep=comma] {tikz/locator.txt};
\end{axis}
\end{tikzpicture}};\\
@@ -74,7 +85,6 @@
\node(FFT) [scale=0.9, above of=IFFT] {FFT};
\draw[-stealth](FFT.north west)--(FFT.north east);
- \draw[thick, ->,] (codiert)++(-1,0) +(0.05,0.5) -- +(-0.1,-0.1) -- +(0.1,0.1) -- +(0,-0.5);
%Arrows
\draw[thick, ->] (signal.east) to (codiert.west);
\draw[thick, ->] (codiert.south) to (empfangen.north);
@@ -85,10 +95,10 @@
%item
\node[circle, draw, fill =lightgray] at (signal.north west) {1};
- \node[circle, draw, fill =lightgray] at (codiert.north west) {2+3};
- \node[circle, draw, fill =lightgray] at (empfangen.north west) {4};
- \node[circle, draw, fill =lightgray] at (decodiert.north west) {5};
- \node[circle, draw, fill =lightgray] at (syndrom.north west) {6};
- \node[circle, draw, fill =lightgray] at (locator.north west) {7};
+ \node[circle, draw, fill =lightgray] at (codiert.north west) {2};
+ \node[circle, draw, fill =lightgray] at (empfangen.north west) {3};
+ \node[circle, draw, fill =lightgray] at (decodiert.north west) {4};
+ \node[circle, draw, fill =lightgray] at (syndrom.north west) {5};
+ \node[circle, draw, fill =lightgray] at (locator.north west) {6};
\end{tikzpicture}
\end{document} \ No newline at end of file
diff --git a/buch/papers/reedsolomon/tikz/plotfftraw.tex b/buch/papers/reedsolomon/tikz/plotfftraw.tex
index 141d2ce..db35734 100644
--- a/buch/papers/reedsolomon/tikz/plotfftraw.tex
+++ b/buch/papers/reedsolomon/tikz/plotfftraw.tex
@@ -1,3 +1,4 @@
+
\begin{tikzpicture}[]
%---------------------------------------------------------------
diff --git a/buch/papers/reedsolomon/tikz/tikz/codiert.txt b/buch/papers/reedsolomon/tikz/tikz/codiert.txt
new file mode 100644
index 0000000..4a481d8
--- /dev/null
+++ b/buch/papers/reedsolomon/tikz/tikz/codiert.txt
@@ -0,0 +1,96 @@
+0,284
+1,131.570790435043
+2,41.9840308053375
+3,12.1189172092243
+4,23.8408857476069
+5,69.1793197789512
+6,24.0186013379153
+7,37.3066577242559
+8,18.2010889773887
+9,12.3214904922455
+10,15.6627133315015
+11,24.5237955316204
+12,32.1114345314062
+13,44.9845039238714
+14,13.5324640263625
+15,10.1736266929292
+16,4.58257569495584
+17,23.217268502288
+18,16.5769107917917
+19,6.89948680823017
+20,4.84567134895776
+21,10.4219666223433
+22,43.6179140616243
+23,35.9073375743642
+24,15.0332963783729
+25,21.7594021268945
+26,23.2496572716993
+27,17.9815599423852
+28,11.3577742151117
+29,38.467599433197
+30,28.3035029562577
+31,9.54321919833388
+32,21.377558326432
+33,17.6292439561917
+34,12.6951848921471
+35,20.0667752354841
+36,22.9097309529208
+37,8.78894645948548
+38,13.360682005498
+39,25.1757616314718
+40,38.0357773686457
+41,18.4633287776253
+42,19.0584505869806
+43,10.8631093309173
+44,12.6147770818983
+45,12.5398140021274
+46,34.901983501949
+47,22.3480442021702
+48,6
+49,22.3480442021702
+50,34.901983501949
+51,12.5398140021274
+52,12.6147770818983
+53,10.8631093309173
+54,19.0584505869806
+55,18.4633287776253
+56,38.0357773686457
+57,25.1757616314718
+58,13.360682005498
+59,8.78894645948548
+60,22.9097309529208
+61,20.0667752354841
+62,12.6951848921471
+63,17.6292439561917
+64,21.377558326432
+65,9.54321919833388
+66,28.3035029562577
+67,38.467599433197
+68,11.3577742151117
+69,17.9815599423852
+70,23.2496572716993
+71,21.7594021268945
+72,15.0332963783729
+73,35.9073375743642
+74,43.6179140616243
+75,10.4219666223433
+76,4.84567134895776
+77,6.89948680823017
+78,16.5769107917917
+79,23.217268502288
+80,4.58257569495584
+81,10.1736266929292
+82,13.5324640263625
+83,44.9845039238714
+84,32.1114345314062
+85,24.5237955316204
+86,15.6627133315015
+87,12.3214904922455
+88,18.2010889773887
+89,37.3066577242559
+90,24.0186013379153
+91,69.1793197789512
+92,23.8408857476069
+93,12.1189172092243
+94,41.9840308053375
+95,131.570790435043
diff --git a/buch/papers/reedsolomon/tikz/tikz/decodiert.txt b/buch/papers/reedsolomon/tikz/tikz/decodiert.txt
new file mode 100644
index 0000000..f6221e6
--- /dev/null
+++ b/buch/papers/reedsolomon/tikz/tikz/decodiert.txt
@@ -0,0 +1,96 @@
+0,6.05208333333333
+1,6.02602539785853
+2,0.0261327016093151
+3,5.98927158561317
+4,4.019445724874
+5,0.0247005083663722
+6,4.97798278395618
+7,1.95246440445439
+8,0.974000110512201
+9,2.00528527696027
+10,1.00071804528155
+11,1.97630907888264
+12,0.0232923747656228
+13,6.01302820392331
+14,3.03567381915226
+15,5.02435590137329
+16,7.00526061008995
+17,5.00739608089369
+18,5.02211514480064
+19,4.02175864806658
+20,1.00236543833726
+21,4.98147315261261
+22,8.97728828610336
+23,8.98481304394618
+24,2.98958333333333
+25,1.98491220960989
+26,5.97728835934715
+27,5.98144124907561
+28,4.00163839998525
+29,2.02176249296313
+30,9.02210713874162
+31,1.00742763919872
+32,1.00557258081044
+33,1.02435888848794
+34,2.03577412756745
+35,6.01302820392331
+36,5.97917574041123
+37,0.976310374034338
+38,9.00062625447998
+39,7.00515849238528
+40,6.97396416790894
+41,0.95256880864368
+42,8.97794719866783
+43,9.01850701506487
+44,10.0194409579917
+45,8.98926601525997
+46,7.9866590265379
+47,5.02603060999077
+48,2.05208333333333
+49,4.02603841132848
+50,0.986882897867895
+51,0.0177592928994285
+52,9.01944131204563
+53,3.0185365665612
+54,2.97803642439316
+55,2.95243072164649
+56,4.97396651395488
+57,6.00516695947321
+58,0.0143895905726619
+59,7.97630812771393
+60,5.97917574041123
+61,9.01298821331865
+62,3.03567381915226
+63,4.02435609145793
+64,0.0275599094902563
+65,0.0115837187254191
+66,0.025877761014238
+67,0.0224618032819697
+68,0.04410594689944
+69,0.0474504002669341
+70,0.0227694695500626
+71,0.0271436638090525
+72,0.0104166666666667
+73,0.0271436638090523
+74,0.0227694695500608
+75,0.0474504002669343
+76,0.0441059468994397
+77,0.0224618032819701
+78,0.0258777610142379
+79,0.0115837187254183
+80,0.027559909490256
+81,0.0245124379481793
+82,0.0499782237195209
+83,0.0401432022864265
+84,0.0232923747656228
+85,0.0237974288564099
+86,0.0143895905726624
+87,0.0271745729691685
+88,0.0275599094902567
+89,0.0515501672184983
+90,0.0358255004834542
+91,0.024700508366373
+92,0.0210194725405171
+93,0.0177592928994296
+94,0.0261327016093158
+95,0.0314909067039411
diff --git a/buch/papers/reedsolomon/tikz/tikz/empfangen.txt b/buch/papers/reedsolomon/tikz/tikz/empfangen.txt
new file mode 100644
index 0000000..38c13b0
--- /dev/null
+++ b/buch/papers/reedsolomon/tikz/tikz/empfangen.txt
@@ -0,0 +1,96 @@
+0,284
+1,131.570790435043
+2,41.9840308053375
+3,12.1189172092243
+4,23.8408857476069
+5,69.1793197789512
+6,23.6290258699579
+7,37.3066577242559
+8,18.2010889773887
+9,12.3214904922455
+10,15.6627133315015
+11,24.5237955316204
+12,32.1114345314062
+13,44.9845039238714
+14,13.5324640263625
+15,10.1736266929292
+16,4.58257569495584
+17,23.217268502288
+18,16.5769107917917
+19,6.89948680823017
+20,5.55320238736303
+21,10.4219666223433
+22,43.6179140616243
+23,35.9073375743642
+24,15.0332963783729
+25,21.7594021268945
+26,23.2496572716993
+27,17.9815599423852
+28,11.3577742151117
+29,38.467599433197
+30,28.3035029562577
+31,9.54321919833388
+32,21.377558326432
+33,17.6292439561917
+34,12.6951848921471
+35,20.0667752354841
+36,22.9097309529208
+37,8.78894645948548
+38,13.360682005498
+39,25.1757616314718
+40,38.0357773686457
+41,18.4633287776253
+42,19.0584505869806
+43,10.8631093309173
+44,12.6147770818983
+45,12.5398140021274
+46,34.901983501949
+47,22.3480442021702
+48,6
+49,22.3480442021702
+50,34.901983501949
+51,12.5398140021274
+52,12.6147770818983
+53,10.8631093309173
+54,19.0584505869806
+55,18.4633287776253
+56,38.0357773686457
+57,25.1757616314718
+58,13.360682005498
+59,8.78894645948548
+60,22.9097309529208
+61,20.0667752354841
+62,12.6951848921471
+63,17.6292439561917
+64,21.377558326432
+65,9.54321919833388
+66,28.3035029562577
+67,38.467599433197
+68,11.3577742151117
+69,17.9815599423852
+70,23.2496572716993
+71,21.7594021268945
+72,15.0332963783729
+73,35.9073375743642
+74,44.6135417384784
+75,10.4219666223433
+76,4.84567134895776
+77,6.89948680823017
+78,16.5769107917917
+79,23.217268502288
+80,4.58257569495584
+81,10.1736266929292
+82,13.5324640263625
+83,44.9845039238714
+84,32.1114345314062
+85,24.5237955316204
+86,15.6627133315015
+87,12.3214904922455
+88,18.2010889773887
+89,37.3066577242559
+90,24.0186013379153
+91,69.1793197789512
+92,23.8408857476069
+93,12.1189172092243
+94,41.9840308053375
+95,131.570790435043
diff --git a/buch/papers/reedsolomon/tikz/tikz/fehler.txt b/buch/papers/reedsolomon/tikz/tikz/fehler.txt
new file mode 100644
index 0000000..23f1a83
--- /dev/null
+++ b/buch/papers/reedsolomon/tikz/tikz/fehler.txt
@@ -0,0 +1,96 @@
+0,0
+1,0
+2,0
+3,0
+4,0
+5,0
+6,2
+7,0
+8,0
+9,0
+10,0
+11,0
+12,0
+13,0
+14,0
+15,0
+16,0
+17,0
+18,0
+19,0
+20,2
+21,0
+22,0
+23,0
+24,0
+25,0
+26,0
+27,0
+28,0
+29,0
+30,0
+31,0
+32,0
+33,0
+34,0
+35,0
+36,0
+37,0
+38,0
+39,0
+40,0
+41,0
+42,0
+43,0
+44,0
+45,0
+46,0
+47,0
+48,0
+49,0
+50,0
+51,0
+52,0
+53,0
+54,0
+55,0
+56,0
+57,0
+58,0
+59,0
+60,0
+61,0
+62,0
+63,0
+64,0
+65,0
+66,0
+67,0
+68,0
+69,0
+70,0
+71,0
+72,0
+73,0
+74,1
+75,0
+76,0
+77,0
+78,0
+79,0
+80,0
+81,0
+82,0
+83,0
+84,0
+85,0
+86,0
+87,0
+88,0
+89,0
+90,0
+91,0
+92,0
+93,0
+94,0
+95,0
diff --git a/buch/papers/reedsolomon/tikz/tikz/locator.txt b/buch/papers/reedsolomon/tikz/tikz/locator.txt
new file mode 100644
index 0000000..b28988c
--- /dev/null
+++ b/buch/papers/reedsolomon/tikz/tikz/locator.txt
@@ -0,0 +1,96 @@
+0,0.0301224340567056
+1,0.141653026854885
+2,0.138226631799377
+3,0.0339903276086929
+4,0.310585462557496
+5,0.551427312631385
+6,0.628514858396814
+7,0.51102386251559
+8,0.275861355940449
+9,0.0502396354182268
+10,0.090185502547573
+11,0.110759344849756
+12,0.0684618905063001
+13,0.0362855426992259
+14,0.0697096919781468
+15,0.109288539370248
+16,0.0923187999496653
+17,0.0512198536768088
+18,0.274192386987782
+19,0.51349614953654
+20,0.633154426602466
+21,0.553283743533942
+22,0.307840573214514
+23,0.0341664350328392
+24,0.140270857957
+25,0.138527177682831
+26,0.029637547736156
+27,0.0816962563186052
+28,0.0944383203811073
+29,0.0263932110686261
+30,0.0585881348402056
+31,0.0737117341599984
+32,0.0239973937701886
+33,0.0464215468420038
+34,0.0616218854220964
+35,0.0221963086695009
+36,0.0390764778127646
+37,0.0537637218396934
+38,0.0208333333333332
+39,0.0343107696069045
+40,0.0483441215964552
+41,0.0198077862118806
+42,0.0311207395968725
+43,0.0444955089373458
+44,0.0190533549944159
+45,0.0290049795038723
+46,0.0417536642697558
+47,0.0185261550443084
+48,0.0277059929762261
+49,0.0398606084144816
+50,0.0181978813094817
+51,0.0271098219177584
+52,0.0386836665079729
+53,0.0180518611046889
+54,0.0272138992557141
+55,0.0381891287148314
+56,0.0180809085252469
+57,0.0281418959420061
+58,0.0384596362516637
+59,0.0182864418432272
+60,0.0302250788423173
+61,0.0397874837986351
+62,0.0186786556701694
+63,0.0342489348284216
+64,0.0429932815348666
+65,0.0192777878591759
+66,0.0422808966931999
+67,0.0506815964680563
+68,0.0201167847752226
+69,0.0615048274405271
+70,0.0744953894508454
+71,0.021246054596492
+72,0.142602265816215
+73,0.273502052865436
+74,0.325309673287599
+75,0.272705389655349
+76,0.149074257381345
+77,0.0247199397628712
+78,0.0680137859566976
+79,0.075388270873485
+80,0.0273637831604903
+81,0.0407867704453274
+82,0.0632964886441949
+83,0.0309749128751093
+84,0.0315202035072035
+85,0.0627625211892184
+86,0.0360843918243497
+87,0.02794920551495
+88,0.0677921493367236
+89,0.0437167157553067
+90,0.0270640150996317
+91,0.0783380025231622
+92,0.0561293738314281
+93,0.0278742033265809
+94,0.0981443889498639
+95,0.0794543457386548
diff --git a/buch/papers/reedsolomon/tikz/tikz/signal.txt b/buch/papers/reedsolomon/tikz/tikz/signal.txt
new file mode 100644
index 0000000..c4fa5f8
--- /dev/null
+++ b/buch/papers/reedsolomon/tikz/tikz/signal.txt
@@ -0,0 +1,96 @@
+0,6
+1,6
+2,0
+3,6
+4,4
+5,0
+6,5
+7,2
+8,1
+9,2
+10,1
+11,2
+12,0
+13,6
+14,3
+15,5
+16,7
+17,5
+18,5
+19,4
+20,1
+21,5
+22,9
+23,9
+24,3
+25,2
+26,6
+27,6
+28,4
+29,2
+30,9
+31,1
+32,1
+33,1
+34,2
+35,6
+36,6
+37,1
+38,9
+39,7
+40,7
+41,1
+42,9
+43,9
+44,10
+45,9
+46,8
+47,5
+48,2
+49,4
+50,1
+51,0
+52,9
+53,3
+54,3
+55,3
+56,5
+57,6
+58,0
+59,8
+60,6
+61,9
+62,3
+63,4
+64,0
+65,0
+66,0
+67,0
+68,0
+69,0
+70,0
+71,0
+72,0
+73,0
+74,0
+75,0
+76,0
+77,0
+78,0
+79,0
+80,0
+81,0
+82,0
+83,0
+84,0
+85,0
+86,0
+87,0
+88,0
+89,0
+90,0
+91,0
+92,0
+93,0
+94,0
+95,0
diff --git a/buch/papers/reedsolomon/tikz/tikz/syndrom.txt b/buch/papers/reedsolomon/tikz/tikz/syndrom.txt
new file mode 100644
index 0000000..8ca9eed
--- /dev/null
+++ b/buch/papers/reedsolomon/tikz/tikz/syndrom.txt
@@ -0,0 +1,96 @@
+0,0
+1,0
+2,0
+3,0
+4,0
+5,0
+6,0
+7,0
+8,0
+9,0
+10,0
+11,0
+12,0
+13,0
+14,0
+15,0
+16,0
+17,0
+18,0
+19,0
+20,0
+21,0
+22,0
+23,0
+24,0
+25,0
+26,0
+27,0
+28,0
+29,0
+30,0
+31,0
+32,0
+33,0
+34,0
+35,0
+36,0
+37,0
+38,0
+39,0
+40,0
+41,0
+42,0
+43,0
+44,0
+45,0
+46,0
+47,0
+48,0
+49,0
+50,0
+51,0
+52,0
+53,0
+54,0
+55,0
+56,0
+57,0
+58,0
+59,0
+60,0
+61,0
+62,0
+63,0
+64,0.0275599094902563
+65,0.0115837187254191
+66,0.025877761014238
+67,0.0224618032819697
+68,0.04410594689944
+69,0.0474504002669341
+70,0.0227694695500626
+71,0.0271436638090525
+72,0.0104166666666667
+73,0.0271436638090523
+74,0.0227694695500608
+75,0.0474504002669343
+76,0.0441059468994397
+77,0.0224618032819701
+78,0.0258777610142379
+79,0.0115837187254183
+80,0.027559909490256
+81,0.0245124379481793
+82,0.0499782237195209
+83,0.0401432022864265
+84,0.0232923747656228
+85,0.0237974288564099
+86,0.0143895905726624
+87,0.0271745729691685
+88,0.0275599094902567
+89,0.0515501672184983
+90,0.0358255004834542
+91,0.024700508366373
+92,0.0210194725405171
+93,0.0177592928994296
+94,0.0261327016093158
+95,0.0314909067039411