Hamming-Code-Fehlerkorrektur erklärt (mit Mathematik)

Hamming(7,4) kodieren, ein Syndrom berechnen, jede Einbitposition korrigieren, zu SECDED erweitern und den Decoder prüfen, ohne seine Grenzen zu überzeichnen.

Denny

7. Mai 20267 Min. Lesezeit

Chalkboard feature illustration for “Hamming-Code-Fehlerkorrektur erklärt (mit Mathematik)”

Kurz gesagt: Hamming(7,4) ordnet vier Datenbits sieben Positionen zu. Drei Paritätsprüfungen geben jeder Position eine eindeutige, von null verschiedene Drei-Bit-Spalte; ein einzelnes gekipptes Bit erzeugt deshalb ein Syndrom, das dem Binärindex dieser Position entspricht. Der Decoder kann es dann invertieren. Einfaches Hamming(7,4) kann einen Zwei-Bit-Fehler nicht von manchen Ein-Bit-Fehlern unterscheiden; ein Gesamtparitätsbit erweitert es unter der angenommenen Fehlergrenze zu SECDED.

Ein Paritätsbit kann melden, dass sich eine ungerade Anzahl von Positionen geändert hat, aber eine einzelne Prüfung kann nicht sagen, welche Position es ist. Hammings Konstruktion verwendet mehrere überlappende Paritätsprüfungen. Das Muster fehlgeschlagener Prüfungen – das Syndrom – fungiert als Adresse.

Diese Idee ist mächtig, weil sich Encoder, Prüfer und Korrektor vollständig aus XOR-Netzwerken und Dekodierlogik aufbauen lassen. Sie hat auch eine klare Grenze: Die bekannte Korrekturregel setzt höchstens einen Fehler im geschützten Block voraus, sofern ein erweiterter Code nicht eine weitere Prüfung ergänzt.

Positionierung der Bits

Nummerieren Sie die Codewortpositionen ab 1. Zweierpotenzen enthalten Paritätsbits:

Position	1	2	3	4	5	6	7
Rolle	$P_1$	$P_2$	$D_1$	$P_4$	$D_2$	$D_3$	$D_4$
Binärindex	001	010	011	100	101	110	111

Jede Paritätsprüfung entspricht einem Bit des binären Positionsindexes:

$P_1$ deckt Positionen ab, deren Index Bit 0 gesetzt hat: 1, 3, 5, 7.
$P_2$ deckt Positionen ab, deren Index Bit 1 gesetzt hat: 2, 3, 6, 7.
$P_4$ deckt Positionen ab, deren Index Bit 2 gesetzt hat: 4, 5, 6, 7.

Jede Position besitzt ein eindeutiges, von null verschiedenes Zugehörigkeitsmuster. Position 5 gehört beispielsweise zu den Prüfungen 1 und 4, weil $5=101_2$ .

Diese einsbasierte Konvention ist praktisch, nicht mystisch: Die Spalten der Paritätsprüfmatrix sind einfach die binären Kennzeichnungen 1 bis 7.

Kodierung mit gerader Parität

Wählen Sie jedes Paritätsbit so, dass das XOR seiner vollständigen Überdeckungsmenge null ist:

P_1=D_1\oplus D_2\oplus D_4

P_2=D_1\oplus D_3\oplus D_4

P_4=D_2\oplus D_3\oplus D_4

Diese Gleichungen machen den Code systematisch: Die ursprünglichen Daten erscheinen unverändert an den Positionen 3, 5, 6 und 7, während die Parität die übrigen Positionen einnimmt.

Auch ungerade Parität wäre möglich, wenn die erwarteten Prüfwerte konsistent angepasst würden. Gerade Parität hält die Form der linearen Algebra besonders direkt, weil jedes gültige Codewort ein Nullsyndrom hat.

Beispielkodierung: Daten 1011

Setzen Sie:

D_1=1,\quad D_2=0,\quad D_3=1,\quad D_4=1

Dann:

P_1=1\oplus0\oplus1=0

