MINT lernen

Abituraufgaben: Fehlerkorrektur: Hamming-Code

Zwei Abituraufgaben zum (7,4)-Hamming-Code — vom Codieren bis zur Doppelfehlererkennung in Java.

Dein Fortschritt:
0 / 0 Aufgaben
1

Messdaten eines Kleinsatelliten

14 BEAFB I–II

Ein Kleinsatellit überträgt Messdaten in Blöcken zu 4 Bit. Weil ein Neusenden wegen der Funkfenster nur selten möglich ist, wird jeder Block mit dem (7,4)-Hamming-Code gesichert. Die Bits stehen in der Reihenfolge p0 p1 d0 p2 d1 d2 d3; die Kontrollgruppen entsprechen der Anlage der Abitur-Hinweise (p0: d0 d1 d3, p1: d0 d2 d3, p2: d1 d2 d3), jede Gruppe hat gerade Parität.

  1. Wenden Sie den (7,4)-Hamming-Code auf die Datenwörter 1100 und 0010 (d0 d1 d2 d3) an. (4 BE)
  2. Empfangen werden 0010001, 0011111, 1011010. Ermitteln Sie jeweils das Syndrom, korrigieren Sie gegebenenfalls und geben Sie die Datenbits an. (5 BE)
  3. Begründen Sie, warum die Prüfbits an den Stellen 1, 2 und 4 stehen und das Syndrom direkt die Fehlerstelle liefert. (3 BE)
  4. Vergleichen Sie den Hamming-Code mit einem Paritätsbit je 4 Datenbits hinsichtlich Aufwand und Leistung. (2 BE)

Hinweise

Hinweis zu Aufgabe a)
Prüfbits mit der Gruppentabelle, dann Reihenfolge p0 p1 d0 p2 d1 d2 d3.
Hinweis zu Aufgabe b)
s0: Stellen 1, 3, 5, 7; s1: 2, 3, 6, 7; s2: 4, 5, 6, 7.
Hinweis zu Aufgabe c)
Schreiben Sie die Stellen 1 bis 7 als Dualzahl.
Hinweis zu Aufgabe d)
Prüfbits je 4 Datenbits zählen.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

1100 → p0 = 0, p1 = 1, p2 = 1 → 0111100; 0010 → p0 = 0, p1 = 1, p2 = 1 → 0101010.

Erwartungshorizont zu Aufgabe b)

0010001: s0 = 0, s1 = 0, s2 = 1 → Stelle 4, korrigiert 0011001, Daten 1001
0011111: s0 = 1, s1 = 1, s2 = 0 → Stelle 3, korrigiert 0001111, Daten 0111
1011010: s0 = 0, s1 = 0, s2 = 0 → kein Fehler, Daten 1010

Erwartungshorizont zu Aufgabe c)

Jede Stelle 1–7 ist eindeutig als Summe von 1, 2 und 4 darstellbar. Ein Bit gehört genau zu den Gruppen, deren Stellenwert in seiner Summe vorkommt; die Prüfbits (Zweierpotenzen) gehören nur zu ihrer eigenen Gruppe. Kippt ein Bit, werden genau diese Gruppen ungerade — \(s_0+2s_1+4s_2\) ergibt seine Stelle.

Erwartungshorizont zu Aufgabe d)

Parität: 5 Bit je 4 Datenbits (80 % Nutzdaten), erkennt Einzelfehler, korrigiert nicht. Hamming: 7 Bit (57 % Nutzdaten), erkennt und korrigiert Einzelfehler. Beide versagen bei Doppelfehlern (Parität erkennt sie nicht, Hamming korrigiert falsch).

2

Ein Decoder für die Bodenstation

16 BEAFB II–III

Die Bodenstation speichert ein empfangenes Codewort als Reihung int[] c mit c[0] = p0, c[1] = p1, c[2] = d0, …, c[6] = d3. Gegeben sind die Methoden aus dem Unterricht:

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
    }
}
  1. Stellen Sie die Operation fehlerstelle(c: Reihung von Ganzzahl): Ganzzahl als Struktogramm dar. (3 BE)
  2. Implementieren Sie eine Methode static int[] decodiere(int[] c), die ein empfangenes Codewort korrigiert und die vier Datenbits d0 bis d3 zurückgibt. korrigiere darf verwendet werden. (4 BE)
  3. Gesendet wird 1001100, empfangen 0001110. Analysieren Sie das Verhalten von decodiere. (4 BE)
  4. Ein achtes Bit c[7] ergänzt das Codewort so, dass alle 8 Bits gerade Parität haben. Erweitern Sie das Verfahren zu einer Methode static int pruefe(int[] c), die 0 (fehlerfrei), 1 (Einzelfehler korrigiert) oder 2 (Doppelfehler, neu anfordern) zurückgibt. (5 BE)

Hinweise

Hinweis zu Aufgabe a)
Drei Zuweisungen, eine Rückgabe — keine Schleife nötig.
Hinweis zu Aufgabe b)
Welche Indizes haben d0, d1, d2, d3?
Hinweis zu Aufgabe c)
Syndrom berechnen, dann mit dem Gesendeten vergleichen.
Hinweis zu Aufgabe d)
Kombinieren Sie Syndrom und Gesamtparität: Welche vier Fälle gibt es?

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)
Erwartungshorizont zu Aufgabe b)
public static int[] decodiere(int[] c) {
    korrigiere(c);                               // Einzelfehler beheben
    return new int[] {c[2], c[4], c[5], c[6]};   // d0 d1 d2 d3
}

Für {0, 1, 1, 0, 1, 1, 1} liefert die Methode {1, 0, 1, 1}.

Erwartungshorizont zu Aufgabe c)

Gekippt sind die Stellen 1 und 6. Syndrom: s0 = 1, s1 = 1, s2 = 1 → Stelle 7. korrigiere kippt Stelle 7: 0001111, Daten 0111 statt 0100. Der Doppelfehler wird nicht erkannt, sondern „falsch korrigiert“; drei Bits sind jetzt falsch.

Erwartungshorizont zu Aufgabe d)
public static int pruefe(int[] c) {             // c[0..6] Hamming, c[7] Gesamtparität
    int stelle = fehlerstelle(c);
    int einsen = 0;
    for (int i = 0; i < 8; i++) {
        einsen = einsen + c[i];
    }
    boolean gesamtOk = einsen % 2 == 0;
    if (stelle == 0 && gesamtOk) {
        return 0;                                // fehlerfrei
    }
    if (!gesamtOk) {                             // ungerade Anzahl Fehler: Einzelfehler
        if (stelle > 0) {
            c[stelle - 1] = 1 - c[stelle - 1];
        } else {
            c[7] = 1 - c[7];                     // nur das Gesamtparitätsbit gekippt
        }
        return 1;                                // korrigiert
    }
    return 2;                                    // Doppelfehler: neu anfordern
}

Ungerade Gesamtparität ↔ ungerade Anzahl Fehler (bei höchstens zwei: genau einer). Syndrom ≠ 0 bei gerader Gesamtparität ↔ Doppelfehler. Alle 16 Codewörter mit allen Einzel- und Doppelfehlern wurden damit geprüft.