Direkt zum Inhalt

Lexikon der Mathematik: zyklischer Code

ein linearer Code, bei dem mit jedem Codewort (c1, c2, …, cn) auch das zyklisch verschobene Wort (cn, c1, c2.c3, …, cn−1) im Code enthalten ist.

Interpretiert man die Codevektoren c = (ci) eines linearen Codes CKn als Polynome Σici−1xi über K, dann ist ein zyklischer Code ein Ideal im Faktorring K[x]/(xn − 1), in dem die Multiplikation mit x gerade die zyklische Verschiebung des Koeffizientenvektors ist. Das (bis auf konstanten Faktor eindeutig bestimmte) Polynom g(x) minimalen Grades des Codes nennt man Generatorpolynom des Codes. Alle Code-Polynome sind durch g(x) teilbar. Weil g(x) minimalen Grad hat, muß auch xn − 1 durch g(x) teilbar sein (sonst wäre der Rest r(x) bei der Division von xn − 1 durchg(x) auch ein Element des Ideals).

Für den Paritätskontroll-Code (Σici = 0), der offensichtlich zyklisch ist, ist das Generatorpolynom \begin{eqnarray}x-1\end{eqnarray} für den Wiederholungscode (c1 = c2 = · · · = cn) ist es \begin{eqnarray}{x}^{n-1}+\cdots +x+1.\end{eqnarray} Die Generatorpolynome lassen sich auch durch ihre Nullstellen im Körper K oder einer Erweiterung K′ von K beschreiben. So kann man für den binären Hamming-Code mit der Kontrollmatrix \begin{eqnarray}H=\left(\begin{array}{ccccccc}1 & 0 & 0 & 1 & 0 & 1 & 1\\ 0 & 1 & 0 & 1 & 1 & 1 & 0\\ 0 & 0 & 1 & 0 & 1 & 1 & 1\end{array}\right)\end{eqnarray} die Spalten der Matrix H als Potenzen \begin{eqnarray}1,\alpha, {\alpha }^{2},\ldots, {\alpha }^{6}\end{eqnarray} eines Elementes α aus \begin{eqnarray}{\mathbb{F}}\end{eqnarray}8 auffassen. Folglich ist c(x) genau dann ein Code-Polynom, wenn c(α) = 0 ist (dies entspricht der Anwendung der Kontrollmatrix auf den Code-Vektor). Daraus erhält man das Generatorpolynom x3 + x + 1 als Minimalpolynom von α.

Erweitert man den Hamming-Code mit der Bedingung c(α) = 0 durch die Bedingung c3) = 0, so erhält man einen Code, der zwei Fehler sicher korrigiert. Aus den Syndrom-Werten s(α) und s3) kann man die beiden fehlerhaften Koeffizienten berechnen. Man erhält so zum Beispiel über \begin{eqnarray}{\mathbb{F}}\end{eqnarray}16 einen (15,7)-Code mit der Matrix \begin{eqnarray}H=\left(\begin{array}{ccccccccccccccc}\text{1} & \text{0} & \text{0} & \text{0} & \text{1} & \text{0} & \text{0} & \text{1} & \text{1} & \text{0} & \text{1} & \text{0} & \text{1} & \text{1} & \text{1}\\ \text{0} & \text{1} & \text{0} & \text{0} & \text{1} & \text{1} & \text{0} & \text{1} & \text{0} & \text{1} & \text{1} & \text{1} & \text{1} & \text{0} & \text{0}\\ \text{0} & \text{0} & \text{1} & \text{0} & \text{0} & \text{1} & \text{1} & \text{0} & \text{1} & \text{0} & \text{1} & \text{1} & \text{1} & \text{1} & \text{0}\\ 0 & 0 & 0 & 1 & \text{0} & \text{0} & \text{1} & \text{1} & \text{0} & \text{1} & \text{0} & \text{1} & \text{1} & \text{1} & \text{1}\\ 1 & 0 & 0 & 0 & \text{1} & \text{1} & \text{0} & \text{0} & \text{0} & \text{1} & \text{1} & \text{0} & \text{0} & \text{0} & \text{1}\\ 0 & 0 & 0 & \text{1} & \text{1} & \text{0} & \text{0} & \text{0} & \text{1} & \text{1} & \text{0} & \text{0} & \text{0} & \text{1} & \text{1}\\ 0 & 0 & 1 & 0 & \text{1} & \text{0} & \text{0} & \text{1} & \text{0} & \text{1} & \text{0} & \text{0} & \text{1} & \text{0} & \text{1}\\ 0 & 1 & 1 & \text{1} & \text{1} & \text{0} & \text{1} & \text{1} & \text{1} & \text{1} & \text{0} & \text{1} & \text{1} & \text{1} & \text{1}\end{array}\right)\end{eqnarray}

Ist n zu q teilerfremd und α eine n-te primitive Einheitswurzel aus einer Erweiterung von \begin{eqnarray}{\mathbb{F}}\end{eqnarray}q, dann wird für jedes k ein zyklischer Code C der Länge n über \begin{eqnarray}{\mathbb{F}}\end{eqnarray}q durch das Minimalpolynom von \begin{eqnarray}{\alpha }^{k},{\alpha }^{k+1},\ldots, {\alpha }^{k+d-2}\end{eqnarray} erzeugt. R.C. Bose, D.K. Ray-Chaudhuri und A. Hocquenghem haben 1960 gezeigt, daß der minimale Hamming-Abstand dieser Codes mindestens d beträgt. Sie werden deshalb auch BCH-Codes genannt.

Im Spezialfall n = q − 1 liegen die n-ten Einheitswurzeln im Grundkörper \begin{eqnarray}{\mathbb{F}}\end{eqnarray}q, und das Generatorpolynom ist gleich dem Minimalpolynom. Diese speziellen BCH-Codes (auch Reed-Solomon-Codes genannt) haben maximalen Hamming-Abstand (Singleton-Schranke).

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos