Skript zur Vorlesung

Signale und Codes

Oktober 2012

Inhaltsverzeichnis

1 Einleitung 2

2 Informationstheorie 22.1 Entropie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.2 AEP, Datenkompression und Shannons Source-Coding-Theorem 42.3 Kanalkapazitat und Shannons Noisy-Channel-Theorem . . . . 7

2.3.1 Beispiele von Kanalen . . . . . . . . . . . . . . . . . . 72.3.2 Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.3.3 Gemeinsam typische Folgen . . . . . . . . . . . . . . . 92.3.4 Das Coding-Theorem . . . . . . . . . . . . . . . . . . 10

3 Codierungstheorie 123.1 Block-Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123.2 Lineare Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3.2.1 Syndromdecodierung . . . . . . . . . . . . . . . . . . . 153.2.2 Hamming-Codes . . . . . . . . . . . . . . . . . . . . . 153.2.3 Majority-Logic-Decoding . . . . . . . . . . . . . . . . 163.2.4 Weight-Enumeratives . . . . . . . . . . . . . . . . . . 173.2.5 Golay-Codes . . . . . . . . . . . . . . . . . . . . . . . 183.2.6 Reed-Muller-Codes . . . . . . . . . . . . . . . . . . . . 213.2.7 Schranken fur Codes . . . . . . . . . . . . . . . . . . . 22

3.3 Zyklische Codes . . . . . . . . . . . . . . . . . . . . . . . . . . 233.3.1 Bose-Chaudhuri-Hocquenghem-Codes (BCH-Codes) . 283.3.2 Reed-Solomon-Codes . . . . . . . . . . . . . . . . . . . 29

1

1 Einleitung

Jeder Kommunikationskanal unterliegt unvorhersehbaren Storungen, die manin der Praxis uberwinden mochte. Dazu konnen einerseits im Einzelfall diejeweiligen Komponenten des Systems verbessert werden (großere Antenne,hohere Sendeleistung, hoherwertige Komponenten, . . . ) oder andererseitsan einem systematischen Losungsansatz gearbeitet werden. Hierbei kom-men codierungs- und informationstheoretische Techniken zum Einsatz, diedie Qualitat eines Kanals verbessern. Man erganzt einen Kanal um Encoderund Decoder, um systeminherente Fehler so gut wie moglich zu korrigieren.

Der Encoder fugt einer Nachricht Redundanz hinzu. Der Decoder regeneriertaus einem gestorten, redundanten Signal wieder das ursprungliche Signal.

• Informationstheorie befasst sich mit den theoretischen Grenzen undMoglichkeiten der eben beschriebenen Systeme.

• Codierungstheorie befasst sich mit dem tatsachlichen Entwurf vonEncoder-Decoder-Verfahren fur solche Kanale. Sie findet daruber hin-aus in der Komplexitatstheorie (Average-Case Hardness, Beweis furIP = PSPACE) und der Kryptographie (McEliece Kryptosystem, Si-cherstellung von ehrlichen Verhalten bei Mehrparteienberechnungen)Anwendung.

2 Informationstheorie

Quellen/Signale modellieren wir als diskrete Zufallsvariablen X,Y, . . . uberAlphabeten X ,Y, . . . (ublicherweise {0, 1}n). Dadurch wird modelliert, dassein Empfanger eines Signals kein vollstandiges Wissen uber diese Nachrichthat. Er ist also uberrascht von diesem Signal. Bei deterministischen Prozes-sen (Empfanger kennt bereits die Nachricht) kann man die Kommunikationkomplett sparen.

2

2.1 Entropie

Definition 1 (Information, Uuberraschung). Sei X eine Zufallsvariablegegeben durch eine Wahrscheinlichkeits-Masse-Verteilung p(x) = Pr[X =x], x ∈ X . Wir bezeichnen

I(x) = − log(p(x))

als die Information/Uuberraschung eines Zeichens x.

Definition 2 ((Shannon-)Entropie). Die (Shannon-)Entropie einer Zufalls-variable X ist definiert durch

H(X) = −∑x∈X

p(x) · log(p(x)) = IE[I(x)].

Die Pseudoeinheit fur H(X) heißt Bits. Ist Xn ein zeitinvarianter (stati-onarer) Prozess, bei dem alle Xi unabhangig identisch verteilt sind, dannbezeichnet H(Xn) die Rate des Prozesses und wird in Bits pro Zeiteinheitangegeben.

Definition 3 (Verbundentropie). Die Verbundentropie zweier Zufallsvaria-blen X und Y ist definiert als die Entropie der Zufallsvariable (X,Y ), also

H(X,Y ) = −∑x∈X

∑y∈Y

p(x, y) · log(p(x, y)).

Definition 4 (Bedingte Entropie). Die bedingte Entropie ist definiert durch

H(X|Y ) = −∑y∈Y

p(y) ·H(X|Y = y) = −∑x∈X

∑y∈Y

p(x, y) · log(p(x|y)).

Definition 5 (Transinformation, gemeinsame Information). Die Transin-formation/gemeinsame Information I(X;Y ) gibt an, um wie viele Bits sichdie Entropie von X verringert, wenn man Y lernt. Sie ist gegeben durch

I(X;Y ) = H(X)−H(X|Y ) =∑x∈X

∑y∈Y

p(x, y) · log(p(x, y)

p(x) · p(y)).

Eigenschaften der Entropie

1. 0 ≤ H(X) ≤ log(|X|), wobei die erste Gleichheit gilt, wenn fur ein xip(xi) = 1 gilt. Die zweite Gleichheit, wenn X auf X gleichverteilt ist.

3

Beweis. Wir benutzen Jensens Ungleichung fur konkave Funktionen:

H(X)− log |X | =∑x

p(x) log1

p(x)− log |X |

=∑x

p(x) log1

p(x)|X |

= IE(log1

p(x)|X |)

≤ log IE(1

p(x)|X |)

= log∑x

p(x)1

p(x)|X |

= log∑x

p(x)1

|X |= log(1)

= 0

2. H(X,Y ) = H(X) +H(Y |X)

3. H(X,Y |Z) = H(X|Z) +H(Y |X,Z)

4. 0 ≤ I(X;Y ) = I(Y ;X)

5. I(X;Y ) = H(X) − H(X|Y ) = H(Y ) − H(Y |X) = H(X) + H(Y ) −H(X,Y )

2.2 AEP, Datenkompression und Shannons Source-Coding-Theorem

Wir interessieren uns dafur, wie sich bei haufiger Wiederholung eines Zu-fallsexperiments Vorhersagen uber die Gesamtmessung machen lassen. Sei

4

X eine Zufallsvariable, X1, . . . , Xn identisch, unabhangig verteilt mit p(x).Dann ist die Wahrscheinlichkeit, dass wir Messfolge (x1, . . . , xn) messenp(x1, . . . , xn) =

∏ni=0 p(xi). Man sieht, dass nicht alle Tupel gleiche Auf-

trittswahrscheinlichkeit haben. Man kann jedoch die Auftrittswahrschein-lichkeit der Folge, die man messen wird, vorhersagen; d.h. die Zufallsva-riable p(X1, . . . , Xn) schatzen. Es wird sich zeigen, dass p(X1, . . . , Xn) furwachsendes n nahe an 2−n·H(X) liegt.

Satz 1 (Asymptotische Aquipartitionsprinzip (AEP)). SindX1, . . . , Xn iden-tisch, unabhangig verteilt, dann konvergiert− 1

n ·log(p(X1, . . . , Xn))→ H(X)in der Wahrscheinlichkeit. Genauer:

Pr[| − 1

n· log(p(X1, . . . , Xn))−H(X)| > ε]→ 0 fur n→∞

Beweis. Es ist − 1n log(p(X1, . . . , Xn)) = − 1

n

∑ni=1 log(p(Xi)). Das schwa-

che Gesetz der großen Zahlen besagt nun, dass

Pr[| − 1

n

∑log

1

p(Xi)−H(X)| > ε] =

Pr[| − 1

n

∑log

1

p(Xi)− IE(log

1

p(x))| > ε] ≤

V ar(log 1p(x))

nε2n→∞−→ 0

Wir werden nun sehen, dass das AEP typische Mengen charakterisiert.

Definition 6 (Typische Menge). Eine typische Menge A(n)ε bezuglich p(x)

ist die Menge aller endlichen Folgen/Tupel (x1, . . . , xn) ∈ X n, sodass

