diff options
author | JODBaer <JODBaer@github.com> | 2021-07-29 16:54:19 +0200 |
---|---|---|
committer | JODBaer <JODBaer@github.com> | 2021-07-29 16:54:19 +0200 |
commit | 8cc6ee76118ec1b446a732b9b7e06147737957d1 (patch) | |
tree | f253324587eb3fd31759a11b0d02e5558aec9c00 /buch/papers/reedsolomon | |
parent | Merge remote-tracking branch 'upstream/master' into Baer (diff) | |
download | SeminarMatrizen-8cc6ee76118ec1b446a732b9b7e06147737957d1.tar.gz SeminarMatrizen-8cc6ee76118ec1b446a732b9b7e06147737957d1.zip |
save typos
Diffstat (limited to 'buch/papers/reedsolomon')
-rw-r--r-- | buch/papers/reedsolomon/dtf.tex | 57 | ||||
-rw-r--r-- | buch/papers/reedsolomon/idee.tex | 56 | ||||
-rw-r--r-- | buch/papers/reedsolomon/tikz/polynom2.tex | 2 |
3 files changed, 60 insertions, 55 deletions
diff --git a/buch/papers/reedsolomon/dtf.tex b/buch/papers/reedsolomon/dtf.tex index e9aacfb..e9717c8 100644 --- a/buch/papers/reedsolomon/dtf.tex +++ b/buch/papers/reedsolomon/dtf.tex @@ -9,35 +9,15 @@ Um die Polynominterpolation zu umgehen, gehen wir nun über in die Fourientransformation. Dies wird weder eine Erklärung der Forientransorfmation, noch ein genauer gebrauch für den Reed-Solomon-Code. Dieser Abschnitt zeigt nur wie die Fourientransformation auf Fehler reagiert. -wobei sie dann bei späteren Berchnungen ganz nützlich ist. +Das ganze zeigen wir mit einem Beispiel einer Übertragung von Zahlen mit Hilfe der Fourientransformation. \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. -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. -\subsection{Beispiel +\subsubsection{Beispiel einer Übertragung mit Fourientransformation \label{reedsolomon:subsection:Übertragungsabfolge}} Der Auftrag ist nun 64 Daten zu übertragen und nach 32 Fehler abzusicheren, 16 Fehler erkennen und rekonstruieren. @@ -51,8 +31,8 @@ Dabei zusätzlich nach 16 Fehler abgesichert, macht insgesamt 96 Übertragungsza (siehe Abschnitt \externaldocument{papers/reedsolomon/idee}\ref{reedsolomon:section:Fehlerkorrekturstellen}) Die 32 Fehlerkorrekturstellen werden als Null Übertragen \item Nun wurde mittels der diskreten Fourientransformation diese 96 codiert. -Das heisst alle Informationen ist in alle Zahlenvorhanden. (Auch die Fehlerkorrekturstellen Null) -\item Nun kommen drei Fehler dazu an den Übertragungsstellen 7, 21 und 75.(die Skala ist Rechts) +Das heisst alle Informationen ist in alle Zahlenvorhanden. Auch die Fehlerkorrekturstellen Null. +\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. \item Dieses wird nun Empfangen und mittels inversen diskreten Fourientransormation, wieder rücktransformiert.(Iklusive der Fehler) \item Nun sieht man den Fehler im Decodieren in den Übertragungsstellen 64 bis 96, da es dort nicht mehr Null ist. @@ -71,4 +51,31 @@ jetzt gilt es nur noch diese zu korrigieren und wir haben unser originales Signa } \caption{Übertragungsabfolge \ref{reedsolomon:subsection:Übertragungsabfolge}} \label{fig:sendorder} -\end{figure}
\ No newline at end of file +\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 Fourientransformation 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/idee.tex b/buch/papers/reedsolomon/idee.tex index 8ad3d27..d8b8a93 100644 --- a/buch/papers/reedsolomon/idee.tex +++ b/buch/papers/reedsolomon/idee.tex @@ -14,9 +14,9 @@ Das Problem liegt darin Informationen, Zahlen, zu Übertragen und Fehler zu erkennen. 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 mit: Ist die Übertragung fehlerhaft oder nicht? -Beim Korrigieren werden Fehler erkennt und dann zusätzlich noch den original Wert rekonstruieren. -Auch eine Variante wäre es die Daten nach einem Fehler nachdem Fehlerhaften senden, nochmals versenden(auch hier wieder doppelt und dreifach Sendung), +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 wieder doppelt und dreifach Sendung), was bei Reed-Solomon-Code-Anwendungen nicht immer sinnvoll ist. \externaldocument{papers/reedsolomon/anwendungen} \ref{reedsolomon:section:anwendung} @@ -24,8 +24,8 @@ was bei Reed-Solomon-Code-Anwendungen nicht immer sinnvoll ist. \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, ausrechnet und diese Punkte dann überträgt. +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} @@ -48,18 +48,17 @@ Die Farbe blau brauchen wir für die \textcolor{blue}{Daten} welche wir mit der \end{beispiel} \begin{beispiel} -Aus der Gleichung \eqref{reedsolomon:equation1}, -ist ein Polynome zweiten Grades durch drei Punkte eindeutig bestimmbar. -Hat es Fehler in der Übertragunge gegeben,(Bei Abbildung \ref{fig:polynom}\textcolor{red}{roten Punkte}) kann man diese erkennen, -da alle Punkte, die korrekt sind, auf dem Polynom liegen müssen. -(Bei Abbildung \ref{fig:polynom}\textcolor{darkgreen}{grünen Punkte}) +Ein Polynome zweiten Grades ist durch drei Punkte eindeutig bestimmbar. +Hat es Fehler in der Übertragunge gegeben,(Bei Abb. \ref{fig:polynom} \textcolor{red}{roten Punkte}), +kann man diese erkennen, da alle Punkte, die korrekt sind, auf der Parabel liegen müssen. +(Bei Abb. \ref{fig:polynom} \textcolor{darkgreen}{grünen Punkte}) 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 erkennt werden, dass das Polynom nicht stimmt. +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 das Konkurenzpolynom, grau gestrichelt in Abbildung \ref{fig:polynom}, das orginal fehlleited. -Um das Konkurenzpolynom auszuschliessen, währen mehr \textcolor{darkgreen}{Übertragungspunkte} nötig. +Da 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} @@ -72,25 +71,25 @@ Um das Konkurenzpolynom auszuschliessen, währen mehr \textcolor{darkgreen}{Übe \section{Fehlerkorekturstellen bestimmen \label{reedsolomon:section:Fehlerkorrekturstellen}} -Um zu bestimmen wieviel zusätzliche \textcolor{darkgreen}{Übertragungspunkte} notwendig sind, die dann Fehler korrigieren, -muss man zuerst Wissen wieviel \textcolor{blue}{Daten} gesendet und wieviel \textcolor{red}{Fehler} erkennt werden sollen. +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 Polynomgraden, 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 7 \textcolor{darkgreen}{Übertragungspunkte} senden. -Durch 3 Punkte wird das Polyom eindeutig bestimmt, nun haben wir mehrere Konkurenzpolynome, doch mit maximal 2 Fehler liegen auf einem Konkurenzpolynom, -maximal 4 Punkte und auf unserem orginal 5 Punkte. Ansonsten hatt es mehr Fehler oder unser Konkurenzpolynom ist das gleiche wie das Original. +\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} -Durch das erkennen des Schemas in der Tabelle\ref{tabel:fehlerkorrekturstellen} +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 das es $k+2t$ Übertragungspunkte braucht. +zeigt sich, dass es $k+2t$ Übertragungspunkte braucht. -\begin{center} +\begin{table} \begin{tabular}{ c c | c} \hline Nutzlas & Fehler & Übertragen \\ @@ -102,11 +101,10 @@ zeigt sich das es $k+2t$ Übertragungspunkte braucht. $k$ & $t$ & $k+2t$ Werte eines Polynoms vom Grad $k-1$ \\ \hline \end{tabular} - Fehlerkorrekturstellen Bestimmung TODO: Tabellenreferenz - \label{tabel:fehlerkorrekturstellen} -\end{center} + \caption{\label{tab:fehlerkorrekturstellen} Fehlerkorrekturstellen Bestimmung.} +\end{table} -Ein Nebeneffekt ist das 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 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/tikz/polynom2.tex b/buch/papers/reedsolomon/tikz/polynom2.tex index 47dc679..80557fb 100644 --- a/buch/papers/reedsolomon/tikz/polynom2.tex +++ b/buch/papers/reedsolomon/tikz/polynom2.tex @@ -14,7 +14,7 @@ %////////////////////////////////////// -\begin{tikzpicture}[>=latex,thick] +\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}); |