%\NeedsTeXFormat{LaTeX2e} \documentclass[12pt,a4paper]{article} \usepackage{german} % erlaubt sind Umlautdarst. wie "a"o"u \usepackage[ansinew]{inputenc} %direkte Eingabe der Umlaute in Windows %----------------------------------------------------------------------- %\def\N{{\rm I\mkern-3mu N}} %\def\R{{\rm I\mkern-3mu R}} %\def\Q{{\@QC Q}} %\def\C{{\@QC C}} %\def\Z{{\rm Z\mkern-9mu Z}} %\def\@QC#1{\mathpalette{\setbox0=\hbox\bgroup$\rm}% % {\egroup C$\egroup\rm\rlap{\kern0.4\wd0\vrule % width 0.05\wd0 height 0.97\ht0 depth -0.01\ht0}% % #1\bgroup}} %--------------------------------------------------------------------------- \begin{document} %\twocolumn \title{Wir konstruieren Zahlen: \\ Galois\discretionary{–}{}{–}Felder für Forth--Programmierer am Beispiel der RS\discretionary{–}{}{–}Kodierung}[Galois\discretionary{–}{}{–}Felder] \author{Jens Storjohann} \date{Mai 2006} %\begin{document} \maketitle \begin{multicols}{2} %\begin{abstract} % %\end{abstract} %\tableofcontents %-------------------------------------------------------------------------------- % Hier beginnt der Inhalt \section{Zählen und Nummerieren} Ein wesentlicher Unterschied zwischen den Zahlen, auf die wir beim Zählen stoßen, und denjenigen, die wir nur zum Nummerieren brauchen, wird nach kurzem Nachdenken klar. Beim Zählen kommen wir zunächst auf die natürlichen Zahlen $\{1,2,\cdots\}$, beim Umkehren der Addition, dem Subtrahieren, auf die Null und die negativen Zahlen, die zusammen die ganzen Zahlen $\{ \cdots,-2,-1,0,1,2,\cdots\}$ bilden. Die Addition und die Multiplikation entsprechen Operationen, die mit unterscheidbaren Gegenständen durchgeführt werden, wie Zusammenfassen oder Zusammenfassen mehrerer Mengen mit einheitlicher Anzahl von Gegenständen. Aber Nummern tragen keine nahe liegende Arithmetik in sich. Wenn die Addition zweier Hausnummern die Nummer eines anderen Hauses ergibt, ist dies eher Zufall und Willkür als Widerspiegelung eines Zusammenhanges. Bei einem Wechsel des Schemas, z. B. einer anderen Richtung der Nummerierung, würde man ein anderes Ergebnis erhalten. Bei Kodierungssystemen ordnet man die zu übertragenden Zeichen in eine Reihenfolge, wie z.B. beim Alphabet ein, und überträgt die Nummern. Damit haben die zu übertragenden Nummern keine in sich liegende Arithmetik, die z. B. Regeln für ihre Addition festlegt. Aber wenn die Übertragung gestört ist, muss man sich Schemata überlegen, die durch Erzeugung von Zusatzinformationen eine sichere Datenübertragung gewährleisten. Dies würde man am liebsten durch arithmetische Operationen mit den zu übertragenden Nummern bewirken. Aber in der Computertechnik sind die natürlichen Zahlen $\{1, 2, 3, ... \}$ und die mit ihnen verbundene Arithmetik nur unvollkommen zu behandeln. Denn nur ein Teil dieser Elemente aus dieser unendlichen Zahlenmenge kann auf einem reservierten Speicherplatz gegebener Größe gespeichert werden. Damit haben schon die einfachsten Operationen Addition und Multiplikation immer die Gefahr in sich, einen Speicherplatzüberlauf zu erzeugen. Außerdem zwingt uns alleine die Umkehrung der Addition, die Subtraktion, die Zahlenreihe beidseitig unendlich, d.h. auch mit negativen Zahlen anzusetzen. Damit treten bei der Multiplikation Fallunterscheidungen wie {\em MINUS*PLUS = MINUS} auf. Am unerfreulichsten aber ist, dass die Division manchmal ein ganzzahliges Ergebnis hat, {\em manchmal nicht aufgeht}, d. h. einen Rest lässt. Weil, wie wir oben festgestellt haben, das Rechnen mit Nummern ohnehin keine in sich liegende Bedeutung hat, sind wir frei, uns eine Arithmetik zu wählen, ausschließlich unter dem Gesichtspunkt, dass sie für unsere Bedürfnisse möglichst zweckmäßig ist. All dies kann nur die Konsequenz haben, dass wir uns Zahlen verschaffen, die diese Nachteile einer für unsere besonderen Zwecke ungeeigneten Arithmetik nicht haben. {\em Also konstruieren wir neue Zahlen mit einer praktischen Arithmetik.} \section{Die Restklassen--Arithmetik} Die folgende sehr einfache Konstruktion liefert schon Zahlen mit einer geeigneten Arithmetik. Bevor wir sie beschreiben, lohnt der Hinweis, dass im Programmierer--Jargon zwar von {\em Hex--Zahlen} oder {\em Binär--Zahlen} gesprochen wird, dies aber die bekannten natürlichen oder ganzen Zahlen sind, die nur abweichend von der uns seit der Kinderzeit bekannten Dezimal--Schreibweise dargestellt sind. Im Folgenden dagegen werden andere {\em neue Zahlen} beschrieben, für die wir aber zum Teil die alten uns bekannten Ziffernsymbole verwenden. Wir beginnen mit den natürlichen Zahlen. Wenn wir uns eine Zahl wie z.~B. die 3 fest vorgeben und vereinbaren, dass alle Zahlen, die bezüglich der 3 den gleichen Rest lassen, als gleich anzusehen sind, haben wir nur 3 Zahlen zu unterscheiden: 0, 1, 2. Denn z. B. die 4 ist mit der 1 gleichzusetzen und braucht deshalb nicht als eigenes Zeichen dargestellt zu werden. Als Multiplikationsregel und Additionsregel vereinbaren wir, dass die Operationen wie gewohnt durchzuführen sind, aber vom Ergebnis nur der Rest bezüglich der 3 zu betrachten ist. Die Klasse von Zahlen, die den gleichen Rest bei Division durch eine gegebene Zahl lassen, nennt man in der Algebra Restklasse. Wir können die Zahlen 0, 1, 2 als Restklassenvertreter ansehen, und die folgende Tabelle \ref{mod3} für Addition und Multiplikation als Beschreibung der Arithmetik mit Restklassen. \begin{table} \caption{Addition und Multiplikation modulo 3} \begin{tabular}{c||c|c|c|c c|| c| c| c|} + & 0 & 1 & 2 & ~~~~~~~~~~~~~~~& $\cdot$ & 0 & 1 & 2 \\ \hline \hline 0 & 0 & 1 & 2 & & 0 & 0 & 0 & 0 \\ 1 & 1 & 2 & 0 & & 1 & 0 & 1 & 2 \\ 2 & 2 & 0 & 1 & & 2 & 0 & 2 & 1 \\ \hline \end{tabular} \label{mod3} \end{table} Wir erkennen auch, dass jede Division außer der durch 0 möglich ist. Dies sieht man daran, dass in jeder Zeile und jeder Spalte der Multiplikationstabelle, wenn man die Multiplikation mit der Null außer Acht lässt, jede Zahl genau einmal vorkommt. Unser nächster {\em Versuch} arbeitet mit den Restklassen, die bei Division durch 4 entstehen. \begin{table} \caption{Addition und Multiplikation modulo 4} \begin{tabular}{c||c|c|c|c|c c|| c| c|c| c|} + & 0 & 1 & 2 & 3 & ~~~~~~~~~~~~~~~& $\cdot$ & 0 & 1 & 2 & 3 \\ \hline \hline 0 & 0 & 1 & 2 & 3 & & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 2 & 3 & 0 & & 1 & 0 & 1 & 2 & 3 \\ 2 & 2 & 3 & 0 & 1 & & 2 & 0 & 2 & 0 & 2 \\ 3 & 3 & 0 & 1 & 2 & & 3 & 0 & 3 & 2 & 1 \\ \hline \end{tabular} \label{mod4} \end{table} Hier haben wir {\em eine Arithmetik, die nicht zweckmäßig ist,} erhalten. Denn wenn ein Produkt aus zwei Zahlen, die beide von 0 verschieden sind, 0 ergibt, wie oben 2*2=0, heißt das, dass beispielsweise durch 2 nicht sinnvoll zu dividieren ist. Man erkennt, dass bei einer Restklassen--Arithmetik nach einer {\em Primzahl} dieses Problem nicht auftritt. Damit wissen wir, dass wir eine ganze Klasse von neuen Zahlen erfunden haben, die endliche Körper oder Galois--Felder genannt werden und mit den Symbolen $GF(p)$, $F(p)$ oder $F_p$ bezeichnet werden. Hierbei steht $p$ für eine beliebige Primzahl. Wir stellen die Eigenschaften dieser Zahlen kurz zusammen. Es gilt \begin{description} \item[Kommutativgesetz der Addition] $a+b=b+a$ \item[Kommutativgesetz der Multiplikation] $ a\cdot b=b\cdot a $ \item[Assoziativgesetz der Addition] $(a+b)+c=a+(b+c) $ \item[Assoziativgesetz der Multiplikation] ~\\ $a\cdot(b\cdot c)=(a\cdot b)\cdot c $ \item[Distributivgesetz] $a\cdot(b+c)=a \cdot b+a\cdot c $ \item[Existenz der Null] $a+0=a$ \item[Existenz der Eins] $1\cdot a=a$ \item[Existenz eines Negativen zu jedem Element] $ -a \mbox{~mit~} a+(-a)=0$ \item[Existenz eines Inversen zu jedem Element] (außer der Null) $ aa^{-1}=1$ \end{description} Alle diese allgemeinen Gesetze kennen wir aus der Bruchrechnung schon seit der Schulzeit. Wir haben sogar darüber hinausgehend ziemlich komplizierte Algorithmen für Operationen mit Brüchen gelernt, mit denen beispielsweise zwei Brüche addiert werden und als gekürzter Bruch dargestellt werden können. Bei der Restklassenarithmetik geht jede Division auf, deshalb benötigt man keine Brüche. Dies gilt auch für die später eingeführten endlichen Körper mit $p^n$ Elementen $F(p^n)$. Wir brauchen also hier keine solch komplizierten Algorithmen zu betrachten und können Rechenergebnisse entweder in einer Tabelle nachsehen oder sie berechnen, indem wir das ursprüngliche einfache Bildungsgesetz heranziehen. Auch beim Implementieren dieser Rechnung auf einem Computer haben wir diese beiden Möglichkeiten. Beides ist einfacher als das, was wir in der Schule mit 12 Jahren gelernt haben. Ich habe mir die Aufgabe gestellt, {\em ohne Tabellen und ohne Probierverfahren} die elementare Arithmetik der Galois--Felder $F(p)$ und einer weiter unten erklärten Erweiterung dieser Zahlenbereiche zu programmieren, natürlich in Forth. An den Programmtexten für die Arithmetik von $F(p)$ erkennt man, dass Addition, Multiplikation und Subtraktion begrifflich und von der Programmierung her einfach durchzuführen sind. Nur die Division ist aufwändig. Die Idee hinter der Division ist ähnlich dem Verfahren, das man für Dezimalzahlen in der Schule lernt. Wir nutzen aus, dass die Multiplikation in $F(p)$ durchgeführt werden kann, indem die bekannte Multiplikation der ganzen Zahlen ergänzt wird durch eine Restbildung modulo p. Damit können wir auch die Division durchführen, indem wir die bekannte Division ganzer Zahlen verwenden und dem Dividenden oder seinem abgearbeiteten Rest genügend oft ein $p$ dazu addieren. Ein Beispiel erläutert das. Wir bilden 2/5 in der Restklassenarithmetik modulo 7. Im Folgenden steht der Doppelpunkt für die gewöhnliche Division ganzer Zahlen. $$2:5=0 \mbox{~~Rest~} 2.$$ Also bilden wir $$(2+7):5=9:5=1 \mbox{~~Rest~} 4.$$ $$(4+7):5=11:5=2 \mbox{~~Rest~}1.$$ $$(1+7):5=8:5=1\mbox{~~Rest~}3.$$ $$(3+7):5=10:5=2\mbox{~~Rest~}0.$$ Also haben wir als Quotienten $$ 2/5 = 0+1+2+1+2= 6 \mbox{~modulo~}7.$$ Probe ergibt $$6 \cdot 5=30 =2 \mbox{~~modulo~} 7.$$ \section{Erweiterung der Restklassenarithmetik --- die endlichen Körper $F(p^n)$} Wir haben nun auf eine sehr einfache Weise für jede Primzahl $p$ endliche Körper mit $p$ Elementen konstruiert. Aber der Versuch, auf die gleiche Weise, nämlich durch {\em Rechnen modulo 4}, beispielsweise einen Körper $F(4)$ zu erzeugen, ist gescheitert. Es ist aber mit einer Verallgemeinerung des gleichen Gedankens möglich. Wir betrachten Polynome, d. h. formale Ausdrücke der Form $$P(x)=c_0+c_1x^1+c_2x^2+ \cdots +c_{n-1}x^{n-1}$$. Wenn wir für die Koeffizienten Werte aus dem endlichen Körper $F(p)$ wählen, haben wir für jeden der $n$ Koeffizienten $p$ Möglichkeiten. Also gibt es $p^n$ solcher Polynome. Die Größe x hat hier die Bedeutung eines Platzhalters. Wir bezeichnen den höchsten auftretenden Exponenten von x als {\em Grad} eines Polynoms. Es fehlt nur noch eine geeignete Arithmetik für solche Polynome. Die Addition liegt nahe: \begin{eqnarray*} P(x) & = & c_0+c_1x^1+c_2x^2+ \cdots +c_{n-1}x^{n-1}. \\ Q(x) & = & d_0+d_1x^1+d_2x^2+ \cdots +d_{n-1}x^{n-1}. \\ P(x)+Q(x) & = & (c_0+d_0)+(c_1+d_1)x^1+(c_2+d_2)x^2 \\ & & +\cdots+(c_{n-1}+d_{n-1})x^{n-1}. \end{eqnarray*} Aber es führt aber die übliche Multiplikation von zwei Polynomen mit dem Grad $k$, so wie man es in der Schule lernt, immer zu einem Polynom mit Grad $2k$. Ein Beispiel illustriert das: \begin{eqnarray*} P(x)Q(x) & = & (c_0+c_1x^1)(d_0+d_1x^1) \\ & = & c_0d_0 + (c_0d_1+c_1d_0)x+c_1d_1x^2. \end{eqnarray*} Damit haben wir wieder das Problem, dass bei naiv durchgeführter Arithmetik der Speicher überläuft, weil bei der Multiplikation Polynome beliebigen Grades entstehen können. Man kann vermuten, dass die Lösung dieses Problems auch wieder durch eine Restbildung, aber nicht modulo einer Zahl, sondern einem Polynom erfolgen kann. Es kann gezeigt werden, dass dies genau dann zu einem Körper führt, wenn das Polynom, das man zur Restbildung heranzieht, analog zu einer Primzahl, nicht zerlegbar in ein Produkt von anderen Polynomen ist. Die gebräuchliche Bezeichnung für diese Eigenschaft eines Polynoms lautet {\em irreduzibel}\/. \subsection{Die Konstruktion von $F(2^2)$ als Beispiel} Wir betrachten alle Polynome mit Koeffizienten aus $F(2)$. Das Polynom $P(x)=1+1x+1x^2$ ziehen wir heran, um modulo diesem Polynom Reste zu bilden. Wir können zeigen, dass dieses Polynom irreduzibel, also für unsere Aufgabe geeignet ist, weil es nicht als Produkt von Polynomen mit Koeffizienten in $F(2)$ zerlegbar ist. Denn es könnte nur ein Produkt zweier linearer Polynome von der Art $(x+a)(x+b)$ sein. Jede Annahme von Werten für $a$ und $b$, wobei nur $0$ und $1$ möglich sind, führt zu einem anderen Produkt als dem oben gegebenen Polynom. Ein Beispiel zeigt wie die Multiplikation zweier Polynome $P_1$ und $P_2$ durchzuführen ist: $$P_1(x)=1+1x$$ $$P_2(x)= x $$ $$P_1(x)\cdot P_2(x)= (1+1x)\cdot (1x)= 1x + 1x^2$$ Nun ist \begin{eqnarray*} (1x + 1x^2 ):P(x) & = & (1x + 1x^2 ):(1+1x+1x^2)\\ & = & 1 \mbox{~Rest~}1x+1x^2-(1+1x+1x^2) \end{eqnarray*} Für den Rest erhalten wir $$1x+1x^2-(1+1x+1x^2)=-1=1$$ Damit erhalten wir als Multiplikationsergebnis in $F(2^2)$ $$(1+1x)\cdot (x)=1 \mbox{ modulo }(1+1x+1x^2).$$ Dabei haben wir benutzt, dass in F(2) jede Zahl gleich ihrer negativen ist, was symbolisch durch $+=-$ beschrieben wird. Mit einigen ähnlichen Rechnungen gewinnen wir eine Additions- und Multiplikationstabelle für $F(2^2)$. Darin folgen wir einer Konvention und benutzen das Symbol $a$ statt $x$. \begin{table} \caption{Addition und Multiplikation für $F(2^2)$} \begin{tabular}{c||c|c|c|c|c} + & 0+0a & 1+0a & 0+1a & 1+1a \\ \hline \hline 0+0a & 0+0a & 1+0a & 0+1a & 1+1a \\ 1+0a & 1+0a & 0+0a & 1+1a & 0+1a \\ 0+1a & 0+1a & 1+1a & 0+0a & 1+0a \\ 1+1a & 1+1a & 0+1a & 1+0a & 0+0a \\ \hline \end{tabular}\\ \begin{tabular}{c||c|c|c| c|} $\cdot$ & 0+0a & 1+0a & 0+1a & 1+1a \\ \hline \hline 0+0a & 0+0a & 0+0a & 0+0a & 0+0a \\ 1+0a & 0+0a & 1+0a & 0+1a & 1+1a \\ 0+1a & 0+0a & 0+1a & 1+1a & 1+0a \\ 1+1a & 0+0a & 1+1a & 1+0a & 0+1a \\ \hline \end{tabular} \end{table} Diese Tabelle lässt sich unmittelbar einleuchtend in eine Arithmetik mit Nummern übersetzen \begin{table} \caption{Addition und Multiplikation für $F(2^2)$ durchnummeriert} \begin{tabular}{c||c|c|c|c|c c|| c| c|c| c|} + & 0 & 1 & 2 & 3 & ~~~~~~~~~~& $\cdot$ & 0 & 1 & 2 & 3 \\ \hline \hline 0 & 0 & 1 & 2 & 3 & & 0 & 0 & 0 &0 & 0 \\ 1 & 1 & 0 & 3 & 2 & & 1 & 0 & 1 & 2 & 3 \\ 2 & 2 & 3 & 0 & 1 & & 2 & 0 & 2 & 3 & 1 \\ 3 & 3 & 2 & 1 & 0 & & 3 & 0 & 3 & 1 & 2 \\ \hline \end{tabular} \end{table} \subsection{Didaktische Bemerkung} Mathematiker sind vertraut mit einem abstrakten Begriff von Zahlen, so dass die Einführung neuer Zahlen für sie Routine ist. Für Anwender, die sich daran gewöhnt haben, dass sie nie über die in ihrem Taschenrechner implementierte Begriffswelt hinausgehen müssen, bedarf es einer geistigen Lockerung, solche Gebilde als Zahlen anzuerkennen. Das eigentliche Problem liegt darin, dass wir uns ungern damit abfinden, dass es Zahlen gibt, von denen wir noch nie etwas gehört haben, obwohl wir in der Schule gut aufgepasst haben und den Alltag meistern. Wir müssen also eher {\em entlernen} als lernen. Beim durchschnittlich trinkfesten erwachsenen Mann konnte ich empirisch nachweisen, dass die Einnahme von ca. zwei Gläsern Wein das Vertrautwerden mit diesen Zahlen sig\-ni\-fi\-kant erleichtert. Der Wechsel in der Symbolik von $x$ zu $a$ hilft psychologisch dabei, weil $x$ gewohnheitsmäßig mit unbekannten Größen assoziiert wird. \subsection{Grundkörper und Erweiterungskörper} Die beschriebenen Gebilde werden als Galois--Felder (Galois fields) oder endliche Körper bezeichnet. Die $F(p)$ werden auch als Grundkörper der Erweiterungskörper $F(p^n)$ bezeichnet. Man kann beweisen, dass alle endlichen Körper wie hier beschrieben konstruiert werden können. Auch kann man zeigen, dass es im abstrakten Sinne genau einen endlichen Körper für ein Parameterpaar $(p,n)$ gibt. \section{Implementierung in Forth} \subsection{Eigener Stapel für die Zahlen aus $F(p^n)$} Für die eigentlich interessierenden Daten, nämlich Zahlen aus $F(p^n)$, wird, außer bei sehr kleinem n, ein eigener Datenstapel, ähnlich wie für Gleitkommazahlen üblich, eingerichtet. In Hilfsrechnungen treten Zahlen aus $F(p)$ auf. Diese lassen sich sinnvoll auf dem Parameterstapel bearbeiten. Auch für $n=2$ kann man mit etwas Stapelmanipulationen und Benutzung des Rücksprungstapels die Arithmetik ohne eigenen Stapel durchführen. Damit sind die abgedruckten Programme im Prinzip wiedereintrittsfest, weil sie auf keine eigenen Variablen schreibend zugreifen. % \subsection{Experimentiersystem} % Wenn man mit verschiedenen Arithmetiken experimentieren will ist es vernünftig, die Beschreibung der jeweils eingestellten % Arithmetik auf einen {\em Stapel arithmetischer Umgebungen} zu schieben. Dadurch kann ein vorangegangener Zustand wieder % hergestellt werden. %\subsection{Welche Befehle benötigen wir?} %Neben den arithmetischen Operationen benötigen wir die in Tabelle~ \ref{fpnworte} beschriebenen. %\begin{table}[ht] %\caption{Worte für $F(p^n)$} % \begin{tabular}{|l||l|l|l|} % \hline % Befehl & P-Stapel & $F(p^n)$-Stapel & Beschreibung \\ % \hline % \hline % $F(p^n)$! & adr -- & (f1...fn) -- & abspeichern \\ % \hline % $F(p^n)$@ & adr -- & -- (f1...fn) & aus dem Speicher auf den $F(p^n)$-Stapel\\ % \hline % $F(p^n)$variable & & & definiert eine Variable v-name \\ % v-name & & & (kompilierend) \\ % \hline % v-name & -- adr & & legt die Adresse von v-name auf den \\ % & & & Parameterstapel \\ % \hline % $F(p^n)$constant & & (f1...fn) -- & definiert eine Konstante k-name\\ % k-name & & & (kompilierend)\\ % \hline % k-name & & -- (f1...fn) & legt den Wert einer Konstanten auf den \\ % & & & $F(p^n)$-Stapel\\ % \hline % $F(p^n)>$ & f1,...,fn -- & (f1...fn) -- & vom $F(p^n)$-Stapel auf den Parameter-Stapel \\ % \hline % $>F(p^n)$ & -- f1,...,fn & -- (f1...fn) & vom Parameterstapel auf den $F(p^n)$-Stapel \\ %\hline % \end{tabular} % \label{fpnworte} %\end{table} % \subsection{Wahl der Parameter $p$ und $n$ für $F(p^n)$ und Initialisierung} % Für die Arithmetik in $F(p)$ müssen wir nur eine Variable mit dem Wert $p$ initialisieren. Für die Arithmetik in $F(p^n)$ % müssen zusätzlich der Exponent $n$ und die Koeffizienten des gewählten Polynoms, das zur Restbildung genutzt wird, angegeben % und abgespeichert werden. In der Stapelverwaltung ist zu beachten, dass eine Zahl aus $F(p^n)$ durch die Inhalte von $n$ % Zellen dargestellt wird. Damit ist beim Arbeiten mit wechselnden Körpern durch den Benutzer ein Löschen des $F(p^n)$--Stapels % durch z. B. ein {\bf forget} notwendig \section{Festlegen der Arithmetik} Wir haben zwei freie Parameter, die es uns erlauben, einen endlichen Körper auszuwählen. Wenn man seine Wahl von $p$ und $n$ trifft, muss ein in $F(p)$ irreduzibles Polynom vom Grade n (aus Tabellen) bekannt sein. Es ist aber auch möglich, geratene Polynome auf Irreduzibilität zu prüfen oder alle geeigneten systematisch aufzustellen und zu prüfen. \section{Anwendung auf Kodierung} Mit den vorangegangenen Erklärungen ist das Prinzip der fehlerkorrigierenden Kodierung mit Hilfe endlicher Körper leicht zu schildern: Aus den zu übertragenden Zahlen $m_i$ werden unabhängige einzelne Blöcke $m_0,m_1,\cdots,m_k$ herausgegriffen und als Koeffizienten einer Folge von Polynomen $M_l(x)$ vom Grade $k$ aufgefasst. Die Werte dieser Polynome für vereinbarte Argumente $x_k$ werden als Prüf\/informationen mit übertragen. Weil die Arithmetik dieser Zahlenbereiche im abstrakten Sinne wie Bruchrechnung oder Rechnen mit reellen Zahlen abläuft, können bekannte mathematische Formeln herangezogen werden, um beispielsweise fehlerhaft über\-tragene Daten zu rekonstruieren. Ein Beispiel zeigt das: Wir verwenden Blöcke aus zwei Zahlen $m_0,m_1$. Das Polynom $M(x)=m_0+m_1x$ werten wir für $x_1$ und $x_2$ aus und erhalten $M_1$ und $M_2$. Daraus rekonstruieren wir $m_0$ und $m_1$ durch Interpolation nach Lagrange. $$M(x)=M_1 \frac{x-x_2}{x_1-x_2} + M_2 \frac{x-x_1}{x_2-x_1}$$ $$ m_o=M_1 \frac{(-x_2)}{x_1-x_2} + M_2 \frac{(-x_1)}{x_2-x_1} $$ $$ m_1=M_1 \frac{1}{x_1-x_2} + M_2 \frac{1}{x_2-x_1} $$ Man kann nachvollziehen, dass mit dieser Kodierung, die genau so viel Bandbreite beansprucht wie eine doppelte Übertragung der ursprünglichen Nachricht, alle einzelnen Fehler in einem Block korrigiert und zwei Fehler entdeckt werden können. Eine doppelte Übertragung kann nur einzelne Fehler entdecken, aber nicht korrigieren. Zwei Fehler in einem Block können unentdeckt bleiben. Für praktische Anwendungen verwendet man Dekodierungs--Algorithmen, die effektiver, aber auch schwieriger zu verstehen sind. Die grundlegende Idee wurde im Jahre 1960 von Reed und Solomon veröffentlicht, blieb aber lange Jahre mangels geeigneter Hardware und schneller Algorithmen zum Dekodieren eine akademische Lösung, von der man glaubte, dass sie nie eingesetzt werden würde. Heute ist Reed--Solomon--Kodierung ein Standard--Verfahren, z. B. für CDs. Für das effektive Rechnen mit Zahlen aus Galois--Feldern verwendet man auf Tabellen basierende schnelle Algorithmen, wie z. B. auf dem Zech--Loga\-rith\-mus beruhende, die hier nicht behandelt werden sollen. \section{Imaginäre Einheit und galoisionäre Einheit} Für Anwender in Technik und Naturwissenschaften werden die komplexen Zahlen oft so eingeführt: \begin{itemize} \item es gibt eine imaginäre Einheit $i$, die der Gleichung $i^2=-1$ gehorcht. \item wer damit nicht rechnen kann, fällt durch die Prüfung. \end{itemize} Ähnlich hätte ich auch für den Fall $F(2^2)$ schreiben können: \begin{itemize} \item $2x=0$ oder $x=-x$ für alle $x$ \item es gibt eine galoisionäre Einheit $a$, die der Gleichung $a^2=-a-1=a+1$ oder $a^2+a+1=0$ gehorcht. \item wer damit nicht rechnen kann, muss für seine Programmieraufgaben Lösungen mit geschobenen oder sonst wie manipulierten Bits erdenken. \end{itemize} \section{Forth als universelle Algebra} Der Verfasser hat vor etwa 25 Jahren Vorlesungen über Algebra bei Prof. Ernst Witt gehört. Er gehörte zu den bedeutendsten Algebraikern des zwanzigsten Jahrhunderts und war auch einer der ersten Mathematiker, der Computer zu Forschungszwecken in der höheren Algebra einsetzte. Er machte damals die Bemerkung, dass Forth eine universelle Algebra sei. Das heißt, dass Forth insbesondere durch seine Konvention der Nutzung des Stapels für die Übergabe der Eingangsgrößen und der Ergebnisse geeignet ist, beliebige mathematische Operationen mit beliebigen Zahlen von Argumenten und Ergebnissen auf eine einheitliche Weise durchzuführen. Bei einem Zusammenspiel einer Computersprache mit einem {\em realen Computer} sind natürlich Einschränkungen solch allgemeiner Aussagen, insbesondere durch den endlichen Speicherplatz, zu bemerken. Aber bei Forth ist dies im Wesentlichen nur der insgesamt für den Stapel reservierte Platz. Die vorliegenden Programme demonstrieren diese Eignung von Forth, Algebren mit geringem Aufwand zu realisieren, nur mit für Algebraiker sehr durchsichtigen Gebilden. \section{Biografische Notiz} Der Mathematiker Evariste Galois lebte als Zeitgenosse Napoleons von 1811 bis 1832. Er starb in jungen Jahren an den Folgen eines Duells. Die hier beschriebenen endlichen Körper sind vom ihm entdeckt. Die Theorie über die Bedingungen für die Auflösbarkeit algebraischer Gleichungen durch Wurzelausdrücke, an deren Anfang er steht, gehört zu den beeindruckendsten Leistungen der Mathematik. \section{Quellen und Literaturempfehlungen} Eine für angehende Mathematiker geeignete Einführung findet sich in den bekannten Büchern von van der Waerden\cite{vdW1971}, die in vielen Auflagen und Übersetzungen erschienen sind, oder im Netz \cite{Wiki}. Die Originalarbeit \cite{ReedSolomon1960} über die Kodierung mit Hilfe endlicher Körper ist nun schon fast ein halbes Jahrhundert alt. Aber trotzdem lässt sich bis heute ein Strom von darauf aufbauenden Arbeiten, die sich mit der Implementierung und vielen weiteren praktisch relevanten Problemen befassen, beobachten. Als Beispiel sei eine Diplomarbeit \cite{Garz1995} genannt, für deren Zusendung ich mich bei Herrn Garz bedanke. Forth und Reed--Solomon sind schon mehrfach in Verbindung gekommen. Der Artikel in der VD von Rafael Deliano \cite{Deliano2005} war für mich der Anstoß, einen Artikel zu entwerfen, in dem möglichst allgemein verständlich Galois--Felder erklärt werden. Ich danke Herrn Behringer für den Hinweis auf G. Dixons Artikel \cite{Dixon1999a} und \cite{Dixon1999b}, der mir bei der Abfassung der vorliegenden Notiz entgangen war. \begin{thebibliography}{999} \bibitem{vdW1971} B.L. van der Waerden, Algebra I, Achte Auflage der Modernen Algebra, Springer, 1971 \bibitem{Wiki} Wikipedia deutsch unter dem Stichwort {\em Endlicher Körper} \bibitem{ReedSolomon1960} Reed, I. und G. Solomon, Polynomial codes over certain finite fields, Journal of the Society for Industrial and Applied Mathematics [SIAM J.], 8 (1960), 300--304. \bibitem{Dixon1999a} Dixon, G., Reed--Solomon--Fehlerkorrektur, {\em Vierte Dimension} Das Forth Magazin, Ausgabe 4/1999, 13--16 (Übersetzt von Fred Behringer, das Original ist in Forth Dimensions Band XX, Nr. 4 erschienen) \bibitem{Dixon1999b} Dixon, G., Reed--Solomon--Fehlerkorrektur Teil 2, {\em Vierte Dimension} Das Forth Magazin, Ausgabe 4/1999, 34--36 (Übersetzt von Fred Behringer, das Original ist in Forth Dimensions Band XX, Nr. 5,6 erschienen) \bibitem{Deliano2005} Deliano, R., Arithmetik im Galoisfeld, Forth Magazin {\em Vierte Dimension}, Nr. 3/4/ (2005), 24--26 \bibitem{Garz1995} Bernhard Garz, Decodierungsalgorithmen für Reed--Solomon--Codes, 1995 Diplomarbeit Universität Karlsruhe --- Fakultät für Informatik \end{thebibliography} \end{multicols} \begin{quote} \begin{small} \listinginput[1]{1}{2006-03/galois2.f} \end{small} \end{quote} \end{document}