diff options
Diffstat (limited to '')
| -rw-r--r-- | buch/papers/reedsolomon/codebsp.tex | 94 | ||||
| -rw-r--r-- | buch/papers/reedsolomon/hilfstabellen.tex | 21 |
2 files changed, 87 insertions, 28 deletions
diff --git a/buch/papers/reedsolomon/codebsp.tex b/buch/papers/reedsolomon/codebsp.tex index 5b67c43..818078e 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,41 +45,63 @@ 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. + +Wenn wir jetzt sämtliche Zahlen von $\mathbb{F}_{11}$ in $a$ einsetzen + +% 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\} \\ @@ -94,21 +132,26 @@ $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. -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. \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} -Für eine elegantere Formulierung stellen wir das ganze als Matrix dar, wobei $m$ unser Nachrichtenvektor, $A$ die Transformationsmatrix und $v$ unser Übertragungsvektor ist. - + +\subsection{Allgemeine Codierung + \label{reedsolomon:subsection:algCod}} + +Für eine elegantere Formulierung stellen wir das ganze als Matrix dar, wobei $m$ unsere Nachricht, $A$ die Transformationsmatrix und $v$ unser Übertragungsvektor ist. \[ 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 +170,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 \[ 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/hilfstabellen.tex b/buch/papers/reedsolomon/hilfstabellen.tex new file mode 100644 index 0000000..10e4fd1 --- /dev/null +++ b/buch/papers/reedsolomon/hilfstabellen.tex @@ -0,0 +1,21 @@ +% +% 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} + +\textbf{TODO}: gibt es eine besser darstellungsart der tabellen? (\& platzierung der subsections) + +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 |