diff options
| -rw-r--r-- | buch/papers/reedsolomon/codebsp.tex | 6 | ||||
| -rw-r--r-- | buch/papers/reedsolomon/decmitfehler.tex | 43 | ||||
| -rw-r--r-- | buch/papers/reedsolomon/decohnefehler.tex | 115 | ||||
| -rw-r--r-- | buch/papers/reedsolomon/hilfstabellen.tex | 2 | ||||
| -rw-r--r-- | buch/papers/reedsolomon/main.tex | 6 | ||||
| -rw-r--r-- | buch/papers/reedsolomon/nachschlagewerk.tex | 4 | ||||
| -rw-r--r-- | buch/papers/reedsolomon/rekonstruktion.tex | 9 | ||||
| -rw-r--r-- | buch/papers/reedsolomon/zusammenfassung.tex | 15 |
8 files changed, 156 insertions, 44 deletions
diff --git a/buch/papers/reedsolomon/codebsp.tex b/buch/papers/reedsolomon/codebsp.tex index 6ab792a..0339d9c 100644 --- a/buch/papers/reedsolomon/codebsp.tex +++ b/buch/papers/reedsolomon/codebsp.tex @@ -147,12 +147,12 @@ $a = 10$ & $\Rightarrow$ & $\{a^i | 0 \le i \le 10\}$ & $=$ & $\{1, 10, 1, 10, 1 %\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 = 8$. +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$. \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 +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. % @@ -164,7 +164,7 @@ Mit der Wahl einer Einheitswurzel ist es uns jetzt möglich, unsere Nachricht zu $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. +als unser Übertragungsvektor. \subsection{Allgemeine Codierung \label{reedsolomon:subsection:algCod}} diff --git a/buch/papers/reedsolomon/decmitfehler.tex b/buch/papers/reedsolomon/decmitfehler.tex index 1f195e9..a46d7da 100644 --- a/buch/papers/reedsolomon/decmitfehler.tex +++ b/buch/papers/reedsolomon/decmitfehler.tex @@ -10,12 +10,12 @@ Bisher haben wir die Decodierung unter der Bedingung durchgeführt, dass der Üb 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] \] auf. - Senden wir jetzt unser Übertragungsvektor $v$ durch diesen Kanal addiert sich der Fehlervektor $u$ auf unsere Übertragung und wir erhalten \begin{center} @@ -73,10 +73,10 @@ als neuen, fehlerbehafteten Übertragungsvektor $w$ auf der Empfängerseite. % %\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. +Als Empfänger wissen wir 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,}_{\text{Syndrom}}5,4,5,7,6,7]. +r = [\underbrace{5,7,4,10,}_{\text{Syndrom}}5,4,5,7,6,7] \] 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. @@ -85,21 +85,29 @@ Der Nachrichtenblock weisst jetzt ein \em Syndrom \em auf, welches anzeigt, dass %\[ %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. +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 +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 berechnen wir die Differenz $d$ des empfangenen und dem gesendeten Übertragungsvektor mit +%Alle Stellen in $d$, die nicht null sind sind demnach fehler. +% +%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)$. + $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. +und nennen $d(X)$ als unseres Fehlerstellenpolynom. Dieses Polynom soll uns sagen, welche Stellen korrekt und welche fehlerhaft sind. -Setzen wir jetzt noch unsere Einheitswurzel aus dem Beispiel ein so erhalten wir +Durch das verwenden von $m(X)$ stossen wir auf weitere Probleme, da wir den Nachrichtenvektor auf der Empfängerseite nicht kennen (unser Ziel ist es ja genau diesen zu finden). Dieses Problem betrachten wir im Abschnitt \ref{reedsolomon:subsection:nachrichtenvektor} genauer. Um die Überlegungen in den folgenden Abschnitten besser zu verstehen sei $m(X)$ bekannt auf der Empfängerseite. + +%Dies wird uns zwar andere sorgen wegen $m(X)$ bereiten, wir werden werden deshalb erst in Abschnitt \ref{reedsolomon:subsection:nachrichtenvektor} darauf zurückkommen. + +Setzen wir jetzt 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 \\ @@ -126,15 +134,15 @@ Für das einfache Bestimmen von Hand mag dies ja noch ausreichen, jedoch können \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 +Zuerst betrachten wir den Satz von Fermat, dessen Funktionsweise wir in Abschnitt \ref{buch:section:galoiskoerper} kennengelernt haben. Der besagt, dass \[ f(X) = X^{q-1} -1 = 0 \] -wobei dies für jedes $q$ gilt. Setzen wir also das $q$ von unserem Beispiel ein +gilt für jedes $X$. Setzen wir 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 stellen dies als Nullstellenform (\textcolor{red}{richtiger name für die Schreibweise?}) dar. So ergibt sich die Darstellung +und stellen dies als Faktorisierung 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). \] @@ -145,7 +153,7 @@ Wir können jetzt auch $d(X)$ nach der gleichen Überlegung darstellen als 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 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. +Dies liegt daran, dass wir ja zwei Fehlerstellen (grau markiert) haben, die nicht Null sind. Diese fassen wir zum Restpolynom $p(X)$ zusammen. Wenn wir jetzt den grössten gemeinsamen Teiler von $f(X)$ und $d(X)$ berechnen, so erhalten wir mit \[ \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) @@ -174,7 +182,7 @@ 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. +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, auf der Empfängerseite aber nicht kennen. \subsection{Der problematische Nachrichtenvektor $m(X)$ \label{reedsolomon:subsection:nachrichtenvektor}} @@ -190,20 +198,18 @@ Wir könnten uns höchstens noch fragen, ob wir tatsächlich nichts über den Na \[ m = [0,0,0,0,4,7,2,5,8,1] \] -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 +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 \[ m = [0,0,0,0,?,?,?,?,?,?]. \] -Wie der Zufall es so will liegt an diesen vier Stellen auch die Information, wo die Fehlerstellen liegen. Daher reicht es auch aus +Nach der Definition des Reed-Solomon-Codes soll an genau diesen vier Stellen auch die Information befinden, wo die Fehlerstellen liegen. Daher reicht es auch aus % darum werden die stellen auch als fehlerkorrekturstellen bezeichnet \[ d(X) = 5X^9 + 7X^8 + 4X^7 + 10X^6 + p(X) \] 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}} @@ -294,6 +300,7 @@ Daraus erhalten wir die Faktoren \[ l(X) = 2X^2 + 5 \qquad \rightarrow \qquad l(X) = 2(X-5)(X-6). \] +\subsubsection{Schritt 3: Fehlerstellen bestimmen} Unser gesuchtes Lokatorpolynom hat also die Form \[ l(X) = (X-a^i)(X-a^j). diff --git a/buch/papers/reedsolomon/decohnefehler.tex b/buch/papers/reedsolomon/decohnefehler.tex index 3b709f3..0470db0 100644 --- a/buch/papers/reedsolomon/decohnefehler.tex +++ b/buch/papers/reedsolomon/decohnefehler.tex @@ -5,7 +5,7 @@ % \section{Decodierung: Ansatz ohne Fehler \label{reedsolomon:section:decohnefehler}} -\rhead{fehlerlose rekonstruktion} +\rhead{Decodierung ohne Fehler} 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. @@ -33,7 +33,7 @@ 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. \] -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$. +Damit beschäftigen wir uns im Abschnitt \ref{reedsolomon:subsection:sfaktor} weiter, konkret suchen wir momentan aber eine Inverse für unsere primitive Einheitswurzel $a$. \[ 8^1 \qquad \rightarrow \qquad 8^{-1} \] @@ -45,7 +45,7 @@ Mit einem solchen Problem haben wir uns bereits in Abschnitt \ref{buch:section:e \subsection{Inverse der primitiven Einheitswurzel \label{reedsolomon:subsection:invEinh}} -Die Funktionsweise des euklidischen Algorithmus ist im Kapitel \ref{buch:section:euklid} ausführlich beschrieben. +Die Funktionsweise des euklidischen Algorithmus ist im Abschnitt \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 @@ -76,21 +76,112 @@ 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. Die inverse Transformationsmatrix $A^{-1}$ bilden wir, indem wir jetzt die inverse primitive Einheitswurzel anstelle der primitiven Einheitswurzel in die Matrix einsetzen: +\[ +\begin{pmatrix} + 8^0 & 8^0 & 8^0 & 8^0 & \dots & 8^0 \\ + 8^0 & 8^{-1} & 8^{-2} & 8^{-3} & \dots & 8^{-9} \\ + 8^0 & 8^{-2} & 8^{-4} & 8^{-6} & \dots & 8^{-18} \\ + 8^0 & 8^{-3} & 8^{-6} & 8^{-9} & \dots & 8^{-27} \\ + \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ + 8^0 & 8^{-9} & 8^{-18} & 8^{-27} & \dots & 8^{-81} \\ +\end{pmatrix} +\qquad +\Rightarrow +\qquad +\begin{pmatrix} + 7^0 & 7^0 & 7^0 & 7^0 & \dots & 7^0 \\ + 7^0 & 7^{1} & 7^{2} & 7^{3} & \dots & 7^{9} \\ + 7^0 & 7^{2} & 7^{4} & 7^{6} & \dots & 7^{18} \\ + 7^0 & 7^{3} & 7^{6} & 7^{9} & \dots & 7^{27} \\ + \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ + 7^0 & 7^{9} & 7^{18} & 7^{27} & \dots & 7^{81} \\ +\end{pmatrix} +\] -\subsection{Allgemeine Decodierung - \label{reedsolomon:subsection:algdec}} +\subsection{Der Faktor $s$ + \label{reedsolomon:subsection:sfaktor}} +Die diskrete Fouriertransformation benötigt für die Inverse einen Vorfaktor von $\frac{1}{2\pi}$. +Primitiv nehmen wir an, dass wir für die Inverse Transformationsmatrix ebenfalls einen benötigen. +Nur stellt sich jetzt die Frage, wie wir diesen Vorfaktor in unserem Fall ermitteln können. +Dafür betrachten wir eine Regel aus der Linearen Algebra, nämlich dass -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 +A \cdot A^{-1} = E +\] +entsprechen muss. +Ist dies nicht der Fall, so benötigt $A^{-1}$ eben genau diesen Korrekturfaktor und ändert die Gleichung so zu +\begin{equation} + A \cdot s \cdot A^{-1} = E. + \label{reedsolomon:equation:sfaktor} +\end{equation} +%\[ +%A \cdot s \cdot A^{-1} = E. +%\] +Somit sollte es für uns ein leichtes Spiel sein, $s$ für unser Beispiel zu ermitteln: +\[ +\begin{pmatrix} + 8^0 & 8^0 & 8^0 & \dots & 8^0 \\ + 8^0 & 8^1 & 8^2 & \dots & 8^9 \\ + 8^0 & 8^2 & 8^4 & \dots & 8^{18} \\ + \vdots & \vdots & \vdots & \ddots & \vdots \\ + 8^0 & 8^9 & 8^{18} & \dots & 8^{81} \\ +\end{pmatrix} +\cdot +\begin{pmatrix} + 7^0 & 7^0 & 7^0 & \dots & 7^0 \\ + 7^0 & 7^{1} & 7^{2} & \dots & 7^{9} \\ + 7^0 & 7^{2} & 7^{4} & \dots & 7^{18} \\ + \vdots & \vdots & \vdots & \ddots & \vdots \\ + 7^0 & 7^{9} & 7^{18} & \dots & 7^{81} \\ +\end{pmatrix} += +\begin{pmatrix} + 10 & 0 & 0 & \dots & 0 \\ + 0 & 10 & 0 & \dots & 0 \\ + 0 & 0 & 10 & \dots & 0 \\ + \vdots & \vdots & \vdots & \ddots & \vdots \\ + 0 & 0 & 0 & \dots & 10 \\ +\end{pmatrix} \] -den wir noch bestimmen müssen. -Glücklicherweise lässt der sich analog wie bei der inversen diskreten Fouriertransformation bestimmen und beträgt +Aus der letzten Matrix folgt, dass wir \[ -s = \frac{1}{10}. +s = \dfrac{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$ in $\mathbb{F}_{11}$ ergibt. Somit lässt sich der Nachrichtenvektor einfach bestimmen mit +als unseren Vorfaktor setzen müssen um die Gleichung \ref{reedsolomon:equation:sfaktor} zu erfüllen. Da wir in $\mathbb{F}_{11}$ nur mit ganzen Zahlen arbeiten schreiben wir $\frac{1}{10}$ in $10^{-1}$ um und bestimmen diese Inverse erneut mit dem euklidischen Algorithmus und erhalten für $10^{-1} = 10$ als unseren Vorfaktor in $\mathbb{F}_{11}$. +% +%erfüllt wird. Wir schreiben den Bruch um in $\frac{1}{10} = 10^{-1}$ und wenden darauf erneut den euklidischen Algorithmus an und erhalten somit den Vorfaktor $10^{-1} = 10 = s$ in $\mathbb{F}_{11}$. +% +%Um $s$ eindeutig zu bestimmen müssen wir $\frac{1}{10}$ nur noch in den Bereich von $\mathbb{F}_{11}$ verschieben. Wie sich herausstellt können wir das recht einfach bewerkstelligen, da $\frac{1}{10} = 10^{-1}$ entspricht. Daraus können wir $s$ mit dem euklidischen Algorithmus bestimmen und stellen fest, dass $10^{-1} = 10$ in $\mathbb{F}_{11}$ ergibt. +% +%Da $s$ jetzt ein Bruch ist brauchen wir ihn nur noch in $\mathbb{F}_{11}$ zu schieben. Praktischerweise können wir $\frac{1}{10} = 10^{-1}$ darstellen +% +%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. +% +%Daher nehmen wir an, dass wir für die Inverse Transformationsmatrix ebenfalls ein solcher Vorfaktor benötigen. Dieser Faktor hat seinen Ursprung in der Gleichung +%\[ +%A \cdot A^{-1} = E. +%\] +%Sollte diese Gleichung nicht aufgehen, so muss die Inverse mit +\subsection{Allgemeine Decodierung + \label{reedsolomon:subsection:algdec}} + +Wir haben jetzt alles für eine erfolgreiche Rücktransformation vom empfangenen Nachrichtenvektor beisammen. Die allgemeine Gleichung für die Rücktransformation lautet +\[ +m = s \cdot A^{-1} \cdot v. +\] +Setzen wir nun die Werte ein in +% +%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 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$ 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/hilfstabellen.tex b/buch/papers/reedsolomon/hilfstabellen.tex index 4e39de5..b006f21 100644 --- a/buch/papers/reedsolomon/hilfstabellen.tex +++ b/buch/papers/reedsolomon/hilfstabellen.tex @@ -4,7 +4,7 @@ % % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil % -\section{$\mathbb{F}_{11}$ Hilfstabellen +\section{Hilfstabellen für $\mathbb{F}_{11}$ \label{reedsolomon:section:hilfstabellen}} \rhead{Hilfstabellen} diff --git a/buch/papers/reedsolomon/main.tex b/buch/papers/reedsolomon/main.tex index b4899cb..4e2fd60 100644 --- a/buch/papers/reedsolomon/main.tex +++ b/buch/papers/reedsolomon/main.tex @@ -1,7 +1,7 @@ % % main.tex -- Paper zum Thema <reedsolomon> % -% (c) 2020 Hochschule Rapperswil +% (c) 2021 Joshua Bär und Michael Steiner, Hochschule Rapperswil % \chapter{Reed-Solomon-Code\label{chapter:reedsolomon}} \lhead{Reed-Solomon-Code} @@ -39,9 +39,9 @@ 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/zusammenfassung} %\input{papers/reedsolomon/anwendungen} -> geplant +\input{papers/reedsolomon/hilfstabellen} \nocite{reedsolomon:weitz} \nocite{reedsolomon:informationkommunikation} diff --git a/buch/papers/reedsolomon/nachschlagewerk.tex b/buch/papers/reedsolomon/nachschlagewerk.tex deleted file mode 100644 index 60b857e..0000000 --- a/buch/papers/reedsolomon/nachschlagewerk.tex +++ /dev/null @@ -1,4 +0,0 @@ -\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/rekonstruktion.tex b/buch/papers/reedsolomon/rekonstruktion.tex index 40919d7..04e748c 100644 --- a/buch/papers/reedsolomon/rekonstruktion.tex +++ b/buch/papers/reedsolomon/rekonstruktion.tex @@ -7,7 +7,7 @@ \section{Nachricht Rekonstruieren \label{reedsolomon:section:rekonstruktion}} \rhead{Rekonstruktion der Nachricht} -Im letzten Kapitel haben wir eine Möglichkeit gefunden, wie wir die fehlerhaften Stellen lokalisieren können. +Im letzten Abschnitt 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 \[ @@ -21,7 +21,7 @@ Als Ausgangslage verwenden wir die Matrix, mit der wir den Nachrichtenvektor urs 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. +Wir stellen also die Matrix auf und markieren gleichzeitig die Fehlerstellen: \[ \textcolor{gray}{ \begin{pmatrix} @@ -47,8 +47,9 @@ Wir stellen also die Matrix auf und markieren gleichzeitig die Fehlerstellen. \begin{pmatrix} m_0 \\ m_1 \\ m_2 \\ m_3 \\ m_4 \\ m_5 \\ m_6 \\ m_7 \\ m_8 \\ m_9 \\ \end{pmatrix} +. \] -Die rot markierten Stellen im Übertragungsvektor enthalten Fehler und bringt uns daher kein weiterer Nutzen. +Die rot markierten Stellen im Übertragungsvektor enthalten Fehler und bringt uns daher keinen weiterer Nutzen. Aus diesem Grund werden diese Stellen aus dem Vektor entfernt, was wir hier ohne Probleme machen können, da dieser Code ja über Fehlerkorrekturstellen verfügt, deren Aufgabe es ist, eine bestimmte Anzahl an Fehler kompensieren zu können. Die dazugehörigen Zeilen in der Matrix werden ebenfalls entfernt, da die Matrix gleich viele Zeilen wie im Übertragungsvektor aufweisen muss, damit man ihn decodieren kann. @@ -183,3 +184,5 @@ m = [4,7,2,5,8,1] \] zurück, den wir ursprünglich versendet haben. +Wir möchten noch anmerken, dass es mehrere Wege für die Rekonstruktion des Nutzdatenteils gibt, diese aber alle auf dem Lokatorpolynom basieren. + diff --git a/buch/papers/reedsolomon/zusammenfassung.tex b/buch/papers/reedsolomon/zusammenfassung.tex new file mode 100644 index 0000000..568356f --- /dev/null +++ b/buch/papers/reedsolomon/zusammenfassung.tex @@ -0,0 +1,15 @@ +\section{Zusammenfassung + \label{reedsolomon:section:zf}} +\rhead{Zusammenfassung} +Dieser Abschnitt beinhaltet eine Übersicht über die Funktionsweise eines Reed-Solomon-Codes für beliebige endliche Körper. + +TODO: + +\subsubsection{Schritt 1: primitives Element} + +\subsubsection{Schritt 2: Codierung} + +\subsubsection{Schritt 3: Decodierung ohne Fehler} + +\subsubsection{Schritt 4: Decodierung mit Fehler} + |