Hamming Code und LDPC: Fehlerkorrektur interaktiv verstehen
Interaktive Demos für Fehlerkorrekturcodes: Hamming(7,4) zeigt die direkte 1-Bit-Korrektur, der LDPC-Tanner-Graph zeigt Paritätsprüfungen und einfache Bit-Flipping-Korrektur.
Passender Hintergrund: Dieses Tool ergänzt den Bericht Fehlerkorrekturcodes in biometrischen Authentifizierungssystemen. Hamming(7,4) ist bewusst einfach gewählt, damit Syndrom und Fehlerkorrektur direkt sichtbar werden.
Fehlerkorrekturcodes bauen gezielt Redundanz in Daten ein. Dadurch kann ein Empfänger erkennen, ob ein Bitmuster noch zu den gültigen Codewörtern passt. Hamming(7,4) zeigt dieses Prinzip sehr direkt: Ein einzelner Bitfehler erzeugt ein Syndrom, das unmittelbar auf die fehlerhafte Position zeigt. LDPC-Codes gehen einen Schritt weiter und beschreiben viele einfache Paritätsprüfungen als dünn besetztes Netz aus Bits und Prüfungen. Genau dieses Netz wird als Tanner-Graph dargestellt.
Interaktiver Hamming(7,4)-Demonstrator
Hamming(7,4) nimmt 4 Datenbits und ergänzt 3 Paritätsbits. Damit entsteht ein 7-Bit-Codewort, das genau einen Bitfehler erkennen und korrigieren kann.
1. Datenbits eingeben
2. Codewort
Positionen 1, 2 und 4 sind Paritätsbits. Positionen 3, 5, 6 und 7 enthalten die Datenbits.
3. Fehler simulieren
Klicke ein Bit im empfangenen Wort an, um einen Übertragungsfehler zu simulieren.
4. Syndrom und Korrektur
Korrigiertes Codewort
Korrigierte Datenbits
Prüfmatrix H
[0 1 1 0 0 1 1]
[0 0 0 1 1 1 1]
Die Spalten der Matrix entsprechen den Bitpositionen 1 bis 7. Das Syndrom zeigt bei einem 1-Bit-Fehler direkt auf die Spalte und damit auf die fehlerhafte Position.
LDPC-Code als Tanner-Graph
Low Density Parity Check Codes werden häufig über einen Tanner-Graph dargestellt. Links stehen die Daten- beziehungsweise Codebits, rechts die Paritätsprüfungen. Jede Verbindung bedeutet: Dieses Bit ist Teil dieser Prüfung.
Der Begriff „low density“ bedeutet, dass jede Paritätsprüfung nur wenige Bits betrachtet und jedes Bit nur in wenigen Prüfungen vorkommt. Dadurch bleibt die Prüfmatrix groß, aber dünn besetzt. Das ist praktisch, weil der Decoder nicht eine riesige Gleichung auf einmal lösen muss, sondern viele lokale Prüfungen auswertet.
In der Grafik sind die runden Knoten Variablenknoten \(v1\) bis \(v6\). Sie stehen für die Bits des Codeworts. Die rechteckigen Knoten c1 bis c3 sind Prüfknoten. Eine Prüfung ist erfüllt, wenn die XOR-Summe aller verbundenen Bits 0 ergibt. Ist die XOR-Summe 1, ist diese Prüfung verletzt und wird rot markiert.
Codewort prüfen
[0 1 1 0 1 0]
[1 0 1 0 0 1]
Tanner-Graph
Rot markierte Prüfknoten sind verletzt. Ein einfacher Bit-Flipping-Decoder zählt, welches Bit an den meisten verletzten Prüfungen beteiligt ist. Das ist nicht der vollständige LDPC-Decoder moderner Kommunikationssysteme, zeigt aber die Grundidee: Fehler werden über mehrere lokale Paritätsprüfungen eingegrenzt.
Was zeigt der LDPC-Tanner-Graph?
Ein Tanner-Graph macht sichtbar, welche Bits gemeinsam geprüft werden. Im kleinen Beispiel gilt:
c1 prüft: v1 XOR v2 XOR v4 = 0 c2 prüft: v2 XOR v3 XOR v5 = 0 c3 prüft: v1 XOR v3 XOR v6 = 0
Wenn ein einzelnes Bit kippt, werden genau die Prüfungen verletzt, an denen dieses Bit beteiligt ist. Der Bit-Flipping-Schritt sucht deshalb das Bit, das in den meisten verletzten Prüfungen vorkommt, und kippt es zurück. Bei großen LDPC-Codes wird dieses Prinzip iterativ und mit Wahrscheinlichkeiten beziehungsweise Zuverlässigkeitswerten erweitert.
Datenkorrektur als Code
Für echte Anwendungen ist die Demonstration nur der erste Schritt. Entscheidend ist, dass die Korrektur reproduzierbar im Code umgesetzt wird. Hier sind kompakte Beispiele für Hamming(7,4) in Python, Structured Text und C.
Python
def hamming74_correct(bits):
# bits: Liste mit 7 Werten, Positionen 1..7 werden intern 0..6 adressiert
s1 = bits[0] ^ bits[2] ^ bits[4] ^ bits[6]
s2 = bits[1] ^ bits[2] ^ bits[5] ^ bits[6]
s4 = bits[3] ^ bits[4] ^ bits[5] ^ bits[6]
position = s1 + 2 * s2 + 4 * s4
corrected = bits[:]
if 1 <= position <= 7:
corrected[position - 1] ^= 1
data = [corrected[2], corrected[4], corrected[5], corrected[6]]
return corrected, data, positionStructured Text (IEC 61131-3)
s1 := bits[1] XOR bits[3] XOR bits[5] XOR bits[7];
s2 := bits[2] XOR bits[3] XOR bits[6] XOR bits[7];
s4 := bits[4] XOR bits[5] XOR bits[6] XOR bits[7];
errorPosition := BOOL_TO_INT(s1) + 2 * BOOL_TO_INT(s2) + 4 * BOOL_TO_INT(s4);
IF (errorPosition >= 1) AND (errorPosition <= 7) THEN
bits[errorPosition] := NOT bits[errorPosition];
END_IF;
data[1] := bits[3];
data[2] := bits[5];
data[3] := bits[6];
data[4] := bits[7];C
int hamming74_correct(unsigned char bits[7], unsigned char data[4]) {
int s1 = bits[0] ^ bits[2] ^ bits[4] ^ bits[6];
int s2 = bits[1] ^ bits[2] ^ bits[5] ^ bits[6];
int s4 = bits[3] ^ bits[4] ^ bits[5] ^ bits[6];
int position = s1 + 2 * s2 + 4 * s4;
if (position >= 1 && position <= 7) {
bits[position - 1] ^= 1;
}
data[0] = bits[2];
data[1] = bits[4];
data[2] = bits[5];
data[3] = bits[6];
return position;
}Einordnung
Die Hamming-Demo zeigt den einfachsten Fall sehr klar: Ein einzelner Fehler erzeugt ein eindeutiges Syndrom und kann direkt korrigiert werden. Der LDPC-Teil zeigt die gleiche Grundidee in einer graphischen Form: Viele lokale Paritätsprüfungen liefern Hinweise darauf, welche Bits wahrscheinlich fehlerhaft sind.
In echten Systemen werden solche Verfahren größer und robuster aufgebaut. Statt nur sieben oder sechs Bits werden lange Codewörter verwendet, und die Korrektur läuft iterativ über viele Prüfungen. Das Prinzip bleibt aber gleich: Redundanz macht Fehler sichtbar und ermöglicht, verrauschte Daten wieder in ein gültiges Bitmuster zurückzuführen.