diff options
Diffstat (limited to 'buch/papers/reedsolomon')
48 files changed, 1955 insertions, 302 deletions
diff --git a/buch/papers/reedsolomon/Makefile b/buch/papers/reedsolomon/Makefile index 9c96e88..25fd98b 100644 --- a/buch/papers/reedsolomon/Makefile +++ b/buch/papers/reedsolomon/Makefile @@ -4,6 +4,52 @@ # (c) 2020 Prof Dr Andreas Mueller # -images: - @echo "no images to be created in reedsolomon" +SOURCES := \ + anwendungen.tex \ + codebsp.tex \ + decmitfehler.tex \ + decohnefehler.tex \ + dtf.tex \ + einleitung.tex \ + endlichekoerper.tex \ + hilfstabellen.tex \ + idee.tex \ + main.tex \ + packages.tex \ + rekonstruktion.tex \ + restetabelle1.tex \ + restetabelle2.tex \ + standalone.tex \ + zusammenfassung.tex + +TIKZFIGURES := \ + tikz/polynom2.tex \ + tikz/plotfft.tex + +FIGURES := $(patsubst tikz/%.tex, figures/%.pdf, $(TIKZFIGURES)) + + +all: images standalone + + +.PHONY: images +images: $(FIGURES) + +figures/%.pdf: tikz/%.tex + mkdir -p figures + pdflatex --output-directory=figures $< + +.PHONY: standalone +standalone: standalone.tex $(SOURCES) $(FIGURES) + mkdir -p standalone + cd ../..; \ + pdflatex \ + --halt-on-error \ + --shell-escape \ + --output-directory=papers/reedsolomon/standalone \ + papers/reedsolomon/standalone.tex; + cd standalone; \ + bibtex standalone; \ + makeindex standalone; + diff --git a/buch/papers/reedsolomon/Makefile.inc b/buch/papers/reedsolomon/Makefile.inc index 6a676f8..ea51f7a 100644 --- a/buch/papers/reedsolomon/Makefile.inc +++ b/buch/papers/reedsolomon/Makefile.inc @@ -6,9 +6,17 @@ dependencies-reedsolomon = \ papers/reedsolomon/packages.tex \ papers/reedsolomon/main.tex \ - papers/reedsolomon/references.bib \ - papers/reedsolomon/teil0.tex \ - papers/reedsolomon/teil1.tex \ - papers/reedsolomon/teil2.tex \ - papers/reedsolomon/teil3.tex + papers/reedsolomon/einleitung.tex \ + papers/reedsolomon/idee.tex \ + papers/reedsolomon/dtf.tex \ + papers/reedsolomon/endlichekoerper.tex \ + papers/reedsolomon/codebsp.tex \ + papers/reedsolomon/decohnefehler.tex \ + papers/reedsolomon/decmitfehler.tex \ + papers/reedsolomon/rekonstruktion.tex \ + papers/reedsolomon/zusammenfassung.tex \ + papers/reedsolomon/anwendungen.tex \ + papers/reedsolomon/hilfstabellen.tex \ + papers/reedsolomon/references.bib + diff --git a/buch/papers/reedsolomon/RS presentation/images/polynom1 - Kopie.tex b/buch/papers/reedsolomon/RS presentation/images/polynom1 - Kopie.tex new file mode 100644 index 0000000..038e93e --- /dev/null +++ b/buch/papers/reedsolomon/RS presentation/images/polynom1 - Kopie.tex @@ -0,0 +1,33 @@ +% polynome1 +%------------------- +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{times} +\usepackage{txfonts} +\usepackage{pgfplots} +\usepackage{csvsimple} +\usetikzlibrary{arrows,intersections,math} +\newcommand{\teiler}{40} +\begin{document} + + +\begin{tikzpicture}[>=latex,thick] + + \begin{axis}[ + axis lines = left, + xlabel = \(x\), + ylabel = {\(f(x)\)}, + ] + %Below the red parabola is defined + \addplot[ + color=blue, + ] + coordinates { + (0,23.1)(10,27.5)(20,32)(30,37.8)(40,44.6)(60,61.8)(80,83.8)(100,114) + }; + %Here the blue parabola is defined + + \end{axis} +\end{tikzpicture} +\end{document} + diff --git a/buch/papers/reedsolomon/anwendungen.tex b/buch/papers/reedsolomon/anwendungen.tex new file mode 100644 index 0000000..b9b1d69 --- /dev/null +++ b/buch/papers/reedsolomon/anwendungen.tex @@ -0,0 +1,168 @@ +% +% anwendungen.tex -- Anwendungen des Reed-Solomon-Codes +% +% (c) 2021 Michael Steiner, Hochschule Rapperswil +% +\section{Anwendungen des Reed-Solomon-Codes + \label{reedsolomon:section:anwendung}} +\rhead{Anwendungen} + +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. + +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. +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. +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. + +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. + +Einen ähnlichen Ansatz verfolgen QR-Codes, wobei die Information auch dann noch gelesen werden kann wenn der Code nicht mehr vollständig vorhanden ist. + +%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. +% +% da aufgrund der grossen Distanz Stunden vergehen können bis gesendete Daten auf der Erde empfangen werden kann. +% + +Obwohl alle diese Codes nach dem gleichen Prinzip arbeiten gibt es starke Unterschiede in deren Funktionsweise. +Dies kommt vor allem daher, da die Codes nur Ressourcen zur Verfügung haben, die von der Hardware bereitstellt wird, auf denen die Codes implementiert wurden. +Diese Codes bedienen sich daher verschiedener Tricks und Optimierungen um möglichst effizient zu arbeiten. + +Um die Fähigkeit eines verwendeten Reed-Solomon-Codes zu beschreiben verwendet man die Notation ($n$,$k$), wobei $n$ die Grösse des Nachrichtenblocks angibt und $k$ die Anzahl der Stellen, die für Nutzdaten gebraucht werden können. + +%Dies kommt vor allem daher, da diese Codes an ihre Hardware gebunden sind, auf denen sie implementiert worden sind. +%Deshalb wurden diese Codes stark optimiert damit sie möglichst Effizient arbeiten können. +% +%Um diese Hardware möglichst effizient zu nutzen wurden gewisse mathematische tricks angewendet um den Code möglichst effizient zu nutzen. +% +% um mit maximaler Effizienz zu arbeiten. +%Es überrascht daher nicht, dass vor allem ältere Codes im binären Körper $\mathbb{F}_{2}$ arbeiten. +% +% um den Code mit maximaler Effizienz zu nutzen. +% +%Alle diese Anwendungen verfügen über eigene spezifizierten Eigenschaften. +% +%, wobei bei allen dieser Anwendungen jeweils eine unterschiedliche Version des Codes implementiert wurden. +% +%Dies kommt vor allem daher, da diese Codes immer an ihre dementsprechende Hardware gebunden sind, auf denen sie implementiert wurden um den Code mit maximaler Effizienz zu nutzen. +% +% eigene Version des Codes implementiert haben. +% +%Bei einer Technischen Umsetzung eines solchen Codes werden wir auf eine reihe neuer Probleme stossen wie Ressourceneffizienz, Laufzeitoptimierung, usw. +% +%Hinzu kommt, dass für verschiedene Anwendungen verschiedene Versionen des Reed-Solomon-Codes zur Anwendung kommen. +% +%Nachfolgend werden wir ein paar dieser Anwendungen Vorstellen, da sich herausstellt, dass Reed-Solomon-Code sehr +% +%Als letzte Frage stellt sich jetzt nur noch, wo diese Codes eingesetzt werden. +% +%Bisher haben wir +% +%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 + +\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. +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. +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. + +% +% Funktioniert aber nach einem ganz anderen Prinzip. +% +%Durch diese doppelte Codierung wird eine äusserst hohe Übertragungssicherheit garantiert. +% +%Dabei steht die Zahl 255 für grösse des Nachrichtenblocks, der die Anzahl 233 +% +% +% \textcolor{red}{benötigt das weitere Erklärungen, wie z.b. 255: grösse Nachrichtenblock, 233: anzahl der nutzbaren daten ?} zusammen mit einem konventionellen Faltungscode übertragen. Eine von der Sonde gesendete Nachricht hat eine Blockgrösse von 255 Zeichen, wovon 233 für die Nutzdaten gebraucht werden können. Dieser Code ist somit in der Lage 11 Fehler in einem Nachrichtenblock zu korrigieren. +% +% Die zwei im Jahre 1977 gestarteten Sonden senden Daten mit der Hilfe eines RS(255,233)-Code für die digitalen Bilder sowie einem konventionellen Faltungscode. +% +% +%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. +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. + +%Beide lesen +% wobei beide Codes auch Fehler aus dem jeweiligen anderen Block korrigieren + +\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[]{ + \includegraphics[width=0.4\textwidth]{papers/reedsolomon/images/qrcode_l} + } +% \subfigure[]{ +% \includegraphics[width=0.4\textwidth]{papers/reedsolomon/images/designer_qrcode_ohnelogo} +% } +% \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.} + \label{fig:qr} +\end{figure} + +\begin{figure} + \centering +% \subfigure[]{ +% \includegraphics[width=0.4\textwidth]{papers/reedsolomon/images/qrcode_h} +% } +% \subfigure[]{ +% \includegraphics[width=0.4\textwidth]{papers/reedsolomon/images/qrcode_l} +% } + \subfigure[]{ + \includegraphics[width=0.4\textwidth]{papers/reedsolomon/images/designer_qrcode_ohnelogo} + } + \subfigure[]{ + \includegraphics[width=0.4\textwidth]{papers/reedsolomon/images/designer_qrcode} + } + \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 diff --git a/buch/papers/reedsolomon/codebsp.tex b/buch/papers/reedsolomon/codebsp.tex index 262297e..8430ebd 100644 --- a/buch/papers/reedsolomon/codebsp.tex +++ b/buch/papers/reedsolomon/codebsp.tex @@ -1,18 +1,17 @@ % -% teil3.tex -- Beispiel-File für Teil 3 +% codebsp.tex -- Codierung eines Beispiels % -% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil +% (c) 2021 Michael Steiner, Hochschule Rapperswil % \section{Codierung eines Beispiels \label{reedsolomon:section:codebsp}} -\rhead{Koerper Festlegen} +\rhead{Codierung eines Beispiels} -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 \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. +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. +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. @@ -22,7 +21,7 @@ Aus der Definition der Endlichen Körper (ersichtlich auch in den Tabellen) folg %\input{papers/reedsolomon/restetabelle1} %\input{papers/reedsolomon/restetabelle2} -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. +Die Menge uns zur Verfügung stehender Zahlen legt auch fest, 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}, @@ -52,16 +51,16 @@ 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 die Nachricht +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, so ist die Nachricht fehlerfrei übertragen worden. -Da wir in den folgenden Abschnitten mit Polynomen arbeiten, stellen wir die Nachicht auch noch als Polynom +Da wir in den folgenden Abschnitten mit Polynomen arbeiten, stellen wir die Nachricht auch noch als Polynom \[ m(X) = 4X^5 + 7X^4 + 2X^3 + 5X^2 + 8X + 1 \] @@ -77,16 +76,17 @@ dar. \subsection{Der Ansatz der diskreten Fouriertransformation \label{reedsolomon:subsection:diskFT}} -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 +In einem vorherigen Abschnitt \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 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 \[ \mathbb{F}_{11} = \{0,1,2,3,4,5,6,7,8,9,10\} \] -in +in die von $a$ abhängige Schreibweise \[ \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\}. \] -umzuschreiben. +%Jetzt brauchen wir nur noch eine geeignete Zahl für $a$ zu finden. % 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 @@ -116,29 +116,45 @@ umzuschreiben. \subsubsection{Die primitiven Einheitswurzeln \label{reedsolomon:subsection:primsqrt}} -Wenn wir jetzt sämtliche Zahlen von $\mathbb{F}_{11}$ in $a$ einsetzen +Wenn wir jetzt Zahlen von $\mathbb{F}_{11}$ an Stelle von $a$ einsetzen, erhalten wir \begin{center} -\begin{tabular}{c r c l} -%$a = 0 :$& $\qquad \mathbb{Z}_{11}\setminus\{0\}$ &$=$& $\{0, 0, 0, 0, 0, 0, 0, 0, 0, 0\}$ \\ -$a = 1 :$& $\qquad \mathbb{Z}_{11}\setminus\{0\}$ &$=$& $\{1, 1, 1, 1, 1, 1, 1, 1, 1, 1\}$ \\ -$a = 2 :$& $\qquad \mathbb{Z}_{11}\setminus\{0\}$ &$=$& $\{1, 2, 4, 8, 5, 10, 9, 7, 3, 6\}$ \\ -$a = 3 :$& $\qquad \mathbb{Z}_{11}\setminus\{0\}$ &$=$& $\{1, 3, 9, 5, 4, 1, 3, 9, 5, 4\}$ \\ -$a = 4 :$& $\qquad \mathbb{Z}_{11}\setminus\{0\}$ &$=$& $\{1, 4, 5, 9, 3, 1, 4, 5, 9, 3\}$ \\ -$a = 5 :$& $\qquad \mathbb{Z}_{11}\setminus\{0\}$ &$=$& $\{1, 5, 3, 4, 9, 1, 5, 3, 4, 9\}$ \\ -$a = 6 :$& $\qquad \mathbb{Z}_{11}\setminus\{0\}$ &$=$& $\{1, 6, 3, 7, 9, 10, 5, 8, 4, 2\}$ \\ -$a = 7 :$& $\qquad \mathbb{Z}_{11}\setminus\{0\}$ &$=$& $\{1, 7, 5, 2, 3, 10, 4, 6, 9, 8\}$ \\ -$a = 8 :$& $\qquad \mathbb{Z}_{11}\setminus\{0\}$ &$=$& $\{1, 8, 9, 6, 4, 10, 3, 2, 5, 7\}$ \\ -$a = 9 :$& $\qquad \mathbb{Z}_{11}\setminus\{0\}$ &$=$& $\{1, 9, 4, 3, 5, 1, 9, 4, 3, 5\}$ \\ -$a = 10 :$& $\qquad \mathbb{Z}_{11}\setminus\{0\}$ &$=$& $\{1, 10, 1, 10, 1, 10, 1, 10, 1, 10\}$ +\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\}$. \\ \end{tabular} \end{center} -so fällt uns auf, dass für $a$ die Zahlen $2,6,7,8$ erhalten, die tatsächlich den gesamten Zahlenraum von $\mathbb{F}_{11}$ abbilden. Solche Zahlen werden \em Primitive Einheitswurzel \em genannt. -Wenden wir diese Vorgehensweise auch für andere Endliche Körper an, so werden wir sehen, dass wir immer mindestens zwei solcher Einheitswurzel finden werden. Somit ist es uns überlassen, eine dieser Einheitswurzeln auszuwählen, mit der wir weiter rechnen wollen. Für das Beispiel wählen wir die Zahl $a^i = 8$. +%\begin{center} +%\begin{tabular}{c r c l} +%%$a = 0 :$& $\qquad \mathbb{Z}_{11}\setminus\{0\}$ &$=$& $\{0, 0, 0, 0, 0, 0, 0, 0, 0, 0\}$ \\ +%$a = 1 :$& $\qquad \mathbb{Z}_{11}\setminus\{0\}$ &$=$& $\{1, 1, 1, 1, 1, 1, 1, 1, 1, 1\}$ \\ +%$a = 2 :$& $\qquad \mathbb{Z}_{11}\setminus\{0\}$ &$=$& $\{1, 2, 4, 8, 5, 10, 9, 7, 3, 6\}$ \\ +%$a = 3 :$& $\qquad \mathbb{Z}_{11}\setminus\{0\}$ &$=$& $\{1, 3, 9, 5, 4, 1, 3, 9, 5, 4\}$ \\ +%$a = 4 :$& $\qquad \mathbb{Z}_{11}\setminus\{0\}$ &$=$& $\{1, 4, 5, 9, 3, 1, 4, 5, 9, 3\}$ \\ +%$a = 5 :$& $\qquad \mathbb{Z}_{11}\setminus\{0\}$ &$=$& $\{1, 5, 3, 4, 9, 1, 5, 3, 4, 9\}$ \\ +%$a = 6 :$& $\qquad \mathbb{Z}_{11}\setminus\{0\}$ &$=$& $\{1, 6, 3, 7, 9, 10, 5, 8, 4, 2\}$ \\ +%$a = 7 :$& $\qquad \mathbb{Z}_{11}\setminus\{0\}$ &$=$& $\{1, 7, 5, 2, 3, 10, 4, 6, 9, 8\}$ \\ +%$a = 8 :$& $\qquad \mathbb{Z}_{11}\setminus\{0\}$ &$=$& $\{1, 8, 9, 6, 4, 10, 3, 2, 5, 7\}$ \\ +%$a = 9 :$& $\qquad \mathbb{Z}_{11}\setminus\{0\}$ &$=$& $\{1, 9, 4, 3, 5, 1, 9, 4, 3, 5\}$ \\ +%$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$. \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 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. % @@ -150,12 +166,13 @@ 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. Um das ganze noch ein wenig übersichtlicher zu gestalten können wir die Polynome zu einer Matrix zusammenfassen und bildet so unsere Transformationsmatrix $A$. +als unser Übertragungsvektor. \subsection{Allgemeine Codierung \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 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\\ @@ -173,6 +190,7 @@ v = A \cdot m \qquad \Rightarrow \qquad v = \begin{pmatrix} \begin{pmatrix} 1 \\ 8 \\ 5 \\ 2 \\ 7 \\ 4 \\ 0 \\ 0 \\ 0 \\ 0 \\ \end{pmatrix} +. \] Für unseren Übertragungsvektor resultiert \[ diff --git a/buch/papers/reedsolomon/decmitfehler.tex b/buch/papers/reedsolomon/decmitfehler.tex index feaa027..598cf68 100644 --- a/buch/papers/reedsolomon/decmitfehler.tex +++ b/buch/papers/reedsolomon/decmitfehler.tex @@ -1,22 +1,22 @@ % -% teil3.tex -- Beispiel-File für Teil 3 +% decmitfehler.tex -- Decodierung mit Fehler % -% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil +% (c) 2021 Michael Steiner, Hochschule Rapperswil % \section{Decodierung: Ansatz mit Fehlerkorrektur \label{reedsolomon:section:decmitfehler}} -\rhead{fehlerhafte rekonstruktion} +\rhead{Decodierung mit Fehler} Bisher haben wir die Decodierung unter der Bedingung durchgeführt, dass der Übertragungsvektor fehlerlos versendet und empfangen wurde. In der realen Welt müssen wir uns jedoch damit abfinden, dass kein Übertragungskanal garantiert fehlerfrei ist und das wir früher oder später mit Fehlern rechnen müssen. Genau für dieses Problem wurden Fehler korrigierende Codes, wie der Reed-Solomon-Code, entwickelt. In diesem Abschnitt betrachten wir somit die Idee der Fehlerkorrektur und wie wir diese auf unser Beispiel anwenden können. + Der Übertragungskanal im Beispiel weisst jetzt den Fehlervektor \[ u = [0, 0, 0, 3, 0, 0, 0, 0, 2, 0] \] auf. - -Senden wir jetzt unser Übertragungsvektor $v$ durch diesen Kanal addiert sich der Fehlervektor $u$ auf unsere Übertragung und wir erhalten +Senden wir jetzt unser Übertragungsvektor $v$ durch diesen Kanal, addiert sich der Fehlervektor $u$ auf unsere Übertragung und wir erhalten \begin{center} \begin{tabular}{c | c r } @@ -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. + +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. -Setzen wir jetzt noch unsere Einheitswurzel aus dem Beispiel ein so erhalten wir +%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 \\ @@ -119,22 +127,22 @@ Setzen wir jetzt noch 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, 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 drei und acht zu finden sind. Für das einfache Bestimmen von Hand mag dies ja noch ausreichen, jedoch können wir mit diesen Stellen nicht das Lokatorpolynom bestimmen, denn dafür bräuchten wir alle Nullstellen, an denen es Fehler gegeben hat (also sozusagen genau das umgekehrte). Um dies zu erreichen wenden wir eine andere Herangehensweise und nehmen uns den Satz von Fermat sowie den kleinsten gemeinsamen Teiler zur Hilfe. \subsection{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\} +f(X) = X^{10}-1 = 0 \qquad \text{für } X \in \{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) @@ -165,7 +173,7 @@ Das kgV hat nämlich die Eigenschaft sämtliche Nullstellen zu finden, also nich ersichtlich ist. Aus dem vorherigen Abschnitt wissen wir auch, dass $d(X)$ alle korrekten Nullstellen beinhaltet. Teilen wir das kgV jetzt auf in \[ -\operatorname{kgV}(f(X),d(X)) = d(X) \cdot l(X) +\operatorname{kgV}(f(X),d(X)) = d(X) \cdot l(X), \] sollten wir für $l(X)$ eine Liste mit allen fehlerhaften Nullstellen erhalten. Somit ist @@ -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}} @@ -184,26 +192,26 @@ In Abschnitt \ref{reedsolomon:section:decmitfehler} haben wir d(X) = r(X) - m(X) \] in Abhängigkeit von $m(X)$ berechnet. -Jedoch haben wir ausser acht gelassen, dass $m(X)$ auf der Empfängerseite nicht existiert und somit gänzlich unbekannt ist. +Jedoch haben wir ausser acht gelassen, dass $m(X)$ auf der Empfängerseite nicht verfügbar und somit gänzlich unbekannt ist. Es scheint so als würde dieser Lösungsansatz, den wir bisher verfolgt haben, nicht funktioniert. -Wir könnten uns höchstens noch fragen, ob wir tatsächlich nichts über den Nachrichtenvektor im Beispiel wissen. Wenn wir noch einmal den Vektor betrachten als +Wir könnten uns höchstens noch fragen, ob wir tatsächlich nichts über den Nachrichtenvektor im Beispiel wissen. + +Wenn wir noch einmal den Vektor betrachten als \[ m = [0,0,0,0,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 $0$ haben 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 +302,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..50bd8d6 100644 --- a/buch/papers/reedsolomon/decohnefehler.tex +++ b/buch/papers/reedsolomon/decohnefehler.tex @@ -1,11 +1,11 @@ % -% teil3.tex -- Beispiel-File für Teil 3 +% decohnefehler.tex -- Decodierung ohne Fehler % -% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil +% (c) 2021 Michael Steiner, Hochschule Rapperswil % \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,11 +33,12 @@ 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$. +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 +%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} +8^1 \qquad \rightarrow \qquad 8^{-1}. \] -Mit einem solchen Problem haben wir uns bereits in Abschnitt \ref{buch:section:euklid} befasst und so den euklidischen Algorithmus kennengelernt, den wir auf unseren Fall anwenden können. +Mit einem solchen Problem haben wir uns bereits in Abschnitt \ref{buch:section:euklid} befasst und so den euklidischen Algorithmus kennengelernt, den wir auf diesen Fall anwenden können. % Old Text %Im Abschnitt \textcolor{red}{4.1} haben wir den euklidischen Algorithmus kennengelernt, den wir auf unseren Fall anwenden können. @@ -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}} -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 +77,114 @@ 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. +Alternativ können wir das Resultat auch aus der Tabelle \ref{reedsolomon:subsection:mptab} ablesen. +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}$. +Wir müssen also damit rechnen, dass wir für die Inverse Transformationsmatrix ebenfalls einen solchen Vorfaktor 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. So erhalten wir $10^{-1} = 10$ als 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/dtf.tex b/buch/papers/reedsolomon/dtf.tex new file mode 100644 index 0000000..4552bed --- /dev/null +++ b/buch/papers/reedsolomon/dtf.tex @@ -0,0 +1,85 @@ +% +% dtf.tex -- Idee mit DFT +% +\section{Übertragung mit Hilfe der Diskrten Fourientransformation +\label{reedsolomon:section:dtf}} +\rhead{Umwandlung mit DTF} +Um die Polynominterpolation zu umgehen, gehen wir nun über in die Fourietransformation. +Dies wird weder eine Erklärung der Forientransorfmation, noch ein genauer gebrauch für den Reed-Solomon-Code. +Dieser Abschnitt zeigt nur wie die Fourietransformation auf Fehler reagiert. +Das ganze zeigen wir mit einem Beispiel einer Übertragung von Zahlen mit Hilfe der Fourietransformation. + +\subsection{Diskrete Fourietransformation Zusamenhang +\label{reedsolomon:subsection:dtfzusamenhang}} +Mit hilfe der Fourietransformation werden die \textcolor{blue}{blauen Datenpunkte} transformiert, +zu den \textcolor{darkgreen}{grünen Übertragungspunkten}. +Durch eine Rücktransformation könnnen die \textcolor{blue}{blauen Datenpunkte} wieder rekonstruiert werden. + +\subsubsection{Beispiel einer Übertragung +\label{reedsolomon:subsection:Übertragungsabfolge}} +Der Auftrag ist nun 64 Daten zu übertragen und nach 32 Fehler abzusicheren, +16 Fehler erkennen und rekonstruieren. + +Dieser Auftrag soll mittels Fouriertransformation bewerkstelligt werden. +In der Abbildung \ref{reedsolomon:subsection:Übertragungsabfolge} sieht man dies Schritt für Schritt, +und hier werden die einzelne Schritte erklärt: +\begin{enumerate}[(1)] + \item Das Signal hat 64 die Daten $k$, hier zufällige Zahlen, welche übertragen werden sollen. + Zusätzlich soll nach 16 Fehler $t$, die rekonstruierbar sind abgesichert werden. + Das macht dann insgesamt $k + 2t = + 64 +2 \cdot 16= 96$ Übertragungszahlen. + (siehe Abschnitt \externaldocument{papers/reedsolomon/idee}\ref{reedsolomon:section:Fehlerkorrekturstellen}) + Die 32 Fehlerkorrekturstellen werden als Nullzahlen Übertragen. + \item Nun werden mittels der diskreten Fourietransformation diese 96 codiert, transformiert. + Das heisst alle Informationen ist in alle Zahlenvorhanden, auch die Fehlerkorrekturstellen Nullzahlen. + \item Nun kommen drei Fehler dazu an den Übertragungsstellen 7, 21 und 75. + Die Fehler können auf den ganzen 96 Übertragungswerten liegen, wie die 75 zeigt. +Zu Beachten ist auch noch, dass der Fehler um das 20- bis 150-Fache kleiner ist.Die Fehlerskala ist rechts. + \item Dieses wird nun Empfangen, man kann keine Fehler erkennen, da diese soviel kleiner sind. + Für das Decodieren wird die Inverse Fourietransformation angewendet, und alle Fehler werden mittransformiert. + \item Nun sieht man die Fehler im decodierten Signal in den Übertragungszahlen. + Von den Übertragungsstellen 64 bis 96 erkennt man, das diese nicht mehr Null sind. + \item Diese Fehlerkorrekturstellen 64 bis 96, dies definieren wir als Syndrom. + In diesem Syndrom ist die Fehlerinformation gespeichert und muss nur noch transformiert werden. + \item Hier sieht man genau wo die Fehler stattgefunden haben. + Leider nicht mehr mit der Qualtiätt der Ursprünglichen Fehler, sie sind nur noch 0.6 oder 0.4 gross. + Obwohl der Fehler um das 20Fache kleiner ist erkennt man im Locator die Fehlerstellen wieder. + \end{enumerate} + Nun haben wir mit Hilfe der Fourietransformation die 3 Fehlerstellen durch das Syndrom lokalisiert, + jetzt gilt es nur noch diese zu korrigieren und wir haben unser originales Signal wieder. +\begin{figure} + \centering + \resizebox{1.1\textwidth}{!}{ + \includegraphics[width=\textwidth]{papers/reedsolomon/figures/plotfft} + %\input{papers/reedsolomon/tikz/plotfftraw.tex} + } + \caption{Übertragungsabfolge \ref{reedsolomon:subsection:Übertragungsabfolge}} + \label{fig:sendorder} +\end{figure} + +Nun zur Definition der Diskrete Fourietransformation, diese ist definiert als + \begin{equation} + \hat{c}_{k} + = \frac{1}{N} \sum_{n=0}^{N-1} + {f}_n \cdot e^{-\frac{2\pi j}{N} \cdot kn}. + ,\label{reedsolomon:DFT} + \end{equation} + Wenn man nun + \begin{equation} + w = + e^{-\frac{2\pi j}{N} k} + \label{reedsolomon:DFT_summand} + \end{equation} + ersetzte, und $N$ konstantbleibt, erhält man + \begin{equation} + \hat{c}_{k}= + \frac{1}{N}( {f}_0 w^0 + {f}_1 w^1 + {f}_2 w^2 + \dots + {f}_{N-1} w^N) + \label{reedsolomon:DFT_polynom} + \end{equation} + was überaust ähnlich zu unserem Polynomidee ist. +Die Polynominterpolation und die Fourietransformation rechnen beide mit reelen Zahlen. +Wenn die Fehlerabweichung sehr sehr klein ist, erkennt man diese irgendwann nicht mehr. +Zusätzlich muss mann immer Grenzen bestimmen auf wieviel Stellen gerechnet wird und wie die Fehler erkannt werden im Locator. +Deshalb haben Mathematiker einen neuen Körper gesucht und ihn in der Endlichkeit gefunden, +dies wird nun im nächsten Abschnitt genauer erklärt. + diff --git a/buch/papers/reedsolomon/einleitung.tex b/buch/papers/reedsolomon/einleitung.tex new file mode 100644 index 0000000..074df05 --- /dev/null +++ b/buch/papers/reedsolomon/einleitung.tex @@ -0,0 +1,17 @@ +% +% einleitung.tex -- Beispiel-File für die Einleitung +% +% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil +% +\section{Einleitung +\label{reedsolomon:section:einleitung}} +\rhead{Einleitung} +Der Reed-Solomon-Code ist entstanden um, +das Problem der Fehler bei der Datenübertragung, zu lösen. +In diesem Abschnitt wird möglichst verständlich die mathematische Abfolge, +Funktion oder Algorithmus des Reed-Solomon-Code erklärt. +Es wird jedoch nicht auf die technische Umsetzung oder Implementierung eingegangen. + + + + diff --git a/buch/papers/reedsolomon/endlichekoerper.tex b/buch/papers/reedsolomon/endlichekoerper.tex index 146067a..1d196fd 100644 --- a/buch/papers/reedsolomon/endlichekoerper.tex +++ b/buch/papers/reedsolomon/endlichekoerper.tex @@ -1,14 +1,14 @@ % -% teil1.tex -- Beispiel-File für das Paper +% endlichekoerper.tex -- endliche Körper % -% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil +% (c) 2021 Michael Steiner, Hochschule Rapperswil % \section{Reed-Solomon in Endlichen Körpern \label{reedsolomon:section:endlichekoerper}} -\rhead{Problemstellung} - -\textcolor{red}{TODO: (warten auf den 1. Teil)} - +\rhead{Reed-Solomon in endlichen Körpern} +\[ +\textcolor{red}{\text{TODO: (warten auf den 1. Teil)}} +\] Das Rechnen in endlichen Körpern bietet einige Vorteile: \begin{itemize} diff --git a/buch/papers/reedsolomon/experiments/f.m b/buch/papers/reedsolomon/experiments/f.m index 6bdc741..bf2587c 100644 --- a/buch/papers/reedsolomon/experiments/f.m +++ b/buch/papers/reedsolomon/experiments/f.m @@ -1,8 +1,8 @@ -# -# f.m -- Reed-Solomon-Visualisierung mit FFT -# -# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule -# +% +% f.m -- Reed-Solomon-Visualisierung mit FFT +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule + N = 64; b = 32; l = N + b; @@ -51,6 +51,7 @@ syndrom(1:N,1) = zeros(N,1) plot(abs(syndrom)); xlim([1, l]); title("Syndrom"); + pause() locator = abs(fft(syndrom)) @@ -59,3 +60,13 @@ plot(locator); xlim([1, l]); title("Locator"); pause() + + +writematrix([transpose(counter), abs(signal)], 'signal.txt') +writematrix([transpose(counter), abs(codiert)], 'codiert.txt') +writematrix([transpose(counter), fehler], 'fehler.txt') +writematrix([transpose(counter), abs(empfangen)], 'empfangen.txt') +writematrix([transpose(counter), abs(decodiert)], 'decodiert.txt') +writematrix([transpose(counter), abs(syndrom)], 'syndrom.txt') +writematrix([transpose(counter), locator], 'locator.txt') + diff --git a/buch/papers/reedsolomon/experiments/plot.tex b/buch/papers/reedsolomon/experiments/plot.tex new file mode 100644 index 0000000..4b156bb --- /dev/null +++ b/buch/papers/reedsolomon/experiments/plot.tex @@ -0,0 +1,103 @@ +% polynome1 +%------------------- +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{times} +\usepackage{txfonts} +\usepackage{pgfplots} +\usepackage{csvsimple} +\usepackage{pgfplotstable} +\usepackage{filecontents} +\usetikzlibrary{arrows,intersections,math} +\newcommand{\x}{10} +\newcommand{\y}{-8} +\begin{document} + +\begin{tikzpicture}[] + + %--------------------------------------------------------------- + %Knote + \matrix[draw = none, column sep=20mm, row sep=4mm]{ + \node(signal) [] { + \begin{tikzpicture} + \begin{axis}[ + title = {\Large {Signal}}, + xlabel={Anzahl Übertragene Zahlen}, + xtick={0,20,40,64,80,98},] + \addplot[blue] table[col sep=comma] {signal.txt}; + \end{axis} + \end{tikzpicture}}; & + + \node(codiert) [] { + \begin{tikzpicture} + \begin{axis}[title = {\Large {Codiert}}] + \addplot[] table[col sep=comma] {codiert.txt}; + \end{axis} + \end{tikzpicture}}; \\ + + &\node(fehler) [] { + \begin{tikzpicture} + \begin{axis}[scale=0.6, title = {\Large {Fehler}}] + \addplot[red] table[col sep=comma] {fehler.txt}; + \end{axis} + \end{tikzpicture}};\\ + + \node(decodiert) [] { + \begin{tikzpicture} + \begin{axis}[title = {\Large {Decodiert}}] + \addplot[blue] table[col sep=comma] {decodiert.txt}; + \end{axis} + \end{tikzpicture}}; & + + \node(empfangen) [] { + \begin{tikzpicture} + \begin{axis}[title = {\Large {Empfangen}}] + \addplot[] table[col sep=comma] {empfangen.txt}; + \end{axis} + \end{tikzpicture}};\\ + + \node(syndrom) [] { + \begin{tikzpicture} + \begin{axis}[title = {\Large {Syndrom}}] + \addplot[blue] table[col sep=comma] {syndrom.txt}; + \end{axis} + \end{tikzpicture}}; & + + \node(locator) [] { + \begin{tikzpicture} + \begin{axis}[title = {\Large {Locator}}] + \addplot[] table[col sep=comma] {locator.txt}; + \end{axis} + \end{tikzpicture}};\\ + }; + %------------------------------------------------------------- + %FFT & IFFT deskription + + \draw[thin,gray,dashed] (0,12) to (0,-12); + \node(IFFT) [scale=0.7] at (0,12.3) {IFFT}; + \draw[<-](IFFT.south west)--(IFFT.south east); + \node(FFT) [scale=0.7, above of=IFFT] {FFT}; + \draw[->](FFT.north west)--(FFT.north east); + + \draw[thick, ->,] (fehler.west)++(-1,0) +(0.05,0.5) -- +(-0.1,-0.1) -- +(0.1,0.1) -- +(0,-0.5); + %Arrows + \draw[ultra thick, ->] (signal.east) to (codiert.west); + \draw[ultra thick, ->] (codiert.south) to (fehler.north); + \draw[ultra thick, ->] (fehler.south) to (empfangen.north); + \draw[ultra thick, ->] (empfangen.west) to (decodiert.east); + \draw[ultra thick, ->] (syndrom.east) to (locator.west); + \draw(decodiert.south east)++(-1.8,1) ellipse (1.3cm and 0.8cm) ++(-1.3,0) coordinate(zoom) ; + \draw[ultra thick, ->] (zoom) to[out=180, in=90] (syndrom.north); + + %item + \node[circle, draw, fill =lightgray] at (signal.north west) {1}; + \node[circle, draw, fill =lightgray] at (codiert.north west) {2}; + \node[circle, draw, fill =lightgray] at (fehler.north west) {3}; + \node[circle, draw, fill =lightgray] at (empfangen.north west) {4}; + \node[circle, draw, fill =lightgray] at (decodiert.north west) {5}; + \node[circle, draw, fill =lightgray] at (syndrom.north west) {6}; + \node[circle, draw, fill =lightgray] at (locator.north west) {7}; + +\end{tikzpicture} +\end{document} + diff --git a/buch/papers/reedsolomon/figures/plotfft.pdf b/buch/papers/reedsolomon/figures/plotfft.pdf Binary files differnew file mode 100644 index 0000000..80d17d2 --- /dev/null +++ b/buch/papers/reedsolomon/figures/plotfft.pdf diff --git a/buch/papers/reedsolomon/figures/polynom2.pdf b/buch/papers/reedsolomon/figures/polynom2.pdf Binary files differnew file mode 100644 index 0000000..55a50ac --- /dev/null +++ b/buch/papers/reedsolomon/figures/polynom2.pdf diff --git a/buch/papers/reedsolomon/hilfstabellen.tex b/buch/papers/reedsolomon/hilfstabellen.tex index 4e39de5..24fabdf 100644 --- a/buch/papers/reedsolomon/hilfstabellen.tex +++ b/buch/papers/reedsolomon/hilfstabellen.tex @@ -1,10 +1,9 @@ % -% hilfstabellen.tex -% Autor: Michael Steiner +% hilfstabellen.tex -- Hilfstabellen % -% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil +% (c) 2021 Michael Steiner, 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/idee.tex b/buch/papers/reedsolomon/idee.tex new file mode 100644 index 0000000..41e0d4c --- /dev/null +++ b/buch/papers/reedsolomon/idee.tex @@ -0,0 +1,111 @@ +% +% idee.tex -- Polynom Idee +% +\section{Idee +\label{reedsolomon:section:idee}} +\rhead{Problemstellung} +Um beim Datenübertragen Fehler zu erkennen, könnte man die Daten jeweils doppelt senden, +und so jeweilige Fehler zu erkennen. +Doch nur schon um Fehler zu erkennen werden überproportional viele Daten doppelt und dreifach gesendet. +Der Reed-Solomon-Code macht dies auf eine andere, clevere Weise. +Das Problem liegt darin Informationen, Zahlen, +zu Übertragen und Fehler zu erkennen. +Speziell beim Reed-Solomon-Code kann man nicht nur Fehler erkennen, +man kann sogar einige Fehler korrigieren. +Der Unterschied des Fehler erkennen und korrigiren, ist das beim Erkennen nur die Frage beantwortet wird: Ist die Übertragung fehlerhaft oder nicht? +Beim Korrigieren werden Fehler erkannt und dann zusätzlich noch den original Wert rekonstruieren. +Auch eine Variante wäre die Daten nach einer Fehlerhaften sendung, nochmals zum senden auffordern(auch hier wird doppelt und dreifach gesendung), +was bei Reed-Solomon-Code-Anwendungen nicht immer sinnvoll ist. +Anwendungen finden sind im Abchnitt \externaldocument{papers/reedsolomon/anwendungen} +\ref{reedsolomon:section:anwendung} beschrieben. + +\subsection{Polynom-Ansatz +\label{reedsolomon:section:polynomansatz}} +\rhead{Polynom-Ansatz} +Eine Idee ist, aus den Daten ein Polynom zu bilden. +Diese Polynomfunktion bei bestimmten Werten errechnet und diese Punkte dann überträgt. +\begin{beispiel} Nehmen wir die Zahlen \textcolor{blue}{2}, \textcolor{blue}{1}, \textcolor{blue}{5}, +welche uns dann das Polynom +\begin{equation} +p(x) += +\textcolor{blue}{2}x^2 + \textcolor{blue}{1}x + \textcolor{blue}{5} +\label{reedsolomon:equation1} +\end{equation} +ergeben. +Übertragen werden nun die \textcolor{darkgreen}{grünen Werte} +dieses \textcolor{blue}{blauen Polynomes} an den Stellen 1, 2, 3\dots 7 dieses Polynomes. +Grafisch sieht man dies dann in Abbildung \ref{fig:polynom}, +mit den Punkten, $p(1),p(2),...,p(7) = (\textcolor{darkgreen}{8}, +\textcolor{darkgreen}{15}, \textcolor{darkgreen}{26}, +\textcolor{darkgreen}{41}, \textcolor{darkgreen}{60}, +\textcolor{darkgreen}{83}, \textcolor{darkgreen}{110})$ +Wenn ein Fehler sich in die Übertragung eingeschlichen hat, muss der Leser/Empfänger diesen erkennen und das Polynom rekonstruieren. +Der Leser/Empfänger weiss, den Grad des Polynoms und dessen \textcolor{darkgreen}{Werte} übermittelt wurden. +Die Farbe blau brauchen wir für die \textcolor{blue}{Daten} welche wir mit der Farbe grün \textcolor{darkgreen}{Übermitteln}. +\end{beispiel} + +\begin{beispiel} +Ein Polynome zweiten Grades ist durch drei Punkte eindeutig bestimmbar. +Hat es Fehler in der Übertragunge gegeben,in der Abbilbung \ref{fig:polynom} die \textcolor{red}{roten Punkte}). +Erkennt man diese Fehler, da alle korrekten Punkte auf der Parabel liegen müssen. +Die \textcolor{darkgreen}{grünen Punkte} bestimmen die Parabel, und die Fehler können zu den +\textcolor{gray}{Orginalpunkte} rekonstruiert werden. +Ab wie vielen Fehler ist das Polynom nicht mehr erkennbar beim Übertragen von 7 Punkten? +Bei 2 Fehlern kann man noch eindeutig bestimmen, dass das Polynom mit 4 Punkten, +gegenüber dem mit 5 Punkten falsch liegt. \ref{fig:polynom} +Werden es mehr Fehler kann nur erkannt werden, dass das Polynom nicht stimmt. +Das orginale Polynom kann aber nicht mehr gefunden werden. +Da andere Polynome oder das Konkurrenzpolynom, grau gestrichelt in Abbildung \ref{fig:polynom}, das orginal fehlleitet. +Um das Konkurrenzpolynom auszuschliessen, währen mehr \textcolor{darkgreen}{Übertragungspunkte} nötig. +\end{beispiel} + +\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} + +\section{Fehlerkorekturstellen bestimmen +\label{reedsolomon:section:Fehlerkorrekturstellen}} +Um zu bestimmen wieviel zusätzliche \textcolor{darkgreen}{Übertragungspunkte} notwendig sind, um die Fehler zu korrigieren, +muss man zuerst wissen, wieviel \textcolor{blue}{Daten} gesendet und wieviel \textcolor{red}{Fehler} erkennt werden sollen. +Die Anzahl \textcolor{blue}{Daten} (ab hier verwenden wir das Wort Nutzlast), die als Polynomkoeffizente $k$ übergeben werden, +brauchen die gleiche Anzahl an Polynomkoeffizententräger, beginnend bei Grad 0 somit ergibt sich der Polynomgrad mit $k-1$. +Für die Anzahl der Fehler $t$, welche korrigiert werden können, gehen wir zum Beispiel. +\begin{beispiel} von den Polynom \ref{reedsolomon:equation1} in, welchem wir \textcolor{darkgreen}{7 Übertragungspunkte} senden. +Durch 3 Punkte wird das Polyom eindeutig bestimmt, nun haben wir mehrere Konkurrenzpolynome, doch mit maximal 2 Fehler liegen auf einem Konkurrenzpolynom, +maximal 4 Punkte und auf unserem orginal 5 Punkte. Ansonsten hatt es mehr Fehler oder unser Konkurrenzpolynom ist das gleiche wie das Original. +Somit können wir nun bestimmen, dass von den \textcolor{darkgreen}{7 Übertragungspunkten$u$} bis zu 2 Fehler korrigiert werden können und 4 Übertragungspunkte zusätzlich gesendet werden müssen. +\end{beispiel} +Man könnte auch dies in der Tabelle \ref{tab:fehlerkorrekturstellen} erkennen, doch mit dieser Gleichung +\begin{equation} + \frac{\textcolor{darkgreen}{u}-\textcolor{blue}{k}}{\textcolor{red}{t}} + =2 + \label{reedsolomon:equation2} +\end{equation} +zeigt sich, dass es $k+2t$ Übertragungspunkte braucht. + +\begin{table} + \centering + \begin{tabular}{ c c | c} + \hline + Nutzlas & Fehler & Übertragen \\ + \hline + 3 & 2 & 7 Werte eines Polynoms vom Grad 2 \\ + 4 & 2 & 8 Werte eines Polynoms vom Grad 3 \\ + 3 & 3 & 9 Werte eines Polynoms vom Grad 2 \\ + \hline + $k$ & $t$ & $k+2t$ Werte eines Polynoms vom Grad $k-1$ \\ + \hline + \end{tabular} + \caption{ Fehlerkorrekturstellen Bestimmung.} + \label{tab:fehlerkorrekturstellen} +\end{table} + +Ein Nebeneffekt ist, dass dadurch auch $2t$ Fehler erkannt werden können, nicht aber korrigiert. +Um aus den übertragenen Zahlen wieder die Nutzlastzahlen zu bekommen könnte man eine Polynominterpolation anwenden, +doch die Punkte mit Polynominterpolation zu einem Polynom zu rekonstruieren ist schwierig und fehleranfällig. + diff --git a/buch/papers/reedsolomon/images/Compact_Disc.png b/buch/papers/reedsolomon/images/Compact_Disc.png Binary files differnew file mode 100644 index 0000000..7e3f870 --- /dev/null +++ b/buch/papers/reedsolomon/images/Compact_Disc.png diff --git a/buch/papers/reedsolomon/images/Compact_Disc_zoomed_in.png b/buch/papers/reedsolomon/images/Compact_Disc_zoomed_in.png Binary files differnew file mode 100644 index 0000000..69556d0 --- /dev/null +++ b/buch/papers/reedsolomon/images/Compact_Disc_zoomed_in.png diff --git a/buch/papers/reedsolomon/images/Voyager_Sonde.png b/buch/papers/reedsolomon/images/Voyager_Sonde.png Binary files differnew file mode 100644 index 0000000..e4dc400 --- /dev/null +++ b/buch/papers/reedsolomon/images/Voyager_Sonde.png diff --git a/buch/papers/reedsolomon/images/designer_qrcode.png b/buch/papers/reedsolomon/images/designer_qrcode.png Binary files differnew file mode 100644 index 0000000..a9e0505 --- /dev/null +++ b/buch/papers/reedsolomon/images/designer_qrcode.png diff --git a/buch/papers/reedsolomon/images/designer_qrcode_ohnelogo.png b/buch/papers/reedsolomon/images/designer_qrcode_ohnelogo.png Binary files differnew file mode 100644 index 0000000..fe4251d --- /dev/null +++ b/buch/papers/reedsolomon/images/designer_qrcode_ohnelogo.png diff --git a/buch/papers/reedsolomon/images/qrcode_h.png b/buch/papers/reedsolomon/images/qrcode_h.png Binary files differnew file mode 100644 index 0000000..4dc5779 --- /dev/null +++ b/buch/papers/reedsolomon/images/qrcode_h.png diff --git a/buch/papers/reedsolomon/images/qrcode_l.png b/buch/papers/reedsolomon/images/qrcode_l.png Binary files differnew file mode 100644 index 0000000..69f807f --- /dev/null +++ b/buch/papers/reedsolomon/images/qrcode_l.png diff --git a/buch/papers/reedsolomon/main.tex b/buch/papers/reedsolomon/main.tex index fa20936..017fe94 100644 --- a/buch/papers/reedsolomon/main.tex +++ b/buch/papers/reedsolomon/main.tex @@ -1,37 +1,17 @@ % % 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{Thema} +\lhead{Reed-Solomon-Code} \begin{refsection} \chapterauthor{Joshua Bär und Michael Steiner} -Ein paar Hinweise für die korrekte Formatierung des Textes -\begin{itemize} -\item -Absätze werden gebildet, indem man eine Leerzeile einfügt. -Die Verwendung von \verb+\\+ ist nur in Tabellen und Arrays gestattet. -\item -Die explizite Platzierung von Bildern ist nicht erlaubt, entsprechende -Optionen werden gelöscht. -Verwenden Sie Labels und Verweise, um auf Bilder hinzuweisen. -\item -Beginnen Sie jeden Satz auf einer neuen Zeile. -Damit ermöglichen Sie dem Versionsverwaltungssysteme, Änderungen -in verschiedenen Sätzen von verschiedenen Autoren ohne Konflikt -anzuwenden. -\item -Bilden Sie auch für Formeln kurze Zeilen, einerseits der besseren -Übersicht wegen, aber auch um GIT die Arbeit zu erleichtern. -\end{itemize} - % Joshua -\input{papers/reedsolomon/teil0.tex} -\input{papers/reedsolomon/teil1.tex} -\input{papers/reedsolomon/teil2.tex} -\input{papers/reedsolomon/teil3.tex} +\input{papers/reedsolomon/einleitung.tex} +\input{papers/reedsolomon/idee.tex} +\input{papers/reedsolomon/dtf.tex} % Michael \input{papers/reedsolomon/endlichekoerper} @@ -39,12 +19,19 @@ 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/zusammenfassung} +\input{papers/reedsolomon/anwendungen} \input{papers/reedsolomon/hilfstabellen} -%\input{papers/reedsolomon/anwendungen} -> geplant \nocite{reedsolomon:weitz} \nocite{reedsolomon:informationkommunikation} +\nocite{reedsolomon:voyager_programm} +\nocite{reedsolomon:voyager} +\nocite{reedsolomon:cd_wiki} +\nocite{reedsolomon:cd} +\nocite{reedsolomon:strichepunkte} +\nocite{reedsolomon:qr_wiki} +\nocite{reedsolomon:qr} %\nocite{reedsolomon:mendezmueller} \printbibliography[heading=subbibliography] 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/packages.tex b/buch/papers/reedsolomon/packages.tex index 3643731..40c6ea3 100644 --- a/buch/papers/reedsolomon/packages.tex +++ b/buch/papers/reedsolomon/packages.tex @@ -8,3 +8,7 @@ % following example %\usepackage{packagename} +\usepackage{pgfplots} +\usepackage{filecontents} +\usepackage{xr} + diff --git a/buch/papers/reedsolomon/references.bib b/buch/papers/reedsolomon/references.bib index 731bd35..b84b5a4 100644 --- a/buch/papers/reedsolomon/references.bib +++ b/buch/papers/reedsolomon/references.bib @@ -23,3 +23,65 @@ volume = {1} } +@online{reedsolomon:voyager_programm, + title = {Information über das Voyager Programm}, + url = {https://de.wikipedia.org/wiki/Voyager-Programm}, + date = {2021-07-19}, + year = {2021}, + month = {7}, + day = {19} +} + +@online{reedsolomon:voyager, + title = {Bild der Voyager Raumsonde}, + url = {https://en.wikipedia.org/wiki/Voyager_1}, + date = {2021-07-19}, + year = {2021}, + month = {7}, + day = {19} +} + +@online{reedsolomon:cd_wiki, + title = {Alles über die CD}, + url = {https://de.wikipedia.org/wiki/Compact_Disc}, + date = {2021-07-19}, + year = {2021}, + month = {7}, + day = {19} +} + +@online{reedsolomon:cd, + title = {Abbildung einer CD}, + url = {https://www.stickpng.com/img/electronics/compact-discs/stack-compact-disc}, + date = {2021-07-19}, + year = {2021}, + month = {7}, + day = {19} +} + +@online{reedsolomon:strichepunkte, + title = {Abbildung der Striche und Punkte einer CD}, + url = {https://www.researchgate.net/figure/The-readable-area-of-a-CD-is-magnified-in-order- to-see-the-pit-and-land-sizing-The_fig7_303401629}, + date = {2021-07-26}, + year = {2021}, + month = {7}, + day = {26} +} + +@online{reedsolomon:qr_wiki, + title = {Funktionsweise des QR-Codes}, + url = {https://de.wikipedia.org/wiki/QR-Code}, + date = {2021-07-19}, + year = {2021}, + month = {7}, + day = {19} +} + +@online{reedsolomon:qr, + title = {Tool zum erstellen von QR-Codes}, + url = {https://www.qrcode-generator.ch}, + date = {2021-07-19}, + year = {2021}, + month = {7}, + day = {19} +}
\ No newline at end of file diff --git a/buch/papers/reedsolomon/rekonstruktion.tex b/buch/papers/reedsolomon/rekonstruktion.tex index 89a700f..b099e68 100644 --- a/buch/papers/reedsolomon/rekonstruktion.tex +++ b/buch/papers/reedsolomon/rekonstruktion.tex @@ -1,13 +1,12 @@ % -% rekonstruktion.tex -% Autor: Michael Steiner +% rekonstruktion.tex -- Rekonstruktion % -% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil +% (c) 2021 Michael Steiner, Hochschule Rapperswil % -\section{Nachricht Rekonstruieren +\section{Nachricht rekonstruieren \label{reedsolomon:section:rekonstruktion}} -\rhead{Rekonstruktion} -Im letzten Kapitel haben wir eine Möglichkeit gefunden, wie wir die fehlerhaften Stellen lokalisieren können. +\rhead{Rekonstruktion der Nachricht} +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 +20,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 +46,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 weiteren 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. @@ -77,6 +77,7 @@ Daraus resultiert Die Matrix ist jedoch nicht mehr quadratisch, was eine Rekonstruktion durch Inversion ausschliesst. Um die quadratische Form wieder herzustellen müssen wir zwei Spalten aus der Matrix entfernen. Wir kennen aber das Resultat aus den letzten vier Spalten, da wir wissen, das die Nachricht aus Nutzdatenteil und Fehlerkorrekturteil besteht, wobei der letzteres bekanntlich aus lauter Nullstellen besteht. +Wir nehmen die markierten Spalten in \[ \begin{pmatrix} 5 \\ 3 \\ 6 \\ 2 \\ 10 \\ 2 \\ 7 \\ 4 \\ @@ -97,7 +98,7 @@ Wir kennen aber das Resultat aus den letzten vier Spalten, da wir wissen, das di m_0 \\ m_1 \\ m_2 \\ m_3 \\ m_4 \\ m_5 \\ \textcolor{darkgreen}{m_6} \\ \textcolor{darkgreen}{m_7} \\ \textcolor{darkgreen}{m_8} \\ \textcolor{darkgreen}{m_9} \\ \end{pmatrix} \] -Wir nehmen die entsprechenden Spalten aus der Matrix heraus und erhalten so das Überbestimmte Gleichungssystem +aus der Matrix heraus und erhalten so das Überbestimmte Gleichungssystem \[ \begin{pmatrix} 5 \\ 3 \\ 6 \\ 2 \\ 10 \\ 2 \\ \textcolor{red}{7} \\ \textcolor{red}{4} \\ @@ -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/restetabelle1.tex b/buch/papers/reedsolomon/restetabelle1.tex index 3969ef2..b9a0e59 100644 --- a/buch/papers/reedsolomon/restetabelle1.tex +++ b/buch/papers/reedsolomon/restetabelle1.tex @@ -1,6 +1,8 @@ -% created by Michael Steiner % -% Restetabelle von F_11: Addition +% restetabelle1.tex -- Restetabelle von F_11: Addition +% +% (c) 2021 Michael Steiner, Hochschule Rapperswil +% % alternatives design %\begin{figure} diff --git a/buch/papers/reedsolomon/restetabelle2.tex b/buch/papers/reedsolomon/restetabelle2.tex index 1a9815c..3b13ea2 100644 --- a/buch/papers/reedsolomon/restetabelle2.tex +++ b/buch/papers/reedsolomon/restetabelle2.tex @@ -1,6 +1,8 @@ -% created by Michael Steiner % -% Restetabelle von F_11: Multiplikation +% restetabelle2.tex -- Restetabelle von F_11: Multiplikation +% +% (c) 2021 Michael Steiner, Hochschule Rapperswil +% % alternatives design %\begin{figure} diff --git a/buch/papers/reedsolomon/standalone.tex b/buch/papers/reedsolomon/standalone.tex new file mode 100644 index 0000000..c850d1f --- /dev/null +++ b/buch/papers/reedsolomon/standalone.tex @@ -0,0 +1,30 @@ +\documentclass{book} + +\input{common/packages.tex} + +% additional packages used by the individual papers, add a line for +% each paper +\input{papers/common/addpackages.tex} + +% workaround for biblatex bug +\makeatletter +\def\blx@maxline{77} +\makeatother +\addbibresource{chapters/references.bib} + +% Bibresources for each article +\input{papers/common/addbibresources.tex} + +% make sure the last index starts on an odd page +\AtEndDocument{\clearpage\ifodd\value{page}\else\null\clearpage\fi} +\makeindex + +%\pgfplotsset{compat=1.12} +\setlength{\headheight}{15pt} % fix headheight warning +\DeclareGraphicsRule{*}{mps}{*}{} + +\begin{document} + \input{common/macros.tex} + \def\chapterauthor#1{{\large #1}\bigskip\bigskip} + \input{papers/reedsolomon/main.tex} +\end{document} diff --git a/buch/papers/reedsolomon/standalone/standalone.pdf b/buch/papers/reedsolomon/standalone/standalone.pdf Binary files differnew file mode 100644 index 0000000..4a44333 --- /dev/null +++ b/buch/papers/reedsolomon/standalone/standalone.pdf diff --git a/buch/papers/reedsolomon/teil0.tex b/buch/papers/reedsolomon/teil0.tex deleted file mode 100644 index b7ae971..0000000 --- a/buch/papers/reedsolomon/teil0.tex +++ /dev/null @@ -1,22 +0,0 @@ -% -% einleitung.tex -- Beispiel-File für die Einleitung -% -% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil -% -\section{Teil 0\label{reedsolomon:section:teil0}} -\rhead{Teil 0} -Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam -nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam -erat, sed diam voluptua \cite{reedsolomon:bibtex}. -At vero eos et accusam et justo duo dolores et ea rebum. -Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum -dolor sit amet. - -Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam -nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam -erat, sed diam voluptua. -At vero eos et accusam et justo duo dolores et ea rebum. Stet clita -kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit -amet. - - diff --git a/buch/papers/reedsolomon/teil1.tex b/buch/papers/reedsolomon/teil1.tex deleted file mode 100644 index 0aa9b41..0000000 --- a/buch/papers/reedsolomon/teil1.tex +++ /dev/null @@ -1,55 +0,0 @@ -% -% teil1.tex -- Beispiel-File für das Paper -% -% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil -% -\section{Teil 1 -\label{reedsolomon:section:teil1}} -\rhead{Problemstellung} -Sed ut perspiciatis unde omnis iste natus error sit voluptatem -accusantium doloremque laudantium, totam rem aperiam, eaque ipsa -quae ab illo inventore veritatis et quasi architecto beatae vitae -dicta sunt explicabo. -Nemo enim ipsam voluptatem quia voluptas sit aspernatur aut odit -aut fugit, sed quia consequuntur magni dolores eos qui ratione -voluptatem sequi nesciunt -\begin{equation} -\int_a^b x^2\, dx -= -\left[ \frac13 x^3 \right]_a^b -= -\frac{b^3-a^3}3. -\label{reedsolomon:equation1} -\end{equation} -Neque porro quisquam est, qui dolorem ipsum quia dolor sit amet, -consectetur, adipisci velit, sed quia non numquam eius modi tempora -incidunt ut labore et dolore magnam aliquam quaerat voluptatem. - -Ut enim ad minima veniam, quis nostrum exercitationem ullam corporis -suscipit laboriosam, nisi ut aliquid ex ea commodi consequatur? -Quis autem vel eum iure reprehenderit qui in ea voluptate velit -esse quam nihil molestiae consequatur, vel illum qui dolorem eum -fugiat quo voluptas nulla pariatur? - -\subsection{De finibus bonorum et malorum -\label{reedsolomon:subsection:finibus}} -At vero eos et accusamus et iusto odio dignissimos ducimus qui -blanditiis praesentium voluptatum deleniti atque corrupti quos -dolores et quas molestias excepturi sint occaecati cupiditate non -provident, similique sunt in culpa qui officia deserunt mollitia -animi, id est laborum et dolorum fuga \eqref{000tempmlate:equation1}. - -Et harum quidem rerum facilis est et expedita distinctio -\ref{reedsolomon:section:loesung}. -Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil -impedit quo minus id quod maxime placeat facere possimus, omnis -voluptas assumenda est, omnis dolor repellendus -\ref{reedsolomon:section:folgerung}. -Temporibus autem quibusdam et aut officiis debitis aut rerum -necessitatibus saepe eveniet ut et voluptates repudiandae sint et -molestiae non recusandae. -Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis -voluptatibus maiores alias consequatur aut perferendis doloribus -asperiores repellat. - - diff --git a/buch/papers/reedsolomon/teil2.tex b/buch/papers/reedsolomon/teil2.tex deleted file mode 100644 index b2adc9f..0000000 --- a/buch/papers/reedsolomon/teil2.tex +++ /dev/null @@ -1,40 +0,0 @@ -% -% teil2.tex -- Beispiel-File für teil2 -% -% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil -% -\section{Teil 2 -\label{reedsolomon:section:teil2}} -\rhead{Teil 2} -Sed ut perspiciatis unde omnis iste natus error sit voluptatem -accusantium doloremque laudantium, totam rem aperiam, eaque ipsa -quae ab illo inventore veritatis et quasi architecto beatae vitae -dicta sunt explicabo. Nemo enim ipsam voluptatem quia voluptas sit -aspernatur aut odit aut fugit, sed quia consequuntur magni dolores -eos qui ratione voluptatem sequi nesciunt. Neque porro quisquam -est, qui dolorem ipsum quia dolor sit amet, consectetur, adipisci -velit, sed quia non numquam eius modi tempora incidunt ut labore -et dolore magnam aliquam quaerat voluptatem. Ut enim ad minima -veniam, quis nostrum exercitationem ullam corporis suscipit laboriosam, -nisi ut aliquid ex ea commodi consequatur? Quis autem vel eum iure -reprehenderit qui in ea voluptate velit esse quam nihil molestiae -consequatur, vel illum qui dolorem eum fugiat quo voluptas nulla -pariatur? - -\subsection{De finibus bonorum et malorum -\label{reedsolomon:subsection:bonorum}} -At vero eos et accusamus et iusto odio dignissimos ducimus qui -blanditiis praesentium voluptatum deleniti atque corrupti quos -dolores et quas molestias excepturi sint occaecati cupiditate non -provident, similique sunt in culpa qui officia deserunt mollitia -animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis -est et expedita distinctio. Nam libero tempore, cum soluta nobis -est eligendi optio cumque nihil impedit quo minus id quod maxime -placeat facere possimus, omnis voluptas assumenda est, omnis dolor -repellendus. Temporibus autem quibusdam et aut officiis debitis aut -rerum necessitatibus saepe eveniet ut et voluptates repudiandae -sint et molestiae non recusandae. Itaque earum rerum hic tenetur a -sapiente delectus, ut aut reiciendis voluptatibus maiores alias -consequatur aut perferendis doloribus asperiores repellat. - - diff --git a/buch/papers/reedsolomon/teil3.tex b/buch/papers/reedsolomon/teil3.tex deleted file mode 100644 index 91a8d4e..0000000 --- a/buch/papers/reedsolomon/teil3.tex +++ /dev/null @@ -1,40 +0,0 @@ -% -% teil3.tex -- Beispiel-File für Teil 3 -% -% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil -% -\section{Teil 3 -\label{reedsolomon:section:teil3}} -\rhead{Teil 3} -Sed ut perspiciatis unde omnis iste natus error sit voluptatem -accusantium doloremque laudantium, totam rem aperiam, eaque ipsa -quae ab illo inventore veritatis et quasi architecto beatae vitae -dicta sunt explicabo. Nemo enim ipsam voluptatem quia voluptas sit -aspernatur aut odit aut fugit, sed quia consequuntur magni dolores -eos qui ratione voluptatem sequi nesciunt. Neque porro quisquam -est, qui dolorem ipsum quia dolor sit amet, consectetur, adipisci -velit, sed quia non numquam eius modi tempora incidunt ut labore -et dolore magnam aliquam quaerat voluptatem. Ut enim ad minima -veniam, quis nostrum exercitationem ullam corporis suscipit laboriosam, -nisi ut aliquid ex ea commodi consequatur? Quis autem vel eum iure -reprehenderit qui in ea voluptate velit esse quam nihil molestiae -consequatur, vel illum qui dolorem eum fugiat quo voluptas nulla -pariatur? - -\subsection{De finibus bonorum et malorum -\label{reedsolomon:subsection:malorum}} -At vero eos et accusamus et iusto odio dignissimos ducimus qui -blanditiis praesentium voluptatum deleniti atque corrupti quos -dolores et quas molestias excepturi sint occaecati cupiditate non -provident, similique sunt in culpa qui officia deserunt mollitia -animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis -est et expedita distinctio. Nam libero tempore, cum soluta nobis -est eligendi optio cumque nihil impedit quo minus id quod maxime -placeat facere possimus, omnis voluptas assumenda est, omnis dolor -repellendus. Temporibus autem quibusdam et aut officiis debitis aut -rerum necessitatibus saepe eveniet ut et voluptates repudiandae -sint et molestiae non recusandae. Itaque earum rerum hic tenetur a -sapiente delectus, ut aut reiciendis voluptatibus maiores alias -consequatur aut perferendis doloribus asperiores repellat. - - diff --git a/buch/papers/reedsolomon/tikz/codiert.txt b/buch/papers/reedsolomon/tikz/codiert.txt new file mode 100644 index 0000000..4a481d8 --- /dev/null +++ b/buch/papers/reedsolomon/tikz/codiert.txt @@ -0,0 +1,96 @@ +0,284 +1,131.570790435043 +2,41.9840308053375 +3,12.1189172092243 +4,23.8408857476069 +5,69.1793197789512 +6,24.0186013379153 +7,37.3066577242559 +8,18.2010889773887 +9,12.3214904922455 +10,15.6627133315015 +11,24.5237955316204 +12,32.1114345314062 +13,44.9845039238714 +14,13.5324640263625 +15,10.1736266929292 +16,4.58257569495584 +17,23.217268502288 +18,16.5769107917917 +19,6.89948680823017 +20,4.84567134895776 +21,10.4219666223433 +22,43.6179140616243 +23,35.9073375743642 +24,15.0332963783729 +25,21.7594021268945 +26,23.2496572716993 +27,17.9815599423852 +28,11.3577742151117 +29,38.467599433197 +30,28.3035029562577 +31,9.54321919833388 +32,21.377558326432 +33,17.6292439561917 +34,12.6951848921471 +35,20.0667752354841 +36,22.9097309529208 +37,8.78894645948548 +38,13.360682005498 +39,25.1757616314718 +40,38.0357773686457 +41,18.4633287776253 +42,19.0584505869806 +43,10.8631093309173 +44,12.6147770818983 +45,12.5398140021274 +46,34.901983501949 +47,22.3480442021702 +48,6 +49,22.3480442021702 +50,34.901983501949 +51,12.5398140021274 +52,12.6147770818983 +53,10.8631093309173 +54,19.0584505869806 +55,18.4633287776253 +56,38.0357773686457 +57,25.1757616314718 +58,13.360682005498 +59,8.78894645948548 +60,22.9097309529208 +61,20.0667752354841 +62,12.6951848921471 +63,17.6292439561917 +64,21.377558326432 +65,9.54321919833388 +66,28.3035029562577 +67,38.467599433197 +68,11.3577742151117 +69,17.9815599423852 +70,23.2496572716993 +71,21.7594021268945 +72,15.0332963783729 +73,35.9073375743642 +74,43.6179140616243 +75,10.4219666223433 +76,4.84567134895776 +77,6.89948680823017 +78,16.5769107917917 +79,23.217268502288 +80,4.58257569495584 +81,10.1736266929292 +82,13.5324640263625 +83,44.9845039238714 +84,32.1114345314062 +85,24.5237955316204 +86,15.6627133315015 +87,12.3214904922455 +88,18.2010889773887 +89,37.3066577242559 +90,24.0186013379153 +91,69.1793197789512 +92,23.8408857476069 +93,12.1189172092243 +94,41.9840308053375 +95,131.570790435043 diff --git a/buch/papers/reedsolomon/tikz/decodiert.txt b/buch/papers/reedsolomon/tikz/decodiert.txt new file mode 100644 index 0000000..f6221e6 --- /dev/null +++ b/buch/papers/reedsolomon/tikz/decodiert.txt @@ -0,0 +1,96 @@ +0,6.05208333333333 +1,6.02602539785853 +2,0.0261327016093151 +3,5.98927158561317 +4,4.019445724874 +5,0.0247005083663722 +6,4.97798278395618 +7,1.95246440445439 +8,0.974000110512201 +9,2.00528527696027 +10,1.00071804528155 +11,1.97630907888264 +12,0.0232923747656228 +13,6.01302820392331 +14,3.03567381915226 +15,5.02435590137329 +16,7.00526061008995 +17,5.00739608089369 +18,5.02211514480064 +19,4.02175864806658 +20,1.00236543833726 +21,4.98147315261261 +22,8.97728828610336 +23,8.98481304394618 +24,2.98958333333333 +25,1.98491220960989 +26,5.97728835934715 +27,5.98144124907561 +28,4.00163839998525 +29,2.02176249296313 +30,9.02210713874162 +31,1.00742763919872 +32,1.00557258081044 +33,1.02435888848794 +34,2.03577412756745 +35,6.01302820392331 +36,5.97917574041123 +37,0.976310374034338 +38,9.00062625447998 +39,7.00515849238528 +40,6.97396416790894 +41,0.95256880864368 +42,8.97794719866783 +43,9.01850701506487 +44,10.0194409579917 +45,8.98926601525997 +46,7.9866590265379 +47,5.02603060999077 +48,2.05208333333333 +49,4.02603841132848 +50,0.986882897867895 +51,0.0177592928994285 +52,9.01944131204563 +53,3.0185365665612 +54,2.97803642439316 +55,2.95243072164649 +56,4.97396651395488 +57,6.00516695947321 +58,0.0143895905726619 +59,7.97630812771393 +60,5.97917574041123 +61,9.01298821331865 +62,3.03567381915226 +63,4.02435609145793 +64,0.0275599094902563 +65,0.0115837187254191 +66,0.025877761014238 +67,0.0224618032819697 +68,0.04410594689944 +69,0.0474504002669341 +70,0.0227694695500626 +71,0.0271436638090525 +72,0.0104166666666667 +73,0.0271436638090523 +74,0.0227694695500608 +75,0.0474504002669343 +76,0.0441059468994397 +77,0.0224618032819701 +78,0.0258777610142379 +79,0.0115837187254183 +80,0.027559909490256 +81,0.0245124379481793 +82,0.0499782237195209 +83,0.0401432022864265 +84,0.0232923747656228 +85,0.0237974288564099 +86,0.0143895905726624 +87,0.0271745729691685 +88,0.0275599094902567 +89,0.0515501672184983 +90,0.0358255004834542 +91,0.024700508366373 +92,0.0210194725405171 +93,0.0177592928994296 +94,0.0261327016093158 +95,0.0314909067039411 diff --git a/buch/papers/reedsolomon/tikz/empfangen.txt b/buch/papers/reedsolomon/tikz/empfangen.txt new file mode 100644 index 0000000..38c13b0 --- /dev/null +++ b/buch/papers/reedsolomon/tikz/empfangen.txt @@ -0,0 +1,96 @@ +0,284 +1,131.570790435043 +2,41.9840308053375 +3,12.1189172092243 +4,23.8408857476069 +5,69.1793197789512 +6,23.6290258699579 +7,37.3066577242559 +8,18.2010889773887 +9,12.3214904922455 +10,15.6627133315015 +11,24.5237955316204 +12,32.1114345314062 +13,44.9845039238714 +14,13.5324640263625 +15,10.1736266929292 +16,4.58257569495584 +17,23.217268502288 +18,16.5769107917917 +19,6.89948680823017 +20,5.55320238736303 +21,10.4219666223433 +22,43.6179140616243 +23,35.9073375743642 +24,15.0332963783729 +25,21.7594021268945 +26,23.2496572716993 +27,17.9815599423852 +28,11.3577742151117 +29,38.467599433197 +30,28.3035029562577 +31,9.54321919833388 +32,21.377558326432 +33,17.6292439561917 +34,12.6951848921471 +35,20.0667752354841 +36,22.9097309529208 +37,8.78894645948548 +38,13.360682005498 +39,25.1757616314718 +40,38.0357773686457 +41,18.4633287776253 +42,19.0584505869806 +43,10.8631093309173 +44,12.6147770818983 +45,12.5398140021274 +46,34.901983501949 +47,22.3480442021702 +48,6 +49,22.3480442021702 +50,34.901983501949 +51,12.5398140021274 +52,12.6147770818983 +53,10.8631093309173 +54,19.0584505869806 +55,18.4633287776253 +56,38.0357773686457 +57,25.1757616314718 +58,13.360682005498 +59,8.78894645948548 +60,22.9097309529208 +61,20.0667752354841 +62,12.6951848921471 +63,17.6292439561917 +64,21.377558326432 +65,9.54321919833388 +66,28.3035029562577 +67,38.467599433197 +68,11.3577742151117 +69,17.9815599423852 +70,23.2496572716993 +71,21.7594021268945 +72,15.0332963783729 +73,35.9073375743642 +74,44.6135417384784 +75,10.4219666223433 +76,4.84567134895776 +77,6.89948680823017 +78,16.5769107917917 +79,23.217268502288 +80,4.58257569495584 +81,10.1736266929292 +82,13.5324640263625 +83,44.9845039238714 +84,32.1114345314062 +85,24.5237955316204 +86,15.6627133315015 +87,12.3214904922455 +88,18.2010889773887 +89,37.3066577242559 +90,24.0186013379153 +91,69.1793197789512 +92,23.8408857476069 +93,12.1189172092243 +94,41.9840308053375 +95,131.570790435043 diff --git a/buch/papers/reedsolomon/tikz/fehler.txt b/buch/papers/reedsolomon/tikz/fehler.txt new file mode 100644 index 0000000..23f1a83 --- /dev/null +++ b/buch/papers/reedsolomon/tikz/fehler.txt @@ -0,0 +1,96 @@ +0,0 +1,0 +2,0 +3,0 +4,0 +5,0 +6,2 +7,0 +8,0 +9,0 +10,0 +11,0 +12,0 +13,0 +14,0 +15,0 +16,0 +17,0 +18,0 +19,0 +20,2 +21,0 +22,0 +23,0 +24,0 +25,0 +26,0 +27,0 +28,0 +29,0 +30,0 +31,0 +32,0 +33,0 +34,0 +35,0 +36,0 +37,0 +38,0 +39,0 +40,0 +41,0 +42,0 +43,0 +44,0 +45,0 +46,0 +47,0 +48,0 +49,0 +50,0 +51,0 +52,0 +53,0 +54,0 +55,0 +56,0 +57,0 +58,0 +59,0 +60,0 +61,0 +62,0 +63,0 +64,0 +65,0 +66,0 +67,0 +68,0 +69,0 +70,0 +71,0 +72,0 +73,0 +74,1 +75,0 +76,0 +77,0 +78,0 +79,0 +80,0 +81,0 +82,0 +83,0 +84,0 +85,0 +86,0 +87,0 +88,0 +89,0 +90,0 +91,0 +92,0 +93,0 +94,0 +95,0 diff --git a/buch/papers/reedsolomon/tikz/locator.txt b/buch/papers/reedsolomon/tikz/locator.txt new file mode 100644 index 0000000..b28988c --- /dev/null +++ b/buch/papers/reedsolomon/tikz/locator.txt @@ -0,0 +1,96 @@ +0,0.0301224340567056 +1,0.141653026854885 +2,0.138226631799377 +3,0.0339903276086929 +4,0.310585462557496 +5,0.551427312631385 +6,0.628514858396814 +7,0.51102386251559 +8,0.275861355940449 +9,0.0502396354182268 +10,0.090185502547573 +11,0.110759344849756 +12,0.0684618905063001 +13,0.0362855426992259 +14,0.0697096919781468 +15,0.109288539370248 +16,0.0923187999496653 +17,0.0512198536768088 +18,0.274192386987782 +19,0.51349614953654 +20,0.633154426602466 +21,0.553283743533942 +22,0.307840573214514 +23,0.0341664350328392 +24,0.140270857957 +25,0.138527177682831 +26,0.029637547736156 +27,0.0816962563186052 +28,0.0944383203811073 +29,0.0263932110686261 +30,0.0585881348402056 +31,0.0737117341599984 +32,0.0239973937701886 +33,0.0464215468420038 +34,0.0616218854220964 +35,0.0221963086695009 +36,0.0390764778127646 +37,0.0537637218396934 +38,0.0208333333333332 +39,0.0343107696069045 +40,0.0483441215964552 +41,0.0198077862118806 +42,0.0311207395968725 +43,0.0444955089373458 +44,0.0190533549944159 +45,0.0290049795038723 +46,0.0417536642697558 +47,0.0185261550443084 +48,0.0277059929762261 +49,0.0398606084144816 +50,0.0181978813094817 +51,0.0271098219177584 +52,0.0386836665079729 +53,0.0180518611046889 +54,0.0272138992557141 +55,0.0381891287148314 +56,0.0180809085252469 +57,0.0281418959420061 +58,0.0384596362516637 +59,0.0182864418432272 +60,0.0302250788423173 +61,0.0397874837986351 +62,0.0186786556701694 +63,0.0342489348284216 +64,0.0429932815348666 +65,0.0192777878591759 +66,0.0422808966931999 +67,0.0506815964680563 +68,0.0201167847752226 +69,0.0615048274405271 +70,0.0744953894508454 +71,0.021246054596492 +72,0.142602265816215 +73,0.273502052865436 +74,0.325309673287599 +75,0.272705389655349 +76,0.149074257381345 +77,0.0247199397628712 +78,0.0680137859566976 +79,0.075388270873485 +80,0.0273637831604903 +81,0.0407867704453274 +82,0.0632964886441949 +83,0.0309749128751093 +84,0.0315202035072035 +85,0.0627625211892184 +86,0.0360843918243497 +87,0.02794920551495 +88,0.0677921493367236 +89,0.0437167157553067 +90,0.0270640150996317 +91,0.0783380025231622 +92,0.0561293738314281 +93,0.0278742033265809 +94,0.0981443889498639 +95,0.0794543457386548 diff --git a/buch/papers/reedsolomon/tikz/plotfft.tex b/buch/papers/reedsolomon/tikz/plotfft.tex new file mode 100644 index 0000000..bb74dfb --- /dev/null +++ b/buch/papers/reedsolomon/tikz/plotfft.tex @@ -0,0 +1,94 @@ +% +% Plot der Übertrangungsabfolge ins FFT und zurück mit IFFT +% +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{times} +\usepackage{pgfplots} +\usepackage{pgfplotstable} +\usepackage{csvsimple} +\usepackage{filecontents} + + +\begin{document} +\begin{tikzpicture}[] + + %--------------------------------------------------------------- + %Knote + \matrix(m) [draw = none, column sep=25mm, row sep=2mm]{ + + \node(signal) [] { + \begin{tikzpicture} + \begin{axis} + [title = {\Large {Signal}}, + xtick={0,20,40,64,80,98}] + \addplot[blue] table[col sep=comma] {tikz/signal.txt}; + \end{axis} + \end{tikzpicture}}; & + + \node(codiert) [] { + \begin{tikzpicture}[] + \begin{axis}[ title = {\Large {Codiert \space + \space Fehler}}, + xtick={0,40,60,100}, axis y line*=left] + \addplot[green] table[col sep=comma] {tikz/codiert.txt}; + \end{axis} + \begin{axis}[xtick={7,21,75}, axis y line*=right] + \addplot[red] table[col sep=comma] {tikz/fehler.txt}; + \end{axis} + \end{tikzpicture}}; \\ + + \node(decodiert) [] { + \begin{tikzpicture} + \begin{axis}[title = {\Large {Decodiert}}] + \addplot[blue] table[col sep=comma] {tikz/decodiert.txt}; + \end{axis} + \end{tikzpicture}}; & + + \node(empfangen) [] { + \begin{tikzpicture} + \begin{axis}[title = {\Large {Empfangen}}] + \addplot[green] table[col sep=comma] {tikz/empfangen.txt}; + \end{axis} + \end{tikzpicture}};\\ + + \node(syndrom) [] { + \begin{tikzpicture} + \begin{axis}[title = {\Large {Syndrom}}] + \addplot[black] table[col sep=comma] {tikz/syndrom.txt}; + \end{axis} + \end{tikzpicture}}; & + + \node(locator) [] { + \begin{tikzpicture} + \begin{axis}[title = {\Large {Locator}}] + \addplot[gray] table[col sep=comma] {tikz/locator.txt}; + \end{axis} + \end{tikzpicture}};\\ + }; + %------------------------------------------------------------- + %FFT & IFFT deskription + + \draw[thin,gray,dashed] (0,9) to (0,-9); + \node(IFFT) [scale=0.9] at (0,9.3) {IFFT}; + \draw[stealth-](IFFT.south west)--(IFFT.south east); + \node(FFT) [scale=0.9, above of=IFFT] {FFT}; + \draw[-stealth](FFT.north west)--(FFT.north east); + + \draw[thick, ->,] (codiert)++(-1,0) +(0.05,0.5) -- +(-0.1,-0.1) -- +(0.1,0.1) -- +(0,-0.5); + %Arrows + \draw[thick, ->] (signal.east) to (codiert.west); + \draw[thick, ->] (codiert.south) to (empfangen.north); + \draw[thick, ->] (empfangen.west) to (decodiert.east); + \draw[thick, ->] (syndrom.east) to (locator.west); + \draw[thick](decodiert.south east)++(-1.8,1) ellipse (1.3cm and 0.8cm) ++(-1.3,0) coordinate(zoom) ; + \draw[thick, ->] (zoom) to[out=180, in=90] (syndrom.north); + + %item + \node[circle, draw, fill =lightgray] at (signal.north west) {1}; + \node[circle, draw, fill =lightgray] at (codiert.north west) {2+3}; + \node[circle, draw, fill =lightgray] at (empfangen.north west) {4}; + \node[circle, draw, fill =lightgray] at (decodiert.north west) {5}; + \node[circle, draw, fill =lightgray] at (syndrom.north west) {6}; + \node[circle, draw, fill =lightgray] at (locator.north west) {7}; +\end{tikzpicture} +\end{document}
\ No newline at end of file diff --git a/buch/papers/reedsolomon/tikz/plotfftraw.tex b/buch/papers/reedsolomon/tikz/plotfftraw.tex new file mode 100644 index 0000000..141d2ce --- /dev/null +++ b/buch/papers/reedsolomon/tikz/plotfftraw.tex @@ -0,0 +1,80 @@ +\begin{tikzpicture}[] + + %--------------------------------------------------------------- + %Knote + \matrix(m) [draw = none, column sep=25mm, row sep=2mm]{ + + \node(signal) [] { + \begin{tikzpicture} + \begin{axis} + [title = {\Large {Signal}}, + xtick={0,20,40,64,80,98}] + \addplot[blue] table[col sep=comma] {tikz/signal.txt}; + \end{axis} + \end{tikzpicture}}; & + + \node(codiert) [] { + \begin{tikzpicture}[] + \begin{axis}[ title = {\Large {Codiert \space + \space Fehler}}, + xtick={0,40,60,100}, axis y line*=left] + \addplot[green] table[col sep=comma] {tikz/codiert.txt}; + \end{axis} + \begin{axis}[xtick={7,21,75}, axis y line*=right] + \addplot[red] table[col sep=comma] {tikz/fehler.txt}; + \end{axis} + \end{tikzpicture}}; \\ + + \node(decodiert) [] { + \begin{tikzpicture} + \begin{axis}[title = {\Large {Decodiert}}] + \addplot[blue] table[col sep=comma] {tikz/decodiert.txt}; + \end{axis} + \end{tikzpicture}}; & + + \node(empfangen) [] { + \begin{tikzpicture} + \begin{axis}[title = {\Large {Empfangen}}] + \addplot[green] table[col sep=comma] {tikz/empfangen.txt}; + \end{axis} + \end{tikzpicture}};\\ + + \node(syndrom) [] { + \begin{tikzpicture} + \begin{axis}[title = {\Large {Syndrom}}] + \addplot[black] table[col sep=comma] {tikz/syndrom.txt}; + \end{axis} + \end{tikzpicture}}; & + + \node(locator) [] { + \begin{tikzpicture} + \begin{axis}[title = {\Large {Locator}}] + \addplot[gray] table[col sep=comma] {tikz/locator.txt}; + \end{axis} + \end{tikzpicture}};\\ + }; + %------------------------------------------------------------- + %FFT & IFFT deskription + + \draw[thin,gray,dashed] (0,9) to (0,-9); + \node(IFFT) [scale=0.9] at (0,9.3) {IFFT}; + \draw[stealth-](IFFT.south west)--(IFFT.south east); + \node(FFT) [scale=0.9, above of=IFFT] {FFT}; + \draw[-stealth](FFT.north west)--(FFT.north east); + + \draw[thick, ->,] (codiert)++(-1,0) +(0.05,0.5) -- +(-0.1,-0.1) -- +(0.1,0.1) -- +(0,-0.5); + %Arrows + \draw[thick, ->] (signal.east) to (codiert.west); + \draw[thick, ->] (codiert.south) to (empfangen.north); + \draw[thick, ->] (empfangen.west) to (decodiert.east); + \draw[thick, ->] (syndrom.east) to (locator.west); + \draw[thick](decodiert.south east)++(-1.8,1) ellipse (1.3cm and 0.8cm) ++(-1.3,0) coordinate(zoom) ; + \draw[thick, ->] (zoom) to[out=180, in=90] (syndrom.north); + + %item + \node[circle, draw, fill =lightgray] at (signal.north west) {1}; + \node[circle, draw, fill =lightgray] at (codiert.north west) {2+3}; + \node[circle, draw, fill =lightgray] at (empfangen.north west) {4}; + \node[circle, draw, fill =lightgray] at (decodiert.north west) {5}; + \node[circle, draw, fill =lightgray] at (syndrom.north west) {6}; + \node[circle, draw, fill =lightgray] at (locator.north west) {7}; +\end{tikzpicture}
\ No newline at end of file diff --git a/buch/papers/reedsolomon/tikz/polynom2.tex b/buch/papers/reedsolomon/tikz/polynom2.tex new file mode 100644 index 0000000..80557fb --- /dev/null +++ b/buch/papers/reedsolomon/tikz/polynom2.tex @@ -0,0 +1,60 @@ +% polynome +%------------------- + +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{times} +\usepackage{pgfplots} + + +\begin{document} +% Teiler für das Skalieren der Grafik /40 +\newcommand{\teiler}{40} + + +%////////////////////////////////////// + +\begin{tikzpicture}[>=latex,thick,] + \draw[color=blue, line width=1.4pt] + plot[domain=0:8, samples=100] + ({\x},{(2*\x^2+1*\x+5)/\teiler}); + + \draw[->] (-0.2,0) -- (8,0) coordinate[label={$x$}]; + \draw[->] (0,-0.2) -- (0,150/\teiler) coordinate[label={right:$p(x)$}]; + + \def\punkt#1{ + \fill[color=green] #1 circle[radius=0.08]; + \draw #1 circle[radius=0.07]; + } + + \def\hellpunkt#1{ + \fill[color=lightgray] #1 circle[radius=0.08]; + \draw[gray] #1 circle[ radius=0.07]; + } + + \draw[color=gray,line width=1pt,dashed] + plot[domain=0.5:7, samples=100] + ({\x},{(7.832*\x^2-51.5*\x+121.668)/\teiler}); + + + \punkt{(1,8/\teiler)} + \hellpunkt{(2,15/\teiler)} + \hellpunkt{(3,26/\teiler)} + \punkt{(4,41/\teiler)} + \punkt{(5,60/\teiler)} + \punkt{(6,83/\teiler)} + \punkt{(7,110/\teiler)} + + + + \def\erpunkt#1{ + \fill[color=red] #1 circle[radius=0.08]; + \draw #1 circle[radius=0.07]; + } + \erpunkt{(2,50/\teiler)} + \erpunkt{(3,37.66/\teiler)} + + \draw(0,100/\teiler) -- (-0.1,100/\teiler) coordinate[label={left:$100$}]; + \draw(1,0) -- (1,-0.1) coordinate[label={below:$1$}]; +\end{tikzpicture} +\end{document} diff --git a/buch/papers/reedsolomon/tikz/polynomraw.tex b/buch/papers/reedsolomon/tikz/polynomraw.tex new file mode 100644 index 0000000..02968fd --- /dev/null +++ b/buch/papers/reedsolomon/tikz/polynomraw.tex @@ -0,0 +1,50 @@ +% polynomraw + +\newcommand{\teiler}{40} + + +%////////////////////////////////////// + +\begin{tikzpicture}[>=latex,thick,] + \draw[color=blue, line width=1.4pt] + plot[domain=0:8, samples=100] + ({\x},{(2*\x^2+1*\x+5)/\teiler}); + + \draw[->] (-0.2,0) -- (8,0) coordinate[label={$x$}]; + \draw[->] (0,-0.2) -- (0,150/\teiler) coordinate[label={right:$p(x)$}]; + + \def\punkt#1{ + \fill[color=green] #1 circle[radius=0.08]; + \draw #1 circle[radius=0.07]; + } + + \def\hellpunkt#1{ + \fill[color=lightgray] #1 circle[radius=0.08]; + \draw[gray] #1 circle[ radius=0.07]; + } + + \draw[color=gray,line width=1pt,dashed] + plot[domain=0.5:7, samples=100] + ({\x},{(7.832*\x^2-51.5*\x+121.668)/\teiler}); + + + \punkt{(1,8/\teiler)} + \hellpunkt{(2,15/\teiler)} + \hellpunkt{(3,26/\teiler)} + \punkt{(4,41/\teiler)} + \punkt{(5,60/\teiler)} + \punkt{(6,83/\teiler)} + \punkt{(7,110/\teiler)} + + + + \def\erpunkt#1{ + \fill[color=red] #1 circle[radius=0.08]; + \draw #1 circle[radius=0.07]; + } + \erpunkt{(2,50/\teiler)} + \erpunkt{(3,37.66/\teiler)} + + \draw(0,100/\teiler) -- (-0.1,100/\teiler) coordinate[label={left:$100$}]; + \draw(1,0) -- (1,-0.1) coordinate[label={below:$1$}]; +\end{tikzpicture}
\ No newline at end of file diff --git a/buch/papers/reedsolomon/tikz/signal.txt b/buch/papers/reedsolomon/tikz/signal.txt new file mode 100644 index 0000000..c4fa5f8 --- /dev/null +++ b/buch/papers/reedsolomon/tikz/signal.txt @@ -0,0 +1,96 @@ +0,6 +1,6 +2,0 +3,6 +4,4 +5,0 +6,5 +7,2 +8,1 +9,2 +10,1 +11,2 +12,0 +13,6 +14,3 +15,5 +16,7 +17,5 +18,5 +19,4 +20,1 +21,5 +22,9 +23,9 +24,3 +25,2 +26,6 +27,6 +28,4 +29,2 +30,9 +31,1 +32,1 +33,1 +34,2 +35,6 +36,6 +37,1 +38,9 +39,7 +40,7 +41,1 +42,9 +43,9 +44,10 +45,9 +46,8 +47,5 +48,2 +49,4 +50,1 +51,0 +52,9 +53,3 +54,3 +55,3 +56,5 +57,6 +58,0 +59,8 +60,6 +61,9 +62,3 +63,4 +64,0 +65,0 +66,0 +67,0 +68,0 +69,0 +70,0 +71,0 +72,0 +73,0 +74,0 +75,0 +76,0 +77,0 +78,0 +79,0 +80,0 +81,0 +82,0 +83,0 +84,0 +85,0 +86,0 +87,0 +88,0 +89,0 +90,0 +91,0 +92,0 +93,0 +94,0 +95,0 diff --git a/buch/papers/reedsolomon/tikz/syndrom.txt b/buch/papers/reedsolomon/tikz/syndrom.txt new file mode 100644 index 0000000..8ca9eed --- /dev/null +++ b/buch/papers/reedsolomon/tikz/syndrom.txt @@ -0,0 +1,96 @@ +0,0 +1,0 +2,0 +3,0 +4,0 +5,0 +6,0 +7,0 +8,0 +9,0 +10,0 +11,0 +12,0 +13,0 +14,0 +15,0 +16,0 +17,0 +18,0 +19,0 +20,0 +21,0 +22,0 +23,0 +24,0 +25,0 +26,0 +27,0 +28,0 +29,0 +30,0 +31,0 +32,0 +33,0 +34,0 +35,0 +36,0 +37,0 +38,0 +39,0 +40,0 +41,0 +42,0 +43,0 +44,0 +45,0 +46,0 +47,0 +48,0 +49,0 +50,0 +51,0 +52,0 +53,0 +54,0 +55,0 +56,0 +57,0 +58,0 +59,0 +60,0 +61,0 +62,0 +63,0 +64,0.0275599094902563 +65,0.0115837187254191 +66,0.025877761014238 +67,0.0224618032819697 +68,0.04410594689944 +69,0.0474504002669341 +70,0.0227694695500626 +71,0.0271436638090525 +72,0.0104166666666667 +73,0.0271436638090523 +74,0.0227694695500608 +75,0.0474504002669343 +76,0.0441059468994397 +77,0.0224618032819701 +78,0.0258777610142379 +79,0.0115837187254183 +80,0.027559909490256 +81,0.0245124379481793 +82,0.0499782237195209 +83,0.0401432022864265 +84,0.0232923747656228 +85,0.0237974288564099 +86,0.0143895905726624 +87,0.0271745729691685 +88,0.0275599094902567 +89,0.0515501672184983 +90,0.0358255004834542 +91,0.024700508366373 +92,0.0210194725405171 +93,0.0177592928994296 +94,0.0261327016093158 +95,0.0314909067039411 diff --git a/buch/papers/reedsolomon/zusammenfassung.tex b/buch/papers/reedsolomon/zusammenfassung.tex new file mode 100644 index 0000000..c24fcf3 --- /dev/null +++ b/buch/papers/reedsolomon/zusammenfassung.tex @@ -0,0 +1,66 @@ +% +% zusammenfassung.tex -- Zusammenfassung +% +% (c) 2021 Michael Steiner, Hochschule Rapperswil +% +\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. + +\subsubsection{Schritt 1: primitives Element} +Zu Beginn soll entschieden werden, in welchem endlichen Körper $\mathbb{F}_{q}$ gerechnet werden soll. +Ausserdem muss im gewählten Körper eine primitive Einheitswurzel gefunden, bzw. bestimmt werden. + +\subsubsection{Schritt 2: Codierung} +Für die Codierung wird die Nachricht als Koeffizienten des Polynoms $m(X)$ geschrieben, anschliessend wird $a^i$ in $m(X)$ eingesetzt. +Daraus ergibt sich die Codierungsmatrix +\[ +A(a) = +\begin{pmatrix} +a^0 & a^0 & a^0 & \dots \\ +a^0 & a^1 & a^2 & \dots \\ +a^0 & a^2 & a^4 & \dots \\ +\vdots&\vdots&\vdots&\ddots +\end{pmatrix} +. +\] +Mit dieser Matrix können wir den Nachrichtenblock zum Übertragungsvektor codieren. + +\subsubsection{Schritt 3: Decodierung ohne Fehler} +Im ersten Schritt zur Decodierung muss geprüft werden, ob der Übertragungsvektor Fehler beinhaltet. +Ist dies nicht der Fall, so kann die Matrix $A(a)$ invertiert werden mit +\[ +A(a)^{-1} = \frac{1}{q-1} \cdot A(a^{-1}). +\] +Die Codierungsmatrix ändert sich somit zur Decodierungsmatrix +\[ +\begin{pmatrix} + a^0 & a^0 & a^0 & \dots \\ + a^0 & a^1 & a^2 & \dots \\ + a^0 & a^2 & a^4 & \dots \\ + \vdots&\vdots&\vdots &\ddots +\end{pmatrix} += +\frac{1}{q-1} +\cdot +\begin{pmatrix} + a^0 & a^0 & a^0 & \dots \\ + a^0 & a^{-1} & a^{-2} & \dots \\ + a^0 & a^{-2} & a^{-4} & \dots \\ + \vdots&\vdots&\vdots&\ddots +\end{pmatrix} +. +\] +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. +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. +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. +%Dazu nehmen wir das Polynom $f(X)$, welches wir durch den Satz von Fermat erhalten, und berechnen so das $\operatorname{kgV}(f(X),d(X))$ und kommen so auf das Lokatorpolynom $l(X)$. Durch das bestimmen von den Exponenten erhalten wir die Fehlerstellen, welche wir aus dem Gleichungssystem entfernen müssen. Übrig bleibt das berechnen dieses Gleichungssystems. |