2−n·(H(X)+ε) ≤ p(x1, . . . , xn) ≤ 2−n·(H(X)−ε)

bzw.

| − 1

nlog

1

p(x1, . . . , xn)−H(X)| ≤ ε.

Eigenschaften typischer Mengen

1. Pr[(x1, . . . , xn) ∈ A(n)ε ] > 1− ε fur hinreichend großes n

2. |A(n)ε | ≤ 2n(H(X)+ε)

3. |A(n)ε | > (1− ε) · 2n(H(X)−ε)

Beweis. 1. Folgt direkt aus der AEP, da

Pr[(x1, . . . , xn) ∈ A(n)ε ] = Pr[| − 1

nlog

1

p(x1, . . . , xn)−H(X)| ≤ ε]

−→ 1 > 1− ε

5

2. Es gilt

1 =∑

xn∈Xnp(xn) ≥

∑xn∈A(n)

ε

p(xn)

≥∑

xn∈A(n)ε

2−n(H(X)+ε) = |A(n)ε | · 2−n(H(X)+ε)

⇒ |A(n)ε | ≤ 2n(H(X)+ε)

3. Wegen 1. gilt fur hinreichend großes n

1− ε < Pr[(x1, . . . , xn) ∈ A(n)ε ] =

∑xn∈A(n)

ε

p(xn)

≤∑

xn∈A(n)ε

2−n(H(X)−ε) = |A(n)ε | · 2−n(H(X)−ε)

⇒ |A(n)ε | > (1− ε) · 2n(H(X)−ε)

Anwendung zur Datenkompression Seien X1, . . . , Xn Zufallsvariablenmit Massefunktion p(x). Wir suchen kurze Beschreibungen fur die Folgen(x1, . . . , xn). Dazu teilen wir X n in zwei Mengen ein: eine typische Menge

A(n)ε und eine untypische A(n)

ε = X n\A(n)ε . Wir gehen folgendermaßen vor:

1. Ordne die Elemente in A(n)ε und A(n)

ε lexikographisch.

2. Induziere jedes Tupel (x1, . . . , xn) in beiden Mengen mit seinem lexi-kographischen Index in der jeweiligen Menge.

3. Fur (x1, . . . , xn) ∈ A(n)ε benotigt man hochstens n · (H(X) + ε) +

1 Bits. Verwende ein zusatzliches Fuhrungsbit, um anzuzeigen, dass

(x1, . . . , xn) ∈ A(n)ε .

4. Analog fur (x1, . . . , xn) ∈ A(n)ε . Verwende n · log |X | + 1 Bits plus

Fuhrungsbit zum Codieren, also maximal n·log |X |+2 fur jedes Tupel.

Das Codierungsschema hat folgende Eigenschaften:

• Der Code ist bijektiv und “leicht“ decodierter.

• Typische Folgen haben kurze Beschreibungen der Lange ≈ n ·H(X).

• Falls H(X) < log |X |, dann enthalt A(n)ε zwar die uberwaltigende An-

zahl an Folgen; diese Folgen tauchen jedoch nur mit sehr geringerWahrscheinlichkeit auf.

6

Sei n hinreichend groß, sodass Pr[xn ∈ A(n)ε ] > 1−ε. Wir konnen nun die er-

wartete Codewort-Lange einer Folge (x1, . . . , xn) berechnen. l(xn) bezeichnedie Lange der Codierung von xn.

IE[l(Xn)] =∑

xn∈Xn

p(xn) · l(xn)

=∑

xn∈A(n)ε

p(xn) · l(xn) +∑

xn∈A(n)ε

p(xn) · l(xn)

≤ Pr[xn ∈ A(n)ε ] · (n · (H(X) + ε) + 2) + Pr[xn ∈ A(n)

ε ] · (n log |X |+ 2)

≤ n · (H(X) + ε) + εn log |X |+ 2

≤ n · (H(X) + ε′) wobei ε′ = ε+ ε log |X |+ 2

n

Satz 2 (Shannons Source-Coding-Theorem). Sei Xn eine identisch, un-abhangig mit p(x) verteilte Folge von Zufallsvariablen, sei ε > 0. Dannexistiert eine Codierung, welche Folgen xn der Lange n auf binare Stringsabbildet, sodass die Codierung bijektiv ist und fur hinreichend große n gilt:

IE[1

nl(Xn)] ≤ H(X) + ε

2.3 Kanalkapazitat und Shannons Noisy-Channel-Theorem

Definition 7 (Kanal). Ein diskreter, verrauschter Kanal K = (X n, p(y|x),Yn)ist ein System bestehend aus einem Eingabealphabet X , AusgabealphabetY und einer Ubertragungsmatrix M = (p(y|x))x∈X ,y∈Y , wobei p(y|x) =Pr[Y = y|X = x] die Ubertragungswahrscheinlichkeiten sind. Ein Kanalheißt gedachtnislos, falls die Verteilung der Ausgabe nur von der aktuellenEingabe abhangt und bedingt unabhangig von vorherigen Ein- und Ausga-ben ist.

Definition 8 (Kanalkapazitat). Die Kanalkapazitat zu einem Kanal K =(X n, p(y|x),Yn) ist definiert durch

C = maxp(x)

I(X;Y ).

2.3.1 Beispiele von Kanalen

1. Rauschfreier Kanal

7

2. Noisy TypewriterSetze p(0) = p(1) = 1

2 . Dann ist

I(X;Y ) = H(X)−H(X|Y )

= 1− 0

= 1

Damit ist C = 1.

(In der Literatur wird mit Noisy Typewriter ein anderer Ka- Anmerkungnal bezeichnet.)

3. Binarer symmetrischer Kanal

I(X;Y ) = H(Y )−H(Y |X)

= H(Y )−∑x

p(x) ·H(Y |X = x)

= H(Y )−H(ρ)

≤ 1−H(ρ)

Es gilt C = 1−H(ρ), denn fur p(x) = (12 ,12) gilt

auch p(y) = (12 ,12) und damit H(Y ) = 1.

4. Binarer Erasure-Kanal

2.3.2 Codes

Definition 9 ((M,n)-Code). Ein (M,n)-Code fur einen KanalK = (X n, p(y|x),Yn)besteht aus

• einem Nachrichtenraum M = {1, . . . ,M},

• einer Codierungsabbildung Xn(·) : {1, . . . ,M} → X n, welche Code-worte Xn(1), . . . , Xn(M) liefert, und

• einer Decodierabbildung g : Yn → {1, . . . ,M}.

8

Definition 10 (Ubertragungsfehlerwahrscheinlichkeiten). Wir definieren

λi = Pr[g(Y n) 6= i|Xn = Xn(i)]

als Ubertragungsfehlerwahrscheinlichkeiten fur die Nachricht i zu einem ge-geben Kanal K = (X n, p(y|x),Yn) und Code C = (M, Xn, g).

Definition 11 (Mittlere Fehlerwahrscheinlichkeit). Die mittlere Fehlerwahr-scheinlichkeit eines (M,n)-Codes C ist definiert durch

P (n)e =

1

M

M∑i=1

λi =

M∑i=1

Pr[w = i]λi

wobei w gleichverteilt auf {1, . . . ,M}.

Definition 12 (Rate, erreichbare Rate). Die Rate R eines (M, n)-Codes istgegeben durch

R =log |M|

n.

Eine Rate heißt erreichbar fur einen Kanal K, falls es eine Familie von(2nR, n)-Codes gibt, sodass maxi∈{1,...,M} λi → 0 fur n→∞.

2.3.3 Gemeinsam typische Folgen

Definition 13 (Gemeinsam typische Folge). Die Menge A(n)ε der gemein-

sam typischen Folgen bezuglich einer Verteilung p(x, y) ist die Menge aller(xn, yn) ∈ X n × Yn, sodass

| − 1

nlog p(xn)−H(X)| < ε

| − 1

nlog p(yn)−H(Y )| < ε

| − 1

nlog p(xn, yn)−H(X,Y )| < ε

Das heißt xn, yn und (xn, yn) sind jeweils typisch.

Satz 3 (Gemeinsame AEP). Seien (Xn, Y n) identisch, unabhangig verteilteFolgen, die aus der Verteilung p(xn, yn) gezogen werden. Dann gilt:

1. Pr[(xn, yn) ∈ A(n)ε ]→ 1 fur n→∞

2. |A(n)ε | ≤ 2n(H(X,Y )+ε)

