diff options
Diffstat (limited to '')
-rw-r--r-- | buch/papers/mceliece/aufbau.tex | 11 | ||||
-rw-r--r-- | buch/papers/mceliece/fazit.tex | 6 | ||||
-rw-r--r-- | buch/papers/mceliece/funktionsweise.tex | 4 | ||||
-rw-r--r-- | buch/papers/mceliece/references.bib | 8 | ||||
-rw-r--r-- | buch/papers/punktgruppen/crystals.tex | 2 | ||||
-rw-r--r-- | buch/papers/reedsolomon/dtf.tex | 40 | ||||
-rw-r--r-- | buch/papers/reedsolomon/einleitung.tex | 8 | ||||
-rw-r--r-- | buch/papers/reedsolomon/idee.tex | 135 |
8 files changed, 131 insertions, 83 deletions
diff --git a/buch/papers/mceliece/aufbau.tex b/buch/papers/mceliece/aufbau.tex index 521488d..200cb7b 100644 --- a/buch/papers/mceliece/aufbau.tex +++ b/buch/papers/mceliece/aufbau.tex @@ -10,7 +10,8 @@ Das McEliece-Kryptosystem besteht aus folgenden Elementen: \subsection{Datenvektor $d_k$ \label{mceliece:subsection:d_k}} In diesem Vektor der Länge $k$ sind die zu verschlüsselnden Daten enthalten. -Beispielsweise + +Beispiel: \[d_4= \begin{pmatrix} 1\\ @@ -25,7 +26,7 @@ Beispielsweise $S_k$ ist eine Binäre Zufallsmatrix der Grösse $k \times k$. Auch muss diese Matrix in $\mathbb{F}_2$ invertierbar sein. Für kleine Matrizen kann durchaus jedes Matrizenelement zufällig generiert werden, -wobei danach mithilfe des Gauss-Algorythmusses deren Inverse bestimmt werden kann. +wobei danach mithilfe des Gauss-Algorithmus deren Inverse bestimmt werden kann. Da eine solche Matrix möglicherweise singulär ist, muss in diesem Fall eine neue Zufallsmatrix erzeugt werden. Für grössere Matrizen existieren bessere Methoden, auf welche hier nicht weiter eingegangen wird \cite{mceliece:GenerationRandMatrix}. @@ -53,9 +54,9 @@ Beispiel: \label{mceliece:subsection:g_nk}} Das wichtigste Element des McEliece-Systems ist ein fehlerkorrigierender Code, der in der Lage ist, $t$ Fehler zu korrigieren. -Im Zusammenhang mit McEliece werden dabei meist Goppa-Codes verwendet, -es können prinzipiell auch andere Codes wie beispielsweise Reed-Solomin verwendet werden, -jedoch besitzen einige Codes Schwachstellen \cite{mceliece:lorenz}. +Im Zusammenhang mit McEliece werden dabei meist binäre Goppa-Codes \cite{mceliece:goppa} verwendet, +es können prinzipiell auch andere Codes wie beispielsweise Reed-Solomon verwendet werden, +jedoch besitzen einige (unter anderem auch Reed-Solomon) Codes Schwachstellen \cite{mceliece:lorenz}. Das Codieren mit diesem linearen Code kann mithilfe dessen Generatormatrix $G_{n,k}$ erfolgen. Da es sich um einen fehlerkorrigierenden Code handelt, wird das Codewort länger als das Datenwort, diff --git a/buch/papers/mceliece/fazit.tex b/buch/papers/mceliece/fazit.tex index d618993..186708b 100644 --- a/buch/papers/mceliece/fazit.tex +++ b/buch/papers/mceliece/fazit.tex @@ -35,12 +35,12 @@ Grosse unterschiede zwischen den beiden Kryptosystemen gibt es jedoch bei der Si Der Kern der RSA-Verschlüsselung beruht auf dem Problem, eine grosse Zahl in ihre beiden Primfaktoren zu zerlegen. Bei genügend grossen Zahlen ist diese Zerlegung auch mit den heute besten verfügbaren Computern kaum innerhalb vernünftiger Zeit zu lösen. Weiter ist aber bekannt, -dass mithilfe des sogenannten Shor-Algorithmuses \cite{mceliece:shor} und einem Quantencomputer auch diese Zerlegung zügig realisiert werden könnte, +dass mithilfe des sogenannten Shor-Algorithmus \cite{mceliece:shor} und einem Quantencomputer auch diese Zerlegung zügig realisiert werden könnte, was zur Folge hätte, dass die Verschlüsselung von RSA unwirksam würde. Zurzeit sind die Quantencomputer jedoch noch bei weitem nicht in der Lage, grosse Zahlen mithilfe dieses Algorithmuses zu zerlegen. -Das McEliece-System hingegen beruht auf dem Problem des ``Syndrome decoding'' (Korrektur von Bitfehlern eines Codewortes, das mit dem entsprechenden Linearcode codiert wurde). +Das McEliece-System hingegen beruht auf dem Problem des ``Syndrome decoding'' (Korrektur von Bitfehlern eines Codewortes, das mit einem entsprechenden Linearcode codiert wurde). Für das ``Syndrome decoding'' sind bis heute keine Methoden bekannt, -welche nennenswerte Vorteile gegenüber dem durchprobieren (brute-force) bringen, +welche nennenswerte Vorteile gegenüber dem Durchprobieren (brute-force) bringen, auch nicht mithilfe eines Quantencomputers. \begin{center} \begin{tabular}{c|c|c} diff --git a/buch/papers/mceliece/funktionsweise.tex b/buch/papers/mceliece/funktionsweise.tex index 93bb1c7..7c69b13 100644 --- a/buch/papers/mceliece/funktionsweise.tex +++ b/buch/papers/mceliece/funktionsweise.tex @@ -18,7 +18,7 @@ Dazu erstellt sie die einzelnen Matrizen $S_k$, $G_{n,k}$ und $P_n$. Diese drei einzelnen Matrizen bilden den privaten Schlüssel von Alice und sollen geheim bleiben. Der öffentliche Schlüssel $K_{n,k}$ hingegen berechnet sich -aus der Multiplikation der privaten Matrizen\ref{mceliece:subsection:k_nk} +aus der Multiplikation der privaten Matrizen (Abschnitt \ref{mceliece:subsection:k_nk}) und wird anschliessend Bob zugestellt. \subsection{Verschlüsselung @@ -61,7 +61,7 @@ können nun die Bitfehler, verursacht durch den Fehlervektor $e'_n$, entfernt werden. Da es sich bei diesem Schritt nicht um eine einfache Matrixmultiplikation handelt, wird die Operation durch eine Funktion dargestellt. -Wie dieser Decoder genau aufgebaut ist ist, +Wie dieser Decoder genau aufgebaut ist, hängt vom verwendeten Linearcode ab. \begin{align*} c_{k}'\,&=\text{Linear-Code-Decoder($c''_n$)}\\ diff --git a/buch/papers/mceliece/references.bib b/buch/papers/mceliece/references.bib index 52aa166..0388ff4 100644 --- a/buch/papers/mceliece/references.bib +++ b/buch/papers/mceliece/references.bib @@ -37,4 +37,12 @@ year = {2021}, month = {8}, day = {9} +} + +@online{mceliece:goppa, + title = {Binary Goppa code}, + url = {https://en.m.wikipedia.org/wiki/Binary_Goppa_code}, + year = {2021}, + month = {8}, + day = {10} }
\ No newline at end of file diff --git a/buch/papers/punktgruppen/crystals.tex b/buch/papers/punktgruppen/crystals.tex index 4b93927..0a9d3b6 100644 --- a/buch/papers/punktgruppen/crystals.tex +++ b/buch/papers/punktgruppen/crystals.tex @@ -19,7 +19,7 @@ Ein zweidimensionales Beispiel eines solchen Muster ist Abbildung \ref{fig:punkt Für die Überschaubarkeit haben wir ein simples Motiv eines einzelnen grauen Punktes dargestellt und betrachten dies nur in zwei Dimensionen. Die eingezeichneten Vektoren \(\vec{a}_1\) und \(\vec{a}_2\) sind die kleinstmöglichen Schritte im Raum bis sich das Kristallgitter wiederholt. Wird ein beliebiger grauer Gitterpunkt in Abbildung \ref{fig:punktgruppen:lattice} gewählt und um eine ganzzahlige Linearkombination von \(\vec{a}_1\) und \(\vec{a}_2\) verschoben, endet er zwangsweise auf einem Gitterpunkt, wenn nicht wieder am selben Ort. -Im dreidimensionalen Raum können alle Gitterpunkte mit derselben Idee und einem zusätzlichen Vektor \(\vec{c}\) also +Im dreidimensionalen Raum können alle Gitterpunkte mit derselben Idee und einem zusätzlichen Vektor \(\vec{a}_3\) also \[ \vec{r} = n_1 \vec{a}_1 + n_2 \vec{a}_2 + n_3 \vec{a}_3 = \sum_i n_i \vec{a}_i \] diff --git a/buch/papers/reedsolomon/dtf.tex b/buch/papers/reedsolomon/dtf.tex index 7c88c16..9647775 100644 --- a/buch/papers/reedsolomon/dtf.tex +++ b/buch/papers/reedsolomon/dtf.tex @@ -4,7 +4,7 @@ \section{Übertragung mit Hilfe der diskrten Fourier-Transformation \label{reedsolomon:section:dtf}} \rhead{Umwandlung mit DTF} -Die Grundidee eines fehlerkorrigierenden Code ist, dass Informationen eines Datenpunkt +Die Grundidee eines fehlerkorrigierenden Code ist, dass Informationen eines Datenpunktes durch die Codierung auf viele übertragene Werte verteilt werden. Die Decodierung ist in der Lage, den ursprünglichen Datenwert zu rekonstruieren, sogar wenn einzelne wenige übertragene Werte beschädigt worden sind. @@ -12,22 +12,24 @@ sogar wenn einzelne wenige übertragene Werte beschädigt worden sind. Die Fourier-Transformation transformiert einen einzelnen Wert, eine Dirac-Funktion, auf ein Spektrum, welches sich über die ganze Frequenzachse erstreckt. Aus der Filtertheorie ist bekannt, dass der ursprüngliche Impuls mehr oder weniger rekonstruierbar ist, - vorausgestzt, es gehen nicht zu viele Frequenzen bei der Übertragung verloren. + vorausgesetzt, es gehen nicht zu viele Frequenzen bei der Übertragung verloren. \par Es liegt daher nahe zu versuchen, die Fourier-Transformation für Codierung und Decodierung zu verwenden. \subsection{Beispiel mit Fehlerkorrektur mit Fourier-Transformation \label{reedsolomon:subsection:sendbsp}} +Das folgende Beispiel soll zeigen, wie die Idee der Fehlerkorrektur umgesetzt wurde. +Die Fehlererkennung des Reed-Solomon-Codes funktioniert nach einem sehr Ähnlichen Prinzip. -Das folgende Beispiel soll zeigen, wie Fehlerkorrektur möglich ist. -Dieses auf eine Art, die der Funktionsweise des Reed-Solomon-Codes, -der später erklärt wird, analog ist. +%Das folgende Beispiel soll zeigen, wie Fehlerkorrektur möglich ist. +%Dieses auf eine Art, die der Funktionsweise des Reed-Solomon-Codes, +%der später erklärt wird, analog ist. \par -Der Auftrag ist nun 64 Datenwerte zu übertragen, 32 Fehler zu erkennen und 16 Fehler zu rekonstruieren. +Der Auftrag besteht darin, 64 Datenwerte zu übertragen, 32 Fehler erkennen können und bis zu 16 Fehler zu rekonstruieren. Mit Hilfe der Fourier-Transformation 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. +Durch eine Rücktransformation können die \textcolor{blue}{blauen Datenpunkte} wieder rekonstruiert werden. \begin{figure}%[!ht] \centering @@ -42,8 +44,8 @@ In der Abbildung \ref{fig:sendorder} wird eine Übertragung Schritt für Schritt In der folgenden Aufzählung werden diese einzelne Schritte erklärt und erläutert: \begin{enumerate}[(1)] \item Das Signal besteht aus 64 zufälligen, ganzzahligen Datenwerten zwischen 0 und 10. - Für die Rekonstruktion werden zusäzlich Datenwert benötigt, wir fügen deshalb 32 Werte hinzu. - Diese setzen wir willkürlich auf Null und nennen sie Fehlerkorrekturstellen. + Für die Rekonstruktion werden zusätzliche Datenwerte benötigt, wir fügen deshalb 32 Werte hinzu. + Diese setzen wir willkürlich alle auf Null und nennen sie Fehlerkorrekturstellen. Wir erhalten so einen erweiterten Signalvektor der Länge $N =96$. \item Mit der Fourier-Transformation wird der ganze Signalvektor codiert. Dadurch wird jede Informationseinheit auf alle Punkte des Spektrums verteilt. @@ -52,13 +54,13 @@ In der folgenden Aufzählung werden diese einzelne Schritte erklärt und erläut \par Im Beispiel sind dies die Werte an den Stellen 6, 20 und 74 (\textcolor{red}{rote Kurve}), die um einen Betrag verändert werden. - Dieser ist bis zu 150-mal kleiner, als die ursprünglichen codierte Werte. - Der Empfänger kennt daher im allgemeinen nicht, ob und wo Übertragungsfehler aufgetreten sind. - \item Ohne Übertragungsfehler kann der Signalvektor durch inverse Fourier-Transformation vollständig + Dieser ist bis zu 150-mal kleiner als die ursprünglich codierten Werte. + Der Empfänger erkennt daher im allgemeinen nicht, ob und wo Übertragungsfehler aufgetreten sind. + \item Ohne Übertragungsfehler kann der Signalvektor durch die inverse Fourier-Transformation vollständig wiederhergestellt werden. Dazu gehören auch die Nullen an den Fehlerkorrekturstellen 64 - 96. \par - Sind Übertragungsfehler aufgetreten, werden an diesen Stellen Werte abweichend von Null auftreten. + Sind Übertragungsfehler aufgetreten, werden an diesen Stellen die Werte von Null abweichen. Somit haben wir bereits Fehler erkannt. \item Die Werte an den Fehlerkorrekturstellen 64 - 96, die nicht mehr Null sind, nennen wir das Syndrom. Im Syndrom steckt nur Information über die Fehler, sie werden durch die inverse Fourier-Transformation erzeugt. @@ -69,7 +71,7 @@ In der folgenden Aufzählung werden diese einzelne Schritte erklärt und erläut Im Beispiel haben wir mit dem Syndrom nur etwa ein Drittel der Fehlerinformation, es ist daher zu erwarten, dass die Fehlerwerte auch nur ein Drittel so gross sind. \par -Damit können die Fehler korrigiert und die Orginaldaten wiederhergestellt werden. +Damit können die Fehler korrigiert und die Originaldaten wiederhergestellt werden. Der Rekonstruktionsauftrag ist damit erfolgreich ausgeführt. \subsection{Fourier-Transformation und Polynome\label{reedsolomon:subsection:ftandpolynom}} @@ -113,10 +115,10 @@ Die Analogie geht aber noch weiter. \label{reedsolomon:DFT_polynom2} \end{equation} für verschiedene \( w = e^{-\frac{2\pi j}{N} k}, k=1, \dots ,N-1\) übermittelt. -Das Syndrom entstand durch die Wahl ${f_{64}}=0$ bis ${f}_{N-1}=0$.(graue koeffizenten) +Das Syndrom entstand durch die Wahl ${f_{64}}=0$ bis ${f}_{N-1}=0$ (graue Koeffizenten). \par -Die Polynominterpolation und die Fourier-Transformation rechnen beide mit reeleen Zahlen. +Die Polynominterpolation und die Fourier-Transformation rechnen beide mit reellen Zahlen. Wenn die Approximation nicht mehr genügend gut ist um die Fehler zu erkennen und rekonstruieren, -dann müssen wir von den reeleen Zahlen weg und zum endlichen Körpern, oder auch Galios-Körper genannt. -Dies wird nun im nächsten Abschnitt genauer erklärt. - +dann brauchen wir andere Varianten. +Um dieser Approximation zu entkommen, verlassen wir die reellen Zahlen und gehen zum endlichen Körpern, oder auch Galois-Körper genannt. +Dieser bietet uns einige Vorteile.
\ No newline at end of file diff --git a/buch/papers/reedsolomon/einleitung.tex b/buch/papers/reedsolomon/einleitung.tex index 04f1fe2..f99ad82 100644 --- a/buch/papers/reedsolomon/einleitung.tex +++ b/buch/papers/reedsolomon/einleitung.tex @@ -7,10 +7,10 @@ \label{reedsolomon:section:einleitung}} \rhead{Einleitung} Der Reed-Solomon-Code wurde von den beiden Mathematiker Irving S. Reed und Gustave Solomon im Jahre 1960 entwickelt. -Dabei haben sie das Problem der Fehler bei der Datenübertragung gelöst. -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. +Dabei haben sie das Problem der Fehlerhaften Datenübertragung gelöst. +In diesem Abschnitt wird möglichst verständlich die mathematische Abfolge und +Funktionsweise des Reed-Solomon-Code erklärt. +Es wird jedoch nicht auf die technische Umsetzung oder Implementierung eingegangen, jedoch wird im Abschnitt \ref{reedsolomon:section:anwendung} einige Anwendungen des Reed-Solomon-Codes vorgestellt. diff --git a/buch/papers/reedsolomon/idee.tex b/buch/papers/reedsolomon/idee.tex index 6ee42ef..daa2913 100644 --- a/buch/papers/reedsolomon/idee.tex +++ b/buch/papers/reedsolomon/idee.tex @@ -5,67 +5,104 @@ \label{reedsolomon:section:idee}} \rhead{Problemstellung} Um Fehler in einer Datenübertragung zu erkennen, könnte man die Daten jeweils doppelt senden, - also immer zwei gleich Werte miteinander und so jeweils einzelne Fehler erkennen. -Wenn jedoch mehr als nur ein Fehler erkannt werden soll und sogar noch das Orginal rekonstruiert werden soll, -dann werden die Daten drei oder vierfach versendet. -Doch nur schon um Fehler zu erkennen werden überproportional viele Daten doppelt und dreifach gesendet. -Das Problem liegt darin Informationen, Zahlen, - zu Übertragen und Fehler zu erkennen und zu korrigieren. -Der Unterschied des Fehler Erkennens und Korrigirens, 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 die Originalwerte rekonstruiert. -Eine weitere Möglichkeit wäre, dass der Empfänger nach einer fehlerhaften Übertragung die selben Daten nochmals anfordert. -Dies führt wieder zu unerwünschten mehrfachen Übertragung. -In Anwendungen des Reed-Solomon-Codes Abschnitt \externaldocument{papers/reedsolomon/anwendungen} \ref{reedsolomon:section:anwendung} - ist diese vom Empfänger gesteuerte erneute Übertragen meistens nicht sinnvoll oder sogar unmöglich. -Der Reed-Solomon-Code macht dies Übertragung auf eine andere, clevere Weise. +also den gleiche Wert immer zweimal versenden. +Tritt ein Fehler ein wird sich dies in der Differenz der beiden Werten bemerkbar machen. +Aber wie erkennen wir, welcher nun der richtige ist? Die Lösung ist simpel: Wir übertragen den Wert einfach dreimal. +Wenn jetzt ein Fehler auftritt, kann durch die beiden unveränderten Werten den richtigen bestimmt werden. +Doch was machen wir, wenn bei dieser Übertragung zwei Fehler auftreten? +Oder noch schlimmer: Was wenn zweimal derselbe Fehler auftritt? Die beiden Fehlerhaften Werte überstimmen bei der Evaluierung den gesendeten Datenwert, der dann unwiderruflich verloren geht. +Wir könnten dies noch steigern mit vier, fünf oder mehr gleichen Übertragenen Werte. Dies erhöht zwar die Robustheit der gesendeten Daten, führt aber auch dazu, dass wir durch die Mehrfachübertragung nur sehr wenige Nutzdaten versenden können. +Gerade in unserer heutigen Zeit wäre dies ein enorm grosses Problem und aus diesem Grund wurden alternative Ansätze ausgearbeitet um dieses grundlegende Problem zu lösen. +% +% +%Gerade in der heutigen modernen Zeit bei dem hohen bedarf an Daten würden unsere Kommunikationssysteme bei weitem nicht ausreichen um den einen einzigen Datenwert mehrfach zu übertragen +% +% Gerade in der Heutigen modernen Zeit bei diesem enormen mass an daten die wir alle tagtäglich anfordern Währe dies wohl unmöglich, wenn wir die daten auf diese Weise +% +% +% +% +% +%Wenn es uns gelingt, Fehler nach Ihrer Übertragung zu erkennen, dann könnten wir in einem neuen Ansatz den fehlerhaft empfangenen Wert noch einmal anfordern. +%Wir stellen fest, dass für viele alltägliche Anwendungen völlig ausreichend ist. +% +%Was ist, wenn wir aber eine Datenquelle haben, von der wir nur einmalig lesen können? +% +% +% +%Beim Übertragen von drei Werten können wir maximal 2 Fehler erkennen aber nicht mehr korrigieren. +%Wenn wir noch mehr Werte +% +%Wir Übertragen Ziemlich viele Werte für so wenige Nutzdaten. Hinzu kommt, dass wir bei dieser Vorgehensweise gerade mal bestimmen können, dass überhaupt Fehler aufgetreten sind +% +% +%Wir haben also drei Werte die bestimmt einen Fehler korrigieren können, was ziemlich viele Werte um einen Fehler zu korrigieren. +% +% um so jeweils einzelne Fehler zu erkennen. +%Wenn jedoch mehr als nur ein Fehler erkannt werden und sogar noch das Original rekonstruiert werden soll, dann sollen die Daten drei oder vierfach versendet werden. +%Doch nur schon um einen Fehler zu erkennen werden überproportional viele Daten doppelt und dreifach versendet. +%Das Hauptproblem ist, dass Informationen Fehlerfrei Übertragen werden sollen. Um dies zu erreichen muss gleich nach dem Empfangen Fehler erkannt und korrigiert werden. +% +%Das Problem liegt darin, Informationen oder Zahlen beim Übertragen gleichzeitig noch +% +%Das Problem liegt darin, das Informationen oder Zahlen zu Übertragen und gleichzeitig Fehler zu erkennen +% +% +%Das Problem liegt darin Informationen, Zahlen, zu Übertragen und Fehler zu erkennen und zu korrigieren. +%Der Unterschied des Fehler Erkennens und Korrigirens, 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 die Originalwerte rekonstruiert. +%Eine weitere Möglichkeit wäre, dass der Empfänger nach einer fehlerhaften Übertragung die selben Daten nochmals anfordert. +%Dies führt wieder zu unerwünschten mehrfachen Übertragung. +%In Anwendungen des Reed-Solomon-Codes Abschnitt \externaldocument{papers/reedsolomon/anwendungen} \ref{reedsolomon:section:anwendung} +% ist diese vom Empfänger gesteuerte erneute Übertragen meistens nicht sinnvoll oder sogar unmöglich. +%Der Reed-Solomon-Code macht dies Übertragung auf eine andere, clevere Weise. \subsection{Polynom-Ansatz \label{reedsolomon:section:polynomansatz}} \rhead{Polynom-Ansatz} Eine zentrale Idee des Reed-Solomon-Code ist, aus den Daten ein Polynom zu bilden. -Von dieser Polynomfunktion wird dann eine Anzahl Werte übertragen. -\begin{beispiel} Nehmen wir die Zahlen \textcolor{blue}{2}, \textcolor{blue}{1}, \textcolor{blue}{5}, - welche übertragen werden sollen. Daraus bilden wir das Polynom +Mit dieser Polynomfunktion wird dann eine Anzahl von Werten übertragen. +\begin{beispiel} Nehmen wir die Zahlen \textcolor{blue}{2}, \textcolor{blue}{1} und \textcolor{blue}{5}, welche übertragen werden sollen. Daraus bilden wir das Polynom \begin{equation} p(x) = -\textcolor{blue}{2}x^2 + \textcolor{blue}{1}x + \textcolor{blue}{5} +\textcolor{blue}{2}x^2 + \textcolor{blue}{1}x + \textcolor{blue}{5}. \label{reedsolomon:equation1} -\end{equation}. +\end{equation} \par -Ein Polynome zweiten Grades ist durch drei Punkte eindeutig bestimmbar. -Bei einer fehlerlosen Übertragung können wir mit 3 übertragene Werte +Ein Polynom zweiten Grades ist durch drei Punkte eindeutig bestimmbar. +Bei einer fehlerlosen Übertragung können wir mit 3 übertragenen Werten das Polynom durch Polynominterpolation volständig rekonstruieren. -Wir brauchen Polynominterpolation als Methode, um aus Punkte wieder Polynom zu berechnen. -Die Koeffizente des rekonstruierten Polynoms sind dann unsere gesendeten Zahlen \textcolor{blue}{2}, \textcolor{blue}{1}, \textcolor{blue}{5}. +Wir brauchen Polynominterpolation als Methode, um aus den Punkten wieder ein Polynom zu bilden. +Die Koeffizente des rekonstruierten Polynoms sind dann unsere gesendeten Zahlen \textcolor{blue}{2}, \textcolor{blue}{1} und \textcolor{blue}{5}. \par Wie können wir nun Fehler erkennen oder sogar korrigieren? -Versuchen wir doch mehr Werte zu übertragen, wir nehmen im Beispiel 7 Werte. +Versuchen wir doch, mehr Werte zu übertragen, wie zum Beispiel 7 Werte. Übertragen werden nun die \textcolor{darkgreen}{grünen Werte} - dieses \textcolor{blue}{blauen Polynomes} an den Stellen 1, 2, 3, \dots , 7. + des \textcolor{blue}{blauen Polynomes} an den Stellen 1, 2, 3, \dots , 7. In Abbildung \ref{fig:polynom} ist das zu den \textcolor{blue}{Datenpunkten} gehörige Polynom blau dargestellt, - die \textcolor{darkgreen}{übertragenen Werte} des Polynoms sind grün. -Die grünen Punkte bestimmen die Parabel. -Damit können die Fehler erkannt werden, weil die empfangenen Punkte nicht auf der Parabel liegen. -Somit können die grauen Punkte auf der Parabel ersetzt werden und sind damit korrigiert. -Bis zu wievielen Fehler können wir nun im Beispiel korrigieren? -Wir erhöhen nun die Fehleranzahl Schritt für Schritt: +die \textcolor{darkgreen}{übertragenen Werte} des Polynoms sind grün, wobei diese Punkte aufgrund von Übertragungsfehler jetzt eine Parabel darstellen. +Die Fehlerhaften Punkte lassen sich sehr einfach bestimmen, weil diese nicht auf der ursprünglichen Funktion liegen. +Somit können die roten Punkte auf der Parabel durch die grauen ersetzt werden und sind damit korrigiert. + +Bisher konnten wir von 7 Zahlen zwei Fehler erkennen und korrigieren. Können wir in diesem Beispiel noch mehr Fehler korrigieren? +Wir erhöhen dazu die Fehleranzahl Schritt für Schritt: \begin{itemize} \item[\textit{1 Fehler}:] Bei einem Fehler können konkurrenzierende, aber falsche Polynome zusammen mit zwei originalen Punkten entstehen. Dabei können aber maximal 3 Punkte auf diesem Konkurrenzpolynom sein. - Da 6 > 3 ist haben wir unser original Polynom gefunden. + Da 6 > 3 ist haben wir unser originales Polynom gefunden. \item[\textit{2 Fehler}:] Bei Zwei Fehlern kann ein Fehler mit zwei originalen Punkten ein konkurrenzierendes, aber falsches Polynom bilden. - Da der zweite \textcolor{red}{Fehler} frei wählbar ist, kann dieser auch auf dem \textcolor{gray}{Konkurrenzpolynom} liegen, wie in der Abbilbung \ref{fig:polynom}. - Nun haben wir, ein \textcolor{blue}{originales Polynom} mit \textcolor{darkgreen}{5} übereinstimmenden und eine konkurrenzierendes mit 4 Punkten. + Da der zweite \textcolor{red}{Fehler} frei wählbar ist, kann dieser auch auf dem \textcolor{gray}{Konkurrenzpolynom} liegen, wie in der Abbilbung \ref{fig:polynom} zu sehen ist. + Nun haben wir, ein \textcolor{blue}{originales Polynom} mit \textcolor{darkgreen}{5} übereinstimmenden und ein konkurrenzierendes mit 4 Punkten. Da 5 noch grösser als 4 ist, können wir sagen, welches das Originalpolynom ist. - \item[\textit{3 Fehler}:] Bei Drei kann genau wie bei 2 oder 1 Fehler, ein konkurenzierendes Polynom mit einem Fehler und zwei originalen Punkten bestimmen werden. + \item[\textit{3 Fehler}:] Bei Drei kann genau wie bei 1 oder 2 Fehler, ein konkurenzierendes Polynom mit einem Fehler und zwei originalen Punkten bestimmt werden. Auch hier sind die anderen Fehler frei wählbar und liegen auf dem Konkurrenzpolynom. Nun ist es so das 5 Punkte auf diesem konkurenzierenden Polynom und 4 Punkte auf dem originalen. Das Originalpolynom kann nicht mehr gefunden werden. - \item[\textit{4 Fehler}:] Bei Vier, kann es noch erkannt werden, dass Fehler statt gefunden haben, da 3 orginale Punkte das ursprüngliche Polynom ergeben. - Somit haben wir mindestens 2 verschieden Polynome, dass bedeutet Fehler sind entstanden. - \item[\textit{5 Fehler}] Bei Fünf, kann mit den 2 originalen Punkte das Originale Polynom nicht mehr erkannt werden und - somit auch keine Aussgae gemacht werden ob Fehler statt gefunden haben oder nicht. + \item[\textit{4 Fehler}:] Bei Vier kann noch erkannt werden, dass Fehler aufgetreten sind, da 3 originale Punkte das ursprüngliche Polynom ergeben. + Somit haben wir mindestens 2 verschieden Polynome, was bedeutet, dass Fehler entstanden sind. + \item[\textit{5 Fehler:}] Bei Fünf kann mit den 2 originalen Punkte das Originale Polynom nicht mehr erkannt werden und + somit kann auch keine Aussage mehr gemacht werden, ob Fehler aufgetreten sind oder nicht. \end{itemize} \begin{figure}%[!ht] @@ -80,12 +117,12 @@ Wir erhöhen nun die Fehleranzahl Schritt für Schritt: \section{Anzahl Übertragungswerte 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}{Datenwerte} gesendet und wieviel \textcolor{red}{Fehler} erkennt werden sollen. -Die Anzahl Datenwerte, ergeben die Anzahl Polynomkoeffizente \textcolor{blue}{$k$} und somit den Grad $k-1$. +Um zu bestimmen, wie viele zusätzliche \textcolor{darkgreen}{Übertragungspunkte} notwendig sind um die Fehler zu korrigieren, + muss man zuerst wissen, wie viele \textcolor{blue}{Datenwerte} gesendet und wie viele \textcolor{red}{Fehler} erkannt werden sollen. +Die Anzahl Datenwerte ergeben die Anzahl Polynomkoeffizenten \textcolor{blue}{$k$} und somit den Grad $k-1$ des Polynoms. Die Bestimmung der Anzahl der Fehler \textcolor{red}{$t$}, welche korrigiert werden können, braucht Redundanz. -Gehen wir die Fehleranzahl mit verschiedenen Übertragungsanzahlen durch, - erkennt man almählich ein Muster. +Bilden wir verschieden grosse Polynome und untersuchen diese mit unterschiedlich vielen Fehlern erkennt man allmählich ein Muster. + \begin{table}%[!ht] \centering \begin{tabular}{ c c | c} @@ -105,16 +142,16 @@ Gehen wir die Fehleranzahl mit verschiedenen Übertragungsanzahlen durch, \par Es müssen mehr Punkte auf dem \textcolor{blue}{originalen Polynom} liegen, als auf dem konkurenzierenden. Somit braucht man für die Übertragung pro \textcolor{red}{Fehler} zwei Übertragungspunkte mehr. -Wie in der Tabelle ergibt sich diese \textcolor{darkgreen}{Übertragungsanzahl} +Wie in der Tabelle \ref{tab:fehlerkorrekturstellen} ersichtlich ist ergeben sich diese Anzahl an \textcolor{darkgreen}{Punkte} für die Übertragung. \begin{equation} \textcolor{darkgreen}{u}= \textcolor{blue}{k}+2\textcolor{red}{t}. \label{reedsolomon:equation2} \end{equation} -Ein Nebeneffekt ist, dass auch $2t$ Fehler erkannt werden können, nicht aber korrigiert. -Für die Polynomkoeffizente nach der Übertragung zu rekonstruieren, - haben wir jedes mal die Polynominterpolationmethode angewendet. -Diese Polynoiminterpolation ist leider schwierig und fehleranfällig. -Deshalb finden wir eine alternative im nächsten Abschnitt. +Ein Nebeneffekt ist, dass auch $2t$ Fehler erkannt werden können, die aber nicht korrigiert werden können. +Um die Polynomkoeffizenten nach der Übertragung zu rekonstruieren, haben wir jedes mal die Polynominterpolationsmethode angewendet. +Diese Polynominterpolation ist leider schwierig zu berechnen und sehr fehleranfällig. +Es wäre daher einfacher, wenn wir eine alternative Vorgehensweise finden könnten. + |