P_2=1\oplus1\oplus1=1

P_4=0\oplus1\oplus1=0

Tragen Sie diese Werte in die sieben Positionen ein:

Position	1	2	3	4	5	6	7
Rolle	$P_1$	$P_2$	$D_1$	$P_4$	$D_2$	$D_3$	$D_4$
Bit	0	1	1	0	0	1	1

Liest man die Positionen 1 bis 7, lautet das Codewort:

Einige Texte geben Codewörter in entgegengesetzter visueller Richtung aus. Die Arithmetik bleibt korrekt, wenn die Positionskonvention ausdrücklich angegeben und konsistent verwendet wird.

Berechnung des Syndroms

Seien die empfangenen Positionen $R_1$ bis $R_7$ . Berechnen Sie die vollständigen Paritätsprüfungen erneut:

S_1=R_1\oplus R_3\oplus R_5\oplus R_7

S_2=R_2\oplus R_3\oplus R_6\oplus R_7

S_4=R_4\oplus R_5\oplus R_6\oplus R_7

Interpretieren Sie das Syndrom als:

S=(S_4S_2S_1)_2

Für ein unverändertes gültiges Codewort gilt $S=000$ . Kippt genau eine Position $i$ , so ändert sich jede Prüfung, die $i$ abdeckt. Das resultierende Syndrom ist die dieser Position $i$ zugewiesene Binärspalte.

Korrektur eines Kippens an Position 5

Kippen Sie Position 5 im kodierten Beispiel:

sent:     0 1 1 0 0 1 1
received: 0 1 1 0 1 1 1
position: 1 2 3 4 5 6 7

Jetzt:

S_1=0\oplus1\oplus1\oplus1=1

S_2=1\oplus1\oplus1\oplus1=0

S_4=0\oplus1\oplus1\oplus1=1

Folglich:

S_4S_2S_1=101_2=5

Unter der Annahme eines einzelnen Fehlers invertieren Sie die empfangene Position 5. Das korrigierte Wort wird wieder zu 0110011, und die Positionen 3, 5, 6 und 7 ergeben die Daten 1011.

Ein Kippen einer Paritätsposition funktioniert genauso. Ändert sich Position 2, ist das Syndrom 010, und der Korrektor invertiert Position 2.

Matrixansicht

Mit dem Codewortvektor

\mathbf r=[R_1\ R_2\ R_3\ R_4\ R_5\ R_6\ R_7]^T

ist eine mögliche Paritätsprüfmatrix:

H= \begin{bmatrix} 1&0&1&0&1&0&1\\ 0&1&1&0&0&1&1\\ 0&0&0&1&1&1&1 \end{bmatrix}

Das Syndrom lautet:

\mathbf s=H\mathbf r\pmod 2

Spalte $i$ von H ist die Binärdarstellung von $i$ , geordnet als $(S_1,S_2,S_4)^T$ . Ein Einbit-Fehlervektor mit seiner 1 an Position $i$ liefert daher genau Spalte $i$ zurück.

Diese Formulierung skaliert besser als das Auswendiglernen überlappender Kreise. Sie macht auch die Linearität deutlich: Das XOR zweier gültiger Codewörter ergibt ein weiteres gültiges Codewort.

Warum einfaches Hamming zwei Fehler nicht sicher korrigieren kann

Hamming(7,4) hat die minimale Hamming-Distanz:

d_{\min}=3

Ein Code mit minimaler Distanz $d_{\min}$ kann:

bis zu $d_{\min}-1$ beliebige Fehler erkennen, wenn er nur zwischen gültig und ungültig entscheidet; oder
bis zu $\left\lfloor(d_{\min}-1)/2\right\rfloor$ Fehler korrigieren, indem er das nächstgelegene Codewort wählt.

Hamming(7,4) kann somit einen Fehler korrigieren. Es kann auch eine Zwei-Bit-Verfälschung als „kein Codewort“ erkennen, wenn keine Korrektur versucht wird. Sein von null verschiedenes Drei-Bit-Syndrom kann jedoch nicht sagen, ob es von einem Fehler oder einem bestimmten Fehlerpaar stammt.

