Kapitel 3

Codierungstheorie

3.1 Einleitung
Wir wollen uns im Folgenden mit der sog. Fehlererkennung beschäftigen. Wir
kümmern uns vornehmlich um Fehler, die beim Lesen, bei der Speicherung und
beim Auslesen von Daten entstehen1 . Wie kann man also Fehler bei der Da-
tenübermittlung vermeiden ? Wir kennen das vom Telefonieren: Wenn jemand
unseren Namen nicht richtig versteht, so fügen wir zusätzliche Informationen
hinzu, indem wir unseren Namen buchstabieren oder das Wort wiederholen.
Hieran kann der Empfänger erkennen, ob die übermittelte Nachricht richtig
oder falsch ist.

3.2 Die Grundidee

Ein fehlererkennender Code ist eine Menge C ⊆ V. Der Sender codiert seine
Information durch ein c ∈ C. Dieses wird dann dem Empfänger übermittelt.
Dieser empfängt möglicherweise ein verändertes c ∈ V. Er überprüft, ob c ∈ C
gilt. Wenn nicht, weist er die Nachricht zurück. Wenn c ∈ C ist, so wird c und
die darin enthaltene Information akzeptiert.
Üblicherweise ist V die Menge aller n-Tupel über einem Alphabet A.

Angenommen, wir wollen 4-stellige Zahlen der Form αβγδ übermitteln2 . Der
Empfänger soll merken, ob die Daten korrekt sind oder nicht. Da man dies an
den Daten nicht erkennen kann, fügt man eine weitere (also eine fünfte) Ziffer ζ
an, die die Quersumme der ersten vier Zahlen zu einer Zehnerzahl ergänzt, also
α + β + γ + δ + ζ ≡ 0 mod 10.
Beispiele:
1234 −→ 1234ζ = 12340 4813 −→ 4813ζ = 48134
Der Code ist in diesem Beispiel die Menge aller 5-stelligen Zahlen, deren Quer-
summe durch 10 teilbar ist:
C = {αβγδζ : α, β, γ, δ, ζ ∈ {0, 1, . . . , 9}, 10 | α + β + γ + δ + ζ}.
1 z.B. falsche Ziffer gespeichert oder zwei Ziffern vertauscht.
2 In jeder Zahle stecke eine Information, die sich problemlos extrahieren lässt.

13
Die Elemente eines Codes heißen Codewörter. Die Menge V ist hier die Menge
aller 5-stelligen Zahlen.

Dieser Code erkennt Einzelfehler. Also merkt der Empfänger, wenn etwas falsch
übermittelt wurde, indem ihm auffällt, dass er kein Codewort erhalten hat. Er
prüft also, ob die Quersumme durch 10 teilbar ist. Wenn nicht, so weist er
die Nachricht zurück, ansonsten akzeptiert er die Nachricht und extrahiert die
Informationen.

3.3 Paritätscodes
Ein Code über dem Alphabet A = {0, 1, . . . , q−1} und den Ziffern 0, 1, . . . , q−
1 ist irgendeine Menge von Folgen (a1 , a2 , . . . , an ), wobei ai ∈ A. In obigem Bei-
spiel ist q = 10 und n = 5.
Ein Code erkennt Einzelfehler, wenn an einem Codewort an einer Stelle der
Wert ai in ai = ai geändert wird, so dass die entstehende Folge kein Codewort
mehr ist. Je zwei verschiedene Codewörter unterscheiden sich also an mindes-
tens zwei Stellen!

Ein Code der Länge n zur Basis q (der Länge n über einem Alphabet
mit q Ziffern) heißt Paritätscode, wenn für jedes Codewort (a1 , a2 , . . . , an ) die
Summe a1 + a2 + · · · + an ein Vielfaches von q ist.
Bekanntlich war ja die letzte Ziffer eines Codes die sog. Prüfziffer. Die eigentli-
che Information steckt dann natürlich in den Ziffern a1 , . . . , an−1 . Die Prüfziffer
an errechnet sich wie oben dann:
an = −(a1 + a2 + . . . an−1 ) mod q.
Jeder solche Paritätscode erkennt Einzelfehler3 .

Nun aber zu den Vertauschungsfehlern:

Wir sagen, dass ein Code C Vertauschungsfehler erkennt, falls für jedes Code-
wort (a1 , . . . , ai , ai+1 , . . . , an ) gilt: Die durch die Vertauschung der Elemente ai
und ai+1 = ai entstehende Folge (a1 , . . . , ai+1 , ai , . . . , an ) ist kein Codewort.

PROBLEM: Da 5 + 3 = 3 + 5 gilt, fällt eine Vertauschung 35 −→ 53 bei ei-

nem einfachen Paritätscode gar nicht auf.

Wir müssen uns etwas einfallen lassen: Jede Stelle wird mit einem Gewicht
versehen (multipliziert), bevor die Quersumme berechnet wird.

