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
126
127
128
129
130
131
132
133
|
%
% dtf.tex -- Idee mit DFT
%
\section{Übertragung mit Hilfe der diskreten Fourier-Transformation
\label{reedsolomon:section:dtf}}
\rhead{Fehlerkorrektur mit diskreter Fourier-Transformation}
Die Grundidee eines fehlerkorrigierenden Code ist, dass Informationen eines Datenpunktes
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,
\index{Fourier-Transformation}%
eine Dirac-Funktion, auf ein Spektrum, welches sich über die ganze Frequenzachse erstreckt.
\index{Dirac-Funktion}%
\index{Spektrum}%
Aus der Filtertheorie ist bekannt, dass der ursprüngliche Impuls mehr oder weniger rekonstruierbar ist,
vorausgesetzt, es gehen nicht zu viele Frequenzen bei der Übertragung verloren.
\index{Filtertheorie}%
Es liegt daher nahe zu versuchen, die Fourier-Transformation
für Codierung und Decodierung zu verwenden.
\subsection{Beispiel: Fehlerkorrektur mit Fourier-Transformation
\label{reedsolomon:subsection:sendbsp}}
Das folgende Beispiel soll zeigen, wie die Idee der Fehlerkorrektur umgesetzt wurde.
Die Fehlererkennung des Reed-Solomon-Codes funktioniert nach einem sehr Ähnlichen Prinzip.
\index{Reed-Solomon-Code}%
%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 besteht darin, 64 Datenwerte zu übertragen, 32 Fehler erkennen können und bis zu 16 Fehler zu 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önnen die \textcolor{blue}{blauen Datenpunkte} wieder rekonstruiert werden.
\begin{figure}%[!ht]
\centering
\resizebox{\textwidth}{!}{
\includegraphics[width=\textwidth]{papers/reedsolomon/figures/fourier}
%\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 besteht aus 64 zufälligen, ganzzahligen Datenwerten zwischen 0 und 10.
Für die Rekonstruktion werden zusätzliche Datenwerte benötigt, wir fügen deshalb 32 Werte hinzu.
Diese setzen wir willkürlich alle auf Null und nennen sie {\em Fehlerkorrekturstellen}.
\index{Fehlerkorrekturstellen}%
Wir erhalten so einen erweiterten Signalvektor der Länge $N =96$.
\index{Signalvektor}%
\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 6, 20 und 74 (\textcolor{red}{rote Kurve}),
die um einen Betrag verändert werden.
Dieser ist bis zu 150-mal kleiner als die ursprünglich codierten Werte.
Der Empfänger erkennt daher im allgemeinen nicht, ob und wo Übertragungsfehler aufgetreten sind.
\item Ohne Übertragungsfehler kann der Signalvektor durch die 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 die Werte von Null abweichen.
Somit haben wir bereits Fehler erkannt.
\item Die Werte an den Fehlerkorrekturstellen 64--96, die nicht mehr Null sind, nennen wir das {\em Syndrom}.
\index{Syndrom}%
Im Syndrom steckt nur Information über die Fehler, sie werden durch die inverse Fourier-Transformation erzeugt.
\item Um die Fehler zu rekonstruieren, kann 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 lokalisieren.
\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.
Damit können die Fehler korrigiert und die Originaldaten 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 diskrete-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 Polynoms
\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}
für verschiedene \( w = e^{-\frac{2\pi j}{N} k}, k=1, \dots ,N-1\) übermittelt.
Das Syndrom entstand durch die Wahl ${f_{64}}=0$ bis ${f}_{N-1}=0$ (graue Koeffizenten).
Die Polynominterpolation und die Fourier-Transformation rechnen beide mit reellen Zahlen.
Wenn die Approximation nicht mehr genügend gut ist, um die Fehler zu erkennen und zu rekonstruieren,
dann brauchen wir andere Varianten.
Um dieser Approximation zu entkommen, verlassen wir die reellen Zahlen und gehen zu endlichen Körpern, auch Galois-Körper genannt.
\index{endlicher Körper}%
\index{Galois-Körper}%
\index{Körper, endlich}%
Diese bieten uns einige Vorteile.
|