3. Gilt (Xn, Y n) ∼ p(xn)·p(yn), sind Xn und Y n unabhangig aber jeweilsmit den selben Marginalverteilungen wie Xn und Y n verteilt, dann gilt

Pr[(xn, yn) ∈ A(n)ε ] ≤ 2−n·(I(X;Y )−3ε)

9

Beweis. 1. Folgt direkt aus der einfach AEP fur (xn, yn):

Pr[| − 1

nlog p(xn, yn)−H(X,Y )| < ε]→ 1 fur n→∞

2. Es gilt

1 =∑

(xn,yn)∈Xn×Ynp(xn, yn) ≥

∑(xn,yn)∈A(n)

ε

p(xn, yn)

≥∑

(xn,yn)∈A(n)ε

2−n(H(X,Y )+ε) = |A(n)ε | · 2−n(H(X,Y )+ε)

⇒ |A(n)ε | ≤ 2n(H(X,Y )+ε).

3. Sind Xn und Y n unabhangig, aber jeweils fur sich wie Xn und Y n

verteilt, dann gilt

Pr[(xn, yn) ∈ A(n)ε ] =

∑(xn,yn)∈A(n)

ε

≤2−n(H(X)−ε)

p(xn) ·≤2−n(H(Y )−ε)

p(yn)

≤ |A(n)ε | · 2−n(H(X)+H(Y )−2ε)

≤ 2−n(H(X)+H(Y )−H(X,Y )−3ε)

= 2−n(I(X;Y )−3ε)

2.3.4 Das Coding-Theorem

Wir werden zeigen, dass fur einen Kanal K = (X n, p(y|x),Yn) jede RateR < C erreichbar ist. Wir wenden die gemeinsame AEP an, das heißt wirverwenden lange Codeworte und verwenden deshalb den Kanal vielfach. Einempfangenes Signal yn decodieren wir zu einem xn, welches gemeinsam ty-pisch mit yn ist. Wir werden zeigen, dass wenn R < C dieses xn mit hoherWahrscheinlichkeit eindeutig ist.

Satz 4 (Shannons Coding Theorem). Fur jede Rate R < C existiert eineFamilie von (2nR, n)-Codes, sodass

maxi∈{1,...,2nR}

λi → 0 fur n→∞.

Beweis. Wahle p(x) (wird spater genauer spezifiziert). Wir ziehen nun einen(2nR, n)-Code C zufallig mit der Verteilung p(x). Das heißt wir ziehen 2nR

unabhangige Codeworte Xn(1), . . . , Xn(2nR). Die Wahrscheinlichkeit, dassein bestimmter Code C gezogen wird, ist also

Pr[C] = Π2nR

w=1Πni=1p(X

n(w)i)

10

Wir nehmen nun folgendes an:

• Der Code C wird wie oben beschrieben zufallig gezogen und Senderund Empfanger bekannt gemacht.

• Sowohl Sender als auch Empfanger kennen die Kanalubertragungs-wahrscheinlichkeiten p(y|x).

• Eine Nachricht w wird gleichverteilt vom Sender gezogen.

Pr[W = w] = 2−nR fur w = 1, . . . , 2nR

• Das Code-Wort Xn(w) wird durch den Kanal geschickt.

• Der Empfanger decodiert yn zu w, falls (Xn(w), yn) gemeinsam typischsind. Falls kein solches w existiert oder mehrere existieren, wird einFehler deklariert. Außerdem tritt ein Fehler auf, wenn w 6= w.

Sei E das Ereignis, das w 6= w. Wir berechnen nun die mittlere Fehlerwahr-scheinlichkeit, gemittelt uber alle Codeworter und alle Codes.

Pr[E ] =∑CPr[C]P (n)

e (C)

=∑CPr[C]( 1

2nR

2nR∑w=1

λw(C))

=1

2nR

2nR∑w=1

∑CPr[C]λw(C)

Da alle Codeworte Xn(w) identisch verteilt zufallig gezogen wurden, hangtder Ausdruck

∑C Pr[C]λw(C) nicht von w ab. Wir fixieren o.B.d.A. w = 1.

Sei Ei das Ereignis, dass (Xn(i), yn) ∈ A(n)ε . Die tatsachliche Ursache fur yn

ist Xn(1). Ein Fehler passiert genau dann, wenn E1, d.h. wenn (Xn(1), yn)nicht gemeinsam typisch sind, oder E2 ∨ . . . ∨ E2nR , d.h. wenn ein falschesCodewort gemeinsam typisch mit yn ist.

Pr[E ] = Pr[E1 ∨ (E2 ∨ . . . ∨ E2nR)]

≤ Pr[E1] +

2nR∑i=2

Pr[Ei]

Da Xn(2), . . . , Xn(2nR) unabhangig von xn = Xn(1) gezogen wurden, sindalsoXn(2), . . . , Xn(2nR) auch unabhangig von Y n. Damit gilt fur i ∈ {2, . . . , 2nR} :

Pr[Ei] = Pr[(Xn(i), yn) ∈ A(n)ε ] ≤ 2−n(I(X;Y )−3ε). Weiter gilt aufgrund der

11

gemeinsamen AEP, dass Pr[E1] ≤ ε. Insgesamt:

Pr[E ] ≤ ε+2nR∑i=2

2−n(I(X;Y )−3ε)

= ε+ (2nR − 1)2−n(I(X;Y )−3ε)

≤ ε+ 2−n(I(X;Y )−3ε−R)

≤ 2ε

falls n hinreichend groß und R < I(X;Y ) − 3ε. In diesem Fall ist also diemittlere Fehlerwahrscheinlichkeit uber alle Codeworter und alle Codes ≤ 2ε.Einige Konkretisierungen:

• Wir hatten p(x) bisher beliebig aber fest gewahlt. Wahle p(x) nunso, dass I(X;Y ) = C. Damit wird die Erreichbarkeitsbedingung zuR < C.

• Die Fehlerwahrscheinlichkeit wird bisher im Mittel uber eine großeAnzahl von Codes angegeben. Weil Pr[E ] ≤ 2ε gilt, gibt es mindestens

einen Code C?, fur welchen P(n)e (C) ≤ 2ε gilt. Man kann ein solches C?

beispielsweise durch vollstandige Suche finden.

• Vom besten Code C? verwerfe die Halfte aller Codeworter w, namlichsolche mit großer Fehlerwahrscheinlichkeit λw. Sortiere dazu beispiels-weise die Codeworter nach ihrer Fehlerwahrscheinlichkeit und nehmedie untere Halfte der Liste. Diesen neuen Code bezeichnen wir mit C?.

• Es gilt P(n)e (C?) = 1

2nR

∑2nR

i=1 λi ≤ 2ε. Das bedeutet, dass fur minde-stens die Halfte aller Codeworter w (insbesondere fur die Codeworter

in C?) die Ungleichung λw ≤ 4ε gelten muss, da ansonsten P(n)e > 2ε.

Wir haben einen Code C? konstruiert, der 2nR−1 Codeworte hat. Somithat C? die Rate R − 1

n → R fur n → ∞. C? hat maximale Fehlerwahr-scheinlichkeit maxw=1,...,2nR λw ≤ 4ε. Das zeigt, dass jede Rate unterhalbder Kapazitat C erreichbar ist.

3 Codierungstheorie

3.1 Block-Codes

Definition 14 (Block-Code, trivialer Code, binarer Code). Mit einem Block-Code werden Blocke fester Lange uber einem Alphabet Q (hier 0 ∈ Q) alsCodeworte verwendet. Codierung und Decodierung beachten keine Nachbar-blocke.Ein Code C der Lange n uber Q ist eine nicht-leere Teilmenge C ⊆ Qn. Ist|C| = 1 oder C = Qn, so heißt C trivial. Ist Q = F2, so heißt C binar.

12

Definition 15 (Hammingabstand, Hamminggewicht, Minimalabstand). Sei-en x, y ∈ Qn, dann heißt d(x, y) := |{i | xi 6= yi}| der Hammingabstand vonx und y. Das Hamminggewicht von x ist w(x) := d(x, 0). Der Minimalab-stand von C ist gegeben durch min{d(x, y) | x, y ∈ C, x 6= y} und ist einGutemaß fur den Code C.

Definition 16 (Informationsrate). Die Informationsrate R von C istlogq |C|n

mit q = |Q|.

