⚙️ Hamming-Codes

Über Hamming-Codes SECDED

Hamming-Codes sind eine Familie linearer, fehlerkorrigierender Codes, die 1950 von Richard Hamming bei Bell Labs erfunden wurden. Ein Hamming(7,4)-Code codiert 4 Datenbits in 7 Codewortbits, indem 3 Paritätsbits an Zweierpotenz-Positionen (1, 2, 4) hinzugefügt werden; jedes Paritätsbit deckt eine bestimmte Teilmenge von Datenbitpositionen ab, die durch die Spalten der Paritätsprüfmatrix H definiert wird. Diese Anordnung verleiht dem Code einen minimalen Hamming-Abstand von 3, wodurch garantiert wird, dass er jeden Einzelbitfehler korrigieren und jeden Zweibitfehler erkennen kann. Fügt man ein zusätzliches Gesamtparitätsbit hinzu, entsteht der SECDED-Code (Single-Error Correcting, Double-Error Detecting) Hamming(8,4), der in ECC-RAM verwendet wird, wo ein gekipptes Speicherbit bei jedem Lesevorgang automatisch korrigiert wird.

Der Simulator erlaubt es Ihnen, 4-Bit-Datenwörter einzugeben, dabei zuzusehen, wie die Paritätsprüfmatrix sie in 7- oder 8-Bit-Codewörter codiert, einzelne oder doppelte Bitkipper einzufügen und die Syndrom-Decodierung zu beobachten: Der Syndromvektor s = H·r (mod 2) zeigt direkt auf die Position des fehlerhaften Bits und ermöglicht so eine automatische Korrektur in einem Schritt.

Häufig gestellte Fragen

Häufig gestellte Fragen

Was ist ein Hamming-Code?

Ein Hamming-Code ist ein linearer, fehlerkorrigierender Code, der 1950 von Richard Hamming erfunden wurde. Er fügt einem Datenwort redundante Paritätsbits hinzu, sodass jeder Einzelbitfehler erkannt und korrigiert werden kann. Hamming(7,4) codiert 4 Datenbits in ein 7-Bit-Codewort mithilfe von 3 Paritätsbits, die an Zweierpotenz-Positionen platziert sind.

Wie funktioniert die Syndrom-Decodierung?

Nach Empfang eines Codeworts multipliziert der Decoder es mit der Paritätsprüfmatrix H, um einen Syndromvektor s = H·r mod 2 zu erzeugen. Ist s = 0, liegen keine Fehler vor. Ist s ungleich null, gibt sein Binärwert direkt die Position des fehlerhaften Bits an, das dann zur Korrektur invertiert wird.

Was ist SECDED und warum ist es wichtig?

SECDED steht für Single Error Correct, Double Error Detect. Es erweitert Hamming(7,4) zu Hamming(8,4), indem ein zusätzliches Gesamtparitätsbit hinzugefügt wird. Das zusätzliche Bit erhöht den minimalen Hamming-Abstand von 3 auf 4 und ermöglicht es dem Code, jeden Einzelbitfehler zu korrigieren und gleichzeitig jeden Doppelbitfehler zu erkennen (aber nicht zu korrigieren). ECC-RAM in Servern nutzt SECDED, um sich gegen Bitkipper durch kosmische Strahlung oder Spannungsschwankungen zu schützen.

Wo werden Hamming-Codes in der Praxis eingesetzt?

Hamming-Codes werden in ECC-RAM in Servern und Workstations, in Satellitenkommunikationsverbindungen, in DRAM-Speichercontrollern, in manchen NAND-Flash-Speichersystemen und historisch in der Telekommunikation verwendet. Sie sind die konzeptionelle Grundlage für fortgeschrittenere Codes wie Reed-Solomon und Turbocodes.

Warum werden Paritätsbits an Zweierpotenz-Positionen platziert?

Die Positionen 1, 2, 4, 8, … (Zweierpotenzen) werden gewählt, damit jedes Paritätsbit eine eindeutige Teilmenge von Datenpositionen abdeckt, die durch das entsprechende Bit der binären Positionsnummer definiert wird. Dies stellt sicher, dass das Syndrom jedes Einzelbitfehlers die Fehlerposition direkt binär codiert, was die Korrektur ohne Nachschlagetabelle einfach macht.

Was ist der Hamming-Abstand?

Der Hamming-Abstand zwischen zwei Binärstrings ist die Anzahl der Positionen, an denen sie sich unterscheiden. Der minimale Hamming-Abstand d_min eines Codes bestimmt seine Fehlerkorrekturfähigkeit: Ein Code kann bis zu floor((d_min-1)/2) Fehler korrigieren und bis zu d_min-1 Fehler erkennen. Hamming(7,4) hat d_min = 3, korrigiert also 1 Fehler; SECDED hat d_min = 4, korrigiert 1 und erkennt 2.

Wie hoch ist die Coderate von Hamming(7,4)?

Die Coderate ist das Verhältnis von Datenbits zu gesamten Codewortbits. Für Hamming(7,4) beträgt die Rate 4/7 ≈ 0,571, was bedeutet, dass etwa 57 % der übertragenen Bits Informationen tragen und 43 % Redundanz sind. Mit wachsender Blockgröße werden Hamming-Codes effizienter: Hamming(15,11) hat eine Rate von 11/15 ≈ 0,733.

Können Hamming-Codes mehr als einen Bitfehler korrigieren?

Standard-Hamming(7,4) kann nur Einzelbitfehler korrigieren. Werden zwei Bits gekippt, zeigt das Syndrom auf eine falsche Position, und der Decoder verschlimmert die Sache, statt sie zu verbessern. SECDED kann Doppelbitfehler erkennen (aber nicht korrigieren). Zur Korrektur mehrerer Fehler werden stärkere Codes wie Reed-Solomon, LDPC oder Turbocodes verwendet.

Wie wird die Paritätsprüfmatrix H konstruiert?

Für Hamming(7,4) ist jede Spalte von H die Binärdarstellung der Spaltenposition (1 bis 7). Spalte 1 = 001, Spalte 2 = 010, Spalte 3 = 011 und so weiter. Die Zeilen entsprechen den Paritätsprüfungen s1, s2, s4. Das Syndrom s = H·r isoliert die Fehlerposition, da jede Bitposition eine eindeutige binäre Codierung als Spalte von H besitzt.

Was ist der Unterschied zwischen Fehlererkennung und Fehlerkorrektur?

Fehlererkennung bedeutet, dass der Empfänger feststellen kann, dass etwas schiefgelaufen ist (und eine erneute Übertragung anfordern kann), es aber nicht beheben kann. Fehlerkorrektur bedeutet, dass der Empfänger genügend Redundanz besitzt, um die Originaldaten ohne erneute Übertragung zu rekonstruieren. Hamming-Codes bieten beides: Sie erkennen bis zu 2 Fehler und korrigieren 1, was sie ideal für Kanäle macht, bei denen eine erneute Übertragung unpraktisch ist, wie etwa bei der Kommunikation im tiefen Weltraum oder bei RAM.