Grundlagen der Informatik
Kapitel 5: Algebraische Codierung

5.1 Lineare Codes

Wir betrachten ein Alphabet S (z.B. S={0,1}) mit |S| = q. Dabei ergibt sich q als Potenz einer Primzahl p: q = p ^ k.. Dabei gibt es genau einen endlichen Körper, der q Elemente enthält. Es sei von jetzt an S der Körper F(q). F(q)(n) seinen genau die Wörter aus F(q), die die Länge n haben, also ein n-dimensianler Vektorraum über F(q). Für F(q)(n) wird im Skript die Abkürzung V(n) verwendet, ich werde dies hier übernehmen.

Nach der Hamming-Metrik ist d(x,y) der Abstand der beiden Codewörter x und y aus V(n). Wir sprechen von einem linearen Code, wenn C eine Teilmenge (ein Untervektorraum) von V(n) ist. C sei ein [n,k] Code, wobei k die Anzahl der Informationsstellen und n - k die Anzahl der Prüfstellen ist. Zusammen mit dem Mindestabstand d heißt C ein [n,k,d] - Code.

Wir brauchen nun eine Möglichkeit, Generatoren für diesen Code zu finden, also ein Erzeugendensystem. Um Vektoren in einem Vektorraum zu erzeugen, bedienen wir uns der Basisvektoren. Um 2^(n-k) Vektoren zu erzeugen, benötigen wir n-k Basisvektoren. Um geeignete Basisvektoren zu finden, schreibet man die Vektoren untereinander jeden in eine Zeile und lässt den Gauß-Algorithmus anlaufen, solange, bis noch k Vektoren übrig bleiben, die dann linear unabhängig sind und die in beliebiger Linearkombination alle Codevektoren erzeugen, jedoch nicht mehr.

Wir haben so Basisvektoren v1 - v(n-k) erzeugt. Diese schreiben wir nacheinander in eine Matrix G, an die wir hinten noch eine Einheitsmatrix anhängen. Mit n-k Basisvektoren (Prüfvektoren) und k Einheitsvektoren haben wir eine Matrix in Standartform gewonnen.

Wir multiplizieren den Codevektor c(i) mit der Matrix G und erhalten so ein Codewort c*, das wir sicher durch den Kanal übermitteln können: c x G = c*. Nicht vergessen: Hier gilt das Kommutativgesetz nicht.

Zum decodieren bedienen wir uns einer Prüfmatrix, den wir aus der Genaratormatrix gewinnen können. Wir nehmen einfach die Matrix G ohne die angehängte Einheitsmatrix und transponieren G zu Gt. Dieser transponierten Matrix stellen wir nun wieder die Einheitsmatrix voran und gewinnen so die Prüfmatrix H. Um ein empfangenes Wort auf Übertrgungsfehler hin zu prüfen, berechnen wir das Syndrom aus s = H * c*. Dieses Syndrom gibt Aufschluss, ob und wenn ja, wo ein Fehler bei der Übertragung aufgetretten ist. Ist das Syndrom 0, so entstand kein Fehler, das Übertragene Wort war ein Codewort. Oder es entstanden so viele Fehler, das aus einem Codewort ein anderes wurde.

Fehlerkorrektur

Um nun Fehler korrigieren zu können, empiehlt sich folgendes Vorgehen: Berechnen zunächst eine Tabelle, in der wir jedem Wort, das theoretisch empfangen werden könnte, ein Syndrom zuordnen. Wörter mit gleichem Syndrom werden jeweils in einer Zeile zusammengefasst. Jede Zeile (jedes Syndrom) markiert eine Nebenklasse. Nun wählen wir aus jeder Nebenklasse einen Nebenklassenführer so, dass der Abstand des Nebenklassenführers vom Nullvektor minimal ist. Der Nebenklassen führer ist der Korrekturvektor KV für dieses Syndrom H(c*). Um den zugehörigen Codevektor zu erhalten, decodieren wir c = c* + KV[H(c*)].

