diff options
Diffstat (limited to 'buch/papers/reedsolomon')
| -rw-r--r-- | buch/papers/reedsolomon/anwendungen.tex | 96 | ||||
| -rw-r--r-- | buch/papers/reedsolomon/codebsp.tex | 12 | ||||
| -rw-r--r-- | buch/papers/reedsolomon/decmitfehler.tex | 39 | ||||
| -rw-r--r-- | buch/papers/reedsolomon/decohnefehler.tex | 15 | ||||
| -rw-r--r-- | buch/papers/reedsolomon/dtf.tex | 33 | ||||
| -rw-r--r-- | buch/papers/reedsolomon/einleitung.tex | 10 | ||||
| -rw-r--r-- | buch/papers/reedsolomon/idee.tex | 68 | ||||
| -rw-r--r-- | buch/papers/reedsolomon/rekonstruktion.tex | 7 | ||||
| -rw-r--r-- | buch/papers/reedsolomon/zusammenfassung.tex | 8 |
9 files changed, 170 insertions, 118 deletions
diff --git a/buch/papers/reedsolomon/anwendungen.tex b/buch/papers/reedsolomon/anwendungen.tex index b9b1d69..9bb1d99 100644 --- a/buch/papers/reedsolomon/anwendungen.tex +++ b/buch/papers/reedsolomon/anwendungen.tex @@ -10,24 +10,31 @@ In den vorherigen Abschnitten haben wir betrachtet, wie Reed-Solomon-Codes in der Theorie funktionieren. In diesem Abschnitt werden wir einige Anwendungen vorstellen, bei denen ein Reed-Solomon-Code zum Einsatz kommt. -Dabei teilen all diese Anwendungen das gleiche Problem: Die Daten können nur durch einen (höchst Wahrscheinlichen) fehlerbehafteten Kanal empfangen werden. Es gibt keine andere Methode, an diese Daten zu kommen, als über diesen Kanal. +All diese Anwendungen teilen das gleiche Problem: Die Daten können nur durch einen höchstwahrscheinlich fehlerbehafteten Kanal empfangen werden. Es gibt keine andere Methode, an diese Daten zu kommen, als über diesen Kanal. In der Netzwerktechnik zum Beispiel ist es üblich, dass bei Paketverluste oder beschädigt empfangene Datenpaketen diese einfach noch einmal innert wenigen Millisekunden angefordert werden können. +\index{Paketverluste}% In der Raumfahrt ist dies nicht möglich, da aufgrund der beschränkten Speichermöglichkeit die gesammelten Daten so rasch wie möglich zur Erde gesendet werden. +\index{Raumfahrt}% Diese Daten wiederum brauchen aufgrund der grossen Distanz Stunden bis die Daten beim Empfänger ankommen. -Fehlerhafte Daten kann also auf Grund der Zeitverzögerung nicht mehr angefordert werden. +Fehlerhafte Daten können also auf Grund der Zeitverzögerung nicht mehr angefordert werden. Bei CDs oder DVDs gibt es zwar kein zeitliches Problem, jedoch erschweren Kratzer, Verschmutzungen oder Produktionsfehler das Lesen einer solchen Disk. -Da vor allem Produktionsfehler und Kratzer irreversibel sind und die Disk nicht nach jedem Kratzer ersetzt werden muss, so wird die korrekte Ausgabe der gespeicherten Information durch die Fehlerkorrektur sichergestellt. +\index{CD}% +\index{Compact-Disc}% +\index{DVD}% +\index{Digital Video Disk}% +Da vor allem Produktionsfehler und Kratzer irreversibel sind und die Disk nicht nach jedem Kratzer ersetzt werden, wird die korrekte Ausgabe der gespeicherten Information durch die Fehlerkorrektur sichergestellt. Einen ähnlichen Ansatz verfolgen QR-Codes, wobei die Information auch dann noch gelesen werden kann wenn der Code nicht mehr vollständig vorhanden ist. +\index{QR-Code}% %Wie man sieht, eignen sich Reed-Solomon-Codes vor allem für Anwendungen, bei der die Informationen nicht auf einen Anderen Weg beschafft werden kann. % % %, bei denen die Wahrscheinlichkeit hoch ist, dass während der Übertragung % -%Es ist deshalb umso wichtiger die Daten Codiert zu lesen um so gleich die Lesefehler zu korrigieren. +%Es ist deshalb umso wichtiger die Daten codiert zu lesen um so gleich die Lesefehler zu korrigieren. % % da aufgrund der grossen Distanz Stunden vergehen können bis gesendete Daten auf der Erde empfangen werden kann. % @@ -68,15 +75,36 @@ Um die Fähigkeit eines verwendeten Reed-Solomon-Codes zu beschreiben verwendet % %In den letzten abschnitten haben wir uns ausführlich die Funktionsweise des Reed-Solomon-Codes angeschaut. In diesem Abschnitt möchten wir dem Leser ein paar bekannte beispiele vorstellen, in denen Reed-Solomon-Codes zum einsatz kommen. Es sei jedoch angemerkt, dass diese Anwendungen in der Umsetzung oft ein wenig anderst funktionieren als hier vorgestellt. Dies wurde vor allem wegen technischen optimierungen realisiert. (technische tricks und finessen), von der logik jedoch sehr stark an unserem Beispiel orientieren +\begin{figure} + \centering + \includegraphics[width=0.5\textwidth]{papers/reedsolomon/images/Voyager_Sonde} + \caption{Mit einer Entfernung von über 22.8 Milliarden Kilometer ist die Voyager 1 Raumsonde das am weitesten entfernte, von Menschen erschaffene Objekt. Obwohl ihre Schwestersonde Voyager 2 zuerst ins All gestartet wurde befindet Sie sich ``nur'' 19 Milliarden Kilometer weit weg von der Erde. Aufgrund abnehmender Batterieleistung werden die beiden Sonden ihre wissenschaftlichen Aktivitäten etwa 2025 einstellen, bleiben aber bis in die 2030er mit uns in Kontakt.} +\index{Voyager 1 und 2}% + \label{fig:voyager} +\end{figure} + \subsection{Raumfahrt} Obwohl Reed-Solomon-Codes bereits in den 1960er entwickelt wurden fanden sie erstmals Anwendung in der Voyager Raumsonde der NASA. Die Daten der zwei im Jahre 1977 gestarteten Sonden (siehe Abbildung \ref{fig:voyager}) werden mit einem ($255$,$233$)-Code -Codiert. +\index{Voyager Raumsonde}% +\index{NASA}% +codiert. Der Nachrichtenblock hat somit eine Länge von $255$ Zahlen, wovon $233$ als Nutzlast zur Verfügung stehen. Damit ist es möglich bis zu $11$ Fehler im Nachrichtenblock zu korrigieren. -Der Codierte Nachrichtenblock wird in kleinere Blöcke aufgeteilt, mit einem Faltungscode erneut Codiert und anschliessend gesendet. +Der codierte Nachrichtenblock wird in kleinere Blöcke aufgeteilt, mit einem Faltungscode erneut codiert und anschliessend gesendet. Ein Faltungscode ist wie ein Reed-Solomon-Code in der Lage Fehler zu korrigieren, -Codiert seine Information aber auf eine andere weise. Aus jedem unterteilten Block wird vor dem Versenden ein Paritätsbit erzeugt und dem Block angehängt. Anhand diesem Paritätsbit überprüft der Empfänger, ob bei der Übertragung der Block beschädigt wurde. Ist dies der Fall, wird der Block bei der Decodierung nicht beachtet. Diese so entstandenen ``Lücken'' im Datenstrom werden wiederum vom Reed-Solomon-Code korrigiert. Dieses Zusammenspiel beider Codes garantiert so eine hohe Robustheit gegenüber Übertragungsfeher. +codiert seine Information aber auf eine andere Weise. Aus jedem unterteilten Block wird vor dem Versenden ein Paritätsbit erzeugt und dem Block angehängt. Anhand dieses Paritätsbits überprüft der Empfänger, ob bei der Übertragung der Block beschädigt wurde. Ist dies der Fall, wird der Block bei der Decodierung nicht beachtet. Diese so entstandenen ``Lücken'' im Datenstrom werden wiederum vom Reed-Solomon-Code korrigiert. Dieses Zusammenspiel beider Codes garantiert so eine hohe Robustheit gegenüber Übertragungsfehler. +\begin{figure} + \centering + \subfigure[]{ + \includegraphics[width=0.45\textwidth]{papers/reedsolomon/images/Compact_Disc} + } + \subfigure[]{ + \includegraphics[width=0.45\textwidth]{papers/reedsolomon/images/Compact_Disc_zoomed_in} + } + \caption{CDs kamen 1982 auf den Markt. Sie funktioniert durch das Einpressen oder Einbrennen von Punkten und Strichen, die die Daten repräsentieren. Gelesen werden diese wiederum durch die Reflektion eines Lasers an diesen Punkten und Strichen.} + \label{fig:cd} +\end{figure} % % Funktioniert aber nach einem ganz anderen Prinzip. % @@ -92,16 +120,12 @@ Codiert seine Information aber auf eine andere weise. Aus jedem unterteilten Blo % %mit der Erde mit einem RS(255,233)-Code für die digitalen Bilder sowie einem konventionellen Faltungscode. -\begin{figure} - \centering - \includegraphics[width=0.5\textwidth]{papers/reedsolomon/images/Voyager_Sonde} - \caption{Mit einer Entfernung von über 22.8 Milliarden Kilometer ist die Voyager 1 Raumsonde das am weitesten entfernte, von Menschen erschaffene Objekt. Obwohl ihre Schwestersonde Voyager 2 zuerst ins All gestartet wurde befindet Sie sich ``nur'' 19 Milliarden Kilometer weit weg von der Erde. Aufgrund abnehmender Batterieleistung werden die beiden Sonden ihre wissenschaftlichen Aktivitäten etwa 2025 einstellen, bleiben aber bis in die 2030er mit uns in Kontakt.} - \label{fig:voyager} -\end{figure} \subsection{CD/DVD} Compact discs verwenden sogar zwei ineinander verschachtelte Reed-Solomon-Codes, einen (32,28)-Code und einen (28,24)-Code. -Beide Codes sind in der Lage, Fehler aus dem jeweils anderen gelesenen Block zu korrigieren. Dieses spezielle Zusammenspielen dieser beiden Codes werden auch Cross-interleaved Reed-Solomon-Codes (CIRC) genannt. +Beide Codes sind in der Lage, Fehler aus dem jeweils anderen gelesenen Block zu korrigieren. Dieses spezielle Zusammenspielen dieser beiden Codes wird auch Cross-interleaved Reed-Solomon-Code (CIRC) genannt. +\index{CIRC}% +\index{Cross-interleaved Reed-Solomon code}% Diese Vorgehensweise erzielt eine hohe Robustheit gegenüber Produktionsfehlern oder Verschmutzung auf der Disc. Bei CDs sind diese in der Lage, bis zu 4000 fehlerhafte Bits am Stück (ca. $2.5mm$) zu erkennen und zu korrigieren. Die Digital Video Disc funktioniert nach dem selben Konzept mit grösseren Codeblöcken. Die DVD verwendet einen (208,192)-Code und einen (182,172)-Code. @@ -112,28 +136,6 @@ Die Digital Video Disc funktioniert nach dem selben Konzept mit grösseren Codeb \begin{figure} \centering \subfigure[]{ - \includegraphics[width=0.45\textwidth]{papers/reedsolomon/images/Compact_Disc} - } - \subfigure[]{ - \includegraphics[width=0.45\textwidth]{papers/reedsolomon/images/Compact_Disc_zoomed_in} - } - \caption{CDs kamen 1982 auf den Markt. Sie funktioniert durch das Einpressen oder Einbrennen von Punkten und Strichen, die die Daten repräsentieren. Gelesen werden diese wiederum durch die Reflektion eines Lasers an diesen Punkten und Strichen.} - \label{fig:cd} -\end{figure} - -\subsection{QR-Codes} -Quick Response Codes oder auch QR-Codes funktionieren nach einem sehr ähnlichen Prinzip wie in unserem Beispiel der Abschnitte \ref{reedsolomon:section:codebsp} - \ref{reedsolomon:section:rekonstruktion} nur das QR-Codes in einem $\mathbb{F}_{256}$ Körper arbeiten. Die physische Grösse eines Codes ist stark abhängig von der Menge an codierten Daten sowie dem verwendeten Fehlerkorrektur-Level. Es ist so auf dem ersten Blick nicht ersichtlich, wie viel Nutzinformationen ein Qr-Code enthält. Die QR-Codes in Abbildung \ref{fig:qr} zeigen jeweils die Gleiche Information mit unterschiedlichem Fehlerkorrektur-Level. Codes mit einem höheren Korrektur-Level können auch für Designer-Codes Zweckentfremdet werden. Dabei wird z.B. das Firmenlogo oder einen Schriftzug über den Qr-Code gelegt, ohne das die Funktion des Codes beeinträchtigt wird. Ein Beispiel dazu ist unter Abbildung \ref{fig:designqr} zu finden. - -% - -%So kann auf den ersten Blick nicht -% -% -% funktionieren nach einem sehr ähnlichen Prinzip wie in unserem Beispiel, nur dass QR-Codes in einem $\mathbb{F}_{256}$ Körper arbeiten. Je nach grösse der Codierung ist der QR-Code im Endeffekt robuster gegen Beschädigungen. Bei Low Level Codes können 7\% der Daten Wiederhergestellt werden, beim High Level Code sind das sogar 30\%. - -\begin{figure} - \centering - \subfigure[]{ \includegraphics[width=0.4\textwidth]{papers/reedsolomon/images/qrcode_h} } \subfigure[]{ @@ -145,7 +147,7 @@ Quick Response Codes oder auch QR-Codes funktionieren nach einem sehr ähnlichen % \subfigure[]{ % \includegraphics[width=0.4\textwidth]{papers/reedsolomon/images/designer_qrcode} % } - \caption{Anhand der grösse würde man darauf schliessen, dass bei (a) mehr Informationen Codiert sind als bei (b). Tatsächlich aber beinhalten beide Codes die gleiche Information. Das liegt daran, da die Fehlerkorrekturfähigkeit von QR-Codes sich in insgesamt vier Levels aufteilen lassen. Der höchste Fehlerkorrektur-Level, der bei (a) angewendet wurde, ist in der Lage, bis zu 30\% der Daten wiederherzustellen. Der kleinste Level schafft etwa 7\%, der in (b) veranschaulicht wird. Da die Grösse also nichts über die Menge an Daten aussagt, könnte es sich bei (a) auch um einen Code mit viel Nutzdaten und kleinem Fehlerkorrektur-Level handeln. Der Unterschied ist von Auge nicht sichtbar.} + \caption{Anhand der grösse würde man darauf schliessen, dass bei (a) mehr Informationen codiert sind als bei (b). Tatsächlich aber beinhalten beide Codes die gleiche Information. Das liegt daran, da die Fehlerkorrekturfähigkeit von QR-Codes sich in insgesamt vier Levels aufteilen lassen. Der höchste Fehlerkorrektur-Level, der bei (a) angewendet wurde, ist in der Lage, bis zu 30\% der Daten wiederherzustellen. Der kleinste Level schafft etwa 7\%, der in (b) veranschaulicht wird. Da die Grösse also nichts über die Menge an Daten aussagt, könnte es sich bei (a) auch um einen Code mit viel Nutzdaten und kleinem Fehlerkorrektur-Level handeln. Der Unterschied ist von Auge nicht sichtbar.} \label{fig:qr} \end{figure} @@ -165,4 +167,22 @@ Quick Response Codes oder auch QR-Codes funktionieren nach einem sehr ähnlichen } \caption{Während (a) noch einen unveränderten QR-Code repräsentiert, handelt es sich bei (b) nun um einen Designer-QR-Code. Beide Codes verfügen über einen mittleren Fehlerkorrektur-Level von theoretisch 15\%. Da bei (b) jetzt einen Teil des Codes durch ein Logo verdeckt wird, schränkt sich die Fehlerkorrekturfähigkeit je nach Grösse des verdeckten Teils mehr oder weniger stark ein. Unser Designer-Code in (b) ist nur noch in der Lage etwa 9\% des Codes zu rekonstruieren.} \label{fig:designqr} -\end{figure}
\ No newline at end of file +\end{figure} + +\subsection{QR-Codes} +\index{QR-Code}% +Quick Response Codes oder auch QR-Codes funktionieren nach einem sehr ähnlichen Prinzip wie in unserem Beispiel der Abschnitte \ref{reedsolomon:section:codebsp} - \ref{reedsolomon:section:rekonstruktion} nur das QR-Codes in einem $\mathbb{F}_{256}$ Körper arbeiten. +Die physische Grösse eines Codes ist stark abhängig von der Menge an codierten Daten sowie dem verwendeten Fehlerkorrektur-Level. +Es ist so auf dem ersten Blick nicht ersichtlich, wie viel Nutzinformationen ein QR-Code enthält. +Die QR-Codes in Abbildung \ref{fig:qr} zeigen jeweils die gleiche Information mit unterschiedlichem Fehlerkorrektur-Level. +Codes mit einem höheren Korrektur-Level können auch für Designer-Codes zweckentfremdet werden. +\index{Designed-QR-Code}% +Dabei wird z.~B.~das Firmenlogo oder einen Schriftzug über den QR-Code gelegt, ohne das die Funktion des Codes beeinträchtigt wird. Ein Beispiel dazu ist in Abbildung \ref{fig:designqr} zu finden. + +% + +%So kann auf den ersten Blick nicht +% +% +% funktionieren nach einem sehr ähnlichen Prinzip wie in unserem Beispiel, nur dass QR-Codes in einem $\mathbb{F}_{256}$ Körper arbeiten. Je nach grösse der Codierung ist der QR-Code im Endeffekt robuster gegen Beschädigungen. Bei Low Level Codes können 7\% der Daten Wiederhergestellt werden, beim High Level Code sind das sogar 30\%. + diff --git a/buch/papers/reedsolomon/codebsp.tex b/buch/papers/reedsolomon/codebsp.tex index eb4e82f..02484e0 100644 --- a/buch/papers/reedsolomon/codebsp.tex +++ b/buch/papers/reedsolomon/codebsp.tex @@ -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, 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. @@ -51,7 +51,7 @@ 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 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 für das Beispiel die Nachricht \[ @@ -76,7 +76,7 @@ dar. \subsection{Der Ansatz der diskreten Fouriertransformation \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 Eulerische Zahl $e$ in endlichen Körpern nicht existiert. +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. Dazu ändern wir die Darstellung von \[ @@ -115,7 +115,8 @@ in die von $a$ abhängige Schreibweise \subsubsection{Die primitiven Einheitswurzeln \label{reedsolomon:subsection:primsqrt}} - +\index{primitive Einheitswurzel}% +\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} @@ -151,6 +152,7 @@ Wenden wir diese Vorgehensweise auch für andere endliche Körper an, so werden \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 @@ -167,6 +169,7 @@ Für die Codierung setzen wir alle Zahlen in $\mathbb{F}_{11}\setminus\{0\}$ nac \end{tabular} \end{center} als unser Übertragungsvektor. +\index{Ubertragungsvektor@Übertragungsvektor}% \subsection{Allgemeine Codierung \label{reedsolomon:subsection:algCod}} @@ -197,3 +200,4 @@ 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. +\index{Nachrichtenkanal}% diff --git a/buch/papers/reedsolomon/decmitfehler.tex b/buch/papers/reedsolomon/decmitfehler.tex index 598cf68..97694ae 100644 --- a/buch/papers/reedsolomon/decmitfehler.tex +++ b/buch/papers/reedsolomon/decmitfehler.tex @@ -11,7 +11,7 @@ In der realen Welt müssen wir uns jedoch damit abfinden, dass kein Übertragung 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 +Der Übertragungskanal im Beispiel weist jetzt den Fehlervektor \[ u = [0, 0, 0, 3, 0, 0, 0, 0, 2, 0] \] @@ -76,16 +76,18 @@ als neuen, fehlerbehafteten Übertragungsvektor $w$ auf der Empfängerseite. 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,}_{\displaystyle\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. +Der Nachrichtenblock weisst jetzt ein {\em Syndrom} auf, welches anzeigt, dass der Übertragungsvektor fehlerhaft empfangen wurde. +\index{Syndrom}% % 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. +\index{Lokatorpolynom}% \subsection{Das Fehlerstellenpolynom $d(X)$ \label{reedsolomon:subsection:fehlerpolynom}} @@ -101,9 +103,11 @@ In einem ersten Versuch berechnen wir die Differenz $d$ des empfangenen und dem $d(X)$ & $=$ & $r(X) - m(X)$ \end{tabular} \end{center} -und nennen $d(X)$ als unseres Fehlerstellenpolynom. Dieses Polynom soll uns sagen, welche Stellen korrekt und welche fehlerhaft sind. +und nennen $d(X)$ unser {\em Fehlerstellenpolynom}. +\index{Fehlerstellenpolynom}% +Dieses Polynom soll uns sagen, welche Stellen korrekt und welche fehlerhaft sind. -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. +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. @@ -127,18 +131,19 @@ Setzen wir jetzt unsere Einheitswurzel aus dem Beispiel ein so erhalten wir \end{tabular} \end{center} und damit die Information, dass allen Stellen, die nicht Null sind, Fehler enthalten. -Aus der Tabelle lesen wir ab, das in unserem Beispiel die Fehler an der Stelle drei und acht zu finden sind. +Aus der Tabelle lesen wir ab, das in unserem Beispiel die Fehler an der Stelle $3$ und $8$ 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{Mit dem grössten gemeinsamen Teiler auf Nullstellenjagd \label{reedsolomon:subsection:ggT}} - +\index{ggT}% +\index{grösster gemeinsamer Teiler}% 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 \] -gilt für jedes $X$. Setzen wir das $q$ von unserem Beispiel ein +gilt für jedes $X$. Setzen wir das $q$ von unserem Beispiel ein, erhalten wir \[ f(X) = X^{10}-1 = 0 \qquad \text{für } X \in \{1,2,3,4,5,6,7,8,9,10\} \] @@ -165,7 +170,8 @@ Dies scheint zuerst nicht sehr hilfreich zu sein, da wir für das Lokatorpolynom \subsection{Mit dem kgV fehlerhafte Nullstellen finden \label{reedsolomon:subsection:kgV}} - +\index{kgV}% +\index{kleinstes gemeinsames Vielfaches}% 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),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). @@ -181,7 +187,7 @@ Somit ist 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. +Es scheint so als müssten wir nur noch an den besagten Stellen den Übertragungsvektor korrigieren und wir wären 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, auf der Empfängerseite aber nicht kennen. \subsection{Der problematische Nachrichtenvektor $m(X)$ @@ -214,7 +220,7 @@ so zu berechnen, dass wir die wichtigen vier Stellen kennen, der Rest des Polyno \subsection{Die Berechnung der Fehlerstellen \label{reedsolomon:subsection:nachrichtenvektor}} - +\index{Fehlerstellen}% 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} @@ -309,11 +315,12 @@ l(X) = (X-a^i)(X-a^j). \] 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^j = 6 \qquad \Rightarrow \qquad j = 8$. -\end{center} +\begin{equation*} +\begin{aligned} + a^i &= 5 &&\Rightarrow & i &= 3\\ + a^j &= 6 &&\Rightarrow & j &= 8. +\end{aligned} +\end{equation*} Schlussendlich erhalten wir \[ d(X) = (X-a^3)(X-a^8) diff --git a/buch/papers/reedsolomon/decohnefehler.tex b/buch/papers/reedsolomon/decohnefehler.tex index 50bd8d6..2c755f9 100644 --- a/buch/papers/reedsolomon/decohnefehler.tex +++ b/buch/papers/reedsolomon/decohnefehler.tex @@ -33,7 +33,8 @@ 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. \] -Im wesentlichen ändert sich bei der inversen diskreten Fouriertransformation $e^{j/2\pi}$ zu $e^{-j/2\pi}$. Zusätzlich benötigt die inverse noch einen Korrekturfaktor $1/n$. Wir erwarten daher, dass wir auch im endlichen Körper $A$ die Zahl $a$ durch $a^{-1}$ ersetzen können. Mit der primitiven Einheitswurzel ergibt das +Im wesentlichen ändert sich bei der inversen diskreten Fouriertransformation $e^{j/2\pi}$ zu $e^{-j/2\pi}$. Zusätzlich benötigt die Inverse noch einen Korrekturfaktor $1/n$. Wir erwarten daher, dass wir auch im endlichen Körper $A$ die Zahl $a$ durch $a^{-1}$ ersetzen können. Mit der primitiven Einheitswurzel ergibt das +\index{Korrekturfaktor}% %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 +46,7 @@ Mit einem solchen Problem haben wir uns bereits in Abschnitt \ref{buch:section:e \subsection{Inverse der primitiven Einheitswurzel \label{reedsolomon:subsection:invEinh}} - +\index{Inverse}% 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 @@ -169,7 +170,8 @@ als unseren Vorfaktor setzen müssen um, die Gleichung \ref{reedsolomon:equation \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 +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. \] @@ -201,10 +203,11 @@ m = 10 \cdot A^{-1} \cdot v \qquad \Rightarrow \qquad m = 10 \cdot \begin{pmatri \cdot \begin{pmatrix} 5 \\ 3 \\ 6 \\ 5 \\ 2 \\ 10 \\ 2 \\ 7 \\ 10 \\ 4 \\ -\end{pmatrix} +\end{pmatrix}, \] -und wir erhalten +erhalten wir \[ m = [0,0,0,0,4,7,2,5,8,1] \] -als unsere Nachricht zurück.
\ No newline at end of file +als unsere Nachricht zurück. + diff --git a/buch/papers/reedsolomon/dtf.tex b/buch/papers/reedsolomon/dtf.tex index 9647775..a50a134 100644 --- a/buch/papers/reedsolomon/dtf.tex +++ b/buch/papers/reedsolomon/dtf.tex @@ -1,26 +1,30 @@ % % dtf.tex -- Idee mit DFT % -\section{Übertragung mit Hilfe der diskrten Fourier-Transformation +\section{Übertragung mit Hilfe der diskreten Fourier-Transformation \label{reedsolomon:section:dtf}} -\rhead{Umwandlung mit DTF} +\rhead{Fehlerkorrektur mit diskreter Fourier-Transformation} Die Grundidee eines fehlerkorrigierenden Code ist, dass Informationen eines Datenpunktes durch die Codierung auf viele übertragene Werte verteilt werden. Die Decodierung ist in der Lage, den ursprünglichen Datenwert zu rekonstruieren, sogar wenn einzelne wenige übertragene Werte beschädigt worden sind. \par Die Fourier-Transformation transformiert einen einzelnen Wert, +\index{Fourier-Transformation}% eine Dirac-Funktion, auf ein Spektrum, welches sich über die ganze Frequenzachse erstreckt. +\index{Dirac-Funktion}% +\index{Spektrum}% Aus der Filtertheorie ist bekannt, dass der ursprüngliche Impuls mehr oder weniger rekonstruierbar ist, vorausgesetzt, es gehen nicht zu viele Frequenzen bei der Übertragung verloren. -\par +\index{Filtertheorie}% Es liegt daher nahe zu versuchen, die Fourier-Transformation für Codierung und Decodierung zu verwenden. -\subsection{Beispiel mit Fehlerkorrektur mit Fourier-Transformation +\subsection{Beispiel: Fehlerkorrektur mit Fourier-Transformation \label{reedsolomon:subsection:sendbsp}} Das folgende Beispiel soll zeigen, wie die Idee der Fehlerkorrektur umgesetzt wurde. Die Fehlererkennung des Reed-Solomon-Codes funktioniert nach einem sehr Ähnlichen Prinzip. +\index{Reed-Solomon-Code}% %Das folgende Beispiel soll zeigen, wie Fehlerkorrektur möglich ist. %Dieses auf eine Art, die der Funktionsweise des Reed-Solomon-Codes, @@ -45,8 +49,10 @@ In der folgenden Aufzählung werden diese einzelne Schritte erklärt und erläut \begin{enumerate}[(1)] \item Das Signal besteht aus 64 zufälligen, ganzzahligen Datenwerten zwischen 0 und 10. Für die Rekonstruktion werden zusätzliche Datenwerte benötigt, wir fügen deshalb 32 Werte hinzu. - Diese setzen wir willkürlich alle auf Null und nennen sie Fehlerkorrekturstellen. + Diese setzen wir willkürlich alle auf Null und nennen sie {\em Fehlerkorrekturstellen}. +\index{Fehlerkorrekturstellen}% Wir erhalten so einen erweiterten Signalvektor der Länge $N =96$. +\index{Signalvektor}% \item Mit der Fourier-Transformation wird der ganze Signalvektor codiert. Dadurch wird jede Informationseinheit auf alle Punkte des Spektrums verteilt. \item Wir dürfen annehmen, dass bei der Übertragung, nur einzelne übertragene @@ -58,11 +64,12 @@ In der folgenden Aufzählung werden diese einzelne Schritte erklärt und erläut Der Empfänger erkennt daher im allgemeinen nicht, ob und wo Übertragungsfehler aufgetreten sind. \item Ohne Übertragungsfehler kann der Signalvektor durch die inverse Fourier-Transformation vollständig wiederhergestellt werden. - Dazu gehören auch die Nullen an den Fehlerkorrekturstellen 64 - 96. + Dazu gehören auch die Nullen an den Fehlerkorrekturstellen 64--96. \par Sind Übertragungsfehler aufgetreten, werden an diesen Stellen die Werte von Null abweichen. Somit haben wir bereits Fehler erkannt. - \item Die Werte an den Fehlerkorrekturstellen 64 - 96, die nicht mehr Null sind, nennen wir das Syndrom. + \item Die Werte an den Fehlerkorrekturstellen 64--96, die nicht mehr Null sind, nennen wir das {\em Syndrom}. +\index{Syndrom}% Im Syndrom steckt nur Information über die Fehler, sie werden durch die inverse Fourier-Transformation erzeugt. \item Um die Fehler zu rekonstruieren, kann man versuchen, die Information im Syndrom mit Fourier-Transformation zu transformieren. Da das Syndrom nur ein Teil der Fehlerinformation ist, liefert die Fourier-Transformation eine Approximation der Fehler. @@ -70,7 +77,6 @@ In der folgenden Aufzählung werden diese einzelne Schritte erklärt und erläut \end{enumerate} Im Beispiel haben wir mit dem Syndrom nur etwa ein Drittel der Fehlerinformation, es ist daher zu erwarten, dass die Fehlerwerte auch nur ein Drittel so gross sind. -\par Damit können die Fehler korrigiert und die Originaldaten wiederhergestellt werden. Der Rekonstruktionsauftrag ist damit erfolgreich ausgeführt. @@ -116,9 +122,12 @@ Die Analogie geht aber noch weiter. \end{equation} für verschiedene \( w = e^{-\frac{2\pi j}{N} k}, k=1, \dots ,N-1\) übermittelt. Das Syndrom entstand durch die Wahl ${f_{64}}=0$ bis ${f}_{N-1}=0$ (graue Koeffizenten). -\par + Die Polynominterpolation und die Fourier-Transformation rechnen beide mit reellen Zahlen. -Wenn die Approximation nicht mehr genügend gut ist um die Fehler zu erkennen und rekonstruieren, +Wenn die Approximation nicht mehr genügend gut ist, um die Fehler zu erkennen und zu rekonstruieren, dann brauchen wir andere Varianten. -Um dieser Approximation zu entkommen, verlassen wir die reellen Zahlen und gehen zum endlichen Körpern, oder auch Galois-Körper genannt. -Dieser bietet uns einige Vorteile.
\ No newline at end of file +Um dieser Approximation zu entkommen, verlassen wir die reellen Zahlen und gehen zu endlichen Körpern, auch Galois-Körper genannt. +\index{endlicher Körper}% +\index{Galois-Körper}% +\index{Körper, endlich}% +Diese bieten uns einige Vorteile. diff --git a/buch/papers/reedsolomon/einleitung.tex b/buch/papers/reedsolomon/einleitung.tex index f99ad82..cf46c27 100644 --- a/buch/papers/reedsolomon/einleitung.tex +++ b/buch/papers/reedsolomon/einleitung.tex @@ -6,11 +6,13 @@ \section{Einleitung \label{reedsolomon:section:einleitung}} \rhead{Einleitung} -Der Reed-Solomon-Code wurde von den beiden Mathematiker Irving S. Reed und Gustave Solomon im Jahre 1960 entwickelt. -Dabei haben sie das Problem der Fehlerhaften Datenübertragung gelöst. -In diesem Abschnitt wird möglichst verständlich die mathematische Abfolge und +Der Reed-Solomon-Code wurde von den beiden Mathematikern Irving S. Reed und Gustave Solomon im Jahre 1960 entwickelt. +\index{Reed, Irving S.}% +\index{Solomon, Gustave}% +Dabei haben sie das Problem der fehlerhaften Datenübertragung gelöst. +In diesem Kapitel wird möglichst verständlich die mathematische Abfolge und Funktionsweise des Reed-Solomon-Code erklärt. -Es wird jedoch nicht auf die technische Umsetzung oder Implementierung eingegangen, jedoch wird im Abschnitt \ref{reedsolomon:section:anwendung} einige Anwendungen des Reed-Solomon-Codes vorgestellt. +Es wird jedoch nicht auf die technische Umsetzung oder Implementierung eingegangen, jedoch werden im Abschnitt \ref{reedsolomon:section:anwendung} einige Anwendungen des Reed-Solomon-Codes vorgestellt. diff --git a/buch/papers/reedsolomon/idee.tex b/buch/papers/reedsolomon/idee.tex index daa2913..b1ab8f6 100644 --- a/buch/papers/reedsolomon/idee.tex +++ b/buch/papers/reedsolomon/idee.tex @@ -5,13 +5,13 @@ \label{reedsolomon:section:idee}} \rhead{Problemstellung} Um Fehler in einer Datenübertragung zu erkennen, könnte man die Daten jeweils doppelt senden, -also den gleiche Wert immer zweimal versenden. -Tritt ein Fehler ein wird sich dies in der Differenz der beiden Werten bemerkbar machen. +also den gleiche Wert immer zweimal. +Tritt ein Fehler ein wird sich dies in der Differenz der beiden Werte bemerkbar machen. Aber wie erkennen wir, welcher nun der richtige ist? Die Lösung ist simpel: Wir übertragen den Wert einfach dreimal. -Wenn jetzt ein Fehler auftritt, kann durch die beiden unveränderten Werten den richtigen bestimmt werden. +Wenn jetzt ein Fehler auftritt, kann durch die beiden unveränderten Werte der richtige bestimmt werden. Doch was machen wir, wenn bei dieser Übertragung zwei Fehler auftreten? -Oder noch schlimmer: Was wenn zweimal derselbe Fehler auftritt? Die beiden Fehlerhaften Werte überstimmen bei der Evaluierung den gesendeten Datenwert, der dann unwiderruflich verloren geht. -Wir könnten dies noch steigern mit vier, fünf oder mehr gleichen Übertragenen Werte. Dies erhöht zwar die Robustheit der gesendeten Daten, führt aber auch dazu, dass wir durch die Mehrfachübertragung nur sehr wenige Nutzdaten versenden können. +Oder noch schlimmer: Was wenn zweimal derselbe Fehler auftritt? Die beiden fehlerhaften Werte überstimmen bei der Evaluierung den gesendeten Datenwert, der dann unwiderruflich verloren geht. +Wir könnten dies noch steigern mit vier, fünf oder mehr gleichen übertragenen Werte. Dies erhöht zwar die Robustheit der gesendeten Daten, führt aber auch dazu, dass wir durch die Mehrfachübertragung nur sehr wenige Nutzdaten versenden können. Gerade in unserer heutigen Zeit wäre dies ein enorm grosses Problem und aus diesem Grund wurden alternative Ansätze ausgearbeitet um dieses grundlegende Problem zu lösen. % % @@ -69,58 +69,60 @@ p(x) \textcolor{blue}{2}x^2 + \textcolor{blue}{1}x + \textcolor{blue}{5}. \label{reedsolomon:equation1} \end{equation} -\par + Ein Polynom zweiten Grades ist durch drei Punkte eindeutig bestimmbar. -Bei einer fehlerlosen Übertragung können wir mit 3 übertragenen Werten +Bei einer fehlerlosen Übertragung können wir mit drei übertragenen Werten das Polynom durch Polynominterpolation volständig rekonstruieren. Wir brauchen Polynominterpolation als Methode, um aus den Punkten wieder ein Polynom zu bilden. Die Koeffizente des rekonstruierten Polynoms sind dann unsere gesendeten Zahlen \textcolor{blue}{2}, \textcolor{blue}{1} und \textcolor{blue}{5}. -\par + Wie können wir nun Fehler erkennen oder sogar korrigieren? -Versuchen wir doch, mehr Werte zu übertragen, wie zum Beispiel 7 Werte. +Versuchen wir doch, mehr Werte zu übertragen, wie zum Beispiel sieben Werte. Übertragen werden nun die \textcolor{darkgreen}{grünen Werte} des \textcolor{blue}{blauen Polynomes} an den Stellen 1, 2, 3, \dots , 7. In Abbildung \ref{fig:polynom} ist das zu den \textcolor{blue}{Datenpunkten} gehörige Polynom blau dargestellt, die \textcolor{darkgreen}{übertragenen Werte} des Polynoms sind grün, wobei diese Punkte aufgrund von Übertragungsfehler jetzt eine Parabel darstellen. -Die Fehlerhaften Punkte lassen sich sehr einfach bestimmen, weil diese nicht auf der ursprünglichen Funktion liegen. +Die fehlerhaften Punkte lassen sich sehr einfach bestimmen, weil diese nicht auf der ursprünglichen Funktion liegen. Somit können die roten Punkte auf der Parabel durch die grauen ersetzt werden und sind damit korrigiert. -Bisher konnten wir von 7 Zahlen zwei Fehler erkennen und korrigieren. Können wir in diesem Beispiel noch mehr Fehler korrigieren? +Bisher konnten wir von sieben Zahlen zwei Fehler erkennen und korrigieren. Können wir in diesem Beispiel noch mehr Fehler korrigieren? Wir erhöhen dazu die Fehleranzahl Schritt für Schritt: +\begin{figure}%[!ht] + \centering + %\includegraphics[width=\textwidth]{papers/reedsolomon/figures/polynom2} + \input{papers/reedsolomon/tikz/polynomraw.tex} + \caption{Polynom $p(x)$ von der Gleichung\eqref{reedsolomon:equation1}} + \label{fig:polynom} +\end{figure}% \begin{itemize} \item[\textit{1 Fehler}:] Bei einem Fehler können konkurrenzierende, aber falsche Polynome zusammen mit zwei originalen Punkten entstehen. - Dabei können aber maximal 3 Punkte auf diesem Konkurrenzpolynom sein. + Dabei können aber maximal drei Punkte auf diesem Konkurrenzpolynom sein. Da 6 > 3 ist haben wir unser originales Polynom gefunden. \item[\textit{2 Fehler}:] Bei Zwei Fehlern kann ein Fehler mit zwei originalen Punkten ein konkurrenzierendes, aber falsches Polynom bilden. Da der zweite \textcolor{red}{Fehler} frei wählbar ist, kann dieser auch auf dem \textcolor{gray}{Konkurrenzpolynom} liegen, wie in der Abbilbung \ref{fig:polynom} zu sehen ist. - Nun haben wir, ein \textcolor{blue}{originales Polynom} mit \textcolor{darkgreen}{5} übereinstimmenden und ein konkurrenzierendes mit 4 Punkten. - Da 5 noch grösser als 4 ist, können wir sagen, welches das Originalpolynom ist. - \item[\textit{3 Fehler}:] Bei Drei kann genau wie bei 1 oder 2 Fehler, ein konkurenzierendes Polynom mit einem Fehler und zwei originalen Punkten bestimmt werden. + Nun haben wir, ein \textcolor{blue}{originales Polynom} mit \textcolor{darkgreen}{fünf} übereinstimmenden und ein konkurrenzierendes mit vier Punkten. + Da fünf noch grösser als vier ist, können wir sagen, welches das Originalpolynom ist. + \item[\textit{3 Fehler}:] Bei drei kann genau wie bei ein oder zwei Fehler, ein konkurenzierendes Polynom mit einem Fehler und zwei originalen Punkten bestimmt werden. Auch hier sind die anderen Fehler frei wählbar und liegen auf dem Konkurrenzpolynom. - Nun ist es so das 5 Punkte auf diesem konkurenzierenden Polynom und 4 Punkte auf dem originalen. + Nun ist es so das fünf Punkte auf diesem konkurenzierenden Polynom und vier Punkte auf dem originalen liegen. Das Originalpolynom kann nicht mehr gefunden werden. - \item[\textit{4 Fehler}:] Bei Vier kann noch erkannt werden, dass Fehler aufgetreten sind, da 3 originale Punkte das ursprüngliche Polynom ergeben. - Somit haben wir mindestens 2 verschieden Polynome, was bedeutet, dass Fehler entstanden sind. - \item[\textit{5 Fehler:}] Bei Fünf kann mit den 2 originalen Punkte das Originale Polynom nicht mehr erkannt werden und + \item[\textit{4 Fehler}:] Bei vier kann noch erkannt werden, dass Fehler aufgetreten sind, da drei originale Punkte das ursprüngliche Polynom ergeben. + Somit haben wir mindestens zwei verschiedene Polynome, was bedeutet, dass Fehler entstanden sind. + \item[\textit{5 Fehler:}] Bei fünf kann mit den zwei originalen Punkten das originale Polynom nicht mehr erkannt werden und somit kann auch keine Aussage mehr gemacht werden, ob Fehler aufgetreten sind oder nicht. -\end{itemize} - -\begin{figure}%[!ht] - \centering - %\includegraphics[width=\textwidth]{papers/reedsolomon/figures/polynom2} - \input{papers/reedsolomon/tikz/polynomraw.tex} - \caption{Polynom $p(x)$ von der Gleichung\eqref{reedsolomon:equation1}} - \label{fig:polynom} -\end{figure} \qedhere +\end{itemize} \end{beispiel} \section{Anzahl Übertragungswerte bestimmen \label{reedsolomon:section:Fehlerkorrekturstellen}} -Um zu bestimmen, wie viele zusätzliche \textcolor{darkgreen}{Übertragungspunkte} notwendig sind um die Fehler zu korrigieren, +Um zu bestimmen, wie viele zusätzliche \textcolor{darkgreen}{Übertragungspunkte} notwendig sind, um die Fehler zu korrigieren, muss man zuerst wissen, wie viele \textcolor{blue}{Datenwerte} gesendet und wie viele \textcolor{red}{Fehler} erkannt werden sollen. -Die Anzahl Datenwerte ergeben die Anzahl Polynomkoeffizenten \textcolor{blue}{$k$} und somit den Grad $k-1$ des Polynoms. -Die Bestimmung der Anzahl der Fehler \textcolor{red}{$t$}, welche korrigiert werden können, braucht Redundanz. +Die Anzahl Datenwerte ergibt die Anzahl +\textcolor{blue}{$k$} +Polynomkoeffizenten +und somit den Grad $k-1$ des Polynoms. +Die Bestimmung der Anzahl \textcolor{red}{$t$} der Fehler, welche korrigiert werden können, braucht Redundanz. Bilden wir verschieden grosse Polynome und untersuchen diese mit unterschiedlich vielen Fehlern erkennt man allmählich ein Muster. \begin{table}%[!ht] @@ -142,12 +144,14 @@ Bilden wir verschieden grosse Polynome und untersuchen diese mit unterschiedlich \par Es müssen mehr Punkte auf dem \textcolor{blue}{originalen Polynom} liegen, als auf dem konkurenzierenden. Somit braucht man für die Übertragung pro \textcolor{red}{Fehler} zwei Übertragungspunkte mehr. -Wie in der Tabelle \ref{tab:fehlerkorrekturstellen} ersichtlich ist ergeben sich diese Anzahl an \textcolor{darkgreen}{Punkte} für die Übertragung. +Wie in der Tabelle \ref{tab:fehlerkorrekturstellen} ersichtlich ist ergibt sich die +Anzahl \begin{equation} \textcolor{darkgreen}{u}= \textcolor{blue}{k}+2\textcolor{red}{t}. \label{reedsolomon:equation2} \end{equation} +von \textcolor{darkgreen}{Punkten} für die Übertragung. Ein Nebeneffekt ist, dass auch $2t$ Fehler erkannt werden können, die aber nicht korrigiert werden können. Um die Polynomkoeffizenten nach der Übertragung zu rekonstruieren, haben wir jedes mal die Polynominterpolationsmethode angewendet. diff --git a/buch/papers/reedsolomon/rekonstruktion.tex b/buch/papers/reedsolomon/rekonstruktion.tex index b099e68..4f7fd7b 100644 --- a/buch/papers/reedsolomon/rekonstruktion.tex +++ b/buch/papers/reedsolomon/rekonstruktion.tex @@ -23,9 +23,10 @@ Aufgrund der Fehlerstellen müssen wir aber davon ausgehen, das wir nicht mehr d Wir stellen also die Matrix auf und markieren gleichzeitig die Fehlerstellen: \[ \textcolor{gray}{ - \begin{pmatrix} + \begin{matrix} a^0 \\ a^1 \\ a^2 \\ \textcolor{red}{a^3} \\ a^4 \\ a^5 \\ a^6 \\ a^7 \\ \textcolor{red}{a^8} \\ a^9 \\ -\end{pmatrix}} +\end{matrix}} +\qquad \begin{pmatrix} 5 \\ 3 \\ 6 \\ \textcolor{red}{8} \\ 2 \\ 10 \\ 2 \\ 7 \\ \textcolor{red}{1} \\ 4 \\ \end{pmatrix} @@ -176,7 +177,7 @@ Nun können wir den Gauss-Algorithmus anwenden um die Matrix zu Invertieren. \cdot \begin{pmatrix} 5 \\ 3 \\ 6 \\ 2 \\ 10 \\ 2 \\ -\end{pmatrix} +\end{pmatrix}. \] Multiplizieren wir nun aus, erhalten wir unseren Nutzdatenteil \[ diff --git a/buch/papers/reedsolomon/zusammenfassung.tex b/buch/papers/reedsolomon/zusammenfassung.tex index c24fcf3..a098107 100644 --- a/buch/papers/reedsolomon/zusammenfassung.tex +++ b/buch/papers/reedsolomon/zusammenfassung.tex @@ -6,6 +6,8 @@ \section{Zusammenfassung \label{reedsolomon:section:zf}} \rhead{Zusammenfassung} +\index{Reed-Solomon-Code, Zusammenfassung}% +\index{Zusammenfassung Reed-Solomon-Code}% Dieser Abschnitt beinhaltet eine Übersicht über die Funktionsweise eines Reed-Solomon-Codes für beliebige endliche Körper. \subsubsection{Schritt 1: primitives Element} @@ -55,11 +57,11 @@ Die Codierungsmatrix ändert sich somit zur Decodierungsmatrix Daraus lässt sich der Nachrichtenblock aus dem Übertragungsvektor rekonstruieren. \subsubsection{Schritt 4: Decodierung mit Fehler} -Sollte der Übertragungsvektor fehlerhaft empfangen werden, so kann der Nachrichtenblock nicht durch invertieren der Matrix rekonstruiert werden. +Sollte der Übertragungsvektor fehlerhaft empfangen werden, so kann der Nachrichtenblock nicht durch Invertieren der Matrix rekonstruiert werden. Zur Lokalisierung der Fehlerstellen nehmen wir das Polynom $f(X)$ zur Hilfe, welches wir über den Satz von Fermat bestimmt haben. Berechnen wir daraus das $\operatorname{kgV}$ von $f(X)$ und $d(X)$, so erhalten wir ein Lokatorpolynom. -Durch das bestimmen der Exponenten erhalten wir die Fehlerhaften Stellen im Übertragungsvektor. -Für die Rekonstruktion stellen wir ein Gleichungssystem auf und entfernen daraus die Fehlerhaften Zeilen. +Durch das Bestimmen der Exponenten erhalten wir die fehlerhaften Stellen im Übertragungsvektor. +Für die Rekonstruktion stellen wir ein Gleichungssystem auf und entfernen daraus die fehlerhaften Zeilen. Im Anschluss kann das verkleinerte Gleichungssystem gelöst werden. Als Resultat erhalten wir die fehlerfreie Nachricht. %Aus diesem Grund suchen wir nach einem Lokatorpolynom, welches uns die Fehlerhaften Stellen im Übertragungsvektor anzeigt. |