6 Zyklische Codes

6.1 Grundbegriffe

Definition. Sei C ⊆ GF (q)n ein linearer Code, dessen Worter c ∈ C wirc = cn−1cn−2 . . . c1c0 schreiben. C heißt zyklischer Code, falls gilt

cn−1cn−2 . . . c1c0 ∈ C =⇒ cn−2cn−3 . . . c1c0cn−1 ∈ C .

Beispiel. a. Offenbar ist der Wiederholungscode C = {00 . . . 0, 11 . . . 1, . . .}zyklisch. Sei q = 2, dann ist der Paritatscode

C = {c ∈ GF (2)n : w(c) gerade}

zyklisch, da das Gewicht unter zyklischer Vertauschung invariant bleibt.

Wie konnen wir allgemein feststellen, ob ein Code zyklisch ist?

Zur Abkurzung sei K = GF (q) endlicher Korper. Zu jedem Wort a =an−1 . . . a1a0 assoziieren wir das Polynom a(x) = an−1x

n−1+. . .+a1x+a0. SeiKn[x] der Vektorraum aller Polynome vom Grad ≤ n−1. Dann ist a −→ a(x)ein Isomorphismus von Kn auf Kn[x]. Jeder Code C ⊆ Kn korrespondiertzu einem C(x) ⊆ Kn[x].

Die Basis {(1, 0, . . . , 0), (0, 1, 0, . . . , 0), . . . , (0, 0, . . . , 0, 1)} von Kn entsprichtder Basis {xn−1, xn−2, . . . , x, 1} von Kn[x].

Sei m(x) ∈ K[x] vom Grad n. Wir betrachten den Ring K[x]/(m(x)) derPolynome mod m(x), das heißt

f(x) ≡ g(x)(mod m(x)) ⇐⇒ m(x)∣∣f(x) − g(x) .

Ein Reprasentantensystem ist dann Kn[x]. Ist f(x) ∈ K[x], dann ergibtPolynomdivision

f(x) = p(x)m(x) + r(x)

mit r(x) = 0 oder Grad r(x) < n. Aus f(x) − r(x) = p(x)m(x) folgtf(x) ≡ r(x) (mod m(x)), somit ist jedes Polynom kongruent zu einem Poly-

83

nom aus Kn[x]. Sind a(x), b(x) ∈ Kn[x] mit m(x)|a(x) − b(x), so haben wirGrad (a(x) − b(x)) < n also a(x) = b(x).

Mit Kn[x] K[x]/(m(x)) haben wir nun auch eine Multiplikation gegeben.Seien a(x), b(x) ∈ Kn[x], und

a(x)b(x) = p(x)m(x) + r(x) ,

dann ist r(x) ∈ Kn[x] und

a(x)b(x) ≡ r(x) (mod m(x)).

Nun betrachten wir speziell das Polynom m(x) = xn− 1. Der zyklische Shiftan−1 . . . a1a0 −→ an−2 . . . a0an−1 entspricht

xa(x) = an−2xn−1 + . . . + a0x + an−1x

n

≡ an−2xn−1 + . . . + a0x + an−1 (mod xn − 1),

und wir haben gezeigt:

Satz 29. C ⊆ Kn ist zyklisch ⇐⇒ (c(x) ∈ C(x) =⇒ xc(x) ∈ C(x) (mod xn−1)).

Aus der Algebra kennen wir die Begriffe Ideal, Hauptideal und Hauptideal-ring. Eine Menge J ⊆ K[x] heißt Ideal, falls

• J Unterraum von K[x] ist und

• a(x) ∈ J , h(x) ∈ K[x] =⇒ h(x)a(x) ∈ J fur alle h(x) ∈ K[x].

J heißt Hauptideal, falls g(x) ∈ K[x] existiert mit J = {a(x) : g(x)|a(x)}.Wir schreiben dann J = (g(x)).

Satz 30. K[x] ist Hauptidealring, das heißt jedes Ideal ist Hauptideal.

Beweis. Sei J = (0) Ideal und g(x) das eindeutig bestimmte normiertePolynom von minimalem Grad in J . Sei c(x) ∈ J , dann haben wir

c(x) = p(x)g(x) + r(x).

84

Wegen p(x)g(x) ∈ J und r(x) = c(x) − p(x)g(x) ist r(x) ∈ J und daherr(x) = 0 wegen der Minimalitat des Grades. J besteht also genau aus allenVielfachen von g(x), somit J = (g(x)). �

Wir konnen dies sofort auf Kn[x] erweitern.

Satz 31. Sei m(x) ∈ K[x] normiertes Polynom vom Grad n. Dann istKn[x] ∼= K[x]/(m(x)) Hauptidealring. J ist genau dann Ideal von Kn[x],falls ein normiertes Polynom g(x) ∈ Kn[x] existiert mit

J = {a(x) ∈ Kn[x] : g(x)|a(x)}, g(x)|m(x). (1)

Beweis. Sei J = (0) Ideal in Kn[x] = K[x]/(m(x)) und g(x) das normiertePolynom mit minimalem Grad, g(x) = 0. Polynomdivision ergibt fur a(x) ∈J

a(x) = p(x)g(x) + r(x), Grad r(x) < Grad g(x) .

Daraus folgta(x) ≡ p(x)g(x) + r(x) (mod m(x)) ,

daher r(x) ∈ J und somit r(x) = 0, das heißt g(x)|a(x). Umgekehrt sindnaturlich alle Vielfachen a(x) ∈ Kn[x] von g(x) in J . Um g(x)|m(x) zuzeigen, verwenden wir wieder Polynomdivision

m(x) = p(x)g(x) + r(x), Grad r(x) < Grad g(x).

Wir haben m(x) ≡ 0 (mod m(x)), also 0 ∈ J , p(x)g(x) ∈ J , somit r(x) ∈ Jund wegen der Minimalitat folgt wieder r(x) = 0, das heißt g(x)|m(x).

Nun nehmen wir umgekehrt an, dass J ⊆ Kn[x] von der Form (1) ist. Offen-bar ist J Unterraum. Sei nun s(x) ∈ Kn[x] beliebig, a(x) ∈ J , dann gilt

s(x)a(x) = s(x)p(x)g(x), g(x) | m(x)

≡ r(x) (mod m(x))

mit r(x) ∈ Kn[x]. Wir haben somit

m(x) | s(x)p(x)g(x) − r(x)

85

und wegen g(x)|m(x) auch g(x)|r(x), das heißt r(x) = q(x)g(x). Insgesamtgilt

s(x)a(x) ≡ q(x)g(x) (mod m(x))

mit q(x)g(x) ∈ Kn[x], also s(x)a(x) ∈ J . �

Satz 32. Sei C ⊆ Kn linearer Code. Dann gilt

C ist zyklisch ⇐⇒ C(x) ist Ideal in Kn[x] = K[x]/(xn − 1) .

Beweis. Ist C(x) Ideal, so haben wir fur c(x) ∈ C(x) auch xc(x) ∈ C(x)(mod xn−1), also ist C zyklisch. Sei umgekehrt C zyklisch. Wir wissen, dassC(x) Unterraum von Kn[x] ist. Sei nun c(x) ∈ C(x), dann gilt xc(x) ∈ C(x)(mod xn − 1) nach Satz 29, somit auch x2c(x) ∈ C(x), allgemein xic(x) ∈C(x) fur alle i. Aus der Unterraumeigenschaft folgt dann auch p(x)c(x) ∈C(x) fur alle p(x) ∈ Kn[x]. �

