diff options
Diffstat (limited to 'buch/papers/reedsolomon')
36 files changed, 715 insertions, 245 deletions
diff --git a/buch/papers/reedsolomon/Makefile b/buch/papers/reedsolomon/Makefile index 9c96e88..25fd98b 100644 --- a/buch/papers/reedsolomon/Makefile +++ b/buch/papers/reedsolomon/Makefile @@ -4,6 +4,52 @@ # (c) 2020 Prof Dr Andreas Mueller # -images: - @echo "no images to be created in reedsolomon" +SOURCES := \ + anwendungen.tex \ + codebsp.tex \ + decmitfehler.tex \ + decohnefehler.tex \ + dtf.tex \ + einleitung.tex \ + endlichekoerper.tex \ + hilfstabellen.tex \ + idee.tex \ + main.tex \ + packages.tex \ + rekonstruktion.tex \ + restetabelle1.tex \ + restetabelle2.tex \ + standalone.tex \ + zusammenfassung.tex + +TIKZFIGURES := \ + tikz/polynom2.tex \ + tikz/plotfft.tex + +FIGURES := $(patsubst tikz/%.tex, figures/%.pdf, $(TIKZFIGURES)) + + +all: images standalone + + +.PHONY: images +images: $(FIGURES) + +figures/%.pdf: tikz/%.tex + mkdir -p figures + pdflatex --output-directory=figures $< + +.PHONY: standalone +standalone: standalone.tex $(SOURCES) $(FIGURES) + mkdir -p standalone + cd ../..; \ + pdflatex \ + --halt-on-error \ + --shell-escape \ + --output-directory=papers/reedsolomon/standalone \ + papers/reedsolomon/standalone.tex; + cd standalone; \ + bibtex standalone; \ + makeindex standalone; + diff --git a/buch/papers/reedsolomon/anwendungen.tex b/buch/papers/reedsolomon/anwendungen.tex index c03b1a4..b9b1d69 100644 --- a/buch/papers/reedsolomon/anwendungen.tex +++ b/buch/papers/reedsolomon/anwendungen.tex @@ -7,21 +7,20 @@ \label{reedsolomon:section:anwendung}} \rhead{Anwendungen} -In den vorherigen Abschnitten haben wir betrachtet, wie Reed-Solomon-Codes in der Theorie Funktionieren. +In den vorherigen Abschnitten haben wir betrachtet, wie Reed-Solomon-Codes in der Theorie funktionieren. In diesem Abschnitt werden wir einige Anwendungen vorstellen, bei denen ein Reed-Solomon-Code zum Einsatz kommt. -Dabei teilen all diese Anwendungen das gleiche Problem: Die Daten können nur durch einen (höchst Wahrscheinlichen) fehlerbehafteten Kanal empfangen werden. Es gibt keine andere Methode an diese Daten zu kommen als über diesen Kanal. +Dabei teilen all diese Anwendungen das gleiche Problem: Die Daten können nur durch einen (höchst Wahrscheinlichen) fehlerbehafteten Kanal empfangen werden. Es gibt keine andere Methode, an diese Daten zu kommen, als über diesen Kanal. - -In der Netzwerktechnik zum Beispiel ist es üblich, dass bei Paketverluste oder beschädigt empfangene Datenpakete diese einfach noch einmal inert wenigen Millisekunden angefordert werden können. +In der Netzwerktechnik zum Beispiel ist es üblich, dass bei Paketverluste oder beschädigt empfangene Datenpaketen diese einfach noch einmal innert wenigen Millisekunden angefordert werden können. In der Raumfahrt ist dies nicht möglich, da aufgrund der beschränkten Speichermöglichkeit die gesammelten Daten so rasch wie möglich zur Erde gesendet werden. Diese Daten wiederum brauchen aufgrund der grossen Distanz Stunden bis die Daten beim Empfänger ankommen. Fehlerhafte Daten kann also auf Grund der Zeitverzögerung nicht mehr angefordert werden. -Bei CDs oder DVDs gibt es zwar kein Zeitliches Problem, jedoch erschweren Kratzer, Verschmutzungen oder Produktionsfehler das Lesen einer solchen Disk. +Bei CDs oder DVDs gibt es zwar kein zeitliches Problem, jedoch erschweren Kratzer, Verschmutzungen oder Produktionsfehler das Lesen einer solchen Disk. Da vor allem Produktionsfehler und Kratzer irreversibel sind und die Disk nicht nach jedem Kratzer ersetzt werden muss, so wird die korrekte Ausgabe der gespeicherten Information durch die Fehlerkorrektur sichergestellt. -Ein ähnlicher Ansatz verfolgen QR-Codes, wobei die Information auch dann noch gelesen werden kann wenn der Code nicht mehr vollständig vorhanden ist. +Einen ähnlichen Ansatz verfolgen QR-Codes, wobei die Information auch dann noch gelesen werden kann wenn der Code nicht mehr vollständig vorhanden ist. %Wie man sieht, eignen sich Reed-Solomon-Codes vor allem für Anwendungen, bei der die Informationen nicht auf einen Anderen Weg beschafft werden kann. % @@ -33,7 +32,6 @@ Ein ähnlicher Ansatz verfolgen QR-Codes, wobei die Information auch dann noch g % da aufgrund der grossen Distanz Stunden vergehen können bis gesendete Daten auf der Erde empfangen werden kann. % - Obwohl alle diese Codes nach dem gleichen Prinzip arbeiten gibt es starke Unterschiede in deren Funktionsweise. Dies kommt vor allem daher, da die Codes nur Ressourcen zur Verfügung haben, die von der Hardware bereitstellt wird, auf denen die Codes implementiert wurden. Diese Codes bedienen sich daher verschiedener Tricks und Optimierungen um möglichst effizient zu arbeiten. @@ -75,8 +73,14 @@ Obwohl Reed-Solomon-Codes bereits in den 1960er entwickelt wurden fanden sie ers Codiert. Der Nachrichtenblock hat somit eine Länge von $255$ Zahlen, wovon $233$ als Nutzlast zur Verfügung stehen. Damit ist es möglich bis zu $11$ Fehler im Nachrichtenblock zu korrigieren. -Der Codierte Nachrichtenblock wird in kleinere Blöcke aufgeteilt, mit einem Faltungscode erneut Codiert und anschliessend gesendet. Ein Faltungscode ist wie ein Reed-Solomon-Code in der Lage Fehler zu korrigieren, Funktioniert aber nach einem ganz anderen Prinzip. -Durch diese doppelte Codierung wird eine äusserst hohe Übertragungssicherheit garantiert. +Der Codierte Nachrichtenblock wird in kleinere Blöcke aufgeteilt, mit einem Faltungscode erneut Codiert und anschliessend gesendet. +Ein Faltungscode ist wie ein Reed-Solomon-Code in der Lage Fehler zu korrigieren, +Codiert seine Information aber auf eine andere weise. Aus jedem unterteilten Block wird vor dem Versenden ein Paritätsbit erzeugt und dem Block angehängt. Anhand diesem Paritätsbit überprüft der Empfänger, ob bei der Übertragung der Block beschädigt wurde. Ist dies der Fall, wird der Block bei der Decodierung nicht beachtet. Diese so entstandenen ``Lücken'' im Datenstrom werden wiederum vom Reed-Solomon-Code korrigiert. Dieses Zusammenspiel beider Codes garantiert so eine hohe Robustheit gegenüber Übertragungsfeher. + +% +% Funktioniert aber nach einem ganz anderen Prinzip. +% +%Durch diese doppelte Codierung wird eine äusserst hohe Übertragungssicherheit garantiert. % %Dabei steht die Zahl 255 für grösse des Nachrichtenblocks, der die Anzahl 233 % @@ -107,13 +111,18 @@ Die Digital Video Disc funktioniert nach dem selben Konzept mit grösseren Codeb \begin{figure} \centering - \includegraphics[width=0.5\textwidth]{papers/reedsolomon/images/Compact_Disc} - \caption{CDs kamen 1982 auf den Markt. Sie funktioniert durch das ``einbrennen'' von Punkten und Strichen, die die Daten repräsentieren. Gelesen werden diese wiederum durch die Reflektion eines Lasers an diesen Punkten und Strichen.} + \subfigure[]{ + \includegraphics[width=0.45\textwidth]{papers/reedsolomon/images/Compact_Disc} + } + \subfigure[]{ + \includegraphics[width=0.45\textwidth]{papers/reedsolomon/images/Compact_Disc_zoomed_in} + } + \caption{CDs kamen 1982 auf den Markt. Sie funktioniert durch das Einpressen oder Einbrennen von Punkten und Strichen, die die Daten repräsentieren. Gelesen werden diese wiederum durch die Reflektion eines Lasers an diesen Punkten und Strichen.} \label{fig:cd} \end{figure} \subsection{QR-Codes} -Quick Response Codes oder auch QR-Codes funktionieren nach einem sehr ähnlichen Prinzip wie in unserem Beispiel der Abschnitte \ref{reedsolomon:section:codebsp} - \ref{reedsolomon:section:rekonstruktion} nur das QR-Codes in einem $\mathbb{F}_{256}$ Körper arbeiten. Die Physische Grösse eines Codes ist stark abhängig von der Grösse der Codierung sowie dem Fehlerkorrektur-Level. Es ist so auf dem ersten Blick nicht ersichtlich, wie viel Nutzinformationen ein Qr-Code enthält. Die QR-Codes in Abbildung \ref{fig:qr} zeigen jeweils die Gleiche Information mit unterschiedlichem Fehlerkorrektur-Level. Codes mit einem höheren Korrektur-Level können auch für Designer-Codes Zweckentfremdet werden. Dabei wird z.B. das Firmenlogo oder einen Schriftzug über den Qr-Code gelegt, ohne das die Funktion des Codes beeinträchtigt wird. Ein Beispiel dazu ist unter Abbildung \ref{fig:designqr} zu finden. +Quick Response Codes oder auch QR-Codes funktionieren nach einem sehr ähnlichen Prinzip wie in unserem Beispiel der Abschnitte \ref{reedsolomon:section:codebsp} - \ref{reedsolomon:section:rekonstruktion} nur das QR-Codes in einem $\mathbb{F}_{256}$ Körper arbeiten. Die physische Grösse eines Codes ist stark abhängig von der Menge an codierten Daten sowie dem verwendeten Fehlerkorrektur-Level. Es ist so auf dem ersten Blick nicht ersichtlich, wie viel Nutzinformationen ein Qr-Code enthält. Die QR-Codes in Abbildung \ref{fig:qr} zeigen jeweils die Gleiche Information mit unterschiedlichem Fehlerkorrektur-Level. Codes mit einem höheren Korrektur-Level können auch für Designer-Codes Zweckentfremdet werden. Dabei wird z.B. das Firmenlogo oder einen Schriftzug über den Qr-Code gelegt, ohne das die Funktion des Codes beeinträchtigt wird. Ein Beispiel dazu ist unter Abbildung \ref{fig:designqr} zu finden. % @@ -154,6 +163,6 @@ Quick Response Codes oder auch QR-Codes funktionieren nach einem sehr ähnlichen \subfigure[]{ \includegraphics[width=0.4\textwidth]{papers/reedsolomon/images/designer_qrcode} } - \caption{Während (a) noch ein unveränderter QR-Code repräsentiert, handelt es sich bei (b) nun um einen Designer-QR-Code. Beide Codes verfügen über einen mittleren Fehlerkorrektur-Level von theoretisch 15\%. Da bei (b) jetzt einen Teil des Codes durch ein Logo verdeckt wird, schränkt sich dadurch die Fehlerkorrekturfähigkeit je nach grösse des verdeckten Teils mehr oder weniger stark ein. Unser Designer-Code in (b) ist nur noch in der Lage etwa 9\% des Codes zu rekonstruieren.} + \caption{Während (a) noch einen unveränderten QR-Code repräsentiert, handelt es sich bei (b) nun um einen Designer-QR-Code. Beide Codes verfügen über einen mittleren Fehlerkorrektur-Level von theoretisch 15\%. Da bei (b) jetzt einen Teil des Codes durch ein Logo verdeckt wird, schränkt sich die Fehlerkorrekturfähigkeit je nach Grösse des verdeckten Teils mehr oder weniger stark ein. Unser Designer-Code in (b) ist nur noch in der Lage etwa 9\% des Codes zu rekonstruieren.} \label{fig:designqr} \end{figure}
\ No newline at end of file diff --git a/buch/papers/reedsolomon/dtf.tex b/buch/papers/reedsolomon/dtf.tex index a111527..179d90d 100644 --- a/buch/papers/reedsolomon/dtf.tex +++ b/buch/papers/reedsolomon/dtf.tex @@ -1,55 +1,125 @@ % -% teil3.tex -- Beispiel-File für Teil 3 +% dtf.tex -- Idee mit DFT % -% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil -% -\section{Diskrete Fourier Transformation +\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 Fourientransformation. -Dies wird weder eine erklärung der Forientransorfmation noch ein genauer gebrauch -für den Reed-Solomon-Code. Dieser Abschnitt zeigt nur wie die Fourientransformation auf Fehler reagiert. -wobei sie dann bei späteren Berchnungen ganz nützlich ist. +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 Fourientransformation Zusamenhang -\label{reedsolomon:subsection:dtfzusamenhang}} -Die Diskrete Fourientransformation ist definiert als - \[ - \label{ft_discrete} - \hat{c}_{k} - = \frac{1}{N} \sum_{n=0}^{N-1} - {f}_n \cdot e^{-\frac{2\pi j}{N} \cdot kn} - \] -, wenn man nun - \[ - w = e^{-\frac{2\pi j}{N} k} - \] -ersetzte, und $N$ konstantbleibt, erhält man - \[ - \hat{c}_{k}=\frac{1}{N}( {f}_0 w^0 + {f}_1 w^1 + {f}_2 w^2 + \dots + {f}_{N-1} w^N) - \] -was überaust ähnlich zu unserem Polynomidee ist. -\subsection{Übertragungsabfolge -\label{reedsolomon:subsection:Übertragungsabfolge}} +\subsection{Beispiel mit Fehlerkorrektur mit Fourier-Transformation +\label{reedsolomon:subsection:sendbsp}} -\begin{enumerate}[1)] -\item Das Signal hat 64 die Daten, Zahlen welche übertragen werden sollen. -Dabei zusätzlich nach 16 Fehler abgesichert, macht insgesamt 96 Übertragungszahlen. -\item Nun wurde mittels der schnellen diskreten Fourientransformation diese 96 codiert. -Das heisst alle information ist in alle Zahlenvorhanden. -\item Nun kommen drei Fehler dazu an den Übertragungsstellen 7, 21 und 75. -\item Dieses wird nun Empfangen und mittels inversen diskreten Fourientransormation, wieder rücktransformiert. -\item Nun sieht man den Fehler im Decodieren in den Übertragungsstellen 64 bis 96. -\item Nimmt man nun nur diese Stellen 64 bis 96, auch Syndrom genannt, und Transformiert diese. -\item Bekommt man die Fehlerstellen im Locator wieder, zwar nichtso genau, dennoch erkkent man wo die Fehler stattgefunden haben. -\end{enumerate} +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. \begin{figure} \centering - \resizebox{0.9\textwidth}{!}{ - %\includegraphics[width=0.5\textwidth]{papers/reedsolomon/images/plot.pdf} - \input{papers/reedsolomon/images/plotfft.tex} + \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}
\ No newline at end of file +\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. + +\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} + ,\label{reedsolomon:DFT} + \end{equation} + für die Diskrte-Fourier-Transformation das Polynom + \begin{equation} + 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} + 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} + \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} +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/einleitung.tex b/buch/papers/reedsolomon/einleitung.tex index 2b1d878..ca4f398 100644 --- a/buch/papers/reedsolomon/einleitung.tex +++ b/buch/papers/reedsolomon/einleitung.tex @@ -6,14 +6,12 @@ \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. -In diesem Abschnitt wird möglichst verständlich die mathematische Abfolge, Funktion oder Algorithmus erklärt. +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. -Um beim Datenübertragen Fehler zu erkennen, könnte man die Daten jeweils doppelt senden, -und so jeweilige Fehler zu erkennen. -Doch nur schon um weinige Fehler zu erkennen werden überproportional viele Daten doppelt und dreifach gesendet. -Der Reed-Solomon-Code macht dies auf eine andere, clevere Weise. + diff --git a/buch/papers/reedsolomon/experiments/plot.tex b/buch/papers/reedsolomon/experiments/plot.tex index 2196c82..4b156bb 100644 --- a/buch/papers/reedsolomon/experiments/plot.tex +++ b/buch/papers/reedsolomon/experiments/plot.tex @@ -90,7 +90,7 @@ \draw[ultra thick, ->] (zoom) to[out=180, in=90] (syndrom.north); %item - \node[circle, draw, fill =lightgray] at (signal.north west)+(1,0) {1}; + \node[circle, draw, fill =lightgray] at (signal.north west) {1}; \node[circle, draw, fill =lightgray] at (codiert.north west) {2}; \node[circle, draw, fill =lightgray] at (fehler.north west) {3}; \node[circle, draw, fill =lightgray] at (empfangen.north west) {4}; diff --git a/buch/papers/reedsolomon/figures/plotfft.pdf b/buch/papers/reedsolomon/figures/plotfft.pdf Binary files differnew file mode 100644 index 0000000..b455da5 --- /dev/null +++ b/buch/papers/reedsolomon/figures/plotfft.pdf diff --git a/buch/papers/reedsolomon/figures/polynom2.pdf b/buch/papers/reedsolomon/figures/polynom2.pdf Binary files differnew file mode 100644 index 0000000..55a50ac --- /dev/null +++ b/buch/papers/reedsolomon/figures/polynom2.pdf diff --git a/buch/papers/reedsolomon/idee.tex b/buch/papers/reedsolomon/idee.tex index 39adbbf..2142f88 100644 --- a/buch/papers/reedsolomon/idee.tex +++ b/buch/papers/reedsolomon/idee.tex @@ -1,72 +1,93 @@ % -% teil1.tex -- Beispiel-File für das Paper -% -% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil +% idee.tex -- Polynom Idee % \section{Idee \label{reedsolomon:section:idee}} \rhead{Problemstellung} +Um Fehler in einer Datenübertragung zu erkennen, könnte man die Daten jeweils doppelt senden, + also immer zwei gleich Werte miteinander und so jeweilige einzelne Fehler erkennen. +Wenn jedoch mehr als nur ein Fehler erkennt werden soll und sogar noch das orginal rekonstruiert werden soll, +dann werden die Daten drei oder vierfach versendet. +Doch nur schon um Fehler zu erkennen werden überproportional viele Daten doppelt und dreifach gesendet. Das Problem liegt darin Informationen, Zahlen, -zu Übertragen und Fehler zu erkennen. -Beim Reed-Solomon-Code kann man nicht nur Fehler erkennen, -man kann sogar einige Fehler korrigieren. + zu Übertragen und Fehler zu erkennen und zu korrigieren. +Der Unterschied des Fehler erkennen und korrigiren, ist das beim Erkennen nur die Frage beantwortet wird: Ist die Übertragung fehlerhaft oder nicht? +Beim Korrigieren werden Fehler erkannt und dann zusätzlich noch den original Wert rekonstruieren. +Eine weitere Möglichkeit wäre, dass der Empfänger nach einer fehlerhaften Übertragung die selben Daten nochmals auffordert. +Dies führt wieder zu unerwünschten mehrfach Übertragung. +In Anwendungen des Reed-Soöomon-Code \externaldocument{papers/reedsolomon/anwendungen} \ref{reedsolomon:section:anwendung} +ist dies vom Empfänger gesteuerte erneute Übertragen meistens nicht sinnvoll oder sogar unmöglich. +Der Reed-Solomon-Code macht dies Übertragung auf eine andere, clevere Weise. +\subsection{Polynom-Ansatz +\label{reedsolomon:section:polynomansatz}} \rhead{Polynom-Ansatz} -Eine Idee ist aus den Daten -ein Polynom zu bilden. -Diese Polynomfunktion bei bestimmten Werten, ausrechnet und diese Punkte dann überträgt. -Nehmen wir als beisbiel die Zahlen \textcolor{blue}{2}, \textcolor{blue}{1}, \textcolor{blue}{5}, -welche uns dann das Polynom +Eine zentrale Idee des Reed-Solomon-Code ist, aus den Daten ein Polynom zu bilden. +Von dieser Polynomfunktion wird dann eine Anzahl Werte übertragen. +\begin{beispiel} Nehmen wir die Zahlen \textcolor{blue}{2}, \textcolor{blue}{1}, \textcolor{blue}{5}, + welche übertragen werden sollen. Daraus bilden wir das Polynom \begin{equation} p(x) = \textcolor{blue}{2}x^2 + \textcolor{blue}{1}x + \textcolor{blue}{5} \label{reedsolomon:equation1} -\end{equation} -ergeben. -Übertragen werden nun die Werte 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{green}{8}, -\textcolor{green}{15}, \textcolor{green}{26}, -\textcolor{green}{41}, \textcolor{green}{60}, -\textcolor{green}{83}, \textcolor{green}{110})$ -Wenn ein Fehler sich in die Übertragung eingeschlichen hatt, muss der Leser/Empfänger diesen erkennen und das Polynom rekonstruieren. -Der Leser/Empfänger weiss, den Grad des Polynoms und dessen Werte übermittelt wurden. - -\subsection{Beispiel} -Für das Beispeil aus der Gleichung \eqref{reedsolomon:equation1}, -ist ein Polynome zweiten Grades durch drei Punkte eindeutig bestimmbar. -Hat es Fehler in der Übertragunge gegeben,(Bei Abbildung \ref{fig:polynom}\textcolor{red}{roten Punkte}) kann man diese erkennen, -da alle Punkte, die korrekt sind, auf dem Polynom liegen müssen. -(Bei Abbildung \ref{fig:polynom}\textcolor{green}{grünen Punkte}) -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 erkennt werden, dass das Polynom nicht stimmt. -Das orginale Polynom kann aber nicht mehr gefunden werden. -Dafür sind mehr übertragene Werte nötig. +\end{equation}. +\par +Ein Polynome zweiten Grades ist durch drei Punkte eindeutig bestimmbar. +Bei einer fehlerlosen Übertragung, können wir mit 3 übertragene Werte, + das Polynom durch Polynominterpolation volständig rekonstruieren. +Weder erkläre noch erläutere ich die Polynominterpolation, + wir brauchen sie als Funktion, die von Punktn ein Polynom errechnet. +Die koeffizente, des rekonstruierten Polynoms, sind dann unsere gesendten Zahlen \textcolor{blue}{2}, \textcolor{blue}{1}, \textcolor{blue}{5}. +Wie können wir nun Fehler erkennen oder sogar korrigieren? +Versuchen wir doch mehr Werte zu Übertragen, wir nehmen im Beispiel 7 Werte. +Übertragen werden nun die \textcolor{darkgreen}{grünen Werte} + dieses 7 Werte \textcolor{blue}{blauen Polynomes} an den Stellen 1, 2, 3\dots 7 . +In Abbildung \ref{fig:polynom} ist das zu den \textcolor{blue}{Datenpunkten} gehörige Polynom blau dargestellt, +die \textcolor{darkgreen}{übertragene Werte} des Polynoms sind grün. +Die grünen Punkte bestimmen die Parabel. +Damit können die Fehler erkannt werden, weil die empfangenen Punktenicht auf der Parabel liegen. +Somit könnendie grauen Punkte auf der Parabel ersetzt werden und sind damit korrigiert. +bis zu wivielen Fehler können wir nun korrigieren im Beispiel korrigieren? +Wir erhöhen nun die Fehleranzahl Schritt für Schritt: +\begin{itemize} + \item Bei \textit{1 Fehler} können konkurenzierende Polynome, zusammen mit zwei originalen Punkten fehlleiten. + Dabei kann aber maximal 3 Punkte auf diesem Konkurrenzpolynom sein. + Da 6 übereinstimende grössser als 3 ist haben wir unser original Polynom gefunden. + \item Bei \textit{2 Fehler} kann ein Fehler mit zwei originalen Punkten ein fehlleitendes Konkurrenzpolynom bilden. + Da der zweite Fehler frei wählbar ist, kann dieser auch auf dem Konkurrenzpolynom liegen, wie in der Abbilbung \ref{fig:polynom}. + Nun haben wir, ein originles Polynom mit 5 übereinstimmenden und eine konkurrenzierendes mit 4 Punkten. + Da 5 noch grösser als 4 ist, können wir sagen, welches das original Polynom ist. + \item Bei \textit{3 Fehler} kann genau wie bei 2 Fehler, ein Fehler ein fehlleitendes Polynom mit 2 original Punkten bestimmen werden. + Auch hier sind die anderen Fehler frei wählbar und liegen auf dem Konkurrenzpolynom. + Nun ist es so das 5 Punkte auf diesem konkurenzierenden Polynom und 4 Punkte auf dem Originalen. + Das Original Polynom kann nicht mehr gefunden werden. + \item Bei \textit{4 Fehler} Es kann noch erkennt weden das Fehler statt gefunden haben, da 3 orginale Punkte das ursprüngliche Polynom ergeben. + Somit haben wir mindestens 2 verschieden Polynome, dass bedeutet Fehler sind entstanden. + \item Bei \textit{5 Fehler} Mit den 2 originalen Punkte kann das Originale Polynom nicht mehr erkannt werden und + somit auch keine Aussgae gemacht werden ob Fehler statt gefunden haben oder nicht. +\end{itemize} -\begin{figure} +\begin{figure}%[!ht] \centering - %\includegraphics[width=0.5\textwidth]{papers/reedsolomon/images/polynom2} - \input{papers/reedsolomon/images/polynom2.tex} - \caption{Polynom $p(x)$ \eqref{reedsolomon:equation1}} + %\includegraphics[width=\textwidth]{papers/reedsolomon/figures/polynom2} + \input{papers/reedsolomon/tikz/polynomraw.tex} + \caption{Polynom $p(x)$ von der Gleichung\eqref{reedsolomon:equation1}} \label{fig:polynom} \end{figure} +\end{beispiel} -\section{Fehlerbestimmung -\label{reedsolomon:section:Fehlerbestimmmung}} -So wird ein Muster indentifiziert, welches genau vorherbestimmen kann, -wie gross das Polynom sein muss und wie viele Übertragungspunkte gegeben werden müssen. -Um zu bestimmen wie viel Fehler erkennt und korriegiert werden können. -Die Anzahl Zahlen (Daten, ab hier verwenden wir das Wort Nutzlast), -die Entschlüsselt werden sollen, brauchen die gleiche Anzahl an Polynomgraden, beginnend bei Grad 0. ( \( k-1 \) ) -Für die Anzahl an Übertragungspunkte, muss bestimmt werden wieviel Fehler erkennt und korrigiert werden sollen. -Mit Hilfe der Tabelle, sieht man das es bei $t$ Fehlern und $k$ Nutzlast Zahlen, -$k+2t$ Punkte übertragen werden müssen. - -\begin{center} - \begin{tabular}{ c c c } +\section{Anzahl Übertragungswerte bestimmen +\label{reedsolomon:section:Fehlerkorrekturstellen}} +Um zu bestimmen, wieviel zusätzliche \textcolor{darkgreen}{Übertragungspunkte} notwendig sind, um die Fehler zu korrigieren, + muss man zuerst wissen, wieviel \textcolor{blue}{Datenwerte} gesendet und wieviel \textcolor{red}{Fehler} erkennt werden sollen. +Die Anzahl \textcolor{blue}{Datenwerte}, ergeben die anzahl Polynomkoeffizente $k$ und somit den Grad $k-1$. +Die Bestimmung der Anzahl der Fehler $t$, welche korrigiert werden können, brauchen redundanz. +Gehen wir die Fehleranzahl mit verschiedenen Übertragungsanzahlen durch, + erkennt man almählich ein Muster. +\begin{table} + \centering + \begin{tabular}{ c c | c} \hline Nutzlas & Fehler & Übertragen \\ \hline @@ -77,12 +98,20 @@ $k+2t$ Punkte übertragen werden müssen. $k$ & $t$ & $k+2t$ Werte eines Polynoms vom Grad $k-1$ \\ \hline \end{tabular} -\end{center} + \caption{ Fehlerkorrekturstellen Bestimmung.} + \label{tab:fehlerkorrekturstellen} +\end{table} +Es müssen mehr Punkte auf dem \textcolor{blue}{originalen Polynom} liegen, als auf dem Konkurenzierenden. +Somit braucht man für die Übertragung pro Fehler 2 übertragungspunkte mehr. +Wie in der Tabelle ergibt sich diese Übertragungsanzahl +\begin{equation} + \textcolor{darkgreen}{u}= + \textcolor{blue}{k}+2\textcolor{red}{t} + \label{reedsolomon:equation2} +\end{equation}. -Ein toller Nebeneffekt ist das dadurch auch $2t$ Fehler erkannt werden. -Um zurück auf unser Beispiel zu kommen, -können von den 7 Übertragungspunkten bis zu $2t = 2\cdot2 = 4 $ Punkten falsch liegen -und es wird kein eindeutiges Polynom zweiten Grades erkannt, und somit die Nutzlast Daten als fehlerhaft deklariert. -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. +Nun haben wir für jede rekonstruktion des Polynoms, die Polynominterpolation gebraucht. +Diese Polynoiminterpolation ist leider schwierig und fehleranfällig. +Deshalb finden wir eine alternative im nächsten Abschnitt. diff --git a/buch/papers/reedsolomon/images/Compact_Disc_zoomed_in.png b/buch/papers/reedsolomon/images/Compact_Disc_zoomed_in.png Binary files differnew file mode 100644 index 0000000..69556d0 --- /dev/null +++ b/buch/papers/reedsolomon/images/Compact_Disc_zoomed_in.png diff --git a/buch/papers/reedsolomon/images/plotfft.tex b/buch/papers/reedsolomon/images/plotfft.tex deleted file mode 100644 index 83a89eb..0000000 --- a/buch/papers/reedsolomon/images/plotfft.tex +++ /dev/null @@ -1,89 +0,0 @@ -% -% Plot der Übertrangungsabfolge ins FFT und zurück mit IFFT -% -\begin{tikzpicture}[] - -%--------------------------------------------------------------- - %Knote -\matrix[draw = none, column sep=25mm, row sep=2mm]{ - \node(signal) [] { - \begin{tikzpicture} - \begin{axis} - [title = {\Large {Signal}}, - xlabel={Anzahl Übertragene Zahlen}, - xtick={0,20,40,64,80,98},] - \addplot[blue] table[col sep=comma] {papers/reedsolomon/images/signal.txt}; - \end{axis} - \end{tikzpicture}}; & - - \node(codiert) [] { - \begin{tikzpicture} - \begin{axis}[title = {\Large {Codiert}}] - \addplot[] table[col sep=comma] {papers/reedsolomon/images/codiert.txt}; - \end{axis} - \end{tikzpicture}}; \\ - - &\node(fehler) [] { - \begin{tikzpicture} - \begin{axis}[scale=0.6, title = {\Large {Fehler}}, - xtick={7,21,75}] - \addplot[red] table[col sep=comma] {papers/reedsolomon/images/fehler.txt}; - \end{axis} - \end{tikzpicture}};\\ - - \node(decodiert) [] { - \begin{tikzpicture} - \begin{axis}[title = {\Large {Decodiert}}] - \addplot[blue] table[col sep=comma] {papers/reedsolomon/images/decodiert.txt}; - \end{axis} - \end{tikzpicture}}; & - - \node(empfangen) [] { - \begin{tikzpicture} - \begin{axis}[title = {\Large {Empfangen}}] - \addplot[] table[col sep=comma] {papers/reedsolomon/images/empfangen.txt}; - \end{axis} - \end{tikzpicture}};\\ - - \node(syndrom) [] { - \begin{tikzpicture} - \begin{axis}[title = {\Large {Syndrom}}] - \addplot[blue] table[col sep=comma] {papers/reedsolomon/images/syndrom.txt}; - \end{axis} - \end{tikzpicture}}; & - - \node(locator) [] { - \begin{tikzpicture} - \begin{axis}[title = {\Large {Locator}}] - \addplot[] table[col sep=comma] {papers/reedsolomon/images/locator.txt}; - \end{axis} - \end{tikzpicture}};\\ -}; -%------------------------------------------------------------- - %FFT & IFFT deskription - -\draw[thin,gray,dashed] (0,12) to (0,-12); -\node(IFFT) [scale=0.7] at (0,12.3) {IFFT}; -\draw[<-](IFFT.south west)--(IFFT.south east); -\node(FFT) [scale=0.7, above of=IFFT] {FFT}; -\draw[->](FFT.north west)--(FFT.north east); - -\draw[thick, ->,] (fehler.west)++(-1,0) +(0.05,0.5) -- +(-0.1,-0.1) -- +(0.1,0.1) -- +(0,-0.5); -%Arrows -\draw[ultra thick, ->] (signal.east) to (codiert.west); -\draw[ultra thick, ->] (codiert.south) to (fehler.north); -\draw[ultra thick, ->] (fehler.south) to (empfangen.north); -\draw[ultra thick, ->] (empfangen.west) to (decodiert.east); -\draw[ultra thick, ->] (syndrom.east) to (locator.west); -\draw(decodiert.south east)++(-1.8,1) ellipse (1.3cm and 0.8cm) ++(-1.3,0) coordinate(zoom) ; -\draw[ultra thick, ->] (zoom) to[out=180, in=90] (syndrom.north); - -%item -\node[circle, draw, fill =lightgray] at (signal.north west) {1}; -\node[circle, draw, fill =lightgray] at (codiert.north west) {2}; -\node[circle, draw, fill =lightgray] at (fehler.north west) {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}; -\end{tikzpicture}
\ No newline at end of file diff --git a/buch/papers/reedsolomon/main.tex b/buch/papers/reedsolomon/main.tex index e68b947..017fe94 100644 --- a/buch/papers/reedsolomon/main.tex +++ b/buch/papers/reedsolomon/main.tex @@ -8,29 +8,9 @@ \begin{refsection} \chapterauthor{Joshua Bär und Michael Steiner} -Ein paar Hinweise für die korrekte Formatierung des Textes -\begin{itemize} -\item -Absätze werden gebildet, indem man eine Leerzeile einfügt. -Die Verwendung von \verb+\\+ ist nur in Tabellen und Arrays gestattet. -\item -Die explizite Platzierung von Bildern ist nicht erlaubt, entsprechende -Optionen werden gelöscht. -Verwenden Sie Labels und Verweise, um auf Bilder hinzuweisen. -\item -Beginnen Sie jeden Satz auf einer neuen Zeile. -Damit ermöglichen Sie dem Versionsverwaltungssysteme, Änderungen -in verschiedenen Sätzen von verschiedenen Autoren ohne Konflikt -anzuwenden. -\item -Bilden Sie auch für Formeln kurze Zeilen, einerseits der besseren -Übersicht wegen, aber auch um GIT die Arbeit zu erleichtern. -\end{itemize} - % Joshua \input{papers/reedsolomon/einleitung.tex} \input{papers/reedsolomon/idee.tex} -%\input{papers/reedsolomon/teil2.tex} \input{papers/reedsolomon/dtf.tex} % Michael @@ -49,6 +29,7 @@ Bilden Sie auch für Formeln kurze Zeilen, einerseits der besseren \nocite{reedsolomon:voyager} \nocite{reedsolomon:cd_wiki} \nocite{reedsolomon:cd} +\nocite{reedsolomon:strichepunkte} \nocite{reedsolomon:qr_wiki} \nocite{reedsolomon:qr} %\nocite{reedsolomon:mendezmueller} diff --git a/buch/papers/reedsolomon/packages.tex b/buch/papers/reedsolomon/packages.tex index b84e228..40c6ea3 100644 --- a/buch/papers/reedsolomon/packages.tex +++ b/buch/papers/reedsolomon/packages.tex @@ -10,3 +10,5 @@ \usepackage{pgfplots} \usepackage{filecontents} +\usepackage{xr} + diff --git a/buch/papers/reedsolomon/references.bib b/buch/papers/reedsolomon/references.bib index e0a75a8..b84b5a4 100644 --- a/buch/papers/reedsolomon/references.bib +++ b/buch/papers/reedsolomon/references.bib @@ -51,7 +51,7 @@ } @online{reedsolomon:cd, - title = {Funktionsweise des QR-Codes}, + title = {Abbildung einer CD}, url = {https://www.stickpng.com/img/electronics/compact-discs/stack-compact-disc}, date = {2021-07-19}, year = {2021}, @@ -59,6 +59,15 @@ day = {19} } +@online{reedsolomon:strichepunkte, + title = {Abbildung der Striche und Punkte einer CD}, + url = {https://www.researchgate.net/figure/The-readable-area-of-a-CD-is-magnified-in-order- to-see-the-pit-and-land-sizing-The_fig7_303401629}, + date = {2021-07-26}, + year = {2021}, + month = {7}, + day = {26} +} + @online{reedsolomon:qr_wiki, title = {Funktionsweise des QR-Codes}, url = {https://de.wikipedia.org/wiki/QR-Code}, diff --git a/buch/papers/reedsolomon/standalone.tex b/buch/papers/reedsolomon/standalone.tex new file mode 100644 index 0000000..c850d1f --- /dev/null +++ b/buch/papers/reedsolomon/standalone.tex @@ -0,0 +1,30 @@ +\documentclass{book} + +\input{common/packages.tex} + +% additional packages used by the individual papers, add a line for +% each paper +\input{papers/common/addpackages.tex} + +% workaround for biblatex bug +\makeatletter +\def\blx@maxline{77} +\makeatother +\addbibresource{chapters/references.bib} + +% Bibresources for each article +\input{papers/common/addbibresources.tex} + +% make sure the last index starts on an odd page +\AtEndDocument{\clearpage\ifodd\value{page}\else\null\clearpage\fi} +\makeindex + +%\pgfplotsset{compat=1.12} +\setlength{\headheight}{15pt} % fix headheight warning +\DeclareGraphicsRule{*}{mps}{*}{} + +\begin{document} + \input{common/macros.tex} + \def\chapterauthor#1{{\large #1}\bigskip\bigskip} + \input{papers/reedsolomon/main.tex} +\end{document} diff --git a/buch/papers/reedsolomon/standalone/standalone.pdf b/buch/papers/reedsolomon/standalone/standalone.pdf Binary files differnew file mode 100644 index 0000000..dc34b2d --- /dev/null +++ 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/experiments/codiert.txt b/buch/papers/reedsolomon/tikz/codiert.txt index 4a481d8..4a481d8 100644 --- a/buch/papers/reedsolomon/experiments/codiert.txt +++ b/buch/papers/reedsolomon/tikz/codiert.txt diff --git a/buch/papers/reedsolomon/experiments/decodiert.txt b/buch/papers/reedsolomon/tikz/decodiert.txt index f6221e6..f6221e6 100644 --- a/buch/papers/reedsolomon/experiments/decodiert.txt +++ b/buch/papers/reedsolomon/tikz/decodiert.txt diff --git a/buch/papers/reedsolomon/experiments/empfangen.txt b/buch/papers/reedsolomon/tikz/empfangen.txt index 38c13b0..38c13b0 100644 --- a/buch/papers/reedsolomon/experiments/empfangen.txt +++ b/buch/papers/reedsolomon/tikz/empfangen.txt diff --git a/buch/papers/reedsolomon/experiments/fehler.txt b/buch/papers/reedsolomon/tikz/fehler.txt index 23f1a83..23f1a83 100644 --- a/buch/papers/reedsolomon/experiments/fehler.txt +++ b/buch/papers/reedsolomon/tikz/fehler.txt diff --git a/buch/papers/reedsolomon/tikz/fourier.pdf b/buch/papers/reedsolomon/tikz/fourier.pdf Binary files differnew file mode 100644 index 0000000..a1b6e24 --- /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..af556d1 --- /dev/null +++ b/buch/papers/reedsolomon/tikz/fourier.tex @@ -0,0 +1,132 @@ +% +% 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}; +} + +\begin{document} +\begin{tikzpicture}[>=latex,thick] + +\draw[dashed,line width=2pt,color=lightgray] (2.6,4.4) -- (2.6,-14.3); +\coordinate (B) at (2.6,-1.3); +\node[color=gray] at (B) [rotate=90,above] {Zeitbereich}; +\node[color=gray] at (B) [rotate=90,below] {Frequenzbereich}; + +\begin{scope}[xshift=-\xverschiebung,yshift=0cm] + \begin{axis} + [title = {\large Signal\strut}, + xtick={0,32,64,96}, 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}[axis x line= none, axis y line*=right,ytick={0}, + width=\plotwidth,height=\plotheight] + \addplot[color=white] {0}; + \end{axis} + + \begin{axis}[title = {\large Codiert\strut}, axis y line*=left, + xtick={0,32,64,96}, + 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}, + 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 Fehler}\strut}, + xtick={0,96}, + 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}, + 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}, + width=\plotwidth,height=\plotheight] + \addplot[color=black!60,line width=1pt] {0.3}; + \end{axis} + \begin{axis}[title = {\large Locator\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/experiments/locator.txt b/buch/papers/reedsolomon/tikz/locator.txt index b28988c..b28988c 100644 --- a/buch/papers/reedsolomon/experiments/locator.txt +++ b/buch/papers/reedsolomon/tikz/locator.txt diff --git a/buch/papers/reedsolomon/tikz/plotfft.tex b/buch/papers/reedsolomon/tikz/plotfft.tex new file mode 100644 index 0000000..77c4dc3 --- /dev/null +++ b/buch/papers/reedsolomon/tikz/plotfft.tex @@ -0,0 +1,104 @@ +% +% 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} + + + +\begin{document} +\begin{tikzpicture}[] + + %--------------------------------------------------------------- + %Knote + \matrix(m) [draw = none, column sep=25mm, row sep=2mm]{ + + \node(signal) [] { + \begin{tikzpicture} + \begin{axis} + [title = {\Large {Signal}}, + xtick={0,20,40,64,80,98}] + \addplot[blue] table[col sep=comma] {tikz/signal.txt}; + \end{axis} + \end{tikzpicture}}; & + + \node(codiert) [] { + \begin{tikzpicture}[] + % Beschriftung Rechts + \begin{axis}[axis x line= none, axis y line*=right,ytick={0}] + \addplot[color=white] {0}; + \end{axis} + + \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}}; \\ + + \node(decodiert) [] { + \begin{tikzpicture} + \begin{axis}[title = {\Large {Decodiert}}] + \addplot[blue] table[col sep=comma] {tikz/decodiert.txt}; + \end{axis} + \end{tikzpicture}}; & + + \node(empfangen) [] { + \begin{tikzpicture} + \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}};\\ + + \node(syndrom) [] { + \begin{tikzpicture} + \begin{axis}[title = {\Large {Syndrom}}] + \addplot[black] table[col sep=comma] {tikz/syndrom.txt}; + \end{axis} + \end{tikzpicture}}; & + + \node(locator) [] { + \begin{tikzpicture} + % 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}};\\ + }; + %------------------------------------------------------------- + %FFT & IFFT deskription + + \draw[thin,gray,dashed] (0,9) to (0,-9); + \node(IFFT) [scale=0.9] at (0,9.3) {IFFT}; + \draw[stealth-](IFFT.south west)--(IFFT.south east); + \node(FFT) [scale=0.9, above of=IFFT] {FFT}; + \draw[-stealth](FFT.north west)--(FFT.north east); + + %Arrows + \draw[thick, ->] (signal.east) to (codiert.west); + \draw[thick, ->] (codiert.south) to (empfangen.north); + \draw[thick, ->] (empfangen.west) to (decodiert.east); + \draw[thick, ->] (syndrom.east) to (locator.west); + \draw[thick](decodiert.south east)++(-1.8,1) ellipse (1.3cm and 0.8cm) ++(-1.3,0) coordinate(zoom) ; + \draw[thick, ->] (zoom) to[out=180, in=90] (syndrom.north); + + %item + \node[circle, draw, fill =lightgray] at (signal.north west) {1}; + \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 new file mode 100644 index 0000000..db35734 --- /dev/null +++ b/buch/papers/reedsolomon/tikz/plotfftraw.tex @@ -0,0 +1,81 @@ + +\begin{tikzpicture}[] + + %--------------------------------------------------------------- + %Knote + \matrix(m) [draw = none, column sep=25mm, row sep=2mm]{ + + \node(signal) [] { + \begin{tikzpicture} + \begin{axis} + [title = {\Large {Signal}}, + xtick={0,20,40,64,80,98}] + \addplot[blue] table[col sep=comma] {tikz/signal.txt}; + \end{axis} + \end{tikzpicture}}; & + + \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}; + \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}}; \\ + + \node(decodiert) [] { + \begin{tikzpicture} + \begin{axis}[title = {\Large {Decodiert}}] + \addplot[blue] table[col sep=comma] {tikz/decodiert.txt}; + \end{axis} + \end{tikzpicture}}; & + + \node(empfangen) [] { + \begin{tikzpicture} + \begin{axis}[title = {\Large {Empfangen}}] + \addplot[green] table[col sep=comma] {tikz/empfangen.txt}; + \end{axis} + \end{tikzpicture}};\\ + + \node(syndrom) [] { + \begin{tikzpicture} + \begin{axis}[title = {\Large {Syndrom}}] + \addplot[black] table[col sep=comma] {tikz/syndrom.txt}; + \end{axis} + \end{tikzpicture}}; & + + \node(locator) [] { + \begin{tikzpicture} + \begin{axis}[title = {\Large {Locator}}] + \addplot[gray] table[col sep=comma] {tikz/locator.txt}; + \end{axis} + \end{tikzpicture}};\\ + }; + %------------------------------------------------------------- + %FFT & IFFT deskription + + \draw[thin,gray,dashed] (0,9) to (0,-9); + \node(IFFT) [scale=0.9] at (0,9.3) {IFFT}; + \draw[stealth-](IFFT.south west)--(IFFT.south east); + \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); + \draw[thick, ->] (empfangen.west) to (decodiert.east); + \draw[thick, ->] (syndrom.east) to (locator.west); + \draw[thick](decodiert.south east)++(-1.8,1) ellipse (1.3cm and 0.8cm) ++(-1.3,0) coordinate(zoom) ; + \draw[thick, ->] (zoom) to[out=180, in=90] (syndrom.north); + + %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}; +\end{tikzpicture}
\ No newline at end of file diff --git a/buch/papers/reedsolomon/tikz/polynom2.tex b/buch/papers/reedsolomon/tikz/polynom2.tex new file mode 100644 index 0000000..80557fb --- /dev/null +++ b/buch/papers/reedsolomon/tikz/polynom2.tex @@ -0,0 +1,60 @@ +% polynome +%------------------- + +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{times} +\usepackage{pgfplots} + + +\begin{document} +% Teiler für das Skalieren der Grafik /40 +\newcommand{\teiler}{40} + + +%////////////////////////////////////// + +\begin{tikzpicture}[>=latex,thick,] + \draw[color=blue, line width=1.4pt] + plot[domain=0:8, samples=100] + ({\x},{(2*\x^2+1*\x+5)/\teiler}); + + \draw[->] (-0.2,0) -- (8,0) coordinate[label={$x$}]; + \draw[->] (0,-0.2) -- (0,150/\teiler) coordinate[label={right:$p(x)$}]; + + \def\punkt#1{ + \fill[color=green] #1 circle[radius=0.08]; + \draw #1 circle[radius=0.07]; + } + + \def\hellpunkt#1{ + \fill[color=lightgray] #1 circle[radius=0.08]; + \draw[gray] #1 circle[ radius=0.07]; + } + + \draw[color=gray,line width=1pt,dashed] + plot[domain=0.5:7, samples=100] + ({\x},{(7.832*\x^2-51.5*\x+121.668)/\teiler}); + + + \punkt{(1,8/\teiler)} + \hellpunkt{(2,15/\teiler)} + \hellpunkt{(3,26/\teiler)} + \punkt{(4,41/\teiler)} + \punkt{(5,60/\teiler)} + \punkt{(6,83/\teiler)} + \punkt{(7,110/\teiler)} + + + + \def\erpunkt#1{ + \fill[color=red] #1 circle[radius=0.08]; + \draw #1 circle[radius=0.07]; + } + \erpunkt{(2,50/\teiler)} + \erpunkt{(3,37.66/\teiler)} + + \draw(0,100/\teiler) -- (-0.1,100/\teiler) coordinate[label={left:$100$}]; + \draw(1,0) -- (1,-0.1) coordinate[label={below:$1$}]; +\end{tikzpicture} +\end{document} diff --git a/buch/papers/reedsolomon/images/polynom2.tex b/buch/papers/reedsolomon/tikz/polynomraw.tex index 288b51c..02968fd 100644 --- a/buch/papers/reedsolomon/images/polynom2.tex +++ b/buch/papers/reedsolomon/tikz/polynomraw.tex @@ -1,12 +1,11 @@ -% polynome -%------------------- -% Teiler für das Skalieren der Grafik /40 +% polynomraw + \newcommand{\teiler}{40} %////////////////////////////////////// -\begin{tikzpicture}[>=latex,thick] +\begin{tikzpicture}[>=latex,thick,] \draw[color=blue, line width=1.4pt] plot[domain=0:8, samples=100] ({\x},{(2*\x^2+1*\x+5)/\teiler}); @@ -21,9 +20,14 @@ \def\hellpunkt#1{ \fill[color=lightgray] #1 circle[radius=0.08]; - \draw #1 circle[radius=0.07]; + \draw[gray] #1 circle[ radius=0.07]; } + \draw[color=gray,line width=1pt,dashed] + plot[domain=0.5:7, samples=100] + ({\x},{(7.832*\x^2-51.5*\x+121.668)/\teiler}); + + \punkt{(1,8/\teiler)} \hellpunkt{(2,15/\teiler)} \hellpunkt{(3,26/\teiler)} @@ -32,9 +36,7 @@ \punkt{(6,83/\teiler)} \punkt{(7,110/\teiler)} - \draw[color=gray,line width=1pt,dashed] - plot[domain=0.5:7, samples=100] - ({\x},{(7.832*\x^2-51.5*\x+121.668)/\teiler}); + \def\erpunkt#1{ \fill[color=red] #1 circle[radius=0.08]; @@ -45,5 +47,4 @@ \draw(0,100/\teiler) -- (-0.1,100/\teiler) coordinate[label={left:$100$}]; \draw(1,0) -- (1,-0.1) coordinate[label={below:$1$}]; -\end{tikzpicture} -%\end{document} +\end{tikzpicture}
\ No newline at end of file diff --git a/buch/papers/reedsolomon/experiments/signal.txt b/buch/papers/reedsolomon/tikz/signal.txt index c4fa5f8..c4fa5f8 100644 --- a/buch/papers/reedsolomon/experiments/signal.txt +++ b/buch/papers/reedsolomon/tikz/signal.txt diff --git a/buch/papers/reedsolomon/experiments/syndrom.txt b/buch/papers/reedsolomon/tikz/syndrom.txt index 8ca9eed..8ca9eed 100644 --- a/buch/papers/reedsolomon/experiments/syndrom.txt +++ b/buch/papers/reedsolomon/tikz/syndrom.txt diff --git a/buch/papers/reedsolomon/images/codiert.txt b/buch/papers/reedsolomon/tikz/tikz/codiert.txt index 4a481d8..4a481d8 100644 --- a/buch/papers/reedsolomon/images/codiert.txt +++ b/buch/papers/reedsolomon/tikz/tikz/codiert.txt diff --git a/buch/papers/reedsolomon/images/decodiert.txt b/buch/papers/reedsolomon/tikz/tikz/decodiert.txt index f6221e6..f6221e6 100644 --- a/buch/papers/reedsolomon/images/decodiert.txt +++ b/buch/papers/reedsolomon/tikz/tikz/decodiert.txt diff --git a/buch/papers/reedsolomon/images/empfangen.txt b/buch/papers/reedsolomon/tikz/tikz/empfangen.txt index 38c13b0..38c13b0 100644 --- a/buch/papers/reedsolomon/images/empfangen.txt +++ b/buch/papers/reedsolomon/tikz/tikz/empfangen.txt diff --git a/buch/papers/reedsolomon/images/fehler.txt b/buch/papers/reedsolomon/tikz/tikz/fehler.txt index 23f1a83..23f1a83 100644 --- a/buch/papers/reedsolomon/images/fehler.txt +++ b/buch/papers/reedsolomon/tikz/tikz/fehler.txt diff --git a/buch/papers/reedsolomon/images/locator.txt b/buch/papers/reedsolomon/tikz/tikz/locator.txt index b28988c..b28988c 100644 --- a/buch/papers/reedsolomon/images/locator.txt +++ b/buch/papers/reedsolomon/tikz/tikz/locator.txt diff --git a/buch/papers/reedsolomon/images/signal.txt b/buch/papers/reedsolomon/tikz/tikz/signal.txt index c4fa5f8..c4fa5f8 100644 --- a/buch/papers/reedsolomon/images/signal.txt +++ b/buch/papers/reedsolomon/tikz/tikz/signal.txt diff --git a/buch/papers/reedsolomon/images/syndrom.txt b/buch/papers/reedsolomon/tikz/tikz/syndrom.txt index 8ca9eed..8ca9eed 100644 --- a/buch/papers/reedsolomon/images/syndrom.txt +++ b/buch/papers/reedsolomon/tikz/tikz/syndrom.txt |
