Fehlererkennende & -korrigierende Verfahren
IMP Klasse 8 · Gymnasium Baden-Württemberg
🎯 Worum geht's? Klasse 8 · 2 Unterrichtsstunden
Nach dieser Seite kannst du …
- erklären, warum bei der Übertragung von Daten Fehler entstehen
- mit Wiederholung und Paritätsbit Übertragungsfehler erkennen
- mit dem Hamming-Code einen Fehler nicht nur erkennen, sondern auch korrigieren
Vorwissen: Binärzahlen (0 und 1)
Digitale Daten können bei der Übertragung verfälscht werden – ein Bit kippt von 0 auf 1 oder umgekehrt. Die folgenden Verfahren helfen dabei, solche Fehler zu erkennen oder sogar zu korrigieren.
📊 Übersicht aller Verfahren
| Verfahren | Zusatzbits | Fehler erkennen | Fehler korrigieren | Effizienz |
|---|---|---|---|---|
| Repetition (n×) | (n−1) Kopien | ✅ bis zu ⌊n/2⌋ | ✅ bis zu ⌊(n−1)/2⌋ ⚠ nur bei ungeradem n |
1/n |
| Parität 1D | 1 Bit | ✅ ungerade Fehler | ❌ | k/(k+1) |
| Parität 2D | Zeile + Spalte | ✅ | ✅ 1 Bit | n·m/((n+1)·(m+1)) |
| 3-Kreis-Hamming | 3 Bits | ✅ | ✅ 1 Bit | 4/7 ≈ 57 % |
| Hamming (allg.) | r = ⌈log₂(n+1)⌉ | ✅ | ✅ 1 Bit | k/(k+r) |
1. Repetitionsverfahren erkennt & korrigiert
Beim Repetitionsverfahren wird jedes Datenbit n-mal hintereinander gesendet. Der Empfänger entscheidet anhand der Mehrheit, welcher Wert gemeint war.
Empfangen: 1 0 1 0 0 0
Mehrheit: 1 (2×1, 1×0) 0 (3×0) ✓
| n | Erkennbar | Korrigierbar | Besonderheit |
|---|---|---|---|
| 3× | 1 Fehler | 1 Fehler | Standard |
| 4× | 2 Fehler | ❌ Bei 2×2 Gleichstand | Gerades n: kein eindeutiger Entscheid möglich |
| 5× | 2 Fehler | 2 Fehler | Aufwändiger, aber zuverlässiger |
2. Paritätsbit (1D) erkennt Fehler
Ein zusätzliches Prüfbit p0 wird so gewählt, dass die Gesamtanzahl der Einsen im Codewort gerade ist (gerade Parität). p0 ist das XOR aller Datenbits.
Codewort: 1 0 1 1 1
Prüfung beim Empfang: XOR aller Bits
→ Ergebnis 0: kein Fehler
→ Ergebnis 1: Fehler erkannt (Position unbekannt!)
3. Paritätsbit (2D) korrigiert 1 Fehler
Die Datenbits werden in einer Matrix angeordnet. Für jede Zeile und jede Spalte wird ein eigenes Prüfbit berechnet (XOR). Fehlerhafte Zeile und fehlerhafte Spalte „zeigen" auf das falsche Bit.
Z1: 1 0 1 | 0
Z0: 1 1 0 | 0
pS: 0 1 1 | 0
Fehlersuche: Welche Zeile hat XOR ≠ 0? Welche Spalte? Der Schnittpunkt ist das fehlerhafte Bit → einfach umkehren (0↔1).
4. 3-Kreis-Hamming-Code korrigiert 1 Fehler
Genau 4 Datenbits (d3 d2 d1 d0) werden auf drei Kreise A, B, C verteilt. Jeder Kreis enthält 3 Datenbits und 1 Prüfbit (p0, p1, p2). Das Prüfbit sorgt dafür, dass in jedem Kreis die Anzahl der Einsen gerade ist.
Kreis B: p1, d0, d2, d3 → p1 = d0⊕d2⊕d3
Kreis C: p2, d1, d2, d3 → p2 = d1⊕d2⊕d3
Fehlersuche mit dem Syndrom:
sA = p0⊕d0⊕d1⊕d3 | sB = p1⊕d0⊕d2⊕d3 | sC = p2⊕d1⊕d2⊕d3
Fehlerposition (Hamming) = sA·1 + sB·2 + sC·4
0 = kein Fehler, 1–7 = Position des fehlerhaften Bits
5. Hamming-Code (allgemein) korrigiert 1 Fehler
Der allgemeine Hamming-Code funktioniert für beliebig viele Datenbits. Die Prüfbits stehen immer an den Positionen, die Zweierpotenzen sind: 1, 2, 4, 8, … (von rechts gezählt).
- Anzahl Prüfbits r bestimmen: kleinstes r mit 2r ≥ k + r + 1
- Datenbits an alle Positionen eintragen, die keine Zweierpotenz sind
- Prüfbit pi = XOR aller Bits, deren Position Bit i gesetzt hat
Bit: d3 d2 d1 p2 d0 p1 p0
Wert: 1 0 1 0 1 0 1
Pos.7 d3: 1 1 1
Pos.5 d1: 1 0 1
Pos.3 d0: 0 1 1
HP: 0 0 1
HP = empfangene Prüfbits ablesen.
Alle Datenbits mit Wert 1 untereinander schreiben (Hamming-Position binär).
XOR aus HP und allen Datenbit-Zeilen = Syndrom S.
S = 0 → kein Fehler | S ≠ 0 → S ist die Position des Fehlers (dezimal).
📤 Sender
Verfahren Nachricht (Binär, MSB links)📡 Übertragungskanal
📋 Protokoll
📥 Empfänger
📋 Protokoll
📜 Verlauf (letzte 10)
| # | Verfahren | Schw. | Aufgabe | Erg. | XP |
|---|
🧪 Diagnose & Test
Teste dein Wissen systematisch – wähle Umfang und Verfahren.
⚙️ Test konfigurieren
📄 Arbeitsblatt-Export
Erstelle individuell zusammengestellte Arbeitsblätter als PDF – mit oder ohne Lösungen.