Zyklischer Code

Ein zyklischer Code ist ein in der digitalen Signalverarbeitung und der Nachrichtentechnik eingesetzter Kanalcode. Zyklische Codes sind Teil der Gruppe der linearen Codes und werden unter anderem zur Vorwärtsfehlerkorrektur auf Übertragungskanälen oder bei Datenspeichern eingesetzt.

Als solcher ist er die Basis für eine Reihe von Verfahren zur Signalübertragung, mit denen der Empfänger einer Nachricht diese auf Fehler prüfen kann, und gegebenenfalls aufgetretene Fehler ohne Rückfrage an den Sender durch die zusätzliche eingebrachte Redundanz korrigieren kann.

Definition

Ein zyklischer Code Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C} ist ein linearer Code, der zusätzlich folgende Eigenschaft hat: Ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (a_0, a_1, \dots, a_{n-1})} ein Codewort von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C} , dann ist auch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (a_1, a_2, \dots, a_{n-1}, a_0)} ein Codewort von $C$. Daraus folgt, dass auch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (a_2, a_3, \dots, a_{n-1}, a_0, a_1), (a_3, a_4, \dots, a_{n-1}, a_0, a_1, a_2), \ldots, (a_{n-1}, a_0, a_1, \ldots, a_{n-2})} Codewörter von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C} sind.

Polynomiale Darstellung

Zyklische Codes der Länge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} lassen sich als Ideale des Rings Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R:=\mathbb F_q[x]/(x^n-1)} beschreiben. Die Zeichen eines Codewortes $a$ werden dabei als Koeffizienten eines Polynomes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a(x)} betrachtet:

$(a_{0},a_{1},a_{2},\dots ,a_{n-1})\leftrightarrow a_{0}+a_{1}x+a_{2}x^{2}+\dots +a_{n-1}x^{n-1}$.

Elemente des Rings $R$ sind Restklassen von Polynomen bezüglich der Polynomdivision durch $x^{n}-1$. Jede Restklasse hat ein ausgezeichnetes Element vom Grad kleiner Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} , welches zur Bezeichnung der Restklasse verwendet wird: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a(x)=a_0+a_1x+\dots+a_{n-1}x^{n-1}} . Multiplikation mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} und Reduktion modulo Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x^n-1} führen auf das Polynom

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x\,a(x) \mod x^n-1=a_{n-1}+a_0 x+\dots +a_{n-2}x^{n-1}} ,

das gerade die zyklisch verschobene Koeffizientenfolge besitzt. Die Eigenschaft zyklisch zu sein bedeutet also im Polynomring, dass der Code $C$ gegen Multiplikation mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} und somit mit Monomen beliebigen Grades abgeschlossen ist.

Da der Code Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle C} auch linear ist, also Vielfache und Summen von Codewörtern enthält, ergibt sich, dass mit einem Polynom Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a(x)} auch die Koeffizientenfolgen aller Polynome Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b(x)a(x) \mod x^n-1} im Code enthalten sind, der Code also einem Ideal im Ring entspricht.

Da $\mathbb {F} _{q}[x]$ ein Hauptidealring ist, wird das Ideal, das von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (x^n-1)} und den Polynomen, die Codewörtern entsprechen, erzeugt wird, schon von einem darin enthaltenen Polynom Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g(x)} kleinsten Grades erzeugt (Erzeugerpolynom). Dieses ist immer ein Teiler von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (x^n-1)} . Kennt man also alle Teilerpolynome von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (x^n-1)} , so kennt man auch alle zyklischen linearen Codes in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb F_q^n} . Besonderes Interesse genießen die Codes, die den irreduziblen Faktoren entsprechen.

Codierung und Decodierung

Codierung

Das Erzeugerpolynom Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g(x)} habe den Grad Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n-k} . Der Code hat dann die Dimension Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} . Ein Klartextwort Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w\leftrightarrow w(x)=w_0+\dots+w_{k-1} x^{k-1}} wird entweder durch Multiplikation oder durch Division zu einem Codewort Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c(x)} codiert:

