Endliche Körper und Codierungs­theorie: Hamming und Reed-Solomon

Beim Übertragen und Speichern kippen manchmal einzelne Bits: durch Rauschen im Funk, durch einen Kratzer auf einer CD, durch einen Fehler im Arbeitsspeicher. Ein fehlerkorrigierender Code fügt der Nachricht gezielt Redundanz hinzu, sodass der Empfänger Fehler nicht nur bemerkt, sondern behebt. Die Mathematik dahinter sind lineare Algebra und endliche Körper, also Körper mit nur endlich vielen Elementen.

Auf dieser Seite lernst du, wie man mit endlichen Körpern rechnet, wie man sie konstruiert und wie daraus Codes entstehen. Die Grundlagen stehen in Ringe und Körper und in der modularen Arithmetik. Die tiefere Struktur erklärt die Galois-Theorie.

Primkörper

Der Restklassenring ${\mathbb{Z}}_n$ ist ein Körper genau dann, wenn $n$ eine Primzahl ist. Beweis. Ist $n=ab$ mit $1<a,b<n$, dann ist $a·b=0$ in ${\mathbb{Z}}_n$, und ein Körper hat keine Nullteiler. Ist $p$ prim und $a\not\equiv 0$, dann ist $\mathrm{ggT}(a,p)=1$, und der erweiterte euklidische Algorithmus liefert $s,t$ mit $sa+tp=1$, also $s·a\equiv 1(\mathrm{mod}p)$: Das Inverse existiert. $\square$ Für ${𝔽}_7$ ist zum Beispiel $3^{-1}=5$, denn $15=2·7+1$.

In einem endlichen Körper $K$ ist $1+1+\dots +1$ irgendwann $0$. Die kleinste Anzahl $p$ von Einsen, die $0$ ergibt, heißt die Charakteristik, und sie ist eine Primzahl: Ein Produkt $p=ab$ würde Nullteiler erzeugen. Damit enthält $K$ den Körper ${𝔽}_p$ und ist ein Vektorraum über ${𝔽}_p$. Hat dieser Vektorraum die Dimension $n$, dann hat $K$ genau $p^n$ Elemente.

Körper mit $p^n$ Elementen

Die Rechenregeln in ${\mathbb{Z}}_4$ passen nicht zu einem Körper ($2·2=0$). Einen Körper mit $4$ Elementen erhältst du anders: Nimm ${𝔽}_2=\{0,1\}$ und das Polynom $f(x)=x^2+x+1$. Es hat keine Nullstelle in ${𝔽}_2$ ($f(0)=1$, $f(1)=1$) und ist deshalb irreduzibel. Rechne mit Polynomen modulo $f$: Sei $\alpha$ die „Nullstelle“ von $f$, also ${\alpha }^2=\alpha +1$. Der Körper ${𝔽}_4=\{0,1,\alpha ,\alpha +1\}$ hat die Rechenregel $1+1=0$ und die folgende Multiplikationstabelle.

Es ist $\alpha ·\alpha =\alpha +1=\beta$ und $\alpha ·\beta ={\alpha }^2+\alpha =(\alpha +1)+\alpha =1$. Jedes Element außer $0$ hat ein Inverses, und $\alpha$ erzeugt die multiplikative Gruppe: $\alpha ,{\alpha }^2=\beta ,{\alpha }^3=1$.

Existenz und Eindeutigkeit beweist man mit Zerfällungskörpern: ${𝔽}_q$ ist der Zerfällungskörper von $x^q-x$ über ${𝔽}_p$ und besteht genau aus den Nullstellen dieses Polynoms. Weil ${𝔽}_q^{\ast }$ eine endliche Untergruppe der Einheiten eines Körpers ist, ist sie zyklisch. Ein erzeugendes Element heißt primitives Element. In ${𝔽}_7^{\ast }$ ist $3$ primitiv: $3^1,\dots ,3^6=3,2,6,4,5,1$. Wichtig ist auch die Frobenius-Abbildung $x\mapsto x^p$. Weil $p$ alle Binomialkoeffizienten $\left(\genfrac{}{}{0ex}{}{p}{k}\right)$ mit $0<k<p$ teilt, gilt ${(a+b)}^p=a^p+b^p$ in Charakteristik $p$. Sie ist ein Automorphismus von ${𝔽}_q$ und erzeugt dessen Galoisgruppe über ${𝔽}_p$, die zyklisch von der Ordnung $n$ ist.