Sieht ein Standarddecoder für Einzelfehlerkorrektur einen Zwei-Bit-Fehler, entspricht das XOR der beiden Fehlerpositionsspalten einer dritten, von null verschiedenen Spalte. Der Decoder invertiert diese dritte Position und erzeugt damit eine Drei-Bit-Differenz zum übertragenen Codewort. Das ist eine Fehlkorrektur, keine Zwei-Fehler-Korrektur.

Geben Sie stets das angenommene Fehlermodell des Decoders an. „Syndrom ungleich null, also diese Position kippen“ ist nur gültig, wenn das System festgestellt hat, dass höchstens eine geschützte Position fehlerhaft ist.

Erweitertes Hamming und SECDED

Fügen Sie dem sieben Bit langen Hamming-Wort ein Gesamtparitätsbit $P_0$ hinzu. Der erweiterte Acht-Bit-Code hat $d_{\min}=4$ und unterstützt Einzelfehlerkorrektur, Doppelfehlererkennung (SECDED), sofern ein Codewort nicht mehr als zwei Fehler enthält.

Berechnen Sie:

das ursprüngliche Drei-Bit-Syndrom S aus den Positionen 1–7;
eine Gesamtparitätsprüfung P über alle acht empfangenen Positionen.

Für gerade Gesamtparität:

Syndrom S	Gesamtprüfung P	Interpretation bei 0–2 Fehlern	Aktion
000	0	kein Fehler	akzeptieren
ungleich null	1	ein Fehler an Positionen 1–7	Position S korrigieren
000	1	Fehler in der Gesamtparitätsposition	korrigieren oder Paritätsbitfehler melden
ungleich null	0	zwei Fehler	als nicht korrigierbar melden; nicht einzeln korrigieren

Die Einschränkung ist wichtig. Drei oder mehr Fehler können eine andere Tabellenzeile nachahmen. SECDED ist kein unbegrenzter Fehlerdetektor.

Reale Speicher- und Kommunikationssysteme können verkürzte Hamming-Codes, Interleaving, symbolorientierte Codes, BCH- oder Reed-Solomon-Codes, Low-Density-Parity-Check-Codes, Produktcodes oder proprietäre Verfahren nutzen. Leiten Sie die ECC-Fähigkeit eines Systems nicht allein aus den sichtbaren Breiten seiner Daten- und Prüfbits ab.

Allgemeine Dimensionierung von Hamming-Codes

Für $m$ Datenbits und $r$ Hamming-Paritätsbits müssen genügend Syndrommuster für jede Codewortposition plus den fehlerfreien Fall vorhanden sein:

2^r\ge m+r+1

Die binäre Hamming-Familie voller Länge verwendet:

n=2^r-1

k=n-r=2^r-r-1

Paritätsbits r	Codelänge n	Datenbits k	Vollständiger Code
3	7	4	Hamming(7,4)
4	15	11	Hamming(15,11)
5	31	26	Hamming(31,26)
6	63	57	Hamming(63,57)

Verkürzte Varianten lassen ausgewählte Datenpositionen weg, erhalten aber die Prüfstruktur. Erweiterte Varianten fügen das Gesamtparitätsbit hinzu und erhöhen die Distanz von 3 auf 4.

Beim Overhead muss der Nenner genannt werden. Hamming(7,4) fügt 3 Prüfbits pro 4 Datenbits hinzu – 75 % Overhead bezogen auf die Nutzlast oder 3/7 des übertragenen Worts. Hamming(63,57) fügt 6/57 hinzu, etwa 10,5 % bezogen auf die Nutzlast, und Prüfbits belegen 6/63, etwa 9,5 % des Codeworts.

Hardwarearchitektur

Eine einfache systematische Implementierung besteht aus vier Stufen:

data ─▶ parity generator ─▶ codeword
                              │