Multiplikation

Die Multiplikation mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g(x)} ist die offensichtliche Methode: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c(x)=w(x)\cdot g(x)} .

Division

Der Ring Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R} ist ein Euklidischer Ring bezüglich der Polynomdivision. Daher sind in der Gleichung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w(x)\cdot x^{n-k} = q(x)\cdot g(x) + r(x)} die Polynome Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q(x)} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r(x)} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \text{Grad}(r(x))<\text{Grad}(g(x))} eindeutig bestimmt (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r(x)} wird mittels Polynomdivision berechnet). Das Wort Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w(x)} wird dann nach Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c(x) = w(x) \cdot x^{n-k} - r(x) } codiert.

Vorteil dieses Verfahrens ist einerseits, dass die Informationssymbole/Informationsbits direkt als Klartext im Codewort stehen. Weiterhin ist die schaltungstechnische Realisierung dieses Verfahren für Binärcodes sehr einfach (siehe unten).

Decodierung

Ein empfangenes Wort Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b(x)} wird durch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g(x)} dividiert. Ist der Rest gleich Null, war Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b(x)} bereits aus dem Code. Ist der Rest ungleich Null, dann trat bei der Übertragung ein Fehler auf. Der Rest entspricht dabei dem Syndrom, das Wort kann dann mit Hilfe einer Syndromtabelle decodiert werden.

Schaltungstechnisch bedeutet dies, dass für die Codierung mittels Division und die Decodierung – im Großen und Ganzen – die gleichen Schaltungen verwendet werden können.

Realisierungen

Datei:Hamming Encoder cyclic.PNG

Zyklischer Codegenerator in Form eines LFSR

Der Vorteil von zyklischen Codes in praktischen Anwendungen, wie digitalen Schaltungen, besteht in der Möglichkeit, diese Codes mit linear rückgekoppelten Schieberegistern (LFSR) erzeugen zu können.

In nebenstehender Abbildung ist zur Veranschaulichung ein zyklischer (15,11)-Hamming Encoder mit dem Generatorpolynom z⁴ + z + 1 dargestellt. Im Encoder werden die Nutzdatenbits d als serieller Datenstrom in der Mitte oben eingelesen und rechts das Codewort c seriell ausgegeben. Die Schalter befinden sich zunächst in Stellung A: Damit werden im Codewort zunächst die Datenbits direkt ausgegeben und gleichzeitig in das LFSR geschoben. Sind alle Datenbits eines Datenwortes eingelesen, wechseln die beiden Schalter in Stellung B: Es wird nun bitweise der Inhalt des LFSR ausgegeben, der den Prüfstellen p entspricht. Sind alle Prüfstellen ausgegeben, wiederholt sich der Vorgang. Zur Vereinfachung sind die nötigen Taktleitungen und Synchronisationschaltungen in der Schaltskizze nicht dargestellt.

Die Decodierung von zyklischen Code auf Empfängerseite kann mittels LFSR erfolgen, wobei meist eine Syndromdecodierung zur Anwendung kommt.

Beispiele

Neben den erwähnten zyklischen Hamming-Codes gibt es spezielle zyklischen Varianten der Reed-Solomon-Codes, die unter anderem im Datenformat der CD-ROM Anwendung finden. Wiederum ein Spezialfall der letztgenannten sind die Codes, die bei der zyklischen Redundanzprüfung (CRC) zur Fehlererkennung verwendet werden.

Literaturquellen

• Martin Bossert: Kanalcodierung. 2. vollständig neubearbeitete und erweiterte Auflage. Teubner, Stuttgart 1998, ISBN 3-519-16143-5 (Informationstechnik). 
• Todd K. Moon: Error Correction Coding. Mathematical Methods and Algorithms. Wiley-Interscience, Hoboken NJ 2005, ISBN 0-471-64800-0. 
• Harm Pralle: Codierungstheorie, Vorlesungsskript. Technische Universität Braunschweig, 2005.