diff options
Diffstat (limited to 'buch/papers/reedsolomon/codebsp.tex')
| -rw-r--r-- | buch/papers/reedsolomon/codebsp.tex | 51 |
1 files changed, 26 insertions, 25 deletions
diff --git a/buch/papers/reedsolomon/codebsp.tex b/buch/papers/reedsolomon/codebsp.tex index 67f33da..037fba7 100644 --- a/buch/papers/reedsolomon/codebsp.tex +++ b/buch/papers/reedsolomon/codebsp.tex @@ -9,7 +9,7 @@ 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 einen Körper festlegen. Dabei müssen wir die Definition \ref{buch:endlichekoerper:def:galois-koerper} 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 $\mathbb{F}_{q}$ mit $q = 11$ fest. -Zur Hilfestellung zum Rechnen in $\mathbb{F}_{11}$ können die beiden Tabellen \ref{reedsolomon:subsection:adtab} und \ref{reedsolomon:subsection:mptab} hinzugezogen werden. Diese Tabellen enthalten die Resultate der arithmetischen Operationen im Körper $\mathbb{F}_{11}$, die durchgeführt werden können. +Zur Hilfestellung beim Rechnen in $\mathbb{F}_{11}$ können die beiden Tabellen \ref{reedsolomon:subsection:adtab} und \ref{reedsolomon:subsection:mptab} hinzugezogen werden. Diese Tabellen enthalten die Resultate der arithmetischen Operationen im Körper $\mathbb{F}_{11}$, die 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. \rhead{Codierung eines Beispiels} @@ -26,7 +26,7 @@ Der Nachrichtenblock im Beispiel besteht aus \[ 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. +wobei die Null weggelassen wird. Wenn wir versuchen würden, mit der Null zu codieren, 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. @@ -37,28 +37,28 @@ wobei die Null weggelassen wird. Wenn wir versuchen würden, mit der Null zu cod %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. +Im nächsten Schritt bestimmen wir, wie viele Fehler $t$ während der Übertragung maximal auftreten dürfen, damit wir sie noch korrigieren können. Unser Beispielcode sollte in der Lage sein \[ t = 2 \] Fehlerstellen korrigieren zu können. -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 +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 bleibt für Nutzdaten $k$ in der Nachricht übrig. +Bei maximal 2 Fehlern können wir noch \[ k = n - 2t = 6\text{ Zahlen} \] übertragen. -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. +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 fehlerhaften 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 für das Beispiel 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 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. +Solange diese Stellen vor dem Codieren und nach dem Decodieren den Wert null haben, ist die Nachricht fehlerfrei übertragen worden. Da wir in den folgenden Abschnitten mit Polynomen arbeiten, stellen wir die Nachricht auch noch als Polynom \[ @@ -77,7 +77,7 @@ dar. \label{reedsolomon:subsection:diskFT}} Im vorherigen Abschnitt \ref{reedsolomon:section:dtf} haben wir schon einmal die diskrete Fouriertransformation zum Codieren einer Nachricht verwendet. In den endlichen Körpern wird dies jedoch nicht gelingen, da die Eulersche Zahl $e$ in endlichen Körpern nicht existiert. -Wir wählen deshalb eine Zahl $a$, die die gleichen Aufgaben haben soll wie $e^{\frac{j}{2 \pi}}$ in der diskreten Fouriertransformation, nur mit dem Unterschied, dass $a$ in $\mathbb{F}_{11}$ ist. Dazu soll die Potenz von $a$ den gesamten Zahlenbereich von $\mathbb{F}_{11}$ abdecken. +Wir wählen deshalb eine Zahl $a$, die die gleiche Aufgabe haben soll wie $e^{\frac{j}{2 \pi}}$ in der diskreten Fouriertransformation, nur mit dem Unterschied, dass $a$ in $\mathbb{F}_{11}$ ist. Dazu soll die Potenz von $a$ den gesamten Zahlenbereich von $\mathbb{F}_{11}$ abdecken. Dazu ändern wir die Darstellung von \[ \mathbb{F}_{11} = \{0,1,2,3,4,5,6,7,8,9,10\} @@ -119,17 +119,18 @@ in die von $a$ abhängige Schreibweise \index{Einheitswurzel, primitiv}% Wenn wir jetzt Zahlen von $\mathbb{F}_{11}$ an Stelle von $a$ einsetzen, erhalten wir \begin{center} -\begin{tabular}{c c c c c c c} -$a = 1$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1, 1, 1, 1, 1, 1, 1, 1, 1, 1\}$ & $\neq$ & $\mathbb{F}_{11}\setminus\{0\}$ \\ -$a = 2$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1, 2, 4, 8, 5, 10, 9, 7, 3, 6\}$ & $ = $ & $\mathbb{F}_{11}\setminus\{0\}$ \\ -$a = 3$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1, 3, 9, 5, 4, 1, 3, 9, 5, 4\}$ & $\neq$ & $\mathbb{F}_{11}\setminus\{0\}$ \\ -$a = 4$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1, 4, 5, 9, 3, 1, 4, 5, 9, 3\}$ & $\neq$ & $\mathbb{F}_{11}\setminus\{0\}$ \\ -$a = 5$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1, 5, 3, 4, 9, 1, 5, 3, 4, 9\}$ & $\neq$ & $\mathbb{F}_{11}\setminus\{0\}$ \\ -$a = 6$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1, 6, 3, 7, 9, 10, 5, 8, 4, 2\}$ & $ = $ & $\mathbb{F}_{11}\setminus\{0\}$ \\ -$a = 7$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1, 7, 5, 2, 3, 10, 4, 6, 9, 8\}$ & $ = $ & $\mathbb{F}_{11}\setminus\{0\}$ \\ -$a = 8$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1, 8, 9, 6, 4, 10, 3, 2, 5, 7\}$ & $ = $ & $\mathbb{F}_{11}\setminus\{0\}$ \\ -$a = 9$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1, 9, 4, 3, 5, 1, 9, 4, 3, 5\}$ & $\neq$ & $\mathbb{F}_{11}\setminus\{0\}$ \\ -$a = 10$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1, 10, 1, 10, 1, 10, 1, 10, 1, 10\}$ & $\neq$ & $\mathbb{F}_{11}\setminus\{0\}$. \\ +\def\s{\phantom{0}} +\begin{tabular}{c c c c c c l} +$a = \s1$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1,\s1,\s1,\s1,\s1,\s1,\s1,\s1,\s1,\s1\}$ & $\neq$ & $\mathbb{F}_{11}\setminus\{0\}$ \\ +$a = \s2$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1,\s2,\s4,\s8,\s5,10,\s9,\s7,\s3,\s6\}$ & $ = $ & $\mathbb{F}_{11}\setminus\{0\}$ \\ +$a = \s3$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1,\s3,\s9,\s5,\s4,\s1,\s3,\s9,\s5,\s4\}$ & $\neq$ & $\mathbb{F}_{11}\setminus\{0\}$ \\ +$a = \s4$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1,\s4,\s5,\s9,\s3,\s1,\s4,\s5,\s9,\s3\}$ & $\neq$ & $\mathbb{F}_{11}\setminus\{0\}$ \\ +$a = \s5$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1,\s5,\s3,\s4,\s9,\s1,\s5,\s3,\s4,\s9\}$ & $\neq$ & $\mathbb{F}_{11}\setminus\{0\}$ \\ +$a = \s6$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1,\s6,\s3,\s7,\s9, 10,\s5,\s8,\s4,\s2\}$ & $ = $ & $\mathbb{F}_{11}\setminus\{0\}$ \\ +$a = \s7$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1,\s7,\s5,\s2,\s3,10,\s4,\s6,\s9,\s8\}$ & $ = $ & $\mathbb{F}_{11}\setminus\{0\}$ \\ +$a = \s8$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1,\s8,\s9,\s6,\s4, 10,\s3,\s2,\s5,\s7\}$ & $ = $ & $\mathbb{F}_{11}\setminus\{0\}$ \\ +$a = \s9$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1,\s9,\s4,\s3,\s5,\s1,\s9,\s4,\s3,\s5\}$ & $\neq$ & $\mathbb{F}_{11}\setminus\{0\}$ \\ +$a = 10$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1, 10,\s1,10,\s1, 10,\s1, 10,\s1, 10\}$ & $\neq$ & $\mathbb{F}_{11}\setminus\{0\}$. \\ \end{tabular} \end{center} %\begin{center} @@ -147,15 +148,15 @@ $a = 10$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1, 10, 1, 10, 1 %$a = 10 :$& $\qquad \mathbb{Z}_{11}\setminus\{0\}$ &$=$& $\{1, 10, 1, 10, 1, 10, 1, 10, 1, 10\}$ %\end{tabular} %\end{center} -Es fällt auf, dass wir für $a$ die Zahlen $2,6,7,8$ Mengen 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 Einheitswurzel auszuwählen, mit der wir weiter rechnen wollen. Für das Beispiel wählen wir die Zahl $a = 8$. +Es fällt auf, dass wir für $a$ die Zahlen $2,6,7,8$ Mengen erhalten, die tatsächlich den gesamten Zahlenraum von $\mathbb{F}_{11}$ abbilden. Solche Zahlen werden \em primitive Einheitswurzeln \em genannt. +Wenden wir diese Vorgehensweise auch für andere endliche Körper an, so werden wir sehen, dass wir immer mindestens zwei solcher Einheitswurzeln 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 = 8$. \subsubsection{Bildung einer Transformationsmatrix \label{reedsolomon:subsection:transMat}} \index{Transformationsmatrix}% -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 setzen wir alle Zahlen in $\mathbb{F}_{11}\setminus\{0\}$ nacheinander in $m(X)$ ein. Da wir zuvor eine von $a$ abhängige Schreibweise gewählt haben setzen wir stattdessen $a^i$ ein mit $a = 8$ als die von uns gewählten primitiven Einheitswurzel. Daraus ergibt sich +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 setzen wir alle Zahlen in $\mathbb{F}_{11}\setminus\{0\}$ nacheinander in $m(X)$ ein. Da wir zuvor eine von $a$ abhängige Schreibweise gewählt haben, setzen wir stattdessen $a^i$ ein mit $a = 8$ als die von uns gewählten primitiven Einheitswurzel. Daraus ergibt sich %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. @@ -164,7 +165,7 @@ Für die Codierung setzen wir alle Zahlen in $\mathbb{F}_{11}\setminus\{0\}$ nac \begin{tabular}{c} $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 \\ + \vdots \\[5pt] $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} @@ -175,7 +176,7 @@ als unser Übertragungsvektor. \label{reedsolomon:subsection:algCod}} Um das Ganze noch ein wenig übersichtlicher zu gestalten, können wir die Polynome zu einer Matrix zusammenfassen, die unsere Transformationsmatrix $A$ bildet. -Für die allgemeine 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: +Für die allgemeine 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\\ |