Rechnernetze
Home Nach oben

Hamming-Verfahren mit Paritätsgruppen

Die Formel über die Hammingbedingung lässt sich also auch folgendermaßen rechtfertigen: Es gebe r Paritätsgruppen; jedes der n=r+k Bits lässt sich mit genau einer unterschiedlichen Kombination der r Gruppen absichern. Es können also r Bits jeweils durch eine Gruppe gesichert werden, durch jede Kombination von zwei Gruppen können (r2)=r·(r-1)/2 Bits abgesichert werden, usw. Insgesamt folgt, dass

rueber1.gif (3504 Byte)

Bits abgesichert werden können. Somit erhält man das gleiche Ergebnis wie oben; während oben die Mindestanzahl benötigter Prüfbits berechnet wurde, konnte hier jedoch zugleich ein konstruktives Verfahren zur Fehlererkennung dargestellt werden. Das ergibt den folgenden Satz:

Satz

Um 1-Bit-Fehler bei Informationsfeldern der Länge k Bits korrigieren zu können, werden genau r Prüfbits benötigt, wobei

k  <  2r – 1 – r

Ordnet man in der obigen Darstellung 3 Bits eines Codeworts den Prüfbits zu, so kann jede Gruppe so gestaltet werden, dass die Anzahl gesetzter Bits in jeder Gruppe gerade ist, da die Werte der Prüfbits beliebig gewählt werden dürfen. Entdeckt der Empfänger, dass ein oder mehrere dieser Gruppen eine ungerade Anzahl gesetzter Bits enthalten, so kann nach der letzten Tabelle eindeutig bestimmt werden, welches Bit verfälscht wurde.

Ein Algorithmus, der genau das fehlerhafte Bit bestimmt, könnte folgendermaßen implementiert werden: Das i-te Prüfbit wird in einem Codewort der Länge n=k+r an 2i-1-ter Stelle übertragen: das erste Prüfbit an 1., das zweite an 2., das dritte an 4. Stelle usw.:

1. Prüfbit 2. Prüfbit 1. Datenbit 3. Prüfbit 2. Datenbit 3. Datenbit 4. Datenbit

Die restlichen Stellen werden mit Datenbits belegt. In die i-te Gruppe werden die Bits eingeordnet, in deren (binär dargestellter) Nummer (=i) das i-te Bit gesetzt ist, also in die erste Gruppe die Bits an ungerader Stelle, in die zweite die Bits an den Stellen 2, 3, 6, 7,… Jedes Bit steht also genau in so vielen Paritätsgruppen wie seine Ordnungsnummer gesetzte Bits in der binären Zahlendarstellung enthält; jene mit nur einem Bit in der Ordnungsnummer sind die Prüfbits.

Gruppe

Prüfbit

Datenbit

Datenbit

Datenbit

1.

1

3

5

7

2.

2

3

6

7

3.

4

5

6

7

Ist nun das Bit an der Stelle p falsch, so hat die i-te Prüfgruppe genau dann eine ungerade Parität, wenn in der Nummer der Stelle p das Bit i gesetzt ist. Addiert man die Ordnungsnummern dieser fehlerhaften Prüfgruppenbits, so erhält man die Ordnungsnummer des falschen Bits: Ist z.B. das 6. Bit falsch, so hat die zweite und die dritte Prüfgruppe, jedoch keine andere eine ungerade Parität. Also ist die Nummer des falschen Bits: 21 + 22 = 6.

Das Verfahren sichert im obigen Beispiel genau 4 Nutzdatenbits mit 3 Prüfbits ab. Die Redundanz ist also 75%. Mit r=4 Prüfbits lassen sich bis zu k=11 Nutzdatenbits absichern, so dass die Redundanz hier bei ca 36% liegt. Die allgemeine Formel für die Redundanz ist offensichtlich:

REDUNDANZ-4.gif (1997 Byte)

und wird mit wachsendem k rasch kleiner. Für r=16 und somit k = 65519 erhalten wir: R=0.025%. Allerdings würden wir mit diesem Verfahren genau den Fall behandeln können, dass ein 1-Bit-Fehler in einem Codewort der Länge k = 65519 auftritt. Treten jedoch zwei oder mehr Bitfehler auf, so meldet uns dieses Verfahren lediglich einen Bitfehler (oder keinen), so dass trotz Korrektur kein korrektes Ergebnis erzielt würde. Da in der Praxis jedoch meistens Folgen von Bitfehlern (error bursts) auftreten, ist dieses Verfahren (zumindest im Bereich der Datenübertragung) wenig nützlich. Statt auch von sehr langen Bitfolgen genau einen Bitfehler zu erkennen, ist man eher daran interessiert zu erkennen, ob überhaupt ein Fehler aufgetreten ist. Um selbstkorrigierende Codes bei der Datenübertragung einzusetzen, müssen also noch Ergänzungen angebracht werden.