From d223220e4fdd827a5c0dd76e3d7b1453876f3e4b Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Sun, 8 Aug 2021 11:47:57 +0200 Subject: add image to reedsolomon --- buch/papers/reedsolomon/tikz/Makefile | 7 ++ buch/papers/reedsolomon/tikz/fourier.pdf | Bin 0 -> 59496 bytes buch/papers/reedsolomon/tikz/fourier.tex | 132 +++++++++++++++++++++++++++++++ 3 files changed, 139 insertions(+) create mode 100644 buch/papers/reedsolomon/tikz/Makefile create mode 100644 buch/papers/reedsolomon/tikz/fourier.pdf create mode 100644 buch/papers/reedsolomon/tikz/fourier.tex (limited to 'buch/papers/reedsolomon') diff --git a/buch/papers/reedsolomon/tikz/Makefile b/buch/papers/reedsolomon/tikz/Makefile new file mode 100644 index 0000000..1753f37 --- /dev/null +++ b/buch/papers/reedsolomon/tikz/Makefile @@ -0,0 +1,7 @@ +# +# Makefile +# +# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +# +fourier.pdf: fourier.tex + pdflatex fourier.tex diff --git a/buch/papers/reedsolomon/tikz/fourier.pdf b/buch/papers/reedsolomon/tikz/fourier.pdf new file mode 100644 index 0000000..a1b6e24 Binary files /dev/null and b/buch/papers/reedsolomon/tikz/fourier.pdf differ diff --git a/buch/papers/reedsolomon/tikz/fourier.tex b/buch/papers/reedsolomon/tikz/fourier.tex new file mode 100644 index 0000000..af556d1 --- /dev/null +++ b/buch/papers/reedsolomon/tikz/fourier.tex @@ -0,0 +1,132 @@ +% +% Plot der Übertrangungsabfolge ins FFT und zurück mit IFFT +% +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{times} +\usepackage{pgfplots} +\usepackage{pgfplotstable} +\usepackage{csvsimple} +\usepackage{filecontents} + +\def\plotwidth{7.5cm} +\def\plotheight{5.5cm} +\def\xverschiebung{4.5cm} +\def\yverschiebung{-7cm} +\def\yyverschiebung{-14cm} + +\def\marke#1{ + \coordinate (M) at (-0.8,4.6); + \fill[color=lightgray] (M) circle[radius=0.3]; + \draw (M) circle[radius=0.3]; + \node at (M) {#1}; +} + +\begin{document} +\begin{tikzpicture}[>=latex,thick] + +\draw[dashed,line width=2pt,color=lightgray] (2.6,4.4) -- (2.6,-14.3); +\coordinate (B) at (2.6,-1.3); +\node[color=gray] at (B) [rotate=90,above] {Zeitbereich}; +\node[color=gray] at (B) [rotate=90,below] {Frequenzbereich}; + +\begin{scope}[xshift=-\xverschiebung,yshift=0cm] + \begin{axis} + [title = {\large Signal\strut}, + xtick={0,32,64,96}, width=\plotwidth,height=\plotheight] + \addplot[blue,line width=1pt] table[col sep=comma] + {tikz/signal.txt}; + \end{axis} + \marke{1} +\end{scope} + +\begin{scope}[xshift=\xverschiebung,yshift=0cm] + \begin{axis}[axis x line= none, axis y line*=right,ytick={0}, + width=\plotwidth,height=\plotheight] + \addplot[color=white] {0}; + \end{axis} + + \begin{axis}[title = {\large Codiert\strut}, axis y line*=left, + xtick={0,32,64,96}, + width=\plotwidth,height=\plotheight] + \addplot[color=black!60!green,line width=1pt] + table[col sep=comma] + {tikz/codiert.txt}; + \end{axis} + \marke{2} + \draw[->,line width=1pt] (3,-0.4) -- node[right] {Übertragung} (3,-2.2); +\end{scope} + +\definecolor{pink}{rgb}{0.6,0.2,1} + +\begin{scope}[xshift=-\xverschiebung,yshift=\yverschiebung] + \fill[color=pink!20] (4.65,0.35) ellipse (1.1cm and 0.5cm); + \begin{axis}[title = {\large Decodiert\strut}, + xtick={0,32,64,96}, + width=\plotwidth,height=\plotheight] + \addplot[blue,line width=1pt] + table[col sep=comma] {tikz/decodiert.txt}; + \end{axis} + \marke{4} + \draw[color=pink] (4.65,0.35) ellipse (1.1cm and 0.5cm); + \draw[->,color=pink,line width=1pt] + (4.65,-0.15) to[out=-90,in=90] (3,-2.2); +\end{scope} + +\begin{scope}[xshift=\xverschiebung,yshift=\yverschiebung] + \begin{axis}[title = {\large Empfangen {\color{red} mit Fehler}\strut}, + xtick={0,96}, + axis y line*=left, + width=\plotwidth,height=\plotheight] + \addplot[color=black!60!green,line width=1pt] + table[col sep=comma] + {tikz/empfangen.txt}; + \end{axis} + \begin{axis}[xtick={6,20,74}, axis y line*=right, + width=\plotwidth,height=\plotheight] + \addplot[red,line width=1pt] + table[col sep=comma] {tikz/fehler.txt}; + \end{axis} + \marke{3} +\end{scope} + +\begin{scope}[xshift=-\xverschiebung,yshift=\yyverschiebung] + \begin{axis}[title = {\large \color{pink}Syndrom\strut}, + xtick={0,32,64,96}, + width=\plotwidth,height=\plotheight] + \addplot[pink,line width=1pt] + table[col sep=comma] {tikz/syndrom.txt}; + \end{axis} + \marke{5} +\end{scope} + +\begin{scope}[xshift=\xverschiebung,yshift=\yyverschiebung] + % Beschriftung Rechts + \begin{axis}[axis x line= none, axis y line*=right, ytick={0.3}, + xtick={0,32,64,96}, + width=\plotwidth,height=\plotheight] + \addplot[color=black!60,line width=1pt] {0.3}; + \end{axis} + \begin{axis}[title = {\large Locator\strut},axis y line*=left, + xtick={0,6,20,74,96}, + width=\plotwidth,height=\plotheight] + \addplot[gray,line width=1pt] + table[col sep=comma] {tikz/locator.txt}; + \end{axis} + \marke{6} +\end{scope} + +% Fourier-Transformations-Pfeile + +\draw[->,line width=1pt] (1.8,2) -- node[above] {DFT\strut} (3.8,2); + +\begin{scope}[yshift=\yverschiebung] +\draw[<-,line width=1pt] (1.8,2) -- node[above] {DFT$\mathstrut^{-1}$} (3.8,2); +\end{scope} + +\begin{scope}[yshift=\yyverschiebung] +\draw[->,line width=1pt] (1.8,2) -- node[above] {DFT\strut} (3.8,2); +\end{scope} + +\end{tikzpicture} +\end{document} -- cgit v1.2.1 From 08ea2ca03c7cc6dc99550dc0c768ad690b7e96bb Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Sun, 8 Aug 2021 12:56:13 +0200 Subject: improve spacing --- buch/papers/reedsolomon/tikz/fourier.pdf | Bin 59496 -> 59500 bytes buch/papers/reedsolomon/tikz/fourier.tex | 4 ++-- 2 files changed, 2 insertions(+), 2 deletions(-) (limited to 'buch/papers/reedsolomon') diff --git a/buch/papers/reedsolomon/tikz/fourier.pdf b/buch/papers/reedsolomon/tikz/fourier.pdf index a1b6e24..b200458 100644 Binary files a/buch/papers/reedsolomon/tikz/fourier.pdf and b/buch/papers/reedsolomon/tikz/fourier.pdf differ diff --git a/buch/papers/reedsolomon/tikz/fourier.tex b/buch/papers/reedsolomon/tikz/fourier.tex index af556d1..d5a8d06 100644 --- a/buch/papers/reedsolomon/tikz/fourier.tex +++ b/buch/papers/reedsolomon/tikz/fourier.tex @@ -27,8 +27,8 @@ \draw[dashed,line width=2pt,color=lightgray] (2.6,4.4) -- (2.6,-14.3); \coordinate (B) at (2.6,-1.3); -\node[color=gray] at (B) [rotate=90,above] {Zeitbereich}; -\node[color=gray] at (B) [rotate=90,below] {Frequenzbereich}; +\node[color=gray] at (B) [rotate=90,above] {Zeitbereich\strut}; +\node[color=gray] at (B) [rotate=90,below] {Frequenzbereich\strut}; \begin{scope}[xshift=-\xverschiebung,yshift=0cm] \begin{axis} -- cgit v1.2.1 From 2805ea85b02609e6f7b7c2d511260ed94944722e Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Sun, 8 Aug 2021 13:34:03 +0200 Subject: mehr Farbe ;-) --- buch/papers/reedsolomon/tikz/fourier.pdf | Bin 59500 -> 59572 bytes buch/papers/reedsolomon/tikz/fourier.tex | 17 +++++++++++++++-- 2 files changed, 15 insertions(+), 2 deletions(-) (limited to 'buch/papers/reedsolomon') diff --git a/buch/papers/reedsolomon/tikz/fourier.pdf b/buch/papers/reedsolomon/tikz/fourier.pdf index b200458..6491f08 100644 Binary files a/buch/papers/reedsolomon/tikz/fourier.pdf and b/buch/papers/reedsolomon/tikz/fourier.pdf differ diff --git a/buch/papers/reedsolomon/tikz/fourier.tex b/buch/papers/reedsolomon/tikz/fourier.tex index d5a8d06..bbe0508 100644 --- a/buch/papers/reedsolomon/tikz/fourier.tex +++ b/buch/papers/reedsolomon/tikz/fourier.tex @@ -22,9 +22,14 @@ \node at (M) {#1}; } +\definecolor{darkgreen}{rgb}{0,0.6,0} + \begin{document} \begin{tikzpicture}[>=latex,thick] +\fill[color=blue!10] (-5.7,-14.5) rectangle (2.6,5.0); +\fill[color=darkgreen!10] (2.6,-14.5) rectangle (11.1,5.0); + \draw[dashed,line width=2pt,color=lightgray] (2.6,4.4) -- (2.6,-14.3); \coordinate (B) at (2.6,-1.3); \node[color=gray] at (B) [rotate=90,above] {Zeitbereich\strut}; @@ -33,7 +38,9 @@ \begin{scope}[xshift=-\xverschiebung,yshift=0cm] \begin{axis} [title = {\large Signal\strut}, - xtick={0,32,64,96}, width=\plotwidth,height=\plotheight] + xtick={0,32,64,96}, + axis background/.style={fill=white}, + width=\plotwidth,height=\plotheight] \addplot[blue,line width=1pt] table[col sep=comma] {tikz/signal.txt}; \end{axis} @@ -42,12 +49,14 @@ \begin{scope}[xshift=\xverschiebung,yshift=0cm] \begin{axis}[axis x line= none, axis y line*=right,ytick={0}, + axis background/.style={fill=white}, width=\plotwidth,height=\plotheight] \addplot[color=white] {0}; \end{axis} \begin{axis}[title = {\large Codiert\strut}, axis y line*=left, xtick={0,32,64,96}, + axis background/.style={fill=white}, width=\plotwidth,height=\plotheight] \addplot[color=black!60!green,line width=1pt] table[col sep=comma] @@ -60,9 +69,10 @@ \definecolor{pink}{rgb}{0.6,0.2,1} \begin{scope}[xshift=-\xverschiebung,yshift=\yverschiebung] - \fill[color=pink!20] (4.65,0.35) ellipse (1.1cm and 0.5cm); + %\fill[color=pink!20] (4.65,0.35) ellipse (1.1cm and 0.5cm); \begin{axis}[title = {\large Decodiert\strut}, xtick={0,32,64,96}, + axis background/.style={fill=white}, width=\plotwidth,height=\plotheight] \addplot[blue,line width=1pt] table[col sep=comma] {tikz/decodiert.txt}; @@ -76,6 +86,7 @@ \begin{scope}[xshift=\xverschiebung,yshift=\yverschiebung] \begin{axis}[title = {\large Empfangen {\color{red} mit Fehler}\strut}, xtick={0,96}, + axis background/.style={fill=white}, axis y line*=left, width=\plotwidth,height=\plotheight] \addplot[color=black!60!green,line width=1pt] @@ -93,6 +104,7 @@ \begin{scope}[xshift=-\xverschiebung,yshift=\yyverschiebung] \begin{axis}[title = {\large \color{pink}Syndrom\strut}, xtick={0,32,64,96}, + axis background/.style={fill=white}, width=\plotwidth,height=\plotheight] \addplot[pink,line width=1pt] table[col sep=comma] {tikz/syndrom.txt}; @@ -104,6 +116,7 @@ % Beschriftung Rechts \begin{axis}[axis x line= none, axis y line*=right, ytick={0.3}, xtick={0,32,64,96}, + axis background/.style={fill=white}, width=\plotwidth,height=\plotheight] \addplot[color=black!60,line width=1pt] {0.3}; \end{axis} -- cgit v1.2.1 From b76522a3dda77a3319d92c901b5e27586686c3d2 Mon Sep 17 00:00:00 2001 From: michael-OST <75078383+michael-OST@users.noreply.github.com> Date: Sun, 8 Aug 2021 15:53:09 +0200 Subject: chapters updated --- buch/papers/reedsolomon/codebsp.tex | 2 +- buch/papers/reedsolomon/endlichekoerper.tex | 69 +++++++++++++++++++++++------ 2 files changed, 56 insertions(+), 15 deletions(-) (limited to 'buch/papers/reedsolomon') diff --git a/buch/papers/reedsolomon/codebsp.tex b/buch/papers/reedsolomon/codebsp.tex index 8430ebd..eb4e82f 100644 --- a/buch/papers/reedsolomon/codebsp.tex +++ b/buch/papers/reedsolomon/codebsp.tex @@ -76,7 +76,7 @@ dar. \subsection{Der Ansatz der diskreten Fouriertransformation \label{reedsolomon:subsection:diskFT}} -In einem vorherigen Abschnitt \textcolor{red}{(???)} haben wir schon einmal die diskrete Fouriertransformation zum Codieren einer Nachricht verwendet. In den endlichen Körpern wird dies jedoch nicht gelingen, da die Eulerische Zahl $e$ in endlichen Körpern nicht existiert. +Im vorherigen Abschnitt \ref{reedsolomon:section:dtf} haben wir schon einmal die diskrete Fouriertransformation zum Codieren einer Nachricht verwendet. In den endlichen Körpern wird dies jedoch nicht gelingen, da die Eulerische Zahl $e$ in endlichen Körpern nicht existiert. Wir wählen deshalb eine Zahl $a$, die die gleichen Aufgaben haben soll wie $e^{\frac{j}{2 \pi}}$ in der diskreten Fouriertransformation, nur mit dem Unterschied, dass $a$ in $\mathbb{F}_{11}$ ist. Dazu soll die Potenz von $a$ den gesamten Zahlenbereich von $\mathbb{F}_{11}$ abdecken. Dazu ändern wir die Darstellung von \[ diff --git a/buch/papers/reedsolomon/endlichekoerper.tex b/buch/papers/reedsolomon/endlichekoerper.tex index 1d196fd..d70125b 100644 --- a/buch/papers/reedsolomon/endlichekoerper.tex +++ b/buch/papers/reedsolomon/endlichekoerper.tex @@ -3,21 +3,62 @@ % % (c) 2021 Michael Steiner, Hochschule Rapperswil % -\section{Reed-Solomon in Endlichen Körpern +\section{Reed-Solomon in endlichen Körpern \label{reedsolomon:section:endlichekoerper}} \rhead{Reed-Solomon in endlichen Körpern} -\[ -\textcolor{red}{\text{TODO: (warten auf den 1. Teil)}} -\] -Das Rechnen in endlichen Körpern bietet einige Vorteile: +Im vorherigen Abschnitt haben wir gesehen, dass wir die Fehler mittels Approximation suchen und somit keine Konkreten Angaben haben, wo sich Fehler garantiert aufhalten. +Um dies zu ändern wechseln wir vom Komplexen Zahlenraum in den endlichen Körper. +In endlichen Körpern gibt es weder rationale noch komplexe Zahlen. +Zudem beschränken sich die möglichen arithmetischen Rechenoperationen auf das Addieren und Multiplizieren. +Wir können also nur ganze Zahlen als Resultat erhalten. +Dies erleichtert auch die Umsetzung auf ein digitales System, da Computer in der Regel lieber mit ganzen als mit gebrochenen oder komplexen Zahlen arbeiten. -\begin{itemize} - \item Konkrete Zahlen: In endlichen Körpern gibt es weder rationale noch komplexe Zahlen. Zudem beschränken sich die möglichen Rechenoperationen auf das Addieren und Multiplizieren. Somit können wir nur ganze Zahlen als Resultat erhalten. - - \item Digitale Fehlerkorrektur: lässt sich nur in endlichen Körpern umsetzen. - -\end{itemize} +Um jetzt eine Nachricht in den endlichen Körpern zu konstruieren gehen wir im Grunde gleich vor wie im Beispiel aus dem Abschnitt \ref{reedsolomon:subsection:sendbsp}. +Eine Nachricht besteht aus einem Nutzdatenteil und einem Fehlerkorrekturteil. +Diese Nachricht wird Codiert, übertragen und beim Empfänger wieder decodiert. +In endlichen Körpern können wir jedoch nicht mehr die Fouriertransformation uns zur Hilfe nehmen. +Wir müssen also eine Alternative finden, welche die gleichen Eigenschaften wie die Fouriertransformation aufweist, aber im endlichen Körper verwendet werden kann. +Auch beim decodieren müssen wir uns etwas einfallen lassen, damit die Vorgehensweise mit dem Lokatorpolynom auch in endlichen Körpern funktionieren soll. Die folgenden Abschnitte widmen sich deshalb der genaueren Betrachtung eines Reed-Solomon-Codes und wie er in endlichen Körpern funktioniert. -Um jetzt eine Nachricht in den endlichen Körpern zu konstruieren legen wir fest, dass diese Nachricht aus einem Nutzdatenteil und einem Fehlerkorrekturteil bestehen muss. Somit ist die zu übertragende Nachricht immer grösser als die Daten, die wir übertragen wollen. Zudem müssen wir einen Weg finden, den Fehlerkorrekturteil so aus den Nutzdaten zu berechnen, dass wir die Nutzdaten auf der Empfängerseite wieder rekonstruieren können, sollte es zu einer fehlerhaften Übertragung kommen. - -Nun stellt sich die Frage, wie wir eine fehlerhafte Nachricht korrigieren können, ohne ihren ursprünglichen Inhalt zu kennen. Der Reed-Solomon-Code erzielt dies, indem aus dem Fehlerkorrekturteil ein sogenanntes ``Lokatorpolynom'' generiert werden kann. Dieses Polynom gibt dem Emfänger an, welche Stellen in der Nachricht feherhaft sind. +% +%Damit all diese Probleme möglichst verständlich +% +% +%Um all diese Probleme und möglichst +% +% +%um Fehler zu erkennen und mittels Lokatorpolynom +% +% +% ein Lokatorpolynom zu finden. +% +% +% +% Eine Nachricht besteht aus einem Nutzdatenanteil und einem Fehlerkorrekturteil, +% +% +% +%In diesem Zahlenraum gibt es nur Natürliche Zahlen und es darf nur Addiert oder Multipliziert werden. +%Der grosse Vorteil an endlichen Körper ist, dass dich der einfacher Digital umsetzen lässt. +% +% +%Dieser Zahlenraum bringt eine Menge von neuen Regeln mit sich. +%So gibt es dort nur Natürliche Zahlen und die Arithmetischen Rechenoperationen sind beschränkt auf die Addition und Multiplikation. +% +% +% +%\[ +%\textcolor{red}{\text{TODO: (warten auf den 1. Teil)}} +%\] +%Das Rechnen in endlichen Körpern bietet einige Vorteile: +% +%\begin{itemize} +% \item Konkrete Zahlen: In endlichen Körpern gibt es weder rationale noch komplexe Zahlen. Zudem beschränken sich die möglichen Rechenoperationen auf das Addieren und Multiplizieren. Somit können wir nur ganze Zahlen als Resultat erhalten. +% +% \item Digitale Fehlerkorrektur: lässt sich nur in endlichen Körpern umsetzen. +% +%\end{itemize} +% +%Um jetzt eine Nachricht in den endlichen Körpern zu konstruieren legen wir fest, dass diese Nachricht aus einem Nutzdatenteil und einem Fehlerkorrekturteil bestehen muss. Somit ist die zu übertragende Nachricht immer grösser als die Daten, die wir übertragen wollen. Zudem müssen wir einen Weg finden, den Fehlerkorrekturteil so aus den Nutzdaten zu berechnen, dass wir die Nutzdaten auf der Empfängerseite wieder rekonstruieren können, sollte es zu einer fehlerhaften Übertragung kommen. +% +%Nun stellt sich die Frage, wie wir eine fehlerhafte Nachricht korrigieren können, ohne ihren ursprünglichen Inhalt zu kennen. Der Reed-Solomon-Code erzielt dies, indem aus dem Fehlerkorrekturteil ein sogenanntes ``Lokatorpolynom'' generiert werden kann. Dieses Polynom gibt dem Emfänger an, welche Stellen in der Nachricht feherhaft sind. -- cgit v1.2.1 From 8f68f18b9745cec1257e1e1fef9a2c9076839ddd Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Sun, 8 Aug 2021 20:17:16 +0200 Subject: trennlinie zwischen Zeit/Frequenzbereich --- buch/papers/reedsolomon/tikz/fourier.pdf | Bin 59572 -> 59767 bytes buch/papers/reedsolomon/tikz/fourier.tex | 6 +++--- 2 files changed, 3 insertions(+), 3 deletions(-) (limited to 'buch/papers/reedsolomon') diff --git a/buch/papers/reedsolomon/tikz/fourier.pdf b/buch/papers/reedsolomon/tikz/fourier.pdf index 6491f08..25e8d6d 100644 Binary files a/buch/papers/reedsolomon/tikz/fourier.pdf and b/buch/papers/reedsolomon/tikz/fourier.pdf differ diff --git a/buch/papers/reedsolomon/tikz/fourier.tex b/buch/papers/reedsolomon/tikz/fourier.tex index bbe0508..d151b2b 100644 --- a/buch/papers/reedsolomon/tikz/fourier.tex +++ b/buch/papers/reedsolomon/tikz/fourier.tex @@ -30,7 +30,7 @@ \fill[color=blue!10] (-5.7,-14.5) rectangle (2.6,5.0); \fill[color=darkgreen!10] (2.6,-14.5) rectangle (11.1,5.0); -\draw[dashed,line width=2pt,color=lightgray] (2.6,4.4) -- (2.6,-14.3); +\draw[dashed,line width=2pt,color=lightgray] (2.6,4.9) -- (2.6,-14.4); \coordinate (B) at (2.6,-1.3); \node[color=gray] at (B) [rotate=90,above] {Zeitbereich\strut}; \node[color=gray] at (B) [rotate=90,below] {Frequenzbereich\strut}; @@ -84,7 +84,7 @@ \end{scope} \begin{scope}[xshift=\xverschiebung,yshift=\yverschiebung] - \begin{axis}[title = {\large Empfangen {\color{red} mit Fehler}\strut}, + \begin{axis}[title = {\large Empfangen {\color{red} mit Fehlern}\strut}, xtick={0,96}, axis background/.style={fill=white}, axis y line*=left, @@ -120,7 +120,7 @@ width=\plotwidth,height=\plotheight] \addplot[color=black!60,line width=1pt] {0.3}; \end{axis} - \begin{axis}[title = {\large Locator\strut},axis y line*=left, + \begin{axis}[title = {\large Lokator\strut},axis y line*=left, xtick={0,6,20,74,96}, width=\plotwidth,height=\plotheight] \addplot[gray,line width=1pt] -- cgit v1.2.1 From 89874953eb8c9d2e4ac9bb1cfe77a4e7e2ace9a3 Mon Sep 17 00:00:00 2001 From: michael-OST <75078383+michael-OST@users.noreply.github.com> Date: Sun, 8 Aug 2021 21:32:38 +0200 Subject: minor improvements --- buch/papers/reedsolomon/endlichekoerper.tex | 17 +++++++++-------- 1 file changed, 9 insertions(+), 8 deletions(-) (limited to 'buch/papers/reedsolomon') diff --git a/buch/papers/reedsolomon/endlichekoerper.tex b/buch/papers/reedsolomon/endlichekoerper.tex index d70125b..3019dd7 100644 --- a/buch/papers/reedsolomon/endlichekoerper.tex +++ b/buch/papers/reedsolomon/endlichekoerper.tex @@ -6,19 +6,20 @@ \section{Reed-Solomon in endlichen Körpern \label{reedsolomon:section:endlichekoerper}} \rhead{Reed-Solomon in endlichen Körpern} -Im vorherigen Abschnitt haben wir gesehen, dass wir die Fehler mittels Approximation suchen und somit keine Konkreten Angaben haben, wo sich Fehler garantiert aufhalten. -Um dies zu ändern wechseln wir vom Komplexen Zahlenraum in den endlichen Körper. -In endlichen Körpern gibt es weder rationale noch komplexe Zahlen. -Zudem beschränken sich die möglichen arithmetischen Rechenoperationen auf das Addieren und Multiplizieren. +Im vorherigen Abschnitt haben wir gesehen, dass wir die Fehler mittels Approximation suchen und somit nur ungefähre Angaben haben, wo sich Fehler aufhalten. +Um dies zu ändern wechseln wir vom komplexen Zahlenraum in endliche Körper. +In endlichen Körpern gibt es keine Approximationen wie bei den rationalen und reellen Zahlen. +Alle Zahlen sind richtig oder falsch, ``fast richtig'' gibt es nicht. +Zudem beschränken sich die arithmetischen Rechenoperationen auf das Addieren und Multiplizieren. Wir können also nur ganze Zahlen als Resultat erhalten. Dies erleichtert auch die Umsetzung auf ein digitales System, da Computer in der Regel lieber mit ganzen als mit gebrochenen oder komplexen Zahlen arbeiten. -Um jetzt eine Nachricht in den endlichen Körpern zu konstruieren gehen wir im Grunde gleich vor wie im Beispiel aus dem Abschnitt \ref{reedsolomon:subsection:sendbsp}. +Um jetzt eine Nachricht in einem endlichen Körpern zu konstruieren gehen, wir im Grunde gleich vor wie im Beispiel aus dem Abschnitt \ref{reedsolomon:subsection:sendbsp}. Eine Nachricht besteht aus einem Nutzdatenteil und einem Fehlerkorrekturteil. -Diese Nachricht wird Codiert, übertragen und beim Empfänger wieder decodiert. -In endlichen Körpern können wir jedoch nicht mehr die Fouriertransformation uns zur Hilfe nehmen. +Diese Nachricht wird codiert, übertragen und beim Empfänger wieder decodiert. +In endlichen Körpern können wir jedoch nicht mehr die Fouriertransformation zur Hilfe nehmen. Wir müssen also eine Alternative finden, welche die gleichen Eigenschaften wie die Fouriertransformation aufweist, aber im endlichen Körper verwendet werden kann. -Auch beim decodieren müssen wir uns etwas einfallen lassen, damit die Vorgehensweise mit dem Lokatorpolynom auch in endlichen Körpern funktionieren soll. Die folgenden Abschnitte widmen sich deshalb der genaueren Betrachtung eines Reed-Solomon-Codes und wie er in endlichen Körpern funktioniert. +Auch beim Decodieren müssen wir uns etwas einfallen lassen, wenn die Vorgehensweise mit dem Lokator auch in endlichen Körpern funktionieren soll. Die folgenden Abschnitte widmen sich deshalb der genaueren Betrachtung eines Reed-Solomon-Codes und wie er in endlichen Körpern funktioniert. % %Damit all diese Probleme möglichst verständlich -- 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 ++++++++++++------------- buch/papers/reedsolomon/einleitung.tex | 2 +- buch/papers/reedsolomon/figures/plotfft.pdf | Bin 59772 -> 59772 bytes buch/papers/reedsolomon/idee.tex | 74 ++++++++++++++-------------- 4 files changed, 71 insertions(+), 72 deletions(-) (limited to 'buch/papers/reedsolomon') 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. diff --git a/buch/papers/reedsolomon/einleitung.tex b/buch/papers/reedsolomon/einleitung.tex index ca4f398..04f1fe2 100644 --- a/buch/papers/reedsolomon/einleitung.tex +++ b/buch/papers/reedsolomon/einleitung.tex @@ -6,7 +6,7 @@ \section{Einleitung \label{reedsolomon:section:einleitung}} \rhead{Einleitung} -Der Reed-Solomon-Code wurde von den beiden Mathematiker Irving S.Reed und Gustave Solomon, im Jahre 1960, entwickelt. +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. diff --git a/buch/papers/reedsolomon/figures/plotfft.pdf b/buch/papers/reedsolomon/figures/plotfft.pdf index b455da5..80adafb 100644 Binary files a/buch/papers/reedsolomon/figures/plotfft.pdf and b/buch/papers/reedsolomon/figures/plotfft.pdf differ diff --git a/buch/papers/reedsolomon/idee.tex b/buch/papers/reedsolomon/idee.tex index 2142f88..26e617c 100644 --- a/buch/papers/reedsolomon/idee.tex +++ b/buch/papers/reedsolomon/idee.tex @@ -5,18 +5,18 @@ \label{reedsolomon:section:idee}} \rhead{Problemstellung} Um Fehler in einer Datenübertragung zu erkennen, könnte man die Daten jeweils doppelt senden, - also immer zwei gleich Werte miteinander und so jeweilige einzelne Fehler erkennen. -Wenn jedoch mehr als nur ein Fehler erkennt werden soll und sogar noch das orginal rekonstruiert werden soll, + also immer zwei gleich Werte miteinander und so jeweils einzelne Fehler erkennen. +Wenn jedoch mehr als nur ein Fehler erkannt werden soll und sogar noch das Orginal rekonstruiert werden soll, dann werden die Daten drei oder vierfach versendet. Doch nur schon um Fehler zu erkennen werden überproportional viele Daten doppelt und dreifach gesendet. Das Problem liegt darin Informationen, Zahlen, zu Übertragen und Fehler zu erkennen und zu korrigieren. -Der Unterschied des Fehler 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. -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 Unterschied des Fehler Erkennens und Korrigirens, ist das beim Erkennen nur die Frage beantwortet wird: Ist die Übertragung fehlerhaft oder nicht? +Beim Korrigieren werden Fehler erkannt und dann zusätzlich noch die Originalwerte rekonstruiert. +Eine weitere Möglichkeit wäre, dass der Empfänger nach einer fehlerhaften Übertragung die selben Daten nochmals anfordert. +Dies führt wieder zu unerwünschten mehrfachen Übertragung. +In Anwendungen des Reed-Solomon-Codes Abschnitt \externaldocument{papers/reedsolomon/anwendungen} \ref{reedsolomon:section:anwendung} + ist diese vom Empfänger gesteuerte erneute Übertragen meistens nicht sinnvoll oder sogar unmöglich. Der Reed-Solomon-Code macht dies Übertragung auf eine andere, clevere Weise. \subsection{Polynom-Ansatz @@ -34,35 +34,35 @@ p(x) \end{equation}. \par Ein Polynome zweiten Grades ist durch drei Punkte eindeutig bestimmbar. -Bei einer fehlerlosen Übertragung, können wir mit 3 übertragene Werte, +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, - 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}. +Wir brauchen Polynominterpolation als Methode, um aus Punkte wieder Polynom zu berechnen. +Die Koeffizente des rekonstruierten Polynoms sind dann unsere gesendeten Zahlen \textcolor{blue}{2}, \textcolor{blue}{1}, \textcolor{blue}{5}. +\par Wie können wir nun Fehler erkennen oder sogar korrigieren? -Versuchen wir doch mehr Werte zu Übertragen, wir nehmen im Beispiel 7 Werte. +Versuchen wir doch mehr Werte zu übertragen, 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 \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 \textcolor{darkgreen}{übertragenen Werte} des Polynoms sind grün. Die grünen Punkte bestimmen die Parabel. -Damit können die Fehler erkannt werden, weil die empfangenen 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? +Damit können die Fehler erkannt werden, weil die empfangenen Punkte nicht auf der Parabel liegen. +Somit können die grauen Punkte auf der Parabel ersetzt werden und sind damit korrigiert. +Bis zu wievielen Fehler können wir nun im Beispiel korrigieren? Wir erhöhen nun die Fehleranzahl Schritt für Schritt: \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. - \item Bei \textit{2 Fehler} kann ein Fehler mit zwei originalen Punkten ein fehlleitendes Konkurrenzpolynom bilden. + \item Bei \textit{1 Fehler} können konkurrenzierende Polynome, zusammen mit zwei originalen Punkten entstehen. + Dabei können aber maximal 3 Punkte auf diesem Konkurrenzpolynom sein. + Da 6 > 3 ist haben wir unser original Polynom gefunden. + \item Bei \textit{2 Fehlern} kann ein Fehler mit zwei originalen Punkten ein 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. + Nun haben wir, ein originales Polynom mit 5 übereinstimmenden und eine konkurrenzierendes mit 4 Punkten. + Da 5 noch grösser als 4 ist, können wir sagen, welches das Originalpolynom ist. + \item Bei \textit{3 Fehlern} kann genau wie bei 2 oder 1 Fehler, ein konkurenzierendes Polynom mit einem Fehler und zwei originalen 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. - \item Bei \textit{4 Fehler} Es kann noch erkennt weden das Fehler statt gefunden haben, da 3 orginale Punkte das ursprüngliche Polynom ergeben. + Nun ist es so das 5 Punkte auf diesem konkurenzierenden Polynom und 4 Punkte auf dem originalen. + Das Originalpolynom kann nicht mehr gefunden werden. + \item Bei \textit{4 Fehlern} Es kann noch erkannt werden, dass Fehler statt gefunden haben, da 3 orginale Punkte das ursprüngliche Polynom ergeben. Somit haben wir mindestens 2 verschieden Polynome, dass bedeutet Fehler sind entstanden. \item 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. @@ -75,17 +75,18 @@ 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} +\qedhere \end{beispiel} \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. +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, braucht Redundanz. Gehen wir die Fehleranzahl mit verschiedenen Übertragungsanzahlen durch, erkennt man almählich ein Muster. -\begin{table} +\begin{table}%[!ht] \centering \begin{tabular}{ c c | c} \hline @@ -101,17 +102,18 @@ Gehen wir die Fehleranzahl mit verschiedenen Übertragungsanzahlen durch, \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. +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 zwei Ü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}. +\end{equation} 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. +Für die Polynomkoeffizente nach der Übertragung zu rekonstruieren, + haben wir jedes mal die Polynominterpolationmethode angewendet. Diese Polynoiminterpolation ist leider schwierig und fehleranfällig. Deshalb finden wir eine alternative im nächsten Abschnitt. -- 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/Makefile | 2 +- buch/papers/reedsolomon/dtf.tex | 2 +- buch/papers/reedsolomon/figures/fourier.pdf | Bin 0 -> 59770 bytes buch/papers/reedsolomon/idee.tex | 23 +++++++++++----------- buch/papers/reedsolomon/standalone/standalone.pdf | Bin 1835588 -> 1837295 bytes 5 files changed, 14 insertions(+), 13 deletions(-) create mode 100644 buch/papers/reedsolomon/figures/fourier.pdf (limited to 'buch/papers/reedsolomon') diff --git a/buch/papers/reedsolomon/Makefile b/buch/papers/reedsolomon/Makefile index 25fd98b..4be963e 100644 --- a/buch/papers/reedsolomon/Makefile +++ b/buch/papers/reedsolomon/Makefile @@ -24,7 +24,7 @@ SOURCES := \ TIKZFIGURES := \ tikz/polynom2.tex \ - tikz/plotfft.tex + tikz/fourier.tex FIGURES := $(patsubst tikz/%.tex, figures/%.pdf, $(TIKZFIGURES)) 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 diff --git a/buch/papers/reedsolomon/figures/fourier.pdf b/buch/papers/reedsolomon/figures/fourier.pdf new file mode 100644 index 0000000..4995141 Binary files /dev/null and b/buch/papers/reedsolomon/figures/fourier.pdf differ diff --git a/buch/papers/reedsolomon/idee.tex b/buch/papers/reedsolomon/idee.tex index 26e617c..6ee42ef 100644 --- a/buch/papers/reedsolomon/idee.tex +++ b/buch/papers/reedsolomon/idee.tex @@ -51,20 +51,20 @@ Somit können die grauen Punkte auf der Parabel ersetzt werden und sind damit ko Bis zu wievielen Fehler können wir nun im Beispiel korrigieren? Wir erhöhen nun die Fehleranzahl Schritt für Schritt: \begin{itemize} - \item Bei \textit{1 Fehler} können konkurrenzierende Polynome, zusammen mit zwei originalen Punkten entstehen. + \item[\textit{1 Fehler}:] Bei einem Fehler können konkurrenzierende, aber falsche Polynome zusammen mit zwei originalen Punkten entstehen. Dabei können aber maximal 3 Punkte auf diesem Konkurrenzpolynom sein. Da 6 > 3 ist haben wir unser original Polynom gefunden. - \item Bei \textit{2 Fehlern} kann ein Fehler mit zwei originalen Punkten ein 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 originales Polynom mit 5 übereinstimmenden und eine konkurrenzierendes mit 4 Punkten. + \item[\textit{2 Fehler}:] Bei Zwei Fehlern kann ein Fehler mit zwei originalen Punkten ein konkurrenzierendes, aber falsches Polynom bilden. + Da der zweite \textcolor{red}{Fehler} frei wählbar ist, kann dieser auch auf dem \textcolor{gray}{Konkurrenzpolynom} liegen, wie in der Abbilbung \ref{fig:polynom}. + Nun haben wir, ein \textcolor{blue}{originales Polynom} mit \textcolor{darkgreen}{5} übereinstimmenden und eine konkurrenzierendes mit 4 Punkten. Da 5 noch grösser als 4 ist, können wir sagen, welches das Originalpolynom ist. - \item Bei \textit{3 Fehlern} kann genau wie bei 2 oder 1 Fehler, ein konkurenzierendes Polynom mit einem Fehler und zwei originalen Punkten bestimmen werden. + \item[\textit{3 Fehler}:] Bei Drei kann genau wie bei 2 oder 1 Fehler, ein konkurenzierendes Polynom mit einem Fehler und zwei originalen 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 Originalpolynom kann nicht mehr gefunden werden. - \item Bei \textit{4 Fehlern} Es kann noch erkannt werden, dass Fehler statt gefunden haben, da 3 orginale Punkte das ursprüngliche Polynom ergeben. + \item[\textit{4 Fehler}:] Bei Vier, kann es noch erkannt werden, dass Fehler statt gefunden haben, da 3 orginale Punkte das ursprüngliche Polynom ergeben. Somit haben wir mindestens 2 verschieden Polynome, dass bedeutet Fehler sind entstanden. - \item Bei \textit{5 Fehler} Mit den 2 originalen Punkte kann das Originale Polynom nicht mehr erkannt werden und + \item[\textit{5 Fehler}] Bei Fünf, kann mit den 2 originalen Punkte das Originale Polynom nicht mehr erkannt werden und somit auch keine Aussgae gemacht werden ob Fehler statt gefunden haben oder nicht. \end{itemize} @@ -82,8 +82,8 @@ Wir erhöhen nun die Fehleranzahl Schritt für Schritt: \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, braucht Redundanz. +Die Anzahl Datenwerte, ergeben die Anzahl Polynomkoeffizente \textcolor{blue}{$k$} und somit den Grad $k-1$. +Die Bestimmung der Anzahl der Fehler \textcolor{red}{$t$}, welche korrigiert werden können, braucht Redundanz. Gehen wir die Fehleranzahl mit verschiedenen Übertragungsanzahlen durch, erkennt man almählich ein Muster. \begin{table}%[!ht] @@ -102,9 +102,10 @@ Gehen wir die Fehleranzahl mit verschiedenen Übertragungsanzahlen durch, \caption{ Fehlerkorrekturstellen Bestimmung.} \label{tab:fehlerkorrekturstellen} \end{table} +\par Es müssen mehr Punkte auf dem \textcolor{blue}{originalen Polynom} liegen, als auf dem konkurenzierenden. -Somit braucht man für die Übertragung pro Fehler zwei Übertragungspunkte mehr. -Wie in der Tabelle ergibt sich diese Übertragungsanzahl +Somit braucht man für die Übertragung pro \textcolor{red}{Fehler} zwei Übertragungspunkte mehr. +Wie in der Tabelle ergibt sich diese \textcolor{darkgreen}{Übertragungsanzahl} \begin{equation} \textcolor{darkgreen}{u}= \textcolor{blue}{k}+2\textcolor{red}{t}. diff --git a/buch/papers/reedsolomon/standalone/standalone.pdf b/buch/papers/reedsolomon/standalone/standalone.pdf index dc34b2d..dfa9eea 100644 Binary files a/buch/papers/reedsolomon/standalone/standalone.pdf and b/buch/papers/reedsolomon/standalone/standalone.pdf differ -- cgit v1.2.1 From 49646a239bcd153e6fb2b85f5839d2f1853b33f0 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Mon, 9 Aug 2021 14:14:19 +0200 Subject: fix right axis --- buch/papers/reedsolomon/tikz/fourier.pdf | Bin 59767 -> 59721 bytes buch/papers/reedsolomon/tikz/fourier.tex | 8 +------- 2 files changed, 1 insertion(+), 7 deletions(-) (limited to 'buch/papers/reedsolomon') diff --git a/buch/papers/reedsolomon/tikz/fourier.pdf b/buch/papers/reedsolomon/tikz/fourier.pdf index 25e8d6d..7e0198b 100644 Binary files a/buch/papers/reedsolomon/tikz/fourier.pdf and b/buch/papers/reedsolomon/tikz/fourier.pdf differ diff --git a/buch/papers/reedsolomon/tikz/fourier.tex b/buch/papers/reedsolomon/tikz/fourier.tex index d151b2b..7b4ccea 100644 --- a/buch/papers/reedsolomon/tikz/fourier.tex +++ b/buch/papers/reedsolomon/tikz/fourier.tex @@ -48,13 +48,7 @@ \end{scope} \begin{scope}[xshift=\xverschiebung,yshift=0cm] - \begin{axis}[axis x line= none, axis y line*=right,ytick={0}, - axis background/.style={fill=white}, - width=\plotwidth,height=\plotheight] - \addplot[color=white] {0}; - \end{axis} - - \begin{axis}[title = {\large Codiert\strut}, axis y line*=left, + \begin{axis}[title = {\large Codiert\strut}, xtick={0,32,64,96}, axis background/.style={fill=white}, width=\plotwidth,height=\plotheight] -- cgit v1.2.1 From 23df345f724b32bb8d5ad6f103c0581458c977a9 Mon Sep 17 00:00:00 2001 From: JODBaer Date: Wed, 11 Aug 2021 17:04:24 +0200 Subject: =?UTF-8?q?=C3=BCbergang=20Endlichek=C3=B6rper=20vereinfacht.?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- buch/papers/reedsolomon/dtf.tex | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'buch/papers/reedsolomon') diff --git a/buch/papers/reedsolomon/dtf.tex b/buch/papers/reedsolomon/dtf.tex index 7c88c16..d05f60f 100644 --- a/buch/papers/reedsolomon/dtf.tex +++ b/buch/papers/reedsolomon/dtf.tex @@ -117,6 +117,6 @@ Das Syndrom entstand durch die Wahl ${f_{64}}=0$ bis ${f}_{N-1}=0$.(graue koeffi \par 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 reeleen Zahlen weg und zum endlichen Körpern, oder auch Galios-Körper genannt. -Dies wird nun im nächsten Abschnitt genauer erklärt. - +dann brauchen wir andere varianten. +Um dieser Aproximation zu entkommen, verlassen wir die reeleen Zahlen und gehen zum endlichen Körpern, oder auch Galios-Körper genannt. +Dieser bietet uns eingie Vorteile. \ No newline at end of file -- cgit v1.2.1