From f12bfc8392b2f09416fb2171a4dd0107ebe16722 Mon Sep 17 00:00:00 2001 From: JODBaer Date: Mon, 26 Jul 2021 14:17:05 +0200 Subject: update some files too --- buch/papers/reedsolomon/dtf.tex | 29 ++++++++++++++++++----------- 1 file changed, 18 insertions(+), 11 deletions(-) (limited to 'buch/papers/reedsolomon/dtf.tex') diff --git a/buch/papers/reedsolomon/dtf.tex b/buch/papers/reedsolomon/dtf.tex index a111527..62e44cc 100644 --- a/buch/papers/reedsolomon/dtf.tex +++ b/buch/papers/reedsolomon/dtf.tex @@ -14,20 +14,27 @@ wobei sie dann bei späteren Berchnungen ganz nützlich ist. \subsection{Diskrete Fourientransformation Zusamenhang \label{reedsolomon:subsection:dtfzusamenhang}} Die Diskrete Fourientransformation ist definiert als - \[ - \label{ft_discrete} +\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 - \[ - w = e^{-\frac{2\pi j}{N} k} - \] +\begin{equation} + w = + e^{-\frac{2\pi j}{N} k} + \label{reedsolomon:DFT_summand} +\end{equation} + ersetzte, und $N$ konstantbleibt, erhält man - \[ - \hat{c}_{k}=\frac{1}{N}( {f}_0 w^0 + {f}_1 w^1 + {f}_2 w^2 + \dots + {f}_{N-1} w^N) - \] +\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{Übertragungsabfolge \label{reedsolomon:subsection:Übertragungsabfolge}} @@ -47,8 +54,8 @@ Das heisst alle information ist in alle Zahlenvorhanden. \begin{figure} \centering \resizebox{0.9\textwidth}{!}{ - %\includegraphics[width=0.5\textwidth]{papers/reedsolomon/images/plot.pdf} - \input{papers/reedsolomon/images/plotfft.tex} + \includegraphics[width=\textwidth]{papers/reedsolomon/figures/plotfft} + %\input{papers/reedsolomon/images/plotfft.tex} } \caption{Übertragungsabfolge \ref{reedsolomon:subsection:Übertragungsabfolge}} \label{fig:sendorder} -- cgit v1.2.1 From 88c208363cf560043f87c2c83fa251177e74cd1b Mon Sep 17 00:00:00 2001 From: JODBaer Date: Tue, 27 Jul 2021 13:20:05 +0200 Subject: save --- buch/papers/reedsolomon/dtf.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'buch/papers/reedsolomon/dtf.tex') diff --git a/buch/papers/reedsolomon/dtf.tex b/buch/papers/reedsolomon/dtf.tex index 62e44cc..ffe98f8 100644 --- a/buch/papers/reedsolomon/dtf.tex +++ b/buch/papers/reedsolomon/dtf.tex @@ -53,7 +53,7 @@ Das heisst alle information ist in alle Zahlenvorhanden. \begin{figure} \centering - \resizebox{0.9\textwidth}{!}{ + \resizebox{\textwidth}{!}{ \includegraphics[width=\textwidth]{papers/reedsolomon/figures/plotfft} %\input{papers/reedsolomon/images/plotfft.tex} } -- cgit v1.2.1 From c3c7a6320004974ba56eb98305b5ac9fa13d4a52 Mon Sep 17 00:00:00 2001 From: JODBaer Date: Tue, 27 Jul 2021 17:10:19 +0200 Subject: save --- buch/papers/reedsolomon/dtf.tex | 20 ++++++++++++-------- 1 file changed, 12 insertions(+), 8 deletions(-) (limited to 'buch/papers/reedsolomon/dtf.tex') diff --git a/buch/papers/reedsolomon/dtf.tex b/buch/papers/reedsolomon/dtf.tex index ffe98f8..73d0d12 100644 --- a/buch/papers/reedsolomon/dtf.tex +++ b/buch/papers/reedsolomon/dtf.tex @@ -7,21 +7,21 @@ \label{reedsolomon:section:dtf}} \rhead{Umwandlung mit DTF} 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. +Dies wird weder eine erklärung der Forientransorfmation noch ein genauer gebrauchfü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. -\subsection{Diskrete Fourientransformation Zusamenhang +\subsection{Diskrete Fourietransformation Zusamenhang \label{reedsolomon:subsection:dtfzusamenhang}} -Die Diskrete Fourientransformation ist definiert als +Die Diskrete Fourietransformation 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} + ,\label{reedsolomon:DFT} \end{equation} -, wenn man nun +wenn man nun \begin{equation} w = e^{-\frac{2\pi j}{N} k} @@ -38,8 +38,12 @@ ersetzte, und $N$ konstantbleibt, erhält man was überaust ähnlich zu unserem Polynomidee ist. \subsection{Übertragungsabfolge \label{reedsolomon:subsection:Übertragungsabfolge}} - -\begin{enumerate}[1)] +Der Auftrag ist nun 64 Daten zu übertragen und nach 16 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, Zahlen welche übertragen werden sollen. Dabei zusätzlich nach 16 Fehler abgesichert, macht insgesamt 96 Übertragungszahlen. \item Nun wurde mittels der schnellen diskreten Fourientransformation diese 96 codiert. -- cgit v1.2.1 From 5daff6cc906d9abb2a913569588a0666b4d53b4a Mon Sep 17 00:00:00 2001 From: JODBaer Date: Wed, 28 Jul 2021 17:52:37 +0200 Subject: rewrite some texts --- buch/papers/reedsolomon/dtf.tex | 42 ++++++++++++++++++++++++----------------- 1 file changed, 25 insertions(+), 17 deletions(-) (limited to 'buch/papers/reedsolomon/dtf.tex') diff --git a/buch/papers/reedsolomon/dtf.tex b/buch/papers/reedsolomon/dtf.tex index 73d0d12..e9aacfb 100644 --- a/buch/papers/reedsolomon/dtf.tex +++ b/buch/papers/reedsolomon/dtf.tex @@ -3,57 +3,65 @@ % % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil % -\section{Diskrete Fourier Transformation +\section{Übertragung mit hilfe der Diskrete Fourier Transformation \label{reedsolomon:section:dtf}} \rhead{Umwandlung mit DTF} Um die Polynominterpolation zu umgehen, gehen wir nun über in die Fourientransformation. -Dies wird weder eine erklärung der Forientransorfmation noch ein genauer gebrauchfür den Reed-Solomon-Code. +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. \subsection{Diskrete Fourietransformation Zusamenhang \label{reedsolomon:subsection:dtfzusamenhang}} -Die Diskrete Fourietransformation ist definiert als +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{Übertragungsabfolge + +\subsection{Beispiel \label{reedsolomon:subsection:Übertragungsabfolge}} -Der Auftrag ist nun 64 Daten zu übertragen und nach 16 Fehler abzusicheren, -16 Fehler erkennen und rekonstruieren. +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. +und hier werden die einzelne Schritte erklärt: \begin{enumerate}[(1)] \item Das Signal hat 64 die Daten, Zahlen welche übertragen werden sollen. Dabei zusätzlich nach 16 Fehler abgesichert, macht insgesamt 96 Übertragungszahlen. -\item Nun wurde mittels der schnellen diskreten Fourientransformation diese 96 codiert. -Das heisst alle information ist in alle Zahlenvorhanden. -\item Nun kommen drei Fehler dazu an den Übertragungsstellen 7, 21 und 75. -\item Dieses wird nun Empfangen und mittels inversen diskreten Fourientransormation, wieder rücktransformiert. -\item Nun sieht man den Fehler im Decodieren in den Übertragungsstellen 64 bis 96. -\item Nimmt man nun nur diese Stellen 64 bis 96, auch Syndrom genannt, und Transformiert diese. -\item Bekommt man die Fehlerstellen im Locator wieder, zwar nichtso genau, dennoch erkkent man wo die Fehler stattgefunden haben. +(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) +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. +\item Nimmt man nun nur diese Stellen 64 bis 96, dies definieren wir als Syndrom, und transformiert nur dieses Syndrom. +\item Bekommt man die Fehlerstellen wieder, zwar nichtso genau, dennoch erkennt man wo die Fehler stattgefunden haben. +Dies definieren wir als Locator. \end{enumerate} +Nun haben wir mit Hilfe der Fourietransformation die 3 Fehlerstellen durch das Syndrom lokalisiert, +jetzt gilt es nur noch diese zu korrigieren und wir haben unser originales Signal wieder. \begin{figure} \centering -- cgit v1.2.1 From 8cc6ee76118ec1b446a732b9b7e06147737957d1 Mon Sep 17 00:00:00 2001 From: JODBaer Date: Thu, 29 Jul 2021 16:54:19 +0200 Subject: save typos --- buch/papers/reedsolomon/dtf.tex | 57 +++++++++++++++++++++++------------------ 1 file changed, 32 insertions(+), 25 deletions(-) (limited to 'buch/papers/reedsolomon/dtf.tex') 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. + -- cgit v1.2.1 From 0cd67d0c23d8781999522a05cf2c5c49e76e3326 Mon Sep 17 00:00:00 2001 From: JODBaer Date: Fri, 30 Jul 2021 11:41:58 +0200 Subject: save --- buch/papers/reedsolomon/dtf.tex | 86 +++++++++++++++++++++-------------------- 1 file changed, 45 insertions(+), 41 deletions(-) (limited to 'buch/papers/reedsolomon/dtf.tex') diff --git a/buch/papers/reedsolomon/dtf.tex b/buch/papers/reedsolomon/dtf.tex index e9717c8..5cee77b 100644 --- a/buch/papers/reedsolomon/dtf.tex +++ b/buch/papers/reedsolomon/dtf.tex @@ -1,15 +1,13 @@ % -% teil3.tex -- Beispiel-File für Teil 3 +% dtf.tex -- Idee mit DFT % -% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil -% -\section{Übertragung mit hilfe der Diskrete Fourier Transformation +\section{Übertragung mit Hilfe der Diskrten Fourientransformation \label{reedsolomon:section:dtf}} \rhead{Umwandlung mit DTF} -Um die Polynominterpolation zu umgehen, gehen wir nun über in die Fourientransformation. +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 Fourientransformation auf Fehler reagiert. -Das ganze zeigen wir mit einem Beispiel einer Übertragung von Zahlen mit Hilfe der Fourientransformation. +Dieser Abschnitt zeigt nur wie die Fourietransformation auf Fehler reagiert. +Das ganze zeigen wir mit einem Beispiel einer Übertragung von Zahlen mit Hilfe der Fourietransformation. \subsection{Diskrete Fourietransformation Zusamenhang \label{reedsolomon:subsection:dtfzusamenhang}} @@ -17,63 +15,69 @@ Mit hilfe der Fourietransformation werden die \textcolor{blue}{blauen Datenpunkt 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 mit Fourientransformation +\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, +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, Zahlen welche übertragen werden sollen. -Dabei zusätzlich nach 16 Fehler abgesichert, macht insgesamt 96 Übertragungszahlen. -(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 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. -\item Nimmt man nun nur diese Stellen 64 bis 96, dies definieren wir als Syndrom, und transformiert nur dieses Syndrom. -\item Bekommt man die Fehlerstellen wieder, zwar nichtso genau, dennoch erkennt man wo die Fehler stattgefunden haben. -Dies definieren wir als Locator. -\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. - + \item Das Signal hat 64 die Daten $k$, hier zufällige Zahlen, welche übertragen werden sollen. + Zusätzlich soll nach 16 Fehler $t$, die rekonstruierbar sind abgesichert werden. + Das macht dann insgesamt $k + 2t = + 64 +2 \cdot 16= 96$ Übertragungszahlen. + (siehe Abschnitt \externaldocument{papers/reedsolomon/idee}\ref{reedsolomon:section:Fehlerkorrekturstellen}) + Die 32 Fehlerkorrekturstellen werden als Nullzahlen Übertragen. + \item Nun werden mittels der diskreten Fourietransformation diese 96 codiert, transformiert. + Das heisst alle Informationen ist in alle Zahlenvorhanden, auch die Fehlerkorrekturstellen Nullzahlen. + \item Nun kommen drei Fehler dazu an den Übertragungsstellen 7, 21 und 75. + Die Fehler können auf den ganzen 96 Übertragungswerten liegen, wie die 75 zeigt. +Zu Beachten ist auch noch, dass der Fehler um das 20- bis 150-Fache kleiner ist.Die Fehlerskala ist rechts. + \item Dieses wird nun Empfangen, man kann keine Fehler erkennen, da diese soviel kleiner sind. + Für das Decodieren wird die Inverse Fourietransformation angewendet, und alle Fehler werden mittransformiert. + \item Nun sieht man die Fehler im decodierten Signal in den Übertragungszahlen. + Von den Übertragungsstellen 64 bis 96 erkennt man, das diese nicht mehr Null sind. + \item Diese Fehlerkorrekturstellen 64 bis 96, dies definieren wir als Syndrom. + In diesem Syndrom ist die Fehlerinformation gespeichert und muss nur noch transformiert werden. + \item Hier sieht man genau wo die Fehler stattgefunden haben. + Leider nicht mehr mit der Qualtiätt der Ursprünglichen Fehler, sie sind nur noch 0.6 oder 0.4 gross. + Obwohl der Fehler um das 20Fache kleiner ist erkennt man im Locator die Fehlerstellen wieder. + \end{enumerate} + Nun haben wir mit Hilfe der Fourietransformation die 3 Fehlerstellen durch das Syndrom lokalisiert, + jetzt gilt es nur noch diese zu korrigieren und wir haben unser originales Signal wieder. \begin{figure} \centering - \resizebox{\textwidth}{!}{ - \includegraphics[width=\textwidth]{papers/reedsolomon/figures/plotfft} - %\input{papers/reedsolomon/images/plotfft.tex} + \resizebox{1.1\textwidth}{!}{ + %\includegraphics[width=\textwidth]{papers/reedsolomon/figures/plotfft} + \input{papers/reedsolomon/tikz/plotfftraw.tex} } \caption{Übertragungsabfolge \ref{reedsolomon:subsection:Übertragungsabfolge}} \label{fig:sendorder} \end{figure} -Nun zur definition der Diskrete Fourietransformation, diese ist definiert als -\begin{equation} +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} + \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} + \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. + \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, -- cgit v1.2.1 From b9cca93f61c5a1200503c75ef548ab12cce21887 Mon Sep 17 00:00:00 2001 From: JODBaer Date: Fri, 30 Jul 2021 11:45:36 +0200 Subject: sourc from tikz changed to pdf --- buch/papers/reedsolomon/dtf.tex | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'buch/papers/reedsolomon/dtf.tex') diff --git a/buch/papers/reedsolomon/dtf.tex b/buch/papers/reedsolomon/dtf.tex index 5cee77b..4552bed 100644 --- a/buch/papers/reedsolomon/dtf.tex +++ b/buch/papers/reedsolomon/dtf.tex @@ -50,8 +50,8 @@ Zu Beachten ist auch noch, dass der Fehler um das 20- bis 150-Fache kleiner ist. \begin{figure} \centering \resizebox{1.1\textwidth}{!}{ - %\includegraphics[width=\textwidth]{papers/reedsolomon/figures/plotfft} - \input{papers/reedsolomon/tikz/plotfftraw.tex} + \includegraphics[width=\textwidth]{papers/reedsolomon/figures/plotfft} + %\input{papers/reedsolomon/tikz/plotfftraw.tex} } \caption{Übertragungsabfolge \ref{reedsolomon:subsection:Übertragungsabfolge}} \label{fig:sendorder} -- cgit v1.2.1 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 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'buch/papers/reedsolomon/dtf.tex') 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, -- 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/dtf.tex') 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 +++++-- 1 file changed, 5 insertions(+), 2 deletions(-) (limited to 'buch/papers/reedsolomon/dtf.tex') 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. -- 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 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'buch/papers/reedsolomon/dtf.tex') 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}{!}{ -- cgit v1.2.1 From 787033c0f57c0890d2c248e95df70281546b3313 Mon Sep 17 00:00:00 2001 From: JODBaer Date: Mon, 9 Aug 2021 11:21:36 +0200 Subject: orthofehler korrigiert --- buch/papers/reedsolomon/dtf.tex | 67 ++++++++++++++++++++--------------------- 1 file changed, 32 insertions(+), 35 deletions(-) (limited to 'buch/papers/reedsolomon/dtf.tex') diff --git a/buch/papers/reedsolomon/dtf.tex b/buch/papers/reedsolomon/dtf.tex index 179d90d..559ea1b 100644 --- a/buch/papers/reedsolomon/dtf.tex +++ b/buch/papers/reedsolomon/dtf.tex @@ -4,15 +4,15 @@ \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, -durch die Codierung, auf viele übertragene Werte verteilt werden. +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. +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. \par Es liegt daher nahe zu versuchen, die Fourier-Transformation für Codierung und Decodierung zu verwenden. @@ -24,15 +24,15 @@ 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, +Der Auftrag ist nun 64 Datenwerte zu übertragen, 32 Fehler zu erkennen und 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. -\begin{figure} +\begin{figure}%[!ht] \centering \resizebox{\textwidth}{!}{ - \includegraphics[width=\textwidth]{papers/reedsolomon/figures/plotfft} + \includegraphics[width=\textwidth]{papers/reedsolomon/figures/fourier} %\input{papers/reedsolomon/tikz/plotfftraw.tex} } \caption{Übertragungsabfolge \ref{reedsolomon:subsection:sendbsp}} @@ -41,34 +41,33 @@ Durch eine Rücktransformation könnnen die \textcolor{blue}{blauen Datenpunkte} 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. + \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 - \externaldocument{papers/reedsolomon/idee}\ref{reedsolomon:section:Fehlerkorrekturstellen}. - Wir erhalten so einen erweiterten Signalvektor der länge $N =96$. + Diese setzen wir willkürlich 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. - \item Wir dürfen annehmen, dass bei der Übertragung, nur einzelne übertragene Werte durch Fehler, - verändert werden. + \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. + 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 - wiederhergestellt werden. + \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. + 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. + \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. + \item Um die Fehler zu rekonstruieren, kann man versuchen, die Information im Syndrom mit Fourier-Transformation zu transformieren. Da das Syndrom nur ein Teil der Fehlerinformation ist, liefert die Fourier-Transformation eine Approximation der Fehler. - Diese Approximation der Fehler ist genau genug, um die Fehlerstellen zu localisieren. + Diese Approximation der Fehler ist genau genug, um die Fehlerstellen zu lokalisieren. \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. +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. @@ -87,8 +86,7 @@ Die 7 Übertragungspunkte könnten ein Polynom \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. +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 @@ -101,25 +99,24 @@ Die Analogie geht aber noch weiter. {f}_n \cdot e^{-\frac{2\pi j}{N} \cdot kn} ,\label{reedsolomon:DFT} \end{equation} - für die Diskrte-Fourier-Transformation das Polynom + für die diskrete-Fourier-Transformation das Polynom \begin{equation} 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} + \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} - 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. + Im Beispiel werden aber Werte des Polynoms \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} \label{reedsolomon:DFT_polynom2} \end{equation} -Das syndrom entstand durch die Wahl ${f_{64}}=0$ bis ${f}_{N-1}=0$.(graue koeffizenten) + für verschiedene \( w = e^{-\frac{2\pi j}{N} k}, k=1, \dots ,N-1\) übermittelt. +Das Syndrom entstand durch die Wahl ${f_{64}}=0$ bis ${f}_{N-1}=0$.(graue koeffizenten) \par -Die Polynominterpolation und die Fourier-Transformation rechnen beide mit reelen Zahlen. +Die Polynominterpolation und die Fourier-Transformation rechnen beide mit reeleen Zahlen. 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. +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. -- cgit v1.2.1 From f54db89a60364ccec5822ab025d2caadb52def8c Mon Sep 17 00:00:00 2001 From: JODBaer Date: Mon, 9 Aug 2021 13:45:45 +0200 Subject: feinheiten --- buch/papers/reedsolomon/dtf.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'buch/papers/reedsolomon/dtf.tex') diff --git a/buch/papers/reedsolomon/dtf.tex b/buch/papers/reedsolomon/dtf.tex index 559ea1b..7c88c16 100644 --- a/buch/papers/reedsolomon/dtf.tex +++ b/buch/papers/reedsolomon/dtf.tex @@ -1,7 +1,7 @@ % % dtf.tex -- Idee mit DFT % -\section{Übertragung mit Hilfe der Diskrten Fourier-Transformation +\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 -- cgit v1.2.1