In Zusammenfassung sehen wir: Zu jedem zyklischen Code C gibt es eineindeutiges normiertes Polynom g(x), so dass

C(x) = {a(x) ∈ Kn[x] : g(x)|a(x)}, g(x)|xn − 1

gilt. Das Polynom g(x) heißt das Generatorpolynom von C. Es gibt also genausoviele zyklische Codes der Lange n uber K, wie es verschiedene normierteTeiler von xn − 1 gibt. Sei g(x) = xr + gr−1x

r−1 + · · ·+ g1x + g0, dann ist

{g(x), xg(x), . . . , xk−1g(x)}, k = n − r ,

eine Basis von C(x), da jedes Vielfache von g(x) in Kn[x] als

(b0 + b1x + . . . + bk−1xk−1)g(x) = b0g(x) + b1xg(x) + · · ·+ bk−1x

k−1g(x)

geschrieben werden kann.

Wir haben alsodim C = n − Grad g(x)

und erhalten eine k × n-Generatormatrix

86

⎛⎜⎜⎜⎝g(x)xg(x)

...xk−1g(x)

⎞⎟⎟⎟⎠ =

⎛⎜⎜⎝0 . . . 0 1 gr−1 . . . g1 g0

0 . . . 1 gr−1 . . . g0 0

�

�

�

1 gr−1 . . . g0 . . . 0

⎞⎟⎟⎠ .

Beispiel. Sei K = GF (2), n = 8. Wir haben

x8 − 1 = (x − 1)8 = (x + 1)8 .

Die Teiler sind also 1, x + 1, (x + 1)2 = x2 + 1, (x + 1)3, . . . , (x + 1)8.

Fur g(x) = 1 ist dim C = 8, also C = (GF (2))8. Fur g(x) = x + 1 istdim C = 7 mit Generatormatrix

G =

⎛⎜⎜⎜⎜⎜⎜⎜⎜⎝

0 0 0 0 0 0 1 10 0 0 0 0 1 1 00 0 0 0 1 1 0 00 0 0 1 1 0 0 00 0 1 1 0 0 0 00 1 1 0 0 0 0 01 1 0 0 0 0 0 0

⎞⎟⎟⎟⎟⎟⎟⎟⎟⎠und wir erhalten den Paritatscode.

Fur g(x) = (x+1)7 = x7+x6+x5+· · ·+x+1 ergibt sich die Generatormatrix

G = (1 1 1 1 1 1 1 1) ,

also der Wiederholungscode C, dim C = 1.

Allgemein haben wir fur GF (2)

xn − 1 = (x − 1)(xn−1 + xn−2 + . . . + x + 1)

Der erste Teiler ergibt den Paritatscode, der zweite den Wiederholungscode.Dass die beiden Teiler zu dualen Codes korrespondieren, gilt ganz allgemein.

Definition. Sei C zyklischer Code der Lange n mit Generatorpolynom g(x).Dann heißt

h(x) =xn − 1

g(x)

87

das Kontrollpolynom von C.

Satz 33. Sei C zyklisch mit Generatorpolynom g(x) und Kontrollpolynomh(x). Dann gilt

c(x) ∈ C(x) ⇐⇒ c(x)h(x) ≡ 0 (mod xn − 1) .

Beweis. Wir haben

c(x) ∈ C(x) ⇐⇒ a(c) = p(x)g(x) ⇐⇒ a(x)h(x) = p(x)g(x)h(x)

⇐⇒ a(x)h(x) = p(x)(xn − 1)

⇐⇒ xn − 1 | a(x)h(x) . �Der folgende Satz wird durch Koeffizientenvergleich in xn − 1 = g(x)h(x)bewiesen.

Satz 34. Sei C ⊆ Kn zyklischer Code, g(x) das Generatorpolynom, h(x) dasKontrollpolynom, h(x) = xk + hk−1x

k−1 + · · · + h1x + h0, k = dim C. Dannist

H =

⎛⎜⎜⎜⎝0 0 . . . 0 h0 h1 . . . hk−1 10 0 . . . h0 h1 . . . 1 0...h0 h1 . . . 1 0 . . . 0

⎞⎟⎟⎟⎠Kontrollmatrix von C.

Fur die Codierung mittels zyklischer Codes verwendet man das Generatorpo-lynom g(x), fur die Decodierung das Kontrollpolynom h(x). Sei k = dim C,r = n−k = Grad g(x). Wir identifizieren die Nachrichten mit Kk und a ∈ Kk

mit a(x) ∈ Kk[x].

Die Codierung ist dann

a(x) ∈ Kk[x]ϕ−→ a(x)g(x) ∈ C(x) ⊆ Kn[x]

aϕ�−→ c ∈ C .

Zur Decodierung nehmen wir an, dass v(x) ∈ Kn[x] empfangen wurde, nach-dem u(x) ∈ C(x) gesendet wurde: v(x) = u(x)+e(x), e(x) = Fehlerpolynom.Wir haben

v(x)h(x) = u(x)h(x) + e(x)h(x) ≡ e(x)h(x) (mod xn − 1) .

88

Angenommen es ist ein Fehler aufgetreten, e(x) = ejxj , dann pruft man

v(x)h(x) ≡ ejxjh(x) (mod xn − 1)

mit dem Euklidischen Algorithmus.

6.2 Einiges uber endliche Korper

Wir stellen ein paar Grundtatsachen uber endliche Korper zusammen, diewir im folgenden brauchen werden.

1. Die kleinsten Korper (Primkorper) sind Zp = {a mod p}, p Primzahl.

2. Jeder Korper K besitzt einen kleinsten Unterkorper. Ist Zp ⊆ K, so ist Kein Vektorraum uber Zp, also |K| = q = pt, t = dimZp K. Ist Zp ⊆ K, so hatK die Charakteristik p, und es gilt

pa := a + a + · · · + a︸ ︷︷ ︸p

= 0 fur alle a ∈ K.

3. Zu jeder Primzahlpotenz q = pt gibt es einen endlichen Korper K, unddieser Korper ist eindeutig bis auf Isomorphie, bezeichnet GF (q). Man kannGF (q) folgendermaßen konstruieren: Man nehme ein irreduzibles Polynomm(x) ∈ GF (p)[x] vom Grad t, dann ist der Faktorring GF [x]/(m(x)) einKorper mit pt Elementen. Dass fur jede Primzahl p und jedes t ≥ 1 einirreduzibles Polynom m(x) ∈ GF (p)[x] vom Grad t existiert, lernt man inder Algebra.

4. Sei q = pt, a, b ∈ GF (q), dann gilt

(a ± b)pi

= api ± bp

i

(i ≥ 1),

insbesondere (a ± b)q = aq ± bq.

Der Beweis erfolgt mit Induktion nach i. Wir haben

(a ± b)p =

p∑i=0

(p

i

)ai(±b)p−i = ap ± bp

89

wegen p∣∣(pi

)fur 0 < i < p und daher

(pi

)ai(±b)p−i = 0. Außerdem ist (−b)p =

