Fehlerkorrektur: Hamming-Code

Ein Paritätsbit meldet einen Fehler, findet ihn aber nicht (8.3.3). Der (7,4)-Hamming-Code nutzt drei Paritätsbits auf überlappenden Gruppen — zusammen zeigen sie auf das gekippte Bit.

• Aufbau:4 Datenbits d0–d3 und 3 Prüfbits p0–p2, notiert als p0 p1 d0 p2 d1 d2 d3 (Stellen 1 bis 7).
• Kontrollgruppen:jedes Prüfbit sichert drei Datenbits (Tabelle); jedes Datenbit liegt in mindestens zwei Gruppen.
• Prüfbits:jede Gruppe erhält gerade Parität: \(p_0=(d_0+d_1+d_3)\bmod 2\), \(p_1=(d_0+d_2+d_3)\bmod 2\), \(p_2=(d_1+d_2+d_3)\bmod 2\).
• Beispiel:\(d_0d_1d_2d_3=1011\): \(p_0=0,\ p_1=1,\ p_2=0\) → 0 1 1 0 0 1 1.

Klicke ein Bit des Codeworts an, um es im Kanal kippen zu lassen. Wähle dann eine Schablone und ziehe sie am Griff rechts nach oben auf das Codewort (Tastatur: Griff mit Tab, dann ↑). Die Schablone lässt nur ihre Kontrollgruppe durchscheinen und misst deren Parität. Miss alle drei — ▶ führt es vor.

Halte fest: Jede Schablone misst eine Kontrollgruppe. Die drei Messwerte \(s_0, s_1, s_2\) ergeben zusammen die Stelle des gekippten Bits — ohne dass der Empfänger das Original kennt.

• Prüfen:der Empfänger bildet je Gruppe die Parität mit Prüfbit: \(s_0\) (Stellen 1, 3, 5, 7), \(s_1\) (2, 3, 6, 7), \(s_2\) (4, 5, 6, 7).
• Syndrom:\(s_2s_1s_0\) als Dualzahl ist die Stelle des gekippten Bits; \(000\) heißt: kein Fehler erkannt.

• Zwei Fehler:das Syndrom ist nicht 000, zeigt aber auf eine falsche Stelle — die „Korrektur“ kippt ein drittes Bit.
• Aufwand:4 Datenbits in 7 Bit: Coderate \(\tfrac{4}{7}\approx 57\,\%\) (Paritätsbit bei 7 Datenbits: \(\tfrac{7}{8}\)).

public static int[] codiere(int d0, int d1, int d2, int d3) {
    int p0 = (d0 + d1 + d3) % 2;
    int p1 = (d0 + d2 + d3) % 2;
    int p2 = (d1 + d2 + d3) % 2;
    return new int[] {p0, p1, d0, p2, d1, d2, d3};
}

public static int fehlerstelle(int[] c) {       // c = p0 p1 d0 p2 d1 d2 d3
    int s0 = (c[0] + c[2] + c[4] + c[6]) % 2;   // Gruppe p0: d0 d1 d3
    int s1 = (c[1] + c[2] + c[5] + c[6]) % 2;   // Gruppe p1: d0 d2 d3
    int s2 = (c[3] + c[4] + c[5] + c[6]) % 2;   // Gruppe p2: d1 d2 d3
    return s0 + 2 * s1 + 4 * s2;                // 0 = kein Fehler, sonst Stelle
}

public static void korrigiere(int[] c) {
    int stelle = fehlerstelle(c);
    if (stelle > 0) {
        c[stelle - 1] = 1 - c[stelle - 1];      // Index = Stelle − 1
    }
}

Aufruf: codiere(1, 0, 1, 1) liefert {0, 1, 1, 0, 0, 1, 1}; für das empfangene Wort {0, 1, 1, 0, 1, 1, 1} gibt fehlerstelle den Wert 5 zurück, korrigiere setzt c[4] zurück.