Einordnung der zyklischen Codes
Die zyklischen Binärcodes sind eine Untergruppe der linearen Codes. Sie sind also ebenfalls Codes über dem Alphabet {0, 1}, die bei einer festen Wortlänge n eine festgelegte Anzahl an Worten, nämlich 2m für ein m <= n, haben. Insbesondere bilden sie eine kommutative Gruppe bezüglich der Addition modulo 2.
Einordnung der zyklischen Codes
Zyklisch heissen die zyklischen Codes nun, weil bei ihnen die zyklische Verschiebung eines Codewortes wieder ein gültiges Codewort ergibt. Bildlich sieht das so aus, dass alle Bits um eine Position nach rechts verschoben werden und das Bit, das an der letzten Position stand, vorne angefügt wird.
Die zyklischen Codes bieten die verschiedenen Möglichkeiten zur Fehlererkennung und -korrektur der linearen Codes, sind aber besonders einfach und effizient realisierbar. Sie finden Verwendung zum Beispiel bei der Datenfernübertragung via Modem und auf Hintergrunddatenspeichern wie Bändern oder CD's.
Die linearen Codes werden im Allgemeinen durch Vektoren dargestellt (siehe Vortrag 3), die durch Multiplikation mit einer Generatormatrix codiert werden. Um auf die besonderen Eigenschaften der zyklischen Codes eingehen zu können, wird jedoch üblicherweise folgende Darstellungsform verwendet:
Ein binäres Wort der Länge n wird dargestellt durch ein Polynom c(x) vom Grad n-1. Die einzelnen Bitpositionen des Wortes sind dabei die Koeffizienten des Polynoms, die Hilfsgrösse x dient zur Festlegung der Stellenposition.
c(x) = cn-1 · xn-1 + ... + c2 · x2 + c1 · x + c0
Die oben beschriebene zyklische Verschiebung eines Codewortes lässt sich nun durch die Multiplikation des zugehörigen Codewortpolynoms mit x modulo (xn - 1) darstellen (siehe [2]).
Anschaulich:
Das gegebene Codewortpolynom c(x) = cn-1 · xn-1 + ... + c2 · x2 + c1 · x + c0 wird mit x multipliziert und vom Ergebnis der Divisionsrest modulo (xn - 1) gebildet.
x · c(x) = cn-1 · xn + ... + c2 · x 3 + c1 · x2 + c0 · x
Die Division ergibt
(cn-1 · xn + ... + c2 · x 3 + c1 · x2 + c0 · x) / (xn - 1) = cn-1 Rest cn-2 · xn-1 + ... + c1 · x 2 + c0 · x + cn-1)
Dieser Rest entspricht der zyklischen Verschiebung von c(x).
Allgemein können die zyklischen Codes als Untermengen des Restklassenrings der Polynome über dem Galois Feld GF(2) modulo (xn - 1) betrachtet werden. Das GF(2) ist die Menge {0, 1} auf der die Addition modulo 2 definiert ist. Ein gegebenes Codewortpolynom wird dabei identifiziert mit dem kleinsten Vertreter seiner Restklasse. Diesen erhält man aus einem Codewortpolynom mit Grad >n durch Restbildung bei der Division durch (xn - 1). Für die weiteren praxisbezogenen Überlegungen werden aber lediglich Polynome vom Grad <n betrachtet werden. Es gibt also immer eine eindeutige Beziehung zwischen Polynom und Restklasse. Beide sollen hier als Darstellung des selben Dinges aufgefasst werden, nämlich eines Elements des Restklassenrings der Polynome über GF(2) modulo (xn - 1). Man kann weiter zeigen, dass eine Menge von Codewortpolynomen mit Grad <n genau dann einen zyklischen Code beschreibt, wenn sie ein Ideal im Restklassenring ist, d.h. wenn mit jedem Polynom aus der Menge auch jedes ganzzahlige Vielfache und jede Differenz in der Menge liegt. Die Mathematik liefert dazu nun folgende wichtigen Eigenschaften:
Betrachte ein normiertes Polynom g(x) kleinsten Grades so dass seine Restklasse in einem Ideal I liegt. Ein anderes Polynom c(x) mit Grad <n ist genau dann durch g(x) ohne Rest teilbar, wenn die Restklasse von c(x) auch im Ideal I liegt. Ein solches g(x) teilt auch (xn - 1) und jedes Polynom das Teiler von (xn - 1) ist, erzeugt ein anderes Ideal. Aus der Zerlegung von (xn - 1) in irreduzible normierte Polynome erhält man also alle Möglichen g(x), die ein Ideal aus Polynomen mit Grad <n erzeugen. Ein solches Polynom g(x) wird Generatorpolynom des zugegörigen zyklischen Codes genannt. Weitere Information sind in [4] zu finden.
Ein zyklischer Code lässt sich also durch Angabe der Codewortlänge n (= dem Grad n von (xn - 1)) und des Generatorpolynoms g(x) vollständig bestimmen. Ein Codewort c(x) entsteht nun einfach durch Multiplikation des Informationswortpolynoms a(x) mit g(x). Dabei muss noch berücksichtigt werden, dass der Grad von g(x) und der der verschiedenen Informations- und Codewortpolynome in folgender Beziehung zueinander stehen:
Generatorpolynom g(x): Grad n-m
Informationswortpolynom a(x): Grad m-1
Codewortpolynom c(x): Grad n-1
Es ist
c(x) = a(x) · g(x)
Auf diese Weise erzeugt das Generatorpolynom alle Worte des zugehörigen Codes.
Es soll ein zyklischer Code gebildet werden, der Informationsworte der Länge 4 mit 3 redundanten Bits codiert. Es ist n = 4 + 3 = 7, man sucht also ein Generatorpolynom, das irreduzibles Teilerpolynom von (x7 - 1) ist und Grad 3 hat. Die Zerlegung von (x7 - 1) ergibt:
(x7 - 1) = (x + 1) · (x3 + x + 1) · (x3 + x2 + 1)
Das Polynom (x3 + x + 1) erfüllt alle Voraussetzungen die an ein Generatorpolynom gestellt werden: es ist irreduzibler Teiler von (x7 - 1) und normiert. Man wählt also
g(x) = (x3 + x + 1)
Nun entstehen alle Codewörter dieses Codes durch Multiplikation von g(x) mit den 16 Informationsworten
a(x) = a3 · x 3 + a2 · x 2 + a1 · x + a0
Die Codeworte haben also die Form
c(x) = g(x) · a(x)
= (x3 + x + 1) · (a3 · x 3 + a2 · x 2 + a1 · x + a0)
= a3 · x6 + a2 · x5 + (a1 + a3) · x4 + (a0 + a2 + a3) · x 3 + (a1 + a2) · x2 + (a0 + a1) · x + a0
Aus dieser Darstellung wird deutlich, dass der Code nicht systematisch ist, da a1 im Codewort nur implizit, d. h. mit den anderen Stellen verknüpft, vorkommt.
Für das Informationswort 1011 ergibt sich hiermit:
a(x) = x3 + x + 1
als Informationswortpolynom und das Codewortpolynom
c(x) = g(x) · a(x) = x6 + x2 + 1
also das Codewort 1000101. Entsprechend lassen sich alle 16 Codewörter durch Multiplikation mit g(x) erzeugen.
Was nun, wenn ein so codiertes Wort fehlerhaft empfangen wird? Diesen Fall stellt man sich so vor, dass zu dem ursprünglich vorhandenen Codewort c(x) bei der Übertragung ein Fehlerwort f(x) addiert worden ist. Man erhält also ein c'(x) der Form:
c'(x) = c(x) + f(x).
Wird nun ein Codewort empfangen und durch g(x) geteilt, dann entsteht bei der Division kein Rest, falls das empfangene Codewort korrekt übertragen wurde. Selbstverständlich besteht theoretisch die Möglichkeit, dass f(x) ein anderes gültiges Codewort oder ein Vielfaches von g(x) ist und man als c'(x) wieder ein gültiges Codewort erhält. In diesem Fall würde ein Fehler nicht erkannt werden können, eine Korrektur wäre nicht möglich.
Wie die allgemeinen linearen Codes sind die zyklischen Codes in der Lage, in Abhängigkeit von ihrer Hammingdistanz Fehler zu erkennen oder zu korrigieren. Zudem können sogenannte Bündelfehler erkannt werden, das bedeutet, dass im gestörten Codewort über mehrere Bitpositionen hinweg nur die Werte 0 oder 1 auftreten.
Dividiert man das gestörte Codewortpolynom c'(x) wieder durch g(x), so ergibt sich ein Divisionsrest in Form eines Polynoms dessen Koeffizienten aus den Koeffizienten des Fehlerpolynoms f(x) zusammengesetzt sind.
| c'(x) | c(x) + f(x) | ||
| ------ | = | ------------ | = q(x) Rest s(x) |
| g (x) | g (x) |
Dieser Rest wird Syndrom(polynom) genannt. Anhand der allgemeinen Form des Syndroms bei gestörtem Codewort lassen sich im speziellen Fall Fehler erkennen und eventuell korrigieren.
Im obigen Beispiel soll nun beispielsweise das Codewort 1010101 decodiert werden. Bei der Division des zugehörigen Polynoms c'(x) durch g(x) entsteht ein Rest:
| c'(x) | |
| ------ | = q(x) Rest (x2 + x) |
| g (x) |
Das empfangene Wort ist also kein gültiges Codewort, es wurde offensichtlich falsch übertragen. Um den Fehler zu finden, betrachtet man nun die allgemeine Form eines gestörten Codeworts dieses Codes.
c'(x) = c(x) + f(x)
= (a3 + f6) · x 6 + (a2 + f5) · x5 + (a1 + a3 + f4) · x4 + (a0 + a2 + a3 + f3) · x3 + (a1 + a2 + f2) · x2 + (a0 + a1 + f1) · x + (a0 + f0)
Die Division durch g(x) ergibt als Rest das Syndrom
s(x) = (f2 + f4 + f5 + f6) · x2 + (f1 + f3 + f4 + f5) · x + (f0 + f3 + f5 + f6)
Ausgehend davon, dass dieser Code Hammingdistanz 3 hat und damit die Korrektur von Einzelfehlern erlaubt, wird nun versucht, den Fehler zu finden. In der allgemeinen Form des Syndroms sind die einzelnen Stellen von f(x) eindeutig codiert. Ein Einzelfehler ließe sich also anhand des Syndroms eindeutig erkennen und korrigieren. Im gegebenen Fall codiert das Syndrom (x2 + x) die Position f4. Unter der Annahme des am nächsten gelegenen Fehlers kann das gestörte Codewort also durch Addition des gefundenen Fehlers f(x) = x4 korrigiert werden. Man beachte, dass beispielsweise der Doppelfehler f(x) = x5 + 1 das selbe Syndrom erzeugt hätte, was aber mit dieser Methode nicht erkannt werden kann. Es besteht hier also immer die Gefahr, dass ein aufgetretener Fehler der die Möglichkeiten des jeweiligen Codes übersteigt, zu falschen Ergebnissen bei der Korrektur führt.
Wie bei den linearen Codes gibt es auch in der Untermenge der zyklischen Codes systematische und nicht systematische (siehe [4]).
Erinnerung: die systematischen Codes sind Codes, bei denen die m Stellen des codierten Informationswortes unverändert im Codewort enthalten sind. Sie können ebenso wie die n Prüfstellen eindeutig angegeben werden. Die systematischen zyklischen Codes lassen sich wieder mit Hilfe des Generatopolynoms g(x) und der Angabe von n erzeugen. Das Informationswort wird durch Multiplikation mit xn-m in höherwertige Polynomstellen verschoben. Das entstandene Polynom wird durch g(x) geteilt, es entsteht ein Rest:
| xn-m · a(x) | |
| ----------- | = q(x) Rest r(x) |
| g(x) |
dieser Rest wird zum verschobenen Informationswort addiert, fertig ist das Codewort.
c(x) = xn-m · a(x) + r(x)
Die Fehlererkennung und -korrektur funktioniert hier genauso wie bei den nichtsystematischen zyklischen Codes. Systematische Codes werden in der Praxis bevorzugt, weil das codierte Wort, sofern es nicht fehlerbehaftet ist, direkt abgelesen werden kann.
Die zyklischen Codes sind vor allem deshalb so interessant, weil die Multiplikation und Division von Polynomen mit Hilfe von sogenannten rückgekoppelten Schieberegistern überraschend einfach realisiert werden kann. Durch die Multiplikation mit dem Generatorpolynom lassen sich also Codewörter generieren, durch die Division dieser Codewörter wird das ursprüngliche Informationswort wiederhergestellt und das Ergebnis gleichzeitig auf Fehler geprüft.
Ein rückgekoppeltes Schieberegister zur Multiplikation besteht aus den folgenden drei Schalterelementen:
Speicherzelle
speichert in jedem Taktschritt den am Eingang ankommenden Wert und gibt den gespeicherten Wert am Ausgang weiter
Antivalenzglied
entspricht der Addition modulo 2 in der Menge {0, 1}, addiert den in der vorgeschalteten Speicherzelle liegenden Wert mit dem am Eingang anliegenden.
Multiplizierer
Das am Eingang anliegende Element wird mit a aus der Menge {0, 1} multipliziert und das Produkt wird ausgegeben.
Der Aufbau eines rückgekoppelten Schieberegisters wird am Besten anhand eines einfachen Beispiels betrachtet (siehe [3]).
rückgekoppeltes Schieberegister zur Polynommultiplikation
Die Abbildung zeigt ein Schieberegister zur Multiplikation eines Eingabepolynoms a(x) mit dem Generatorpolynom g(x) = g3 · x 3 + g2 · x 2 + g1 · x + g0. Die Codierung eines gegebenen Informationswortes läuft nun folgendermassen ab:
Zu Beginn enthalten alle Speicherelemente den Wert 0. Das zu codierende Informationswortpolynom wird nun schrittweise, der Koeffizient höchsten Grades voran, in die Schaltung geschoben. Der an der Eingabe anliegende Koeffizient wird im ersten Taktschritt mit den Koeffizienten von g(x) multipliziert, die Ergebnisse werden modulo 2 zu den in den Speicherelementen vorhandenen Werten (also 0) addiert und einen Speicherbaustein weiter abgelegt. Nach dem ersten Taktzyklus kann also bereits das Produkt der jeweils höchsten Koeffizienten von a(x) und g(x) an der Ausgabe abgelesen werden. Sobald das eingegebene Polynom ganz in die Schaltung geschoben worden ist, ist das Codewort bereits berechnet und die höchsten Koeffizienten sind ausgegeben. Betrachtet man wie im obigen Beispiel die Codierung eines Informationswortpolynoms vom Grad drei, lässt sich an folgender Tabelle leicht nachvollziehen was in den einzelnen Taktschritten passiert.
Taktschritt |
Eingabe |
s0 |
s1 |
s2 |
s3 |
Ausgabe |
|---|---|---|---|---|---|---|
1 |
a3 |
a3 · g0 |
a3 · g1 |
a3 · g2 |
a3 · g3 |
0 |
2 |
a2 |
a2 · g0 |
a3 · g0 + |
a3 · g1 + |
a3 · g2 + |
a3 · g3 |
3 |
a1 |
a1 · g0 |
a2 · g0 + |
a3 · g0 + |
a3 · g1 + |
a3 · g2 + |
4 |
a0 |
a0 · g0 |
a1 · g0 + |
a2 · g0 + |
a3 · g0 + |
a3 · g1 + |
Man erkennt, dass nach dem vierten Taktschritt alle Koeffizienten des Produkts a(x) · g(x) in absteigender Reihenfolge berechnet worden sind (grau unterlegt). Die letzten (im Beispiel vier Stück) Koeffizienten stehen noch in den Speicherzellen des Registers und können durch Eingabe von weiteren (vier) Nullen durchgeschoben werden, an ihren Werten ändert sich dadurch nichts mehr.
rückgekoppeltes Schieberegister zur Polynomdivision
Auch hier steht zu Beginn in allen Speicherstellen des Registers der Wert 0. Man erkennt sofort, dass während der ersten vier Taktzyklen am Ausgang der Wert 0 anliegt. Im fünften Schritt erscheint dann die höchste Stelle des Eingabewortes, die gleichzeitig mit den Koeffizienten g2, g1 und g0 multipliziert und zu den nachfolgenden Stellen des Codewortes addiert wird. Man beachte hierbei, dass g3 = 1 sein muss und die Addition und Subtraktion in GF(2) das selbe sind. Wie oben macht man sich klar, dass dieses Schieberegister eine Division durch g(x) realisiert. Wird ein gestörtes Codewort in dieser Schaltung dividiert, dann bleibt der bei der Division durch das Generatorpolynom entstehende Rest in den Speicherzellen des Schieberegisters stehen, nachdem das Codewort abgearbeitet ist (siehe [3]). Nur wenn ein korrektes Codewort eingegeben wurde ist der Wert in allen Speicherzellen nach der Division Null. Dieser Divisionsrest, der auch Signatur des Polynoms genannt wird, kann dann wie im Beispiel zur Auswertung eines eventuell aufgetretenen Fehlers im Codewort verwendet werden.