5 Lineare Codes

5.1 Grundbegriffe

Von nun an ist q stets eine Primzahlpotenz. Wir betrachten den (bis aufIsomorphie eindeutigen) Korper GF (q) mit q Elementen. Das Alphabet iststets GF (q).

Definition. Ein linearer Code C ist ein Unterraum des Vektorraumes GF (q)n.C ist ein [n, k, d; q]-Code, falls

C ⊆ GF (q)n, n = Lange

dim C = k, also |C| = qk ,

d(C) ≥ d .

Sei c = (c1, . . . , cn) ∈ GF (q)n, dann ist wie bisher w(c) = #{i : ci �= 0} dasGewicht von c. Sind u, v Codeworter des linearen Codes C, so gilt Δ(u, v) =w(u − v), wobei u − v ∈ C ist. Somit haben wir fur lineare Codes C

d(C) = min0�=v∈C

w(v) .

Lineare Codes sind die Codes, die in der Praxis verwendet werden. Sie konnenmit Hilfe einer Generatormatrix bzw. Kontrollmatrix bequem dargestellt wer-den.

Definition. G heißt Generatormatrix des [n, k, d; q]-Codes C, falls die Zeilenc1, . . . , ck von G eine Basis von C sind, also

G =

⎡⎢⎢⎢⎣

. . . c1 . . .

. . . c2 . . ....

. . . ck . . .

⎤⎥⎥⎥⎦ ,

G ist k × n-Matrix. Es gilt somit

c ∈ C ⇐⇒ c = λ1c1 + . . . + λkck, λi ∈ GF (q) .

Bemerkung. Ist B invertible k×k-Matrix, so ist BG ebenfalls Generatorma-trix, da biG ∈ C ist fur alle Zeilen b1, . . . , bk von B, und rk(BG) = r(G) = k

59

ist.

Definition. Ist C [n, k, d; q]-Code, so heißt der orthogonale Unterraum C⊥

der zu C duale Code. Es ist also

v ∈ C⊥ ⇐⇒ v · u = 0 fur alle u ∈ C .

wobei v ·u =∑n

i=1 viui das ubliche innere Produkt ist. Wir haben dim C⊥ =n − k.

Wegen der Linearitat ist

v ∈ C⊥ ⇐⇒ v · ci = 0 fur {c1, . . . , ck} Basis von C ,

das heißtv ∈ C⊥ ⇐⇒ GvT = 0 .

Definition. H heißt Kontrollmatrix von C, falls H Generatormatrix von C⊥

ist. H ist also eine (n − k) × n-Matrix mit

c ∈ C ⇐⇒ HcT = 0 .

Beispiel. Der Wiederholungscode ist linearer Code in GF (q)n mit Dimension= 1 und Generatormatrix G = (1 1 . . . 1). Sei q = 2, dann ist

H =

⎡⎢⎢⎢⎣

1 1 0 . . . 01 0 1 0 . . . 0... . . .1 0 0 . . . 1

⎤⎥⎥⎥⎦

Kontrollmatrix, rk(H) = n − 1, des Wiederholungscodes.

Satz 22. Sei G = [Ik|A] Generatormatrix des [n, k, d; q]-Codes, wobei Ik dieEinheitsmatrix der Ordnung k ist und A eine k × (n − k)-Matrix. Dann istH = [−AT |In−k] eine Kontrollmatrix von C.

Beweis. Wir mussen GHT = 0 zeigen. Wir haben

GHT = [Ik|A]

[ −A

In−k

]= −A + A = 0 .

60

Satz 23. Sei C ein [n, k, d; q]-Code und H eine Kontrollmatrix von C. Danngilt

d(C) ≥ d ⇐⇒ je d − 1 Spalten von H sind linear unabhangig.

Beweis. Es seien u1, u2, . . . , un die Spalten von H . Fur ein Codewort c =(c1, . . . , cn) ∈ C gilt HcT = 0, das heißt

c1u1 + . . . + cnun = 0 .

Angenommen, w(c) = m ≤ d − 1 mit ci1 �= 0, . . . , cim �= 0. Dann ist

ci1ui1 + . . . + cimuim = 0 ,

und die m ≤ d − 1 Spalten ui1 , . . . , uim sind linear abhangig. Nehmen wirumgekehrt an, dass uj1, . . . , ujm linear abhangig sind mit m ≤ d − 1. Danngibt es cj1, . . . , cjm, nicht alle = 0, mit

cj1uj1 + . . . + cjmujm = 0 ,

und wir erhalten ein Codewort c = (0 . . . cj1, . . . , cjm, . . . 0) ∈ C mit Gewichtm ≤ d − 1. Die Kontraposition ergibt die Aussage des Satzes. �

Beispiel. Der Satz gibt eine konkrete Methode an, um Codes mit vorge-gebener Distanz zu konstruieren. Der erste interessante Fall ist d = 3. Um[n, k, 3; q]-Codes zu erhalten, benotigen wir eine Kontrollmatrix mit r = n−kZeilen und n Spalten, so dass je zwei Spalten linear unabhangig sind. JedeSpalte ist ein Vektor �= 0 aus GF (q)r. Ist u �= 0 ein solcher Vektor, so sindgenau die Vielfachen λu linear abhangig. Die Maximalzahl der Spalten inGF (q)r, von denen je zwei linear unabhangig sind, ist demnach

n =qr − 1

q − 1.

Definition. Ein Hamming Code Hr;q uber GF (q) ist [n, k, 3; q]-Code miteiner Kontrollmatrix wie eben konstruiert:

n =qr − 1

q − 1, k =

qr − 1