Beispiel Q = {0, 1, 2, 3}, |Q| = 4C = {(x, x, x) | x ∈ Q}, |C| = 4

R = log4 43 = 1

3Der Minimalabstand von C ist 3.

Definition 17 (Uberdeckungsradius). Der maximale Abstand eines belie-bigen Elementes aus Qn zum nachsten Codewort heißt Uberdeckungsradius:

max {min{d(x, c) | c ∈ C} | x ∈ Qn}

Ein anderes interessantes Maß ist ρ, der maximale Radius, so dass alle Ku-geln Bρ(c) mit Radius ρ um Codeworte c disjunkt sind. Ein perfekter Codeerfullt, dass der Uberdeckungsradius ρ ist.

Definition 18 (Perfekter Code). Ein Code C ⊆ Qn mit Minimalabstandd = 2 · e + 1 heißt perfekt, wenn fur jedes x ∈ Qn genau ein c existiertmit d(c, x) ≤ e. Ein gerader Minimalabstand ist bei perfekten Codes nichtmoglich.

Folgende Codes sind perfekte Codes:

• Triviale Codes

• Binare Wiederholungscodes ungerader Lange

• Hamming-Codes

• Der binare Golay-Code G23 mit den Parametern (23, 12, 7)

• Der ternare Golay-Code G11 mit den Parametern (11, 6, 5)

Satz 5 (Kugelpackungsbedingung). Fur einen perfekten Code C ⊆ Qn mitMinimalabstand d = 2 · e+ 1 gilt:

qn = |C| · |Be(0)|

= |C| ·e∑l=0

(n

l

)(q − 1)l

13

3.2 Lineare Codes

Definition 19 (Linearer Code, Generatormatrix, systematische Codierung).Es sei Q = Fq, das heißt Qn ist ein Vektorraum. Ein linearer Code C ist einUntervektorraum von Qn der Dimension k. Wahle eine Basis von C. Diek×n-Matrix mit den k Basiselementen in den Zeilen heißt GeneratormatrixG von C. Durch a · G kann ein Nachrichtenwort a ∈ Qk codiert werden. Willman den Klartext im Code “direkt sehen”, so muss G die Form

G =

1 0 · · · · · · 0

0. . .

. . ....

.... . .

. . .. . .

... P...

. . .. . . 0

0 · · · · · · 0 1

k

︸ ︷︷ ︸k

︸ ︷︷ ︸n−k

haben. G heißt dann Matrix bei systematischer Codierung.

Die Rate eines linearen Codes der Dimension k istlogq |C|n = k

n .

Definition 20 (Aquivalente Codes). Zwei Codes C1, C2 heißen aquivalent,wenn sie durch Permutation der Stellen des Codes (Spalten in der Gene-ratormatrix) auseinander hervorgehen. Jeder Code ist aquivalent zu einemCode mit systematischer Codierung.Eine systematische Generatormatrix erhalt man durch Zeilenumformungenund Spaltenvertauschungen der ursprunglichen Generatormatrix.

Wie kann der Minimalabstand eines linearen Codes berechnet werden? ImAllgemeinen benotigt man dafur

(|C|2

)Berechnungen. Fur lineare Codes gilt

minx,y∈C

d(x, y) = min06=x∈C

d(x, 0)

Ein linearer Code der Lange n und der Dimension k (und mit Minimalab-stand d) wird als [n, k]-Code ([n, k, d]-Code) bezeichnet.

Definition 21 (Dualer Code, selbstdual). Es sei C ein [n, k]-Code. Dannheißt C⊥ := {y ∈ Qn | 〈y, x〉 = 0 fur alle x ∈ C} der zu C duale Code. Er istein [n, n− k]-Code. Falls C = C⊥ heißt C selbstdual.

Beispiel

• Q = F2, n = 3C = {(0, 0, 0), (1, 1, 1)} ist ein [3, 1]-Code.C⊥ ist also ein [3, 2]-Code und hat 22 Elemente.C⊥ = {(0, 0, 0), (0, 1, 1), (1, 0, 1), (1, 1, 0)}

14

• Q = F2, n = 4C = {(0, 0, 0, 0), (0, 0, 1, 1), (1, 1, 0, 0), (1, 1, 1, 1)} ist ein [4, 2]-Code.C⊥ = C

3.2.1 Syndromdecodierung

Sei G = (Ik|P ) Generatormatrix in systematischer Form von C. Fur dieGeneratormatrix H des Dualcodes muss gelten

∀x ∈ Qk, y ∈ Qn−k : 〈x · (Ik|P ), y ·H〉 = 0 ⇔∀x ∈ Qk, y ∈ Qn−k : x · (Ik|P ) · (y ·H)> = 0 ⇔∀x ∈ Qk, y ∈ Qn−k : x · (Ik|P ) ·H> · y> = 0 ⇔

(Ik|P ) ·H> = (0) ⇐

H =(−P>|In−k

)

C⊥ hat also die Generatormatrix H der Dimensionen n− k×n. Da ∀c ∈ C :c ·H> = 0 heißt H auch Prufmatrix von C, da damit gepruft werden kann,ob c ∈ C. Fur x ∈ Qn heißt x ·H> das Syndrom von x.Zerlege Qn in Nebenklassen x ∼ y :⇔ x − y ∈ C. Es sei nun ein Fehler ebeim Ubertragen eines beliebigen Codewortes c aufgetreten.

(c+ e) ·H> = c ·H> + e ·H> = e ·H>,

das heißt das Syndrom hangt nur vom Fehler ab. Dies nutzen wir zur Syn-dromdecodierung. Fur jede Nebenklassen ist das Syndrom eindeutig:

x ∼ y ⇔ x− y ∈ C ⇔ (x− y) ·H> = 0⇔ x ·H> = y ·H>

Eine Nebenklasse enthalt somit alle Vektoren, die zu einem bestimmtenSyndrom fuhren, sie haben alle denselben Fehler. Der Vektor, der das kleinsteGewicht hat, ist unter diesen der wahrscheinlichste Fehlervektor und wirdals Nebenklassenanfuhrer ausgewahlt.Zum Decodieren benotigt man also eine Tabelle der Lange qn−k, die jedemmoglichen Syndrom den wahrscheinlichsten Fehlervektor zuordnet.

3.2.2 Hamming-Codes

Sei H eine k×n-Prufmatrix eines Codes C uber Fq, bei welcher je zwei Spal-ten linear unabhangig sind. Ist c ∈ C ein Codewort und e ein Fehlervektormit w(e) = 1, dann ist das Syndrom (c + e) · H> von c + e das Vielfacheeiner Spalte von H. Das legt eine Spalte von H und damit die Fehlerpositioneindeutig fest. Wir suchen nun zu einem gegebenen k ein maximales n. Wirunterscheiden hierbei nicht zwischen aquivalenten Codes.

15

Definition 22 (Hamming-Code). Sei n = qk−1q−1 . Ein [n, n − k]-Hamming-

Code uber Fq ist ein Code, fur welchen die Spalten seiner Prufmatrix paar-weise linear unabhangig sind, die Spalten also eine maximale Menge linearunabhangiger Vektoren sind. Das heißt, es gibt 3 Spalten der Prufmatrix,die linear abhangig sind. Ansonsten konnte man eine weitere Spalte finden,die zu allen anderen linear unabhangig ware, das heißt ansonsten ware nnicht maximal. Die Minimaldistanz des Hamming-Codes ist somit 3.

Satz 6. Hamming-Codes sind perfekt.

Beweis. Dies kann mithilfe der Kugelpackungsbedingung gezeigt werden. Sei

C ein [n, n−k]-Hamming-Code uber Fq, wobei n = qk−1q−1 . Sei c ∈ C, sei B1(c)

die 1-Hammingkugel von c, dann gilt |B1(c)| = 1+n·(q−1) = 1+qk−1 = qk.Da C die Dimension n−k hat, gilt |C| = qn−k und damit gibt es eben so vieledisjunkte Kugeln mit Radius 1 um die Codeworte. Diese Kugeln enthaltenzusammen qn−k · qk = qn Worte, was bereits allen Worten in Fnq entspricht.Damit ist C perfekt.

Beispiel Der binare [7, 4]-Hamming-Code hat die Generatormatrix

G =

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

und Prufmatrix

H =

0 1 1 1 1 0 01 0 1 1 0 1 01 1 0 1 0 0 1

.

3.2.3 Majority-Logic-Decoding