(−1)pbp = −bp (f’ur p = 2 ist 1 = −1). Der Induktionsschritt ist

(a ± b)pi+1

=[(a ± b)p

i]p

= (api ± bp

i

)p = api+1 ± bp

i+1

.

Die folgenden Abbildungen sind somit Automorphismen von GF (q), q = pt,genannt Frobenius Automorphismen:

a �−→ ap, a �−→ ap2

, . . . a �−→ aq, . . . .

5. Die multiplikative Gruppe GF (q)∗ =: {a ∈ GF (q), a = 0} ist zyklisch(Algebra). Jedes erzeugende Element α heißt primitives Element von GF (q)∗:

GF (q)∗ = {α, α2, α3, . . . , αq−2, αq−1 = 1}.

Die Anzahl der primitiven Elemente ist ϕ(q−1) (Eulersche ϕ-Funktion). Seiβ ∈ GF (q)∗, dann heißt ord(β) := min(s : βs = 1} die Ordnung von β. Esgilt fur alle β:

• ord(β) | q − 1

• βm = 1 ⇐⇒ ord(β) | m.

Insbesondere ist βq−1 = 1 fur alle β ∈ GF (q)∗. Die Elemente aus GF (q)∗

sind somit die q − 1 Nullstellen des Polynoms xq−1 − 1 ∈ GF (q)[x], und esgilt somit βq = β fur alle β ∈ GF (q). Der Automorphismus β �−→ βq ist aufGF (q) die Identitat.

Ist α primitives Element, d ein Teiler von q − 1, so hat αq−1

d Ordnung d.

Mit diesen Voruberlegungen kehren wir zu den zyklischen Codes zuruck. Un-ser Ziel ist es, bei gegebenen q und n die Zerlegung

xn − 1 = g1(x) · · · gs(x) ∈ GF (q)[x]

in irreduzible Faktoren zu bestimmen, und damit alle zyklischen Codes.

Voraussetzung: Sei q = pt, dann verlangen wir

ggT(n, q) = 1 (⇐⇒ p � n) .

90

In der Algebra lernt man, dass ein Polynom f(x) ∈ K[x] genau dann mehr-fache Nullstellen besitzt, wenn ggT(f(x), f ′(x)) = 1 ist. Fur xn− 1 bedeutetdies mit (xn − 1)′ = nxn−1

ggT(xn − 1, nxn−1) = 1 ,

und dies gilt genau dann, wenn nxn−1 = 0 ist (uber GF (q)) das heißt p|n.

Unsere Generalvoraussetzung besagt somit, dass xn − 1 nur einfache Null-stellen hat, und somit in der Zerlegung

xn − 1 = g1(x) · · · gs(x)

die irreduziblen Faktoren verschieden sind. Es gibt dann 2s zyklische Codes.

Die n Nullstellen von xn−1 (in einem geeigneten Erweiterungskorper GF (qm))heißen n-te Einheitswurzeln. Sie bilden mit Multiplikation eine Gruppe, daαn = 1, βn = 1 impliziert (αβ)n = 1, mit 1 als neutralem Element.

Beispiel. Sei q = 2. Um zu sehen, dass die Bedingung ggT(n, q) = 1 not-wendig ist, betrachten wir n = 6. Dann ist x6 − 1 = (x− 1)2(x2 +x+1)2 mitdoppelten Nullstellen.

n = 3 : x3 − 1 = (x − 1)(x2 + x + 1)

n = 5 : x5 − 1 = (x − 1)(x4 + x3 + x2 + x + 1) .

Ist x4 + x3 + x2 + x + 1 irreduzibel? Ja, denn weder x− 1 noch x2 + x + 1 istTeiler.

n = 7 : x7 − 1 = (x − 1)(x6 + x5 + x4 + x3 + x2 + x + 1)

= (x − 1)(x3 + x2 + 1)(x3 + x + 1) .

Wie findet man die Zerlegung allgemein?

Satz 35. Seien q und n gegeben, GF (q) ⊆ GF (qm). Das Polynom xn − 1zerfallt in Linearfaktoren in GF (qm) (oder aquivalent: GF (qm) enthalt allen-ten Einheitswurzeln) ⇐⇒ n|qm − 1.

91

Beweis. ⇐: Sei n|qm−1, α primitives Element in GF (qm)∗. Dann hat αqm−1

n

Ordnung n in GF (qm)∗, ist also n-te Einheitswurzel, und alle n-ten Einheits-wurzeln sind gegeben durch

αqm−1

n , α2 qm−1n , α3 qm−1

n , . . . , αnqm−1

n = 1 .

Daher zerfallt xn − 1 =n∏i=1

(x − αiqm−1

n ) in GF (qm)[x].

⇒: Sei qm− 1 = sn+ r, 0 ≤ r < n, und β eine beliebige n-te Einheitswurzel.Dann gilt

1 = βqm−1 = βsn · βr = (βn)sβr = βr .

Ware r > 0, so sind alle n-ten Einheitswurzeln Nullstellen des Polynomsxr − 1, was wegen r < n nicht geht. Also ist r = 0, und somit n|qm − 1. �

Folgerung 4. Die n-ten Einheitswurzeln bilden eine zyklische Gruppe mitMultiplikation.

Das ist klar, da eine Untergruppe der zyklischen Gruppe GF (qm)∗ wiederzyklisch ist. Die erzeugenden Elemente der Einheitsgruppe heißen primitiven-te Einheitswurzeln. Es gibt ϕ(n) primitive n-te Einheitswurzeln.

Folgerung 5. Das minimale m, fur das xn−1 in GF (qm) zerfallt, ist ord(q)in der primen Restklassengruppe Z∗

n.

Beispiel. a. q = 2, n = 5. Suche das kleinste m mit 2m ≡ 1 (mod 5). Das istm = 4, x5 − 1 zerfallt linear in GF (24), aber nicht in GF (23).b. x23 − 1 zerfallt uber GF (211):

2, 22 = 4, 23 = 8, 24 = 16, 25 ≡ 9, 26 ≡ 18, 27 ≡ 13, 28 ≡ 3, 29 ≡ 6,

210 ≡ 12, 211 ≡ 1 (mod 23).

Sei GF (q) ⊆ GF (qm), β ∈ GF (qm). Wir betrachten die Polynommenge

Jβ = {f(x) ∈ GF (q)[x] : f(β) = 0} .

92

Jβ ist nicht leer, da xqm − x ∈ Jβ ist fur alle β. Offenbar ist Jβ ein Ideal in

GF (q)[x], also wird Jβ vom normierten Polynom mβ(x) minimalen Gradeserzeugt, mβ(x) heißt das Minimalpolynom von β uber GF (q).

Es ist also mβ(x) ∈ GF (q)[x] und fur jedes f(x) ∈ GF (q)[x] gilt

f(β) = 0 ⇐⇒ mβ(x)∣∣f(x) .

Insbesondere ist fur alle β ∈ GF (qm)∗

mβ(x)∣∣xqm−1 − 1 .

Satz 36. Sei GF (q) ⊆ GF (qm), β ∈ GF (qm). Das Minimalpolynom mβ(x)ist irreduzibel in GF (q)[x].