Ein Körper mit $8$ Elementen entsteht mit $f(x)=x^3+x+1$ über ${𝔽}_2$, denn ein Polynom vom Grad $3$ ist genau dann irreduzibel, wenn es keine Nullstelle hat, und $f(0)=f(1)=1$. Die Elemente sind die Polynome $a+bx+c{x}^2$ mit $a,b,c\in \{0,1\}$, und man rechnet mit $x^3=x+1$.

Fehlerkorrigierende Codes

Ein Code ist eine Menge $C$ von Wörtern der Länge $n$ über einem Alphabet, meist ${𝔽}_2$ oder ${𝔽}_q$. Der Sender verschickt nur Codewörter. Die Hamming-Distanz $d(x,y)$ ist die Zahl der Positionen, an denen sich $x$ und $y$ unterscheiden, und die Mindestdistanz $d$ des Codes ist die kleinste Distanz zweier verschiedener Codewörter.

Beweis. Wird ein Codewort an höchstens $d-1$ Stellen verändert, entsteht kein anderes Codewort. Der Fehler fällt also auf. Die Kugeln mit Radius $t$ um verschiedene Codewörter sind disjunkt, denn läge ein Wort $z$ in zwei Kugeln um $c\ne c^{\prime }$, dann wäre $d(c,c^{\prime })\le d(c,z)+d(z,c^{\prime })\le 2t<d$ nach der Dreiecksungleichung der Hamming-Distanz. Ein Wort in einer Kugel hat deshalb ein eindeutiges nächstes Codewort. $\square$

Das einfachste Beispiel ist der Wiederholungscode: Jedes Bit wird dreimal gesendet, $0\mapsto 000$ und $1\mapsto 111$. Die Mindestdistanz ist $3$, ein Fehler wird per Mehrheit korrigiert. Der Preis: Für ein Datenbit werden drei Bits übertragen, die Rate ist nur $\frac{1}{3}$. Gesucht sind Codes mit großer Distanz und hoher Rate.

Lineare Codes

Ein linearer Code der Länge $n$ und Dimension $k$ ist ein $k$-dimensionaler Unterraum $C$ von ${𝔽}_q^n$. Er hat $q^k$ Codewörter, man nennt ihn einen $[n,k,d]$-Code. Man beschreibt ihn durch eine Prüfmatrix $H$ mit $n-k$ Zeilen: $c\in C$ genau dann, wenn $H{c}^{\top }=0$. Für ein empfangenes Wort $y$ ist $s=H{y}^{\top }$ das Syndrom. Es ist $0$ genau dann, wenn $y$ ein Codewort ist. Die Mindestdistanz eines linearen Codes ist das kleinste Gewicht (Zahl der von $0$ verschiedenen Stellen) eines Codeworts $\ne 0$, und sie ist die kleinste Zahl von Spalten von $H$, die linear abhängig sind.

Der Hamming-Code

Richard Hamming ordnete die Spalten der Prüfmatrix so an, dass die Spalte $j$ die Zahl $j$ im Dualsystem ist, für $j=1,\dots ,7$:

Die sieben Spalten sind alle von $0$ verschiedenen Vektoren aus ${𝔽}_2^3$. Je zwei Spalten sind verschieden, also unabhängig, aber drei sind abhängig, zum Beispiel $(\mathrm{0,0},1)+(\mathrm{0,1},0)=(\mathrm{0,1},1)$. Daher ist $d=3$, und der Code $[7,4,3]$ hat $2^4=16$ Codewörter. Er korrigiert jeden Einzelfehler: Das Syndrom ist die Binärzahl der Fehlerposition.