q − 1− r, (r ≥ 2).

61

Satz 24. Jeder Hamming Code Hr;q uber GF (q) ist 1-perfekt.

Beweis. Die Hamming Schranke fur d(C) = 3 ist

|C| ≤ qn

1 + n(q − 1).

Fur Hr;q haben wir wegen n = qr−1q−1∣∣Hr;q

∣∣ = qk =qn

qr=

qn

1 + n(q − 1),

als ist Hr;q 1-perfekt. �

Beispiel. Sei q = 2. Fur r = 2 erhalten wir n = 3, k = 1, also den Wieder-

holungscode C = {000, 111} mit Kontrollmatrix H =

[1 0 10 1 1

]. Fur r = 3

ist die Kontrollmatrix

H =

⎡⎣ 1 0 0 1 1 0 1

0 1 0 1 0 1 10 0 1 0 1 1 1

⎤⎦

und nach obigem Satz

G =

⎡⎢⎢⎣

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

⎤⎥⎥⎦

eine Generatormatrix. Der so erhaltene Hamming Cod H3;2 ist naturlich ge-nau der im vorigen Kapitel konstruierte Fano Code.

Bemerkungen. Die folgenden Operationen erhalten die Linearitat von Co-des:

1. Permutation der Spalten (die Parameter n, k, d bleiben erhalten),

2. Multiplikation einer Spalte mit einem Element �= 0 (die Parameterbleiben erhalten),

3. Verkurzung.

62

5.2 Schranken fur lineare Codes

Gegeben n, d und eine Primzahlpotenz q, so setzen wir

Aq(n, d) = max(|C| : C ⊆ GF (q)n linear mit d(C) ≥ d).

Es gilt also stets Aq(n, d) ≤ Mq(n, d).

Beispiel. Wir wissen M2(12, 6) = 24 (da eine Hadamard Matrix der Ordnung12 existiert), aber naturlich ist A2(12, 6) < 24, da A2(n, d) eine 2-Potenz seinmuß. Allgemein ist Aq(n, d) = qk, wobei k die Dimension eines optimalenCodes ist.

Satz 25 (Singleton Schranke). Wenn ein [n, k, d; q]-Code C existiert, so giltk ≤ n − d + 1. Ist Gleichheit erfullt, so heißt C linearer MDS-Code.

Beweis. Wir wissen Mq(n, d) ≤ qn−d+1 und somit |C| = qk ≤ qn−d+1, alsok ≤ n−d+1. Ein zweiter Beweis folgt aus Satz 23. Die Kontrollmatrix H isteine (n − k) × n-Matrix, in der je d − 1 Spalten linear unabhangig sind, dasheißt rk(H) ≥ d − 1. Da rk(H) hochstens die Anzahl der Zeilen sein kann,folgt d − 1 ≤ n − k. �

Wir konnen diese Schranke folgendermaßen verscharfen. In Aq(n, d) gebenwir n und d vor und suchen das maximale k, so dass ein [n, k, d; q]-Codeexistiert. Alternativ geben wir k und d vor und suchen das minimale n, sodass ein [n, k, d; q]-Code existiert. Es sei Nq(k, d) diese minimale Lange n.

Lemma 2. Es gilt Nq(1, d) = d und

Nq(k, d) ≥ d + N(k − 1, d

q) (k ≥ 2).

Beweis. Der Wiederholungscode der Lange d gibt Nq(1, d) = d. Es sei C ein[Nq(k, d), k, d; q]-Code mit der Generatormatrix G. Aus der Minimalitat vonNq(k, d) folgt, dass es ein Codewort vom Gewicht d gibt, da wir ansonstenden Code verkurzen konnten. Nach den Bemerkungen am Ende des vorigen

63

Abschnittes konnen wir G von der Form

G =

⎛⎜⎜⎜⎜⎜⎜⎝

0 . . . 0

d︷ ︸︸ ︷1 . . . 1

G1 G2

⎞⎟⎟⎟⎟⎟⎟⎠

annehmen. Es seien c1, c2, . . . , ck die Zeilen von G. Wir setzen ci = (ui|vi),wobei ui das Wort in G1 und vi in G2 ist. �

Behauptung. rk(G1) = k − 1.

Angenommen, dies ist falsch, dann sind die Zeilen u2, . . . , uk von G1 linearabhangig, das heißt λ2u2 + · · · + λkuk = 0, nicht alle λi = 0. Daraus folgtc = λ2c2 + · · · + λkck = (0 . . . 0, y1 . . . yd) ∈ C, c �= 0 (da die ci linearunabhangig sind). Wegen d(C) = d sind alle yi �= 0 und nicht alle gleich einemfesten y, da ansonsten c = yc1 ware. Es sei y1 �= y2, dann ist c′ = c−y1c1 ∈ C,c′ �= 0 und w(c′) < d, im Widerspruch zu d(C) = d.

Die Matrix G1 erzeugt also einen [Nq(k, d) − d, k − 1, d1; q]-Code C1 mitd(C1) = d1. Es sei u = λ2u2 + · · · + λkuk ∈ C von minimalem Gewicht d1,und c = (u|v) = λ2c2 + · · ·+ λkck. Jedes Wort yc1 = (0 . . . 0 y . . . y) ∈ C hatAbstand ≥ d von c, das heißt Δ((y . . . y), v) ≥ d − d1. Mit anderen Wortenjedes y ∈ GF (q) kommt in v hochstens d1 Mal vor. Da v Lange d hat, folgtd ≤ qd1 oder d1 ≥ d

q, das heißt d1 ≥ d

q. Aus der Definition von Nq(k, d)

