1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
|
%
% teil3.tex -- Beispiel-File für Teil 3
%
% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
%
\section{Decodierung: Ansatz ohne Fehler
\label{reedsolomon:section:decohnefehler}}
\rhead{fehlerlose rekonstruktion}
In diesem Abschnitt betrachten wie die Überlegung, wie wir auf der Empfängerseite die Nachricht aus dem empfangenen Übertragungsvektor erhalten. Nach einer einfachen Überlegung müssen wir den Übertragungsvektor decodieren, was auf den ersten Blick nicht allzu kompliziert sein sollte, solange wir davon ausgehen können, dass es während der Übertragung keine Fehler gegeben hat. Wir betrachten deshalb den Übertragungskanal als fehlerfrei.
Der Übertragungsvektor empfangen wir also als
\[
v = [5,3,6,5,2,10,2,7,10,4].
\]
% Old Text
%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].
%\]
Nach einem banalen Ansatz ist die Decodierung die Inverse der Codierung. Dank der Matrixschreibweise lässt sich dies relativ einfach umsetzen.
% Old Text
%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 jetzt die Frage, wie wir die Inverse von $A$ berechnen.
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.
\]
Damit beschäftigen wir uns im Abschnitt \ref{reedsolomon:subsection:algdec} weiter, konkret suchen wir momentan aber eine Inverse für unsere primitive Einheitswurzel $a$.
\[
8^1 \qquad \rightarrow \qquad 8^{-1}
\]
Mit einem solchen Problem haben wir uns bereits in Abschnitt \ref{buch:section:euklid} befasst und so den euklidischen Algorithmus kennengelernt, den wir auf unseren Fall anwenden können.
% Old Text
%Im Abschnitt \textcolor{red}{4.1} haben wir den euklidischen Algorithmus kennengelernt, den wir auf unseren Fall anwenden können.
\subsection{Inverse der primitiven Einheitswurzel
\label{reedsolomon:subsection:invEinh}}
Die Funktionsweise des euklidischen Algorithmus ist im Kapitel \ref{buch:section:euklid} ausführlich beschrieben.
Für unsere Anwendung wählen wir die Parameter $a = 8$ und $b = 11$ ($\mathbb{F}_{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. Die inverse Transformationsmatrix $A^{-1}$ bilden wir indem wir jetzt die inverse primitive Einheitswurzel anstelle der primitiven Einheitswurzel in die Matrix einsetzen.
\subsection{Allgemeine Decodierung
\label{reedsolomon:subsection:algdec}}
Wir haben jetzt fast alles für eine erfolgreiche Rücktransformation beisammen. Wir haben aber noch nicht alle Aspekte der inversen diskreten Fouriertransformation befolgt, so fehlt uns noch 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 diskreten 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$ in $\mathbb{F}_{11}$ ergibt. Somit lässt sich der 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.
|