Der Hamming-Code ist perfekt: Die Kugeln mit Radius $1$ um die $16$ Codewörter enthalten je $1+7=8$ Wörter, und $16·8=128=2^7$ füllt den ganzen Raum aus. Jedes empfangene Wort ist daher entweder ein Codewort oder hat genau ein Codewort im Abstand $1$. Der Hamming-Code nutzt $4$ von $7$ Bits für Daten, die Rate ist $\frac{4}{7}$, deutlich besser als beim Wiederholungscode. Hängt man ein weiteres Paritätsbit an, erhält man den erweiterten Hamming-Code mit $d=4$: Er korrigiert einen und erkennt zwei Fehler, wie im Arbeitsspeicher von Servern.

Reed-Solomon-Codes

Die Idee: Ein Polynom vom Grad kleiner als $k$ ist durch $k$ Werte festgelegt. Man fasst $k$ Datensymbole aus ${𝔽}_q$ als Koeffizienten eines Polynoms $p$ auf und sendet seine Werte $p(a_1),\dots ,p(a_n)$ an $n\le q$ verschiedenen Stellen $a_i\in {𝔽}_q$. Zwei verschiedene Polynome vom Grad kleiner als $k$ haben höchstens $k-1$ gemeinsame Werte, denn ihre Differenz hat höchstens $k-1$ Nullstellen. Deshalb unterscheiden sich zwei Codewörter an mindestens $n-k+1$ Stellen, und die Mindestdistanz ist $d=n-k+1$. Das ist der größtmögliche Wert (Singleton-Schranke), die Codes sind „optimal“. Sie korrigieren $\lfloor \frac{n-k}{2}\rfloor$ Fehler. Weil sie Symbolfehler korrigieren und nicht einzelne Bits, bewältigen sie auch Bündelfehler wie einen Kratzer auf einer CD.

Irving Reed und Gustave Solomon beschrieben die Codes 1960 in der Arbeit „Polynomial Codes over Certain Finite Fields“. Sie stecken in CDs und DVDs, in DSL, im digitalen Fernsehen und in QR-Codes. Dasselbe Prinzip steht hinter dem Teilen von Geheimnissen: Ein Polynom vom Grad $k-1$ wird durch $k$ Punkte festgelegt, aber nicht durch weniger.

Endliche Körper in der Kryptographie

Das Potenzieren in ${𝔽}_p^{\ast }$ ist leicht, das Umkehren (der diskrete Logarithmus) im Allgemeinen schwer. Darauf beruht der Schlüsselaustausch nach Diffie und Hellman: Zwei Parteien einigen sich auf eine Primzahl $p$ und ein primitives Element $g$, wählen geheime Zahlen $a$ und $b$ und tauschen $g^a$ und $g^b$ aus. Beide berechnen $g^{ab}$. Weiteres steht auf der Seite Kryptologie.

Übungen

Geschichte: von Galois zur Compact Disc

Évariste Galois verwendete 1830 „imaginäre“ Lösungen von Kongruenzen modulo einer Primzahl und konstruierte damit die endlichen Körper ${𝔽}_{p^n}$ mit $p^n$ Elementen. Eliakim Hastings Moore bewies 1893, dass es zu jeder Primzahlpotenz bis auf Isomorphie genau einen endlichen Körper gibt, und führte den Namen „Galois field“ ein. Die Anwendung auf die Fehlerkorrektur begann nach dem Zweiten Weltkrieg. Claude Shannon zeigte 1948 in „A Mathematical Theory of Communication“, dass sich mit geeigneten Codes jede Übertragungsrate unterhalb der Kanalkapazität mit beliebig kleiner Fehlerwahrscheinlichkeit erreichen lässt. Sein Beweis war nicht konstruktiv, er sagte nicht, wie die Codes aussehen. Richard Hamming entwickelte sein Verfahren bei den Bell Labs, weil der Rechner Bell Model V Fehler beim Lesen von Lochkarten selbst beheben sollte, und veröffentlichte es 1950. Reed und Solomon folgten 1960. Heute stecken beide Ideen in Speicherchips, Satellitenverbindungen, CDs und QR-Codes.

Häufige Fragen

Quellen und weiterführende Literatur

• Wikipedia: Endlicher Körper
• Wikipedia: Hamming-Code
• Wikipedia (englisch): Reed–Solomon error correction
• Rudolf Lidl, Harald Niederreiter: Finite Fields, Cambridge University Press.
• Jürgen Bierbrauer: Introduction to Coding Theory, Chapman and Hall/CRC.