diff options
Diffstat (limited to '')
| -rw-r--r-- | buch/papers/reedsolomon/codebsp.tex | 106 | ||||
| -rw-r--r-- | buch/papers/reedsolomon/decmitfehler.tex | 293 | ||||
| -rw-r--r-- | buch/papers/reedsolomon/decohnefehler.tex | 54 | ||||
| -rw-r--r-- | buch/papers/reedsolomon/endlichekoerper.tex | 6 | ||||
| -rw-r--r-- | buch/papers/reedsolomon/hilfstabellen.tex | 19 | ||||
| -rw-r--r-- | buch/papers/reedsolomon/main.tex | 7 | ||||
| -rw-r--r-- | buch/papers/reedsolomon/nachschlagewerk.tex | 4 | ||||
| -rw-r--r-- | buch/papers/reedsolomon/references.bib | 69 | ||||
| -rw-r--r-- | buch/papers/reedsolomon/rekonstruktion.tex | 33 | ||||
| -rw-r--r-- | buch/papers/reedsolomon/restetabelle1.tex | 190 | ||||
| -rw-r--r-- | buch/papers/reedsolomon/restetabelle2.tex | 192 |
11 files changed, 748 insertions, 225 deletions
diff --git a/buch/papers/reedsolomon/codebsp.tex b/buch/papers/reedsolomon/codebsp.tex index 5b67c43..262297e 100644 --- a/buch/papers/reedsolomon/codebsp.tex +++ b/buch/papers/reedsolomon/codebsp.tex @@ -8,19 +8,35 @@ \rhead{Koerper Festlegen} Um die Funktionsweise eines Reed-Solomon-Codes besser zu verstehen werden wir die einzelnen Probleme und ihre Lösungen anhand eines Beispiels betrachten. -Da wir in Endlichen Körpern Rechnen werden wir zuerst solch ein Körper festlegen. Dabei müssen wir die \textcolor{red}{Definition 4.6} berücksichtigen, die besagt, dass nur Primzahlen für endliche Körper in Frage kommen. -Wir legen für unser Beispiel den endlichen Körper $q = 11$ fest. -Alle folgenden Berechnungen wurden mit den beiden Restetabellen \textcolor{red}{xx} und \textcolor{red}{yy} durchgeführt. -Aus den Tabellen folgt auch, dass uns nur die Zahlen \[\mathbb{F}_{11} = \{0,1,2,3,4,5,6,7,8,9,10\}\] zur Verfügung stehen. +Da wir in Endlichen Körpern Rechnen werden wir zuerst solch einen Körper festlegen. Dabei müssen wir die \textcolor{red}{Definition 4.6 (wie verweist man auf eine definition?)} berücksichtigen, die besagt, dass nur Primzahlen für endliche Körper in Frage kommen. +Wir legen für unser Beispiel den endlichen Körper mit $q = 11$ fest. +Zur Hilfestellung können dazu die beiden Tabellen \ref{reedsolomon:subsection:adtab} und +\ref{reedsolomon:subsection:mptab} hinzugezogen werden. Diese Tabellen enthalten sämtliche Resultate aller gültigen Operationen \textcolor{red}{(Notiz: nach meinem Wissen gibt es ja nur addition und multiplikation als gültige operationen)}, die in diesem Körper durchgeführt werden können. +Aus der Definition der Endlichen Körper (ersichtlich auch in den Tabellen) folgt, dass uns nur die Zahlen \[\mathbb{F}_{11} = \{0,1,2,3,4,5,6,7,8,9,10\}\] zur verfügung stehen und somit $11 = 0$ gelten muss. + +% OLD TEXT +%Alle folgenden Berechnungen wurden mit den beiden Restetabellen \ref{reedsolomon:subsection:adtab} und \ref{reedsolomon:subsection:mptab} durchgeführt. +%Aus den Tabellen folgt auch, dass uns nur die Zahlen \[\mathbb{F}_{11} = \{0,1,2,3,4,5,6,7,8,9,10\}\] zur Verfügung stehen. % die beiden Restetabellen von F_11 %\input{papers/reedsolomon/restetabelle1} %\input{papers/reedsolomon/restetabelle2} -Die grösse des endlichen Körpers legt auch fest, wie gross unsere Nachricht $n$ bestehend aus Nutzdatenteil und Fehlerkorrekturteil sein kann und beträgt in unserem Beispiel +Anhand der Menge uns zur Verfügung stehenden Zahlen wird auch festgelegt, wie viele Zahlen ein Nachrichtenblock $n$, bestehend aus Nutzdatenteil und Fehlerkorrekturteil, umfassen kann. +Der Nachrichtenblock im Beispiel besteht aus \[ -n = q - 1 = 10 \text{ Zahlen}. +n = q - 1 = 10 \text{ Zahlen}, \] +wobei die null weggelassen wird. Wenn wir versuchen würden, mit der null zu codieren, so stellen wir fest, dass wir wieder null an der gleichen Stelle erhalten und somit wäre die Codierung nicht eindeutig. + +% Notes +%Da bei allen Codes, die codiert werden wird an der gleichen Stelle eine Nullstelle auftreten. + +% Old Text +%Die grösse des endlichen Körpers legt auch fest, wie gross unsere Nachricht $n$ bestehend aus Nutzdatenteil und Fehlerkorrekturteil sein kann und beträgt in unserem Beispiel +%\[ +%n = q - 1 = 10 \text{ Zahlen}. +%\] Im nächsten Schritt bestimmen wir, wie viele Fehler $t$ maximal während der Übertragung auftreten dürfen, damit wir sie noch korrigieren können. Unser Beispielcode sollte in der Lage sein @@ -29,42 +45,60 @@ t = 2 \] Fehlerstellen korrigieren zu können. -Die Grösse des Nutzdatenteils hängt von der Grösse der Nachricht sowie der Anzahl der Fehlerkorrekturstellen. Je robuster der Code sein muss, desto weniger Platz für Nutzdaten $k$ bleibt in der Nachricht übrig. +Die Grösse des Nutzdatenteils hängt von der Grösse des Nachrichtenblocks sowie der Anzahl der Fehlerkorrekturstellen ab. Je robuster der Code sein muss, desto weniger Platz für Nutzdaten $k$ bleibt in der Nachricht übrig. Bei maximal 2 Fehler können wir noch \[ k = n - 2t = 6\text{ Zahlen} \] übertragen. -Zusammenfassend haben wir einen Codeblock mit der Länge von 10 Zahlen definiert, der 6 Zahlen als Nutzlast beinhaltet und in der Lage ist aus 2 fehlerhafte Stellen im Block die ursprünglichen Nutzdaten rekonstruieren kann. Zudem werden wir im weiteren feststellen, dass dieser Code maximal 4 Fehlerstellen erkennen, diese aber nicht rekonstruieren kann. +Zusammenfassend haben wir einen Nachrichtenblock mit der Länge von 10 Zahlen definiert, der 6 Zahlen als Nutzlast beinhaltet und in der Lage ist aus 2 fehlerhafte Stellen im Block die ursprünglichen Nutzdaten zu rekonstruieren. Zudem werden wir im weiteren feststellen, dass dieser Code maximal vier Fehlerstellen erkennen, diese aber nicht rekonstruieren kann. Wir legen nun die Nachricht \[ m = [0,0,0,0,4,7,2,5,8,1] \] -fest, die wir gerne an einen Empfänger übertragen möchten, wobei die vorderen vier Nullstellen für die Fehlerkorrektur zuständig sind. -Die Nachricht können wir auch als Polynom +fest, die wir gerne an einen Empfänger übertragen möchten, wobei die vorderen vier Stellen für die Fehlerkorrektur zuständig sind. +Solange diese Stellen vor dem Codieren und nach dem Decodieren den Wert null haben, so ist die Nachricht Fehlerfrei übertragen worden. + +Da wir in den folgenden Abschnitten mit Polynomen arbeiten, stellen wir die Nachicht auch noch als Polynom \[ m(X) = 4X^5 + 7X^4 + 2X^3 + 5X^2 + 8X + 1 \] -darstellen. +dar. + +% Old Text +%Die Nachricht können wir auch als Polynom +%\[ +%m(X) = 4X^5 + 7X^4 + 2X^3 + 5X^2 + 8X + 1 +%\] +%darstellen. \subsection{Der Ansatz der diskreten Fouriertransformation \label{reedsolomon:subsection:diskFT}} -In einem vorherigen Kapitel (???) 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 $\mathrm{e}$ in $\mathbb{F}_{11}$ nicht existiert. -Wir suchen also eine Zahl $a^i$, die in endlichen Körpern existiert und den gesamten Zahlenbereich von $\mathbb{F}_{11}$ abdecken kann. -Dazu schreiben wir +In einem vorherigen Kapitel \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. +Wir legen deshalb die Zahl $a$ fest. Diese Zahl soll die gleichen aufgaben haben, wie $e^{\frac{j}{2 \pi}}$ in der Diskreten Fouriertransformation, nur mit dem Unterschied, dass $a$ in $\mathbb{F}_{11}$ existiert. Dazu soll $a$ den gesamten Zahlenbereich von $\mathbb{F}_{11}$ abdecken, um \[ \mathbb{F}_{11} = \{0,1,2,3,4,5,6,7,8,9,10\} \] -um in +in \[ \mathbb{Z}_{11}\setminus\{0\} = \{a^0, a^1, a^2, a^3, a^4, a^5, a^6, a^7, a^8, a^9\}. \] - -Wenn wir alle möglichen Werte für $a$ einsetzen, also - +umzuschreiben. +% Old Text +%Wir suchen also eine Zahl $a$, die in endlichen Körpern existiert und den gesamten Zahlenbereich von $\mathbb{F}_{11}$ abdecken kann. +%Dazu schreiben wir +%\[ +%\mathbb{F}_{11} = \{0,1,2,3,4,5,6,7,8,9,10\} +%\] +%um in +%\[ +%\mathbb{Z}_{11}\setminus\{0\} = \{a^0, a^1, a^2, a^3, a^4, a^5, a^6, a^7, a^8, a^9\}. +%\] +% +%Wenn wir alle möglichen Werte für $a$ einsetzen, also %\begin{align} %a = 0 : \qquad \mathbb{Z}_{11}\setminus\{0\} = \{0, 0, 0, 0, 0, 0, 0, 0, 0, 0\} \\ %a = 1 : \qquad \mathbb{Z}_{11}\setminus\{0\} = \{1, 1, 1, 1, 1, 1, 1, 1, 1, 1\} \\ @@ -79,6 +113,10 @@ Wenn wir alle möglichen Werte für $a$ einsetzen, also %a = 10 : \qquad \mathbb{Z}_{11}\setminus\{0\} = \{1, 10, 1, 10, 1, 10, 1, 10, 1, 10\} %\end{align} +\subsubsection{Die primitiven Einheitswurzeln + \label{reedsolomon:subsection:primsqrt}} + +Wenn wir jetzt sämtliche Zahlen von $\mathbb{F}_{11}$ in $a$ einsetzen \begin{center} \begin{tabular}{c r c l} %$a = 0 :$& $\qquad \mathbb{Z}_{11}\setminus\{0\}$ &$=$& $\{0, 0, 0, 0, 0, 0, 0, 0, 0, 0\}$ \\ @@ -94,21 +132,30 @@ $a = 9 :$& $\qquad \mathbb{Z}_{11}\setminus\{0\}$ &$=$& $\{1, 9, 4, 3, 5, 1, 9, $a = 10 :$& $\qquad \mathbb{Z}_{11}\setminus\{0\}$ &$=$& $\{1, 10, 1, 10, 1, 10, 1, 10, 1, 10\}$ \end{tabular} \end{center} +so fällt uns auf, dass für $a$ die Zahlen $2,6,7,8$ erhalten, die tatsächlich den gesamten Zahlenraum von $\mathbb{F}_{11}$ abbilden. Solche Zahlen werden \em Primitive Einheitswurzel \em genannt. +Wenden wir diese Vorgehensweise auch für andere Endliche Körper an, so werden wir sehen, dass wir immer mindestens zwei solcher Einheitswurzel finden werden. Somit ist es uns überlassen, eine dieser Einheitswurzeln auszuwählen, mit der wir weiter rechnen wollen. Für das Beispiel wählen wir die Zahl $a^i = 8$. -so fällt uns auf, dass die Zahlen $2,6,7,8$ tatsächlich den gesamten Zahlenraum von $\mathbb{F}_{11}$ abbilden. Solche Zahlen werden \em Primitive Einheitswurzel \em genannt. -Für das Beispiel wählen wir die Zahl $a^i = 8$. -Damit wir unsere Nachricht codieren können, müssen wir $8^i$ in $m(X)$ einsetzen. +\subsubsection{Bildung einer Transformationsmatrix + \label{reedsolomon:subsection:transMat}} +Mit der Wahl einer Einheitswurzel ist es uns jetzt möglich, unsere Nachricht zu Codieren. Daraus sollen wir dann einen Übertragungsvektor $v$ erhalten, den wir an den Empfänger schicken können. Für die Codierung müssen wir alle $a^i$ in das Polynom $m(X)$ einsetzen. Da wir $a^i = 8^i$ gewählt haben ergibt sich daraus +% +%Damit wir unsere Nachricht codieren können, müssen wir $8^i$ in $m(X)$ einsetzen. +% \begin{center} \begin{tabular}{c} - $m(8^0) = 4 \cdot 1 + 7 \cdot 1 + 2 \cdot 1 + 5 \cdot 1 + 8 \cdot 1 + 1 = 5$ \\ - $m(8^1) = 4 \cdot 8 + 7 \cdot 8 + 2 \cdot 8 + 5 \cdot 8 + 8 \cdot 8 + 1 = 3$ \\ - \vdots + $m(8^0) = 4 \cdot 1^5 + 7 \cdot 1^4 + 2 \cdot 1^3 + 5 \cdot 1^2 + 8 \cdot 1^1 + 1 = 5$ \\ + $m(8^1) = 4 \cdot 8^5 + 7 \cdot 8^4 + 2 \cdot 8^3 + 5 \cdot 8^2 + 8 \cdot 8^1 + 1 = 3$ \\ + \vdots \\ + $m(8^9) = 4 \cdot 7^5 + 7 \cdot 7^4 + 2 \cdot 7^3 + 5 \cdot 7^2 + 8 \cdot 7^1 + 1 = 4$ \end{tabular} \end{center} +unser Übertragungsvektor. Um das ganze noch ein wenig übersichtlicher zu gestalten können wir die Polynome zu einer Matrix zusammenfassen und bildet so unsere Transformationsmatrix $A$. + +\subsection{Allgemeine Codierung + \label{reedsolomon:subsection:algCod}} -Für eine elegantere Formulierung stellen wir das ganze als Matrix dar, wobei $m$ unser Nachrichtenvektor, $A$ die Transformationsmatrix und $v$ unser Übertragungsvektor ist. - +Für die Codierung benötigen wir die Nachricht $m$, die Codiert werden soll sowie die Transformationsmatrix $A$. Daraus erhalten wir den Übertragungsvektor $v$. Setzen wir die Zahlen aus dem Beispiel ein erhalten wir folgende Darstellung. \[ v = A \cdot m \qquad \Rightarrow \qquad v = \begin{pmatrix} 8^0& 8^0& 8^0& 8^0& 8^0& 8^0& 8^0& 8^0& 8^0& 8^0\\ @@ -127,13 +174,8 @@ v = A \cdot m \qquad \Rightarrow \qquad v = \begin{pmatrix} 1 \\ 8 \\ 5 \\ 2 \\ 7 \\ 4 \\ 0 \\ 0 \\ 0 \\ 0 \\ \end{pmatrix} \] - -Somit bekommen wir für unseren Übertragungsvektor +Für unseren Übertragungsvektor resultiert \[ v = [5,3,6,5,2,10,2,7,10,4], \] den wir jetzt über einen beliebigen Nachrichtenkanal versenden können. - -\textbf{NOTES} - -warum wird 0 weggelassen? diff --git a/buch/papers/reedsolomon/decmitfehler.tex b/buch/papers/reedsolomon/decmitfehler.tex index 923c1c5..feaa027 100644 --- a/buch/papers/reedsolomon/decmitfehler.tex +++ b/buch/papers/reedsolomon/decmitfehler.tex @@ -3,52 +3,110 @@ % % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil % -\section{Decodierung mit Fehler +\section{Decodierung: Ansatz mit Fehlerkorrektur \label{reedsolomon:section:decmitfehler}} \rhead{fehlerhafte rekonstruktion} -Im zweiten Teil zur Decodierung betrachten wir den Fall, dass unser Übertragungskanal nicht fehlerfrei ist. -Wir legen daher den Fehlervektor +Bisher haben wir die Decodierung unter der Bedingung durchgeführt, dass der Übertragungsvektor fehlerlos versendet und empfangen wurde. +In der realen Welt müssen wir uns jedoch damit abfinden, dass kein Übertragungskanal garantiert fehlerfrei ist und das wir früher oder später mit Fehlern rechnen müssen. +Genau für dieses Problem wurden Fehler korrigierende Codes, wie der Reed-Solomon-Code, entwickelt. +In diesem Abschnitt betrachten wir somit die Idee der Fehlerkorrektur und wie wir diese auf unser Beispiel anwenden können. +Der Übertragungskanal im Beispiel weisst jetzt den Fehlervektor \[ u = [0, 0, 0, 3, 0, 0, 0, 0, 2, 0] \] -fest, den wir zu unserem Übertragungsvektor als Fehler dazu addieren und somit +auf. +Senden wir jetzt unser Übertragungsvektor $v$ durch diesen Kanal addiert sich der Fehlervektor $u$ auf unsere Übertragung und wir erhalten \begin{center} - -\begin{tabular}{c | c r } - $v$ & & $[5,3,6,5,2,10,2,7,10,4]$\\ - $u$ & $+$ & $[0,0,0,3,0,0,0,0,2,0]$\\ - \hline - $w$ & & $[5,3,6,8,2,10,2,7,1,4]$\\ -\end{tabular} - -% alternative design -%\begin{tabular}{c | c cccccccccccc } -% $v$ & & $[$&$5,$&$3,$&$6,$&$5,$&$2,$&$10,$&$2,$&$7,$&$10,$&$4$&$]$\\ -% $u$ & $+$ & $[$&$0,$&$0,$&$0,$&$3,$&$0,$&$0,$&$0,$&$0,$&$2,$&$0$&$]$\\ + + \begin{tabular}{c | c r } + $v$ & & $[5,3,6,5,2,10,2,7,10,4]$\\ + $u$ & $+$ & $[0,0,0,3,0,0,0,0,2,0]$\\ + \hline + $w$ & & $[5,3,6,8,2,10,2,7,1,4]$\\ + \end{tabular} + + % alternative design + %\begin{tabular}{c | c cccccccccccc } + % $v$ & & $[$&$5,$&$3,$&$6,$&$5,$&$2,$&$10,$&$2,$&$7,$&$10,$&$4$&$]$\\ + % $u$ & $+$ & $[$&$0,$&$0,$&$0,$&$3,$&$0,$&$0,$&$0,$&$0,$&$2,$&$0$&$]$\\ + % \hline + % $w$ & & $[$&$5,$&$3,$&$6,$&$8,$&$2,$&$10,$&$2,$&$7,$&$1,$&$4$&$]$\\ + %\end{tabular} + +\end{center} +als neuen, fehlerbehafteten Übertragungsvektor $w$ auf der Empfängerseite. +% Old Text +%In diesem Abschnitt gehen wir genauer darauf ein, wie der Reed-Solomon-Code eine solche Feherkorrektur vornimt. +% +%In diesem Abschnitt betrachten wir das Problem, dass während der Übertragung des Übertragungsvektors von unserem Beispiel +% +% +%Zu diesem Zweck wurden Fehler korrigierende Codes entwickelt. +% +%Dieser Optimalfall kann jedoch mit keinem Übertragungskanal garantiert werden +% +% +%Im zweiten Teil zur Decodierung betrachten wir den Fall, dass unser Übertragungskanal nicht fehlerfrei ist. +%Wir legen daher den Fehlervektor +%\[ +%u = [0, 0, 0, 3, 0, 0, 0, 0, 2, 0] +%\] +%fest, den wir zu unserem Übertragungsvektor als Fehler dazu addieren und somit +% +%\begin{center} +% +%\begin{tabular}{c | c r } +% $v$ & & $[5,3,6,5,2,10,2,7,10,4]$\\ +% $u$ & $+$ & $[0,0,0,3,0,0,0,0,2,0]$\\ % \hline -% $w$ & & $[$&$5,$&$3,$&$6,$&$8,$&$2,$&$10,$&$2,$&$7,$&$1,$&$4$&$]$\\ +% $w$ & & $[5,3,6,8,2,10,2,7,1,4]$\\ %\end{tabular} - -\end{center} -als Übertragungsvektor auf der Empfängerseite erhalten. - -Wenn wir den Übertragungsvektor jetzt Rücktransformieren wie im vorherigen Kapitel erhalten wir +% +%% alternative design +%%\begin{tabular}{c | c cccccccccccc } +%% $v$ & & $[$&$5,$&$3,$&$6,$&$5,$&$2,$&$10,$&$2,$&$7,$&$10,$&$4$&$]$\\ +%% $u$ & $+$ & $[$&$0,$&$0,$&$0,$&$3,$&$0,$&$0,$&$0,$&$0,$&$2,$&$0$&$]$\\ +%% \hline +%% $w$ & & $[$&$5,$&$3,$&$6,$&$8,$&$2,$&$10,$&$2,$&$7,$&$1,$&$4$&$]$\\ +%%\end{tabular} +% +%\end{center} +%als Übertragungsvektor auf der Empfängerseite erhalten. +Wir jetzt als Empfänger wissen jedoch nicht, dass der erhaltene Übertragungsvektor jetzt fehlerbehaftet ist und werden dementsprechend den Ansatz aus Abschnitt \ref{reedsolomon:section:decohnefehler} anwenden. +Wir stellen jedoch recht schnell fest, dass am decodierten Nachrichtenblock \[ -r = [\underbrace{5,7,4,10,}_{Fehlerinfo}5,4,5,7,6,7]. +r = [\underbrace{5,7,4,10,}_{\text{Syndrom}}5,4,5,7,6,7]. \] -Im Vergleich zum vorherigen Kapitel sind die Fehlerkorrekturstellen jetzt $\neq 0$, was bedeutet, dass wir diesen Übertragungsvektor fehlerhaft empfangen haben und sich die Nachricht jetzt nicht mehr so einfach decodieren lässt. +etwas nicht in Ordnung ist, denn die vorderen vier Fehlerkorrekturstellen haben nicht mehr den Wert null. +Der Nachrichtenblock weisst jetzt ein \em Syndrom \em auf, welches anzeigt, dass der Übertragungsvektor fehlerhaft empfangen wurde. +% Old Text +%Wenn wir den Übertragungsvektor jetzt Rücktransformieren wie im vorherigen Kapitel erhalten wir +%\[ +%r = [\underbrace{5,7,4,10,}_{Fehlerinfo}5,4,5,7,6,7]. +%\] +Jetzt stellt sich natürlich die Frage, wie wir daraus den ursprünglich gesendeten Nachrichtenvektor zurückerhalten sollen. Laut der Definition über die Funktionsweise eines Reed-Solomon-Codes können wir aus den Fehlerkorrekturstellen ein ``Lokatorpolynom'' berechnen, welches die Information enthält, welche stellen innerhalb des empfangenen Übertragungsvektors fehlerhaft sind. + +\subsection{Das Fehlerstellenpolynom $d(X)$ + \label{reedsolomon:subsection:fehlerpolynom}} +Bevor wir unser Lokatorpolynom berechnen können, müssen wir zuerst eine Möglichkeit finden, die Fehlerhaften von den Korrekten Stellen im Übertragungsvektor unterscheiden zu können. In einem ersten Versuch könnten wir $d$ berechnen mit +\begin{center} +\begin{tabular}{r c l} + $m(X)$ & $=$ & $4X^5 + 7X^4 + 2X^3 + 5X^2 + 8X + 1$ \\ + $r(X)$ & $=$ & $5X^9 + 7X^8 + 4X^7 + 10X^6 + 5X^5 + 4X^4 + 5X^3 + 7X^2 + 6X + 7$ \\ + $d(X)$ & $=$ & $r(X) - m(X)$. +\end{tabular} +\end{center} +Dies wird uns zwar andere sorgen wegen $m(X)$ bereiten, wir werden werden deshalb erst in Abschnitt \ref{reedsolomon:subsection:nachrichtenvektor} darauf zurückkommen. -% warum wir die fehler suchen -Da Reed-Solomon-Codes in der Lage sind, eine Nachricht aus weniger Stellen zu rekonstruieren als wir ursprünglich haben, so müssen wir nur die Fehlerhaften Stellen finden und eliminieren, damit wir unsere Nutzdaten rekonstruieren können. -Damit stellt sich die Frage, wie wir die Fehlerstellen $e$ finden. -Dafür wählen wir einen Primitiven Ansatz mit -\begin{align} - m(X) & = 4X^5 + 7X^4 + 2X^3 + 5X^2 + 8X + 1 \\ - r(X) & = 5X^9 + 7X^8 + 4X^7 + 10X^6 + 5X^5 + 4X^4 + 5X^3 + 7X^2 + 6X + 7 \\ - e(X) & = r(X) - m(X). -\end{align} -Setzen wir jetzt unsere Einheitswurzel für $X$ ein, so erhalten wir +Setzen wir jetzt noch unsere Einheitswurzel aus dem Beispiel ein so erhalten wir +% Old Text +%\begin{align} +% m(X) & = 4X^5 + 7X^4 + 2X^3 + 5X^2 + 8X + 1 \\ +% r(X) & = 5X^9 + 7X^8 + 4X^7 + 10X^6 + 5X^5 + 4X^4 + 5X^3 + 7X^2 + 6X + 7 \\ +% e(X) & = r(X) - m(X). +%\end{align} +%Setzen wir jetzt unsere Einheitswurzel für $X$ ein, so erhalten wir \begin{center} \begin{tabular}{c c c c c c c c c c c} \hline @@ -56,80 +114,137 @@ Setzen wir jetzt unsere Einheitswurzel für $X$ ein, so erhalten wir \hline $r(a^{i})$& $5$& $3$& $6$& $8$& $2$& $10$& $2$& $7$& $1$& $4$\\ $m(a^{i})$& $5$& $3$& $6$& $5$& $2$& $10$& $2$& $7$& $10$& $4$\\ - $e(a^{i})$& $0$& $0$& $0$& $3$& $0$& $0$& $0$& $0$& $2$& $0$\\ + $d(a^{i})$& $0$& $0$& $0$& $3$& $0$& $0$& $0$& $0$& $2$& $0$\\ \hline \end{tabular} \end{center} -und damit die Information, dass an allen Stellen, die nicht Null sind, Fehler enthalten. -Um jetzt alle nicht Nullstellen zu finden, wenden wir den Satz von Fermat an. +und damit die Information, dass allen Stellen, die nicht Null sind, Fehler enthalten. +Aus der Tabelle lesen wir, das in unserem Beispiel die Fehler an der Stelle drei und acht zu finden sind. + +Für das einfache Bestimmen von Hand mag dies ja noch ausreichen, jedoch können wir mit diesen Stellen nicht das Lokatorpolynom bestimmen, denn dafür bräuchten wir alle Nullstellen, an denen es Fehler gegeben hat (also sozusagen genau das umgekehrte). Um dies zu erreichen wenden wir eine andere Herangehensweise und nehmen uns den Satz von Fermat sowie den kleinsten gemeinsamen Teiler zur Hilfe. -\subsection{Der Satz von Fermat -\label{reedsolomon:subsection:fermat}} -Der Satz von Fermat besagt, dass für +\subsection{Mit dem grössten gemeinsamen Teiler auf Nullstellenjagd +\label{reedsolomon:subsection:ggT}} + +Zuerst betrachten wir mal den Satz von Fermat deren Funktionsweise wir in Abschnitt \ref{buch:section:galoiskoerper} kennengelernt haben. Der besagt, dass für \[ f(X) = X^{q-1} -1 = 0 \] -gilt, egal was wir für $q$ einsetzen. - -Für unser Beispiel erhalten wir +wobei dies für jedes $q$ gilt. Setzen wir also das $q$ von unserem Beispiel ein \[ f(X) = X^{10}-1 = 0 \qquad \text{für } X = \{1,2,3,4,5,6,7,8,9,10\} \] -und können $f(X)$ auch umschreiben in +und stellen dies als Nullstellenform (\textcolor{red}{richtiger name für die Schreibweise?}) dar. So ergibt sich die Darstellung \[ f(X) = (X-a^0)(X-a^1)(X-a^2)(X-a^3)(X-a^4)(X-a^5)(X-a^6)(X-a^7)(X-a^8)(X-a^9). \] Zur Überprüfung können wir unsere Einheitswurzel in $a$ einsetzen und werden sehen, dass wir für $f(X) = 0$ erhalten werden. -Nach der gleichen Überlegung können wir jetzt auch $e(X)$ darstellen als + +Wir können jetzt auch $d(X)$ nach der gleichen Überlegung darstellen als \[ -e(X) = (X-a^0)(X-a^1)(X-a^2) \qquad \qquad (X-a^4)(X-a^5)(X-a^6)(X-a^7) \qquad \qquad (X-a^9) \cdot p(x), +d(X) = (X-a^0)(X-a^1)(X-a^2)\textcolor{gray!40}{(X-a^3)}(X-a^4)(X-a^5)(X-a^6)(X-a^7)\textcolor{gray!40}{(X-a^8)}(X-a^9) \cdot p(x), \] -wobei $p(X)$ das Restpolynom ist und die Fehlerstellen beinhaltet. -Wenn wir jetzt den grössten gemeinsamen Teiler von $f(X)$ und $e(X)$ berechnen, so erhalten wir mit +wobei diese Darstellung nicht mehr alle Nullstellen umfasst wie es noch in $f(X)$ der Fall war. +Dies liegt daran, dass wir ja zwei Fehlerstellen (grau markiert) haben, die nicht Null sind. Diese fassen wir zum Restpolynom $p(X)$ (\textcolor{red}{eventuell farblich kennzeichnen?}) zusammen. +Wenn wir jetzt den grössten gemeinsamen Teiler von $f(X)$ und $d(X)$ berechnen, so erhalten wir mit \[ -\operatorname{ggT}(f(X),e(X)) = (X-a^0)(X-a^1)(X-a^2) \qquad \qquad (X-a^4)(X-a^5)(X-a^6)(X-a^7) \qquad \qquad (X-a^9) +\operatorname{ggT}(f(X),d(X)) = (X-a^0)(X-a^1)(X-a^2)\textcolor{gray!40}{(X-a^3)}(X-a^4)(X-a^5)(X-a^6)(X-a^7)\textcolor{gray!40}{(X-a^8)}(X-a^9) \] eine Liste von Nullstellen, an denen es keine Fehler gegeben hat. -Da wir uns jedoch für eine Liste mit Nullstellen interessieren, an denen es Fehler gegeben hat berechnen wir stattdessen das kgV von $f(X)$ und $e(X)$ als +Dies scheint zuerst nicht sehr hilfreich zu sein, da wir für das Lokatorpolynom ja eine Liste der Nullstellen suchen, an denen es Fehler gegeben hat. Aus diesem Grund berechnen wir im nächsten Schritt das kleinste gemeinsame Vielfache von $f(X)$ und $d(X)$. + +%Wir werden auch feststellen, das unsere Bemühungen bisher nicht umsonst waren. + +\subsection{Mit dem kgV fehlerhafte Nullstellen finden + \label{reedsolomon:subsection:kgV}} + +Das kgV hat nämlich die Eigenschaft sämtliche Nullstellen zu finden, also nicht nur die fehlerhaften sondern auch die korrekten, was in \[ -\operatorname{kgV}(f(X),e(X)) = (X-a^0)(X-a^1)(X-a^2)(X-a^3)(X-a^4)(X-a^5)(X-a^6)(X-a^7)(X-a^8)(X-a^9) \cdot q(X). +\operatorname{kgV}(f(X),d(X)) = (X-a^0)(X-a^1)(X-a^2)(X-a^3)(X-a^4)(X-a^5)(X-a^6)(X-a^7)(X-a^8)(X-a^9) \cdot q(X). \] -Wir können das Resultat noch zerlegen in +ersichtlich ist. +Aus dem vorherigen Abschnitt wissen wir auch, dass $d(X)$ alle korrekten Nullstellen beinhaltet. Teilen wir das kgV jetzt auf in \[ -\operatorname{kgV}(f(X),e(X)) = d(X) \cdot e(X). +\operatorname{kgV}(f(X),d(X)) = d(X) \cdot l(X) \] -Somit muss $d(X)$ eine Liste von Nullstellen enthalten an denen es Fehler gegeben hat. +sollten wir für $l(X)$ eine Liste mit allen fehlerhaften Nullstellen erhalten. +Somit ist \[ -d(X) = (X-a^3)(X-a^8) +l(X) = (X-a^3)(X-a^8) \] +unser gesuchtes Lokatorpolynom. +Es scheint so als müssten wir nur noch an den besagten Stellen den Übertragungsvektor korrigieren und wir währen fertig mit der Fehlerkorrektur. +Jedoch haben wir noch ein grundlegendes Problem, dass zu beginn aufgetaucht ist, wir aber beiseite geschoben haben. Die Rede ist natürlich vom Nachrichtenvektor $m(X)$, mit dem wir in erster Linie das wichtige Fehlerstellenpolynom $d(X)$ berechnet haben. +\subsection{Der problematische Nachrichtenvektor $m(X)$ + \label{reedsolomon:subsection:nachrichtenvektor}} -und ist damit unser gesuchtes Lokatorpolynom. - -Das einzige Problem was jetzt noch bleibt ist, dass wir $e(X)$ berechnet haben aus +In Abschnitt \ref{reedsolomon:section:decmitfehler} haben wir \[ -e(X) = r(X) - m(X), +d(X) = r(X) - m(X) \] -wobei $m(X)$ auf der Empfängerseite unbekannt ist. -Es sieht danach aus, das wir diesen Lösungsansatz nicht verwenden können, da uns ein entscheidender Teil fehlt. -Bei einer näheren Betrachtung von $m(X)$ fällt uns aber auf, dass wir doch etwas über $m(X)$ wissen. -Wir kennen nämlich die ersten vier Stellen, da diese für die Fehlerkorrektur zuständig sind und daher Null sein müssen. +in Abhängigkeit von $m(X)$ berechnet. +Jedoch haben wir ausser acht gelassen, dass $m(X)$ auf der Empfängerseite nicht existiert und somit gänzlich unbekannt ist. +Es scheint so als würde dieser Lösungsansatz, den wir bisher verfolgt haben, nicht funktioniert. +Wir könnten uns höchstens noch fragen, ob wir tatsächlich nichts über den Nachrichtenvektor im Beispiel wissen. Wenn wir noch einmal den Vektor betrachten als \[ -m = [0,0,0,0,?,?,?,?,?,?] +m = [0,0,0,0,4,7,2,5,8,1] \] -An genau diesen Stellen liegt auch die Information, wo unsere Fehlerstellen liegen, was uns ermöglicht, den Teil von $e(X)$ zu berechnen, der uns auch interessiert. - -Wir können $e(X)$ also bestimmen als +fällt uns aber auf, dass wir doch etwas über diesen Vektor wissen, nämlich den Wert der ersten 2t (im Beispiel vier) stellen. +Im Normalfall sollen diese nämlich den Wert null betragen und somit sind nur die letzten k stellen (im Beispiel sechs) für uns unbekannt, dargestellt als \[ -e(X) = 5X^9 + 7X^8 + 4X^7 + 10X^6 + p(X) +m = [0,0,0,0,?,?,?,?,?,?]. \] -wobei $p(X)$ wiederum ein unbekanntes Restpolynom ist und +Wie der Zufall es so will liegt an diesen vier Stellen auch die Information, wo die Fehlerstellen liegen. Daher reicht es auch aus +% darum werden die stellen auch als fehlerkorrekturstellen bezeichnet \[ -f(X) = X^{10} - 1 = X^{10} + 10 +d(X) = 5X^9 + 7X^8 + 4X^7 + 10X^6 + p(X) \] -ist können wir so in einer ersten Instanz den grössten gemeinsamen Teiler von $f(X)$ und $e(X)$ berechnen. -Dafür nehmen wir uns wiederum den Euklidischen Algorithmus zur Hilfe und berechnen so +so zu berechnen, dass wir die wichtigen vier Stellen kennen, der Rest des Polynoms jedoch im unbekannten Restpolynom $p(X)$ enthalten ist. + +\textcolor{red}{ist das wechseln zwischen 2t,k aus dem allgemeinfall und vier,sechs aus dem beispiel zu verwirrend?} + +\subsection{Die Berechnung der Fehlerstellen + \label{reedsolomon:subsection:nachrichtenvektor}} + +Um die Fehlerstellen zu berechnen wenden wir die gleiche Vorgehensweise wie zuvor an, also zuerst den ggT, danach berechnen wir das kgV um am Ende das Lokatorpolynom zu erhalten. + +\subsubsection{Schritt 1: ggT} +Wir berechnen den ggT von $f(X)$ und $d(X)$ mit +\begin{center} +\begin{tabular}{r c l} + $f(X)$ & $=$ & $X^{10} - 1 = X^{10} + 10$ \\ + $d(X)$ & $=$ & $5X^9 + 7X^8 + 4X^7 + 10X^6 + p(X)$ +\end{tabular} +\end{center} +% +% +% +%Das einzige Problem was jetzt noch bleibt ist, dass wir $e(X)$ berechnet haben aus +%\[ +%e(X) = r(X) - m(X), +%\] +%wobei $m(X)$ auf der Empfängerseite unbekannt ist. +%Es sieht danach aus, das wir diesen Lösungsansatz nicht verwenden können, da uns ein entscheidender Teil fehlt. +%Bei einer näheren Betrachtung von $m(X)$ fällt uns aber auf, dass wir doch etwas über $m(X)$ wissen. +%Wir kennen nämlich die ersten vier Stellen, da diese für die Fehlerkorrektur zuständig sind und daher Null sein müssen. +%\[ +%m = [0,0,0,0,?,?,?,?,?,?] +%\] +%An genau diesen Stellen liegt auch die Information, wo unsere Fehlerstellen liegen, was uns ermöglicht, den Teil von $e(X)$ zu berechnen, der uns auch interessiert. +% +%Wir können $e(X)$ also bestimmen als +%\[ +%e(X) = 5X^9 + 7X^8 + 4X^7 + 10X^6 + p(X) +%\] +%wobei $p(X)$ wiederum ein unbekanntes Restpolynom ist und +%\[ +%f(X) = X^{10} - 1 = X^{10} + 10 +%\] +%ist können wir so in einer ersten Instanz den grössten gemeinsamen Teiler von $f(X)$ und $e(X)$ berechnen. +%Dafür nehmen wir uns wiederum den Euklidischen Algorithmus zur Hilfe und berechnen so +% \[ \arraycolsep=1.4pt \begin{array}{rcrcrcrcccrcrcrcrcrcrcrcrcr} @@ -151,11 +266,16 @@ Dafür nehmen wir uns wiederum den Euklidischen Algorithmus zur Hilfe und berech \] und erhalten \[ -\operatorname{ggT}(f(X),e(X)) = 6X^8 +\operatorname{ggT}(f(X),e(X)) = 6X^8. \] -Mit den Resultaten, die wir vom Rechenweg des grössten gemeinsamen Teiler erhalten haben können wir jetzt auch das kleinste Gemeinsame Vielfache berechnen. Eine detailliertere Vorgehensweise findet man in Kapitel ???. -Aus diesem erweiterten Euklidischen Algorithmus erhalten wir +\subsubsection{Schritt 2: kgV} + +Mit dem Resultat das wir vom ggT erhalten haben können wir jetzt das kgV berechnen. Dazu können wir jetzt den erweiterten Euklidischen Algorithmus verwenden, den wir in Abschnitt \ref{buch:subsection:daskgv} kennengelernt haben. +% +%Mit den Resultaten, die wir vom Rechenweg des grössten gemeinsamen Teiler erhalten haben können wir jetzt auch das kleinste Gemeinsame Vielfache berechnen. Eine detailliertere Vorgehensweise findet man in Kapitel ???. +% +%Aus diesem erweiterten Euklidischen Algorithmus erhalten wir \begin{center} \begin{tabular}{| c | c | c c |} @@ -170,28 +290,23 @@ Aus diesem erweiterten Euklidischen Algorithmus erhalten wir \end{tabular} \end{center} -und erhalten auf diesem Weg den Faktor +Daraus erhalten wir die Faktoren \[ -d(X) = 2X^2 + 5, +l(X) = 2X^2 + 5 \qquad \rightarrow \qquad l(X) = 2(X-5)(X-6). \] -den wir in +Unser gesuchtes Lokatorpolynom hat also die Form \[ -d(X) = 2(X-5)(X-6) +l(X) = (X-a^i)(X-a^j). \] -zerlegen können. -Da die unbekannten Stellen im Lokatorpolynom -\[ -d(X) = (X-a^i)(X-a^i) -\] -sind, müssen wir nur noch $i$ berechnen als +Also brauchen wir nur noch $i$ und $j$ zu berechnen und wir haben unsere gesuchten Fehlerstellen. +Diese bekommen wir recht einfach mit \begin{center} $a^i = 5 \qquad \Rightarrow \qquad i = 3$ - $a^i = 6 \qquad \Rightarrow \qquad i = 8$. + $a^j = 6 \qquad \Rightarrow \qquad j = 8$. \end{center} - -Somit erhalten wir schliesslich +Schlussendlich erhalten wir \[ d(X) = (X-a^3)(X-a^8) \] -als unser Lokatorpolynom mit den Fehlerhaften Stellen.
\ No newline at end of file +als unser Lokatorpolynom mit den fehlerhaften Stellen. diff --git a/buch/papers/reedsolomon/decohnefehler.tex b/buch/papers/reedsolomon/decohnefehler.tex index 6ca577a..3b709f3 100644 --- a/buch/papers/reedsolomon/decohnefehler.tex +++ b/buch/papers/reedsolomon/decohnefehler.tex @@ -3,41 +3,50 @@ % % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil % -\section{Decodierung ohne Fehler +\section{Decodierung: Ansatz ohne Fehler \label{reedsolomon:section:decohnefehler}} \rhead{fehlerlose rekonstruktion} -Im ersten Teil zur Decodierung des Übertragungsvektor betrachten wir den Übertragungskanal als fehlerfrei. -Wir erhalten also unseren Übertragungsvektor + +In diesem Abschnitt betrachten wie die Überlegung, wie wir auf der Empfängerseite die Nachricht aus dem empfangenen Übertragungsvektor erhalten. Nach einer einfachen Überlegung müssen wir den Übertragungsvektor decodieren, was auf den ersten Blick nicht allzu kompliziert sein sollte, solange wir davon ausgehen können, dass es während der Übertragung keine Fehler gegeben hat. Wir betrachten deshalb den Übertragungskanal als fehlerfrei. + +Der Übertragungsvektor empfangen wir also als \[ v = [5,3,6,5,2,10,2,7,10,4]. \] - -Gesucht ist nun einen Weg, mit dem wir auf unseren Nachrichtenvektor zurückrechnen können. -Ein banaler Ansatz ist das Invertieren der Glechung +% Old Text +%Im ersten Teil zur Decodierung des Übertragungsvektor betrachten wir den Übertragungskanal als fehlerfrei. +%Wir erhalten also unseren Übertragungsvektor +%\[ +%v = [5,3,6,5,2,10,2,7,10,4]. +%\] +Nach einem banalen Ansatz ist die Decodierung die Inverse der Codierung. Dank der Matrixschreibweise lässt sich dies relativ einfach umsetzen. +% Old Text +%Gesucht ist nun einen Weg, mit dem wir auf unseren Nachrichtenvektor zurückrechnen können. +%Ein banaler Ansatz ist das Invertieren der Glechung \[ -v = A \cdot m \qquad \Rightarrow \qquad m = A^{-1} \cdot v. +v = A \cdot m \qquad \Rightarrow \qquad m = A^{-1} \cdot v \] - -Nur stellt sich dann die Frage, wie wir auf die Inverse der Matix $A$ kommen. +Nur stellt sich jetzt die Frage, wie wir die Inverse von $A$ berechnen. Dazu können wir wiederum den Ansatz der Fouriertransformation uns zur Hilfe nehmen, jedoch betrachten wir jetzt deren Inverse. Definiert ist sie als \[ F(\omega) = \int_{-\infty}^{\infty} f(t) \mathrm{e}^{-j\omega t} dt \qquad \Rightarrow \qquad \mathfrak{F}^{-1}(F(\omega)) = f(t) = \frac{1}{2 \pi} \int_{-\infty}^{\infty} F(\omega) \mathrm{e}^{j \omega t} d\omega. \] - -In unserem Fall suchen wir also eine inverse für die Primitive Einheitswurzel $a$, also +Damit beschäftigen wir uns im Abschnitt \ref{reedsolomon:subsection:algdec} weiter, konkret suchen wir momentan aber eine Inverse für unsere primitive Einheitswurzel $a$. \[ -8^1 \qquad \Rightarrow \qquad 8^{-1}. +8^1 \qquad \rightarrow \qquad 8^{-1} \] +Mit einem solchen Problem haben wir uns bereits in Abschnitt \ref{buch:section:euklid} befasst und so den euklidischen Algorithmus kennengelernt, den wir auf unseren Fall anwenden können. -Im Abschnitt \textcolor{red}{4.1} haben wir den euklidischen Algorithmus kennengelernt, den wir auf unseren Fall anwenden können. +% Old Text +%Im Abschnitt \textcolor{red}{4.1} haben wir den euklidischen Algorithmus kennengelernt, den wir auf unseren Fall anwenden können. -\subsection{Der Euklidische Algorithmus -\label{reedsolomon:subsection:eukAlgo}} +\subsection{Inverse der primitiven Einheitswurzel +\label{reedsolomon:subsection:invEinh}} -Die Funktionsweise des euklidischen Algorithmus ist im Kapitel \textcolor{red}{4.1} ausführlich beschrieben. -Für unsere Anwendung wählen wir die Parameter $a_i = 8$ und $b_i = 11$. +Die Funktionsweise des euklidischen Algorithmus ist im Kapitel \ref{buch:section:euklid} ausführlich beschrieben. +Für unsere Anwendung wählen wir die Parameter $a = 8$ und $b = 11$ ($\mathbb{F}_{11}$). Daraus erhalten wir \begin{center} @@ -67,20 +76,21 @@ Daraus erhalten wir \end{tabular} \end{center} +als Inverse der primitiven Einheitswurzel. Die inverse Transformationsmatrix $A^{-1}$ bilden wir indem wir jetzt die inverse primitive Einheitswurzel anstelle der primitiven Einheitswurzel in die Matrix einsetzen. -als Inverse der Primitiven Einheitswurzel. +\subsection{Allgemeine Decodierung + \label{reedsolomon:subsection:algdec}} -Nun haben wir fast alles für die Rücktransformation beisammen. Wie auch bei der Inversen Fouriertransformation haben wir nun einen Vorfaktor +Wir haben jetzt fast alles für eine erfolgreiche Rücktransformation beisammen. Wir haben aber noch nicht alle Aspekte der inversen diskreten Fouriertransformation befolgt, so fehlt uns noch einen Vorfaktor \[ m = \textcolor{red}{s} \cdot A^{-1} \cdot v \] den wir noch bestimmen müssen. -Glücklicherweise lässt der sich analog wie bei der Inversen Fouriertransformation bestimmen und beträgt +Glücklicherweise lässt der sich analog wie bei der inversen diskreten Fouriertransformation bestimmen und beträgt \[ s = \frac{1}{10}. \] -Da $\frac{1}{10} = 10^{-1}$ entspricht können wir $s$ ebenfalls mit dem euklidischen Algorithmus bestimmen und stellen fest, dass $10^{-1} = 10$ ergibt. -Somit lässt sich der Nachrichtenvektor einfach bestimmen mit +Da $\frac{1}{10} = 10^{-1}$ entspricht können wir $s$ ebenfalls mit dem euklidischen Algorithmus bestimmen und stellen fest, dass $10^{-1} = 10$ in $\mathbb{F}_{11}$ ergibt. Somit lässt sich der Nachrichtenvektor einfach bestimmen mit \[ m = 10 \cdot A^{-1} \cdot v \qquad \Rightarrow \qquad m = 10 \cdot \begin{pmatrix} 7^0& 7^0& 7^0& 7^0& 7^0& 7^0& 7^0& 7^0& 7^0& 7^0\\ diff --git a/buch/papers/reedsolomon/endlichekoerper.tex b/buch/papers/reedsolomon/endlichekoerper.tex index 8ccd918..146067a 100644 --- a/buch/papers/reedsolomon/endlichekoerper.tex +++ b/buch/papers/reedsolomon/endlichekoerper.tex @@ -7,9 +7,9 @@ \label{reedsolomon:section:endlichekoerper}} \rhead{Problemstellung} -TODO: +\textcolor{red}{TODO: (warten auf den 1. Teil)} -Das rechnen in endlichen Körpern bietet einige Vorteile: +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. @@ -20,4 +20,4 @@ Das rechnen in endlichen Körpern bietet einige Vorteile: 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. +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/hilfstabellen.tex b/buch/papers/reedsolomon/hilfstabellen.tex new file mode 100644 index 0000000..4e39de5 --- /dev/null +++ b/buch/papers/reedsolomon/hilfstabellen.tex @@ -0,0 +1,19 @@ +% +% hilfstabellen.tex +% Autor: Michael Steiner +% +% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil +% +\section{$\mathbb{F}_{11}$ Hilfstabellen + \label{reedsolomon:section:hilfstabellen}} +\rhead{Hilfstabellen} + +Um das rechnen zu erleichtern findet man in diesem Abschnitt die Resultate, die bei der Addition und der Multiplikation in $\mathbb{F}_{11}$ resultieren. + +\subsection{Additionstabelle + \label{reedsolomon:subsection:adtab}} +\input{papers/reedsolomon/restetabelle1.tex} + +\subsection{Multiplikationstabelle + \label{reedsolomon:subsection:mptab}} +\input{papers/reedsolomon/restetabelle2.tex}
\ No newline at end of file diff --git a/buch/papers/reedsolomon/main.tex b/buch/papers/reedsolomon/main.tex index a7485cd..fa20936 100644 --- a/buch/papers/reedsolomon/main.tex +++ b/buch/papers/reedsolomon/main.tex @@ -39,6 +39,13 @@ Bilden Sie auch für Formeln kurze Zeilen, einerseits der besseren \input{papers/reedsolomon/decohnefehler} \input{papers/reedsolomon/decmitfehler} \input{papers/reedsolomon/rekonstruktion} +\input{papers/reedsolomon/nachschlagewerk} +\input{papers/reedsolomon/hilfstabellen} +%\input{papers/reedsolomon/anwendungen} -> geplant + +\nocite{reedsolomon:weitz} +\nocite{reedsolomon:informationkommunikation} +%\nocite{reedsolomon:mendezmueller} \printbibliography[heading=subbibliography] \end{refsection} diff --git a/buch/papers/reedsolomon/nachschlagewerk.tex b/buch/papers/reedsolomon/nachschlagewerk.tex new file mode 100644 index 0000000..60b857e --- /dev/null +++ b/buch/papers/reedsolomon/nachschlagewerk.tex @@ -0,0 +1,4 @@ +\section{Nachschlagewerk + \label{reedsolomon:section:nachschlagen}} +\rhead{nachschlagewerk} +todo: auflistung von z.b nachrichtenvektor, übertragungsvektor usw. inklusiver erklärung was es ist falls man beim lesen den faden verliert
\ No newline at end of file diff --git a/buch/papers/reedsolomon/references.bib b/buch/papers/reedsolomon/references.bib index 38613bd..4c1d17a 100644 --- a/buch/papers/reedsolomon/references.bib +++ b/buch/papers/reedsolomon/references.bib @@ -4,32 +4,53 @@ % (c) 2020 Autor, Hochschule Rapperswil % -@online{reedsolomon:bibtex, - title = {BibTeX}, - url = {https://de.wikipedia.org/wiki/BibTeX}, - date = {2020-02-06}, - year = {2020}, - month = {2}, - day = {6} +@online{reedsolomon:weitz, + title = {Fehlerkorrektur mit Reed-Solomon-Codes}, + url = {https://youtu.be/uOLW43OIZJ0}, + date = {2021-06-10}, + year = {2021}, + month = {6}, + day = {10} } -@book{reedsolomon:numerical-analysis, - title = {Numerical Analysis}, - author = {David Kincaid and Ward Cheney}, - publisher = {American Mathematical Society}, - year = {2002}, - isbn = {978-8-8218-4788-6}, - inseries = {Pure and applied undegraduate texts}, - volume = {2} -} +% https://link.springer.com/chapter/10.1007%2F978-3-8351-9077-1_9 -@article{reedsolomon:mendezmueller, - author = { Tabea Méndez and Andreas Müller }, - title = { Noncommutative harmonic analysis and image registration }, - journal = { Appl. Comput. Harmon. Anal.}, - year = 2019, - volume = 47, - pages = {607--627}, - url = {https://doi.org/10.1016/j.acha.2017.11.004} +@book{reedsolomon:informationkommunikation, + title = {Information und Kommunikation}, + author = {Markus Hufschmid}, + publisher = {Teubner}, + year = {2007}, + isbn = {978-3-8351-0122-7}, + inseries = {}, + volume = {1} } +% Beispiele +%@online{reedsolomon:bibtex, +% title = {BibTeX}, +% url = {https://de.wikipedia.org/wiki/BibTeX}, +% date = {2020-02-06}, +% year = {2020}, +% month = {2}, +% day = {6} +%} +% +%@book{reedsolomon:numerical-analysis, +% title = {Numerical Analysis}, +% author = {David Kincaid and Ward Cheney}, +% publisher = {American Mathematical Society}, +% year = {2002}, +% isbn = {978-8-8218-4788-6}, +% inseries = {Pure and applied undegraduate texts}, +% volume = {2} +%} +% +%@article{reedsolomon:mendezmueller, +% author = { Tabea Méndez and Andreas Müller }, +% title = { Noncommutative harmonic analysis and image registration }, +% journal = { Appl. Comput. Harmon. Anal.}, +% year = 2019, +% volume = 47, +% pages = {607--627}, +% url = {https://doi.org/10.1016/j.acha.2017.11.004} +%}
\ No newline at end of file diff --git a/buch/papers/reedsolomon/rekonstruktion.tex b/buch/papers/reedsolomon/rekonstruktion.tex index 8cb7744..89a700f 100644 --- a/buch/papers/reedsolomon/rekonstruktion.tex +++ b/buch/papers/reedsolomon/rekonstruktion.tex @@ -1,24 +1,25 @@ % -% teil3.tex -- Beispiel-File für Teil 3 +% rekonstruktion.tex +% Autor: Michael Steiner % % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil % \section{Nachricht Rekonstruieren \label{reedsolomon:section:rekonstruktion}} \rhead{Rekonstruktion} -Im letzten Kapitel haben wir eine Möglichkeit gefunden, wie wir die Fehlerhaften Stellen lokalisieren können. +Im letzten Kapitel haben wir eine Möglichkeit gefunden, wie wir die fehlerhaften Stellen lokalisieren können. Mit diesen Stellen soll es uns nun möglich sein, aus dem fehlerhaften empfangenen Nachrichtenvektor wieder unsere Nachricht zu rekonstruieren. Das Lokatorpolynom \[ -d(X) = (X - a^3)(X-a^8) +l(X) = (X - a^3)(X-a^8) \] -markiert dabei diese Fehlerhaften Stellen im Übertragungsvektor +markiert dabei diese fehlerhaften Stellen im Übertragungsvektor \[ w = [5,3,6,8,2,10,2,7,1,4]. \] Als Ausgangslage verwenden wir die Matrix, mit der wir den Nachrichtenvektor ursprünglich codiert haben. -Unser Ziel ist es wie auch schon im Kapitel X.X (Rekonstuktion ohne Fehler) eine Möglichkeit zu finden, wie wir den Übertragungsvektor decodieren können. -Aufgrund der Fehlerstellen müssen wir aber davon ausgehen, das wir nicht mehr den gleichen Weg verfolgen können wie wir im Kapitel X.X angewendet haben. +Unser Ziel ist es wie auch schon im Abschnitt \ref{reedsolomon:section:decohnefehler} eine Möglichkeit zu finden, wie wir den Übertragungsvektor decodieren können. +Aufgrund der Fehlerstellen müssen wir aber davon ausgehen, das wir nicht mehr den gleichen Weg verfolgen können wie wir im Abschnitt \ref{reedsolomon:section:decohnefehler} angewendet haben. Wir stellen also die Matrix auf und markieren gleichzeitig die Fehlerstellen. \[ @@ -82,21 +83,21 @@ Wir kennen aber das Resultat aus den letzten vier Spalten, da wir wissen, das di \end{pmatrix} = \begin{pmatrix} - 8^0& 8^0& 8^0& 8^0& 8^0& 8^0& \textcolor{green}{8^0}& \textcolor{green}{8^0}& \textcolor{green}{8^0}& \textcolor{green}{8^0}\\ - 8^0& 8^1& 8^2& 8^3& 8^4& 8^5& \textcolor{green}{8^6}& \textcolor{green}{8^7}& \textcolor{green}{8^8}& \textcolor{green}{8^9}\\ - 8^0& 8^2& 8^4& 8^6& 8^8& 8^{10}& \textcolor{green}{8^{12}}& \textcolor{green}{8^{14}}& \textcolor{green}{8^{16}}& \textcolor{green}{8^{18}}\\ - 8^0& 8^4& 8^8& 8^{12}& 8^{16}& 8^{20}& \textcolor{green}{8^{24}}& \textcolor{green}{8^{28}}& \textcolor{green}{8^{32}}& \textcolor{green}{8^{36}}\\ - 8^0& 8^5& 8^{10}& 8^{15}& 8^{20}& 8^{25}& \textcolor{green}{8^{30}}& \textcolor{green}{8^{35}}& \textcolor{green}{8^{40}}& \textcolor{green}{8^{45}}\\ - 8^0& 8^6& 8^{12}& 8^{18}& 8^{24}& 8^{30}& \textcolor{green}{8^{36}}& \textcolor{green}{8^{42}}& \textcolor{green}{8^{48}}& \textcolor{green}{8^{54}}\\ - 8^0& 8^7& 8^{14}& 8^{21}& 8^{28}& 8^{35}& \textcolor{green}{8^{42}}& \textcolor{green}{8^{49}}& \textcolor{green}{8^{56}}& \textcolor{green}{8^{63}}\\ - 8^0& 8^9& 8^{18}& 8^{27}& 8^{36}& 8^{45}& \textcolor{green}{8^{54}}& \textcolor{green}{8^{63}}& \textcolor{green}{8^{72}}& \textcolor{green}{8^{81}}\\ + 8^0& 8^0& 8^0& 8^0& 8^0& 8^0& \textcolor{darkgreen}{8^0}& \textcolor{darkgreen}{8^0}& \textcolor{darkgreen}{8^0}& \textcolor{darkgreen}{8^0}\\ + 8^0& 8^1& 8^2& 8^3& 8^4& 8^5& \textcolor{darkgreen}{8^6}& \textcolor{darkgreen}{8^7}& \textcolor{darkgreen}{8^8}& \textcolor{darkgreen}{8^9}\\ + 8^0& 8^2& 8^4& 8^6& 8^8& 8^{10}& \textcolor{darkgreen}{8^{12}}& \textcolor{darkgreen}{8^{14}}& \textcolor{darkgreen}{8^{16}}& \textcolor{darkgreen}{8^{18}}\\ + 8^0& 8^4& 8^8& 8^{12}& 8^{16}& 8^{20}& \textcolor{darkgreen}{8^{24}}& \textcolor{darkgreen}{8^{28}}& \textcolor{darkgreen}{8^{32}}& \textcolor{darkgreen}{8^{36}}\\ + 8^0& 8^5& 8^{10}& 8^{15}& 8^{20}& 8^{25}& \textcolor{darkgreen}{8^{30}}& \textcolor{darkgreen}{8^{35}}& \textcolor{darkgreen}{8^{40}}& \textcolor{darkgreen}{8^{45}}\\ + 8^0& 8^6& 8^{12}& 8^{18}& 8^{24}& 8^{30}& \textcolor{darkgreen}{8^{36}}& \textcolor{darkgreen}{8^{42}}& \textcolor{darkgreen}{8^{48}}& \textcolor{darkgreen}{8^{54}}\\ + 8^0& 8^7& 8^{14}& 8^{21}& 8^{28}& 8^{35}& \textcolor{darkgreen}{8^{42}}& \textcolor{darkgreen}{8^{49}}& \textcolor{darkgreen}{8^{56}}& \textcolor{darkgreen}{8^{63}}\\ + 8^0& 8^9& 8^{18}& 8^{27}& 8^{36}& 8^{45}& \textcolor{darkgreen}{8^{54}}& \textcolor{darkgreen}{8^{63}}& \textcolor{darkgreen}{8^{72}}& \textcolor{darkgreen}{8^{81}}\\ \end{pmatrix} \cdot \begin{pmatrix} - m_0 \\ m_1 \\ m_2 \\ m_3 \\ m_4 \\ m_5 \\ \textcolor{green}{m_6} \\ \textcolor{green}{m_7} \\ \textcolor{green}{m_8} \\ \textcolor{green}{m_9} \\ + m_0 \\ m_1 \\ m_2 \\ m_3 \\ m_4 \\ m_5 \\ \textcolor{darkgreen}{m_6} \\ \textcolor{darkgreen}{m_7} \\ \textcolor{darkgreen}{m_8} \\ \textcolor{darkgreen}{m_9} \\ \end{pmatrix} \] -Wir nehmen die Entsprechenden Spalten aus der Matrix heraus und erhalten so das Überbestimmte Gleichungssystem +Wir nehmen die entsprechenden Spalten aus der Matrix heraus und erhalten so das Überbestimmte Gleichungssystem \[ \begin{pmatrix} 5 \\ 3 \\ 6 \\ 2 \\ 10 \\ 2 \\ \textcolor{red}{7} \\ \textcolor{red}{4} \\ diff --git a/buch/papers/reedsolomon/restetabelle1.tex b/buch/papers/reedsolomon/restetabelle1.tex index a5055c0..3969ef2 100644 --- a/buch/papers/reedsolomon/restetabelle1.tex +++ b/buch/papers/reedsolomon/restetabelle1.tex @@ -1,24 +1,176 @@ % created by Michael Steiner % % Restetabelle von F_11: Addition -\begin{figure} + +% alternatives design +%\begin{figure} +%\begin{center} +%\begin{tabular}{|>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|} +%\hline +%+&0&1&2&3&4&5&6&7&8&9&10\\ +%\hline +%0&0&1&2&3&4&5&6&7&8&9&10\\ +%1&1&2&3&4&5&6&7&8&9&10&0\\ +%2&2&3&4&5&6&7&8&9&10&0&1\\ +%3&3&4&5&6&7&8&9&10&0&1&2\\ +%4&4&5&6&7&8&9&10&0&1&2&3\\ +%5&5&6&7&8&9&10&0&1&2&3&4\\ +%6&6&7&8&9&10&0&1&2&3&4&5\\ +%7&7&8&9&10&0&1&2&3&4&5&6\\ +%8&8&9&10&0&1&2&3&4&5&6&7\\ +%9&9&10&0&1&2&3&4&5&6&7&8\\ +%10&10&0&1&2&3&4&5&6&7&8&9\\ +%\hline +%\end{tabular} +%\end{center} +%\end{figure} + \begin{center} -\begin{tabular}{|>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|} -\hline -+&0&1&2&3&4&5&6&7&8&9&10\\ -\hline -0&0&1&2&3&4&5&6&7&8&9&10\\ -1&1&2&3&4&5&6&7&8&9&10&0\\ -2&2&3&4&5&6&7&8&9&10&0&1\\ -3&3&4&5&6&7&8&9&10&0&1&2\\ -4&4&5&6&7&8&9&10&0&1&2&3\\ -5&5&6&7&8&9&10&0&1&2&3&4\\ -6&6&7&8&9&10&0&1&2&3&4&5\\ -7&7&8&9&10&0&1&2&3&4&5&6\\ -8&8&9&10&0&1&2&3&4&5&6&7\\ -9&9&10&0&1&2&3&4&5&6&7&8\\ -10&10&0&1&2&3&4&5&6&7&8&9\\ -\hline -\end{tabular} + +\begin{tikzpicture}[>=latex,thick,scale=0.45] +\fill[color=gray!40] (0,0) rectangle (18,-1.5); +\fill[color=gray!40] (0,0) rectangle (1.5,-18); +\draw[step = 1.5, gray,very thin] (0,0) grid (18,-18); +\draw[very thick] (0,0) rectangle (18,-18); +\draw[very thick] (0,-1.5) -- (18,-1.5); +\draw[very thick] (1.5,0) -- (1.5,-18); +\node at (0.75,-0.75) {$+$}; +\foreach \x in {0,...,10} + \node at (2.25+\x*1.5,-0.75) {$\x$}; +\foreach \y in {0,...,10} + \node at (0.75,-2.25+\y*-1.5) {$\y$}; +% Row 0 +\node at ( 2.25,-2.25) {$0$}; +\node at ( 3.75,-2.25) {$1$}; +\node at ( 5.25,-2.25) {$2$}; +\node at ( 6.75,-2.25) {$3$}; +\node at ( 8.25,-2.25) {$4$}; +\node at ( 9.75,-2.25) {$5$}; +\node at (11.25,-2.25) {$6$}; +\node at (12.75,-2.25) {$7$}; +\node at (14.25,-2.25) {$8$}; +\node at (15.75,-2.25) {$9$}; +\node at (17.25,-2.25) {$10$}; +% Row 1 +\node at ( 2.25,-3.75) {$1$}; +\node at ( 3.75,-3.75) {$2$}; +\node at ( 5.25,-3.75) {$3$}; +\node at ( 6.75,-3.75) {$4$}; +\node at ( 8.25,-3.75) {$5$}; +\node at ( 9.75,-3.75) {$6$}; +\node at (11.25,-3.75) {$7$}; +\node at (12.75,-3.75) {$8$}; +\node at (14.25,-3.75) {$9$}; +\node at (15.75,-3.75) {$10$}; +\node at (17.25,-3.75) {$0$}; +% Row 2 +\node at ( 2.25,-5.25) {$2$}; +\node at ( 3.75,-5.25) {$3$}; +\node at ( 5.25,-5.25) {$4$}; +\node at ( 6.75,-5.25) {$5$}; +\node at ( 8.25,-5.25) {$6$}; +\node at ( 9.75,-5.25) {$7$}; +\node at (11.25,-5.25) {$8$}; +\node at (12.75,-5.25) {$9$}; +\node at (14.25,-5.25) {$10$}; +\node at (15.75,-5.25) {$0$}; +\node at (17.25,-5.25) {$1$}; +% Row 3 +\node at ( 2.25,-6.75) {$3$}; +\node at ( 3.75,-6.75) {$4$}; +\node at ( 5.25,-6.75) {$5$}; +\node at ( 6.75,-6.75) {$6$}; +\node at ( 8.25,-6.75) {$7$}; +\node at ( 9.75,-6.75) {$8$}; +\node at (11.25,-6.75) {$9$}; +\node at (12.75,-6.75) {$10$}; +\node at (14.25,-6.75) {$0$}; +\node at (15.75,-6.75) {$1$}; +\node at (17.25,-6.75) {$2$}; +% Row 4 +\node at ( 2.25,-8.25) {$4$}; +\node at ( 3.75,-8.25) {$5$}; +\node at ( 5.25,-8.25) {$6$}; +\node at ( 6.75,-8.25) {$7$}; +\node at ( 8.25,-8.25) {$8$}; +\node at ( 9.75,-8.25) {$9$}; +\node at (11.25,-8.25) {$10$}; +\node at (12.75,-8.25) {$0$}; +\node at (14.25,-8.25) {$1$}; +\node at (15.75,-8.25) {$2$}; +\node at (17.25,-8.25) {$3$}; +% Row 5 +\node at ( 2.25,-9.75) {$5$}; +\node at ( 3.75,-9.75) {$6$}; +\node at ( 5.25,-9.75) {$7$}; +\node at ( 6.75,-9.75) {$8$}; +\node at ( 8.25,-9.75) {$9$}; +\node at ( 9.75,-9.75) {$10$}; +\node at (11.25,-9.75) {$0$}; +\node at (12.75,-9.75) {$1$}; +\node at (14.25,-9.75) {$2$}; +\node at (15.75,-9.75) {$3$}; +\node at (17.25,-9.75) {$4$}; +% Row 6 +\node at ( 2.25,-11.25) {$6$}; +\node at ( 3.75,-11.25) {$7$}; +\node at ( 5.25,-11.25) {$8$}; +\node at ( 6.75,-11.25) {$9$}; +\node at ( 8.25,-11.25) {$10$}; +\node at ( 9.75,-11.25) {$0$}; +\node at (11.25,-11.25) {$1$}; +\node at (12.75,-11.25) {$2$}; +\node at (14.25,-11.25) {$3$}; +\node at (15.75,-11.25) {$4$}; +\node at (17.25,-11.25) {$5$}; +% Row 7 +\node at ( 2.25,-12.75) {$7$}; +\node at ( 3.75,-12.75) {$8$}; +\node at ( 5.25,-12.75) {$9$}; +\node at ( 6.75,-12.75) {$10$}; +\node at ( 8.25,-12.75) {$0$}; +\node at ( 9.75,-12.75) {$1$}; +\node at (11.25,-12.75) {$2$}; +\node at (12.75,-12.75) {$3$}; +\node at (14.25,-12.75) {$4$}; +\node at (15.75,-12.75) {$5$}; +\node at (17.25,-12.75) {$6$}; +% Row 8 +\node at ( 2.25,-14.25) {$8$}; +\node at ( 3.75,-14.25) {$9$}; +\node at ( 5.25,-14.25) {$10$}; +\node at ( 6.75,-14.25) {$0$}; +\node at ( 8.25,-14.25) {$1$}; +\node at ( 9.75,-14.25) {$2$}; +\node at (11.25,-14.25) {$3$}; +\node at (12.75,-14.25) {$4$}; +\node at (14.25,-14.25) {$5$}; +\node at (15.75,-14.25) {$6$}; +\node at (17.25,-14.25) {$7$}; +% Row 9 +\node at ( 2.25,-15.75) {$9$}; +\node at ( 3.75,-15.75) {$10$}; +\node at ( 5.25,-15.75) {$0$}; +\node at ( 6.75,-15.75) {$1$}; +\node at ( 8.25,-15.75) {$2$}; +\node at ( 9.75,-15.75) {$3$}; +\node at (11.25,-15.75) {$4$}; +\node at (12.75,-15.75) {$5$}; +\node at (14.25,-15.75) {$6$}; +\node at (15.75,-15.75) {$7$}; +\node at (17.25,-15.75) {$8$}; +% Row 10 +\node at ( 2.25,-17.25) {$10$}; +\node at ( 3.75,-17.25) {$0$}; +\node at ( 5.25,-17.25) {$1$}; +\node at ( 6.75,-17.25) {$2$}; +\node at ( 8.25,-17.25) {$3$}; +\node at ( 9.75,-17.25) {$4$}; +\node at (11.25,-17.25) {$5$}; +\node at (12.75,-17.25) {$6$}; +\node at (14.25,-17.25) {$7$}; +\node at (15.75,-17.25) {$8$}; +\node at (17.25,-17.25) {$9$}; +\end{tikzpicture} + \end{center} -\end{figure}
\ No newline at end of file diff --git a/buch/papers/reedsolomon/restetabelle2.tex b/buch/papers/reedsolomon/restetabelle2.tex index 887c981..1a9815c 100644 --- a/buch/papers/reedsolomon/restetabelle2.tex +++ b/buch/papers/reedsolomon/restetabelle2.tex @@ -1,24 +1,176 @@ % created by Michael Steiner % % Restetabelle von F_11: Multiplikation -\begin{figure} + +% alternatives design +%\begin{figure} +%\begin{center} +%\begin{tabular}{|>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|} +%\hline +%\cdot&0&1&2&3&4&5&6&7&8&9&10\\ +%\hline +%0&0&0&0&0&0&0&0&0&0&0&0\\ +%1&0&1&2&3&4&5&6&7&8&9&10\\ +%2&0&2&4&6&8&10&1&3&5&7&9\\ +%3&0&3&6&9&1&4&7&10&2&5&8\\ +%4&0&4&8&1&5&9&2&6&10&3&7\\ +%5&0&5&10&4&9&3&8&2&7&1&6\\ +%6&0&6&1&7&2&8&3&9&4&10&5\\ +%7&0&7&3&10&6&2&9&5&1&8&4\\ +%8&0&8&5&2&10&7&4&1&9&6&3\\ +%9&0&9&7&5&3&1&10&8&6&4&2\\ +%10&0&10&9&8&7&6&5&4&3&2&1\\ +%\hline +%\end{tabular} +%\end{center} +%\end{figure} + \begin{center} -\begin{tabular}{|>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|} -\hline -\cdot&0&1&2&3&4&5&6&7&8&9&10\\ -\hline -0&0&0&0&0&0&0&0&0&0&0&0\\ -1&0&1&2&3&4&5&6&7&8&9&10\\ -2&0&2&4&6&8&10&1&3&5&7&9\\ -3&0&3&6&9&1&4&7&10&2&5&8\\ -4&0&4&8&1&5&9&2&6&10&3&7\\ -5&0&5&10&4&9&3&8&2&7&1&6\\ -6&0&6&1&7&2&8&3&9&4&10&5\\ -7&0&7&3&10&6&2&9&5&1&8&4\\ -8&0&8&5&2&10&7&4&1&9&6&3\\ -9&0&9&7&5&3&1&10&8&6&4&2\\ -10&0&10&9&8&7&6&5&4&3&2&1\\ -\hline -\end{tabular} -\end{center} -\end{figure}
\ No newline at end of file + + \begin{tikzpicture}[>=latex,thick,scale=0.45] + \fill[color=gray!40] (0,0) rectangle (18,-1.5); + \fill[color=gray!40] (0,0) rectangle (1.5,-18); + \draw[step = 1.5, gray,very thin] (0,0) grid (18,-18); + \draw[very thick] (0,0) rectangle (18,-18); + \draw[very thick] (0,-1.5) -- (18,-1.5); + \draw[very thick] (1.5,0) -- (1.5,-18); + \node at (0.75,-0.75) {$\cdot$}; + \foreach \x in {0,...,10} + \node at (2.25+\x*1.5,-0.75) {$\x$}; + \foreach \y in {0,...,10} + \node at (0.75,-2.25+\y*-1.5) {$\y$}; + % Row 0 + \node at ( 2.25,-2.25) {$0$}; + \node at ( 3.75,-2.25) {$0$}; + \node at ( 5.25,-2.25) {$0$}; + \node at ( 6.75,-2.25) {$0$}; + \node at ( 8.25,-2.25) {$0$}; + \node at ( 9.75,-2.25) {$0$}; + \node at (11.25,-2.25) {$0$}; + \node at (12.75,-2.25) {$0$}; + \node at (14.25,-2.25) {$0$}; + \node at (15.75,-2.25) {$0$}; + \node at (17.25,-2.25) {$0$}; + % Row 1 + \node at ( 2.25,-3.75) {$0$}; + \node at ( 3.75,-3.75) {$1$}; + \node at ( 5.25,-3.75) {$2$}; + \node at ( 6.75,-3.75) {$3$}; + \node at ( 8.25,-3.75) {$4$}; + \node at ( 9.75,-3.75) {$5$}; + \node at (11.25,-3.75) {$6$}; + \node at (12.75,-3.75) {$7$}; + \node at (14.25,-3.75) {$8$}; + \node at (15.75,-3.75) {$9$}; + \node at (17.25,-3.75) {$10$}; + % Row 2 + \node at ( 2.25,-5.25) {$0$}; + \node at ( 3.75,-5.25) {$2$}; + \node at ( 5.25,-5.25) {$4$}; + \node at ( 6.75,-5.25) {$6$}; + \node at ( 8.25,-5.25) {$8$}; + \node at ( 9.75,-5.25) {$10$}; + \node at (11.25,-5.25) {$1$}; + \node at (12.75,-5.25) {$3$}; + \node at (14.25,-5.25) {$5$}; + \node at (15.75,-5.25) {$7$}; + \node at (17.25,-5.25) {$9$}; + % Row 3 + \node at ( 2.25,-6.75) {$0$}; + \node at ( 3.75,-6.75) {$3$}; + \node at ( 5.25,-6.75) {$6$}; + \node at ( 6.75,-6.75) {$9$}; + \node at ( 8.25,-6.75) {$1$}; + \node at ( 9.75,-6.75) {$4$}; + \node at (11.25,-6.75) {$7$}; + \node at (12.75,-6.75) {$10$}; + \node at (14.25,-6.75) {$2$}; + \node at (15.75,-6.75) {$5$}; + \node at (17.25,-6.75) {$8$}; + % Row 4 + \node at ( 2.25,-8.25) {$0$}; + \node at ( 3.75,-8.25) {$4$}; + \node at ( 5.25,-8.25) {$8$}; + \node at ( 6.75,-8.25) {$1$}; + \node at ( 8.25,-8.25) {$5$}; + \node at ( 9.75,-8.25) {$9$}; + \node at (11.25,-8.25) {$2$}; + \node at (12.75,-8.25) {$6$}; + \node at (14.25,-8.25) {$10$}; + \node at (15.75,-8.25) {$3$}; + \node at (17.25,-8.25) {$7$}; + % Row 5 + \node at ( 2.25,-9.75) {$0$}; + \node at ( 3.75,-9.75) {$5$}; + \node at ( 5.25,-9.75) {$10$}; + \node at ( 6.75,-9.75) {$4$}; + \node at ( 8.25,-9.75) {$9$}; + \node at ( 9.75,-9.75) {$3$}; + \node at (11.25,-9.75) {$8$}; + \node at (12.75,-9.75) {$2$}; + \node at (14.25,-9.75) {$7$}; + \node at (15.75,-9.75) {$1$}; + \node at (17.25,-9.75) {$6$}; + % Row 6 + \node at ( 2.25,-11.25) {$0$}; + \node at ( 3.75,-11.25) {$6$}; + \node at ( 5.25,-11.25) {$1$}; + \node at ( 6.75,-11.25) {$7$}; + \node at ( 8.25,-11.25) {$2$}; + \node at ( 9.75,-11.25) {$8$}; + \node at (11.25,-11.25) {$3$}; + \node at (12.75,-11.25) {$9$}; + \node at (14.25,-11.25) {$4$}; + \node at (15.75,-11.25) {$10$}; + \node at (17.25,-11.25) {$5$}; + % Row 7 + \node at ( 2.25,-12.75) {$0$}; + \node at ( 3.75,-12.75) {$7$}; + \node at ( 5.25,-12.75) {$3$}; + \node at ( 6.75,-12.75) {$10$}; + \node at ( 8.25,-12.75) {$6$}; + \node at ( 9.75,-12.75) {$2$}; + \node at (11.25,-12.75) {$9$}; + \node at (12.75,-12.75) {$5$}; + \node at (14.25,-12.75) {$1$}; + \node at (15.75,-12.75) {$8$}; + \node at (17.25,-12.75) {$4$}; + % Row 8 + \node at ( 2.25,-14.25) {$0$}; + \node at ( 3.75,-14.25) {$8$}; + \node at ( 5.25,-14.25) {$5$}; + \node at ( 6.75,-14.25) {$2$}; + \node at ( 8.25,-14.25) {$10$}; + \node at ( 9.75,-14.25) {$7$}; + \node at (11.25,-14.25) {$4$}; + \node at (12.75,-14.25) {$1$}; + \node at (14.25,-14.25) {$9$}; + \node at (15.75,-14.25) {$6$}; + \node at (17.25,-14.25) {$3$}; + % Row 9 + \node at ( 2.25,-15.75) {$0$}; + \node at ( 3.75,-15.75) {$9$}; + \node at ( 5.25,-15.75) {$7$}; + \node at ( 6.75,-15.75) {$5$}; + \node at ( 8.25,-15.75) {$3$}; + \node at ( 9.75,-15.75) {$1$}; + \node at (11.25,-15.75) {$10$}; + \node at (12.75,-15.75) {$8$}; + \node at (14.25,-15.75) {$6$}; + \node at (15.75,-15.75) {$4$}; + \node at (17.25,-15.75) {$2$}; + % Row 10 + \node at ( 2.25,-17.25) {$0$}; + \node at ( 3.75,-17.25) {$10$}; + \node at ( 5.25,-17.25) {$9$}; + \node at ( 6.75,-17.25) {$8$}; + \node at ( 8.25,-17.25) {$7$}; + \node at ( 9.75,-17.25) {$6$}; + \node at (11.25,-17.25) {$5$}; + \node at (12.75,-17.25) {$4$}; + \node at (14.25,-17.25) {$3$}; + \node at (15.75,-17.25) {$2$}; + \node at (17.25,-17.25) {$1$}; + \end{tikzpicture} + +\end{center}
\ No newline at end of file |