received word ─▶ check matrix ─▶ syndrome
                                      │
                       syndrome decoder ─▶ one-hot flip mask
received word ─────────────────────────── XOR ─▶ corrected word ─▶ extract data

Für Hamming(7,4):

Der Encoder berechnet drei Paritätsgleichungen.
Der Prüfer berechnet drei Syndromgleichungen.
Ein 3-zu-8-Decoder kann eine One-Hot-Positionsmaske bilden, wobei Ausgang 0 keine Korrektur bedeutet.
Sieben XOR-Gatter wenden diese Maske an.
Die Verdrahtung extrahiert die Positionen 3, 5, 6 und 7.

Die genaue Gatterzahl und das Timing hängen von der Faktorisierung der XOR-Bäume, gemeinsamen Termen, Zellbibliotheken oder dem FPGA-Mapping ab. Ein breiter Decoder kann Syndromberechnung und Korrektur pipelinen. Wenn ein Flag- oder Statusregister „korrigiert“ und „nicht korrigierbar“ meldet, richten Sie diese Signale an der entsprechenden Datenpipeline-Stufe aus.

Prüfplan

Für den Sieben-Bit-Code:

Kodieren Sie alle 16 möglichen Dateneingaben.
Bestätigen Sie, dass jedes kodierte Wort ein Nullsyndrom hat.
Kippen Sie für jedes Codewort jede der sieben Positionen einzeln.
Bestätigen Sie, dass das Syndrom der gekippten Position entspricht.
Wenden Sie die Korrektur an und bestätigen Sie, dass alle 16×7 Fälle die ursprünglichen Daten wiederherstellen.
Injizieren Sie repräsentative Zwei-Bit-Fehler und zeigen Sie, weshalb ein einfacher Einzelfehlerdecoder fehlkorrigiert.

Für die erweiterte Acht-Bit-Version:

Wiederholen Sie jeden Einpositions-Test, einschließlich der Gesamtparitätsposition.
Testen Sie für jedes Datenwort alle $\binom82=28$ Zwei-Positions-Muster.
Bestätigen Sie, dass jedes Paar als nicht korrigierbar gemeldet und keines einzeln korrigiert wird.
Fügen Sie Assertions hinzu, dass die Korrektur nur bei S != 0 und einer Gesamtparitätsabweichung aktiviert ist.

Die funktionale Simulation beweist die implementierte Wahrheitstabelle für getestete oder vollständig aufgezählte Bitmuster. Sie liefert keine physische Soft-Error-Rate, begründet keine Unabhängigkeit von Fehlern und ersetzt keine Zuverlässigkeitsanalyse auf Systemebene.

Häufige Entwurfsfehler

Positionen ab null nummerieren und das Syndrom dennoch als einsbasierte Adresse interpretieren.
Das Wort in umgekehrter Reihenfolge ausgeben, ohne die Konvention zu dokumentieren.
Kodierung mit gerader Parität und Prüfung mit ungerader Parität vermischen.
Jedes von null verschiedene Syndrom korrigieren, ohne die Fehlerzahl zu begrenzen.
SECDED als Erkennung jedes Fehlers mit Gewicht drei oder mehr behandeln.
Vergessen, dass Prüfbits und das Gesamtparitätsbit ausfallen können.
„Overhead-Prozentsätze“ mit unterschiedlichen Nennern vergleichen.
Annehmen, dass alle als ECC bezeichneten Produkte denselben Code implementieren.

Hamming(7,4) ist wertvoll, weil sein vollständiger Mechanismus sichtbar ist: eindeutige Spalten der Paritätsprüfungen machen aus einem Einbitfehler eine Adresse. Sobald das klar ist, erscheint einfache Parität als einzeilige Prüfmatrix, während stärkere Blockcodes größere Ausführungen derselben zentralen Idee werden – strukturierte Redundanz, abgestimmt auf ein explizites Fehlermodell.

Referenz

R. W. Hamming, „Error Detecting and Error Correcting Codes“, Bell System Technical Journal, 1950