Hamming-Code: Ein Bit über seine Position korrigieren

Lege vier Datenbits fest und kippe im Kanal beliebige Bits, über die Schaltflächen oder direkt im Diagramm. Der Decoder führt die drei Paritätsprüfungen erneut aus, liest die fehlgeschlagenen Prüfungen als Binärzahl und kippt das entsprechende Bit. Geh den Ablauf einmal schrittweise durch und probiere dann zwei gekippte Bits aus.

Rechenbeispiel — Hamming-Code: Ein Bit über seine Position korrigieren

Gesendet: die Prüfbits	0110011
Empfangen	0110111
Syndrom	1012
Ausgegebene Daten	1011
Falsche Datenbits gegenüber den gesendeten 1011	0
Rate, Datenbits je gesendetem Bit	57,1%
Block aus vier Datenbits unbemerkt falsch, bei p	2,03×10⁻³

Das sind die Werte, die der Rechner beim Öffnen der Seite anzeigt. Ändere oben eine Eingabe, um sie neu zu berechnen.

Interaktive Simulation wird geladen...

Lektion

Die Theorie — Hamming-Code: Ein Bit über seine Position korrigieren

Ein Hamming-Code ergänzt Daten um Prüfbits, damit sich ein einzelnes gekipptes Bit finden und zurückkippen lässt. Jedes Prüfbit sorgt dafür, dass eine bestimmte Menge von Positionen eine gerade Anzahl von Einsen enthält. Das ist eine Paritätsprüfung. Der Decoder wiederholt diese Prüfungen an den empfangenen Daten. Das Muster der fehlgeschlagenen Prüfungen heißt Syndrom. Als Binärzahl gelesen gibt es die Position des falschen Bits an; 0 bedeutet, dass kein Fehler vorliegt. Eine Prüfziffer kann nur erkennen, dass etwas nicht stimmt. Hier lässt sich auch die fehlerhafte Position bestimmen. Der erweiterte Code fügt ein Bit hinzu, das dem gesamten Wort gerade Parität gibt. Damit korrigiert er jeden einzelnen Bitfehler und erkennt zwei Bitfehler, ohne sie zu korrigieren: SECDED.

Was die einzelnen Symbole bedeuten

dᵢ: die vier Datenbits an den Positionen 3, 5, 6 und 7
p₁, p₂, p₄: die Prüfbits, jeweils an der Position, nach der sie benannt sind; p₀ ist das Gesamtparitätsbit des erweiterten Codes
s: das Syndrom 4s₄ + 2s₂ + s₁, wobei s_k den Wert 1 hat, wenn Kreis k bei der Ankunft eine ungerade Anzahl von Einsen enthält
P: die Parität aller acht empfangenen Bits im erweiterten Code: 1 bedeutet eine ungerade Anzahl gekippter Bits
p: die Bitfehlerrate, also die Wahrscheinlichkeit, dass ein bestimmtes Bit unabhängig von allen anderen kippt

Setzt voraus: Jedes Bit kippt unabhängig und mit derselben Wahrscheinlichkeit p. In realen Kanälen und Speichern treten Fehler auch gebündelt auf, wenn mehrere benachbarte Bits zugleich kippen. Solche Mehrfachfehler beherrschen diese Codes besonders schlecht.
Versagt, wenn: Bei drei gekippten Bits. Der erweiterte Code deutet drei Bitfehler als einen, weil die Gesamtparität ungerade wird, und kippt ein zuvor richtiges Bit. Die vollständige Fehlertabelle zeigt, dass alle 896 dreifachen Bitfehler ohne Markierung falsche Daten liefern.

Die Nummern der fehlgeschlagenen Kreise ergeben die Position des gekippten Bits 🖖