erhalten wir somit

Nq(k − 1, d

q) ≤ Nq(k − 1, d1) ≤ Nq(k, d) − d . �

Iteration zusammen mit 1q dqi−1 ≥ d

qi liefert die folgende Schranke.

Satz 26 (Griesmer Schranke). Wir haben

Nq(k, d) ≥ d + d

q + d

q2 + · · ·+ d

qk−1 .

64

Beispiel. Sei n = 16, d = 8, q = 2. Die Singleton Schranke ergibt k ≤16 − 8 + 1 = 9, wahrend Griesmer besagt

16 = 8 + 8

2 + 8

22 + 8

23 + 8

24.

also ist ein [16, 5, 8; 2]-Code moglich, aber k = 6 nicht mehr. Wir wissenM2(16, 8) = 32 = 25 mit der Hadamard Konstruktion, aber die HadamardCodes sind nicht linear. Die folgende Konstruktion ergibt einen [16, 5, 8; 2]-Code, also A2(16, 8) = 32.

Es seien C1, C2 ⊆ {0, 1}n, |C1| = M1, |C2| = M2 beliebige Codes mit d(C1) =d1, d(C2) = d2. Wir definieren den Code C = C1 ∗C2 durch {(u, u + v) : u ∈C1, v ∈ C2}. C ist ein Code der Lange n, und es gilt

a. |C| = |C1||C2|,b. d(C) = min(2d1, d2).

Ferner ist C linear, falls C1 und C2 linear sind.

Die Reed-Muller Codes C(r, m) werden rekursiv definiert. Es ist C(0, m) ={00 . . . 0, 11 . . . 1}2m

, C(m, m) = {0, 1}2mund fur 0 ≤ r ≤ m ist

C(r + 1, m + 1) = C(r + 1, m) ∗ C(r, m).

Man pruft leicht nach, dass C(r, m) linearer Code ist mit Lange n = 2m,Dimension k =

∑ri=0

(mi

)und Distanz 2m−r.

Fur m = 4, r = 1 ist C(4, 1) ein [16, 5, 8; 2]-Code.

Beispiel. n = 12, d = 5, q = 2. Die Griesmer Schranke ergibt 12 = 5+52+

522 + 5

23 + 524 , also k ≤ 5. Die Plotkin Schranke fur beliebige Codes war

M2(12, 5) ≤ 48. Nach Griesmer ist theoretisch ein [12, k = 5, d = 5; 2]-CodeC mit |C| = 32 moglich, aber es kann gezeigt werden, dass A2(12, 5) = 16ist, wahrend M2(12, 5) = 32 ist.

Auch die untere Schranke laßt sich auf lineare Codes ubertragen. Die Gilbert-Varshamov Schranke besagte

Mq(n, d) ≥ qn∑d−1i=0

(ni

)(q − 1)i

.

65

Wenn alsoqn∑d−1

i=0

(ni

)(q − 1)i

≥ qk

oder aquivalentd−1∑i=0

(n

i

)(q − 1)i ≤ qn−k

gilt, so existiert ein (n, d, q)-Code C mit |C| = qk. Eine geringfugige Ab-schwachung reicht schon fur die Existenz eines linearen Codes aus.

Satz 27 (Gilbert-Varshamov Schranke fur lineare Codes). Wenn

d−2∑i=0

(n − 1

i

)(q − 1)i < qn−k

gilt, so existiert ein [n, k, d; q]-Code C (d ≥ 2).

Beweis. Wir mussen eine (n − k) × n-Matrix konstruieren, so dass je d − 1Spalten linear unabhangig sind. Wir beginnen mit einem beliebigen Vektoru1 �= 0 aus GF (q)n−k als erster Spalte. Angenommen wir haben bereits m <n Spalten u1, . . . , um konstruiert, so dass je d − 1 linear unabhangig sind.Nicht in Frage als nachste Spalte kommen (klassifiziert nach der Lange derLinearkombination)

1 + m(q − 1) +

(m

2

)(q − 1)2 + . . . +

(m

d − 2

)(q − 1)d−2 .

Wegen m < n ist m ≤ n − 1, also ist diese Summe kleiner als qn−k nachVoraussetzung und es existiert ein Vektor v = um+1 ∈ GF (q)n−k, den wirhinzufugen konnen. �

Beispiel. n = 13, d = 5, q = 2. Wir haben

3∑i=0

(12

i

)= 1 + 12 + 66 + 220 = 299 < 29 = 213−4 .

Somit existiert ein [13, 4, 5; 2]-Code, A2(13, 5) ≥ 16.

66

5.3 Codierung und Decodierung von linearen Codes

Sei C ⊆ GF (q)n linearer Code der Dimension k und

G =

⎛⎜⎜⎜⎝

. . . c1 . . .

. . . c2 . . ....

. . . ck . . .

⎞⎟⎟⎟⎠

eine k × n-Generatormatrix, also C = {λ1c1 + . . . + λkck : λi ∈ GF (q)}.

Wir fassen die Nachrichten als Worter der Lange k aus GF (q)k, u = (λ1, . . . , λk),auf.

Die Codierung ist uϕ−→ uG

u −→ λ1c1 + . . . + λkck ∈ C .

In der Praxis wird der Nachrichtenstrom in Blocke der Lange k zerlegt

x = x1 . . . xk︸ ︷︷ ︸x(1)

∣∣x k+1 . . . x2k︸ ︷︷ ︸x(2)

∣∣x 2k+1 . . . x3k︸ ︷︷ ︸x(3)

∣∣ . . .und in entsprechende Codeworter der Lange n

