diff options
Diffstat (limited to 'buch')
38 files changed, 2065 insertions, 292 deletions
diff --git a/buch/chapters/70-graphen/chapter.tex b/buch/chapters/70-graphen/chapter.tex index 6def393..530d96c 100644 --- a/buch/chapters/70-graphen/chapter.tex +++ b/buch/chapters/70-graphen/chapter.tex @@ -19,7 +19,7 @@ erste Approximation dreidimensionaler Objekte dienen. Die Bedeutung des Graphenkozeptes wird unterstrichen von der Vielzahl von Fragestellungen, die über Graphen gestellt, und der -zugehöriten Lösungsalgorithmen, die zu ihrer Beantwortung gefunden +zugehörigen Lösungsalgorithmen, die zu ihrer Beantwortung gefunden worden sind. Die Komplexitätstheorie hat sogar gezeigt, dass sich jedes diskrete Problem in ein Graphenproblem umformulieren lässt. diff --git a/buch/common/macros.tex b/buch/common/macros.tex index 2c6eea2..5783122 100644 --- a/buch/common/macros.tex +++ b/buch/common/macros.tex @@ -108,6 +108,7 @@ \newtheorem{forderung}{Forderung}[chapter] \newtheorem{konsequenz}[satz]{Konsequenz} \newtheorem{algorithmus}[satz]{Algorithmus} +\newtheorem{ziel}[satz]{Ziel} \renewcommand{\floatpagefraction}{0.7} \definecolor{darkgreen}{rgb}{0,0.6,0} diff --git a/buch/papers/clifford/0_ElevatorPitch.tex b/buch/papers/clifford/0_ElevatorPitch.tex index 0db5617..ad9bcc2 100644 --- a/buch/papers/clifford/0_ElevatorPitch.tex +++ b/buch/papers/clifford/0_ElevatorPitch.tex @@ -1,2 +1,6 @@ -TODO... -GA [Geometric Algebra i.a.W. Clifford Algebra] provides a unified language for the whole of physics and for much of mathematics and its applications that is conceptually and computationally superior to alternative mathematical systems in many application domains.
\ No newline at end of file + +Der Nutzen, welche die Clifford Algebra hat, lässt sich am besten mit den Worten des modernen Begründers dieser erläutern. + +"GA [Geometric Algebra i.a.W. Clifford Algebra] provides a unified language for the whole of physics and for much of mathematics and its applications that is conceptually and computationally superior to alternative mathematical systems in many application domains." \cite{clifford:hestenes_GA} + +Im folgenden hoffen wir den Leser von der Nützlichkeit und der geometrischen Schönheit der Clifford Algebra zu überzeugen.
\ No newline at end of file diff --git a/buch/papers/clifford/1_Vektordarstellung.tex b/buch/papers/clifford/1_Vektordarstellung.tex index 88a5789..ac00a33 100644 --- a/buch/papers/clifford/1_Vektordarstellung.tex +++ b/buch/papers/clifford/1_Vektordarstellung.tex @@ -1,7 +1,7 @@ \section{Vektoroperationen\label{clifford:section:Vektoroperationen}} \rhead{Vektoroperationen} \subsection{Vektordarstellung\label{clifford:section:Vektordarstellung}} -Vektoren können neben der üblichen Darstellung, auch als Linearkombination aus Basisvektoren dargestellt werden +Vektoren können neben der üblichen Spaltendarstellung, auch als Linearkombination aus Basisvektoren \begin{equation} \begin{split} \textbf{a} @@ -31,12 +31,14 @@ Vektoren können neben der üblichen Darstellung, auch als Linearkombination aus \sum_{i=1}^{n} a_i \textbf{e}_i \qquad a_i \in \mathbb{R} - , \textbf{e}_i \in \mathbb{R}^n. + , \textbf{e}_i \in \mathbb{R}^n \end{split} \end{equation} -Diese Basisvektoren sollen orthonormal sein und um die Darstellung zu vereinfachen werden sie durch $\textbf{e}_1 , \textbf{e}_2, ...$ ersetzt. +dargestellt werden. +Diese Basisvektoren werden so gewählt, dass sie orthonormal sind. +Um die Darstellung zu vereinfachen werden sie durch $\textbf{e}_1 , \textbf{e}_2, \dots$ ersetzt. \begin{beispiel} -Linearkombination von Basisvektoren in $\mathbb{R}^4$ +Eine Linearkombination von Basisvektoren in $\mathbb{R}^4$ könnte wie folgt aussehen \begin{equation} \begin{pmatrix} 42 \\ 2 \\ 1291 \\ 4 @@ -65,7 +67,7 @@ Linearkombination von Basisvektoren in $\mathbb{R}^4$ + 1291\textbf{e}_3 + - 4\textbf{e}_4 + 4\textbf{e}_4. \end{equation} +Dieses Beispiel ist für einen vier dimensionalen Vektor, dies kann selbstverständlich für beliebig viele Dimensionen nach demselben Schema erweitert werden. \end{beispiel} -Wobei Beispiel für einen vier dimensionalen Vektor ist, dies kann selbstverständlich für beliebig viele Dimensionen nach demselben Schema erweitert werden.
\ No newline at end of file diff --git a/buch/papers/clifford/2_QuadratVektoren.tex b/buch/papers/clifford/2_QuadratVektoren.tex index cfb05d6..6c6fb7d 100644 --- a/buch/papers/clifford/2_QuadratVektoren.tex +++ b/buch/papers/clifford/2_QuadratVektoren.tex @@ -1,54 +1,71 @@ \subsection{Quadrat von Vektoren} -Was eine Addition von Vektoren bedeutet ist sehr intuitiv und auch leicht geometrisch darzustellen, was allerdings das Produkt von Vektoren ergibt mag anfänglich unintuitiv wirken. +\subsubsection{Ziel der Multiplikation} +Was eine Addition von Vektoren bedeutet ist sehr intuitiv und auch leicht geometrisch darzustellen wie in Abbildung \ref{figure:addition}, was allerdings das Produkt von Vektoren ergibt mag anfänglich unintuitiv wirken. +\begin{figure}[htb] + \centering + \begin{tikzpicture} + \draw[thin,gray!40] (0,0) grid (4,4); + \draw[blue,thick,->] (0,0)--(3.5,2) node[midway,above,sloped] {$\textbf{a}$}; + \draw[red,thick,->] (3.5,2)--(1.5,3.8) node[midway,above,sloped] {$\textbf{b}$}; + \draw[black,thick,->] (0,0)--(1.5,3.8)node[midway,above,sloped] {$\textbf{a} +\textbf{b} = \textbf{c} $}; + \end{tikzpicture} + \caption{Addition von zwei Vektoren\label{figure:addition}} +\end{figure} Was soll es schon heissen zwei Vektoren miteinander zu multiplizieren? -\newline Im Folgenden werden wir versuchen diese Operation ähnlich intuitiv darzustellen. -\newline -Um sinnvoll eine neue Operation zwischen zwei Elementen einer Algebra, in diesem Fall Vektoren, zu definieren, muss man überlegen, was das Ziel dieser Operation ist. -Als grundsätzliches Ziel wird definiert, dass das Quadrat eines Vektor dessen Länge im Quadrat ergibt, da dies auch in vielen anderen Bereichen der Mathematik,zum Beispiel bei komplexen Zahlen, auch so definiert ist. -\newline -Zusätzlich wollen wir auch das Assoziativgesetz und das Kommutativgesetz für Skalare beibehalten. Wobei das Kommutativgesetz leider, oder wie man sehen wird zum Glück, in der geometrischen Algebra im generellen nicht mehr gilt. Das heisst wir dürfen ausklammern \ref{eq:assoziativ} und die Position von Skalaren im Produkt ändern \ref{eq:kommSkalar}, allerdings nicht die Position der Vektoren \ref{eq:kommVector}. + +Um sinnvoll eine neue Operation zwischen zwei Elementen einer Algebra, in diesem Fall sind diese Elemente Vektoren, zu definieren, muss man überlegen, was das Ziel dieser Operation sein soll. + +Als grundsätzliches Ziel wird definiert, dass das Quadrat eines Vektor dessen Länge im Quadrat ergibt, da dies auch in vielen anderen Bereichen der Mathematik,zum Beispiel bei komplexen Zahlen,so definiert ist. + +Zusätzlich soll auch das Assoziativgesetz für die Multiplikation von Vektoren gelten, dass heisst wir dürfen ausklammern \begin{equation} \label{eq:assoziativ} \textbf{e}_i(\textbf{e}_j + \textbf{e}_k) = - \textbf{e}_i\textbf{e}_j + \textbf{e}_i\textbf{e}_k + \textbf{e}_i\textbf{e}_j + \textbf{e}_i\textbf{e}_k. \end{equation} +Allerdings gilt das Kommutativgesetz leider, oder wie man sehen wird zum Glück, nur für skalare Elemente \begin{equation} \label{eq:kommSkalar} a\textbf{e}_ib\textbf{e}_j = - ab\textbf{e}_i\textbf{e}_j + ab\textbf{e}_i\textbf{e}_j \qquad a,b \in \mathbb{R} \end{equation} +und nicht für Vektoren \begin{equation} \label{eq:kommVector} \textbf{e}_i\textbf{e}_j \neq - \textbf{e}_j\textbf{e}_i + \textbf{e}_j\textbf{e}_i. +\end{equation} +\subsubsection{Quadrieren eines Vektors} +Betrachten wir nun mit diesen Regeln das Quadrat eines Vektors. Zuerst werden die Vektoren als Linearkombinationen geschrieben +\begin{equation} + \textbf{a}^2 = + \left ( + \sum_{i=1}^{n} a_i \textbf{e}_i + \right ) + \left ( + \sum_{i=1}^{n} a_i \textbf{e}_i + \right ) + \label{eq:quad_a_1}. +\end{equation} +Das Quadrat kann nun in zwei Summen aufgeteilt werden +\begin{equation} + \textbf{a}^2 = + \textcolor{red}{\sum_{i=1}^{n} a_i^2\textbf{e}_i^2} + + + \textcolor{blue}{\sum_{\begin{subarray}{l}i,j=1\\i \neq j\end{subarray}}^n a_ia_j\textbf{e}_i\textbf{e}_j } + \label{eq:quad_a_2}, +\end{equation} +wobei die roten Summe die quadrierten Terme und die blaue Summe die Mischterme beinhaltet. Da $\textbf{e}_i^2 = 1$ gilt, weil das zuvor definierte Ziel des Quadrates eines Vektors dessen Länge ergibt und die Basisvektoren Länge 1 haben, wird dies nun eingesetzt +\begin{equation} + \textbf{a}^2 = \textcolor{cyan}{\sum_{i=1}^{n} a_i^2} + \textcolor{orange}{\sum_{\begin{subarray}{l}i,j=1\\i \neq j\end{subarray}}^n a_ia_j\textbf{e}_i\textbf{e}_j}. + \label{eq:quad_a_3} \end{equation} -Betrachten wir nun mit diesen Regeln das Quadrat eines Vektors. -\begin{align} - \textbf{a}^2 &= - \left ( - \sum_{i=1}^{n} a_i \textbf{e}_i - \right ) - \left ( - \sum_{i=1}^{n} a_i \textbf{e}_i - \right ) - \label{eq:quad_a_1} - \\ - &= - \textcolor{red}{\sum_{i=1}^{n} a_i^2\textbf{e}_i^2} - + - \textcolor{blue}{\sum_{\begin{subarray}{l}i,j=1\\i \neq j\end{subarray}}^n a_ia_j\textbf{e}_i\textbf{e}_j } - \label{eq:quad_a_2} - \\ - &= \textcolor{cyan}{\sum_{i=1}^{n} a_i^2} + \textcolor{orange}{\sum_{\begin{subarray}{l}i,j=1\\i \neq j\end{subarray}}^n a_ia_j\textbf{e}_i\textbf{e}_j}. - \label{eq:quad_a_3} -\end{align} - \begin{beispiel} -Quadrat eines Vektors in $\mathbb{R}^2$ +Das Quadrat des Vektor $a$ in $\mathbb{R}^2$ ist \begin{equation} \begin{split} \textbf{a}^2 @@ -56,22 +73,17 @@ Quadrat eines Vektors in $\mathbb{R}^2$ &= \textcolor{red}{a_1^2\textbf{e}_1^2 + a_2^2\textbf{e}_2^2} + \textcolor{blue}{a_1\textbf{e}_1a_2\textbf{e}_2 + a_2\textbf{e}_2a_1\textbf{e}_2} \\\ & = \textcolor{cyan}{a_1^2 + a_2^2} + \textcolor{orange}{a_1b\textbf{e}_1a_2\textbf{e}_2 + a_2\textbf{e}_2a_1\textbf{e}_2} - \end{split} + \end{split}. \end{equation} - \end{beispiel} -Der Vektor wird in \ref{eq:quad_a_1} als Linearkombination geschrieben. -Das Quadrat kann, wie in \ref{eq:quad_a_2} gezeigt, in zwei Summen aufteilen werden , wobei die roten Summe die quadrierten Terme und die blaue Summe die Mischterme beinhaltet. -\newline -Da $\textbf{e}_i^2 = 1$ gilt, da zuvor vorausgesetzt wurde, dass man mit orthonormalen Einheitsvektoren arbeitet, wird dies nun eingesetzt ergibt sich \ref{eq:quad_a_3} -\newline -Die hellblaue Teil ist nun bereits Länge im Quadrat eines Vektors, also das Ziel der Multiplikation. -Daher muss der restliche Teil dieser Gleichung null ergeben. -Aus dieser Erkenntnis leiten wir in \ref{eq:Mischterme_Null} weitere Eigenschaften für die Multiplikation her. + +Die hellblaue Teil ist nun bereits die Länge im Quadrat, also das zuvor definierte Ziel der Multiplikation. +Daraus lässt sich schliessen, dass der restliche Teil dieser Gleichung null ergeben muss \begin{equation} \label{eq:Mischterme_Null} - \sum_{\begin{subarray}{l}i,j=1\\i \neq j\end{subarray}}^n a_ia_j\textbf{e}_i\textbf{e}_j = \textcolor{blue}{a_1a_2(\textbf{e}_1\textbf{e}_2 + \textbf{e}_2\textbf{e}_1)} + a_1a_3(\textbf{e}_1\textbf{e}_3 + \textbf{e}_3\textbf{e}_1) + \dots = 0 + \sum_{\begin{subarray}{l}i,j=1\\i \neq j\end{subarray}}^n a_ia_j\textbf{e}_i\textbf{e}_j = \textcolor{blue}{a_1a_2(\textbf{e}_1\textbf{e}_2 + \textbf{e}_2\textbf{e}_1)} + a_1a_3(\textbf{e}_1\textbf{e}_3 + \textbf{e}_3\textbf{e}_1) + \dots = 0. \end{equation} +Aus dieser Erkenntnis können weitere Eigenschaften für die Multiplikation hergeleitet werden. Da dies für beliebige $a_i$ gelten muss werden alle Terme bis auf $a_1$ und $a_2$ gleich null gesetzt. Somit fallen alle Terme bis auf den blauen weg. Wird dies weiter vereinfacht ergibt sich \begin{equation} \begin{split} @@ -81,15 +93,13 @@ Da dies für beliebige $a_i$ gelten muss werden alle Terme bis auf $a_1$ und $a_ \end{split} \end{equation} \begin{satz} - Die Multiplikation von Vektoren ist antikommutativ, wenn die multiplizierten Vektoren orthogonal sind. + Die Multiplikation von Vektoren ist antikommutativ, wenn die multiplizierten Vektoren orthogonal sind, es gilt also \begin{equation} - \textbf{e}_i\textbf{e}_j = -\textbf{e}_j\textbf{e}_i \qquad \textbf{e}_i \perp \textbf{e}_j + \textbf{e}_i\textbf{e}_j = -\textbf{e}_j\textbf{e}_i \quad \textrm{für} \quad \textbf{e}_i \perp \textbf{e}_j. \end{equation} \end{satz} -Dieses Wissen reicht nun bereits um alle Produkte der Basisvektoren zu berechnen, was in \ref{tab:multip_vec} gemacht wurde. +Dieses Wissen reicht nun bereits um alle Produkte der Basisvektoren zu berechnen, was in Tabelle \ref{tab:multip_vec} gemacht wurde. \begin{table} -\caption{Multiplikationstabelle für Vektoren} -\label{tab:multip_vec} \begin{center} \begin{tabular}{ |c|c|c|c|c|c| } \hline @@ -107,4 +117,6 @@ Dieses Wissen reicht nun bereits um alle Produkte der Basisvektoren zu berechnen \hline \end{tabular} \end{center} +\caption{Multiplikationstabelle für Vektoren} +\label{tab:multip_vec} \end{table}
\ No newline at end of file diff --git a/buch/papers/clifford/3_MultiplikationVektoren.tex b/buch/papers/clifford/3_MultiplikationVektoren.tex index 841dde4..0969b89 100644 --- a/buch/papers/clifford/3_MultiplikationVektoren.tex +++ b/buch/papers/clifford/3_MultiplikationVektoren.tex @@ -1,11 +1,14 @@ \subsection{Multiplikation von Vektoren} -Was geschieht nun wenn zwei beliebige Vektoren,$u$ und $v$, miteinander multipliziert werden? +Was geschieht nun wenn zwei beliebige Vektoren, $u$ und $v$ \begin{equation} \textbf{u} = \sum_{i=1}^{n} u_i \textbf{e}_i \qquad \textbf{v} = \sum_{i=1}^{n} v_i \textbf{e}_i \end{equation} + miteinander multipliziert werden? + + Wieder werden die Vektoren zuerst als Linearkombinationen darstellen und danach in zwei Summen aufgeteilt, eine Summe mit quadrierten Termen und eine Summe mit Mischtermen \begin{equation} \begin{split} \textbf{u}\textbf{v} @@ -18,12 +21,12 @@ Was geschieht nun wenn zwei beliebige Vektoren,$u$ und $v$, miteinander multipli \right) = \sum_{i=1}^n u_iv_i\underbrace{\textbf{e}_i^2}_{1} - + \sum_{\begin{subarray}{l}i,j=1\\i \neq j\end{subarray}}^n u_iv_j\textbf{e}_i\textbf{e}_j + + \sum_{\begin{subarray}{l}i,j=1\\i \neq j\end{subarray}}^n u_iv_j\textbf{e}_i\textbf{e}_j, \end{split} \end{equation} +wobei die Summe der quadrierten Termen bereits bekannt vorkommen könnte, es ist nämlich das Skalarprodukt von $u$ und $v$. Die Summe der Mischterme bilden etwas neues, dass wir das äussere Produkt von $u$ und $v$ nennen. \begin{beispiel} Multiplikation von Vektoren in $\mathbb{R}^2$ -\end{beispiel} \begin{equation} \begin{split} \textbf{u}\textbf{v} @@ -44,7 +47,7 @@ Was geschieht nun wenn zwei beliebige Vektoren,$u$ und $v$, miteinander multipli \underbrace{(u_1v_2 - u_2v_1)\textbf{e}_1\textbf{e}_2}_{\text{Äusseres Produkt}} \end{split} \end{equation} -Der linke Teil dieser Multiplikation ergibt das Skalarprodukt der zwei Vektoren, der rechte Term ergibt etwas neues das sich das äussere Produkt der zwei Vektoren nennt. +\end{beispiel} \subsubsection{Äusseres Produkt} Das äussere Produkt von zwei Vektoren wird mit einem $\wedge$ dargestellt \begin{equation} @@ -53,123 +56,118 @@ Das äussere Produkt von zwei Vektoren wird mit einem $\wedge$ dargestellt \sum_{\begin{subarray}{l}i,j=1\\i \neq j\end{subarray}}^n u_iv_j\textbf{e}_i\textbf{e}_j \end{equation} \begin{beispiel} -Äusseres Produkt von zwei Vektoren in $\mathbb{R}^3$ -\end{beispiel} +Das äusseres Produkt von zwei Vektoren in $\mathbb{R}^3$ ist \begin{equation} - \begin{split} - u \wedge v - &= - u_1v_2\textbf{e}_1\textbf{e}_2 - + - u_1v_3\textbf{e}_1\textbf{e}_3 - + - u_2v_2\textbf{e}_2\textbf{e}_3 - + - u_2v_1\textbf{e}_2\textbf{e}_1 - + - u_3v_1\textbf{e}_3\textbf{e}_1 - + - u_3v_2\textbf{e}_3\textbf{e}_2 \\\ - &= - (u_1v_2 - u_2v_1)\textbf{e}_1\textbf{e}_2 - + - (u_1v_3 - v_3u_1)\textbf{e}_1\textbf{e}_3 - + - (u_2v_3 - u_3v_2)\textbf{e}_2\textbf{e}_3 - \end{split} + \begin{split} + u \wedge v + &= + u_1v_2\textbf{e}_1\textbf{e}_2 + + + u_1v_3\textbf{e}_1\textbf{e}_3 + + + u_2v_2\textbf{e}_2\textbf{e}_3 + + + u_2v_1\textbf{e}_2\textbf{e}_1 + + + u_3v_1\textbf{e}_3\textbf{e}_1 + + + u_3v_2\textbf{e}_3\textbf{e}_2 \\\ + &= + (u_1v_2 - u_2v_1)\textbf{e}_1\textbf{e}_2 + + + (u_1v_3 - v_3u_1)\textbf{e}_1\textbf{e}_3 + + + (u_2v_3 - u_3v_2)\textbf{e}_2\textbf{e}_3. + \end{split} \end{equation} -Im letzten Schritt des Beispiels wurden nun, mit Hilfe der antikommutativität des Produkts, die Vektorprodukte, welche die gleichen Einheitsvektoren beinhalten, zusammengefasst. Dieses Vorgehen kann man auch allgemein anwenden, wie in den Gleichungen \ref{eq:u_wedge_v}-\ref{eq:u_wedge_v_5} hergeleitet. +\end{beispiel} + +Im letzten Schritt des Beispiels wurden nun, mit Hilfe der antikommutativität des Produkts, die Vektorprodukte, welche die gleichen Einheitsvektoren beinhalten, zusammengefasst. Dieses Vorgehen kann man auch allgemein anwenden, wie in den Gleichungen \eqref{eq:u_wedge_v}-\eqref{eq:u_wedge_v_5} hergeleitet. Die Summe, \begin{align} \textbf{u}\wedge \textbf{v} &= \sum_{\begin{subarray}{l}i,j=1\\i \neq j\end{subarray}}^n - u_iv_j\textbf{e}_i\textbf{e}_j + u_iv_j\textbf{e}_i\textbf{e}_j, \label{eq:u_wedge_v} - \\ + \intertext{wird in zwei verschiedene Summen aufgeteilt. + Wobei die linke Summe jeweils den Basisvektor mit dem höheren Index an erster Stelle und die rechte Summe diesen jeweils an zweiter Stelle hat} \label{eq:u_wedge_v_1} &= \sum_{\begin{subarray}{l}i,j=1\\i < j\end{subarray}}^n u_iv_j\textbf{e}_i\textbf{e}_j + - \sum_{\begin{subarray}{l}i,j=1\\j < i\end{subarray}}^n u_iv_j\textbf{e}_i\textbf{e}_j - \\ + \sum_{\begin{subarray}{l}i,j=1\\j < i\end{subarray}}^n u_iv_j\textbf{e}_i\textbf{e}_j. + \intertext{Nun werden die Indexe der zweiten Summe vertauscht} \label{eq:u_wedge_v_2} &= \sum_{\begin{subarray}{l}i,j=1\\i < j\end{subarray}}^n u_iv_j\textbf{e}_i\textbf{e}_j + - \sum_{\begin{subarray}{l}i,j=1\\i < j\end{subarray}}^n u_jv_i\textbf{e}_j\textbf{e}_i - \\ - \label{eq:u_wedge_v_3} + \sum_{\begin{subarray}{l}i,j=1\\i < j\end{subarray}}^n u_jv_i\textbf{e}_j\textbf{e}_i, + \intertext{und diese wird nun mit Hilfe der Antikommutativität umgeformt zu} &= \sum_{\begin{subarray}{l}i,j=1\\i < j\end{subarray}}^n u_iv_j\textbf{e}_i\textbf{e}_j - - \sum_{\begin{subarray}{l}i,j=1\\i < j\end{subarray}}^n u_jv_i\textbf{e}_i\textbf{e}_j - \\ + \sum_{\begin{subarray}{l}i,j=1\\i < j\end{subarray}}^n u_jv_i\textbf{e}_i\textbf{e}_j. + \intertext{Nun können die zwei Summen wieder zusammengefasst werden} \label{eq:u_wedge_v_4} &= - \sum_{\begin{subarray}{l}i,j=1\\i < j\end{subarray}}^n (u_iv_j -u_jv_i)\textbf{e}_i\textbf{e}_j - \\ - \label{eq:u_wedge_v_5} + \sum_{\begin{subarray}{l}i,j=1\\i < j\end{subarray}}^n (u_iv_j -u_jv_i)\textbf{e}_i\textbf{e}_j. + \intertext{Der Term in der Summe könnte einem bereits bekannt vorkommen, es ist nämlich die Determinante einer Matrix mit $u$ und $v$ als ihre Spalten} &= + \label{eq:u_wedge_v_5} \sum_{\begin{subarray}{l}i,j=1\\i < j\end{subarray}}^n \begin{vmatrix} u_i & v_i \\ u_j & v_j - \end{vmatrix}\textbf{e}_i\textbf{e}_j + \end{vmatrix}\textbf{e}_i\textbf{e}_j. \end{align} -Die Summe aus \ref{eq:u_wedge_v_1} wird in \ref{eq:u_wedge_v} in zwei verschiedene Summen aufgeteilt. -Wobei die linke Summe jeweils den Basisvektor mit dem höheren Index an erster Stelle und die rechte Summe diesen jeweils an zweiter Stelle hat. -\newline -Bei \ref{eq:u_wedge_v_2} werden die Indexe der zweiten Summe vertauscht, damit man nun bei beiden Teilen die gleiche Summe hat. -Danach werden in \ref{eq:u_wedge_v_3}, mit Hilfe der Antikommutativität, die Einheitsvektoren der zweiten Summe vertauscht. -\newline -Nun können die Summen, wie in \ref{eq:u_wedge_v_4} wieder in eine Summe zusammengefasst werden. -\newline -Der Term in der Klammer in \ref{eq:u_wedge_v_4} kann auch als Determinante einer 2x2 Matrix dargestellt werden, was in \ref{eq:u_wedge_v_5} gemacht wird. -\newline -Die Determinante einer Matrix beschreibt welche von den Spaltenvektoren aufgespannt wird, wie in Abbildung \ref{figure:det} dargestellt. -\begin{figure} -\centering -\begin{tikzpicture} - \draw[thin,gray!40] (0,0) grid (4,4); - \draw[<->] (0,0)--(4,0) ; - \draw[<->] (0,0)--(0,4) ; - \draw[line width=0,fill=gray!40] (0,0)--(3,1)--(4,3)--(1,2); - \draw[line width=2pt,blue,-stealth](0,0)--(3,1) node[anchor=north - west]{$\boldsymbol{u}$}; - \draw[line width=2pt,red,-stealth](0,0)--(1,2) node[anchor=south east]{$\boldsymbol{v}$}; - \draw[black] (2,1.5)--(-0.5,2.5) node[anchor = east]{$\begin{vmatrix} - u_i & v_i \\ - u_j & v_j - \end{vmatrix} = u_iv_j - v_iu_j$}; -\end{tikzpicture} -\caption{Geometrische Interpretation der Determinante einer 2x2 Matrix\label{figure:det}} +Die Determinante einer Matrix beschreibt die Fläche, welche von den Spaltenvektoren aufgespannt wird, wie in Abbildung \ref{figure:det} dargestellt. +\begin{figure}[htb] + \centering + \begin{minipage}[t]{.45\linewidth} + \centering + \begin{tikzpicture} + \draw[thin,gray!40] (0,0) grid (4,4); + \draw[<->] (0,0)--(4,0) ; + \draw[<->] (0,0)--(0,4) ; + \draw[line width=0,fill=gray!40] (0,0)--(3,1)--(4,3)--(1,2); + \draw[line width=2pt,blue,-stealth](0,0)--(3,1) node[anchor=north + west]{$\boldsymbol{u}$}; + \draw[line width=2pt,red,-stealth](0,0)--(1,2) node[anchor=south east]{$\boldsymbol{v}$}; + \draw[black] (2,1.5)--(1.8,3.2) node[anchor = south]{$\begin{vmatrix} + u_i & v_i \\ + u_j & v_j + \end{vmatrix} = u_iv_j - v_iu_j$}; + \end{tikzpicture} + \caption{Geometrische Interpretation der Determinante einer $2 \times 2$ Matrix\label{figure:det}} + \end{minipage}% + \hfill% + \begin{minipage}[t]{.45\linewidth} + \centering + \begin{tikzpicture} + \draw[thin,gray!40] (0,0) grid (4,4); + \draw[<->] (0,0)--(4,0) node[right]{$x$}; + \draw[<->] (0,0)--(0,4) node[above]{$y$}; + \draw[line width=0,fill=gray!40] (0,0)--(3,1)--(4,3)--(1,2); + \draw[line width=2pt,blue,-stealth](0,0)--(3,1) node[anchor=north + west]{$\boldsymbol{u}$}; + \draw[line width=2pt,red,-stealth](0,0)--(1,2) node[anchor=south east]{$\boldsymbol{v}$}; + \draw[->] (2.15,1.5) arc (0:310:0.3); + \draw[black] (2,1.5)--(2.5,3.2) node[anchor = south]{$u\wedge v = \begin{vmatrix} + u_i & v_i \\ + u_j & v_j + \end{vmatrix} e_1e_2 = (u_iv_j - v_iu_j)\textbf{e}_1\textbf{e}_2$}; + \end{tikzpicture} + \caption{Geometrische Interpretation des äusseren Produktes \label{figure:wedge}} + \end{minipage} \end{figure} -\newline Das äussere Produkt besteht nun also aus der Summe - $\sum_{\begin{subarray}{l}i,j=1\\i < j\end{subarray}}^n$ + \(\sum_{\begin{subarray}{l}i,j=1\\i < j\end{subarray}}^n\) von Flächen - $\begin{vmatrix} - u_i & v_i \\ - u_j & v_j - \end{vmatrix}$, welche in $\textbf{e}_i\textbf{e}_j$ aufgespannt sind, wie man in \ref{eq:u_wedge_v_5} sieht. + \(\begin{vmatrix} + u_i & v_i \\ + u_j & v_j + \end{vmatrix}\) +, welche in $\textbf{e}_i\textbf{e}_j$ aufgespannt sind, wie man in \ref{eq:u_wedge_v_5} sieht. Dieses Produkt $\textbf{e}_i\textbf{e}_j$ der Basisvektoren interpretiert man als Umlaufrichtung. Wobei die gebildete Fläche in Richtung des ersten Vektors umschritten wird. -Dies ist in \ref{figure:wedge} dargestellt, wobei bei diesem Beispiel die Umlaufrichtung im Gegenuhrzeigersinn ist, da die Fläche in Richtung u umschritten wird. +Dies ist in Abbildung \ref{figure:wedge} dargestellt, wobei bei diesem Beispiel die Umlaufrichtung im Gegenuhrzeigersinn ist, da die Fläche in Richtung u umschritten wird. Diese Fläche mit einer Richtung nennt man in der geometrischen Algebra einen Bivektor, da er eine Art zwei dimensionaler Vektor ist. -\begin{figure} -\centering -\begin{tikzpicture} - \draw[thin,gray!40] (0,0) grid (4,4); - \draw[<->] (0,0)--(4,0) node[right]{$x$}; - \draw[<->] (0,0)--(0,4) node[above]{$y$}; - \draw[line width=0,fill=gray!40] (0,0)--(3,1)--(4,3)--(1,2); - \draw[line width=2pt,blue,-stealth](0,0)--(3,1) node[anchor=north - west]{$\boldsymbol{u}$}; - \draw[line width=2pt,red,-stealth](0,0)--(1,2) node[anchor=south east]{$\boldsymbol{v}$}; - \draw[->] (2.15,1.5) arc (0:310:0.3); - \draw[black] (2,1.5)--(-0.5,2.5) node[anchor = east]{$u\wedge v = \begin{vmatrix} - u_i & v_i \\ - u_j & v_j - \end{vmatrix} e_1e_2 = (u_iv_j - v_iu_j)\textbf{e}_1\textbf{e}_2$}; -\end{tikzpicture} -\caption{Geometrische Interpretation des äusseren Produkt in $\mathbb{R}^2$\label{figure:wedge}} -\end{figure}
\ No newline at end of file diff --git a/buch/papers/clifford/4_GeometrischesProdukt.tex b/buch/papers/clifford/4_GeometrischesProdukt.tex index a19e983..f18b90d 100644 --- a/buch/papers/clifford/4_GeometrischesProdukt.tex +++ b/buch/papers/clifford/4_GeometrischesProdukt.tex @@ -12,9 +12,9 @@ Ein Multivektor besteht aus den verschiedenen Bauteilen, wie zum Beispiel Vektor M = \sum \left ( \prod a_i\textbf{e}_j \right) \end{equation} \end{definition} -Besteht eine Clifford Algebra aus n Basisvektoren so hat sie n Dimensionen, dies wird nicht wie in der linearen Algebra mit $\mathbb{R}^n$ sondern mit $\mathbb{G}^n$ beschrieben. +Besteht eine Clifford Algebra aus n Basisvektoren so hat sie n Dimensionen, dies wird nicht wie in der linearen Algebra mit $\mathbb{R}^n$ sondern mit $G_n(\mathbb{R})$ beschrieben. Dies wird so geschrieben da man eine neue Algebrastruktur um die Vektoren einführt. \begin{beispiel} -Allgemeiner Multivektor in $\mathbb{G}^3$ +Allgemeiner Multivektor in $G_3(\mathbb{R})$ \begin{equation} M = a + @@ -26,34 +26,30 @@ Allgemeiner Multivektor in $\mathbb{G}^3$ \end{equation} \end{beispiel} \begin{definition} -Um das Produkt von Basisvektoren in Zukunft darzustellen wird folgende Notation definiert +Für das Produkt von Basisvektoren wird folgende Notation definiert \begin{equation} - e_ie_j = e_{ij} + e_ie_j = e_{ij}. \end{equation} \end{definition} -Nun da das geometrische Produkt vollständig definiert wurde können Multiplikationstabellen für verschiedene Dimensionen $\mathbb{G}^n$ erstellt werden. In \ref{tab:multip} ist dies für $\mathbb{G}^3$ gemacht. +Nun da das geometrische Produkt vollständig definiert wurde können Multiplikationstabellen für verschiedene Dimensionen $G_n(\mathbb{R})$ erstellt werden. In Tabelle \ref{tab:multip} ist dies für $G_3(\mathbb{R})$ gemacht. \begin{table} - \caption{Multiplikationstabelle für $\mathbb{G^3}$} \label{tab:multip} \begin{center} - \begin{tabular}{ |c|c|c|c|c|c|c|c| } + \begin{tabular}{ |c|ccc|ccc|c| } \hline 1 & $\textbf{e}_1$ & $\textbf{e}_2$ &$\textbf{e}_3$ & $\textbf{e}_{12}$ & $\textbf{e}_{13}$ & $\textbf{e}_{23}$ & $\textbf{e}_{123}$\\ \hline $\textbf{e}_1$ & 1 & $\textbf{e}_{12}$ & $\textbf{e}_{12}$ & $\textbf{e}_2$ & $\textbf{e}_3$ & $\textbf{e}_{123}$ & $\textbf{e}_{23}$\\ - \hline $\textbf{e}_2$ & $-\textbf{e}_{12}$ & 1 & $\textbf{e}_{23}$ & $-\textbf{e}_1$ & $-\textbf{e}_{123}$ & $\textbf{e}_3$ & $-\textbf{e}_{13}$\\ - \hline $\textbf{e}_3$ & $-\textbf{e}_{13}$ & $-\textbf{e}_{23}$ & 1 & $\textbf{e}_{123}$ & $-\textbf{e}_1$ & $-\textbf{e}_2$ & $\textbf{e}_{12}$\\ \hline $\textbf{e}_{12}$ & -$\textbf{e}_2$ & $\textbf{e}_1$& $\textbf{e}_{123}$ & -1 & $-\textbf{e}_{23}$ & $\textbf{e}_{13}$ & $-\textbf{e}_{3}$\\ - \hline $\textbf{e}_{13}$ & $-\textbf{e}_{3}$ & $-\textbf{e}_{123}$ & $\textbf{e}_{1}$ & $\textbf{e}_{23}$ & -1 & $-\textbf{e}_{12}$ & $\textbf{e}_{2}$\\ - \hline $\textbf{e}_{23}$ & $\textbf{e}_{123}$ & $-\textbf{e}_{3}$ & $\textbf{e}_{2}$ & $-\textbf{e}_{13}$ & $\textbf{e}_{12}$ & -1 & $-\textbf{e}_{1}$ \\ \hline $\textbf{e}_{123}$ & $\textbf{e}_{23}$ & $-\textbf{e}_{13}$ & $\textbf{e}_{12}$ & $-\textbf{e}_{3}$& $\textbf{e}_{2}$ & $-\textbf{e}_{1}$ & -1 \\ \hline \end{tabular} \end{center} + \caption{Multiplikationstabelle für $G_3(\mathbb{R})$} \end{table} diff --git a/buch/papers/clifford/references.bib b/buch/papers/clifford/references.bib index ff829d6..9090005 100644 --- a/buch/papers/clifford/references.bib +++ b/buch/papers/clifford/references.bib @@ -4,32 +4,13 @@ % (c) 2020 Autor, Hochschule Rapperswil % -@online{clifford:bibtex, - title = {BibTeX}, - url = {https://de.wikipedia.org/wiki/BibTeX}, - date = {2020-02-06}, - year = {2020}, - month = {2}, - day = {6} -} - -@book{clifford:numerical-analysis, - title = {Numerical Analysis}, - author = {David Kincaid and Ward Cheney}, - publisher = {American Mathematical Society}, - year = {2002}, - isbn = {978-8-8218-4788-6}, - inseries = {Pure and applied undegraduate texts}, - volume = {2} -} - -@article{clifford:mendezmueller, - author = { Tabea Méndez and Andreas Müller }, - title = { Noncommutative harmonic analysis and image registration }, - journal = { Appl. Comput. Harmon. Anal.}, - year = 2019, - volume = 47, - pages = {607--627}, - url = {https://doi.org/10.1016/j.acha.2017.11.004} +@article{clifford:hestenes_GA, + author = { David Hestenes, Garret Eugene Sobczyk and James S. Marsh }, + title = { Clifford Algebra to Geometric Calculus. A Unified Language for Mathematics and Physics }, + journal = { American Journal of Physics }, + year = 1985, + volume = 53, + pages = {24}, + url = {https://www.researchgate.net/publication/258944244_Clifford_Algebra_to_Geometric_Calculus_A_Unified_Language_for_Mathematics_and_Physics} } diff --git a/buch/papers/reedsolomon/Makefile.inc b/buch/papers/reedsolomon/Makefile.inc index 6a676f8..ea51f7a 100644 --- a/buch/papers/reedsolomon/Makefile.inc +++ b/buch/papers/reedsolomon/Makefile.inc @@ -6,9 +6,17 @@ dependencies-reedsolomon = \ papers/reedsolomon/packages.tex \ papers/reedsolomon/main.tex \ - papers/reedsolomon/references.bib \ - papers/reedsolomon/teil0.tex \ - papers/reedsolomon/teil1.tex \ - papers/reedsolomon/teil2.tex \ - papers/reedsolomon/teil3.tex + papers/reedsolomon/einleitung.tex \ + papers/reedsolomon/idee.tex \ + papers/reedsolomon/dtf.tex \ + papers/reedsolomon/endlichekoerper.tex \ + papers/reedsolomon/codebsp.tex \ + papers/reedsolomon/decohnefehler.tex \ + papers/reedsolomon/decmitfehler.tex \ + papers/reedsolomon/rekonstruktion.tex \ + papers/reedsolomon/zusammenfassung.tex \ + papers/reedsolomon/anwendungen.tex \ + papers/reedsolomon/hilfstabellen.tex \ + papers/reedsolomon/references.bib + diff --git a/buch/papers/reedsolomon/RS presentation/images/polynom1 - Kopie.tex b/buch/papers/reedsolomon/RS presentation/images/polynom1 - Kopie.tex new file mode 100644 index 0000000..038e93e --- /dev/null +++ b/buch/papers/reedsolomon/RS presentation/images/polynom1 - Kopie.tex @@ -0,0 +1,33 @@ +% polynome1 +%------------------- +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{times} +\usepackage{txfonts} +\usepackage{pgfplots} +\usepackage{csvsimple} +\usetikzlibrary{arrows,intersections,math} +\newcommand{\teiler}{40} +\begin{document} + + +\begin{tikzpicture}[>=latex,thick] + + \begin{axis}[ + axis lines = left, + xlabel = \(x\), + ylabel = {\(f(x)\)}, + ] + %Below the red parabola is defined + \addplot[ + color=blue, + ] + coordinates { + (0,23.1)(10,27.5)(20,32)(30,37.8)(40,44.6)(60,61.8)(80,83.8)(100,114) + }; + %Here the blue parabola is defined + + \end{axis} +\end{tikzpicture} +\end{document} + diff --git a/buch/papers/reedsolomon/anwendungen.tex b/buch/papers/reedsolomon/anwendungen.tex index 83e0f94..c03b1a4 100644 --- a/buch/papers/reedsolomon/anwendungen.tex +++ b/buch/papers/reedsolomon/anwendungen.tex @@ -6,14 +6,40 @@ \section{Anwendungen des Reed-Solomon-Codes \label{reedsolomon:section:anwendung}} \rhead{Anwendungen} -\textcolor{red}{Platzierung der Bilder? Quellenangabe der Bilder?} In den vorherigen Abschnitten haben wir betrachtet, wie Reed-Solomon-Codes in der Theorie Funktionieren. In diesem Abschnitt werden wir einige Anwendungen vorstellen, bei denen ein Reed-Solomon-Code zum Einsatz kommt. + +Dabei teilen all diese Anwendungen das gleiche Problem: Die Daten können nur durch einen (höchst Wahrscheinlichen) fehlerbehafteten Kanal empfangen werden. Es gibt keine andere Methode an diese Daten zu kommen als über diesen Kanal. + + +In der Netzwerktechnik zum Beispiel ist es üblich, dass bei Paketverluste oder beschädigt empfangene Datenpakete diese einfach noch einmal inert wenigen Millisekunden angefordert werden können. +In der Raumfahrt ist dies nicht möglich, da aufgrund der beschränkten Speichermöglichkeit die gesammelten Daten so rasch wie möglich zur Erde gesendet werden. +Diese Daten wiederum brauchen aufgrund der grossen Distanz Stunden bis die Daten beim Empfänger ankommen. +Fehlerhafte Daten kann also auf Grund der Zeitverzögerung nicht mehr angefordert werden. + +Bei CDs oder DVDs gibt es zwar kein Zeitliches Problem, jedoch erschweren Kratzer, Verschmutzungen oder Produktionsfehler das Lesen einer solchen Disk. +Da vor allem Produktionsfehler und Kratzer irreversibel sind und die Disk nicht nach jedem Kratzer ersetzt werden muss, so wird die korrekte Ausgabe der gespeicherten Information durch die Fehlerkorrektur sichergestellt. + +Ein ähnlicher Ansatz verfolgen QR-Codes, wobei die Information auch dann noch gelesen werden kann wenn der Code nicht mehr vollständig vorhanden ist. + +%Wie man sieht, eignen sich Reed-Solomon-Codes vor allem für Anwendungen, bei der die Informationen nicht auf einen Anderen Weg beschafft werden kann. +% +% +%, bei denen die Wahrscheinlichkeit hoch ist, dass während der Übertragung +% +%Es ist deshalb umso wichtiger die Daten Codiert zu lesen um so gleich die Lesefehler zu korrigieren. +% +% da aufgrund der grossen Distanz Stunden vergehen können bis gesendete Daten auf der Erde empfangen werden kann. +% + + Obwohl alle diese Codes nach dem gleichen Prinzip arbeiten gibt es starke Unterschiede in deren Funktionsweise. Dies kommt vor allem daher, da die Codes nur Ressourcen zur Verfügung haben, die von der Hardware bereitstellt wird, auf denen die Codes implementiert wurden. Diese Codes bedienen sich daher verschiedener Tricks und Optimierungen um möglichst effizient zu arbeiten. -% + +Um die Fähigkeit eines verwendeten Reed-Solomon-Codes zu beschreiben verwendet man die Notation ($n$,$k$), wobei $n$ die Grösse des Nachrichtenblocks angibt und $k$ die Anzahl der Stellen, die für Nutzdaten gebraucht werden können. + %Dies kommt vor allem daher, da diese Codes an ihre Hardware gebunden sind, auf denen sie implementiert worden sind. %Deshalb wurden diese Codes stark optimiert damit sie möglichst Effizient arbeiten können. % @@ -45,8 +71,17 @@ Diese Codes bedienen sich daher verschiedener Tricks und Optimierungen um mögli %In den letzten abschnitten haben wir uns ausführlich die Funktionsweise des Reed-Solomon-Codes angeschaut. In diesem Abschnitt möchten wir dem Leser ein paar bekannte beispiele vorstellen, in denen Reed-Solomon-Codes zum einsatz kommen. Es sei jedoch angemerkt, dass diese Anwendungen in der Umsetzung oft ein wenig anderst funktionieren als hier vorgestellt. Dies wurde vor allem wegen technischen optimierungen realisiert. (technische tricks und finessen), von der logik jedoch sehr stark an unserem Beispiel orientieren \subsection{Raumfahrt} -Obwohl Reed-Solomon-Codes bereits in den 1960er entwickelt wurden fanden sie erstmals Anwendung in der Voyager Raumsonde der NASA. Die Daten der zwei im Jahre 1977 gestarteten Sonden werden mit einem RS(255,233)-Code \textcolor{red}{benötigt das weitere erklärungen, wie z.b. 255: grösse nachrichtenblock, 233: anzahl der nutzbaren daten ?} zusammen mit einem konventionellen Faltungscode übertragen. - +Obwohl Reed-Solomon-Codes bereits in den 1960er entwickelt wurden fanden sie erstmals Anwendung in der Voyager Raumsonde der NASA. Die Daten der zwei im Jahre 1977 gestarteten Sonden (siehe Abbildung \ref{fig:voyager}) werden mit einem ($255$,$233$)-Code +Codiert. +Der Nachrichtenblock hat somit eine Länge von $255$ Zahlen, wovon $233$ als Nutzlast zur Verfügung stehen. +Damit ist es möglich bis zu $11$ Fehler im Nachrichtenblock zu korrigieren. +Der Codierte Nachrichtenblock wird in kleinere Blöcke aufgeteilt, mit einem Faltungscode erneut Codiert und anschliessend gesendet. Ein Faltungscode ist wie ein Reed-Solomon-Code in der Lage Fehler zu korrigieren, Funktioniert aber nach einem ganz anderen Prinzip. +Durch diese doppelte Codierung wird eine äusserst hohe Übertragungssicherheit garantiert. +% +%Dabei steht die Zahl 255 für grösse des Nachrichtenblocks, der die Anzahl 233 +% +% +% \textcolor{red}{benötigt das weitere Erklärungen, wie z.b. 255: grösse Nachrichtenblock, 233: anzahl der nutzbaren daten ?} zusammen mit einem konventionellen Faltungscode übertragen. Eine von der Sonde gesendete Nachricht hat eine Blockgrösse von 255 Zeichen, wovon 233 für die Nutzdaten gebraucht werden können. Dieser Code ist somit in der Lage 11 Fehler in einem Nachrichtenblock zu korrigieren. % % Die zwei im Jahre 1977 gestarteten Sonden senden Daten mit der Hilfe eines RS(255,233)-Code für die digitalen Bilder sowie einem konventionellen Faltungscode. % @@ -56,14 +91,14 @@ Obwohl Reed-Solomon-Codes bereits in den 1960er entwickelt wurden fanden sie ers \begin{figure} \centering \includegraphics[width=0.5\textwidth]{papers/reedsolomon/images/Voyager_Sonde} - \caption{Voyager Raumsonde} + \caption{Mit einer Entfernung von über 22.8 Milliarden Kilometer ist die Voyager 1 Raumsonde das am weitesten entfernte, von Menschen erschaffene Objekt. Obwohl ihre Schwestersonde Voyager 2 zuerst ins All gestartet wurde befindet Sie sich ``nur'' 19 Milliarden Kilometer weit weg von der Erde. Aufgrund abnehmender Batterieleistung werden die beiden Sonden ihre wissenschaftlichen Aktivitäten etwa 2025 einstellen, bleiben aber bis in die 2030er mit uns in Kontakt.} \label{fig:voyager} \end{figure} \subsection{CD/DVD} Compact discs verwenden sogar zwei ineinander verschachtelte Reed-Solomon-Codes, einen (32,28)-Code und einen (28,24)-Code. -Beide Codes sind in der Lage, Fehler aus dem jeweils anderen gelesenen Block zu korrigieren. Dieses spezielle zusammenspielen dieser beiden Codes werden auch Cross-interleaved Reed-Solomon-Codes (CIRC) genannt. -Diese Vorgehensweise erzielt eine hohe Robustheit gegenüber Produktionsfehler oder Verschmutzung auf der Disc. Bei CD's sind diese in der Lage bis zu 4000 fehlerhafte Bits am Stück (ca. $2.5mm$) zu erkennen und zu korrigieren. +Beide Codes sind in der Lage, Fehler aus dem jeweils anderen gelesenen Block zu korrigieren. Dieses spezielle Zusammenspielen dieser beiden Codes werden auch Cross-interleaved Reed-Solomon-Codes (CIRC) genannt. +Diese Vorgehensweise erzielt eine hohe Robustheit gegenüber Produktionsfehlern oder Verschmutzung auf der Disc. Bei CDs sind diese in der Lage, bis zu 4000 fehlerhafte Bits am Stück (ca. $2.5mm$) zu erkennen und zu korrigieren. Die Digital Video Disc funktioniert nach dem selben Konzept mit grösseren Codeblöcken. Die DVD verwendet einen (208,192)-Code und einen (182,172)-Code. @@ -73,12 +108,19 @@ Die Digital Video Disc funktioniert nach dem selben Konzept mit grösseren Codeb \begin{figure} \centering \includegraphics[width=0.5\textwidth]{papers/reedsolomon/images/Compact_Disc} - \caption{Compact Disc} + \caption{CDs kamen 1982 auf den Markt. Sie funktioniert durch das ``einbrennen'' von Punkten und Strichen, die die Daten repräsentieren. Gelesen werden diese wiederum durch die Reflektion eines Lasers an diesen Punkten und Strichen.} \label{fig:cd} \end{figure} \subsection{QR-Codes} -Quick Response Codes funktionieren nach einem sehr ähnlichen Prinzip wie in unserem Beispiel, nur dass QR-Codes in einem $\mathbb{F}_{256}$ Körper arbeiten. Je nach grösse der Codierung ist der QR-Code im Endeffekt robuster gegen Beschädigungen. Bei Low Level Codes können 7\% der Daten Wiederhergestellt werden, beim High Level Code sind das sogar 30\%. +Quick Response Codes oder auch QR-Codes funktionieren nach einem sehr ähnlichen Prinzip wie in unserem Beispiel der Abschnitte \ref{reedsolomon:section:codebsp} - \ref{reedsolomon:section:rekonstruktion} nur das QR-Codes in einem $\mathbb{F}_{256}$ Körper arbeiten. Die Physische Grösse eines Codes ist stark abhängig von der Grösse der Codierung sowie dem Fehlerkorrektur-Level. Es ist so auf dem ersten Blick nicht ersichtlich, wie viel Nutzinformationen ein Qr-Code enthält. Die QR-Codes in Abbildung \ref{fig:qr} zeigen jeweils die Gleiche Information mit unterschiedlichem Fehlerkorrektur-Level. Codes mit einem höheren Korrektur-Level können auch für Designer-Codes Zweckentfremdet werden. Dabei wird z.B. das Firmenlogo oder einen Schriftzug über den Qr-Code gelegt, ohne das die Funktion des Codes beeinträchtigt wird. Ein Beispiel dazu ist unter Abbildung \ref{fig:designqr} zu finden. + +% + +%So kann auf den ersten Blick nicht +% +% +% funktionieren nach einem sehr ähnlichen Prinzip wie in unserem Beispiel, nur dass QR-Codes in einem $\mathbb{F}_{256}$ Körper arbeiten. Je nach grösse der Codierung ist der QR-Code im Endeffekt robuster gegen Beschädigungen. Bei Low Level Codes können 7\% der Daten Wiederhergestellt werden, beim High Level Code sind das sogar 30\%. \begin{figure} \centering @@ -88,6 +130,30 @@ Quick Response Codes funktionieren nach einem sehr ähnlichen Prinzip wie in uns \subfigure[]{ \includegraphics[width=0.4\textwidth]{papers/reedsolomon/images/qrcode_l} } - \caption{(a) High Level Code, (b) Low Level Code} +% \subfigure[]{ +% \includegraphics[width=0.4\textwidth]{papers/reedsolomon/images/designer_qrcode_ohnelogo} +% } +% \subfigure[]{ +% \includegraphics[width=0.4\textwidth]{papers/reedsolomon/images/designer_qrcode} +% } + \caption{Anhand der grösse würde man darauf schliessen, dass bei (a) mehr Informationen Codiert sind als bei (b). Tatsächlich aber beinhalten beide Codes die gleiche Information. Das liegt daran, da die Fehlerkorrekturfähigkeit von QR-Codes sich in insgesamt vier Levels aufteilen lassen. Der höchste Fehlerkorrektur-Level, der bei (a) angewendet wurde, ist in der Lage, bis zu 30\% der Daten wiederherzustellen. Der kleinste Level schafft etwa 7\%, der in (b) veranschaulicht wird. Da die Grösse also nichts über die Menge an Daten aussagt, könnte es sich bei (a) auch um einen Code mit viel Nutzdaten und kleinem Fehlerkorrektur-Level handeln. Der Unterschied ist von Auge nicht sichtbar.} \label{fig:qr} \end{figure} + +\begin{figure} + \centering +% \subfigure[]{ +% \includegraphics[width=0.4\textwidth]{papers/reedsolomon/images/qrcode_h} +% } +% \subfigure[]{ +% \includegraphics[width=0.4\textwidth]{papers/reedsolomon/images/qrcode_l} +% } + \subfigure[]{ + \includegraphics[width=0.4\textwidth]{papers/reedsolomon/images/designer_qrcode_ohnelogo} + } + \subfigure[]{ + \includegraphics[width=0.4\textwidth]{papers/reedsolomon/images/designer_qrcode} + } + \caption{Während (a) noch ein unveränderter QR-Code repräsentiert, handelt es sich bei (b) nun um einen Designer-QR-Code. Beide Codes verfügen über einen mittleren Fehlerkorrektur-Level von theoretisch 15\%. Da bei (b) jetzt einen Teil des Codes durch ein Logo verdeckt wird, schränkt sich dadurch die Fehlerkorrekturfähigkeit je nach grösse des verdeckten Teils mehr oder weniger stark ein. Unser Designer-Code in (b) ist nur noch in der Lage etwa 9\% des Codes zu rekonstruieren.} + \label{fig:designqr} +\end{figure}
\ No newline at end of file diff --git a/buch/papers/reedsolomon/dtf.tex b/buch/papers/reedsolomon/dtf.tex index 025be3a..a111527 100644 --- a/buch/papers/reedsolomon/dtf.tex +++ b/buch/papers/reedsolomon/dtf.tex @@ -3,28 +3,53 @@ % % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil % -\section{Diskrete Fourien Transformation +\section{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 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ütlich ist. - -\subsection{Übertragungsabfolge -\label{reedsolomon:subsection:Übertragungsabfolge}} -Das Signal.... sind die Daten, Zahlen welche übertragen werden sollen. -Das speziell ist das wir 100 Punkte übertragen und von 64 bis 100, -werden nur Null Punkte übertragen, dies weiss auch unser Empfänger. -Nun wird das Signal in Abbildung... codiert... -Somit wird die Information jedes Punktes auf das ganze spektrum von 0 bis 100 übertragen. -Kommen nuun drei Fehler... hinzu zu diesem codierten Signal sind diese nicht zu erkennen. -Nach dem Empfangen... und decodieren ... erkennt man die fehlerhafte information in den Punkten 64 bis 100. -Filtert man nur diese Punkte heraus und Transformiert sie mit Fourier erhält man die stellen an denen die Fehler sich eingeschlichen haben. +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} + \hat{c}_{k} + = \frac{1}{N} \sum_{n=0}^{N-1} + {f}_n \cdot e^{-\frac{2\pi j}{N} \cdot kn} + \] +, wenn man nun + \[ + w = e^{-\frac{2\pi j}{N} k} + \] +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) + \] +was überaust ähnlich zu unserem Polynomidee ist. +\subsection{Übertragungsabfolge +\label{reedsolomon:subsection:Übertragungsabfolge}} +\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. +\end{enumerate} +\begin{figure} + \centering + \resizebox{0.9\textwidth}{!}{ + %\includegraphics[width=0.5\textwidth]{papers/reedsolomon/images/plot.pdf} + \input{papers/reedsolomon/images/plotfft.tex} + } + \caption{Übertragungsabfolge \ref{reedsolomon:subsection:Übertragungsabfolge}} + \label{fig:sendorder} +\end{figure}
\ No newline at end of file diff --git a/buch/papers/reedsolomon/einleitung.tex b/buch/papers/reedsolomon/einleitung.tex index 3d40db1..2b1d878 100644 --- a/buch/papers/reedsolomon/einleitung.tex +++ b/buch/papers/reedsolomon/einleitung.tex @@ -6,13 +6,13 @@ \section{Einleitung \label{reedsolomon:section:einleitung}} \rhead{Einleitung} -Der Reed-Solomon-Code ist entstaden im ... vom .. um, -das Problem der Daten Übertragung zu lösen. -In deiesem Abschnitt wird möglichst verständlich die mathematische Abfolge, Funktion oder Algorithmus erklärt. +Der Reed-Solomon-Code ist entstanden um, +das Problem der Fehler, bei der Datenübertragung, zu lösen. +In diesem Abschnitt wird möglichst verständlich die mathematische Abfolge, Funktion oder Algorithmus erklärt. Es wird jedoch nicht auf die technische Umsetzung oder Implementierung eingegangen. -Um beim Daten Übertragen fehler zu erkennen könnte man die Daten jeweils doppelt senden, +Um beim Datenübertragen Fehler zu erkennen, könnte man die Daten jeweils doppelt senden, und so jeweilige Fehler zu erkennen. -Doch dies braucht schnell unmengen an Daten, wenn man nach vielen Fehler absichern möchte. +Doch nur schon um weinige Fehler zu erkennen werden überproportional viele Daten doppelt und dreifach gesendet. Der Reed-Solomon-Code macht dies auf eine andere, clevere Weise. diff --git a/buch/papers/reedsolomon/experiments/codiert.txt b/buch/papers/reedsolomon/experiments/codiert.txt new file mode 100644 index 0000000..4a481d8 --- /dev/null +++ b/buch/papers/reedsolomon/experiments/codiert.txt @@ -0,0 +1,96 @@ +0,284 +1,131.570790435043 +2,41.9840308053375 +3,12.1189172092243 +4,23.8408857476069 +5,69.1793197789512 +6,24.0186013379153 +7,37.3066577242559 +8,18.2010889773887 +9,12.3214904922455 +10,15.6627133315015 +11,24.5237955316204 +12,32.1114345314062 +13,44.9845039238714 +14,13.5324640263625 +15,10.1736266929292 +16,4.58257569495584 +17,23.217268502288 +18,16.5769107917917 +19,6.89948680823017 +20,4.84567134895776 +21,10.4219666223433 +22,43.6179140616243 +23,35.9073375743642 +24,15.0332963783729 +25,21.7594021268945 +26,23.2496572716993 +27,17.9815599423852 +28,11.3577742151117 +29,38.467599433197 +30,28.3035029562577 +31,9.54321919833388 +32,21.377558326432 +33,17.6292439561917 +34,12.6951848921471 +35,20.0667752354841 +36,22.9097309529208 +37,8.78894645948548 +38,13.360682005498 +39,25.1757616314718 +40,38.0357773686457 +41,18.4633287776253 +42,19.0584505869806 +43,10.8631093309173 +44,12.6147770818983 +45,12.5398140021274 +46,34.901983501949 +47,22.3480442021702 +48,6 +49,22.3480442021702 +50,34.901983501949 +51,12.5398140021274 +52,12.6147770818983 +53,10.8631093309173 +54,19.0584505869806 +55,18.4633287776253 +56,38.0357773686457 +57,25.1757616314718 +58,13.360682005498 +59,8.78894645948548 +60,22.9097309529208 +61,20.0667752354841 +62,12.6951848921471 +63,17.6292439561917 +64,21.377558326432 +65,9.54321919833388 +66,28.3035029562577 +67,38.467599433197 +68,11.3577742151117 +69,17.9815599423852 +70,23.2496572716993 +71,21.7594021268945 +72,15.0332963783729 +73,35.9073375743642 +74,43.6179140616243 +75,10.4219666223433 +76,4.84567134895776 +77,6.89948680823017 +78,16.5769107917917 +79,23.217268502288 +80,4.58257569495584 +81,10.1736266929292 +82,13.5324640263625 +83,44.9845039238714 +84,32.1114345314062 +85,24.5237955316204 +86,15.6627133315015 +87,12.3214904922455 +88,18.2010889773887 +89,37.3066577242559 +90,24.0186013379153 +91,69.1793197789512 +92,23.8408857476069 +93,12.1189172092243 +94,41.9840308053375 +95,131.570790435043 diff --git a/buch/papers/reedsolomon/experiments/decodiert.txt b/buch/papers/reedsolomon/experiments/decodiert.txt new file mode 100644 index 0000000..f6221e6 --- /dev/null +++ b/buch/papers/reedsolomon/experiments/decodiert.txt @@ -0,0 +1,96 @@ +0,6.05208333333333 +1,6.02602539785853 +2,0.0261327016093151 +3,5.98927158561317 +4,4.019445724874 +5,0.0247005083663722 +6,4.97798278395618 +7,1.95246440445439 +8,0.974000110512201 +9,2.00528527696027 +10,1.00071804528155 +11,1.97630907888264 +12,0.0232923747656228 +13,6.01302820392331 +14,3.03567381915226 +15,5.02435590137329 +16,7.00526061008995 +17,5.00739608089369 +18,5.02211514480064 +19,4.02175864806658 +20,1.00236543833726 +21,4.98147315261261 +22,8.97728828610336 +23,8.98481304394618 +24,2.98958333333333 +25,1.98491220960989 +26,5.97728835934715 +27,5.98144124907561 +28,4.00163839998525 +29,2.02176249296313 +30,9.02210713874162 +31,1.00742763919872 +32,1.00557258081044 +33,1.02435888848794 +34,2.03577412756745 +35,6.01302820392331 +36,5.97917574041123 +37,0.976310374034338 +38,9.00062625447998 +39,7.00515849238528 +40,6.97396416790894 +41,0.95256880864368 +42,8.97794719866783 +43,9.01850701506487 +44,10.0194409579917 +45,8.98926601525997 +46,7.9866590265379 +47,5.02603060999077 +48,2.05208333333333 +49,4.02603841132848 +50,0.986882897867895 +51,0.0177592928994285 +52,9.01944131204563 +53,3.0185365665612 +54,2.97803642439316 +55,2.95243072164649 +56,4.97396651395488 +57,6.00516695947321 +58,0.0143895905726619 +59,7.97630812771393 +60,5.97917574041123 +61,9.01298821331865 +62,3.03567381915226 +63,4.02435609145793 +64,0.0275599094902563 +65,0.0115837187254191 +66,0.025877761014238 +67,0.0224618032819697 +68,0.04410594689944 +69,0.0474504002669341 +70,0.0227694695500626 +71,0.0271436638090525 +72,0.0104166666666667 +73,0.0271436638090523 +74,0.0227694695500608 +75,0.0474504002669343 +76,0.0441059468994397 +77,0.0224618032819701 +78,0.0258777610142379 +79,0.0115837187254183 +80,0.027559909490256 +81,0.0245124379481793 +82,0.0499782237195209 +83,0.0401432022864265 +84,0.0232923747656228 +85,0.0237974288564099 +86,0.0143895905726624 +87,0.0271745729691685 +88,0.0275599094902567 +89,0.0515501672184983 +90,0.0358255004834542 +91,0.024700508366373 +92,0.0210194725405171 +93,0.0177592928994296 +94,0.0261327016093158 +95,0.0314909067039411 diff --git a/buch/papers/reedsolomon/experiments/empfangen.txt b/buch/papers/reedsolomon/experiments/empfangen.txt new file mode 100644 index 0000000..38c13b0 --- /dev/null +++ b/buch/papers/reedsolomon/experiments/empfangen.txt @@ -0,0 +1,96 @@ +0,284 +1,131.570790435043 +2,41.9840308053375 +3,12.1189172092243 +4,23.8408857476069 +5,69.1793197789512 +6,23.6290258699579 +7,37.3066577242559 +8,18.2010889773887 +9,12.3214904922455 +10,15.6627133315015 +11,24.5237955316204 +12,32.1114345314062 +13,44.9845039238714 +14,13.5324640263625 +15,10.1736266929292 +16,4.58257569495584 +17,23.217268502288 +18,16.5769107917917 +19,6.89948680823017 +20,5.55320238736303 +21,10.4219666223433 +22,43.6179140616243 +23,35.9073375743642 +24,15.0332963783729 +25,21.7594021268945 +26,23.2496572716993 +27,17.9815599423852 +28,11.3577742151117 +29,38.467599433197 +30,28.3035029562577 +31,9.54321919833388 +32,21.377558326432 +33,17.6292439561917 +34,12.6951848921471 +35,20.0667752354841 +36,22.9097309529208 +37,8.78894645948548 +38,13.360682005498 +39,25.1757616314718 +40,38.0357773686457 +41,18.4633287776253 +42,19.0584505869806 +43,10.8631093309173 +44,12.6147770818983 +45,12.5398140021274 +46,34.901983501949 +47,22.3480442021702 +48,6 +49,22.3480442021702 +50,34.901983501949 +51,12.5398140021274 +52,12.6147770818983 +53,10.8631093309173 +54,19.0584505869806 +55,18.4633287776253 +56,38.0357773686457 +57,25.1757616314718 +58,13.360682005498 +59,8.78894645948548 +60,22.9097309529208 +61,20.0667752354841 +62,12.6951848921471 +63,17.6292439561917 +64,21.377558326432 +65,9.54321919833388 +66,28.3035029562577 +67,38.467599433197 +68,11.3577742151117 +69,17.9815599423852 +70,23.2496572716993 +71,21.7594021268945 +72,15.0332963783729 +73,35.9073375743642 +74,44.6135417384784 +75,10.4219666223433 +76,4.84567134895776 +77,6.89948680823017 +78,16.5769107917917 +79,23.217268502288 +80,4.58257569495584 +81,10.1736266929292 +82,13.5324640263625 +83,44.9845039238714 +84,32.1114345314062 +85,24.5237955316204 +86,15.6627133315015 +87,12.3214904922455 +88,18.2010889773887 +89,37.3066577242559 +90,24.0186013379153 +91,69.1793197789512 +92,23.8408857476069 +93,12.1189172092243 +94,41.9840308053375 +95,131.570790435043 diff --git a/buch/papers/reedsolomon/experiments/f.m b/buch/papers/reedsolomon/experiments/f.m index 6bdc741..bf2587c 100644 --- a/buch/papers/reedsolomon/experiments/f.m +++ b/buch/papers/reedsolomon/experiments/f.m @@ -1,8 +1,8 @@ -# -# f.m -- Reed-Solomon-Visualisierung mit FFT -# -# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule -# +% +% f.m -- Reed-Solomon-Visualisierung mit FFT +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule + N = 64; b = 32; l = N + b; @@ -51,6 +51,7 @@ syndrom(1:N,1) = zeros(N,1) plot(abs(syndrom)); xlim([1, l]); title("Syndrom"); + pause() locator = abs(fft(syndrom)) @@ -59,3 +60,13 @@ plot(locator); xlim([1, l]); title("Locator"); pause() + + +writematrix([transpose(counter), abs(signal)], 'signal.txt') +writematrix([transpose(counter), abs(codiert)], 'codiert.txt') +writematrix([transpose(counter), fehler], 'fehler.txt') +writematrix([transpose(counter), abs(empfangen)], 'empfangen.txt') +writematrix([transpose(counter), abs(decodiert)], 'decodiert.txt') +writematrix([transpose(counter), abs(syndrom)], 'syndrom.txt') +writematrix([transpose(counter), locator], 'locator.txt') + diff --git a/buch/papers/reedsolomon/experiments/fehler.txt b/buch/papers/reedsolomon/experiments/fehler.txt new file mode 100644 index 0000000..23f1a83 --- /dev/null +++ b/buch/papers/reedsolomon/experiments/fehler.txt @@ -0,0 +1,96 @@ +0,0 +1,0 +2,0 +3,0 +4,0 +5,0 +6,2 +7,0 +8,0 +9,0 +10,0 +11,0 +12,0 +13,0 +14,0 +15,0 +16,0 +17,0 +18,0 +19,0 +20,2 +21,0 +22,0 +23,0 +24,0 +25,0 +26,0 +27,0 +28,0 +29,0 +30,0 +31,0 +32,0 +33,0 +34,0 +35,0 +36,0 +37,0 +38,0 +39,0 +40,0 +41,0 +42,0 +43,0 +44,0 +45,0 +46,0 +47,0 +48,0 +49,0 +50,0 +51,0 +52,0 +53,0 +54,0 +55,0 +56,0 +57,0 +58,0 +59,0 +60,0 +61,0 +62,0 +63,0 +64,0 +65,0 +66,0 +67,0 +68,0 +69,0 +70,0 +71,0 +72,0 +73,0 +74,1 +75,0 +76,0 +77,0 +78,0 +79,0 +80,0 +81,0 +82,0 +83,0 +84,0 +85,0 +86,0 +87,0 +88,0 +89,0 +90,0 +91,0 +92,0 +93,0 +94,0 +95,0 diff --git a/buch/papers/reedsolomon/experiments/locator.txt b/buch/papers/reedsolomon/experiments/locator.txt new file mode 100644 index 0000000..b28988c --- /dev/null +++ b/buch/papers/reedsolomon/experiments/locator.txt @@ -0,0 +1,96 @@ +0,0.0301224340567056 +1,0.141653026854885 +2,0.138226631799377 +3,0.0339903276086929 +4,0.310585462557496 +5,0.551427312631385 +6,0.628514858396814 +7,0.51102386251559 +8,0.275861355940449 +9,0.0502396354182268 +10,0.090185502547573 +11,0.110759344849756 +12,0.0684618905063001 +13,0.0362855426992259 +14,0.0697096919781468 +15,0.109288539370248 +16,0.0923187999496653 +17,0.0512198536768088 +18,0.274192386987782 +19,0.51349614953654 +20,0.633154426602466 +21,0.553283743533942 +22,0.307840573214514 +23,0.0341664350328392 +24,0.140270857957 +25,0.138527177682831 +26,0.029637547736156 +27,0.0816962563186052 +28,0.0944383203811073 +29,0.0263932110686261 +30,0.0585881348402056 +31,0.0737117341599984 +32,0.0239973937701886 +33,0.0464215468420038 +34,0.0616218854220964 +35,0.0221963086695009 +36,0.0390764778127646 +37,0.0537637218396934 +38,0.0208333333333332 +39,0.0343107696069045 +40,0.0483441215964552 +41,0.0198077862118806 +42,0.0311207395968725 +43,0.0444955089373458 +44,0.0190533549944159 +45,0.0290049795038723 +46,0.0417536642697558 +47,0.0185261550443084 +48,0.0277059929762261 +49,0.0398606084144816 +50,0.0181978813094817 +51,0.0271098219177584 +52,0.0386836665079729 +53,0.0180518611046889 +54,0.0272138992557141 +55,0.0381891287148314 +56,0.0180809085252469 +57,0.0281418959420061 +58,0.0384596362516637 +59,0.0182864418432272 +60,0.0302250788423173 +61,0.0397874837986351 +62,0.0186786556701694 +63,0.0342489348284216 +64,0.0429932815348666 +65,0.0192777878591759 +66,0.0422808966931999 +67,0.0506815964680563 +68,0.0201167847752226 +69,0.0615048274405271 +70,0.0744953894508454 +71,0.021246054596492 +72,0.142602265816215 +73,0.273502052865436 +74,0.325309673287599 +75,0.272705389655349 +76,0.149074257381345 +77,0.0247199397628712 +78,0.0680137859566976 +79,0.075388270873485 +80,0.0273637831604903 +81,0.0407867704453274 +82,0.0632964886441949 +83,0.0309749128751093 +84,0.0315202035072035 +85,0.0627625211892184 +86,0.0360843918243497 +87,0.02794920551495 +88,0.0677921493367236 +89,0.0437167157553067 +90,0.0270640150996317 +91,0.0783380025231622 +92,0.0561293738314281 +93,0.0278742033265809 +94,0.0981443889498639 +95,0.0794543457386548 diff --git a/buch/papers/reedsolomon/experiments/plot.tex b/buch/papers/reedsolomon/experiments/plot.tex new file mode 100644 index 0000000..2196c82 --- /dev/null +++ b/buch/papers/reedsolomon/experiments/plot.tex @@ -0,0 +1,103 @@ +% polynome1 +%------------------- +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{times} +\usepackage{txfonts} +\usepackage{pgfplots} +\usepackage{csvsimple} +\usepackage{pgfplotstable} +\usepackage{filecontents} +\usetikzlibrary{arrows,intersections,math} +\newcommand{\x}{10} +\newcommand{\y}{-8} +\begin{document} + +\begin{tikzpicture}[] + + %--------------------------------------------------------------- + %Knote + \matrix[draw = none, column sep=20mm, row sep=4mm]{ + \node(signal) [] { + \begin{tikzpicture} + \begin{axis}[ + title = {\Large {Signal}}, + xlabel={Anzahl Übertragene Zahlen}, + xtick={0,20,40,64,80,98},] + \addplot[blue] table[col sep=comma] {signal.txt}; + \end{axis} + \end{tikzpicture}}; & + + \node(codiert) [] { + \begin{tikzpicture} + \begin{axis}[title = {\Large {Codiert}}] + \addplot[] table[col sep=comma] {codiert.txt}; + \end{axis} + \end{tikzpicture}}; \\ + + &\node(fehler) [] { + \begin{tikzpicture} + \begin{axis}[scale=0.6, title = {\Large {Fehler}}] + \addplot[red] table[col sep=comma] {fehler.txt}; + \end{axis} + \end{tikzpicture}};\\ + + \node(decodiert) [] { + \begin{tikzpicture} + \begin{axis}[title = {\Large {Decodiert}}] + \addplot[blue] table[col sep=comma] {decodiert.txt}; + \end{axis} + \end{tikzpicture}}; & + + \node(empfangen) [] { + \begin{tikzpicture} + \begin{axis}[title = {\Large {Empfangen}}] + \addplot[] table[col sep=comma] {empfangen.txt}; + \end{axis} + \end{tikzpicture}};\\ + + \node(syndrom) [] { + \begin{tikzpicture} + \begin{axis}[title = {\Large {Syndrom}}] + \addplot[blue] table[col sep=comma] {syndrom.txt}; + \end{axis} + \end{tikzpicture}}; & + + \node(locator) [] { + \begin{tikzpicture} + \begin{axis}[title = {\Large {Locator}}] + \addplot[] table[col sep=comma] {locator.txt}; + \end{axis} + \end{tikzpicture}};\\ + }; + %------------------------------------------------------------- + %FFT & IFFT deskription + + \draw[thin,gray,dashed] (0,12) to (0,-12); + \node(IFFT) [scale=0.7] at (0,12.3) {IFFT}; + \draw[<-](IFFT.south west)--(IFFT.south east); + \node(FFT) [scale=0.7, above of=IFFT] {FFT}; + \draw[->](FFT.north west)--(FFT.north east); + + \draw[thick, ->,] (fehler.west)++(-1,0) +(0.05,0.5) -- +(-0.1,-0.1) -- +(0.1,0.1) -- +(0,-0.5); + %Arrows + \draw[ultra thick, ->] (signal.east) to (codiert.west); + \draw[ultra thick, ->] (codiert.south) to (fehler.north); + \draw[ultra thick, ->] (fehler.south) to (empfangen.north); + \draw[ultra thick, ->] (empfangen.west) to (decodiert.east); + \draw[ultra thick, ->] (syndrom.east) to (locator.west); + \draw(decodiert.south east)++(-1.8,1) ellipse (1.3cm and 0.8cm) ++(-1.3,0) coordinate(zoom) ; + \draw[ultra thick, ->] (zoom) to[out=180, in=90] (syndrom.north); + + %item + \node[circle, draw, fill =lightgray] at (signal.north west)+(1,0) {1}; + \node[circle, draw, fill =lightgray] at (codiert.north west) {2}; + \node[circle, draw, fill =lightgray] at (fehler.north west) {3}; + \node[circle, draw, fill =lightgray] at (empfangen.north west) {4}; + \node[circle, draw, fill =lightgray] at (decodiert.north west) {5}; + \node[circle, draw, fill =lightgray] at (syndrom.north west) {6}; + \node[circle, draw, fill =lightgray] at (locator.north west) {7}; + +\end{tikzpicture} +\end{document} + diff --git a/buch/papers/reedsolomon/experiments/signal.txt b/buch/papers/reedsolomon/experiments/signal.txt new file mode 100644 index 0000000..c4fa5f8 --- /dev/null +++ b/buch/papers/reedsolomon/experiments/signal.txt @@ -0,0 +1,96 @@ +0,6 +1,6 +2,0 +3,6 +4,4 +5,0 +6,5 +7,2 +8,1 +9,2 +10,1 +11,2 +12,0 +13,6 +14,3 +15,5 +16,7 +17,5 +18,5 +19,4 +20,1 +21,5 +22,9 +23,9 +24,3 +25,2 +26,6 +27,6 +28,4 +29,2 +30,9 +31,1 +32,1 +33,1 +34,2 +35,6 +36,6 +37,1 +38,9 +39,7 +40,7 +41,1 +42,9 +43,9 +44,10 +45,9 +46,8 +47,5 +48,2 +49,4 +50,1 +51,0 +52,9 +53,3 +54,3 +55,3 +56,5 +57,6 +58,0 +59,8 +60,6 +61,9 +62,3 +63,4 +64,0 +65,0 +66,0 +67,0 +68,0 +69,0 +70,0 +71,0 +72,0 +73,0 +74,0 +75,0 +76,0 +77,0 +78,0 +79,0 +80,0 +81,0 +82,0 +83,0 +84,0 +85,0 +86,0 +87,0 +88,0 +89,0 +90,0 +91,0 +92,0 +93,0 +94,0 +95,0 diff --git a/buch/papers/reedsolomon/experiments/syndrom.txt b/buch/papers/reedsolomon/experiments/syndrom.txt new file mode 100644 index 0000000..8ca9eed --- /dev/null +++ b/buch/papers/reedsolomon/experiments/syndrom.txt @@ -0,0 +1,96 @@ +0,0 +1,0 +2,0 +3,0 +4,0 +5,0 +6,0 +7,0 +8,0 +9,0 +10,0 +11,0 +12,0 +13,0 +14,0 +15,0 +16,0 +17,0 +18,0 +19,0 +20,0 +21,0 +22,0 +23,0 +24,0 +25,0 +26,0 +27,0 +28,0 +29,0 +30,0 +31,0 +32,0 +33,0 +34,0 +35,0 +36,0 +37,0 +38,0 +39,0 +40,0 +41,0 +42,0 +43,0 +44,0 +45,0 +46,0 +47,0 +48,0 +49,0 +50,0 +51,0 +52,0 +53,0 +54,0 +55,0 +56,0 +57,0 +58,0 +59,0 +60,0 +61,0 +62,0 +63,0 +64,0.0275599094902563 +65,0.0115837187254191 +66,0.025877761014238 +67,0.0224618032819697 +68,0.04410594689944 +69,0.0474504002669341 +70,0.0227694695500626 +71,0.0271436638090525 +72,0.0104166666666667 +73,0.0271436638090523 +74,0.0227694695500608 +75,0.0474504002669343 +76,0.0441059468994397 +77,0.0224618032819701 +78,0.0258777610142379 +79,0.0115837187254183 +80,0.027559909490256 +81,0.0245124379481793 +82,0.0499782237195209 +83,0.0401432022864265 +84,0.0232923747656228 +85,0.0237974288564099 +86,0.0143895905726624 +87,0.0271745729691685 +88,0.0275599094902567 +89,0.0515501672184983 +90,0.0358255004834542 +91,0.024700508366373 +92,0.0210194725405171 +93,0.0177592928994296 +94,0.0261327016093158 +95,0.0314909067039411 diff --git a/buch/papers/reedsolomon/idee.tex b/buch/papers/reedsolomon/idee.tex index 4a7716a..39adbbf 100644 --- a/buch/papers/reedsolomon/idee.tex +++ b/buch/papers/reedsolomon/idee.tex @@ -8,51 +8,81 @@ \rhead{Problemstellung} Das Problem liegt darin Informationen, Zahlen, zu Übertragen und Fehler zu erkennen. -Beim Reed-Solomon-Code kann man nicht nur Fehler erkenen, +Beim Reed-Solomon-Code kann man nicht nur Fehler erkennen, man kann sogar einige Fehler korrigieren. \rhead{Polynom-Ansatz} -Eine Idee ist die Daten, -ein Polynom zu bilden und dieses dann mit bestimmten Punkten überträgt. +Eine Idee ist aus den Daten +ein Polynom zu bilden. +Diese Polynomfunktion bei bestimmten Werten, ausrechnet und diese Punkte dann überträgt. Nehmen wir als beisbiel die Zahlen \textcolor{blue}{2}, \textcolor{blue}{1}, \textcolor{blue}{5}, welche uns dann das Polynom \begin{equation} p(x) = -2x^2 + 1x + 5 +\textcolor{blue}{2}x^2 + \textcolor{blue}{1}x + \textcolor{blue}{5} \label{reedsolomon:equation1} \end{equation} ergeben. -Übertragen werden nun die stellen 1, 2, 3\dots 7 dieses Polynomes. -Grafisch sieht man dies dann im Abbild //TODO -Wenn ein Fehler sich in die Übertragung eingeschlichen hatt, muss der Leser/Empfänger erkennen, welches das Richtige Polynom ist. -Der Leser/Empfänger weiss, mit welchem Grad das Polynom entwickelt wurde. +Übertragen werden nun die Werte an den stellen 1, 2, 3\dots 7 dieses Polynomes. +Grafisch sieht man dies dann in Abbildung \ref{fig:polynom}, +mit den Punkten, $p(1),p(2),...,p(7) = (\textcolor{green}{8}, +\textcolor{green}{15}, \textcolor{green}{26}, +\textcolor{green}{41}, \textcolor{green}{60}, +\textcolor{green}{83}, \textcolor{green}{110})$ +Wenn ein Fehler sich in die Übertragung eingeschlichen hatt, muss der Leser/Empfänger diesen erkennen und das Polynom rekonstruieren. +Der Leser/Empfänger weiss, den Grad des Polynoms und dessen Werte übermittelt wurden. + \subsection{Beispiel} -Für das Beispeil aus der Gleichung \ref{reedsolomon:equation1}, +Für das Beispeil aus der Gleichung \eqref{reedsolomon:equation1}, ist ein Polynome zweiten Grades durch drei Punkte eindeutig bestimmbar. -Hat es Fehler in der Übertragunge gegeben, kann man diese erkennen, -da alle Punkte, die korrekt sind, auf dem Polynom liegen müssen. +Hat es Fehler in der Übertragunge gegeben,(Bei Abbildung \ref{fig:polynom}\textcolor{red}{roten Punkte}) kann man diese erkennen, +da alle Punkte, die korrekt sind, auf dem Polynom liegen müssen. +(Bei Abbildung \ref{fig:polynom}\textcolor{green}{grünen Punkte}) Ab wie vielen Fehler ist das Polynom nicht mehr erkennbar beim Übertragen von 7 Punkten? Bei 2 Fehlern kann man noch eindeutig bestimmen, dass das Polynom mit 4 Punkten, -gegenüber dem mit 5 Punkten falsch liegt. -Werden es mehr Fehler kann nur erkennt werden das das Polynom nicht stimmt. -Das Orginale Polynom kann aber nicht mehr gefunden werden. -Dabei sollten mehr Übertragungspunkte gegeben werden. +gegenüber dem mit 5 Punkten falsch liegt.\ref{fig:polynom} +Werden es mehr Fehler kann nur erkennt werden, dass das Polynom nicht stimmt. +Das orginale Polynom kann aber nicht mehr gefunden werden. +Dafür sind mehr übertragene Werte nötig. + +\begin{figure} + \centering + %\includegraphics[width=0.5\textwidth]{papers/reedsolomon/images/polynom2} + \input{papers/reedsolomon/images/polynom2.tex} + \caption{Polynom $p(x)$ \eqref{reedsolomon:equation1}} + \label{fig:polynom} +\end{figure} \section{Fehlerbestimmung \label{reedsolomon:section:Fehlerbestimmmung}} So wird ein Muster indentifiziert, welches genau vorherbestimmen kann, wie gross das Polynom sein muss und wie viele Übertragungspunkte gegeben werden müssen. -Durch ein klein wenig Überlegung ist klar das die anzahl Zahlen (Daten, ab hier verwenden wir das Wort Nutzlast), -die dan Entschlüsselt werden sollen den Grad des Polynoms minus 1 ergeben. +Um zu bestimmen wie viel Fehler erkennt und korriegiert werden können. +Die Anzahl Zahlen (Daten, ab hier verwenden wir das Wort Nutzlast), +die Entschlüsselt werden sollen, brauchen die gleiche Anzahl an Polynomgraden, beginnend bei Grad 0. ( \( k-1 \) ) Für die Anzahl an Übertragungspunkte, muss bestimmt werden wieviel Fehler erkennt und korrigiert werden sollen. -Mit Hilfe der Tabelle.... sieht man das es bei $$t$$ Fehlern und $$k$$ Nutzlast, -für das Übertragen $$k+2t$$ Punkte gegben werden müssen. +Mit Hilfe der Tabelle, sieht man das es bei $t$ Fehlern und $k$ Nutzlast Zahlen, +$k+2t$ Punkte übertragen werden müssen. -Ein toller Nebeneffekt ist das dadurch auch $$2t$$ Fehler erkannt werden. -um zurück auf unser Beispiel zu kommen, -können von den 7 Übertragungspunkten bis zu $$2t = 2*2 = 4 $$ Punkten falsch liegen -und es wird kein eindeutiges Polynom 2ten Grades erkannt, und somit die Nutzlast Daten als fehlerhaft deklariert. +\begin{center} + \begin{tabular}{ c c c } + \hline + Nutzlas & Fehler & Übertragen \\ + \hline + 3 & 2 & 7 Werte eines Polynoms vom Grad 2 \\ + 4 & 2 & 8 Werte eines Polynoms vom Grad 3 \\ + 3 & 3 & 9 Werte eines Polynoms vom Grad 2 \\ + \hline + $k$ & $t$ & $k+2t$ Werte eines Polynoms vom Grad $k-1$ \\ + \hline + \end{tabular} +\end{center} -Ein Polynom durch Punkt mit Polynom Interpolation zu rekonstruieren ist schwierig und Fehleranfällig. +Ein toller Nebeneffekt ist das dadurch auch $2t$ Fehler erkannt werden. +Um zurück auf unser Beispiel zu kommen, +können von den 7 Übertragungspunkten bis zu $2t = 2\cdot2 = 4 $ Punkten falsch liegen +und es wird kein eindeutiges Polynom zweiten Grades erkannt, und somit die Nutzlast Daten als fehlerhaft deklariert. +Um aus den Übertragenen Zahlen wieder die Nutzlastzahlen zu bekommen könnte man eine Polynominterpolation anwenden, +doch die Punkte mit Polynominterpolation zu einem Polynom zu rekonstruieren ist schwierig und Fehleranfällig. diff --git a/buch/papers/reedsolomon/images/codiert.txt b/buch/papers/reedsolomon/images/codiert.txt new file mode 100644 index 0000000..4a481d8 --- /dev/null +++ b/buch/papers/reedsolomon/images/codiert.txt @@ -0,0 +1,96 @@ +0,284 +1,131.570790435043 +2,41.9840308053375 +3,12.1189172092243 +4,23.8408857476069 +5,69.1793197789512 +6,24.0186013379153 +7,37.3066577242559 +8,18.2010889773887 +9,12.3214904922455 +10,15.6627133315015 +11,24.5237955316204 +12,32.1114345314062 +13,44.9845039238714 +14,13.5324640263625 +15,10.1736266929292 +16,4.58257569495584 +17,23.217268502288 +18,16.5769107917917 +19,6.89948680823017 +20,4.84567134895776 +21,10.4219666223433 +22,43.6179140616243 +23,35.9073375743642 +24,15.0332963783729 +25,21.7594021268945 +26,23.2496572716993 +27,17.9815599423852 +28,11.3577742151117 +29,38.467599433197 +30,28.3035029562577 +31,9.54321919833388 +32,21.377558326432 +33,17.6292439561917 +34,12.6951848921471 +35,20.0667752354841 +36,22.9097309529208 +37,8.78894645948548 +38,13.360682005498 +39,25.1757616314718 +40,38.0357773686457 +41,18.4633287776253 +42,19.0584505869806 +43,10.8631093309173 +44,12.6147770818983 +45,12.5398140021274 +46,34.901983501949 +47,22.3480442021702 +48,6 +49,22.3480442021702 +50,34.901983501949 +51,12.5398140021274 +52,12.6147770818983 +53,10.8631093309173 +54,19.0584505869806 +55,18.4633287776253 +56,38.0357773686457 +57,25.1757616314718 +58,13.360682005498 +59,8.78894645948548 +60,22.9097309529208 +61,20.0667752354841 +62,12.6951848921471 +63,17.6292439561917 +64,21.377558326432 +65,9.54321919833388 +66,28.3035029562577 +67,38.467599433197 +68,11.3577742151117 +69,17.9815599423852 +70,23.2496572716993 +71,21.7594021268945 +72,15.0332963783729 +73,35.9073375743642 +74,43.6179140616243 +75,10.4219666223433 +76,4.84567134895776 +77,6.89948680823017 +78,16.5769107917917 +79,23.217268502288 +80,4.58257569495584 +81,10.1736266929292 +82,13.5324640263625 +83,44.9845039238714 +84,32.1114345314062 +85,24.5237955316204 +86,15.6627133315015 +87,12.3214904922455 +88,18.2010889773887 +89,37.3066577242559 +90,24.0186013379153 +91,69.1793197789512 +92,23.8408857476069 +93,12.1189172092243 +94,41.9840308053375 +95,131.570790435043 diff --git a/buch/papers/reedsolomon/images/decodiert.txt b/buch/papers/reedsolomon/images/decodiert.txt new file mode 100644 index 0000000..f6221e6 --- /dev/null +++ b/buch/papers/reedsolomon/images/decodiert.txt @@ -0,0 +1,96 @@ +0,6.05208333333333 +1,6.02602539785853 +2,0.0261327016093151 +3,5.98927158561317 +4,4.019445724874 +5,0.0247005083663722 +6,4.97798278395618 +7,1.95246440445439 +8,0.974000110512201 +9,2.00528527696027 +10,1.00071804528155 +11,1.97630907888264 +12,0.0232923747656228 +13,6.01302820392331 +14,3.03567381915226 +15,5.02435590137329 +16,7.00526061008995 +17,5.00739608089369 +18,5.02211514480064 +19,4.02175864806658 +20,1.00236543833726 +21,4.98147315261261 +22,8.97728828610336 +23,8.98481304394618 +24,2.98958333333333 +25,1.98491220960989 +26,5.97728835934715 +27,5.98144124907561 +28,4.00163839998525 +29,2.02176249296313 +30,9.02210713874162 +31,1.00742763919872 +32,1.00557258081044 +33,1.02435888848794 +34,2.03577412756745 +35,6.01302820392331 +36,5.97917574041123 +37,0.976310374034338 +38,9.00062625447998 +39,7.00515849238528 +40,6.97396416790894 +41,0.95256880864368 +42,8.97794719866783 +43,9.01850701506487 +44,10.0194409579917 +45,8.98926601525997 +46,7.9866590265379 +47,5.02603060999077 +48,2.05208333333333 +49,4.02603841132848 +50,0.986882897867895 +51,0.0177592928994285 +52,9.01944131204563 +53,3.0185365665612 +54,2.97803642439316 +55,2.95243072164649 +56,4.97396651395488 +57,6.00516695947321 +58,0.0143895905726619 +59,7.97630812771393 +60,5.97917574041123 +61,9.01298821331865 +62,3.03567381915226 +63,4.02435609145793 +64,0.0275599094902563 +65,0.0115837187254191 +66,0.025877761014238 +67,0.0224618032819697 +68,0.04410594689944 +69,0.0474504002669341 +70,0.0227694695500626 +71,0.0271436638090525 +72,0.0104166666666667 +73,0.0271436638090523 +74,0.0227694695500608 +75,0.0474504002669343 +76,0.0441059468994397 +77,0.0224618032819701 +78,0.0258777610142379 +79,0.0115837187254183 +80,0.027559909490256 +81,0.0245124379481793 +82,0.0499782237195209 +83,0.0401432022864265 +84,0.0232923747656228 +85,0.0237974288564099 +86,0.0143895905726624 +87,0.0271745729691685 +88,0.0275599094902567 +89,0.0515501672184983 +90,0.0358255004834542 +91,0.024700508366373 +92,0.0210194725405171 +93,0.0177592928994296 +94,0.0261327016093158 +95,0.0314909067039411 diff --git a/buch/papers/reedsolomon/images/designer_qrcode.png b/buch/papers/reedsolomon/images/designer_qrcode.png Binary files differnew file mode 100644 index 0000000..a9e0505 --- /dev/null +++ b/buch/papers/reedsolomon/images/designer_qrcode.png diff --git a/buch/papers/reedsolomon/images/designer_qrcode_ohnelogo.png b/buch/papers/reedsolomon/images/designer_qrcode_ohnelogo.png Binary files differnew file mode 100644 index 0000000..fe4251d --- /dev/null +++ b/buch/papers/reedsolomon/images/designer_qrcode_ohnelogo.png diff --git a/buch/papers/reedsolomon/images/empfangen.txt b/buch/papers/reedsolomon/images/empfangen.txt new file mode 100644 index 0000000..38c13b0 --- /dev/null +++ b/buch/papers/reedsolomon/images/empfangen.txt @@ -0,0 +1,96 @@ +0,284 +1,131.570790435043 +2,41.9840308053375 +3,12.1189172092243 +4,23.8408857476069 +5,69.1793197789512 +6,23.6290258699579 +7,37.3066577242559 +8,18.2010889773887 +9,12.3214904922455 +10,15.6627133315015 +11,24.5237955316204 +12,32.1114345314062 +13,44.9845039238714 +14,13.5324640263625 +15,10.1736266929292 +16,4.58257569495584 +17,23.217268502288 +18,16.5769107917917 +19,6.89948680823017 +20,5.55320238736303 +21,10.4219666223433 +22,43.6179140616243 +23,35.9073375743642 +24,15.0332963783729 +25,21.7594021268945 +26,23.2496572716993 +27,17.9815599423852 +28,11.3577742151117 +29,38.467599433197 +30,28.3035029562577 +31,9.54321919833388 +32,21.377558326432 +33,17.6292439561917 +34,12.6951848921471 +35,20.0667752354841 +36,22.9097309529208 +37,8.78894645948548 +38,13.360682005498 +39,25.1757616314718 +40,38.0357773686457 +41,18.4633287776253 +42,19.0584505869806 +43,10.8631093309173 +44,12.6147770818983 +45,12.5398140021274 +46,34.901983501949 +47,22.3480442021702 +48,6 +49,22.3480442021702 +50,34.901983501949 +51,12.5398140021274 +52,12.6147770818983 +53,10.8631093309173 +54,19.0584505869806 +55,18.4633287776253 +56,38.0357773686457 +57,25.1757616314718 +58,13.360682005498 +59,8.78894645948548 +60,22.9097309529208 +61,20.0667752354841 +62,12.6951848921471 +63,17.6292439561917 +64,21.377558326432 +65,9.54321919833388 +66,28.3035029562577 +67,38.467599433197 +68,11.3577742151117 +69,17.9815599423852 +70,23.2496572716993 +71,21.7594021268945 +72,15.0332963783729 +73,35.9073375743642 +74,44.6135417384784 +75,10.4219666223433 +76,4.84567134895776 +77,6.89948680823017 +78,16.5769107917917 +79,23.217268502288 +80,4.58257569495584 +81,10.1736266929292 +82,13.5324640263625 +83,44.9845039238714 +84,32.1114345314062 +85,24.5237955316204 +86,15.6627133315015 +87,12.3214904922455 +88,18.2010889773887 +89,37.3066577242559 +90,24.0186013379153 +91,69.1793197789512 +92,23.8408857476069 +93,12.1189172092243 +94,41.9840308053375 +95,131.570790435043 diff --git a/buch/papers/reedsolomon/images/fehler.txt b/buch/papers/reedsolomon/images/fehler.txt new file mode 100644 index 0000000..23f1a83 --- /dev/null +++ b/buch/papers/reedsolomon/images/fehler.txt @@ -0,0 +1,96 @@ +0,0 +1,0 +2,0 +3,0 +4,0 +5,0 +6,2 +7,0 +8,0 +9,0 +10,0 +11,0 +12,0 +13,0 +14,0 +15,0 +16,0 +17,0 +18,0 +19,0 +20,2 +21,0 +22,0 +23,0 +24,0 +25,0 +26,0 +27,0 +28,0 +29,0 +30,0 +31,0 +32,0 +33,0 +34,0 +35,0 +36,0 +37,0 +38,0 +39,0 +40,0 +41,0 +42,0 +43,0 +44,0 +45,0 +46,0 +47,0 +48,0 +49,0 +50,0 +51,0 +52,0 +53,0 +54,0 +55,0 +56,0 +57,0 +58,0 +59,0 +60,0 +61,0 +62,0 +63,0 +64,0 +65,0 +66,0 +67,0 +68,0 +69,0 +70,0 +71,0 +72,0 +73,0 +74,1 +75,0 +76,0 +77,0 +78,0 +79,0 +80,0 +81,0 +82,0 +83,0 +84,0 +85,0 +86,0 +87,0 +88,0 +89,0 +90,0 +91,0 +92,0 +93,0 +94,0 +95,0 diff --git a/buch/papers/reedsolomon/images/locator.txt b/buch/papers/reedsolomon/images/locator.txt new file mode 100644 index 0000000..b28988c --- /dev/null +++ b/buch/papers/reedsolomon/images/locator.txt @@ -0,0 +1,96 @@ +0,0.0301224340567056 +1,0.141653026854885 +2,0.138226631799377 +3,0.0339903276086929 +4,0.310585462557496 +5,0.551427312631385 +6,0.628514858396814 +7,0.51102386251559 +8,0.275861355940449 +9,0.0502396354182268 +10,0.090185502547573 +11,0.110759344849756 +12,0.0684618905063001 +13,0.0362855426992259 +14,0.0697096919781468 +15,0.109288539370248 +16,0.0923187999496653 +17,0.0512198536768088 +18,0.274192386987782 +19,0.51349614953654 +20,0.633154426602466 +21,0.553283743533942 +22,0.307840573214514 +23,0.0341664350328392 +24,0.140270857957 +25,0.138527177682831 +26,0.029637547736156 +27,0.0816962563186052 +28,0.0944383203811073 +29,0.0263932110686261 +30,0.0585881348402056 +31,0.0737117341599984 +32,0.0239973937701886 +33,0.0464215468420038 +34,0.0616218854220964 +35,0.0221963086695009 +36,0.0390764778127646 +37,0.0537637218396934 +38,0.0208333333333332 +39,0.0343107696069045 +40,0.0483441215964552 +41,0.0198077862118806 +42,0.0311207395968725 +43,0.0444955089373458 +44,0.0190533549944159 +45,0.0290049795038723 +46,0.0417536642697558 +47,0.0185261550443084 +48,0.0277059929762261 +49,0.0398606084144816 +50,0.0181978813094817 +51,0.0271098219177584 +52,0.0386836665079729 +53,0.0180518611046889 +54,0.0272138992557141 +55,0.0381891287148314 +56,0.0180809085252469 +57,0.0281418959420061 +58,0.0384596362516637 +59,0.0182864418432272 +60,0.0302250788423173 +61,0.0397874837986351 +62,0.0186786556701694 +63,0.0342489348284216 +64,0.0429932815348666 +65,0.0192777878591759 +66,0.0422808966931999 +67,0.0506815964680563 +68,0.0201167847752226 +69,0.0615048274405271 +70,0.0744953894508454 +71,0.021246054596492 +72,0.142602265816215 +73,0.273502052865436 +74,0.325309673287599 +75,0.272705389655349 +76,0.149074257381345 +77,0.0247199397628712 +78,0.0680137859566976 +79,0.075388270873485 +80,0.0273637831604903 +81,0.0407867704453274 +82,0.0632964886441949 +83,0.0309749128751093 +84,0.0315202035072035 +85,0.0627625211892184 +86,0.0360843918243497 +87,0.02794920551495 +88,0.0677921493367236 +89,0.0437167157553067 +90,0.0270640150996317 +91,0.0783380025231622 +92,0.0561293738314281 +93,0.0278742033265809 +94,0.0981443889498639 +95,0.0794543457386548 diff --git a/buch/papers/reedsolomon/images/plotfft.tex b/buch/papers/reedsolomon/images/plotfft.tex new file mode 100644 index 0000000..83a89eb --- /dev/null +++ b/buch/papers/reedsolomon/images/plotfft.tex @@ -0,0 +1,89 @@ +% +% Plot der Übertrangungsabfolge ins FFT und zurück mit IFFT +% +\begin{tikzpicture}[] + +%--------------------------------------------------------------- + %Knote +\matrix[draw = none, column sep=25mm, row sep=2mm]{ + \node(signal) [] { + \begin{tikzpicture} + \begin{axis} + [title = {\Large {Signal}}, + xlabel={Anzahl Übertragene Zahlen}, + xtick={0,20,40,64,80,98},] + \addplot[blue] table[col sep=comma] {papers/reedsolomon/images/signal.txt}; + \end{axis} + \end{tikzpicture}}; & + + \node(codiert) [] { + \begin{tikzpicture} + \begin{axis}[title = {\Large {Codiert}}] + \addplot[] table[col sep=comma] {papers/reedsolomon/images/codiert.txt}; + \end{axis} + \end{tikzpicture}}; \\ + + &\node(fehler) [] { + \begin{tikzpicture} + \begin{axis}[scale=0.6, title = {\Large {Fehler}}, + xtick={7,21,75}] + \addplot[red] table[col sep=comma] {papers/reedsolomon/images/fehler.txt}; + \end{axis} + \end{tikzpicture}};\\ + + \node(decodiert) [] { + \begin{tikzpicture} + \begin{axis}[title = {\Large {Decodiert}}] + \addplot[blue] table[col sep=comma] {papers/reedsolomon/images/decodiert.txt}; + \end{axis} + \end{tikzpicture}}; & + + \node(empfangen) [] { + \begin{tikzpicture} + \begin{axis}[title = {\Large {Empfangen}}] + \addplot[] table[col sep=comma] {papers/reedsolomon/images/empfangen.txt}; + \end{axis} + \end{tikzpicture}};\\ + + \node(syndrom) [] { + \begin{tikzpicture} + \begin{axis}[title = {\Large {Syndrom}}] + \addplot[blue] table[col sep=comma] {papers/reedsolomon/images/syndrom.txt}; + \end{axis} + \end{tikzpicture}}; & + + \node(locator) [] { + \begin{tikzpicture} + \begin{axis}[title = {\Large {Locator}}] + \addplot[] table[col sep=comma] {papers/reedsolomon/images/locator.txt}; + \end{axis} + \end{tikzpicture}};\\ +}; +%------------------------------------------------------------- + %FFT & IFFT deskription + +\draw[thin,gray,dashed] (0,12) to (0,-12); +\node(IFFT) [scale=0.7] at (0,12.3) {IFFT}; +\draw[<-](IFFT.south west)--(IFFT.south east); +\node(FFT) [scale=0.7, above of=IFFT] {FFT}; +\draw[->](FFT.north west)--(FFT.north east); + +\draw[thick, ->,] (fehler.west)++(-1,0) +(0.05,0.5) -- +(-0.1,-0.1) -- +(0.1,0.1) -- +(0,-0.5); +%Arrows +\draw[ultra thick, ->] (signal.east) to (codiert.west); +\draw[ultra thick, ->] (codiert.south) to (fehler.north); +\draw[ultra thick, ->] (fehler.south) to (empfangen.north); +\draw[ultra thick, ->] (empfangen.west) to (decodiert.east); +\draw[ultra thick, ->] (syndrom.east) to (locator.west); +\draw(decodiert.south east)++(-1.8,1) ellipse (1.3cm and 0.8cm) ++(-1.3,0) coordinate(zoom) ; +\draw[ultra thick, ->] (zoom) to[out=180, in=90] (syndrom.north); + +%item +\node[circle, draw, fill =lightgray] at (signal.north west) {1}; +\node[circle, draw, fill =lightgray] at (codiert.north west) {2}; +\node[circle, draw, fill =lightgray] at (fehler.north west) {3}; +\node[circle, draw, fill =lightgray] at (empfangen.north west) {4}; +\node[circle, draw, fill =lightgray] at (decodiert.north west) {5}; +\node[circle, draw, fill =lightgray] at (syndrom.north west) {6}; +\node[circle, draw, fill =lightgray] at (locator.north west) {7}; +\end{tikzpicture}
\ No newline at end of file diff --git a/buch/papers/reedsolomon/images/polynom2.tex b/buch/papers/reedsolomon/images/polynom2.tex new file mode 100644 index 0000000..288b51c --- /dev/null +++ b/buch/papers/reedsolomon/images/polynom2.tex @@ -0,0 +1,49 @@ +% polynome +%------------------- +% Teiler für das Skalieren der Grafik /40 +\newcommand{\teiler}{40} + + +%////////////////////////////////////// + +\begin{tikzpicture}[>=latex,thick] + \draw[color=blue, line width=1.4pt] + plot[domain=0:8, samples=100] + ({\x},{(2*\x^2+1*\x+5)/\teiler}); + + \draw[->] (-0.2,0) -- (8,0) coordinate[label={$x$}]; + \draw[->] (0,-0.2) -- (0,150/\teiler) coordinate[label={right:$p(x)$}]; + + \def\punkt#1{ + \fill[color=green] #1 circle[radius=0.08]; + \draw #1 circle[radius=0.07]; + } + + \def\hellpunkt#1{ + \fill[color=lightgray] #1 circle[radius=0.08]; + \draw #1 circle[radius=0.07]; + } + + \punkt{(1,8/\teiler)} + \hellpunkt{(2,15/\teiler)} + \hellpunkt{(3,26/\teiler)} + \punkt{(4,41/\teiler)} + \punkt{(5,60/\teiler)} + \punkt{(6,83/\teiler)} + \punkt{(7,110/\teiler)} + + \draw[color=gray,line width=1pt,dashed] + plot[domain=0.5:7, samples=100] + ({\x},{(7.832*\x^2-51.5*\x+121.668)/\teiler}); + + \def\erpunkt#1{ + \fill[color=red] #1 circle[radius=0.08]; + \draw #1 circle[radius=0.07]; + } + \erpunkt{(2,50/\teiler)} + \erpunkt{(3,37.66/\teiler)} + + \draw(0,100/\teiler) -- (-0.1,100/\teiler) coordinate[label={left:$100$}]; + \draw(1,0) -- (1,-0.1) coordinate[label={below:$1$}]; +\end{tikzpicture} +%\end{document} diff --git a/buch/papers/reedsolomon/images/signal.txt b/buch/papers/reedsolomon/images/signal.txt new file mode 100644 index 0000000..c4fa5f8 --- /dev/null +++ b/buch/papers/reedsolomon/images/signal.txt @@ -0,0 +1,96 @@ +0,6 +1,6 +2,0 +3,6 +4,4 +5,0 +6,5 +7,2 +8,1 +9,2 +10,1 +11,2 +12,0 +13,6 +14,3 +15,5 +16,7 +17,5 +18,5 +19,4 +20,1 +21,5 +22,9 +23,9 +24,3 +25,2 +26,6 +27,6 +28,4 +29,2 +30,9 +31,1 +32,1 +33,1 +34,2 +35,6 +36,6 +37,1 +38,9 +39,7 +40,7 +41,1 +42,9 +43,9 +44,10 +45,9 +46,8 +47,5 +48,2 +49,4 +50,1 +51,0 +52,9 +53,3 +54,3 +55,3 +56,5 +57,6 +58,0 +59,8 +60,6 +61,9 +62,3 +63,4 +64,0 +65,0 +66,0 +67,0 +68,0 +69,0 +70,0 +71,0 +72,0 +73,0 +74,0 +75,0 +76,0 +77,0 +78,0 +79,0 +80,0 +81,0 +82,0 +83,0 +84,0 +85,0 +86,0 +87,0 +88,0 +89,0 +90,0 +91,0 +92,0 +93,0 +94,0 +95,0 diff --git a/buch/papers/reedsolomon/images/syndrom.txt b/buch/papers/reedsolomon/images/syndrom.txt new file mode 100644 index 0000000..8ca9eed --- /dev/null +++ b/buch/papers/reedsolomon/images/syndrom.txt @@ -0,0 +1,96 @@ +0,0 +1,0 +2,0 +3,0 +4,0 +5,0 +6,0 +7,0 +8,0 +9,0 +10,0 +11,0 +12,0 +13,0 +14,0 +15,0 +16,0 +17,0 +18,0 +19,0 +20,0 +21,0 +22,0 +23,0 +24,0 +25,0 +26,0 +27,0 +28,0 +29,0 +30,0 +31,0 +32,0 +33,0 +34,0 +35,0 +36,0 +37,0 +38,0 +39,0 +40,0 +41,0 +42,0 +43,0 +44,0 +45,0 +46,0 +47,0 +48,0 +49,0 +50,0 +51,0 +52,0 +53,0 +54,0 +55,0 +56,0 +57,0 +58,0 +59,0 +60,0 +61,0 +62,0 +63,0 +64,0.0275599094902563 +65,0.0115837187254191 +66,0.025877761014238 +67,0.0224618032819697 +68,0.04410594689944 +69,0.0474504002669341 +70,0.0227694695500626 +71,0.0271436638090525 +72,0.0104166666666667 +73,0.0271436638090523 +74,0.0227694695500608 +75,0.0474504002669343 +76,0.0441059468994397 +77,0.0224618032819701 +78,0.0258777610142379 +79,0.0115837187254183 +80,0.027559909490256 +81,0.0245124379481793 +82,0.0499782237195209 +83,0.0401432022864265 +84,0.0232923747656228 +85,0.0237974288564099 +86,0.0143895905726624 +87,0.0271745729691685 +88,0.0275599094902567 +89,0.0515501672184983 +90,0.0358255004834542 +91,0.024700508366373 +92,0.0210194725405171 +93,0.0177592928994296 +94,0.0261327016093158 +95,0.0314909067039411 diff --git a/buch/papers/reedsolomon/main.tex b/buch/papers/reedsolomon/main.tex index 6bd04f2..e68b947 100644 --- a/buch/papers/reedsolomon/main.tex +++ b/buch/papers/reedsolomon/main.tex @@ -30,7 +30,7 @@ Bilden Sie auch für Formeln kurze Zeilen, einerseits der besseren % Joshua \input{papers/reedsolomon/einleitung.tex} \input{papers/reedsolomon/idee.tex} -\input{papers/reedsolomon/teil2.tex} +%\input{papers/reedsolomon/teil2.tex} \input{papers/reedsolomon/dtf.tex} % Michael @@ -45,6 +45,12 @@ Bilden Sie auch für Formeln kurze Zeilen, einerseits der besseren \nocite{reedsolomon:weitz} \nocite{reedsolomon:informationkommunikation} +\nocite{reedsolomon:voyager_programm} +\nocite{reedsolomon:voyager} +\nocite{reedsolomon:cd_wiki} +\nocite{reedsolomon:cd} +\nocite{reedsolomon:qr_wiki} +\nocite{reedsolomon:qr} %\nocite{reedsolomon:mendezmueller} \printbibliography[heading=subbibliography] diff --git a/buch/papers/reedsolomon/packages.tex b/buch/papers/reedsolomon/packages.tex index 3643731..b84e228 100644 --- a/buch/papers/reedsolomon/packages.tex +++ b/buch/papers/reedsolomon/packages.tex @@ -8,3 +8,5 @@ % following example %\usepackage{packagename} +\usepackage{pgfplots} +\usepackage{filecontents} diff --git a/buch/papers/reedsolomon/references.bib b/buch/papers/reedsolomon/references.bib index 731bd35..e0a75a8 100644 --- a/buch/papers/reedsolomon/references.bib +++ b/buch/papers/reedsolomon/references.bib @@ -23,3 +23,56 @@ volume = {1} } +@online{reedsolomon:voyager_programm, + title = {Information über das Voyager Programm}, + url = {https://de.wikipedia.org/wiki/Voyager-Programm}, + date = {2021-07-19}, + year = {2021}, + month = {7}, + day = {19} +} + +@online{reedsolomon:voyager, + title = {Bild der Voyager Raumsonde}, + url = {https://en.wikipedia.org/wiki/Voyager_1}, + date = {2021-07-19}, + year = {2021}, + month = {7}, + day = {19} +} + +@online{reedsolomon:cd_wiki, + title = {Alles über die CD}, + url = {https://de.wikipedia.org/wiki/Compact_Disc}, + date = {2021-07-19}, + year = {2021}, + month = {7}, + day = {19} +} + +@online{reedsolomon:cd, + title = {Funktionsweise des QR-Codes}, + url = {https://www.stickpng.com/img/electronics/compact-discs/stack-compact-disc}, + date = {2021-07-19}, + year = {2021}, + month = {7}, + day = {19} +} + +@online{reedsolomon:qr_wiki, + title = {Funktionsweise des QR-Codes}, + url = {https://de.wikipedia.org/wiki/QR-Code}, + date = {2021-07-19}, + year = {2021}, + month = {7}, + day = {19} +} + +@online{reedsolomon:qr, + title = {Tool zum erstellen von QR-Codes}, + url = {https://www.qrcode-generator.ch}, + date = {2021-07-19}, + year = {2021}, + month = {7}, + day = {19} +}
\ No newline at end of file diff --git a/buch/papers/reedsolomon/teil2.tex b/buch/papers/reedsolomon/teil2.tex deleted file mode 100644 index b2adc9f..0000000 --- a/buch/papers/reedsolomon/teil2.tex +++ /dev/null @@ -1,40 +0,0 @@ -% -% teil2.tex -- Beispiel-File für teil2 -% -% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil -% -\section{Teil 2 -\label{reedsolomon:section:teil2}} -\rhead{Teil 2} -Sed ut perspiciatis unde omnis iste natus error sit voluptatem -accusantium doloremque laudantium, totam rem aperiam, eaque ipsa -quae ab illo inventore veritatis et quasi architecto beatae vitae -dicta sunt explicabo. Nemo enim ipsam voluptatem quia voluptas sit -aspernatur aut odit aut fugit, sed quia consequuntur magni dolores -eos qui ratione voluptatem sequi nesciunt. Neque porro quisquam -est, qui dolorem ipsum quia dolor sit amet, consectetur, adipisci -velit, sed quia non numquam eius modi tempora incidunt ut labore -et dolore magnam aliquam quaerat voluptatem. Ut enim ad minima -veniam, quis nostrum exercitationem ullam corporis suscipit laboriosam, -nisi ut aliquid ex ea commodi consequatur? Quis autem vel eum iure -reprehenderit qui in ea voluptate velit esse quam nihil molestiae -consequatur, vel illum qui dolorem eum fugiat quo voluptas nulla -pariatur? - -\subsection{De finibus bonorum et malorum -\label{reedsolomon:subsection:bonorum}} -At vero eos et accusamus et iusto odio dignissimos ducimus qui -blanditiis praesentium voluptatum deleniti atque corrupti quos -dolores et quas molestias excepturi sint occaecati cupiditate non -provident, similique sunt in culpa qui officia deserunt mollitia -animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis -est et expedita distinctio. Nam libero tempore, cum soluta nobis -est eligendi optio cumque nihil impedit quo minus id quod maxime -placeat facere possimus, omnis voluptas assumenda est, omnis dolor -repellendus. Temporibus autem quibusdam et aut officiis debitis aut -rerum necessitatibus saepe eveniet ut et voluptates repudiandae -sint et molestiae non recusandae. Itaque earum rerum hic tenetur a -sapiente delectus, ut aut reiciendis voluptatibus maiores alias -consequatur aut perferendis doloribus asperiores repellat. - - |