Beweis. Aus mβ(x) = f(x)g(x) ∈ GF (q)[x] und mβ(β) = 0 folgt f(β) = 0oder g(β) = 0, sei o.B.d.A. f(β) = 0. Dann ist mβ(x)|f(x), also Grad f(x) =Grad mβ(x) und somit g(x) eine Konstante. �

Fazit: Zerfallt xn − 1 in GF (qm) in Linearfaktoren, so gilt

xn − 1 = mβ1(x) · · ·mβs(x) ∈ GF (q)[x] ,

wobei die mβi(x) die verschiedenen Minimalpolynome der n-ten Einheits-

wurzeln sind.

Wir sind also bei der Frage angelangt: Wie bestimmen wir die Minimalpoly-nome der n-ten Einheitswurzeln?

Dazu erinnern wir an den Frobenius Automorphismus. Sei GF (q) ⊆ GF (qm),und β �→ βq der Automorphismus. Zunachst sehen wir:

β ∈ GF (q) ⇐⇒ βq = β .

Wenn β ∈ GF (q) ist, so wissen wir schon βq = β. Umgekehrt kann dasPolynom xq−x nicht mehr Nullstellen besitzen, also genau die Elemente vonGF (q).

Wir fassen nun den Automorphismus β �→ βq als Permutation von GF (qm)auf und betrachten die Zyklen dieser Permutation. Der Zyklus, der β enthalt,

93

heißt die Bahn von β. Wir haben also:

{0}, {1}, {β, βq, βq2

, βq3

, . . .}, {γ, γq, . . .}, . . .

Beispiel. a. GF (24). Sei α primitives Element, also GF (24)∗ = {α, α2, . . . , α15 =1}, dann erhalten wir die Bahnen

{0}, {α, α2, α4, α8}, {α3, α6, α12, α9}, {α5, α10}, {α7, α14, α13, α11}, {α15 = 1} .

b. GF (2) ⊆ GF (211). Sei β primitive 23-te Einheitswurzel, dann sind dieBahnen der 23-ten Einheitswurzeln:

{β, β2, β4, β8, β16, β9, β18, β13, β3, β6, β12},{β5, β10, β20, β17, β11, β22, β19, β15β7, β14}, {β23 = 1} .

Da 23 Primzahl ist, gibt es 22 primitive 23-te Einheitswurzeln, und sie zer-fallen in zwei Bahnen der Große 11.

Satz 37. Sei GF (q) ⊆ GF (qm), β ∈ GF (qm) und B = {β, βq, βq2, . . .} die

Bahn von β. Dann ist

m(x) =∏γ∈B

(x − γ)

das Minimalpolynom von β in GF (q)[x].

Beweis. Wir wollen folgendes zeigen:

1) Sei h(x) ∈ GF (q)[x] mit h(γ) = 0, dann gilt h(γq) = 0.

2)∏γ∈B

(x − γ) ∈ GF (q)[x].

Aus 1) folgt dann sukzessive aus h(β) = 0, h(βq) = 0, h(βq2) = 0, . . ., das

heißt ist: Ist β Nullstelle von h(x), so sind alle Elemente der Bahn Nullstellen,somit

∏γ∈B

(x−γ) | h(x), und insbesondere∏γ∈B

(x−γ) | mβ(x). Aus 2) resultiert

94

dann sofort die Behauptung.

Beweis von 1). Sei h(x) =∑�

i=0 hixi ∈ GF (q)[x], h(β) = 0. Dann ist

h(βq) =�∑i=0

hi(βq)i =

�∑i=0

hi(βi)q

=�∑i=0

hqi (βi)q (wegen hqi = hi)

=

�∑i=0

(hiβi)q =

(�∑i=�

hiβi

)q

= 0 (wegen (α + β)q = αq + βq).

Beweis von 2). Sei m(x) =∏

γ∈B(x− γ) =∑s

i=0 fixi, und m(x) =

∏γ∈B(x−

γq). da mit γ auch γq die Bahn B durchlauft, haben wir m(x) = m(x).Andererseits sind die Koeffizienten eines Polynoms Summe von Produktender Nullstellen. Wegen des Frobenius Automorphismus haben wir daher

m(x) =

s∑i=0

f qi xi

und somit f qi = fi, das heißt fi ∈ GF (q) fur alle i, und daher m(x) ∈GF (q)[x]. �

Folgerung 6. Wir haben Grad mβ(x) ≤ m fur alle β ∈ GF (qm).

Beweis. Fur jedes β ∈ GF (qm) gilt βqm

= β, also muß sich die Bahn von βnach hochstens m Schritten schließen. �

Beispiel. Sei q = 2, n = 15. Das Polynom x15 − 1 zerfallt in GF (24). Sei αprimitives Element (somit primitive 15-te Einheitswurzel). Die Bahnen sind{0},

{α15 = 1}, {α, α2, α4, α8}, {α7, α14, α13, α11}{α3, α6, α12, α9}, {α5, α10} .

Die zweite und dritte Bahn korrespondieren zu den 8 primitiven 15-Einheits-wurzeln, die vierte Bahn zu den primitiven 5-ten und die letzte zu den pri-

95

mitiven 3-ten Einheitswurzeln.

Die Zerlegung ist

x15 − 1 = (x− 1)(x4 + x3 + 1)(x4 + x + 1)(x4 + x3 + x2 + x + 1)(x2 + x + 1).

Definition. Sei GF (q) ⊆ GF (qm). Ein Polynom m(x) ∈ GF (q)[x], dasMinimalpolynom eines primitiven Elementes von GF (qm) ist, heißt primitivesPolynom.

Satz 38. Sei GF (q) ⊆ GF (qm).

1. Ein irreduzibles normiertes Polynom m(x) ∈ GF (q)[x] ist primitiv ⇐⇒m(x)

∣∣xqm−1 − 1, aber m(x) � xi − 1 fur 0 < i < qm − 1.

2. Jedes primitive Polynom hat Grad m.

Beweis. 1. ⇒: Sei m(x) = mα(x) Minimalpolynom des primitiven Elementesα, dann gilt jedenfalls m(x)

∣∣xqm−1 − 1. Angenommen m(x)|xi − 1 fur i <qm − 1. Dann ist αi = 1 im Widerspruch zu ord(α) = qm − 1.⇐: Sei α beliebige Nullstelle von m(x), 0 < i < qm − 1. Polynomdivision inGF (q)[x] ergibt

xi − 1 = p(x)m(x) + r(x), Grad r(x) < Grad m(x) ,

und wegen m(x) � xi − 1 ist r(x) = 0. Daraus folgt

αi − 1 = p(α)m(α) + r(α) = r(α) .

Da m(x) irreduzibel ist, so ist es Minimalpolynom der Nullstelle α, das heißtr(α) = 0 wegen Grad r(x) < Grad m(x). Dies bedeutet aber αi = 1 fur0 < i < qm − 1, somit ist α primitives Element.

2. Sei α primitives Element, dann ist die Bahn

{α, αq, αq2

, . . . , αqm−1}

und das Minimalpolynom mα(x) =m−1∏i=0

(x − αqi) hat Grad m. �

Sei B = {α, αq, . . . , αqm−1} die Bahn des primitiven Elementes α. Dann bilden

{1, α, α2, . . . , αm−1} eine Basis von GF (qm) uber GF (q). Andernfalls gabe es

