diff options
Diffstat (limited to '')
| -rw-r--r-- | buch/papers/reedsolomon/dtf.tex | 42 | ||||
| -rw-r--r-- | buch/papers/reedsolomon/figures/polynom2.pdf | bin | 20327 -> 20317 bytes | |||
| -rw-r--r-- | buch/papers/reedsolomon/idee.tex | 73 | ||||
| -rw-r--r-- | buch/papers/reedsolomon/packages.tex | 2 | ||||
| -rw-r--r-- | buch/papers/reedsolomon/standalone/standalone.pdf | bin | 1828186 -> 1835615 bytes | |||
| -rw-r--r-- | buch/papers/reedsolomon/tikz/polynom2.tex | 11 |
6 files changed, 79 insertions, 49 deletions
diff --git a/buch/papers/reedsolomon/dtf.tex b/buch/papers/reedsolomon/dtf.tex index 73d0d12..e9aacfb 100644 --- a/buch/papers/reedsolomon/dtf.tex +++ b/buch/papers/reedsolomon/dtf.tex @@ -3,57 +3,65 @@ % % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil % -\section{Diskrete Fourier Transformation +\section{Übertragung mit hilfe der Diskrete 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 gebrauchfür den Reed-Solomon-Code. +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. \subsection{Diskrete Fourietransformation Zusamenhang \label{reedsolomon:subsection:dtfzusamenhang}} -Die Diskrete Fourietransformation ist definiert als +Mit hilfe der Fourietransformation 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. +Nun zur definition der Diskrete Fourietransformation, diese ist definiert als \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} - wenn man nun \begin{equation} w = e^{-\frac{2\pi j}{N} k} \label{reedsolomon:DFT_summand} \end{equation} - ersetzte, und $N$ konstantbleibt, erhält man \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} \end{equation} - was überaust ähnlich zu unserem Polynomidee ist. -\subsection{Übertragungsabfolge + +\subsection{Beispiel \label{reedsolomon:subsection:Übertragungsabfolge}} -Der Auftrag ist nun 64 Daten zu übertragen und nach 16 Fehler abzusicheren, -16 Fehler erkennen und rekonstruieren. +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. +und hier werden die einzelne Schritte erklärt: \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. +(siehe Abschnitt \externaldocument{papers/reedsolomon/idee}\ref{reedsolomon:section:Fehlerkorrekturstellen}) +Die 32 Fehlerkorrekturstellen werden als Null Übertragen +\item Nun wurde mittels der diskreten Fourientransformation diese 96 codiert. +Das heisst alle Informationen ist in alle Zahlenvorhanden. (Auch die Fehlerkorrekturstellen Null) +\item Nun kommen drei Fehler dazu an den Übertragungsstellen 7, 21 und 75.(die Skala ist Rechts) +Die Fehler können auf den ganzen 96 Übertragungswerten liegen, wie die 75 zeigt. +\item Dieses wird nun Empfangen und mittels inversen diskreten Fourientransormation, wieder rücktransformiert.(Iklusive der Fehler) +\item Nun sieht man den Fehler im Decodieren in den Übertragungsstellen 64 bis 96, da es dort nicht mehr Null ist. +\item Nimmt man nun nur diese Stellen 64 bis 96, dies definieren wir als Syndrom, und transformiert nur dieses Syndrom. +\item Bekommt man die Fehlerstellen wieder, zwar nichtso genau, dennoch erkennt man wo die Fehler stattgefunden haben. +Dies definieren wir als Locator. \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} \centering diff --git a/buch/papers/reedsolomon/figures/polynom2.pdf b/buch/papers/reedsolomon/figures/polynom2.pdf Binary files differindex dd6cdd3..55a50ac 100644 --- a/buch/papers/reedsolomon/figures/polynom2.pdf +++ b/buch/papers/reedsolomon/figures/polynom2.pdf diff --git a/buch/papers/reedsolomon/idee.tex b/buch/papers/reedsolomon/idee.tex index 519e642..8ad3d27 100644 --- a/buch/papers/reedsolomon/idee.tex +++ b/buch/papers/reedsolomon/idee.tex @@ -1,5 +1,5 @@ % -% idee.tex -- Beispiel-File für das Paper +% idee.tex -- Polynom Idee % % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil % @@ -14,15 +14,19 @@ 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. -Der unterschied des Fehler erkennen und korrigiren, ist das beim Erkennen nur die Frage kommt hat es Fehler oder keine, -beim korrigieren muss man den Fehler erkennun und dann zusätzlich noch den original Wert rekonstruieren. -Auch eine variante wäre es die Daten nach einem Fehler einfach nochmals zu senden, was bei Reed-Solomon-Code-Anwendungen nicht immer sinnvolll ist. \ref(reedsolomon:section:anwendung) +Der unterschied des Fehler erkennen und korrigiren, ist das beim Erkennen nur die Frage beantwortet wird mit: Ist die Übertragung fehlerhaft oder nicht? +Beim Korrigieren werden Fehler erkennt und dann zusätzlich noch den original Wert rekonstruieren. +Auch eine Variante wäre es die Daten nach einem Fehler nachdem Fehlerhaften senden, nochmals versenden(auch hier wieder doppelt und dreifach Sendung), +was bei Reed-Solomon-Code-Anwendungen nicht immer sinnvoll ist. +\externaldocument{papers/reedsolomon/anwendungen} +\ref{reedsolomon:section:anwendung} +\subsection{Polynom-Ansatz +\label{reedsolomon:section:polynomansatz}} \rhead{Polynom-Ansatz} -Eine Idee ist aus den Daten -ein Polynom zu bilden. +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 Beispiel die Zahlen \textcolor{blue}{2}, \textcolor{blue}{1}, \textcolor{blue}{5}, +\begin{beispiel} Nehmen wir die Zahlen \textcolor{blue}{2}, \textcolor{blue}{1}, \textcolor{blue}{5}, welche uns dann das Polynom \begin{equation} p(x) @@ -31,7 +35,8 @@ p(x) \label{reedsolomon:equation1} \end{equation} ergeben. -Übertragen werden nun die Werte dieses Polynomes an den Stellen 1, 2, 3\dots 7 dieses Polynomes. +Ü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}, @@ -39,9 +44,11 @@ mit den Punkten, $p(1),p(2),...,p(7) = (\textcolor{darkgreen}{8}, \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 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} -\subsection{Beispiel} -Für das Beispiel aus der Gleichung \eqref{reedsolomon:equation1}, +\begin{beispiel} +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. @@ -51,29 +58,40 @@ 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. +Da das Konkurenzpolynom, grau gestrichelt in Abbildung \ref{fig:polynom}, das orginal fehlleited. +Um das Konkurenzpolynom auszuschliessen, währen mehr \textcolor{darkgreen}{Übertragungspunkte} nötig. +\end{beispiel} \begin{figure} \centering \includegraphics[width=\textwidth]{papers/reedsolomon/figures/polynom2} - %\input{papers/reedsolomon/images/polynom2.tex} - \caption{Polynom $p(x)$ \eqref{reedsolomon:equation1}} + %\input{papers/reedsolomon/tikz/polynom2.tex} + \caption{Polynom $p(x)$ von der Gleichung\eqref{reedsolomon:equation1}} \label{fig:polynom} \end{figure} -\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. +\section{Fehlerkorekturstellen bestimmen +\label{reedsolomon:section:Fehlerkorrekturstellen}} +Um zu bestimmen wieviel zusätzliche \textcolor{darkgreen}{Übertragungspunkte} notwendig sind, die dann Fehler 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 Polynomgraden, 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 7 \textcolor{darkgreen}{Übertragungspunkte} senden. +Durch 3 Punkte wird das Polyom eindeutig bestimmt, nun haben wir mehrere Konkurenzpolynome, doch mit maximal 2 Fehler liegen auf einem Konkurenzpolynom, +maximal 4 Punkte und auf unserem orginal 5 Punkte. Ansonsten hatt es mehr Fehler oder unser Konkurenzpolynom ist das gleiche wie das Original. +Somit können wir nun bestimmen, dass von den \textcolor{darkgreen}{7 Übertragungspunkten$u$} bis zu 2 Fehler korrigiert werden können und 4 Übertragungspunkte zusätzlich gesendet werden müssen. +\end{beispiel} +Durch das erkennen des Schemas in der Tabelle\ref{tabel:fehlerkorrekturstellen} +\begin{equation} + \frac{\textcolor{darkgreen}{u}-\textcolor{blue}{k}}{\textcolor{red}{t}} + =2 + \label{reedsolomon:equation2} +\end{equation} +zeigt sich das es $k+2t$ Übertragungspunkte braucht. \begin{center} - \begin{tabular}{ c c c } + \begin{tabular}{ c c | c} \hline Nutzlas & Fehler & Übertragen \\ \hline @@ -84,12 +102,11 @@ $k+2t$ Punkte übertragen werden müssen. $k$ & $t$ & $k+2t$ Werte eines Polynoms vom Grad $k-1$ \\ \hline \end{tabular} + Fehlerkorrekturstellen Bestimmung TODO: Tabellenreferenz + \label{tabel:fehlerkorrekturstellen} \end{center} -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. +Ein Nebeneffekt ist das 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. 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/standalone/standalone.pdf b/buch/papers/reedsolomon/standalone/standalone.pdf Binary files differindex a984f35..1f2f0b9 100644 --- a/buch/papers/reedsolomon/standalone/standalone.pdf +++ b/buch/papers/reedsolomon/standalone/standalone.pdf diff --git a/buch/papers/reedsolomon/tikz/polynom2.tex b/buch/papers/reedsolomon/tikz/polynom2.tex index 456e067..47dc679 100644 --- a/buch/papers/reedsolomon/tikz/polynom2.tex +++ b/buch/papers/reedsolomon/tikz/polynom2.tex @@ -29,9 +29,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)} @@ -40,9 +45,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]; |