Drück Ein Bitfehler. Im Kanal kippt Bit 5. Nun enthalten die Kreise 1 und 4 eine ungerade Anzahl von Einsen, während Kreis 2 gerade bleibt: 1 + 4 = 5. Diese Voreinstellung ist kein eigens gewählter Sonderfall. Kreis k prüft genau die Positionen, deren Binärzahl k enthält. Ein falsches Bit an Position i stört daher genau die Kreise, deren Nummern zusammen i ergeben; seine Stelle im Diagramm ist zugleich seine Adresse. Hamming forderte 1950 eine solche „Prüfzahl“, die die Position jedes einzelnen Fehlers angibt, wobei null für keinen Fehler steht. Drei Prüfungen liefern acht mögliche Ergebnisse. Ein Sieben-Bit-Wort benötigt genau acht: die sieben Positionen und „kein Fehler“. Es bleibt also kein Ergebnis übrig. Von den 128 möglichen Sieben-Bit-Wörtern sind 16 Codewörter. Die übrigen 112 entstehen jeweils durch einen einzelnen Bitfehler in genau einem Codewort. Die Tabelle unter dem Diagramm decodiert alle 112 korrekt. Weshalb die Prüfbits an den Positionen 1, 2 und 4 stehen, ist weniger nebensächlich, als es zunächst scheint. Diese Positionen enthalten in Binärdarstellung jeweils nur eine einzige 1. Deshalb liegt jedes Prüfbit in genau einem Kreis und kann durch seine eigene Paritätsprüfung festgelegt werden. Genau diesen Grund nannte Hamming.

Zwei Bitfehler, und der Decoder beschädigt ein drittes Bit 🖖

Drück Zwei Bitfehler. Die Bits 3 und 5 werden falsch. Kreis 1 enthält beide, wird zweimal gestört und bleibt gerade. Die Kreise 2 und 4 werden ungerade, das Syndrom lautet 6, eine vollkommen gültige Position. Der Decoder kippt Bit 6, obwohl es richtig war. Bei der Ankunft waren zwei Datenbits falsch, nach der Korrektur sind es drei. Das Raster zeigt dasselbe für jedes Paar: Alle 21 und damit sämtliche 336 doppelten Bitfehler über die 16 Datenwörter liefern ohne Markierung falsche Daten. Drück Nur Prüfbits: Die Positionen 1 und 2 tragen keine Daten, die Daten kommen also unversehrt an. Trotzdem weist das Syndrom 3 den Decoder an, d₁ zu beschädigen. Drück nun Erweitert, zwei Fehler. Das achte Bit gibt allen acht Bits zusammen gerade Parität. Ein einzelner Bitfehler macht die Gesamtparität daher immer ungerade, zwei Bitfehler lassen sie stets gerade. Trifft eine gerade Gesamtparität auf ein Syndrom ungleich null, markiert der Decoder das Wort und verändert nichts. Das gilt für alle 448 doppelten Bitfehler. Korrigieren kann er sie nicht, denn 3 und 5 ergeben ebenso das Syndrom 6 wie 1 und 7. Am Anfang stand für Hamming die Fehlermeldung. Seine Arbeit von 1950 beginnt mit den beiden Relaisrechnern, die Bell Labs für das Aberdeen Proving Ground gebaut hatte. Kein Relaisausfall blieb dort unentdeckt; in der Anfangszeit traten unter 8.900 Relais täglich etwa zwei oder drei auf. Liefen die Rechner nachts und am Wochenende unbeaufsichtigt, kamen sie deshalb häufig zum Stillstand.

Jedes Bit zweimal zu senden kostet ebenfalls acht Bits und korrigiert nichts 🖖

Sowohl die doppelte Übertragung jedes Bits als auch der erweiterte Code verwenden acht Bits für vier Datenbits. Stimmen zwei Kopien nicht überein, ist zwar klar, dass etwas schiefging, aber nicht, welche Kopie richtig ist. Der Empfänger kann den Block nur markieren. Bei p = 0,01 geschieht das bei 7,69×10⁻² der Blöcke. Weitere 3,77×10⁻⁴ gelangen unbemerkt falsch ans Ziel, wenn beide Kopien eines Bits gemeinsam kippen. Der erweiterte Hamming-Code korrigiert jeden einzelnen Bitfehler, markiert 2,64×10⁻³ der Blöcke und lässt 5,34×10⁻⁵ unbemerkt falsch passieren. Bei gleichem Aufwand sind das 29-mal weniger Markierungen und 7-mal weniger falsche Blöcke. Sowohl bei den gestrichelten als auch bei den durchgezogenen Linien liegt er vorn, bis p den Wert 0,066 überschreitet. Das entspräche einem Kanal, der eines von fünfzehn Bits kippt. Drei Kopien jedes Bits schlagen den Sieben-Bit-Code pro Block bei jedem p auf dem Schieberegler, hier mit 1,19×10⁻³ gegenüber 2,03×10⁻³. Sie benötigen jedoch 12 statt 7 Bits. Deshalb ist der Vergleich bei acht Bits der faire.