96

λi ∈ GF (q) mit∑m−1

i=0 λiαi = 0, das heißt das Polynom a(x) =

∑m−1i=0 λix

i

hatte α als Nullstelle, im Widerspruch zur Minimalitat von m.

Folgerung 7. Sei GF (q) ⊆ GF (qm), α primitives Element in GF (qm). Dannist

GF (qm) =

{m−1∑i=0

λiαi : λi ∈ GF (q)

}.

Beispiel. Sei GF (2) ⊆ GF (23), α primitives Element. Wir haben x7 − 1 =(x− 1)(x3 +x+1)(x3 +x2 +1). Sei o.B.d.A. x3 +x+1 das Minimalpolynomvon α. Fur die Multiplikation verwendet man die Darstellung GF (23) ={0, α, α2, α3, α4, α5, α6, α7 = 1} und fur die Addition GF (23) = {∑2

i=0 λiαi :

λi ∈ GF (2)} mit komponentenweiser Addition. Zum Beispiel ist (α2 +1)(α+1) = α3 + α2 + α + 1 = α2 wegen α3 + α + 1 = 0.

6.3 BCH-Codes.

Diese wichtige Klasse von Codes geht auf Bose, Ray Chaudhuri und Hoc-quenghem zuruck.

Wie ublich betrachten wir die Situation

• ggT(n, q) = 1

• GF (q) ⊆ GF (qm) mit n|qm − 1,

so dass xn − 1 in GF (qm) vollkommen zerfallt.

Satz 39. Sei GF (q) ⊆ GF (qm), g(x) normierter Teiler von xn − 1 inGF (q)[x] und α1, . . . , αr die Nullstellen von g(x) in GF (qm). Fur den zy-klischen Code C erzeugt von g(x) gilt:

c ∈ C ⇐⇒ c(α1) = c(α2) = . . . = c(αr) = 0 .

Beweis. Ist c ∈ C, so gilt g(x)|c(x) und somit c(αi) = 0 fur alle i. Hatumgekehrt c(x) die αi’s als Nullstellen, so haben wir g(x) = (x−α1) · · · (x−αr)|c(x), also c ∈ C. �

Die folgende Verallgemeinerung ist die Basis fur die BCH-Codes.

97

Satz 40. Sei GF (q) ⊆ GF (qm), und α1, α2, . . . , αs ∈ GF (qm) beliebig mitden Minimalpolynomen mi(x) ∈ GF (q)[x], und g(x) = kgV(m1(x), . . . , ms(x)).Es sei n so gewahlt, dass αni = 1 gilt fur alle i (z.B. n = qm − 1). Fur denzyklischen Code C ⊆ GF (q)n erzeugt von g(x) gilt dann

c ∈ C ⇐⇒ c(α1) = . . . = c(αs) = 0 .

Beweis. Wegen αni = 1 sehen wir mi(x)|xn − 1 fur alle i, und somit g(x) =kgV(m1(x), . . . , ms(x))|xn−1. Als Generatorpolynom erzeugt g(x) also einenzyklischen Code C ⊆ GF (q)n, und wegen mi(x)|g(x) gilt g(αi) = 0 fur alle i.

Ist c ∈ C, so haben wir g(x)|c(x) und somit c(αi) = 0 fur alle i. Umge-kehrt folgt aus c(αi) = 0 fur alle i, mi(x) | c(x) fur alle, und daraus g(x) =kgV(m1(x), . . . , ms(x))|c(x), also c ∈ C. �

Beispiel. Sei GF (2) ⊆ GF (2r), α primitives Element. Wir kennen das Mini-malpolynom von α, namlich mα(x) = (x−α)(x−α2)(x−α4) · · · (x−α2r−1

).Wir betrachten n = 2r − 1, und g(x) =

∏r−1i=0 (x − α2i

). Fur den von g(x)erzeugten zyklischen Code gilt

c ∈ C ⇐⇒ c(α) = 0 ⇐⇒n−1∑i=0

ciαi = 0 ,

wobei c = cn−1 . . . c1, c0.

Der Code C hat Lange n = 2r − 1, Dimension 2r − 1 − r, was ist d(C) ?

Behauptung: d(C ≥ 3 .Angenommen das Codewort c = cn−1 . . . c1c0 = 0 hat Gewicht w(c) ≤ 2. Wirhaben c(α) =

∑n−1i=0 ciα

i = 0. Falls w(c) = 1 ist, ci = 1, cj = 0 (j = i), dannhatten wir αi = 0, was nicht geht. Falls w(c) = 2 ist, ci = cj = 1, ck = 0(k = i, j), dann ware αi + αj = 0, also αi = αj oder αj−i = 1. Das geht abernicht, da α Primitivwurzel ist, also Ordnung n = 2r − 1 > j − i hat.

Wir erhalten somit einen [2r−1, 2r−1−r, 3; 2]-Code, also genau den binarenHamming Code Hr;2 (da die 1-perfekten Codes mit diesen Parametern ein-deutig sind). Die binaren (und analog die q-aren) Hamming Codes sind also

98

zyklische Codes.

Wir konnen auch den Weg uber die Kontrollmatrix gehen, um zu sehen, dasswir die Hamming Codes erhalten. Wir wissen, dass {1, α, α2, . . . , αr−1} eineBasis von GF (2r) uber GF (2) ist. Insbesondere ist

αj =

r−1∑i=0

ε(j)i αi fur 0 ≤ j ≤ n − 1 (n = 2r − 1)

mit ε(j)i ∈ GF (2) fur alle i und j, und die Vektoren (ε

(j)0 , . . . , ε

(j)r−1), 0 ≤ j ≤

n − 1, sind genau alle Vektoren = 0 in GF (2)r. Ersetzen wir αj durch die

Spalte (ε(j)0 , . . . , ε

(j)r−1)

T , so erhalten wir eine r × n-Matrix H

H =

⎛⎜⎜⎜⎝ε(n−1)0 . . . ε

(j)0 . . . ε

(0)0

ε(n−1)1 ε

(j)1 ε

(0)1

......

...

ε(n−1)r−1 ε

(j)r−1 ε

(0)r−1

⎞⎟⎟⎟⎠ .

Es gilt nun

c = cn−1 . . . c0 ∈ C ⇐⇒n−1∑j=0

cjαj = 0 .

Wir haben

n−1∑j=0

cjαj =

n−1∑j=0

cj

(r−1∑i=0

ε(j)i αi

)=

r−1∑i=0

(n−1∑j=0

ε(j)i cj

)αi ,

also

n−1∑j=0

cjαj = 0 ⇐⇒

n−1∑j=0

ε(j)i cj = 0 (i = 0, 1, . . . , r − 1)

⇐⇒ HcT = 0

da {1, α, . . . , αr−1} linear unabhangig uber GF (2) ist. Somit ist H Kontroll-matrix von C, deren Spalten genau alle n = 2r − 1 Vektoren = 0 in GF (2)r

sind, und dies war genau die Definition der Hamming Codes.

Wir kommen zur Definition der BCH-Codes. Wir betrachten xn−1, GF (q) ⊆GF (qm), und α eine primitive n-te Einheitswurzel, α ∈ GF (qm). Wir nehmen

99

δ − 1 aufeinanderfolgende Potenzen

αc, αc+1, . . . , αc+δ−2 (δ ≥ 2)

in GF (qm) mit den Minimalpolynomen mc(x), . . . , mc+δ−2(x). Sei weiter

g(x) = kgV(mc(x), . . . , mc+δ−2(x))

wobei naturlich g(x)|xn − 1 gilt.

Definition. Gegeben GF (q) ⊆ GF (qm), α, c, δ, g(x) = kgV(mc(x), mc+1(δ),. . . , mc+δ−2(x)). Jeder auf diese Weise konstruierte zyklische Code (mit Gene-ratorpolynom g(x)) heißt BCH-Code. Falls c = 1 ist, spricht man von einemBCH-Code im engeren Sinn.

Satz 41. Sei C ein BCH-Code erzeugt von g(x)|xn− 1 mit α, c, δ wie in derDefinition. Dann gilt

1) k = dim C ≥ n − m(δ − 1),

