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
|
%
% teil3.tex -- Beispiel-File für Teil 3
%
% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
%
\section{Decodierung ohne Fehler
\label{reedsolomon:section:decohnefehler}}
\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 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.
|