Beispiel: C = { 0000, 1010, 1101, 0111 }, H =

Hammingcodes

Hammingcodes sind Codes mit einer speziellen Prüfmatrix H. In einem Vektorraum V(m) ist m die Dimension und n = 2^m - 1 die Anzahl der darin enthaltenen Vektoren ohne den Nullvektor. Mit k = n - m beschreibt man einen [n, k]-Hamming-Code. Wir konstruieren die Prüfmatrix H mit m Einheitsvektoren und fügen dahinter alle verbleibenden Vektoren aus V(m) an. Die Generator-Matrix erzeugen wir aus der Prüfmatrix: H = (I(m), A) -> G = (At, I(k))

Beispiel: Sei m = 3, so ist ein [7,4]-Hamming-Code definiert durch:

Jeder Hammingcode ist ein perfekter Einzelfehlerkorrekturcode.

Decodierung von Hamming-Codes

Ordne die Spalten von H bei der Konstruktion so an, dass die i-te Spalte die Zahl i darstellt. Dann ist das errechnete Syndrom eines Codewortes zugleich die Fehlerposition in der Nachricht.

5.2 Zyklische Codes

Betrachten wir lineare Codes, so können wir darin auch solche finden, die sich durch Verschiebung von Bitpsitionen nach links oder rechts darstellen lassen. Solche Codes heißen zyklisch. {110, 011, 101, 000 } wäre ein solcher zyklischer Code.

Es lässt sich zeigen, das zyklische Codes gleichzusetzen sind mit Polynomringen. Wir können dann mit den Codewörtern rechnen wie im Restklassenring von Polynomen. Dabei stellt jedes Codewort einen Rest dar. Das Null-Polynom wird zusätzlich mit aufgenommen. Der Code {110, 011, 101, 000 } ist dann gleichbedeutend mit den Polynomen { 1+x, x+x², 1+x², 0 }.

Allgemein: Für einen (n+1)-dimensionalen Vektorraum von Codewörtern suchen wir uns einen Polynomring n-ten Grades. Dazu müssen die Codewörter zyklisch sein. Das Polynom niedrigsten Grades ist unser Generatorpolynom g(x). Im obigen Beispiel 1+x.

Nachweis: Um zu prüfen, ob ein Code zyklisch ist, muss man zeigen, dass g(x) ein Teiler von X^n - 1 ist.

Ein Prüfpolynom h(x) erhalten wir, indem wir X^n - 1 durch das Generatorpolynom Teilen:

Codierung: Um ein Codewort c zu Codieren, multiplizieren wir c(x) * g(x) = y(x). Um daraus ein Syndrom zu ermitteln multiplizieren wir s(x)=h(x)*y(x) mod g(x). Wir berechnen das Syndrom also im Restklassenring modulo g(x). Ist s(x) das Nullpolynom, so war y(x) ein Codewort, ansonsten trat bei der übertragung ein Fehler auf.

Polynome als Matrizen

Wir betrachten einen Code mit k Informationsstellen und n - k Prüfstellen. Dann sei ein Generatorpolynom. Es lässt sich nachweisen, das die Multipolikation von Polynomen durch eine Matrizenmultiplikation dargestellt werden kann. Wie man Polynome multipliziert, kann hier icht näher erläutert werden und sollte eigentlich auch bekannt sein. Eine Generatormatrix G, die dem Polynom g(X) entspricht, sieht so aus:

Durch Matrizenmultiplikation c(x) * G erhalten wir wie gewohnt unser zur Übertragung bereites Codewort y(x). Die Matrix hat genau so viele Spalten, wie c Stellen hat, nämlich k.

Analog erhalten wir eine Prüfmatrix H aus dem Prüfpolynom h(x) in umgekehrter Anordnung der Koeffizienten mit n - k Zeilen. Wir beginnen links oben mit hk und enden rechts unten mit h0.