2) d(C) ≥ δ (δ heißt vorgegebener Abstand).

Beweis. 1) Aus g(x) = kgV(mc(x), mc+1(x), . . . , mc+δ−2(x)) folgt Grad g(x) ≤Grad (

∏δ−2i=0 mc+i(x)) =

∑δ−2i=0 Grad mc+i(x) ≤ m(δ − 1), da Grad mc+i(x) ≤

m ist nach Folgerung 6. Somit ist dim C = n − Grad g(x) ≥ n − m(δ − 1).

2) Wir wissen

a = an−1 . . . a0 ∈ C ⇐⇒ a(αc) = · · · = a(αc+δ−2) = 0 ,

das heißt

an−1((αc+i)n−1) + . . . + a1(a

c+i) + a0 = 0 fur i = 0, . . . , δ − 2 .

Aquivalent dazu haben wir in GF (qm) das Gleichungssystem⎛⎜⎜⎜⎝(αc)n−1 (ac)n−2 . . . αc 1

(αc+1)n−1 (αc+1)n−2 . . . αc+1 1...

(αc+δ−2)n−1 . . . αc+δ+2 1

⎞⎟⎟⎟⎠⎛⎜⎜⎜⎝

an−1

an−2...a0

⎞⎟⎟⎟⎠ =

⎛⎜⎜⎜⎝00...0

⎞⎟⎟⎟⎠ .

100

Sei nun a ∈ C mit w(a) ≤ δ − 1, d.h. wir haben Stellen n − 1 ≥ 1 > 2 >. . . > δ−1 ≥ 0 mit aj = 0 fur j ∈ {1, 2, . . . , δ−1}.Dies fuhrt zur Matrix H ′

H ′ =

⎛⎜⎜⎜⎝(αc)�1 (αc)�2 . . . (αc)�δ−1

(αc+1)�1 (αc+1)�2 . . . (αc+1)�δ−1

...(αc+δ−2)�1 . . . (αc+δ−2)�δ−1

⎞⎟⎟⎟⎠mit H ′a′T = 0, wobei a′ = a�1 . . . a�δ−1

ist.

Behauptung. a′ = 0, das heißt a = 0.Wir haben

det H ′ = (αc)�1(αc)�2 . . . (αc)�δ−1 det H ′′

mit

H ′′ =

⎛⎜⎜⎜⎜⎜⎝1 1 . . . 1

α�1 α�2 α�δ−1

(α�1)2 (α�2)2 (α�δ−1)2

......

...(α�1)δ−2 (α�2)δ−2 (α�δ−1)δ−2

⎞⎟⎟⎟⎟⎟⎠ .

H ′′ is Vandermonde Matrix mit det H ′′ =∏

1≤i<j≤δ−1

(α�j − α�i) = 0. Daraus

folgt a′ = 0. Jeder Vektor 0 = a ∈ C muß also Gewicht ≥ δ haben. �

Folgerung 8. Fur q = 2, n ungerade, gibt es fur jedes t < n2

einen BCH-Codemit Parametern [n, k, 2t+1; 2] mit k ≥ n−mt. C ist somit t-fehlerkorrigierend.

Beweis. Sei GF (2) ⊆ GF (2m) und α eine primitive n-te Einheitswurzel inGF (2m). Wir wahlen die 2t Potenzen α, α2, α3, α4, . . . , α2t−1, α2t. Offenbarsind αi und α2i in derselben Bahn, also mi(x) = m2i(x), i = 1, . . . , t, unddaher

g(x) = kgV(m1(x), m2(x), . . . , m2t(x))∣∣ m1(x)m3(x) · · ·m2t−1(x) .

101

Es folgt Grad g(x) ≤ mt und daraus dim C ≥ n − mt, und ferner d(C) ≥2t + 1. �

Beispiel 1. GF (2) ⊆ GF (24), n = 15. Sei α primitive 15-te Einheitswurzel.Wir kennen die Zerlegung

x15 − 1 = (x− 1)(x4 + x3 + 1)(x4 + x + 1)(x4 + x3 + x2 + x + 1)(x2 + x + 1) .

Das Minimalpolynom m1(x) von α sei o.B.d.A., m1(x) = x4 + x3 + 1; α3 istprimitive 5-te Einheitswurzel, also m3(x) = x4+x3+x2+x+1. Das Polynom

g(x) = m1(x)m3(x) = x8 + x4 + x2 + x + 1

hat die Nullstellen α, α2, α3, α4, α6, α8, α9, α12. Der zugehorige BCH-Code hatDimension k = 15 − 8 = 7 und d(C) ≥ 5, also d(C) = 5, da g(x) genau 5Koeffizienten = 0 hat.

Beispiel 2. Sei GF (211), α primitive 23-te Einheitswurzel. Wir haben dieBahnenzerlegung berechnet:

{α0 = 1},{α, α2, α3, α4, α6, α8, α9, α12, α13, α16, α18},{α5, α7, α10, α11, α14, α15, α17, α19, α20, α21, α22} .

Sei g(x) = m1(x) das Minimalpolynom von α. Der zugehorige BCH-Code Chat Dimension k = 23 − 11 = 12, d(C) ≥ 5. Wir wollen nun zeigen, dassd(C) ≥ 7 ist. Das heißt, C ist 3-perfekt (nach der Hamming Schranke) unddamit gleich dem Golay Code G23.

Dazu beweisen wir folgendes nutzliche Resultat. Sei S ⊆ GF (qm), dannkonstruieren wir eine Familie U(S) von Untermengen von GF (qm) mittelsder folgenden rekursiven Regeln:

(1) ∅ ∈ U(S) ,

(2) A ⊆ S, A ∈ U(S), b ∈ S ⇒ A ∪ {b} ∈ U(S) ,

(3) A ∈ U(S), s = 0 ⇒ sA ∈ U(S) .

Die Mengen aus U(S) heißen unabhangig bezuglich S.

102

Lemma 5. Sei c(x) ∈ GF (qm)[x], c(x) = 0, und S die Nullstellenmenge vonc(x) in GF (qm). Dann gilt

w(c) ≥ max(|A| : A ∈ U(S)) .

Beweis. Sei c = c1 . . . cn, w(c) = , ci1 = 0, . . . , ci� = 0, c(x) =∑�

j=1 cijxij .