xϕ−→ x(1)G

∣∣x(2)G∣∣x(3)G

∣∣ . . .codiert. Die Rate ist k log q

n.

Der wichtigste Fall ist, wenn G von der Form G = [Ik|A] ist. Wir haben dann

uϕ−→ uG = ( u︸︷︷︸

k

, uA︸︷︷︸r=n−k

).

Die ersten k Symbole sind die Informationssymbole, die restlichen r = n− kdie Kontrollsymbole, r heißt die Redundanz. Man spricht dann von einersystematischen Codierung.

Beispiel. Der Paritatscode uber GF (2) hat die Generatormatrix

G =

⎛⎜⎜⎜⎜⎝

1 1

10

1. . .

...0

1 1

⎞⎟⎟⎟⎟⎠

67

mit der Codierung

u = (λ1, . . . , λk)ϕ−→ (λ1, . . . , λk,

k∑i=1

λi) .

Nun zur Decodierung. Wir verwenden die Hamming Decodierung: Wird y ∈GF (q)n empfangen, so decodiere y zu einem Codewort c mit minimalemAbstand von y, das heißt Gewicht w(y−c) = min. Die moglichen Fehlerwortere = y − c, c ∈ C, ergeben die Nebenklasse y − C der Untergruppe C+ inGF (q)n+. Hat C Dimension k, so gibt es qn−k Nebenklassen.

Praxis I. Stelle eine Liste der Nebenklassen von C zusammen mit einer Listeder Worter von minimalem Gewicht aus den jeweiligen Nebenklassen. Fallsmehrere existieren, wahle eines. Diese Worter heißen die Nebenklassenfuhrer.

Nebenklassen Nebenklassenfuhrer

Cy − Cz − Cv − C

...

0efg...

w(e) = min in y − Cw(f) = min in z − Cw(g) = min in v − C

Algorithmus: Es wird y empfangen.

1. Man sieht nach, in welcher Nebenklasse y liegt.

2. Decodiere yψ−→ y− e, e Nebenklassenfuhrer in der Nebenklasse y−C.

Zur praktischen Durchfuhrung des Algorithmus verwendet man eine Kon-trollmatrix.

Hilfssatz. Sei H Kontrollmatrix von C. Dann liegen y1, y2 genau dann inderselben Nebenklasse von C, wenn HyT1 = HyT2 gilt.

Beweis. Die Worter y1, y2 liegen genau dann in derselben Nebenklasse, wenn

y1 − y2 = c ∈ C ⇔ H(yT1 − yT2 ) = 0 ⇔ HyT1 = HyT2 . �

68

Es genugt also, HyT zu berechnen. Wird y empfangen, so heißt HyT dasSyndrom von y. Es gibt qn−k Syndrome.

Praxis II. Stelle eine Liste der Syndrome auf, zusammen mit den jeweiligenNebenklassenfuhrern.

Syndrome Nebenklassenfuhrer

n − k

⎧⎪⎪⎪⎨⎪⎪⎪⎩

⎛⎜⎜⎜⎝

00...0

⎞⎟⎟⎟⎠ 0 0 . . . 0︸ ︷︷ ︸

n

n − k

⎧⎪⎪⎪⎨⎪⎪⎪⎩

⎛⎜⎜⎜⎝

10...0

⎞⎟⎟⎟⎠ e mit HeT =

⎛⎜⎜⎜⎝

10...0

⎞⎟⎟⎟⎠, w(e) = min

......

Algorithmus: Es werde y empfangen.

1. Berechne das Syndrom HyT , mit Nebenklassenfuhrer e,

2. Decodiere yψ−→ y − e .

Beispiel. q = 2. H =

(1 0 1 10 1 0 1

), n = 4, k = 2.

Syndrome Nebenklassenfuhrer(00

)0 0 0 0(

10

)1 0 0 0(

01

)0 1 0 0(

11

)0 0 0 1

69

Angenommen, es wird y = 1111 empfangen. Dann ist HyT =(10

), also wird

y zu y − 1000 = 0111 ∈ C decodiert. Wir hatten auch 0010 als Nebenklas-senfuhrer mit Syndrom

(10

)wahlen konnen. Man sieht also, dass C einen

Fehler erkennen kann, aber im allgemeinen nicht korrigieren.

Allgemein erkennen wir, dass t-fehlerkorrigierend bedeutet, dass die Wortervom Gewicht ≤ t verschiedene Syndrome haben mussen, also Nebenklas-senfuhrer verschiedener Nebenklassen sind. Da es qn−k Syndrome gibt, folgtdaraus sofort die Hamming Schranke

∑ti=0

(ni

)(q − 1)i ≤ qn−k.

Beispiel. Betrachten wir den 1-perfekten Hamming Code H3;2 mit n = 7,k = 3, q = 2 und Kontrollmatrix

H =

⎛⎝1 0 0 1 1 0 1

0 1 0 1 0 1 10 0 1 0 1 1 1

⎞⎠ .

Zu jedem Syndrom s ∈ GF (2)3 gehort genau ein Nebenklassenfuhrer vom

Gewicht ≤ 1. Zu s0 =

⎛⎝0

00

⎞⎠ gehort 0000000 und zu sj = j-te Spalte von H

offenbar 0 0 . . . 1 0 . . . 0 mit 1 an j-ter Stelle. Wir haben somit den Algorith-mus:

1. Berechne HyT = sj .

2. Ist j = 0, so ist y ∈ H3;2,

ist j > 0, so decodiere y zu y + (00.

j↓1.0).

Wird zum Beispiel y = 1110011 empfangen, so ist HyT =

⎛⎝0

