Was ist Hamming-Code?
Der bekannteste Fehlerkorrekturcode, der 1-Bit-Fehler korrigiert. Mit r Prüfbits ist ein Codewort 2^r − 1 Bit lang, von denen 2^r − 1 − r Bit Daten tragen. Der Hamming-Code (7, 4) mit r = 3 ergänzt 4 Datenbits um 3 Prüfbits. Jedes Prüfbit ist die Parität einer überlappenden Gruppe von Bits, und das Ergebnis der beim Empfänger wiederholten Prüfungen (das Syndrom) gibt die Position des falschen Bits als Binärzahl an. Sein minimaler Hamming-Abstand ist 3, und SECDED, das 1 Bit Gesamtparität hinzufügt, erkennt auch 2-Bit-Fehler. Er wird zum Beispiel für ECC in Serverspeichern verwendet.
Japanische Bezeichnung: ハミング符号
„Hamming-Code“ kommt in 5 Übungsfragen aus 2 Themen vor, z. B. Grundlagen der Informationstheorie und Kodierung, Logikschaltungen.
Fachgebiet: Grundlagen der Informationstheorie und Kodierung
Funktionsweise des (7, 4)-Codes
Die Bitpositionen werden von 1 bis 7 nummeriert, und die Positionen 1, 2 und 4, die Zweierpotenzen sind, sind die Prüfbits. Prüfung 1 macht die Zahl der Einsen über die Positionen gerade, deren Nummer im Binärsystem an der Einerstelle eine 1 hat (1, 3, 5, 7), Prüfung 2 über die Positionen mit einer 1 an der Zweierstelle (2, 3, 6, 7) und Prüfung 4 über die Positionen mit einer 1 an der Viererstelle (4, 5, 6, 7). Nur die Prüfungen, die den Binärstellen mit einer 1 in der Nummer der falschen Position entsprechen, schlagen fehl; die Summe der Gewichte der fehlgeschlagenen Prüfungen ergibt daher die falsche Position.
Coderate und Länge
Mit r Prüfbits ist das Codewort 2^r − 1 Bit lang, und je länger der Code, etwa (7, 4), (15, 11) und (31, 26), desto höher die Coderate: 4/7 ≈ 0,57, 11/15 ≈ 0,73 und 26/31 ≈ 0,84. Dafür kann ein Codewort nur 1 Bit korrigieren, sodass ein längeres Codewort mit höherer Wahrscheinlichkeit einen Fehler von 2 oder mehr Bits enthält.
Häufige Fragen
Was geschieht bei einem Hamming-Code, wenn ein 2-Bit-Fehler auftritt?
Bei einem Hamming-Code ohne Gesamtparität lässt ein 2-Bit-Fehler das Syndrom trotzdem auf irgendeine Position ungleich 0 zeigen; ein richtiges Bit wird invertiert, und der Fehler wächst auf 3 Bit. Um das zu verhindern, verwenden Speicher und ähnliche Bausteine SECDED mit zusätzlicher Gesamtparität und melden einen 2-Bit-Fehler als Fehler, statt ihn zu korrigieren.
Werden Hamming-Codes heute noch verwendet?
Ja. Sie lassen sich einfach und schnell berechnen und werden daher überall dort eingesetzt, wo die Latenz klein bleiben muss, etwa für ECC von Speichern und zum Schutz von Caches und Registern. Wo viele Fehler effizient korrigiert werden müssen, etwa in der Kommunikation, verwendet man leistungsfähigere Codes wie LDPC-Codes.