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
117
118
119
120
121
122
123
124
125
|
%
% dtf.tex -- Idee mit DFT
%
\section{Übertragung mit Hilfe der Diskrten Fourier-Transformation
\label{reedsolomon:section:dtf}}
\rhead{Umwandlung mit DTF}
Die Grundidee eines fehlerkorrigierenden Code ist, dass Informationen eines Datenpunkt,
durch die Codierung, auf viele übertragene Werte verteilt werden.
Die Decodierung ist in der Lage, den ursprünglichen Datenwert zu rekonstruieren,
sogar wenn einzelne wenige übertragene Werte beschädigt worden sind.
\par
Die Fourier-Transformation transformiert einen einzelnen Wert,
eine Dirac-Funktion, auf ein Spektrum, welches sich über die ganze Frequenzachse erstreckt.
Aus der Filtertheorie ist bekannt, dass der ursprüngliche Impuls mehr oder weniger rekonstruierbar ist.
Forausgestzt, es gehen nicht zu viele Frequenzen bei der Übertragung verloren.
\par
Es liegt daher nahe zu versuchen, die Fourier-Transformation
für Codierung und Decodierung zu verwenden.
\subsection{Beispiel mit Fehlerkorrektur mit Fourier-Transformation
\label{reedsolomon:subsection:sendbsp}}
Das folgende Beispiel soll zeigen, wie Fehlerkorrektur möglich ist.
Dieses auf eine Art, die der Funktionsweise des Reed-Solomon-Codes,
der später erklärt wird, analog ist.
\par
Der Auftrag ist nun 64 Daten zu übertragen, 32 Fehler erkennen und 16 Fehler rekonstruieren.
Mit hilfe der Fourier-Transformation werden die \textcolor{blue}{blauen Datenpunkte} transformiert,
zu den \textcolor{darkgreen}{grünen Übertragungspunkten}.
Durch eine Rücktransformation könnnen die \textcolor{blue}{blauen Datenpunkte} wieder rekonstruiert werden.
\begin{figure}
\centering
\resizebox{\textwidth}{!}{
\includegraphics[width=\textwidth]{papers/reedsolomon/figures/plotfft}
%\input{papers/reedsolomon/tikz/plotfftraw.tex}
}
\caption{Übertragungsabfolge \ref{reedsolomon:subsection:sendbsp}}
\label{fig:sendorder}
\end{figure}
In der Abbildung \ref{fig:sendorder} wird eine Übertragung Schritt für Schritt illustriert.
In der folgenden Aufzählung werden diese einzelne Schritte erklärt und erläutert:
\begin{enumerate}[(1)]
\item Das Signal ist mit 64 zufälligrn, ganzzahligen Datenwerten, zwischen 0 und 10.
Für die Rekonstruktion werden zusäzlich Datenwert benötigt, wir fügen deshalb 32 Werte hinzu.
Diese setzen wir willkürlich auf Null und nennen sie Fehlerkorrekturstellen
\externaldocument{papers/reedsolomon/idee}\ref{reedsolomon:section:Fehlerkorrekturstellen}.
Wir erhalten so einen erweiterten Signalvektor der länge $N =96$.
\item Mit der Fourier-Transformation wird der ganze Signalvektor codiert.
Dadurch wird jede Informationseinheit auf alle Punkte des Spektrums verteilt.
\item Wir dürfen annehmen, dass bei der Übertragung, nur einzelne übertragene Werte durch Fehler,
verändert werden.
\par
Im Beispiel sind dies die Werte an den Stellen 7, 21 und 75(\textcolor{red}{rote Kurve}),
die um einen Betrag verändert werden.
Dieser ist bis zu 150-mal kleiner, als die ursprünglichen codierte Werte.
Der Empfänger kennt daher im allgemeinen nicht, ob und wo Übertragungsfehler aufgetreten sind.
\item Ohne Übertragungsfehler kann der Signalvektor durch Inverse Fourier-Transformation vollständig
wiederhergestellt werden.
Dazu gehören auch die Nullen an den Fehlerkorrekturstellen 64 - 96.
\par
Sind Übertragungsfehler aufgetreten, werden an diesen Stellen, Werte abweichend von Null, auftreten.
Somit haben wir bereits Fehler erkannt.
\item Die Werte an den Fehlerkorrekturstellen 64 - 96, die nicht mehr Null sind, nennenwir das Syndrom.
Im Syndrom steckt nur Information über die Fehler, sie werden durch die Inverse Fourier-Transformation erzeugt.
\item Um die Fehler zu rekonstruieren, ann man versuchen, die Information im Syndrom mit Fourier-Transformation zu transformieren.
Da das Syndrom nur ein Teil der Fehlerinformation ist, liefert die Fourier-Transformation eine Approximation der Fehler.
Diese Approximation der Fehler ist genau genug, um die Fehlerstellen zu localisieren.
\end{enumerate}
Im Beispiel haben wir mit dem Syndrom nur etwa ein Drittel der Fehlerinformation, es ist daher zu erwarten,
dass die Fehlerwerte auch nur ein drittel so gross sind.
\par
Damit können die Fehler korrigiert und die Orginaldaten wiederhergestellt werden.
Der Rekonstruktionsauftrag ist damit erfolgreich ausgeführt.
\subsection{Fourier-Transformation und Polynome\label{reedsolomon:subsection:ftandpolynom}}
Im Abschnitt \externaldocument{papers/reedsolomon/idee}\ref{reedsolomon:section:polynomansatz}
wurden Werte eines Polynoms zur Codierung verwendet.
Die 7 Übertragungspunkte könnten ein Polynom
\begin{equation}
\textcolor{darkgreen}{p(x)}
=
\textcolor{blue}{a_0} + \textcolor{blue}{a_1}x + \textcolor{blue}{a_2}x^2 +
\textcolor{gray}{a_3}x^3 + \textcolor{gray}{a_4}x^4 + \textcolor{gray}{a_5}x^5 +
\textcolor{gray}{a_6}x^6
\label{reedsolomon:equationpoly}
\end{equation}
sechsten Grades bestimmen.
Durch die Wahl von $\textcolor{gray}{a_3=0}$, $\textcolor{gray}{a_4=0}$, $\textcolor{gray}{a_5=0}$, $\textcolor{gray}{a_6=0}$
erzeugen wir die, für die Fehlerkorrektur,
nötige Redundanz, ganz analog zum Schritt (1) im Beispiel.
\par
Die Analogie geht aber noch weiter.
Schreibt man
\( w =
e^{-\frac{2\pi j}{N} k}\)
\label{reedsolomon:DFT_summand}, damit wird aus der Formel
\begin{equation}
\hat{c}_{k}
= \frac{1}{N} \sum_{n=0}^{N-1}
{f}_n \cdot e^{-\frac{2\pi j}{N} \cdot kn}
,\label{reedsolomon:DFT}
\end{equation}
für die Diskrte-Fourier-Transformation das Polynom
\begin{equation}
q(w)=
\frac{{f}_0}{N} + \frac{{f}_1}{N} w^1 + \frac{{f}_2}{N} w^2 + \dots + \frac{{f}_{N-1}}{N} w^{N-1}
\label{reedsolomon:DFT_polynom}
\end{equation}
Im Beispiel werden aber Werte des des Polynoms $q(w)$ für verschieden
\( w = e^{-\frac{2\pi j}{N} k}, k=1, \dots , k=N-1\) übermittelt.
\begin{equation}
\textcolor{darkgreen}{q(w)}=
\frac{\textcolor{blue}{{f}_0}}{N} + \frac{\textcolor{blue}{{f}_1}}{N} w^1 + \frac{\textcolor{blue}{{f}_2}}{N} w^2 + \dots +
\frac{\textcolor{blue}{{f}_{63}}}{N} w^{63} + \frac{\textcolor{gray}{{f}_{64}}}{N} w^{64} + \textcolor{gray}{\dots} + \frac{\textcolor{gray}{{f}_{N-1}}}{N} w^{N-1}
\label{reedsolomon:DFT_polynom2}
\end{equation}
Das syndrom entstand durch die Wahl ${f_{64}}=0$ bis ${f}_{N-1}=0$.(graue koeffizenten)
\par
Die Polynominterpolation und die Fourier-Transformation rechnen beide mit reelen Zahlen.
Wenn die Approximation nicht mehr genügend gut ist um die Fehler zu erkennen und rekonstruieren,
dann müssen wir von den Reelen-Zahlen weg und zum endlichen Körpern, oder auch Galios-Körper genannt.
Deshalb haben die Mathematiker einen neuen Körper gesucht und ihn in der Endlichkeit gefunden,
dies wird nun im nächsten Abschnitt genauer erklärt.
|