Zu A ⊆ GF (qm) assoziieren wir die Vektorenmenge

IA = {(ai1 , . . . , ai�) ∈ GF (qm)� : a ∈ A}.

Behauptung: IA ist linear unabhangig fur alle A ∈ U(S). Dies ist rich-tig fur ∅ ∈ U(S), da I∅ = ∅ ist. Nun gehen wir induktiv vor. Sei IAlinear unabhangig fur A ⊆ S, A ∈ US und b ∈ S. Wir haben IA∪b =IA∪ (bii , . . . , bi�). Da IA nach Voraussetzung linear unabhangig ist, kann IA∪bnur linear abhangig sein, wenn (bi1 , . . . , bi�) linear abhangig von den Vektorenaus IA ist:

(bi1 , . . . , bi�) =∑a∈A

λa(ai1 , . . . , ai�) ,

das heißtbij =

∑a∈A

λaaij (j = 1, . . . , ) .

Daraus folgt

c(b) =�∑

j=1

cijbij =

�∑j=1

cij∑a∈A

λaaij =

∑a∈A

λa

�∑j=1

cijaij

=∑a∈A

λac(a) = 0 ,

da A ⊆ S ist, also jedes a ∈ A Nullstelle von c(x) ist. Daraus folgt aberc(b) = 0 im Widerspruch zu b ∈ S.

Zu (3) betrachten wir sA mit A ∈ U(S). Dann ist

IsA = {(sa)i1 , . . . , (sa)i� : a ∈ A},

103

das heißt, IsA ist Bild unter dem Isomorphismus von GF (qm)� auf sich, derdurch die Matrix ⎛⎜⎝ si1 0

. . .

0 si�

⎞⎟⎠induziert wird. Mit IA ist also auch IsA linear unabhangig. Insbesondere istfur alle A ∈ US

|A| = |IA| ≤ dim GF (qm)� = ,

woraus die Behauptung folgt. �

Nun betrachten wir nochmals den Code C ⊆ GF (2)23 aus Beispiel 2. Wirwissen bereits d(C) ≥ 5 und wollen mit dem Lemma d(C) ≥ 7 zeigen. JedesPolynom c(x) ∈ C(x) hat die Nullstellen {α, α2, . . . , α18} von m1(x). Hat c(x)auch eine Nullstelle aus der anderen Bahn der Lange 11 (und damit alle),dann ist c(x) = x22+x21+. . .+x+1, also w(c) = 23. Wenn c(x) die Nullstelle1 hat, das heißt

∑22i=0 ci = 0, so ist w(c) gerade und damit w(c) ≥ 6. Sollte

also c ∈ C mit w(c) = 5 existieren, so ist die Nullstellenmenge S von c(x)genau die Bahn {α, α2, α3, . . . , α18}. Wir konstruieren sukzessive Mengen ausU(S):

∅ ∈ U(S), ∅ ⊆ S2)

=⇒ {α5} ∈ U(S)

3)=⇒{α4} ∈ U(S), {α4} ⊆ S

2)=⇒ {α4, α5} ∈ U(S)

=⇒{α, α2} ∈ U(S) =⇒ {α, α2, α5} ∈ U(S)

=⇒{α8, α9, α12} ∈ U(S) =⇒ {α8, α9, α12, α14} ∈ U(S)

=⇒{α12, α13, α16, α18} ∈ U(S) =⇒ {α11, α12, α13, α16, α18} ∈ U(S)

=⇒{α, α2, α3, α6, α8} ∈ U(S) =⇒ {α, α2, α3, α5, α6, α8} ∈ U(S) ,

also w(c) ≥ 6 nach dem Lemm. Angenommen c′ ist Codewort mit w(c′) = 6,dann ist 1 Nullstelle von c′(x), also die Nullstellenmenge S ′ = S ∪ {α0}. Miteiner ahnlichen Konstruktion erhalt man eine Menge A ∈ U(S ′) mit |A| = 7,also insgesamt d(C) ≥ 7.Beispiel 3. Der ternare Golay Code G11 ist auch BCH-Code. Betrachten wirx11 − 1 ∈ GF (3). Wir haben 35 = 243 ≡ 1 (mod 11). Sei α eine primitive11-te Einheitswurzel, dann sind die Bahnen

{α0 = 1}, {α, α3, α9, α5, α4}, {α2, α6, α7, α10, α8} .

104

Das Polynom g(x) = m1(x) hat die Nullstellen {α, α3, α4, α5, α9}, erzeugtalso einen zyklischen Code C mit d(C) ≥ 4. Wir wollen d(C) = 5 zeigen,dann ist C wegen dim C = 6 2-perfekt und damit gleich G11. Die Zerlegungvon x11 − 1 ist

x11 − 1 = (x − 1)(x5 − x3 + x2 − x − 1)(x5 + x4 − x3 + x2 − 1),

es sei o.B.d.A. G(x) = x5 − x3 + x2 − x − 1. Die Generatormatrix ist daher

G =

⎛⎜⎜⎜⎜⎜⎜⎝

0 0 0 0 0 1 0 −1 1 −1 −10 0 0 0 1 0 −1 1 −1 −1 00 0 0 1 0 −1 1 −1 −1 0 00 0 1 0 −1 1 −1 −1 0 0 00 1 0 −1 1 −1 −1 0 0 0 01 0 −1 1 −1 −1 0 0 0 0 0

⎞⎟⎟⎟⎟⎟⎟⎠ .

Es ist leicht zu sehen, dass in G = (G|1) mit einer 1-Spalte am Ende alle Zei-len aufeinander senkrecht stehen. Der von G erzeugte Code C ist selbstdual.Daraus folgt w(c) ≡ 0 (mod 3) fur alle c ∈ C und daraus w(c) ≥ 6 (wegend(C) ≥ 4). Dies bedeutet aber umgekehrt w(c) ≥ 5 fur alle c ∈ C, was wirzeigen wollten.

Beispiel 4. Wir betrachten GF (q) und ein primitives Element α, n = q− 1.Das Minimalpolynom von αi ist naturlich mi(x) = x−αi. Fur ein beliebigesδ ≥ 2 erzeugt

g(x) = (x − α)(x − α2) · · · (x − αδ−1)

einen BCH-Code C mit den Parametern

Lange C = n, dim C = n − δ + 1, d(C) ≥ δ.

Wegen der Singleton Schranke dim C ≤ n − d(C) + 1, haben wir d(C) = δ,dim C = n − δ + 1, und C ist ein MDS-Code. Diese Codes heißen die Reed-Solomon Codes (im engeren Sinn). Wir konnen sofort eine Kontrollmatrixkonstruieren. Wir haben

c = cn−1 . . . c1c0 ∈ C ⇐⇒ c(α) = c(α2) = . . . = c(αδ−1) = 0 ,

das heißt⎛⎜⎜⎜⎝αn−1 αn−2 . . . α 1

(αn−1)2 (αn−2)2 . . . α2 1...

(αn−1)δ−1 (αn−2)δ−1 . . . αδ−1 1

⎞⎟⎟⎟⎠⎛⎜⎜⎜⎝

an−1

an−2...a0

⎞⎟⎟⎟⎠ =

⎛⎜⎜⎜⎝00...0

⎞⎟⎟⎟⎠ .

105