11

⎞⎠

↑6.Spalte

und yψ−→

1110001.

70

5.4 Gewichtsverteilung und der Satz von MacWilliams

Ist C ⊆ An ein beliebiger Code uber dem Alphabet A, so interessieren wiruns fur die Gewichtsverteilung der Codeworter:

Ai = #{c ∈ C : w(c) = i}, i = 0, 1, . . . , n .

Ist insbesondere C ⊆ GF (q)n linear, so ist d(C) = min(i > 0 : Ai �= 0).

Definition. Das Polynom WC(x, y) =∑n

i=0 Aixn−iyi ist das (homogene)

Gewichtspolynom von C.

Beispiel. Der Hamming Code H3;2 hat

WH3;2(x, y) = x7 + 7x4y3 + 7x3y4 + y7 ,

und der Code H3;2 (mit Paritatscheck)

WH3;2(x, y) = x8 + 14x4y4 + y8 .

Ein wichtiger Satz stellt eine Verbindung zwischen den Gewichtspolynomenvon C und C⊥ her. Dazu benotigen wir einige Vorbereitungen.

Sei G eine endliche abelsche Gruppe, additiv geschrieben, und S1 die multi-plikative Gruppe der komplexen Zahlen vom Betrag 1, also S1 = {eix : 0 ≤x ≤ 2π} mit eix · eiy = ei(x+y).

Definition. Ein Charakter χ von G ist ein Homomorphismus χ : (G, +) −→(S1, ·), also χ(0) = 1, χ(g + h) = χ(g)χ(h).

Der Charakter χ0, der alles auf 1 abbildet, heißt der triviale Charakter. DieCharaktere bilden mit Multiplikation (χχ′)(g) = χ(g)χ′(g) eine Gruppe, mitχ0 als neutralem Element.

Es sei |G| = n, dann gilt ng = 0 fur alle g ∈ G, und somit χ(ng) = χ(g)n =1 fur alle g. Die Bilder unter χ sind also n-te Einheitswurzeln, das heißtNullstellen der Gleichung xn = 1. Die Gruppe G der Charaktere ist somitendlich.

71

Lemma 3. Sei χ Charakter von G. Dann gilt∑g∈G

χ(g) =

