diff options
Diffstat (limited to 'buch/papers/reedsolomon')
21 files changed, 1074 insertions, 157 deletions
diff --git a/buch/papers/reedsolomon/Makefile b/buch/papers/reedsolomon/Makefile index 25fd98b..4be963e 100644 --- a/buch/papers/reedsolomon/Makefile +++ b/buch/papers/reedsolomon/Makefile @@ -24,7 +24,7 @@ SOURCES := \ TIKZFIGURES := \ tikz/polynom2.tex \ - tikz/plotfft.tex + tikz/fourier.tex FIGURES := $(patsubst tikz/%.tex, figures/%.pdf, $(TIKZFIGURES)) diff --git a/buch/papers/reedsolomon/codebsp.tex b/buch/papers/reedsolomon/codebsp.tex index 8430ebd..eb4e82f 100644 --- a/buch/papers/reedsolomon/codebsp.tex +++ b/buch/papers/reedsolomon/codebsp.tex @@ -76,7 +76,7 @@ dar. \subsection{Der Ansatz der diskreten Fouriertransformation \label{reedsolomon:subsection:diskFT}} -In einem vorherigen Abschnitt \textcolor{red}{(???)} haben wir schon einmal die diskrete Fouriertransformation zum Codieren einer Nachricht verwendet. In den endlichen Körpern wird dies jedoch nicht gelingen, da die Eulerische Zahl $e$ in endlichen Körpern nicht existiert. +Im vorherigen Abschnitt \ref{reedsolomon:section:dtf} haben wir schon einmal die diskrete Fouriertransformation zum Codieren einer Nachricht verwendet. In den endlichen Körpern wird dies jedoch nicht gelingen, da die Eulerische Zahl $e$ in endlichen Körpern nicht existiert. Wir wählen deshalb eine Zahl $a$, die die gleichen Aufgaben haben soll wie $e^{\frac{j}{2 \pi}}$ in der diskreten Fouriertransformation, nur mit dem Unterschied, dass $a$ in $\mathbb{F}_{11}$ ist. Dazu soll die Potenz von $a$ den gesamten Zahlenbereich von $\mathbb{F}_{11}$ abdecken. Dazu ändern wir die Darstellung von \[ diff --git a/buch/papers/reedsolomon/dtf.tex b/buch/papers/reedsolomon/dtf.tex index 4552bed..7c88c16 100644 --- a/buch/papers/reedsolomon/dtf.tex +++ b/buch/papers/reedsolomon/dtf.tex @@ -1,85 +1,122 @@ % % 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, + vorausgestzt, 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 Datenwerte zu übertragen, 32 Fehler zu erkennen und 16 Fehler zu 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. -\begin{figure} +\begin{figure}%[!ht] \centering - \resizebox{1.1\textwidth}{!}{ - \includegraphics[width=\textwidth]{papers/reedsolomon/figures/plotfft} + \resizebox{\textwidth}{!}{ + \includegraphics[width=\textwidth]{papers/reedsolomon/figures/fourier} %\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 besteht aus 64 zufälligen, 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. + 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 6, 20 und 74 (\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, nennen wir das Syndrom. + Im Syndrom steckt nur Information über die Fehler, sie werden durch die inverse Fourier-Transformation erzeugt. + \item Um die Fehler zu rekonstruieren, kann 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 lokalisieren. +\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 diskrete-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 Polynoms \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, -dies wird nun im nächsten Abschnitt genauer erklärt. + für verschiedene \( w = e^{-\frac{2\pi j}{N} k}, k=1, \dots ,N-1\) übermittelt. +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 reeleen Zahlen. +Wenn die Approximation nicht mehr genügend gut ist um die Fehler zu erkennen und rekonstruieren, +dann müssen wir von den reeleen Zahlen weg und zum endlichen Körpern, oder auch Galios-Körper genannt. +Dies wird nun im nächsten Abschnitt genauer erklärt. diff --git a/buch/papers/reedsolomon/einleitung.tex b/buch/papers/reedsolomon/einleitung.tex index 074df05..04f1fe2 100644 --- a/buch/papers/reedsolomon/einleitung.tex +++ b/buch/papers/reedsolomon/einleitung.tex @@ -6,8 +6,8 @@ \section{Einleitung \label{reedsolomon:section:einleitung}} \rhead{Einleitung} -Der Reed-Solomon-Code ist entstanden um, -das Problem der Fehler bei der Datenübertragung, zu lösen. +Der Reed-Solomon-Code wurde von den beiden Mathematiker Irving S. Reed und Gustave Solomon im Jahre 1960 entwickelt. +Dabei haben sie das Problem der Fehler bei der Datenübertragung gelöst. In diesem Abschnitt wird möglichst verständlich die mathematische Abfolge, Funktion oder Algorithmus des Reed-Solomon-Code erklärt. Es wird jedoch nicht auf die technische Umsetzung oder Implementierung eingegangen. diff --git a/buch/papers/reedsolomon/endlichekoerper.tex b/buch/papers/reedsolomon/endlichekoerper.tex index 1d196fd..3019dd7 100644 --- a/buch/papers/reedsolomon/endlichekoerper.tex +++ b/buch/papers/reedsolomon/endlichekoerper.tex @@ -3,21 +3,63 @@ % % (c) 2021 Michael Steiner, Hochschule Rapperswil % -\section{Reed-Solomon in Endlichen Körpern +\section{Reed-Solomon in endlichen Körpern \label{reedsolomon:section:endlichekoerper}} \rhead{Reed-Solomon in endlichen Körpern} -\[ -\textcolor{red}{\text{TODO: (warten auf den 1. Teil)}} -\] -Das Rechnen in endlichen Körpern bietet einige Vorteile: +Im vorherigen Abschnitt haben wir gesehen, dass wir die Fehler mittels Approximation suchen und somit nur ungefähre Angaben haben, wo sich Fehler aufhalten. +Um dies zu ändern wechseln wir vom komplexen Zahlenraum in endliche Körper. +In endlichen Körpern gibt es keine Approximationen wie bei den rationalen und reellen Zahlen. +Alle Zahlen sind richtig oder falsch, ``fast richtig'' gibt es nicht. +Zudem beschränken sich die arithmetischen Rechenoperationen auf das Addieren und Multiplizieren. +Wir können also nur ganze Zahlen als Resultat erhalten. +Dies erleichtert auch die Umsetzung auf ein digitales System, da Computer in der Regel lieber mit ganzen als mit gebrochenen oder komplexen Zahlen arbeiten. -\begin{itemize} - \item Konkrete Zahlen: In endlichen Körpern gibt es weder rationale noch komplexe Zahlen. Zudem beschränken sich die möglichen Rechenoperationen auf das Addieren und Multiplizieren. Somit können wir nur ganze Zahlen als Resultat erhalten. - - \item Digitale Fehlerkorrektur: lässt sich nur in endlichen Körpern umsetzen. - -\end{itemize} +Um jetzt eine Nachricht in einem endlichen Körpern zu konstruieren gehen, wir im Grunde gleich vor wie im Beispiel aus dem Abschnitt \ref{reedsolomon:subsection:sendbsp}. +Eine Nachricht besteht aus einem Nutzdatenteil und einem Fehlerkorrekturteil. +Diese Nachricht wird codiert, übertragen und beim Empfänger wieder decodiert. +In endlichen Körpern können wir jedoch nicht mehr die Fouriertransformation zur Hilfe nehmen. +Wir müssen also eine Alternative finden, welche die gleichen Eigenschaften wie die Fouriertransformation aufweist, aber im endlichen Körper verwendet werden kann. +Auch beim Decodieren müssen wir uns etwas einfallen lassen, wenn die Vorgehensweise mit dem Lokator auch in endlichen Körpern funktionieren soll. Die folgenden Abschnitte widmen sich deshalb der genaueren Betrachtung eines Reed-Solomon-Codes und wie er in endlichen Körpern funktioniert. -Um jetzt eine Nachricht in den endlichen Körpern zu konstruieren legen wir fest, dass diese Nachricht aus einem Nutzdatenteil und einem Fehlerkorrekturteil bestehen muss. Somit ist die zu übertragende Nachricht immer grösser als die Daten, die wir übertragen wollen. Zudem müssen wir einen Weg finden, den Fehlerkorrekturteil so aus den Nutzdaten zu berechnen, dass wir die Nutzdaten auf der Empfängerseite wieder rekonstruieren können, sollte es zu einer fehlerhaften Übertragung kommen. - -Nun stellt sich die Frage, wie wir eine fehlerhafte Nachricht korrigieren können, ohne ihren ursprünglichen Inhalt zu kennen. Der Reed-Solomon-Code erzielt dies, indem aus dem Fehlerkorrekturteil ein sogenanntes ``Lokatorpolynom'' generiert werden kann. Dieses Polynom gibt dem Emfänger an, welche Stellen in der Nachricht feherhaft sind. +% +%Damit all diese Probleme möglichst verständlich +% +% +%Um all diese Probleme und möglichst +% +% +%um Fehler zu erkennen und mittels Lokatorpolynom +% +% +% ein Lokatorpolynom zu finden. +% +% +% +% Eine Nachricht besteht aus einem Nutzdatenanteil und einem Fehlerkorrekturteil, +% +% +% +%In diesem Zahlenraum gibt es nur Natürliche Zahlen und es darf nur Addiert oder Multipliziert werden. +%Der grosse Vorteil an endlichen Körper ist, dass dich der einfacher Digital umsetzen lässt. +% +% +%Dieser Zahlenraum bringt eine Menge von neuen Regeln mit sich. +%So gibt es dort nur Natürliche Zahlen und die Arithmetischen Rechenoperationen sind beschränkt auf die Addition und Multiplikation. +% +% +% +%\[ +%\textcolor{red}{\text{TODO: (warten auf den 1. Teil)}} +%\] +%Das Rechnen in endlichen Körpern bietet einige Vorteile: +% +%\begin{itemize} +% \item Konkrete Zahlen: In endlichen Körpern gibt es weder rationale noch komplexe Zahlen. Zudem beschränken sich die möglichen Rechenoperationen auf das Addieren und Multiplizieren. Somit können wir nur ganze Zahlen als Resultat erhalten. +% +% \item Digitale Fehlerkorrektur: lässt sich nur in endlichen Körpern umsetzen. +% +%\end{itemize} +% +%Um jetzt eine Nachricht in den endlichen Körpern zu konstruieren legen wir fest, dass diese Nachricht aus einem Nutzdatenteil und einem Fehlerkorrekturteil bestehen muss. Somit ist die zu übertragende Nachricht immer grösser als die Daten, die wir übertragen wollen. Zudem müssen wir einen Weg finden, den Fehlerkorrekturteil so aus den Nutzdaten zu berechnen, dass wir die Nutzdaten auf der Empfängerseite wieder rekonstruieren können, sollte es zu einer fehlerhaften Übertragung kommen. +% +%Nun stellt sich die Frage, wie wir eine fehlerhafte Nachricht korrigieren können, ohne ihren ursprünglichen Inhalt zu kennen. Der Reed-Solomon-Code erzielt dies, indem aus dem Fehlerkorrekturteil ein sogenanntes ``Lokatorpolynom'' generiert werden kann. Dieses Polynom gibt dem Emfänger an, welche Stellen in der Nachricht feherhaft sind. diff --git a/buch/papers/reedsolomon/figures/fourier.pdf b/buch/papers/reedsolomon/figures/fourier.pdf Binary files differnew file mode 100644 index 0000000..4995141 --- /dev/null +++ b/buch/papers/reedsolomon/figures/fourier.pdf diff --git a/buch/papers/reedsolomon/figures/plotfft.pdf b/buch/papers/reedsolomon/figures/plotfft.pdf Binary files differindex 80d17d2..80adafb 100644 --- a/buch/papers/reedsolomon/figures/plotfft.pdf +++ b/buch/papers/reedsolomon/figures/plotfft.pdf diff --git a/buch/papers/reedsolomon/idee.tex b/buch/papers/reedsolomon/idee.tex index 41e0d4c..6ee42ef 100644 --- a/buch/papers/reedsolomon/idee.tex +++ b/buch/papers/reedsolomon/idee.tex @@ -4,61 +4,69 @@ \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. +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. -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. + 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 Idee ist, aus den Daten ein Polynom zu bilden. -Diese Polynomfunktion bei bestimmten Werten errechnet und diese Punkte dann überträgt. +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 uns dann das Polynom + 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} -ergeben. +\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 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} + 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[\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. + Da 6 > 3 ist haben wir unser original 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}. + Nun haben wir, ein \textcolor{blue}{originales Polynom} mit \textcolor{darkgreen}{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[\textit{3 Fehler}:] Bei Drei 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[\textit{4 Fehler}:] Bei Vier, kann es 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[\textit{5 Fehler}] Bei Fünf, kann mit den 2 originalen Punkte 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 @@ -67,28 +75,18 @@ Um das Konkurrenzpolynom auszuschliessen, währen mehr \textcolor{darkgreen}{Üb \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. +\qedhere \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} +\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 Datenwerte, ergeben die Anzahl Polynomkoeffizente \textcolor{blue}{$k$} und somit den Grad $k-1$. +Die Bestimmung der Anzahl der Fehler \textcolor{red}{$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 @@ -104,8 +102,19 @@ zeigt sich, dass es $k+2t$ Übertragungspunkte braucht. \caption{ Fehlerkorrekturstellen Bestimmung.} \label{tab:fehlerkorrekturstellen} \end{table} +\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 ergibt sich diese \textcolor{darkgreen}{Übertragungsanzahl} +\begin{equation} + \textcolor{darkgreen}{u}= + \textcolor{blue}{k}+2\textcolor{red}{t}. + \label{reedsolomon:equation2} +\end{equation} -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. +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. diff --git a/buch/papers/reedsolomon/standalone/standalone.pdf b/buch/papers/reedsolomon/standalone/standalone.pdf Binary files differindex 4a44333..dfa9eea 100644 --- a/buch/papers/reedsolomon/standalone/standalone.pdf +++ b/buch/papers/reedsolomon/standalone/standalone.pdf diff --git a/buch/papers/reedsolomon/tikz/Makefile b/buch/papers/reedsolomon/tikz/Makefile new file mode 100644 index 0000000..1753f37 --- /dev/null +++ b/buch/papers/reedsolomon/tikz/Makefile @@ -0,0 +1,7 @@ +# +# Makefile +# +# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +# +fourier.pdf: fourier.tex + pdflatex fourier.tex diff --git a/buch/papers/reedsolomon/tikz/fourier.pdf b/buch/papers/reedsolomon/tikz/fourier.pdf Binary files differnew file mode 100644 index 0000000..7e0198b --- /dev/null +++ b/buch/papers/reedsolomon/tikz/fourier.pdf diff --git a/buch/papers/reedsolomon/tikz/fourier.tex b/buch/papers/reedsolomon/tikz/fourier.tex new file mode 100644 index 0000000..7b4ccea --- /dev/null +++ b/buch/papers/reedsolomon/tikz/fourier.tex @@ -0,0 +1,139 @@ +% +% Plot der Übertrangungsabfolge ins FFT und zurück mit IFFT +% +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{times} +\usepackage{pgfplots} +\usepackage{pgfplotstable} +\usepackage{csvsimple} +\usepackage{filecontents} + +\def\plotwidth{7.5cm} +\def\plotheight{5.5cm} +\def\xverschiebung{4.5cm} +\def\yverschiebung{-7cm} +\def\yyverschiebung{-14cm} + +\def\marke#1{ + \coordinate (M) at (-0.8,4.6); + \fill[color=lightgray] (M) circle[radius=0.3]; + \draw (M) circle[radius=0.3]; + \node at (M) {#1}; +} + +\definecolor{darkgreen}{rgb}{0,0.6,0} + +\begin{document} +\begin{tikzpicture}[>=latex,thick] + +\fill[color=blue!10] (-5.7,-14.5) rectangle (2.6,5.0); +\fill[color=darkgreen!10] (2.6,-14.5) rectangle (11.1,5.0); + +\draw[dashed,line width=2pt,color=lightgray] (2.6,4.9) -- (2.6,-14.4); +\coordinate (B) at (2.6,-1.3); +\node[color=gray] at (B) [rotate=90,above] {Zeitbereich\strut}; +\node[color=gray] at (B) [rotate=90,below] {Frequenzbereich\strut}; + +\begin{scope}[xshift=-\xverschiebung,yshift=0cm] + \begin{axis} + [title = {\large Signal\strut}, + xtick={0,32,64,96}, + axis background/.style={fill=white}, + width=\plotwidth,height=\plotheight] + \addplot[blue,line width=1pt] table[col sep=comma] + {tikz/signal.txt}; + \end{axis} + \marke{1} +\end{scope} + +\begin{scope}[xshift=\xverschiebung,yshift=0cm] + \begin{axis}[title = {\large Codiert\strut}, + xtick={0,32,64,96}, + axis background/.style={fill=white}, + width=\plotwidth,height=\plotheight] + \addplot[color=black!60!green,line width=1pt] + table[col sep=comma] + {tikz/codiert.txt}; + \end{axis} + \marke{2} + \draw[->,line width=1pt] (3,-0.4) -- node[right] {Übertragung} (3,-2.2); +\end{scope} + +\definecolor{pink}{rgb}{0.6,0.2,1} + +\begin{scope}[xshift=-\xverschiebung,yshift=\yverschiebung] + %\fill[color=pink!20] (4.65,0.35) ellipse (1.1cm and 0.5cm); + \begin{axis}[title = {\large Decodiert\strut}, + xtick={0,32,64,96}, + axis background/.style={fill=white}, + width=\plotwidth,height=\plotheight] + \addplot[blue,line width=1pt] + table[col sep=comma] {tikz/decodiert.txt}; + \end{axis} + \marke{4} + \draw[color=pink] (4.65,0.35) ellipse (1.1cm and 0.5cm); + \draw[->,color=pink,line width=1pt] + (4.65,-0.15) to[out=-90,in=90] (3,-2.2); +\end{scope} + +\begin{scope}[xshift=\xverschiebung,yshift=\yverschiebung] + \begin{axis}[title = {\large Empfangen {\color{red} mit Fehlern}\strut}, + xtick={0,96}, + axis background/.style={fill=white}, + axis y line*=left, + width=\plotwidth,height=\plotheight] + \addplot[color=black!60!green,line width=1pt] + table[col sep=comma] + {tikz/empfangen.txt}; + \end{axis} + \begin{axis}[xtick={6,20,74}, axis y line*=right, + width=\plotwidth,height=\plotheight] + \addplot[red,line width=1pt] + table[col sep=comma] {tikz/fehler.txt}; + \end{axis} + \marke{3} +\end{scope} + +\begin{scope}[xshift=-\xverschiebung,yshift=\yyverschiebung] + \begin{axis}[title = {\large \color{pink}Syndrom\strut}, + xtick={0,32,64,96}, + axis background/.style={fill=white}, + width=\plotwidth,height=\plotheight] + \addplot[pink,line width=1pt] + table[col sep=comma] {tikz/syndrom.txt}; + \end{axis} + \marke{5} +\end{scope} + +\begin{scope}[xshift=\xverschiebung,yshift=\yyverschiebung] + % Beschriftung Rechts + \begin{axis}[axis x line= none, axis y line*=right, ytick={0.3}, + xtick={0,32,64,96}, + axis background/.style={fill=white}, + width=\plotwidth,height=\plotheight] + \addplot[color=black!60,line width=1pt] {0.3}; + \end{axis} + \begin{axis}[title = {\large Lokator\strut},axis y line*=left, + xtick={0,6,20,74,96}, + width=\plotwidth,height=\plotheight] + \addplot[gray,line width=1pt] + table[col sep=comma] {tikz/locator.txt}; + \end{axis} + \marke{6} +\end{scope} + +% Fourier-Transformations-Pfeile + +\draw[->,line width=1pt] (1.8,2) -- node[above] {DFT\strut} (3.8,2); + +\begin{scope}[yshift=\yverschiebung] +\draw[<-,line width=1pt] (1.8,2) -- node[above] {DFT$\mathstrut^{-1}$} (3.8,2); +\end{scope} + +\begin{scope}[yshift=\yyverschiebung] +\draw[->,line width=1pt] (1.8,2) -- node[above] {DFT\strut} (3.8,2); +\end{scope} + +\end{tikzpicture} +\end{document} 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 |