Die erste Zeile sind gerade alle Elemente = 0 aus GF (q) und die Kontrollma-trix H (vom Vandermonde Typ) ist also im wesentlichen genau die Matrix,die wir in Kapitel 5 fur die Reed-Solomon Codes verwendet haben.

Es gibt eine interessante Anwendung der Reed-Solomon Codes, die Korrekturvon “burst-errors”, das heißt, wenn mehrere Fehler hintereinander passieren.

Sei GF (2) ⊆ GF (28) und C der Reed-Solomon Code uber GF (28) mit n =255, d = 11, k = n − d + 1 = 245. C ist also 5-fehlerkorrigierend. JedesCodewort ist ein 255-Tupel c = c1 . . . c255 mit Eintragen in GF (28). Jedesci ∈ GF (28) kann in bezug auf eine Basis von GF (28) uber GF (2) als Wort

ci = c(1)i . . . c

(8)i ∈ GF (2)8 dargestellt werden. Das Gesamtwort

c = c(1)1 , . . . , c

(8)1 , c

(1)2 , . . . , c

(8)2 , . . . , c

(1)255, . . . , c

(8)255

hat somit Lange 255 · 8 = 2040 uber GF (2).

Passieren nun bis zu 33 aufeinanderfolgende Fehler in c, so liegen diese inhochstens 5 aufeinanderfolgenden 8er Blocken. Der ursprungliche Code Ckorrigiert diese Fehler, und damit ist der Error-burst in c korrigiert.

Decodierung von BCH-CodesWir betrachten als Beispiel den binaren Fall q = 2. Sei α eine primitive n-teEinheitswurzel mit Bahn {α, α2, α4, . . .}, α3 ∈ {α2i

: i ∈ N}. Das Genera-torpolynom g(x) = m1(x)m3(x) hat als Nullstellen α, α2, α3, α4 und erzeugtsomit einen BCH-Code C mit d(C) ≥ 5, also einen 2-fehlerkorrigierendenCode.

Angenommen, es wurde u(x) ∈ C(x) gesendet und v(x) = u(x) + e(x) emp-fangen; e(x) heißt das Fehlerpolynom. Wir setzen voraus, dass hochstens 2Fehler aufgetreten sind.

1. Berechnung der Syndrome:

S1 = v(α), S3 = v(α3).

Wir haben

S1 = v(α) = u(α) + e(α) = e(α)

S3 = v(α3) = u(α3) + e(α3) = e(α3) ,

106

mit

e(x) =

⎧⎨⎩0 kein Fehlerxe1 ein Fehlerxe1 + xe2 zwei Fehler.

Das Ziel ist, aus S1 und S3 die Fehlerstellen e1 und e2 zu berechnen.

2. Setze β1 = αe1, β2 = αe2 und weiter

σ(x) = (x − β1)(x − β2) = x2 + σ1x + σ2 ,

σ(x) heißt das Fehlerstellenpolynom.

3. Berechne die Nullstellen β1, β2 von σ(x) und ermittle e1, e2 aus β1 = αe1 ,β2 = αe2.

4. Decodiere v(x) −→ v(x) + e(x).

Folgende Falle konnen auftreten:

A. Kein Fehler: S1 = S3 = 0

Decodiere v(x)ψ−→ v(x).

B. Ein Fehler: e(x) = xe1 .

Dann ist S1 = αe1 = 0, S3 = (α3)e1 = S31 , also S3 = S3

1 mit σ(x) =

x + αe1 = x + S1. Decodiere v(x)ψ−→ v(x) + xe1 .

C. Zwei Fehler: e(x) = xe1 + xe2 .

Dann ist S1 = αe1 +αe2 = β1 +β2, S2 = β31 +β3

2 , σ1 = β1 +β2 = S1 = 0,σ2 = β1β2 = 0. Wir haben

S31 = (β1 + β2)

3 = β31 + β2

1β2 + β1β22 + β3

2

= S3 + (β1β2)S1 ,

also

σ2 =S3

1 + S3

S1.

Decodiere v(x)ψ−→ v(x) + xe1 + xe2 mit xe1 = β1, x

e2 = β2.

107

Decodierungsregel.

Berechne S1 und S3.

1. Falls S1 = S3 = 0, decodiere v(x)ψ−→ v(x).

2. Falls S1 = 0, S3 = 0, dann keine Decodierung (mehr als 2 Fehleraufgetreten).

3. Sei S1 = 0.

3a. Falls S3 = S31 , decodiere v(x)

ψ−→ v(x) + xe1 mit αe1 = S1.

3b. Falls S3 = S31 , setze σ1 = S1, σ2 =

S31+S3

S1, σ(x) = x2 + σ1x +

σ2. Wegen σ1 = 0 hat σ(x) entweder keine Nullstellen oder zweiverschiedene Nullstellen β1, β2. Im ersten Fall keine Decodierung

(mehr als 2 Fehler), im zweiten Fall decodiere v(x)ψ−→ v(x) +

xe1 + xe2 mit αe1 = β1, αe2 = β2.

Beispiel. Wir betrachten q = 2, n = 21 mit der irreduziblen Zerlegung

x21 − 1 =(x − 1)(x2 + x + 1)(x3 + x + 1)(x3 + x2 + 1)

(x6 + x4 + x3 + x + 1)(x6 + x5 + x4 + x2 + 1)

Sei α primitive 21-ste Einheitswurzel, wobei wir o.B.d.A. m1(x) = x6 + x4 +x2+x+1 wahlen. Der BCH-Code C erzeugt vom Polynom g(x) = m1(x)m3(x)hat Dimension 12 und d(C) ≥ 5. Das Polynom m3(x) ist entweder x3 +x+1oder x3 + x2 + 1. Da

(x6 + x4 + x2 + x + 1)(x3 + x + 1) = x9 + x6 + 1 (2)

ist, kann m3(x) nicht x3 + x + 1 sein, da ansonsten C ein Codewort vomGewicht 3 hatte. Also ist m3(x) = x3 + x2 + 1 und

g(x) = (x6 + x4 + x2 + x + 1)(x3 + x2 + 1) = x9 + x8 + x7 + x5 + x4 + x + 1 .

Wegeng(x)(x2 + x + 1) = x11 + x9 + x4 + x3 + 1 (3)

ist d(C) = 5.

Angenommen wir empfangen das Wort v in Polynomform

v(x) = x12 + x7 + x6 + x3 + 1.

108

Dann ist

S1 = v(α) = α12 + α7 + α6 + α3 + 1

S3 = v(α3) = α15 + 1 + α18 + α9 + 1 = α9(α9 + α6 + 1).

Aus (2) sehen wir α9 + α6 + 1 = 0, also

S1 = α12 + α7 + α9 + α3 = α7 + α3(α9 + α6 + 1) = α7,

S3 = 0.

Wir sind also im Fall 3b und berechnen

σ1 = S1 = α7, σ2 =S3

1 + S3

S1= S2

1 = α14,

σ(x) = x2 + α7x + α14.

Da α7 primitive 3-te Einheitswurzel ist, haben wir α14 +α7 +1 = 0, also sindβ1 = α0, β2 = α14 die Nullstellen von σ(x). Die Decodierung ist demnach

v(x)ψ−→ v(x) + x14 + x0 .

109