aboutsummaryrefslogtreecommitdiffstats
path: root/buch/papers/reedsolomon
diff options
context:
space:
mode:
Diffstat (limited to 'buch/papers/reedsolomon')
-rw-r--r--buch/papers/reedsolomon/decohnefehler.tex128
1 files changed, 97 insertions, 31 deletions
diff --git a/buch/papers/reedsolomon/decohnefehler.tex b/buch/papers/reedsolomon/decohnefehler.tex
index 832d63f..90f8ba8 100644
--- a/buch/papers/reedsolomon/decohnefehler.tex
+++ b/buch/papers/reedsolomon/decohnefehler.tex
@@ -5,36 +5,102 @@
%
\section{Decodierung ohne Fehler
\label{reedsolomon:section:decohnefehler}}
-\rhead{Teil 3}
-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:malorum}}
-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.
+\rhead{fehlerlose rekonstruktion}
+Im ersten Teil zur Decodierung des Übertragungsvektor betrachten wir den Übertragungskanal als fehlerfrei.
+Wir erhalten also unseren Übertragungsvektor
+\[
+v = [5,3,6,5,2,10,2,7,10,4].
+\]
+Gesucht ist nun einen Weg, mit dem wir auf unseren Nachrichtenvektor zurückrechnen können.
+Ein banaler Ansatz ist das Invertieren der Glechung
+\[
+v = A \cdot m \qquad \Rightarrow \qquad m = A^{-1} \cdot v.
+\]
+Nur stellt sich dann die Frage, wie wir auf die Inverse der Matix $A$ kommen.
+Dazu können wir wiederum den Ansatz der Fouriertransformation uns zur Hilfe nehmen,
+jedoch betrachten wir jetzt deren Inverse.
+Definiert ist sie als
+\[
+F(\omega) = \int_{-\infty}^{\infty} f(t) \mathrm{e}^{-j\omega t} dt \qquad \Rightarrow \qquad \mathfrak{F}^{-1}(F(\omega)) = f(t) = \frac{1}{2 \pi} \int_{-\infty}^{\infty} F(\omega) \mathrm{e}^{j \omega t} d\omega.
+\]
+
+In unserem Fall suchen wir also eine inverse für die Primitive Einheitswurzel $a$, also
+\[
+8^1 \qquad \Rightarrow \qquad 8^{-1}.
+\]
+
+Im Abschnitt \textcolor{red}{4.1} haben wir den euklidischen Algorithmus kennengelernt, den wir auf unseren Fall anwenden können.
+
+\subsection{Der Euklidische Algorithmus
+\label{reedsolomon:subsection:eukAlgo}}
+
+Die Funktionsweise des euklidischen Algorithmus ist im Kapitel \textcolor{red}{4.1} ausführlich beschrieben.
+Für unsere Anwendung wählen wir die Parameter $a_i = 8$ und $b_i = 11$.
+Daraus erhalten wir
+
+\begin{center}
+
+\begin{tabular}{| c | c c | c | r r |}
+ \hline
+ $k$ & $a_i$ & $b_i$ & $q_i$ & $c_i$ & $d_i$\\
+ \hline
+ & & & & $1$& $0$\\
+ $0$& $8$& $11$& $0$& $0$& $1$\\
+ $1$& $11$& $8$& $1$& $1$& $0$\\
+ $2$& $8$& $3$& $2$& $-1$& $1$\\
+ $3$& $3$& $2$& $1$& $3$& $-2$\\
+ $4$& $2$& $1$& $2$& \textcolor{blue}{$-4$}& \textcolor{red}{$3$}\\
+ $5$& $1$& $0$& & $11$& $-8$\\
+ \hline
+\end{tabular}
+
+\end{center}
+\begin{center}
+
+\begin{tabular}{rcl}
+ $\textcolor{blue}{-4} \cdot 8 + \textcolor{red}{3} \cdot 11$ &$=$& $1$\\
+ $7 \cdot 8 + 3 \cdot 11$ &$=$& $1$\\
+ $8^{-1}$ &$=$& $7$
+
+\end{tabular}
+
+\end{center}
+
+als Inverse der Primitiven Einheitswurzel.
+
+Nun haben wir fast alles für die Rücktransformation beisammen. Wie auch bei der Inversen Fouriertransformation haben wir nun einen Vorfaktor
+\[
+m = \textcolor{red}{s} \cdot A^{-1} \cdot v
+\]
+den wir noch bestimmen müssen.
+Glücklicherweise lässt der sich analog wie bei der Inversen Fouriertransformation bestimmen und beträgt
+\[
+s = \frac{1}{10}.
+\]
+Da $\frac{1}{10} = 10^{-1}$ entspricht können wir $s$ ebenfalls mit dem euklidischen Algorithmus bestimmen und stellen fest, dass $10^{-1} = 10$ ergibt.
+Somit lässt sich den Nachrichtenvektor einfach bestimmen mit
+\[
+m = 10 \cdot A^{-1} \cdot v \qquad \Rightarrow \qquad m = 10 \cdot \begin{pmatrix}
+ 7^0& 7^0& 7^0& 7^0& 7^0& 7^0& 7^0& 7^0& 7^0& 7^0\\
+ 7^0& 7^1& 7^2& 7^3& 7^4& 7^5& 7^6& 7^7& 7^8& 7^9\\
+ 7^0& 7^2& 7^4& 7^6& 7^8& 7^{10}& 7^{12}& 7^{14}& 7^{16}& 7^{18}\\
+ 7^0& 7^3& 7^6& 7^9& 7^{12}& 7^{15}& 7^{18}& 7^{21}& 7^{24}& 7^{27}\\
+ 7^0& 7^4& 7^8& 7^{12}& 7^{16}& 7^{20}& 7^{24}& 7^{28}& 7^{32}& 7^{36}\\
+ 7^0& 7^5& 7^{10}& 7^{15}& 7^{20}& 7^{25}& 7^{30}& 7^{35}& 7^{40}& 7^{45}\\
+ 7^0& 7^6& 7^{12}& 7^{18}& 7^{24}& 7^{30}& 7^{36}& 7^{42}& 7^{48}& 7^{54}\\
+ 7^0& 7^7& 7^{14}& 7^{21}& 7^{28}& 7^{35}& 7^{42}& 7^{49}& 7^{56}& 7^{63}\\
+ 7^0& 7^8& 7^{16}& 7^{24}& 7^{32}& 7^{40}& 7^{48}& 7^{56}& 7^{64}& 7^{72}\\
+ 7^0& 7^9& 7^{18}& 7^{27}& 7^{36}& 7^{45}& 7^{54}& 7^{63}& 7^{72}& 7^{81}\\
+\end{pmatrix}
+\cdot
+\begin{pmatrix}
+ 5 \\ 3 \\ 6 \\ 5 \\ 2 \\ 10 \\ 2 \\ 7 \\ 10 \\ 4 \\
+\end{pmatrix}
+\]
+und wir erhalten
+\[
+m = [0,0,0,0,4,7,2,5,8,1]
+\]
+als unsere Nachricht zurück. \ No newline at end of file