Aufgabe vollständig gelöst

Wie viele Prüfbits benötigt ein 64-Bit-Wort? 4 Schritte
Schütze 64 Datenbits auf dieselbe Weise. Drück Erweitert, ein Fehler: Für vier Datenbits werden vier Prüfbits verwendet, die Rate beträgt 50,0 %. Bestimme, wie viele Prüfbits ein 64-Bit-Wort für dieselbe Zusicherung benötigt: Jeder einzelne Bitfehler wird korrigiert, zwei werden markiert. Ermittle außerdem, was das längere Wort beim voreingestellten p = 0,001 kostet.

Öffne diese Aufgabe im Tool
1. Bei r Prüfungen kann das Syndrom 2^r verschiedene Werte annehmen. Einer muss „kein Fehler“ bedeuten, und jede der m + r Positionen benötigt einen eigenen Wert. Daher gilt 2^r ≥ m + r + 1. Auf dieser Seite ist m = 4. Mit r = 3 ist die Bedingung exakt erfüllt; kein Wert bleibt übrig.
  
  $2^{r} \geq m + r + 1, m = 4 : 2^{3} = 8 = 4 + 3 + 1$
2. Für m = 64 liefern sechs Prüfungen 64 Werte, benötigt werden 71. Sieben Prüfungen liefern 128 Werte, genug für 72. Somit korrigieren 71 Bits jeden einzelnen Bitfehler.
  
  $m = 64 : 2^{6} = 64 < 71, 2^{7} = 128 \geq 72 \Rightarrow r = 7, n = 71$
3. Ein zusätzliches Gesamtparitätsbit ergibt 72 Bits. Davon sind 8 Prüfbits. Die Rate beträgt 88,9 % gegenüber 50,0 % auf dieser Seite.
  
  $n = 64 + 7 + 1 = 72, \frac{64}{72} = 88 . 9%$
4. Der Preis dafür: In einem längeren Wort treten zwei Bitfehler häufiger auf, und zwei kann SECDED nicht mehr korrigieren. Für ein einzelnes 8-Bit-Wort ergibt sich diese Wahrscheinlichkeit als Summe der beiden auf der Seite angegebenen Werte.
  
  $P_{\geq 2} (n) = 1 - q^{n} - n p q^{n - 1}, P_{\geq 2} (8) = 2.78 \times 1 0^{- 5} + 5.57 \times 1 0^{- 8} = 2.79 \times 1 0^{- 5}$
Antwort

Acht Prüfbits, ein 72-Bit-Wort, Rate 88,9 %. Bei p = 0,001 enthält es mit Wahrscheinlichkeit 2,44×10⁻³ mindestens zwei Bitfehler. Werden dieselben 64 Bits als sechzehn 8-Bit-Wörter gesendet, gehen sie verloren, sobald eines davon verloren geht; die Wahrscheinlichkeit beträgt 4,46×10⁻⁴. Beim langen Wort ist der Verlust der 64 Bits etwa 5,5-mal so wahrscheinlich. Dafür benötigt es nur ein Achtel so viele Prüfbits.

$P_{\geq 2} (72) = 2.44 \times 1 0^{- 3}, 1 - (1 - P_{\geq 2} (8))^{16} = 4.46 \times 1 0^{- 4}, \frac{2 . 44}{0 . 446} \approx 5.5$

Lernpfad

Warum ein Algorithmus korrekt ist

Quellen (2)

The code itself, the requirement that the checking number give the position of any single error, the check positions 1, 2, 4 and the reason for them, the extended code that adds double-error detection, and the relay computers that motivated it: R. W. Hamming, "Error Detecting and Error Correcting Codes." Bell System Technical Journal 29(2), April 1950, pp. 147-160. DOI 10.1002/j.1538-7305.1950.tb00463.x
How Hamming told the story in his later course: a relay computer that could detect an error, retried three times and then dropped the problem, and the question that followed: R. W. Hamming, The Art of Doing Science and Engineering: Learning to Learn, Session 12, "Error-Correcting Codes". Lecture slides, Naval Postgraduate School, Monterey (course delivered 1995).

Vom 42Math-Team · Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen.