From e42e7f03932de6d3d0966bb603c58f7e603b240c Mon Sep 17 00:00:00 2001 From: JODBaer Date: Mon, 2 Aug 2021 16:46:52 +0200 Subject: save --- buch/papers/reedsolomon/dtf.tex | 2 +- buch/papers/reedsolomon/idee.tex | 2 +- buch/papers/reedsolomon/standalone/standalone.pdf | Bin 1835758 -> 1830948 bytes buch/papers/reedsolomon/tikz/plotfft.tex | 5 +++-- buch/papers/reedsolomon/tikz/plotfftraw.tex | 1 + 5 files changed, 6 insertions(+), 4 deletions(-) (limited to 'buch/papers/reedsolomon') diff --git a/buch/papers/reedsolomon/dtf.tex b/buch/papers/reedsolomon/dtf.tex index 4552bed..3e16d81 100644 --- a/buch/papers/reedsolomon/dtf.tex +++ b/buch/papers/reedsolomon/dtf.tex @@ -42,7 +42,7 @@ Zu Beachten ist auch noch, dass der Fehler um das 20- bis 150-Fache kleiner ist. \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. + 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, diff --git a/buch/papers/reedsolomon/idee.tex b/buch/papers/reedsolomon/idee.tex index 41e0d4c..7620df1 100644 --- a/buch/papers/reedsolomon/idee.tex +++ b/buch/papers/reedsolomon/idee.tex @@ -16,7 +16,7 @@ Der Unterschied des Fehler erkennen und korrigiren, ist das beim Erkennen nur di 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} +Anwendungen finden sind im Abschnitt \externaldocument{papers/reedsolomon/anwendungen} \ref{reedsolomon:section:anwendung} beschrieben. \subsection{Polynom-Ansatz diff --git a/buch/papers/reedsolomon/standalone/standalone.pdf b/buch/papers/reedsolomon/standalone/standalone.pdf index 4a44333..2666d1e 100644 Binary files a/buch/papers/reedsolomon/standalone/standalone.pdf and b/buch/papers/reedsolomon/standalone/standalone.pdf differ diff --git a/buch/papers/reedsolomon/tikz/plotfft.tex b/buch/papers/reedsolomon/tikz/plotfft.tex index bb74dfb..3b0c421 100644 --- a/buch/papers/reedsolomon/tikz/plotfft.tex +++ b/buch/papers/reedsolomon/tikz/plotfft.tex @@ -8,6 +8,7 @@ \usepackage{pgfplotstable} \usepackage{csvsimple} \usepackage{filecontents} +\definecolor{darkgreen}{RGB}{0,0.6,0} \begin{document} @@ -30,7 +31,7 @@ \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}; + \addplot[darkgreen] 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}; @@ -47,7 +48,7 @@ \node(empfangen) [] { \begin{tikzpicture} \begin{axis}[title = {\Large {Empfangen}}] - \addplot[green] table[col sep=comma] {tikz/empfangen.txt}; + \addplot[darkgreen] table[col sep=comma] {tikz/empfangen.txt}; \end{axis} \end{tikzpicture}};\\ diff --git a/buch/papers/reedsolomon/tikz/plotfftraw.tex b/buch/papers/reedsolomon/tikz/plotfftraw.tex index 141d2ce..db35734 100644 --- a/buch/papers/reedsolomon/tikz/plotfftraw.tex +++ b/buch/papers/reedsolomon/tikz/plotfftraw.tex @@ -1,3 +1,4 @@ + \begin{tikzpicture}[] %--------------------------------------------------------------- -- cgit v1.2.1 From c059993bcc52aef36aee3a9c5d0b43777db9b061 Mon Sep 17 00:00:00 2001 From: JODBaer Date: Wed, 4 Aug 2021 10:10:17 +0200 Subject: dtf ausgeschrieben --- buch/papers/reedsolomon/dtf.tex | 153 +++++++++++++++++++++++++--------------- 1 file changed, 95 insertions(+), 58 deletions(-) (limited to 'buch/papers/reedsolomon') diff --git a/buch/papers/reedsolomon/dtf.tex b/buch/papers/reedsolomon/dtf.tex index 3e16d81..362f4eb 100644 --- a/buch/papers/reedsolomon/dtf.tex +++ b/buch/papers/reedsolomon/dtf.tex @@ -1,85 +1,122 @@ % % dtf.tex -- Idee mit DFT % -\section{Übertragung mit Hilfe der Diskrten Fourientransformation +\section{Übertragung mit Hilfe der Diskrten Fourier-Transformation \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. +Die Grundidee eines fehlerkorrigierenden Code ist, dass Informationen eines Datenpunkt, +durch die Codierung, auf viele übertragene Werte verteilt werden. +Die Decodierung ist in der Lage, den ursprünglichen Datenwert zu rekonstruieren, +sogar wenn einzelne wenige übertragene Werte beschädigt worden sind. +\par +Die Fourier-Transformation transformiert einen einzelnen Wert, +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. +Forausgestzt, 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{Diskrete Fourietransformation Zusamenhang -\label{reedsolomon:subsection:dtfzusamenhang}} -Mit hilfe der Fourietransformation werden die \textcolor{blue}{blauen Datenpunkte} transformiert, +\subsection{Beispiel mit Fehlerkorrektur mit Fourier-Transformation +\label{reedsolomon:subsection:sendbsp}} + +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 Daten zu übertragen, 32 Fehler erkennen und 16 Fehler 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. - -\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. +\par \begin{figure} \centering - \resizebox{1.1\textwidth}{!}{ + \resizebox{\textwidth}{!}{ \includegraphics[width=\textwidth]{papers/reedsolomon/figures/plotfft} %\input{papers/reedsolomon/tikz/plotfftraw.tex} } - \caption{Übertragungsabfolge \ref{reedsolomon:subsection:Übertragungsabfolge}} + \caption{Übertragungsabfolge \ref{reedsolomon:subsection:sendbsp}} \label{fig:sendorder} \end{figure} +In der Abbildung \ref{fig:sendorder} wird eine Übertragung Schritt für Schritt illustriert. +In der folgenden Aufzählung werden diese einzelne Schritte erklärt und erläutert: +\begin{enumerate}[(1)] + \item Das Signal ist mit 64 zufälligrn, 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 + \externaldocument{papers/reedsolomon/idee}\ref{reedsolomon:section: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. + \item Wir dürfen annehmen, dass bei der Übertragung, nur einzelne übertragene Werte durch Fehler, + verändert werden. + \par + Im Beispiel sind dies die Werte an den Stellen 7, 21 und 75(\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 + 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. + Somit haben wir bereits Fehler erkannt. + \item Die Werte an den Fehlerkorrekturstellen 64 - 96, die nicht mehr Null sind, nennenwir das Syndrom. + Im Syndrom steckt nur Information über die Fehler, sie werden durch die Inverse Fourier-Transformation erzeugt. + \item Um die Fehler zu rekonstruieren, ann man versuchen, die Information im Syndrom mit Fourier-Transformation zu transformieren. + Da das Syndrom nur ein Teil der Fehlerinformation ist, liefert die Fourier-Transformation eine Approximation der Fehler. + Diese Approximation der Fehler ist genau genug, um die Fehlerstellen zu localisieren. +\end{enumerate} +Im Beispiel haben wir mit dem Syndrom nur etwa ein Drittel der Fehlerinformation, es ist daher zu erwarten, +dass die Fehlerwerte auch nur ein drittel so gross sind. +\par +Damit können die Fehler korrigiert und die Orginaldaten wiederhergestellt werden. +Der Rekonstruktionsauftrag ist damit erfolgreich ausgeführt. -Nun zur Definition der Diskrete Fourietransformation, diese ist definiert als +\subsection{Fourier-Transformation und Polynome\label{reedsolomon:subsection:ftandpolynom}} +Im Abschnitt \externaldocument{papers/reedsolomon/idee}\ref{reedsolomon:section:polynomansatz} +wurden Werte eines Polynoms zur Codierung verwendet. +Die 7 Übertragungspunkte könnten ein Polynom +\begin{equation} + \textcolor{darkgreen}{p(x)} + = + \textcolor{blue}{a_0} + \textcolor{blue}{a_1}x + \textcolor{blue}{a_2}x^2 + + \textcolor{gray}{a_3}x^3 + \textcolor{gray}{a_4}x^4 + \textcolor{gray}{a_5}x^5 + + \textcolor{gray}{a_6}x^6 +\label{reedsolomon:equationpoly} +\end{equation} +sechsten Grades bestimmen. +Durch die Wahl von $\textcolor{gray}{a_3=0}$, $\textcolor{gray}{a_4=0}$, $\textcolor{gray}{a_5=0}$, $\textcolor{gray}{a_6=0}$ +erzeugen wir die, für die Fehlerkorrektur, +nötige Redundanz, ganz analog zum Schritt (1) im Beispiel. +\par +Die Analogie geht aber noch weiter. + Schreibt man + \( w = + e^{-\frac{2\pi j}{N} k}\) + \label{reedsolomon:DFT_summand}, damit wird aus der Formel \begin{equation} \hat{c}_{k} = \frac{1}{N} \sum_{n=0}^{N-1} - {f}_n \cdot e^{-\frac{2\pi j}{N} \cdot kn}. + {f}_n \cdot e^{-\frac{2\pi j}{N} \cdot kn} ,\label{reedsolomon:DFT} \end{equation} - Wenn man nun + für die Diskrte-Fourier-Transformation das Polynom \begin{equation} - w = - e^{-\frac{2\pi j}{N} k} - \label{reedsolomon:DFT_summand} + q(w)= + \frac{{f}_0}{N} + \frac{{f}_1}{N} w^1 + \frac{{f}_2}{N} w^2 + \dots + \frac{{f}_{N-1}}{N} w^{N-1} + \label{reedsolomon:DFT_polynom} \end{equation} - ersetzte, und $N$ konstantbleibt, erhält man + Im Beispiel werden aber Werte des des Polynoms $q(w)$ für verschieden + \( w = e^{-\frac{2\pi j}{N} k}, k=1, \dots , k=N-1\) übermittelt. \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} + \textcolor{darkgreen}{q(w)}= + \frac{\textcolor{blue}{{f}_0}}{N} + \frac{\textcolor{blue}{{f}_1}}{N} w^1 + \frac{\textcolor{blue}{{f}_2}}{N} w^2 + \dots + + \frac{\textcolor{blue}{{f}_63}}{N} w^{63} + \frac{\textcolor{gray}{{f}_64}}{N} w^{64} + \textcolor{gray}{\dots} + \frac{\textcolor{gray}{{f}_{N-1}}}{N} w^{N-1} + \label{reedsolomon:DFT_polynom2} \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, +Die Polynominterpolation und die Fourier-Transformation rechnen beide mit reelen Zahlen. +Wenn die Approximation nicht mehr genügend gut ist im die Fehler zu erkennen und rekonstruieren. +Deshalb haben die Mathematiker einen neuen Körper gesucht und ihn in der Endlichkeit gefunden, dies wird nun im nächsten Abschnitt genauer erklärt. -- cgit v1.2.1 From 4215ac353f9234914d5564f82f85045debb40d0b Mon Sep 17 00:00:00 2001 From: JODBaer Date: Wed, 4 Aug 2021 11:22:14 +0200 Subject: save changes --- buch/papers/reedsolomon/dtf.tex | 7 ++++-- buch/papers/reedsolomon/tikz/plotfft.tex | 39 ++++++++++++++++++++------------ 2 files changed, 29 insertions(+), 17 deletions(-) (limited to 'buch/papers/reedsolomon') diff --git a/buch/papers/reedsolomon/dtf.tex b/buch/papers/reedsolomon/dtf.tex index 362f4eb..a975da8 100644 --- a/buch/papers/reedsolomon/dtf.tex +++ b/buch/papers/reedsolomon/dtf.tex @@ -112,11 +112,14 @@ Die Analogie geht aber noch weiter. \begin{equation} \textcolor{darkgreen}{q(w)}= \frac{\textcolor{blue}{{f}_0}}{N} + \frac{\textcolor{blue}{{f}_1}}{N} w^1 + \frac{\textcolor{blue}{{f}_2}}{N} w^2 + \dots + - \frac{\textcolor{blue}{{f}_63}}{N} w^{63} + \frac{\textcolor{gray}{{f}_64}}{N} w^{64} + \textcolor{gray}{\dots} + \frac{\textcolor{gray}{{f}_{N-1}}}{N} w^{N-1} + \frac{\textcolor{blue}{{f}_{63}}}{N} w^{63} + \frac{\textcolor{gray}{{f}_{64}}}{N} w^{64} + \textcolor{gray}{\dots} + \frac{\textcolor{gray}{{f}_{N-1}}}{N} w^{N-1} \label{reedsolomon:DFT_polynom2} \end{equation} +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 reelen Zahlen. -Wenn die Approximation nicht mehr genügend gut ist im die Fehler zu erkennen und rekonstruieren. +Wenn die Approximation nicht mehr genügend gut ist um die Fehler zu erkennen und rekonstruieren, +dann müssen wir von den Reelen-Zahlen weg und zum endlichen Körpern, oder auch Galios-Körper genannt. Deshalb haben die 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/tikz/plotfft.tex b/buch/papers/reedsolomon/tikz/plotfft.tex index 3b0c421..77c4dc3 100644 --- a/buch/papers/reedsolomon/tikz/plotfft.tex +++ b/buch/papers/reedsolomon/tikz/plotfft.tex @@ -8,7 +8,7 @@ \usepackage{pgfplotstable} \usepackage{csvsimple} \usepackage{filecontents} -\definecolor{darkgreen}{RGB}{0,0.6,0} + \begin{document} @@ -29,12 +29,13 @@ \node(codiert) [] { \begin{tikzpicture}[] - \begin{axis}[ title = {\Large {Codiert \space + \space Fehler}}, - xtick={0,40,60,100}, axis y line*=left] - \addplot[darkgreen] table[col sep=comma] {tikz/codiert.txt}; + % Beschriftung Rechts + \begin{axis}[axis x line= none, axis y line*=right,ytick={0}] + \addplot[color=white] {0}; \end{axis} - \begin{axis}[xtick={7,21,75}, axis y line*=right] - \addplot[red] table[col sep=comma] {tikz/fehler.txt}; + + \begin{axis}[ title = {\Large {Codiert}}, axis y line*=left] + \addplot[color=black!60!green] table[col sep=comma] {tikz/codiert.txt}; \end{axis} \end{tikzpicture}}; \\ @@ -47,8 +48,12 @@ \node(empfangen) [] { \begin{tikzpicture} - \begin{axis}[title = {\Large {Empfangen}}] - \addplot[darkgreen] table[col sep=comma] {tikz/empfangen.txt}; + \begin{axis}[title = {\Large {Empfangen \space + \space Fehler}}, + xtick={0,40,60,100}, axis y line*=left] + \addplot[color=black!60!green] table[col sep=comma] {tikz/empfangen.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}};\\ @@ -61,7 +66,12 @@ \node(locator) [] { \begin{tikzpicture} - \begin{axis}[title = {\Large {Locator}}] + % Beschriftung Rechts + \begin{axis}[axis x line= none, axis y line*=right, ytick={0.3}]; + \addplot[color=black!60] {0.3}; + \end{axis} + + \begin{axis}[title = {\Large {Locator}},axis y line*=left] \addplot[gray] table[col sep=comma] {tikz/locator.txt}; \end{axis} \end{tikzpicture}};\\ @@ -75,7 +85,6 @@ \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); @@ -86,10 +95,10 @@ %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}; + \node[circle, draw, fill =lightgray] at (codiert.north west) {2}; + \node[circle, draw, fill =lightgray] at (empfangen.north west) {3}; + \node[circle, draw, fill =lightgray] at (decodiert.north west) {4}; + \node[circle, draw, fill =lightgray] at (syndrom.north west) {5}; + \node[circle, draw, fill =lightgray] at (locator.north west) {6}; \end{tikzpicture} \end{document} \ No newline at end of file -- cgit v1.2.1 From f93391f38bb4fcc1aaad4a22fa23fca78375cf82 Mon Sep 17 00:00:00 2001 From: JODBaer Date: Sat, 7 Aug 2021 11:19:04 +0200 Subject: save --- buch/papers/reedsolomon/idee.tex | 96 +++++++++++++++---------- buch/papers/reedsolomon/tikz/tikz/codiert.txt | 96 +++++++++++++++++++++++++ buch/papers/reedsolomon/tikz/tikz/decodiert.txt | 96 +++++++++++++++++++++++++ buch/papers/reedsolomon/tikz/tikz/empfangen.txt | 96 +++++++++++++++++++++++++ buch/papers/reedsolomon/tikz/tikz/fehler.txt | 96 +++++++++++++++++++++++++ buch/papers/reedsolomon/tikz/tikz/locator.txt | 96 +++++++++++++++++++++++++ buch/papers/reedsolomon/tikz/tikz/signal.txt | 96 +++++++++++++++++++++++++ buch/papers/reedsolomon/tikz/tikz/syndrom.txt | 96 +++++++++++++++++++++++++ 8 files changed, 729 insertions(+), 39 deletions(-) create mode 100644 buch/papers/reedsolomon/tikz/tikz/codiert.txt create mode 100644 buch/papers/reedsolomon/tikz/tikz/decodiert.txt create mode 100644 buch/papers/reedsolomon/tikz/tikz/empfangen.txt create mode 100644 buch/papers/reedsolomon/tikz/tikz/fehler.txt create mode 100644 buch/papers/reedsolomon/tikz/tikz/locator.txt create mode 100644 buch/papers/reedsolomon/tikz/tikz/signal.txt create mode 100644 buch/papers/reedsolomon/tikz/tikz/syndrom.txt (limited to 'buch/papers/reedsolomon') diff --git a/buch/papers/reedsolomon/idee.tex b/buch/papers/reedsolomon/idee.tex index 7620df1..c071b5e 100644 --- a/buch/papers/reedsolomon/idee.tex +++ b/buch/papers/reedsolomon/idee.tex @@ -5,60 +5,78 @@ \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. + also immer zwei gleich Werte miteinander und so jeweilige einen Fehler zu erkennen. +Wenn jedoch mehr als nur ein Fehler erkennt 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. -Der Reed-Solomon-Code macht dies auf eine andere, clevere Weise. Das Problem liegt darin Informationen, Zahlen, -zu Übertragen und Fehler zu erkennen. + zu Übertragen und Fehler zu erkennen. Speziell beim Reed-Solomon-Code kann man nicht nur Fehler erkennen, -man kann sogar einige Fehler korrigieren. + 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. +Der Reed-Solomon-Code macht dies auf eine andere, clevere Weise. Anwendungen finden sind im Abschnitt \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 +Eine Idee ist, aus den Daten ein Polynom zu bilden. +In deieser Art arbeitet der Reed-Solomon-Code. +Von dieser Polynomfunktion wird dann eine Anzahl Werte übertragen. +\begin{beispiel} Nehmen wir zum Beispiel 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. +ergibt. +\par +Ein Polynome zweiten Grades ist durch drei Punkte eindeutig bestimmbar. +Bei einer fehlerlosen Übertragung, können wir mit 3 übertragene Werte, + das Polynom durch Polynominterpolation volständig rekonstruieren. +Weder erkläre noch erläutere ich die Polynominterpolation, + sie kann nachgeschaut werden oder als Funktion angewendet werden. +Die koeffizente, des rekonstruierten Polynoms, sind dann unsere gesendten Zahlen \textcolor{blue}{2}, \textcolor{blue}{1}, \textcolor{blue}{5}. +Wie können wir nun Fehler erkennen oder sogar korrigieren? +Versuchen wir doch mehr Werte zu Übertragen, wir nehmen im 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 dieses Polynomes. + dieses 7 Werte \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} + 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})$ +Nun wird durch drei der 7 Punkte das Polynom eindeutig bestimmbar und + alle anderen müssen auf diesem Polynom liegen. +Dabei gingen wir von keinem Fehler aus, + hat es Fehler in der Übertragunge gegeben. +Wir erhöhen nun die Fehleranzahl Schritt für Schritt: +\begin{enumerate} + \item \textit{Fehler} können konkurenzierende Polynome, zusammen mit zwei originalen Punkten fehlleiten. + Dabei kann aber maximal 3 Punkte auf diesem Konkurrenzpolynom sein, + ansonsten ist der Fehler ein Orginalpunkt und somit kein Fehler. + Da 6 übereinstimende grössser als 3 ist haben wir unser original Polynom gefunden. + \par Orginal mit 6 Punkte > 3 Punkte Konkurrenzpolynom, Original Polynom gefunden + Damit ist klar das unser Polynom mit 6 Punkten richtig ist und unser Fehler kann rekonstruiert werden. + \item \textit{Fehler} kann ein Fehler mit zwei originalen Punkten ein fehlleitendes Konkurrenzpolynom bilden. + Da der zweite Fehler frei wählbar ist kann dieser auch auf dem Konkurrenzpolynom liegen, wie in der Abbilbung \ref{fig:polynom}. + Nun haben wir, wie in unserer Grafik \ref{fig:polynom}, ein Polynom mit 5 übereinstimmenden und eines mit 4 Punkten. + Da 5 noch grösser als 4 ist, können wir sagen welches das original Polynom ist. + \par Orginal mit 5 Punkte > 4 Punkte Konkurrenzpolynom, Original Polynom gefunden + \item \textit{Fehler} kann genau wie bei 2 Fehler, ein Fehler ein fehlleitendes Polynom mit 2 original Punkten bestimmen 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 Original Polynom kann nicht mehr gefunden werden. + \par Orginal mit 5 Punkte > 4 Punkte Konkurrenzpolynom, Original Polynom nicht gefunden + \item \textit{Fehler} Es kann noch erkennt weden das 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{Fehler} Mit den 2 originalen Punkte kann das Originale Polynom nicht mehr erkannt werden und + somit auch keine Aussgae gemacht werden ob Fehler statt gefunden haben oder nicht. +\end{enumerate} \begin{figure}%[!ht] \centering @@ -71,13 +89,13 @@ Um das Konkurrenzpolynom auszuschliessen, währen mehr \textcolor{darkgreen}{Üb \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. + 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$. + 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. + 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 @@ -86,7 +104,7 @@ Man könnte auch dies in der Tabelle \ref{tab:fehlerkorrekturstellen} erkennen, =2 \label{reedsolomon:equation2} \end{equation} -zeigt sich, dass es $k+2t$ Übertragungspunkte braucht. + zeigt sich, dass es $k+2t$ Übertragungspunkte braucht. \begin{table} \centering diff --git a/buch/papers/reedsolomon/tikz/tikz/codiert.txt b/buch/papers/reedsolomon/tikz/tikz/codiert.txt new file mode 100644 index 0000000..4a481d8 --- /dev/null +++ b/buch/papers/reedsolomon/tikz/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/tikz/decodiert.txt b/buch/papers/reedsolomon/tikz/tikz/decodiert.txt new file mode 100644 index 0000000..f6221e6 --- /dev/null +++ b/buch/papers/reedsolomon/tikz/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/tikz/empfangen.txt b/buch/papers/reedsolomon/tikz/tikz/empfangen.txt new file mode 100644 index 0000000..38c13b0 --- /dev/null +++ b/buch/papers/reedsolomon/tikz/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/tikz/fehler.txt b/buch/papers/reedsolomon/tikz/tikz/fehler.txt new file mode 100644 index 0000000..23f1a83 --- /dev/null +++ b/buch/papers/reedsolomon/tikz/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/tikz/locator.txt b/buch/papers/reedsolomon/tikz/tikz/locator.txt new file mode 100644 index 0000000..b28988c --- /dev/null +++ b/buch/papers/reedsolomon/tikz/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/tikz/signal.txt b/buch/papers/reedsolomon/tikz/tikz/signal.txt new file mode 100644 index 0000000..c4fa5f8 --- /dev/null +++ b/buch/papers/reedsolomon/tikz/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/tikz/syndrom.txt b/buch/papers/reedsolomon/tikz/tikz/syndrom.txt new file mode 100644 index 0000000..8ca9eed --- /dev/null +++ b/buch/papers/reedsolomon/tikz/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 -- cgit v1.2.1 From 14c4c9bde57c1cd89510719439bdd31374ddc280 Mon Sep 17 00:00:00 2001 From: JODBaer Date: Sat, 7 Aug 2021 14:11:14 +0200 Subject: save --- buch/papers/reedsolomon/dtf.tex | 2 +- buch/papers/reedsolomon/einleitung.tex | 4 +- buch/papers/reedsolomon/idee.tex | 116 ++++++++++------------ buch/papers/reedsolomon/standalone/standalone.pdf | Bin 1830948 -> 1835588 bytes 4 files changed, 55 insertions(+), 67 deletions(-) (limited to 'buch/papers/reedsolomon') diff --git a/buch/papers/reedsolomon/dtf.tex b/buch/papers/reedsolomon/dtf.tex index a975da8..179d90d 100644 --- a/buch/papers/reedsolomon/dtf.tex +++ b/buch/papers/reedsolomon/dtf.tex @@ -28,7 +28,7 @@ Der Auftrag ist nun 64 Daten zu übertragen, 32 Fehler erkennen und 16 Fehler re 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. -\par + \begin{figure} \centering \resizebox{\textwidth}{!}{ diff --git a/buch/papers/reedsolomon/einleitung.tex b/buch/papers/reedsolomon/einleitung.tex index 074df05..ca4f398 100644 --- a/buch/papers/reedsolomon/einleitung.tex +++ b/buch/papers/reedsolomon/einleitung.tex @@ -6,8 +6,8 @@ \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. +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. diff --git a/buch/papers/reedsolomon/idee.tex b/buch/papers/reedsolomon/idee.tex index c071b5e..3061498 100644 --- a/buch/papers/reedsolomon/idee.tex +++ b/buch/papers/reedsolomon/idee.tex @@ -4,79 +4,69 @@ \section{Idee \label{reedsolomon:section:idee}} \rhead{Problemstellung} -Um beim Datenübertragen Fehler zu erkennen, könnte man die Daten jeweils doppelt senden, - also immer zwei gleich Werte miteinander und so jeweilige einen Fehler zu erkennen. +Um Fehler in einer Datenübertragung zu erkennen, könnte man die Daten jeweils doppelt senden, + also immer zwei gleich Werte miteinander und so jeweilige einzelne Fehler erkennen. Wenn jedoch mehr als nur ein Fehler erkennt 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. -Speziell beim Reed-Solomon-Code kann man nicht nur Fehler erkennen, - man kann sogar einige Fehler korrigieren. + zu Übertragen und Fehler zu erkennen und zu 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. -Der Reed-Solomon-Code macht dies auf eine andere, clevere Weise. -Anwendungen finden sind im Abschnitt \externaldocument{papers/reedsolomon/anwendungen} -\ref{reedsolomon:section:anwendung} beschrieben. +Eine weitere Möglichkeit wäre, dass der Empfänger nach einer fehlerhaften Übertragung die selben Daten nochmals auffordert. +Dies führt wieder zu unerwünschten mehrfach Übertragung. +In Anwendungen des Reed-Soöomon-Code \externaldocument{papers/reedsolomon/anwendungen} \ref{reedsolomon:section:anwendung} +ist dies 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 Idee ist, aus den Daten ein Polynom zu bilden. -In deieser Art arbeitet der Reed-Solomon-Code. +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 zum Beispiel die Zahlen \textcolor{blue}{2}, \textcolor{blue}{1}, \textcolor{blue}{5}, - welche uns dann das Polynom +\begin{beispiel} Nehmen wir die Zahlen \textcolor{blue}{2}, \textcolor{blue}{1}, \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} \label{reedsolomon:equation1} -\end{equation} -ergibt. +\end{equation}. \par Ein Polynome zweiten Grades ist durch drei Punkte eindeutig bestimmbar. Bei einer fehlerlosen Übertragung, können wir mit 3 übertragene Werte, das Polynom durch Polynominterpolation volständig rekonstruieren. -Weder erkläre noch erläutere ich die Polynominterpolation, - sie kann nachgeschaut werden oder als Funktion angewendet werden. +Weder erkläre noch erläutere ich die Polynominterpolation, + wir brauchen sie als Funktion, die von Punktn ein Polynom errechnet. Die koeffizente, des rekonstruierten Polynoms, sind dann unsere gesendten Zahlen \textcolor{blue}{2}, \textcolor{blue}{1}, \textcolor{blue}{5}. Wie können wir nun Fehler erkennen oder sogar korrigieren? Versuchen wir doch mehr Werte zu Übertragen, wir nehmen im Beispiel 7 Werte. Übertragen werden nun die \textcolor{darkgreen}{grünen Werte} - dieses 7 Werte \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})$ -Nun wird durch drei der 7 Punkte das Polynom eindeutig bestimmbar und - alle anderen müssen auf diesem Polynom liegen. -Dabei gingen wir von keinem Fehler aus, - hat es Fehler in der Übertragunge gegeben. + dieses 7 Werte \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}{übertragene Werte} des Polynoms sind grün. +Die grünen Punkte bestimmen die Parabel. +Damit können die Fehler erkannt werden, weil die empfangenen Punktenicht auf der Parabel liegen. +Somit könnendie grauen Punkte auf der Parabel ersetzt werden und sind damit korrigiert. +bis zu wivielen Fehler können wir nun korrigieren im Beispiel korrigieren? Wir erhöhen nun die Fehleranzahl Schritt für Schritt: -\begin{enumerate} - \item \textit{Fehler} können konkurenzierende Polynome, zusammen mit zwei originalen Punkten fehlleiten. - Dabei kann aber maximal 3 Punkte auf diesem Konkurrenzpolynom sein, - ansonsten ist der Fehler ein Orginalpunkt und somit kein Fehler. +\begin{itemize} + \item Bei \textit{1 Fehler} können konkurenzierende Polynome, zusammen mit zwei originalen Punkten fehlleiten. + Dabei kann aber maximal 3 Punkte auf diesem Konkurrenzpolynom sein. Da 6 übereinstimende grössser als 3 ist haben wir unser original Polynom gefunden. - \par Orginal mit 6 Punkte > 3 Punkte Konkurrenzpolynom, Original Polynom gefunden - Damit ist klar das unser Polynom mit 6 Punkten richtig ist und unser Fehler kann rekonstruiert werden. - \item \textit{Fehler} kann ein Fehler mit zwei originalen Punkten ein fehlleitendes Konkurrenzpolynom bilden. - Da der zweite Fehler frei wählbar ist kann dieser auch auf dem Konkurrenzpolynom liegen, wie in der Abbilbung \ref{fig:polynom}. - Nun haben wir, wie in unserer Grafik \ref{fig:polynom}, ein Polynom mit 5 übereinstimmenden und eines mit 4 Punkten. - Da 5 noch grösser als 4 ist, können wir sagen welches das original Polynom ist. - \par Orginal mit 5 Punkte > 4 Punkte Konkurrenzpolynom, Original Polynom gefunden - \item \textit{Fehler} kann genau wie bei 2 Fehler, ein Fehler ein fehlleitendes Polynom mit 2 original Punkten bestimmen werden. + \item Bei \textit{2 Fehler} kann ein Fehler mit zwei originalen Punkten ein fehlleitendes Konkurrenzpolynom bilden. + Da der zweite Fehler frei wählbar ist, kann dieser auch auf dem Konkurrenzpolynom liegen, wie in der Abbilbung \ref{fig:polynom}. + Nun haben wir, ein originles Polynom mit 5 übereinstimmenden und eine konkurrenzierendes mit 4 Punkten. + Da 5 noch grösser als 4 ist, können wir sagen, welches das original Polynom ist. + \item Bei \textit{3 Fehler} kann genau wie bei 2 Fehler, ein Fehler ein fehlleitendes Polynom mit 2 original Punkten bestimmen 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 Original Polynom kann nicht mehr gefunden werden. - \par Orginal mit 5 Punkte > 4 Punkte Konkurrenzpolynom, Original Polynom nicht gefunden - \item \textit{Fehler} Es kann noch erkennt weden das Fehler statt gefunden haben, da 3 orginale Punkte das ursprüngliche Polynom ergeben. + \item Bei \textit{4 Fehler} Es kann noch erkennt weden das 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{Fehler} Mit den 2 originalen Punkte kann das Originale Polynom nicht mehr erkannt werden und + \item Bei \textit{5 Fehler} Mit den 2 originalen Punkte kann das Originale Polynom nicht mehr erkannt werden und somit auch keine Aussgae gemacht werden ob Fehler statt gefunden haben oder nicht. -\end{enumerate} +\end{itemize} \begin{figure}%[!ht] \centering @@ -85,27 +75,16 @@ Wir erhöhen nun die Fehleranzahl Schritt für Schritt: \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. +\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 \textcolor{blue}{Datenwerte}, ergeben die anzahl Polynomkoeffizente $k$ und somit den Grad $k-1$. +Die Bestimmung der Anzahl der Fehler $t$, welche korrigiert werden können, brauchen redundanz. +Gehen wir die Fehleranzahl mit verschiedenen Übertragungsanzahlen durch, + erkennt man almählich ein Muster. \begin{table} \centering \begin{tabular}{ c c | c} @@ -122,8 +101,17 @@ Man könnte auch dies in der Tabelle \ref{tab:fehlerkorrekturstellen} erkennen, \caption{ Fehlerkorrekturstellen Bestimmung.} \label{tab:fehlerkorrekturstellen} \end{table} +Es müssen mehr Punkte auf dem \textcolor{blue}{originalen Polynom} liegen, als auf dem Konkurenzierenden. +Somit braucht man für die Übertragung pro Fehler 2 übertragungspunkte mehr. +Wie in der Tabelle ergibt sich diese Übertragungsanzahl +\begin{equation} + \textcolor{darkgreen}{u}= + \textcolor{blue}{k}2\textcolor{red}{t} + \label{reedsolomon:equation2} +\end{equation}. -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. +Ein Nebeneffekt ist, dass auch $2t$ Fehler erkannt werden können, nicht aber korrigiert. +Nun haben wir für jede rekonstruktion des Polynoms, die Polynominterpolation gebraucht. +Diese Polynoiminterpolation ist leider schwierig und fehleranfällig. +Deshalb finden wir eine alternative im nächsten Abschnitt. diff --git a/buch/papers/reedsolomon/standalone/standalone.pdf b/buch/papers/reedsolomon/standalone/standalone.pdf index 2666d1e..dc34b2d 100644 Binary files a/buch/papers/reedsolomon/standalone/standalone.pdf and b/buch/papers/reedsolomon/standalone/standalone.pdf differ -- cgit v1.2.1 From 00406f140fd8a0680ef9d03a88ec032134e13566 Mon Sep 17 00:00:00 2001 From: JODBaer Date: Sat, 7 Aug 2021 14:22:04 +0200 Subject: + --- buch/papers/reedsolomon/idee.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'buch/papers/reedsolomon') diff --git a/buch/papers/reedsolomon/idee.tex b/buch/papers/reedsolomon/idee.tex index 3061498..2142f88 100644 --- a/buch/papers/reedsolomon/idee.tex +++ b/buch/papers/reedsolomon/idee.tex @@ -106,7 +106,7 @@ Somit braucht man für die Übertragung pro Fehler 2 übertragungspunkte mehr. Wie in der Tabelle ergibt sich diese Übertragungsanzahl \begin{equation} \textcolor{darkgreen}{u}= - \textcolor{blue}{k}2\textcolor{red}{t} + \textcolor{blue}{k}+2\textcolor{red}{t} \label{reedsolomon:equation2} \end{equation}. -- cgit v1.2.1 From b147539fdc2367938af08293aa16808adf6260fe Mon Sep 17 00:00:00 2001 From: JODBaer Date: Sat, 7 Aug 2021 14:22:30 +0200 Subject: plot-green --- buch/papers/reedsolomon/figures/plotfft.pdf | Bin 59617 -> 59772 bytes 1 file changed, 0 insertions(+), 0 deletions(-) (limited to 'buch/papers/reedsolomon') diff --git a/buch/papers/reedsolomon/figures/plotfft.pdf b/buch/papers/reedsolomon/figures/plotfft.pdf index 80d17d2..b455da5 100644 Binary files a/buch/papers/reedsolomon/figures/plotfft.pdf and b/buch/papers/reedsolomon/figures/plotfft.pdf differ -- cgit v1.2.1