Beispiel: Kontonummern und Lokomotivnummern der DB

Kontonummer 1 8 9 8 2 8 0 1
Gewichtung 1 2 1 2 1 2 1 2
Produkt 1 16 9 16 2 16 0 2
Die Prüfziffer bekommt man schnell:
an = −(1 + 16 + 9 + 16 + 2 + 16 + 0 + 2) = −62 ≡ 8 mod 10.
3 Beweis: siehe [BZ], S. 95.

14
Also lautet die Kontonummer 189828018.
Dummerweise kann kann dieser Code keine Einzelfehler erkennen! Ein
entscheidender Nachteil !!!

Also: Ein Code der Länge n zur Basis q heißt Paritätscode mit Gewich-
ten g1 , . . . , gn , wenn für jedes Codewort (a1 , . . . , an ) die gewichtete Summe

g 1 a1 + . . . g n an

ein Vielfaches von q ist. Wenn gn teilerfremd zu q (am besten 1) ist, lässt sich
die Prüfziffer in allen Fällen berechnen.

Um eine Einzelfehlererkennung zu gewährleisten, beachte man:

Ein Paritätscode der Länge n zur Basis q mit Gewichten g1 , . . . , gn erkennt ge-
nau dann alle Einzelfehler, falls jedes gi (i = 1, . . . , n) teilerfremd zu q ist. Sind
für alle i, j die Gewichtsdifferenzen gi − gj teilerfremd zu q, so erkennt der Pa-
ritätscode auch alle Vertauschungsfehler.

Nun aber einige Beispiele:

(i) Für q = 10 müssen alle gewichte ungerade und verschieden von 5 sein,
damit alle Einzelfehler erkannt werden. Es kommen als Gewichte also nur
1, 3, 7, 9 in Frage. Im Falle q = 11 sind alle Zahlen zwischen 1 und 10
möglich, und es werden alle Einzelfehler erkannt.
(ii) Für q = 10 werden Vertauschungen an zwei Stellen genau dann erkannt,
wenn die Differenz der entsprechenden Gewichte gleich 1, 3, 7, 9 ist. Ver-
tauschungen aufeinander folgender Stellen werden z.B. mit der Gewichtung
1, 2, 1, 2, . . . erkannt. Beide Fehler zu erkennen wird allerdings schwer, da
nach (i) für die Einzelfehlererkennung ungerade Gewichte gewählt werden
müssen. Dann sind die Differenzen der Gewichte aber gerade, so dass keine
Vertauschungsfehler erkannt werden !
(iii) q = 11 ist der optimale Code, da beide Fehlerarten erkannt werden.

3.4 ISBN
Der ISBN-Code, der uns von Buchbestellungen bekannt ist, ist fast optimal.
Jedes Buch der Welt hat eine ISBN-Nummer (Internationale Standard Buch
Nummer) mit 10 Stellen, die in vier Gruppen eingeteilt sind:
(i) Sprachraum: 0,1 (englisch), 2 (französisch), 3 (deutsch), ..., 88 (italienisch)
(ii) Verlag im Sprachraum: 528 (Vieweg), 446 (FB Leipzig)
(iii) Nummer des Buches im Verlag: 16989 (DMfA)
(iv) Prüfziffer
Sei a1 a2 . . . a10 eine ISBN. Hier berechnet man die Prüfziffer a10 folgendermaßen:
Wähle die Gewichtung

10a1 + 9a2 + 8a3 + · · · + 3a8 + 2a9 + a10 .

15
Bestimme nun
S := 10a1 + 9a2 + 8a3 + · · · + 3a8 + 2a9
und ergänze diese zu einer Elferzahl. Wir haben also wieder mit Restklassen
mod 11 zu tun. Wenn sich als Prüfziffer 10 ergibt, so schreiben wir X.

Der ISBN-Code erkennt alle Einzelfehler und alle Vertauschungsfehler.

3.5 Übungsaufgaben
(1) Für die ISBN 3 − 528 − 06783−? berechne man die Prüfziffer.
(2) Hat folgende ISBN die richtige Prüfziffer ? Korrigiere gegebenenfalls !

3 − 446 − 22343 − 5

(3) Fast jedes käufliche Produkt besitzt eine EAN (Europäische Artikel Nummer)
mit zugehörigem Strichcode. Die EAN ist entweder 8- oder 13-stellig, an letz-
ter Stelle steht - wie üblich die Prüfziffer. Sie wird nach einem Paritätscode
zur Basis 10 mit den Gewichten 1-3-1-...-1 (bei 13 Stellen) bzw. 3-1-3-...-1
(bei 8 Stellen) berechnet. Zeige, dass der EAN-Code alle Einzelfehler er-
kennt.
(4) Ist 9783446223431 eine korrekte EAN ?

16