Rechnernetze
Home Nach oben

Hammingbedingung

Sei eine Information mit k Bits kodierbar (d.h. das Alphabet umfasst höchstens 2k verschiedene Zeichen). Zusätzlich zu diesen k Bits werden r Bits Redundanz-Information hinzugefügt. Es stellt sich die Frage, wie viele Redundanz-Bits mindestens hinzugefügt werden müssen, um einen Fehler von s Bits in der Nachricht erkennen und korrigieren zu können. Wir betrachten im folgenden nur den Fall, dass s=1, d.h. dass nur ein 1-Bit-Fehler auftreten kann und korrigiert werden soll.

b1b2...bkp1p2..pr Codewort mit k Nutzdatenbit und r Prüfbit

Um diese Frage zu beantworten, führt man den Begriff Hamming-Abstand ein. Die Anzahl von Stellen, an denen zwei Codewörter verschiedene Bits haben, wird als Hamming-Abstand dieser beiden Codewörter definiert:

1 1 0 0 1 0 0 1
0 1 0 0 1 0 1 1
/ = = = = = / = => Hamming-Abstand ist 2

Als Hamming-Abstand eines Alphabets bezeichnet man den minimalen Abstand zweier verschiedener Codewörter in diesem Alphabet. Es soll jetzt ein Verfahren vorgestellt werden, zu einem Alphabet mit k Bits einen fehlerkorrigierenden Code zu konstruieren.

Zu einem Codewort C der Länge n=k+r Bits gibt es genau ein Codewort mit dem Hammingabstand 0, nämlich C selbst. Jedem Codewort C können genau n Codewörter gleicher Länge n mit dem Hamming-Abstand 1 zugeordnet werden, indem jeweils genau eines der n Bits des Codeworts C komplementiert wird.

1 1 0 0 1 0 0 1 => Hamming-Abstand = 0
0 1 0 0 1 0 0 1 => Hamming-Abstand = 1
1 0 0 0 1 0 0 1 => Hamming-Abstand = 1
. . .
1 1 0 0 1 0 0 0 => Hamming-Abstand = 1

Daher haben n+1 Codewörter einen Abstand zum Codewort C, der kleiner ist als 2, nämlich 0 oder 1. Es soll 2k Zeichen im Alphabet geben, von denen jedes n+1 Codewörter belegt. Daher müssen (n+1)·2k Codewörter mit n Bits darstellbar sein, d.h. es muss gelten: (n+1)·2k = (k+r+1)·2k < 2n = 2k+r. Also muss sein: k+r+1 < 2r.

Dieses gibt eine Mindestzahl r von Prüfbits an, die für die Sicherung von k Datenbits nötig sind. 

Um zu einer effektiven Kodierung zu kommen, die jedem der 2k Zeichenwerte ein Codewort der Länge k+r zuordnet, fasst man die k Nutzdatenbits so in r Gruppen (Paritätsgruppen) zusammen, dass ein Fehler in einer Gruppe auf jeden Fall erkannt und eindeutig identifiziert werden kann. Um die i-te Gruppe abzusichern, wird das i-te Prüfbit so gewählt, dass die Anzahl der gesetzten Bits in der i-ten Gruppe zusammen mit dem i-ten Prüfbit gerade ist (Paritätsprüfung). Mit r=3 ist es z.B. möglich, systematisch die folgenden Bitgruppen zu bilden:

Gruppe

Bit

Bit

Bit

Bit

1.

1

3

5

7

2.

2

3

6

7

3.

4

5

6

7

Ein falsches Bit wird somit genau eine Kombination von Paritätsfehlern der einzelnen Gruppen erzeugen:

Fehlerhaftes Bit Nr.

1

2

3

4

5

6

7

Paritätsfehler in Gruppe(n)

1

2

1,2

3

1,3

2,3

1,2,3

Tritt kein Paritätsfehler in einer Gruppe auf, so ist auch kein 1-Bit-Fehler aufgetreten. Drei der sieben Bits des letzten Beispiels sind offenbar die Prüfbits, so dass mit r=3 folgt: k=4.

In dem obigen Beispiel wurden die einzelnen Bits des Codeworts so den Gruppen zugeordnet, dass die Nummer eines Bits b sich aus den Nummern der Codegruppen gi, in welchem sich das Bit befindet, nach der Formel

bgleichSumme2hochgi.gif (487 Byte)

berechnet. So steht das Bit 5 in den Gruppen 1 und 3, und es ist daher 20+22=5. Dieses lässt sich offenbar immer erreichen, da jeweils aus den 1-Termen der Nummer eines Bits in dem Codewort direkt die Prüfgruppen, in welche dieses Bit gehört, ermittelt werden können. Diese Eigenschaft werden wir noch bei der Fehlererkennung mittels Prüfgruppen verwenden.

Mit diesem Verfahren können im Prinzip auch 2-Bitfehler korrigiert werden, indem die Anzahl der Codewörter mit den Hammingabständen 0, 1 und 2 bestimmt werden und mit der Anzahl der Coderwörter verglichen wird. Man erhält die Formel:

Korrektur-2-Bit.gif (1362 Byte)

Die Anzahl der Datenbits, die mit einer gegebenen Anzahl von Prüfbits überwacht werden kann, ergibt sich nach diesem Ansatz zu: 

Prüfbits 4 5 6 7 8 9 10 11 12 13 14
Datenbits 1 2 4 8 14 22 34 52 78 115 166

Mit 4 Prüfbits lässt sich also gerade ein Datenbit absichern. Wird beispielsweise der Zeichenwert 0 mit dem Codewort 00000 kodiert, der Zeichenwert 1 mit dem Codewort 11111, so ist offenbar jedes Codewort mit 2 oder weniger Bits dem Zeichenwert 0 zuzuordnen, während jedes Codewort mit 3 oder mehr Bits dem Zeichenwert 1 zugeordnet werden kann. Allerdings wäre hier ein Schiedsrichterverfahren, welches jedes Bit fünfmal sendet und dann die "Mehrheit" bildet, ebenso effizient.