Definition 23 (Orthogonale Prufgleichungen). Ein System von r Pruf-gleichungen 〈x, y(ν)〉 = 0 mit 1 ≤ ν ≤ r heißt orthogonal bezuglich Positioni (fur den Code und y(ν)) ∈ C⊥), falls:

• y(ν)i = 1 fur 1 ≤ ν ≤ r

• Falls j 6= i, dann gibt es hochstens ein ν, sodass y(ν)j 6= 0

Sei x ein Wort, welches t Fehler enthalte, t ≤ r2 . Dann gilt:

〈x, y(ν)〉 6= 0 fur

{≤ t Werte von ν, falls xi korrekt

≥ r − (t− 1) Werte von ν, falls xi inkorrekt

Weil r−(t−1) > t, konnen wir anhand der Mehrheit der Werte von 〈x, y(ν)〉entscheiden, ob xi korrekt ist oder nicht.

16

Beispiel Gegeben sei die Prufmatrix eines [15, 7, 5]-Codes:

H =

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

Geeignete Linearkombinationen der Zeilen von H (bezeichnet mit z1, ..., z8)ergeben die folgenden 4 Prufgleichungen:

z4 : 0 = x4 + x12 + x13 + x15

z2 + z6 : 0 = x2 + x6 + x14 + x15

z1 + z3 + z7 : 0 = x1 + x3 + x7 + x15

z8 : 0 = x8 + x9 + x11 + x15

Diese sind orthogonal bezuglich Position 15.Ist nur bei x15 ein Fehler aufgetreten, so liefern alle 4 Geleichungen eine 1;ist noch ein zweiter Fehler aufgetreten, dann liefern 3 Gleichungen eine 1.Wurde x15 korrekt ubertragen, so liefern 0, 1 oder 2 Gleichungen eine 1, jenachdem ob 0, 1 oder 2 Fehler aufgetreten sind.Fur bis zu zwei Fehler kann damit x15 per Mehrheitsentscheid mit den 4Prufgleichungen korrekt decodiert werden.Diese Art der Decodierung ist sehr effizient, es ist aber bei den meisten Codesschwierig oder unmoglich passende Gleichungen zu finden. Z. B. gibt es furden [7, 4]-Hamming-Code keinen Satz von orthogonalen Prufgleichungen.

3.2.4 Weight-Enumeratives

Die Minimaldistanz eines Codes legt fest, wie viele Fehler ein empfangenesWort enthalten kann und trotzdem noch decodiert werden kann. Oftmals istes notig mehr Distanzinformationen uber einen Code zu haben.

Definition 24 (Weight-Enumerator, Gewichtsverteilung). Sei C ein linearerCode der Lange n und sei Ai die Zahl der Codeworte von Gewicht i. dannheißt das Polynom A(z) =

∑ni=0Ai · zi der Weight-Enumerator von C. Die

Folge (Ai)ni=0 heißt Gewichtsverteilung von C.

Wir werden nun den Weight-Enumerator des binaren Hammingcodes derLange n berechnen. Dazu betrachten wir zunachst i − 1 Spalten der Pruf-matrix H. Wir unterscheiden drei Moglichkeiten fur die Summe dieser Spal-ten:

17

• Summe der Spalten ist 0

• Summe der Spalten ergibt eine der i− 1 Spalten

• Summe der Spalten ergibt eine der anderen n− (i− 1) Spalten

Es gibt(ni−1)

Moglichkeiten i−1 Spalten auszuwahlen. Dass die Summe derSpalten den Nullvektor ergibt, entspricht der Tatsache, dass fur x ∈ Qn mitw(x) = i − 1 das Produkt x · H> = 0. Da dies genau fur die x ∈ Qn gilt,die Codeworter des Hammingcodes sind, tritt Moglichkeit 1 genau Ai−1 malauf. Daraus lasst sich folgen, dass Moglichkeit 2 (n − (i − 2)) · Ai−2 malvorkommt. Es gibt namlich Ai−2 Moglichkeiten i− 2 Spalten auszuwahlen,deren Summe 0 ist, und in jedem Fall der Ai−2 Falle kann man eine vonn − (i − 2) weiteren Spalten wahlen. Moglichkeit 3 tritt i · Ai mal auf, daes Ai Moglichkeiten gibt, i Spalten mit Summe 0 auszuwahlen und es iMoglichkeiten gibt, aus i Spalten i − 1 Stuck auszuwahlen. Deren Summeentspricht dann der verbleibenden Spalte.Somit gilt:

i ·Ai =

(n

i− 1

)−Ai−1 − (n− i+ 2) ·Ai−2

Multipliziert man beide Seiten mit zi−1 und summiert uber i auf, erhaltman die folgende Differentialgeichung:

A′(z) = (1 + z)n −A(z)− nzA(z) + z2A′(z)

Mit A0 = 1 lasst sich dies zu

A(z) =1

n+ 1(1 + z)n +

n

n+ 1(1 + z)

n−12 (1− z)

n+12

losen.Eines der grundlegendsten Ergebnisse der Codierungstheorie, benannt nachJessi MacWilliams, gibt den Zusammenhang der Weight-Enumeratoren einesCodes C und seines Dualcodes C⊥ an. Wir zitieren diesen Satz hier ohneBeweis:

Satz 7 (MacWilliams-Identitat). Sei C ein [n, k]-Code uber Fq mit Weight-Enumerator A(z) und sei B(z) der Weight-Enumerator von C⊥. Dann gilt

B(z) = q−k · (1 + (q − 1) · z)n ·A(1− z

1 + (q − 1) · z).

3.2.5 Golay-Codes

Es gibt viele Variante die Golay-Codes G24 bzw. den G23 zu konstruieren.Hier seien zwei verschiedene genannt.

18

1. Variante der Konstruktion des G24

• Wahle ein Wort mit Gewicht 8

• Suche (z.B. durch lexikographisches Aufzahlen) ein Wort, das zu denbisher erzeugten Abstand 8 hat.

• Endet mit 212 Vektoren und liefert einen [24, 12, 8]-Code.

2. Variante der Konstruktion des G24

• Betrachte den Hamming-Code mit der Matrix

G =

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

.

G′ =

G

∣∣∣∣∣∣∣∣1101

ist [8, 4, 4]-Code und erweitert den Hamming-Code.

• Definiere einen zu G aquivalenten Code

G =

0 1 1 0 0 0 11 1 0 0 0 1 01 1 1 0 1 0 01 0 1 1 0 0 0

.

G′ =

G

∣∣∣∣∣∣∣∣1101

• G′ und G′ generieren nur Codeworter mit Gewicht 0, 4 und 8.

Der Hamming-Code hat Minimalgewicht 3, durch Erganzen auf geradeParitat ergibt sich ein Code G′ mit Codeworten von geradem Gewicht,also dem Minimalgewicht 4. Da 1 := (1, 1, 1, 1, 1, 1, 1, 1) ∈ G′ kannkein anderes Codewort mit Gewicht > 4 existieren, es hatte einenMinimalabstand < 4 von 1.

• Die beiden erweiterten Codes sind selbstdual, es gilt also G′ = G′⊥ und

G′ = G′⊥

Man kann einfach nachrechnen, dass G′ · G′> = 0 und k = n/2 was die

selbstdualtitat von G′ zeigt. Fur G′ gilt dasselbe Argument.

19

• Die Schnittmenge der beiden erweiterten Codes ist trivial, d.h. G′∩G′ ={0, 1}.Darstellen der Codeworte mit je 4 Unbestimmten und anschliessenderKoeffizientenvergleich liefert die Behauptung.

• Verwende G′ und G′ um einen anderen Code zu definieren

G24 := {(a+ x, b+ x, a+ b+ x)|a, b ∈ G′, x ∈ G′}

Fur die Generatormatrix bedeutet das:

G24 :=

G′ 0 G′0 G′ G′

G′ G′ G′

(12×24)

Eigenschaften des G24

• G24 ist ein selbstdualer (24, 12)-Code.

Die Dimension kann man z. B. uber rang(G24) = 12 berechnen. DieSelbstdualitat ergibt sich wie oben durch G24 · G>24 = 0 und k = n/2.

• Die Gewichte der Codeworte von G24 sind durch 4 teilbar.

Die Gewichte der 12 Basisvektoren sind durch 4 teilbar, es genugt alsozu zeigen:w(c) ≡ w(d) ≡ 0 (mod 4) =⇒ w(c+ d) ≡ 0 (mod 4) fur c, d ∈ G24.Definiere

(c ∩ d)i =

{1 : ci = di = 10 : sonst

Dann gilt 〈c, d〉 ≡ w(c ∩ d) ≡ 0 (mod 2), da G24 selbstdual ist. DasGewicht w(c+d) = w(c)+w(d)−2·w(c∩d) ist daher Summe/Differenzvon durch 4 teilbaren Zahlen also auch durch 4 teilbar.

• G24 hat Minimalgewicht 8.

Offensichtlich enthalt G24 Worte vom Gewicht 8, es ist also nur nochzu zeigen, dass G24 kein Wort vom Gewicht 4 enthalt.

Annahme: c = (a+ x, b+ x, a+ b+ x) ∈ G24 hat Gewicht 4.

In jeder der drei Komponenten erganzt das 8-te Bit die anderen 7 aufgerade Paritat, die drei Komponenten haben also gerades Gewicht undbei Gesamtgewicht 4 muss eine der Komponenten 0 sein.

Ohne Beschrankung der Allgemeinheit sei a + x = 0 und damit a =x ∈ G′ ∩ G′ = {0, 1}.

20

Im Fall a = 0 hat c = (0, b, b) ein Gewicht von mindestens 8, im Falla = 1 hat c = (0, b+ 1, b) ein Gewicht von mindestens 8.

(Fur einen ausfuhrlicheren Beweis, vergleiche z.B. http://www2.iwr.uni-heidelberg.de/groups/compalg/matzat/PDF/Codierungstheorie.

pdf, S.43)

• Es treten nur die Hamming-Gewichte 0, 8, 12, 16 und 24 auf.

• G24 ist [24, 12, 8]-Code.

Konstruktion des G23

• Streichen einer Spalte der Matrix G24, liefert G23

Eigenschaften des G23

• G23 ist ein [23, 12, 7]-Code.

• Es gilt 223 = 212 · (1 +(231

)+(232

)+(233

)) und somit ist G23 perfekt.

3.2.6 Reed-Muller-Codes

Hinfuhrung: Die Summe von Codes Es seien zwei Codes C1 als [n, k1, d1]-Code und C2 als [n, k2, d2]-Code gegeben. Betrachte nun den Code {(a1, a1+a2)|a1 ∈ C1, a2 ∈ C2}. Dies ist ein [2n, k1 + k2, dmin]-Code mit Generatorma-trix

G1&G2 :=

(G1 G10 G2

).

Es gilt dmin = min{2d1, d2}. Beweis:

• Offensichtlich ist dmin ≤ min{2d1, d2}

• Fall 1: a2 = 0⇒ w(a1, a1) ≥ 2d1

• Fall 2: a2 6= 0 ⇒ w(a1, a1 + a2) = w(a1) + w(a1 + a2) = w(−a1) +w(a1 + a2) ≥ w(−a1 + a1 + a2) = w(a2) ≥ d2

Definition 25 (Reed-Muller-Code). Sei r,m ∈ N, 0 ≤ r ≤ m. RM(r,m) istein [n, k, d]-Code mit n = 2m, k =

∑ri=0

(mi

), d = 2m−r. Er wird rekursiv

definiert durch:

• RM(0,m) ist ein [2m, 1, 2m]-Wiederholungscode.

• RM(m,m) ist uncodiert, das heißt, dass das Informationswort direktausgegeben wird.

• RM(r + 1,m+ 1) = RM(r + 1,m)&RM(r,m)

21

Beispiel

RM(1, 1) =

(1 00 1

), dmin = 1

RM(1, 2) = RM(1, 1)&RM(0, 1) =

1 0 1 00 1 0 1

0 0 1 1

, dmin = 2

RM(1, 3) = RM(1, 2)&RM(0, 2) =

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

0 0 0 0 1 1 1 1

, dmin = 4

RM(2, 2) =

1 0 0 00 1 0 00 0 1 00 0 0 1

, dmin = 1

RM(2, 3) = RM(2, 2)&RM(1, 2) =

1 0 0 0 1 0 0 00 1 0 0 0 1 0 00 0 1 0 0 0 1 00 0 0 1 0 0 0 1

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

, dmin = 2

Das Decodieren kann mittels einer Verallgemeinerung des Majority-Logic-Decodings durchgefuhrt werden.

3.2.7 Schranken fur Codes

Wir wenden uns nun dem Problem zu, bei vorgegebener Lange n und Mi-nimaldistanz d Codes zu finden, die moglichst hohe Rate R = k

n haben.Dabei werden wir lediglich die Existenz solcher Codes behandeln. Aspektewie Konstruktion, Codierung und Decodierung lassen wir außen vor.Wir suchen zunachst nach oberen Schranken fur Codes. Ist C ein [n, k, d]-Code, dann erhalten wir durch Weglassen eines redundanten Zeichens einenneuen Code C′. C′ hat die Lange n− 1, Dimension k und mindestens Mini-maldistanz d− 1. C′ heißt punktierter Code.

Satz 8 (Singleton-Schranke). Sei C ein [n, k, d]-Code uber Fq, dann giltk ≤ n − d + 1. Codes, welche die Singleton-Schranke exakt erfullen, also[n, k, n− k+ 1]-Codes heißen Maximum-Distance-Separable-Codes bzw. op-timale Codes.

Beweis. Punktiere den Code C so oft, bis der resultierende Code C′ Mi-nimaldistanz 1 hat. Dazu mussen wir C mindestens d − 1 mal punktie-ren. Bei jeder Punktierung nimmt die Lange des Codes um 1 ab. Also giltk ≤ n− (d− 1) = n− d+ 1

22

Satz 9 (Hamming-Schranke). Sei Bq(n, r) = {x ∈ Fnq |w(x) ≤ r} die Ham-mingkugel mit Radius r um 0. Vq(n, r) = |Bq(n, r)| sei das Volumen die-ser Kugel. Sei C ein [n, k, d]-Code uber Fnq , wobei d = 2r + 1. Dann giltk ≤ n− logq Vq(n, r) (vergleiche Kugelpackungsbedingung).

Beweis. Wir zahlen wie viele Hammingkugeln vom Radius r wir hochstensin den Raum Fnq packen konnen. Fur je zwei Codeworte c 6= c′ ∈ C giltdist(c, c′) ≥ d genau dann wenn die Hammingkugeln um c und c′ mitRadius r disjunkt sind. Eine Schranke fur die Anzahl moglicher disjunk-ter Hammingkugeln mit Radius r liefert also eine Schranke fur die Anzahlmoglicher Codeworte in C. Es gilt |Fnq | = qn. Damit konnen wir hochstensqn

Vq(n,r)Kugeln im Fnq packen, also gilt qk = |C| ≤ qn

Vq(n,r)und somit k ≤

n− logq Vq(n, r).

Satz 10 (Gilbert-Varshamov-Schranke). Seien n und d mogliche Parame-ter eines Codes uber Fq. Dann existiert ein [n, k, d]-Code C, falls k < n −logq Vq(n, d− 1).

Beweis. Die Beweisidee ist, dass ein zufalliger [n, k]-Code wahrscheinlicheine Minimaldistanz ≥ d hat. Wahle G (k × n-Generatormatrix) zufalliggleichverteilt. Fur ein Nachrichtenwort x 6= 0 (zufallig gewahlt und fest)gilt:

Pr[w(x · G) < d] =Vq(n, d− 1)

qn

Fur alle x ∈ Fkq\{0} bedeutet das:

Pr[∃x ∈ Fkq\{0} : w(x · G) < d] ≤ (qk − 1) · Vq(n, d− 1)

qn

< qk · Vq(n, d− 1)

qn

< 1 nach Voraussetzung

Da die Wahrscheinlichkeit < 1 ist, existiert mit Wahrscheinlichkeit > 0 einCode mit Minimalgewicht ≥ d.

3.3 Zyklische Codes

Definition 26 (Zyklischer Code). Ein linearer Code heißt zyklisch, falls

(c0, . . . , cn−1) ∈ C ⇒ (cn−1, c0, . . . , cn−2) ∈ C

Um Struktur ausnutzen zu konnen, betrachte den Isomorphismus

Fnq → Fq[x]/(xn − 1)

(c0, . . . , cn−1) 7→n−1∑i=0

cixi

23

Zyklisches Verschieben entspricht der Multiplikation mit x

x ·n−1∑i=0

cixi ≡ cn−1 + c0x+ . . .

Satz 11. C ist zyklisch ⇔ C ist Ideal in Fq[x]/(xn − 1)

Beweis.“⇐ “ c ∈ C ⇒ x · c = (cn−1, c0, . . . , cn−2) ∈ C

“⇒ “ z.z. ∀g(x) : g(x) · c(x) ∈ C, falls c(x) ∈ Cx · c(x) ∈ C ⇒ ∀i : xi · c(x) ∈ CC ist linearer Code, also c1 + c2 ∈ C (c1, c2 ∈ C)⇒ (

∑aix

i) · c(x) ∈ C

Konvention Um Sonderfalle zu vermeiden sei ab jetzt ggT(q, n) = 1.

Bemerkung. Fq[x]/(xn− 1) ist Hauptidealring, das heißt jedes Ideal C hateinen Erzeuger g(x), so dass C = Fq[x] · g(x).

Beweisidee. Wird eine Funktion c ∈ C dargestellt durch zwei Erzeugerc(x) = a1(x)·g1(x)+a2(x)·g2(x), dann berechne g(x) := ggT(g1(x), g2(x)) =d · g1(x) + e · g2(x) ∈ C. ⇒ c(x) =? · g(x)

Definition 27 (Generatorpolynom). Jeder zyklische Code wird von einemPolynom erzeugt. Das normierte Polynom vom kleinsten Grad heißt Gene-ratorpolynom.

Bemerkung. Das Generatorpolynom g(x) von C teilt xn − 1.

Beweis. Es gilt g(x) ∈ C und ebenso xn − 1 = 0 ∈ C. Wir setzen g(x) :=ggT(g(x), xn− 1). Es gilt also grad(g(x)) ≤ grad(g(x)). Außerdem folgt ausder Definition von g(x), dass es sich als Linearkombination von g(x) undxn − 1 darstellen lasst und somit ebenfalls in C ist. Da g(x) ein Polynomin C von kleinstem Grad ist, folgt grad(g(x)) = grad(g(x)). Es muss alsog(x) = g(x) gelten und somit g(x)|xn − 1.

Damit ergibt sich: Es sei (xn−1) = f1(x) · . . . ·ft(x) Zerlegung in irreduziblePolynome. Dann existieren 2t verschiedene Teiler von xn − 1 und damit 2t

verschiedene zyklische Codes der Lange n.

Beispiel. Wir betrachten Codes uber F2 der Lange n = 7. Es gilt (x7−1) =(x−1)·(x3+x+1)·(x3+x2+1). Es gibt also 23 = 8 zyklische Codes. Beachteim Folgenden, dass sich im F2 die Operationen + und − nicht unterscheiden.

• g(x) = 1 erzeugt C = F2[x]/(x7 − 1).

• g(x) = x7 − 1 erzeugt C = {0}.

24

• g(x) = x + 1 erzeugt C = {a(x) · (x + 1)|a(x) ∈ F2[x]/(x7 − 1)}. DieMultiplikation von a(x) = 0, 1, x, x+ 1, . . . , x5 +x4 +x3 +x2 +x+ 1mit g(x) erzeugt 26 verschiedene Polynome, die alle in C liegen. Wirzeigen, dass dies bereits alle Polynome in C sind. Es gilt

x6 · (x+ 1) = x7 + x6 = (x+ 1) · (x5 + x4 + x3 + x2 + x+ 1).

Sei nun r(x) ein Polynom von Grad ≤ 5 und a(x) = x6 + r(x). Sei

c = a(x) · (x+ 1)

= x6 · (x+ 1) + r(x) · (x+ 1)

= (x5 + x4 + x3 + x2 + x+ 1 + r(x)) · (x+ 1).

Das Codewort c lasst sich also bereits durch die Multiplikation einesPolynom von Grad ≤ 5, namlich x5 + x4 + x3 + x2 + x+ 1 + r(x), mitx+1 erzeugen. Somit haben wir c bereits oben mitgezahlt. Es gilt also|C| = 26. Somit ist C ein [7, 6]-Code.Die Generatormatrix von C ist

G =

x0 x1 x2 x3 x4 x5 x6

1 1 0 0 0 0 00 1 1 0 0 0 00 0 1 1 0 0 00 0 0 1 1 0 00 0 0 0 1 1 00 0 0 0 0 1 1

x0 + x1

x1 + x2

x2 + x3

x3 + x4

x4 + x5

x5 + x6

An der Generatormatrix kann man ablesen, dass jedes Wort c ∈ Cgerade Paritat hat.

• Welchen Code erzeugt g(x) = (x3 + x + 1) · (x3 + x2 + 1) = x6 +x5 + x4 + x3 + x2 + x+ 1? Es gilt, dass g(x) mit grad(g(X)) = 6 dasPolynom kleinsten Grades in C ist. Es gilt x ·g(x) = g(x). Somit ist fura(x) ∈ F2[x]/(xn − 1) das Produkt a(x) · g(x) ein Vielfaches von g(x)und damit 0 oder g(x). Damit gilt C = {0, g(x)} und C ist [7, 1]-Code.

• g(x) = x3 + x2 + 1 und g(x) = x3 + x+ 1 erzeugen [7, 4]-Codes.

• g(x) = (x3 + x2 + 1) · (x+ 1) erzeugt einen [7, 3]-Code.

• g(x) = (x3 +x+1) · (x+1) = x4 +x3 +x2 +1 erzeugt einen [7, 3]-Code

25

mit den folgenden 23 = 8 Codeworten:

0 = (0, 0, 0, 0, 0, 0, 0)

g1 = (1, 0, 1, 1, 1, 0, 0)

g2 = (0, 1, 0, 1, 1, 1, 0)

g3 = (0, 0, 1, 0, 1, 1, 1)

g1 + g2 = (1, 1, 1, 0, 0, 1, 0)

g1 + g3 = (1, 0, 0, 1, 0, 1, 1)

g2 + g3 = (0, 1, 1, 1, 0, 0, 1)

g1 + g2 + g3 = (1, 1, 0, 0, 1, 0, 1)

Die Untersuchung aller 8 Codeworte liefert d = 4. C ist also ein [7, 3, 4]-Code.

Definition 28 (Maximaler zyklischer Code). Ein Code mit Generatorpoly-nom fi(x) (ein irreduzibler Faktor von xn − 1) heißt maximaler zyklischerCode. Dies entspricht einem maximalen Ideal.

Warum zyklische Codes? Bei den linearen Codes haben wir bereits diealgebraische Struktur von Untervektorraumen des Fnq ausgenutzt. Bei zykli-schen Codes greifen wir auf Ideale im Restklassenring Fq[x]/(xn−1) des Po-lynomrings Fq[x] zuruck. Bei zyklischen Codes lassen sich Operationen wieCodieren, Parity-Check, etc. mit effizienten Polynomoperationen darstel-len. Eine Polynommultiplikation kann beispielsweise in geeigneten Ringenin O(n log n) durchgefuhrt werden, wohingegen das Vektor-Matrix-Produktnur in O(n2) berechnet werden kann. Daruber hinaus erlaubt die Ringstruk-tur auch eine einfache Konstruktion von Codes und diese Codes lassen sichmit gut verstanden Techniken fur Ringe/Algebren untersuchen. Da der Fq[x]euklidisch ist, ist eine Polynomdivision moglich. Diese kann z.B. zur Deco-dierung eingesetzt werden.Da Fq[x] euklidisch ist, ist er auch ein Hauptidealring, das heißt fur jedesIdeal I ≤ Fq[x] gilt ∃g(x) ∈ Fq[X] : I = 〈g(x)〉. Da Fq[x] nullteilerfrei ist, ister auch ein faktorieller Ring, das heißt jedes f(x) ∈ Fq[x] besitzt eindeutigeZerlegung in f(x) = f1(x) · . . . · ft(x) mit irreduziblen Polynomen fi(x).Falls char(Fq) 6 |n, dann zerfallt xn− 1 in paarweise verschiedene irreduzibleFaktoren xn − 1 = f1(x) · . . . · ft(x). xn − 1 ist dann also “quadratfrei”.Der Chinesische Restsatz sagt uns

Fq[x]/(xn − 1) ∼= Fq[x]/f1(x)× . . .× Fq[x]/ft(x)

Der zugehorige Isomorphismus Φ ist die Fouriertransformation.In Hauptidealringen sind Primideale maximal. Da die fi(x) irreduzibel sind,sind die Ji = 〈fi(x)〉 also maximale Ideale. Damit gilt:

Fq[x]/fi(x) ∼= Fqgrad(fi) =: Ki

26

Fq[x]/fi(x) ist also Erweiterungskorper vom Grad grad(fi) von Fq. Da dieKi Korper sind, haben sie eine triviale Idealstruktur Ki = 〈1〉 und {0} = 〈0〉.Ideale I in K1 × . . . ×Kt haben also die Form I = I1 × . . . × It, wobei furalle j ∈ {1, . . . , t} entweder Ij = 〈1〉 oder Ij = 〈0〉 gilt.Wie sieht Φ genau aus? Sind φ1, . . . , φt Erzeuger von K1, . . . ,Kt, also Ki =Fq[φi], lasst sich Φ darstellen als:

Φ : Fq[x]/(xn − 1) → K1 × . . .×Kt

c(x) 7→ (c(φ1), . . . , c(φt))

Maximale zyklische Codes entsprechen genau den Idealen I = I1 × . . . × Itfur welche fur genau ein j gilt, dass Ij = 〈0〉 und fur alle anderen i 6= j giltIi = 〈1〉.

Generatormatrix eines zyklischen Codes Sei C = 〈g(x)〉mit grad(g(x)) =n−k, sei a(x) =

∑k−1i=0 aix

i. Stelle c(x) = g(x)·a(x) als Matrixmultiplikationdar. B = {1, x, x2, . . . , xn−1} ist Vektorraumbasis von Fq[x]/(xn − 1). Sei Gdie Generatormatrix von C

G =

g0 · · · gn−k 0 · · · 0

0. . .

. . .. . .

......

. . .. . .

. . . 00 · · · 0 g0 · · · gn−k

Prufpolynom und Prufmatrix eines zyklischen Codes

Definition 29 (Prufpolynom). Analog zur Prufmatrix definieren wir furzyklische Codes ein Prufpolynom h(x), sodass

∀c(x) ∈ C : h(x) · c(x) = 0.

Ein solches Polynom existiert, da g(x)|xn−1 und somit g(x) in Fq[x]/(xn−1)invertierbar ist.

Wir bestimmen nun die Prufmatrix eines zyklischen Codes C mit Erzeuger-polynom g(x). Es gilt g(x)|xn − 1 und wie eben beschrieben existiert einPrufpolynom h ∈ Fq[x]/(xn − 1) mit gh = xn − 1 ≡ 0. Sei h =

∑ki=0 hix

i,dann gilt

∀i ∈ {1, . . . , n− 1} : g0hi + g1hi−1 + g2hi−2 + . . .+ gn−khi−n+k = 0.

Somit hat die Prufmatrix H die folgende Form:

H =

0 · · · 0 hk · · · · · · · · · h0...

......

... 0

0...

......

...hk · · · · · · · · · h0 0 · · · 0

27

Wir werden nun noch eine alternative Darstellung der Prufmatrix bestim-men: Der Chinesische Restsatz liefert uns, dass C ∼= I1 × . . . × It, wobeiIi = 〈0〉 oder Ii = 〈1〉. Seien i1, . . . , il die Indizes mit Iij = 〈0〉. SeiΦ : Fq[x]/(xn − 1) → K1 × . . . × Kt, f(x) 7→ (f(ξ1), . . . , f(ξt)) (Woher Anmerkungkommen die ξi?) der zum Chinesischen Restsatz gehorende Isomorphis-mus. Dann gilt fur alle c ∈ C : c(ξi1) = . . . = c(ξil) = 0. Weil Φ einIsomorphismus ist, sind diese Bedingungen hinreichend fur c ∈ C. Schreibenwir diese Gleichungen in Matrixform, so erhalten wir die Prufmatrix H.

H =

1 ξi1 ξ2i1 . . . ξn−1i11 ξi2 ξ2i2 . . . ξn−1i2...

......

...

1 ξil ξ2il . . . ξn−1il

(Damit die Prufmatrix die richtigen Dimensionen hat, muss jetzt Anmerkungl = n − k gelten. Wieso gilt das?) Fasst man die Korperelemente ξmij ∈Kij = Fq[ξij ] (Verstehe ich nicht.) als Spaltenvektoren uber Fq auf, so Anmerkungerhalt man eine alternative Prufmatrix. (Noch eine dritte?) Anmerkung

3.3.1 Bose-Chaudhuri-Hocquenghem-Codes (BCH-Codes)

Definition 30 (BCH-Codes). Sei β eine primitive n-te Einheitswurzel ineinem Erweiterungskorper von Fq. Seien weiter l, δ ∈ N mit δ ≥ 2. Sei Cder zyklische Code, dessen Erzeugerpolynom g(x) das kleinste gemeinsameVielfache der verschiedenen Minimalpolynome von βl, . . . , βl+δ−2 ist. Furc ∈ C gilt also c(βl) = . . . = c(βl+δ−2) = 0. C heißt BCH-Code mit geplanterMinimaldistanz δ.

Satz 12. Fur die Minimaldistanz d eines BCH-Codes C mit geplanter Mi-nimaldistanz δ gilt d ≥ δ.

Beweis. Es gilt fur alle c ∈ C : c(βl) = . . . = c(βl+δ−2) = 0. Die Parity-Check-Matrix lasst sich also darstellen als

H =

1 βl β2l · · · β(n−1)l

1 βl+1 β2(l+1) · · · β(n−1)(l+1)

......

......

1 βl+δ−2 β2(l+δ−2) · · · β(n−1)(l+δ−2)

,

wobei jeder Eintrag in dieser Matrix als Spaltenvektor der Lange m uber Fqaufgefasst wird. Ein Wort c ∈ Fnq liegt in C genau dann, wenn c ·H> = 0.

Gilt fur jedes c mit w(c) < δ, dass c ·H> = 0, dann ist die Minimaldistanzvon C großer oder gleich δ. Das gilt offensichtlich, wenn je δ−1 Spalten von

28

H linear unabhangig sind. Jede Spalte von H hat die Form

hi =

βil

βi(l+1)

...

βi(l+δ−2)

= βil

1βi

...

βi(δ−2)

.

Sei hi1 , . . . , hiδ−1die Submatrix von H, die aus den Spalten von H mit Indi-

zes i1, . . . , iδ−1 besteht, also Hi1,...,iδ−1= (hi1 , . . . , hiδ−1

). hi1 , . . . , hiδ−1sind

genau dann linear unabhangig, wenn det(Hi1,...,iδ−1) 6= 0. Es gilt

det(Hi1,...,iδ−1) =

δ−1∏j=1

βij l ·

∣∣∣∣∣∣∣∣∣1 · · · 1βi1 · · · βid−1

......

βi1δ−2 · · · βid−1

δ−2

∣∣∣∣∣∣∣∣∣Die Determinante dieser Vandermonde-Matrix lasst sich leicht berechnenund wir formen die Gleichung um zu:

det(Hi1,...,iδ−1) =

δ−1∑j=1

βij l∏r>s

(βir − βis) 6= 0

Damit sind hi1 , . . . , hiδ−1linear unabhangig und deshalb hat C Minimaldi-

stanz ≥ δ.

3.3.2 Reed-Solomon-Codes

Definition 31 (Reed-Solomon-Code). Ein Reed-Solomon-Code ist ein pri-mitiver BCH-Code C der Lange n = q − 1 uber Fq. Das Generatorpolynom

eines solchen Codes hat die Form g(x) =∏δ−1i=1 (x− αi), wobei αi Primitiv-

wurzel von Fq ist und δ die geplante Minimaldistanz von C ist. (α ist genaudann Primitivwurzel von Fq, wenn ∀a ∈ Fq\{0} : ∃i ∈ N : a = αi.) Ein sol-cher Code hat Dimension k = n− δ + 1. Es gilt d ≥ δ, da C ein BCH-Codeist. Andererseits sagt die Singleton-Schranke d ≤ n − k + 1. Damit hat CMinimaldistanz d = δ.

Weitere Materialien

• http://graphics.ethz.ch/teaching/former/showOldCourse.php?

page=infotheory0607&subpage=notes&title=Informationstheorie%

20(WS%2006/07)

• http://www2.iwr.uni-heidelberg.de/groups/compalg/matzat/PDF/

Codierungstheorie.pdf

29