2001:16B8:6800:1F00:800E:AB8D:2724:C3D0: /* Beispiele */

2018-08-13T19:08:51Z

Beispiele

Neue Seite

Ein '''zyklischer Code''' ist ein in der [[Digitale Signalverarbeitung|digitalen Signalverarbeitung]] und der [[Nachrichtentechnik]] eingesetzter [[Kanalcodierung|Kanalcode]]. Zyklische Codes sind Teil der Gruppe der [[Linearer Code|linearen Codes]] und werden unter anderem zur [[Vorwärtsfehlerkorrektur]] auf [[Kanal (Informationstheorie)|Übertragungskanälen]] oder bei [[Datenspeicher]]n 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 (Informationstheorie)|Redundanz]] korrigieren kann.

== Definition ==

Ein zyklischer Code <math>C</math> ist ein linearer Code, der zusätzlich folgende Eigenschaft hat: Ist <math>(a_0, a_1, \dots, a_{n-1})</math> ein Codewort von <math>C</math>, dann ist auch <math>(a_1, a_2, \dots, a_{n-1}, a_0)</math> ein Codewort von <math>C</math>. Daraus folgt, dass auch <math>(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})</math> Codewörter von <math>C</math> sind.

== Polynomiale Darstellung ==
Zyklische Codes der Länge <math>n</math> lassen sich als [[Ideal (Ringtheorie)|Ideale]] des [[Ring (Algebra)|Rings]] <math>R:=\mathbb F_q[x]/(x^n-1)</math> beschreiben. Die Zeichen eines Codewortes <math>a</math> werden dabei als Koeffizienten eines Polynomes <math>a(x)</math> betrachtet:

:<math>(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}</math>.

Elemente des Rings <math>R</math> sind [[Restklasse]]n von Polynomen bezüglich der [[Polynomdivision]] durch <math>x^n-1</math>. Jede Restklasse hat ein ausgezeichnetes Element vom Grad kleiner <math>n</math>, welches zur Bezeichnung der Restklasse verwendet wird: <math>a(x)=a_0+a_1x+\dots+a_{n-1}x^{n-1}</math>. Multiplikation mit <math>x</math> und Reduktion modulo <math>x^n-1</math> führen auf das Polynom

:<math>x\,a(x) \mod x^n-1=a_{n-1}+a_0 x+\dots +a_{n-2}x^{n-1}</math>,

das gerade die zyklisch verschobene Koeffizientenfolge besitzt. Die Eigenschaft zyklisch zu sein bedeutet also im Polynomring, dass der Code <math>C</math> gegen Multiplikation mit <math>x</math> und somit mit [[Monom]]en beliebigen Grades abgeschlossen ist.

Da der Code <math>C</math> auch linear ist, also Vielfache und Summen von Codewörtern enthält, ergibt sich, dass mit einem Polynom <math>a(x)</math> auch die Koeffizientenfolgen aller Polynome <math>b(x)a(x) \mod x^n-1</math> im Code enthalten sind, der Code also einem Ideal im Ring entspricht.

Da <math>\mathbb F_q[x]</math> ein [[Hauptidealring]] ist, wird das Ideal, das von <math>(x^n-1)</math> und den Polynomen, die Codewörtern entsprechen, erzeugt wird, schon von einem darin enthaltenen Polynom <math>g(x)</math> kleinsten Grades erzeugt (Erzeugerpolynom). Dieses ist immer ein Teiler von <math>(x^n-1)</math>. Kennt man also alle Teilerpolynome von <math>(x^n-1)</math>, so kennt man auch alle zyklischen linearen Codes in <math>\mathbb F_q^n</math>. Besonderes Interesse genießen die Codes, die den [[Irreduzibles Polynom|irreduziblen]] Faktoren entsprechen.

== Codierung und Decodierung ==
=== Codierung ===
Das Erzeugerpolynom <math>g(x)</math> habe den Grad <math>n-k</math>. Der Code hat dann die Dimension <math>k</math>. Ein Klartextwort <math>w\leftrightarrow w(x)=w_0+\dots+w_{k-1} x^{k-1}</math> wird entweder durch Multiplikation oder durch Division zu einem Codewort <math>c(x)</math> codiert:

;Multiplikation
Die Multiplikation mit <math>g(x)</math> ist die offensichtliche Methode: <math>c(x)=w(x)\cdot g(x)</math>.

;Division
Der Ring <math>R</math> ist ein [[Euklidischer Ring]] bezüglich der Polynomdivision. Daher sind in der Gleichung <math>w(x)\cdot x^{n-k} = q(x)\cdot g(x) + r(x)</math> die Polynome <math>q(x)</math> und <math>r(x)</math> mit <math>\text{Grad}(r(x))<\text{Grad}(g(x))</math> eindeutig bestimmt (<math>r(x)</math> wird mittels Polynomdivision berechnet). Das Wort <math>w(x)</math> wird dann nach <math>c(x) = w(x) \cdot x^{n-k} - r(x) </math> 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 [[#Realisierungen|unten]]).

=== Decodierung ===
Ein empfangenes Wort <math>b(x)</math> wird durch <math>g(x)</math> dividiert. Ist der Rest gleich Null, war <math>b(x)</math> bereits aus dem Code. Ist der Rest ungleich Null, dann trat bei der Übertragung ein Fehler auf. Der Rest entspricht dabei dem [[Syndromdecodierung|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|mini|hochkant=1.5|Zyklischer Codegenerator in Form eines LFSR]]
Der Vorteil von zyklischen Codes in praktischen Anwendungen, wie [[Digitaltechnik|digitalen Schaltungen]], besteht in der Möglichkeit, diese Codes mit [[Linear rückgekoppeltes Schieberegister|linear rückgekoppelten Schieberegistern]] (LFSR) erzeugen zu können.

In nebenstehender Abbildung ist zur Veranschaulichung ein zyklischer [[Hamming-Code|(15,11)-Hamming Encoder]] mit dem Generatorpolynom ''z''<sup>4</sup> + ''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-Code#Zyklischer_Hamming-Code|Hamming-Code]]s gibt es spezielle zyklischen Varianten der [[Reed-Solomon-Code]]s, die unter anderem im Datenformat der [[CD-ROM]] Anwendung finden. Wiederum ein Spezialfall der letztgenannten sind die Codes, die bei der [[Zyklische Redundanzprüfung|zyklischen Redundanzprüfung]] (CRC) zur Fehlererkennung verwendet werden.

== Literaturquellen ==
* {{Literatur
|Autor = [[Martin Bossert]]
|Titel = Kanalcodierung
|Auflage=2. vollständig neubearbeitete und erweiterte
|Verlag = Teubner |Ort=Stuttgart |Jahr = 1998 |Seiten = |ISBN = 3-519-16143-5 |Kommentar=''Informationstechnik''
}}
* {{Literatur
|Autor = Todd K. Moon
|Titel = Error Correction Coding. Mathematical Methods and Algorithms
|Verlag = Wiley-Interscience |Ort=Hoboken NJ |Jahr = 2005 |ISBN = 0-471-64800-0
}}
* {{Literatur
|Autor = Harm Pralle
|Titel = Codierungstheorie, Vorlesungsskript
|Verlag = Technische Universität Braunschweig |Jahr = 2005
}}

[[Kategorie:Nachrichtentechnik]]
[[Kategorie:Kodierungstheorie]]

Zyklischer Code - Versionsgeschichte

2001:16B8:6800:1F00:800E:AB8D:2724:C3D0: /* Beispiele */