{ |G| χ = χ0

0 χ �= χ0 .

Beweis. Fur χ = χ0 ist χ0(g) = 1 fur alle g ∈ G, und somit∑

g∈G χ(g) = |G|.Sei nun χ �= χ0, z.B. χ(h) �= 1. Dann ist

χ(h)∑g∈G

χ(g) =∑g∈G

χ(h)χ(g) =∑g∈G

χ(h + g) =∑g∈G

χ(g),

da h+g mit g wieder ganz G durchlauft. Wegen χ(h) �= 1, folgt∑

g∈G χ(g) =0. �

Frage. Existiert immer ein nichttrivialer Charakter, sofern |G| ≥ 2 ist. DieAntwort ist ja, die Gruppe der Charaktere ist stets isomorph zu G.

Fur den uns interessierenden Fall G = GF (q)+ konnen wir das direkt sehen.Es sei q = pm, dann ist GF (q) ein Vektorraum der Dimension m uber demPrimkorper Zp = {0, 1, . . . , p − 1}. Sei {1, α2, α3, . . . , αm} eine Basis. Furα = λ1 · 1 + λ2α2 + · · ·+ λmαm, λi ∈ Zp, definieren wir

χ(α) = ζλ1 , ζ = e2πip primitive p-te Einheitswurzel.

Wegen χ(α + β) = ζλ1+μ1 = ζλ1ζμ1 = χ(α)χ(β) und χ(1) = ζ �= 1 ist χ einnichttrivialer Charakter.

Beispiel. GF (4) = {0, 1, α, 1 + α}. Der oben konstruierte Charakter ist

χ :

0 −→ 11 −→ −1α −→ 1

1 + α −→ −1

Als zweite Vorbereitung benotigen wir eine Summenumkehrformel. Sei χ einnichttrivialer Charakter von K+ = GF (q)+ und f : Kn −→ I eine beliebigeAbbildung von Kn in einen Integritatsbereich.

Definition. Die Hadamard Transformierte von f ist f : Kn −→ I mit

f(u) =∑v∈Kn

χ(u · v)f(v) (u ∈ Kn) ,

72

wobei u · v =∑n

i=1 uivi das Skalarprodukt in Kn ist, und χ ein fester nicht-trivialer Charakter von GF (q)+.

Lemma 4. Sei C ⊆ Kn ein linearer Code, f : Kn −→ I, dann gilt

∑v∈C⊥

f(v) =1

|C|∑u∈C

f(u) .

Beweis. Wir haben∑u∈C

f(u) =∑u∈C

∑v∈Kn

χ(u · v)f(v)

=∑v∈Kn

f(v)∑u∈C

χ(u · v).

Falls v ∈ C⊥ ist, so ist u · v = 0 fur alle u ∈ C, somit χ(u · v) = 1, also istdie innere Summe gleich |C|.

Sei v �∈ C⊥, dann ist C �⊆ 〈v〉⊥ und somit C ∩ 〈v〉⊥ ⊆ C ein (k − 1)-dimensionaler Unterraum von C, k = dim C. Die Gruppe C+ zerfallt in

|C||C∩〈v〉⊥| = q Nebenklassen. Zwei Codeworter u1, u2 sind in derselben Neben-klasse genau dann, wenn

u1 − u2 ∈ C ∩ 〈v〉⊥ ⇐⇒ (u1 − u2) · v = 0 ⇐⇒ u1 · v = u2 · v .

Jede Nebenklasse wird also durch ein Element λ ∈ K, u ·v = λ reprasentiert.Es folgt

#{u ∈ C : u · v = λ} = qk−1 fur alle λ ∈ K ,

und somit fur die innere Summe

qk−1∑λ∈K

χ(λ) = 0

nach Lemma 3. �

Satz von MacWilliams. Es sei C ⊆ GF (q)n linearer Code. Dann gilt

WC⊥(x, y) =1

|C|WC(x + (q − 1)y, x− y).

73

Beweis. Die Behauptung ist aquivalent zu

∑v∈C⊥

xn−w(v)yw(v) =1

|C|∑u∈C

(x + (q − 1)y)n−w(u)(x − y)w(u) .

Wir betrachten die Funktion f : GF (q)n −→ GF (q)[x, y], f(u) = xn−w(u)yw(u).Nach Lemma 4 bleibt zu zeigen, dass

f(u) = (x + (q − 1)y)n−w(u)(x − y)w(u)

gilt. Wir setzen wieder K = GF (q), u = u1 . . . un, v = v1 . . . vn und haben

f(u) =∑v∈Kn

χ(u · v)xn−w(v)yw(v)

=∑v∈Kn

χ(u1v1 + · · · + unvn)xn−w(v)yw(v)

=∑v∈Kn

n∏i=1

χ(uivi)x1−viyvi

wobei vi = 1 fur vi �= 0, vi = 0 fur vi = 0 ist. Der letzte Ausdruck ist

=∑v1∈K

. . .∑vn∈K

n∏i=1

χ(uivi)x1−bviybvi

=

n∏i=1

∑a∈K

χ(uia)x1−bayba . (1)

Fur ui = 0 ist die innere Summe∑a∈K

χ(0)x1−bayba = x + (q − 1)y .

Fur ui �= 0 durchlauft uia den Korper K, und es gilt uia = a. Die innereSumme ist daher ∑

a∈Kχ(a)x1−bayba = x +

∑a�=0

χ(a)y = x − y ,

74

da nach Lemma 3 ∑a∈K,a�=0

χ(a) = −χ(0) = −1

ist. Fur das Produkt (1) erhalten wir somit

f(u) = (x + (q − 1)y)n−w(u)(x − y)w(u)

wie behauptet. �

Folgerung. Fur einen selbstdualen Code C = C⊥ gilt

WC(x, y) =1

qn/2WC(x + (q − 1)y, x− y).

Beispiel. Der erweiterte Hamming Code H3;2 ist selbstdual, also gilt

WH3;2(x, y) =

1

16WH3;2

(x + y, x − y) .

5.5 Golay Codes

Neben Shannon und Hamming war Golay ein Pionier der Codierungstheorie.Nach ihm sind zwei beruhmte perfekte Codes benannt.

Ein Code C ⊆ An, |A| = q, heißt bekanntlich t-perfekt, falls

|C| =qn∑t

i=0

(ni

)(q − 1)i

gilt. Wir betrachten lineare perfekte Codes, also |C| = qk, k = dim C.

Fur t = 1 haben wir unendlich viele 1-perfekte Codes, die Hamming Codes,konstruiert.

t = 2: Fur q = 2 haben wir die Existenz bereits ausgeschlossen. Fur q = 3

75

muß gelten

1 + 2n + 4

(n

2

)= 3n−k

⇐⇒ 1 + 2n + 2n2 − 2n = 3n−k

⇐⇒ 2n2 + 1 = 3n−k ,

und wegen t ≥ 2 ist n ≥ 5. Aus der Zahlentheorie weiß man, dass die Glei-chung 2n2 +1 = 3s nur die Losung n = 11, s = 5 hat (2 ·121+1 = 243 = 35).Es konnte also ein 2-perfekter [n = 11, k = 6, d = 5; q = 3]-Code existieren.

t = 3: Fur q = 2 erhalten wir die Gleichung

1 + n +

(n

2

)+

(n

3

)= 2n−k, n ≥ 7,

und man sieht leicht, dass die einzigen Losungen n = 7, k = 1 und n = 23,k = 12 sind. Im ersten Fall haben wir den Wiederholungscode.

Wir wollen nun zeigen, dass tatsachlich ein 2-perfekter [11, 6, 5; 3]-Code G11

und ein 3-perfekter [23, 12, 7; 2]-Code G23 existiert, und dies sind die GolayCodes.

Satz 28 (Tietavainen, van Lint). Außer den Wiederholungscodes (n unge-rade, q = 2), den Hamming und Golay Codes gibt es keine weiteren linearenperfekten Codes.

Konstruktion der Codes G11 und G12.

Es sei GF (3) = {0, 1,−1}. Die folgende 6 × 11-Generatormatrix G erzeugtG11 und die Matrix G = G+ Paritatsspalte den Code G12:

G =

⎛⎜⎜⎜⎜⎜⎜⎝

1 0 1 −1 −1 1 11 1 0 1 −1 −1 −1

1 −1 1 0 1 −1 −11 −1 −1 1 0 1 −1

1 1 −1 −1 1 0 −11 1 1 1 1 1 0

⎞⎟⎟⎟⎟⎟⎟⎠

0

0

↑fur G

76

Die Zeilen von G seien c1, . . . , c6 bzw. c1, . . . , c6 fur G.

Offenbar ist dim G11 = dim G12 = 6. Wenn wir zeigen konnen, dass d(G12) =6 ist, so folgt d(G11) = 5, und G11 ist 2-perfekt.

Behauptung. G12 ist selbstdual, G⊥12 = G12.

Man pruft direkt nach, dass ci · cj = 0 fur alle i und j gilt. Daraus folgtG12 ⊆ G⊥

12 und somit G12 = G⊥12 wegen dim G12 = 6 = n

2(n = 12).

Fur c = (λ1 . . . λ12) ∈ G12 ist c · c =∑12

i=1 λ2i = w(c) und somit w(c) ≡ 0

(mod 3) wegen c · c = 0 in GF (3). Es bleibt also zu zeigen, dass w(c) = 3nicht moglich ist.

Wenn c ∈ G12 Linearkombination von ≥ 4 Zeilen ci ist, so folgt (wegen derEinheitsmatrix I6) w(c) ≥ 4. Wenn c = ci ist, so gilt w(c) = 6. Wenn c ∈ G12

Linearkombination von zwei oder drei Zeilen ist, so sieht man ebenfalls sofortw(c) > 3. Es folgt d(G12) = 6 und somit d(G11) = 5.

Wir wollen nun die Gewichtsverteilung von G11 bestimmen. Wir haben |G11| =36 = 729. Die Koeffizienten sind A0 = 1, A1 = A2 = A3 = A4 = 0. Was istA5? Da G11 2-perfekt ist, liegt jedes Wort vom Gewicht 3 in genau einerKugel um ein Codewort vom Gewicht 5, und wir erhalten(

11

3

)23 = A5 · 10 ,

also A5 = 132.

Zur Bestimmung von A6 gehen wir analog vor. Jedes Wort vom Gewicht 4liegt in genau einer Kugel um ein Codewort vom Gewicht 5 oder 6. Darausfolgt (

11

4

)24 = A5 · 25 + A6 · 15 ,

also A6 = 132. Die Folge der Gewichtskoeffizienten ist fur G11 schließlich

A0 = 1, A5 = A6 = 132, A8 = 330, A9 = 110, A11 = 24

77

und fur G12

A0 = 1, A6 = 264, A9 = 440, A12 = 24 .

Wir konnen aus G11 und G12 Steiner Systeme konstruieren. Wir betrachtendie 132 Codeworter in G11 vom Gewicht 5, und X = {1, 2, . . . , 11} die Koor-dinatenstellen. Der Trager von c ∈ G11 ist B(c) = {i ∈ X : ci �= 0}. Mit c hatauch −c Gewicht 5 mit B(c) = B(−c). Fur jedes andere Codewort c′ vomGewicht 5 gilt B(c′) �= B(c) wegen Δ(c, c′) ≥ 5. Wir haben also 132

2= 66

verschiedene Trager, die wir nun als Blocke (der Große 5) in X = {1, . . . , 11}auffassen. Es sei nun D ⊆ X mit |D| = 4. Angenommen D ist in zwei BlockenB = B(c) und B′ = B(c′) enthalten. Dies bedeutet fur G11 die Existenz vonc, c′ vom Gewicht 5 mit

c = 0 . . . 0a1 · a2 · a3 · a4 . . . b..0 · · · , ai �= 0, b �= 0

c′ = 0 . . . 0a′1 · a′

2 · a′3 · a′

4 . . . 0..b′ · · · , a′i �= 0, b′ �= 0

Wegen Δ(c, c′) ≥ 5 muß fur mindestens drei Indizes j, z.B. j = 1, 2, 3, a′j =

−aj gelten. Daraus wurde aber Δ(−c, c′) ≤ 3 folgen, Widerspruch. Eine 4-Menge ist also in hochstens einem Block enthalten, und wegen(

11

4

)=

11 · 10 · 9 · 824

= 330 = 66 · 5

in genau einem 5-Block. Wir erhalten also ein 4-(11,5) Steiner System. Eben-so erhalt man ein 5-(12,6) Steiner System aus den Wortern vom Gewicht 6in G12.

Konstruktion der Codes G23 und G24

Wiederum konstruieren wir zunachst einen [n = 24, k = 12, d = 8; 2]-CodeG24 und erhalten dann durch Verkurzung einen [23, 12, 7; 2]-Code G23. Es gibtviele Moglichkeiten, G24 zu konstruieren, die vielleicht eleganteste Methode

78

verwendet den Ikosaedergraphen:

Wir nummerieren die Ecken des Graphen mit 1 bis 12. Es sei A = (aij) dieAdjazenzmatrix des Graphen, also

aij =

{1 falls {i, j} Kante0 sonst,

und fassen A als Matrix uber GF (2) auf. A ist somit eine symmetrische Ma-trix mit 5 Einsen in jeder Zeile und Spalte, und Nullen in der Hauptdiagonale.Es seien ai und aj die i-te bzw. j-te Zeile von A, dann gilt

ai · aj =

{1 i = j0 i �= j

da ai · ai = 5 ≡ 1 (mod 2) und ai · aj = 2 oder 0 ≡ 0 (mod 2) fur i �= j ist.Es ist also A2 = I gleich der Einheitsmatrix der Ordnung 12.

Es sei nun J =

⎛⎝1 . . . 1

. . .1 . . . 1

⎞⎠ die 12× 12-Matrix aus lauter Einsen uber GF (2).

Dann gilt J2 =

(12 . . . 1212 . . . 12

)= O gleich der Nullmatrix der Ordnung 12.

Wir betrachten nun folgende Generatormatrix G:

G = [I|J + A] .

79

G ist also eine 12 × 24-Matrix mit jeweils einer Eins in der vorderen Halfteund 7 Einsen in der hinteren Halfte.

Behauptung. Der von G erzeugte Code C ist selbstdual.

Es gilt

GGT = [I|J + A][I

J + A] = I + (J + A)2

= I + J2 + A2 = I + I = O .

Es gilt also C ⊆ C⊥ und somit C = C⊥ wegen dim C = 12.

Behauptung. Ist (u|v) ∈ C, so ist auch (v|u) ∈ C. Wir haben

(J + A)G = (J + A)[I|J + A] = [J + A|(J + A)2]

= [J + A|I] ,

das heißt, [J + A|I] ist ebenfalls Generatormatrix von C. Schreiben wir dieZeilen von G als ci = (ei|fi), so bilden also auch c′i = (= (fi|ei) eine Basis. Aus(u|v) =

∑λici ∈ C folgt u =

∑λiei, v =

∑λifi, also (v|u) =

∑λic

′i ∈ C.

Behauptung. Der Code C ist ein [24, 12, 8; 2]-Code, genannt Golay CodeG24.

Wir wissen, dass C selbstdual ist und alle Basisworter Gewicht 8 haben. MitInduktion nach der Lange der Linearkombination sieht man leicht, dass alleCodeworter c ein Gewicht w(c) ≡ 0 (mod 4) haben. Wir mussen also nur nochGewicht 4 ausschließen. Sei (u|v) ∈ C mit Gewicht 4. Da auch (v|u) ∈ C ist,konnen wir uns auf folgende Falle beschranken:

w(u) w(v)1. 0 42. 1 33. 2 2

Der erste Fall ergibt das Nullwort. Im zweiten Fall erhalten wir ein Zeile vonG mit w(u|v) = 8. Im dritten Fall ist (u|v) = ci + cj Summe von zwei Zeilenci = (ei|fi), cj = (ej|fj) mit

w(ci + cj) = w(ei + ej) + w(fi + fj) .

80

Nun ist ei = (0 . . . 1 . . . 0) Einheitsvektor mit 1 an i-ter Stelle, also w(ei+ej) =2. Ferner ist fi = 1 + ai, wobei 1 der Vektor der Lange 12 aus lauter Einsenist, und ai die i-te Zeile von A. Wir haben somit

w(fi + fj) = w(1 + ai + 1 + aj) = w(ai + aj)

= w(ai) + w(aj) − 2 · #{Nachbarn von i und j}≥ 5 + 5 − 4 = 6 ,

und daher w(ci + cj) ≥ 8.

Der verkurzte Code ist dann der 3-perfekte [23, 12, 7; 2]-Code G23.

Auch hier erhalten wir Steiner Systeme. Nach einem fruheren Satz bilden dieCodeworter in G23 vom Gewicht 7 ein 4-(23,7) Steiner System. Die AnzahlA7 der Codeworter vom Gewicht 7 berechnet sich aus(

23

4

)= A7

(7

3

)= 35A7 ,

mit dem Ergebnis A7 = 253. Analog berechnet man A8 = 506. Im GolayCode G24 gilt also A8 = 759. Damit ist wegen 11 . . . 1 ∈ G24, also Ai = A24−i,die gesamte Gewichtsverteilung gegeben:

A0 A8 A12 A16 A24

G24 1 759 2576 759 1

Fur G23 haben wir wegen 11 . . . 1 ∈ G23 analog Ai = A23−i und erhalten dieVerteilung

A0 A7 A8 A11 A12 A15 A16 A23

G23 1 253 506 1286 1286 506 253 1

Fur G24 beweist man analog, dass die Codeworter in G24 vom Gewicht 8 ein5-(24,8) Steiner System bilden.

Der Golay Code G24 kann auch zur Konstruktion eines besonders interessan-ten nichtlinearen binaren Codes herangezogen werden. Mit Permutation der

81

Spalten schreiben wir die Generatormatrix von G24 in der Form

G =

⎛⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝

1 11 1

. . ....

1 1

G1

O G2

⎞⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠5

⎧⎨⎩

7

⎧⎪⎪⎨⎪⎪⎩

8︷ ︸︸ ︷ 16︷ ︸︸ ︷0

0

Es gibt 25 = 32 Codeworter in G24, die mit 0 0 . . . 0︸ ︷︷ ︸8

beginnen (die Linear-

kombinationen der Zeilen c8, . . . , c12 von G. Sei bi = 0 . . . 1 . . . 0 1 ∈ GF (2)8,i = 1, . . . , 7, dann gibt es 25 = 32 Codeworter in G24, die mit bi beginnen (dieLinearkombination von c8, . . . , c12 plus ci). Mit D bezeichnen wir die Mengendieser 8·25 = 28 Codeworter. Der Nordstrom-Robinson Code N ⊆ {0, 1}16 istD verkurzt auf die Spalten 9 bis 24. Wegen d(G24) = 8 sind die verkurztenWorter alle verschieden, also |N | = 28 = 256, und wir haben d(N ) = 6,da sich die Worter aus D in den ersten acht Koordinaten an hochstens zweiStellen unterscheiden. N ist also ein (nichtlinearer) binarer (16, 6)-Code mit|N | = 28.

Wir haben somit M2(16, 6) ≥ 28 und erhalten durch dreimalige PunktierungM2(13, 6) ≥ 25, also M2(12, 5) = M2(13, 6) ≥ 32. Bisher kennen wir dieobere Schranke M2(12, 5) ≤ 48, durch lineare Programmierung kann dies zuM2(12, 5) ≤ 32 verbessert werden. Es gilt also M2(12, 5) = 32, wahrend an-dererseits gezeigt werden kann, dass A2(12, 5) = 16 ist. Resultat: Es existiertein nichtlinearer (12, 5)-Code C mit |C| = 32, aber kein linearer.

82