Die Paritätsprüfmatrix
Jeder lineare Code über GF(2) – dem Körper mit nur 0 und 1, Arithmetik modulo 2 – hat eine Paritätsprüfmatrix H. Für den (7,4)-Hamming-Code ist H eine 3×7-Matrix, deren Spalten die binären Darstellungen von 1 bis 7 sind:
``
H = [ 0 0 0 1 1 1 1 ] ← bit 2 of position number
[ 0 1 1 0 0 1 1 ] ← bit 1 of position number
[ 1 0 1 0 1 0 1 ] ← bit 0 of position number
``
Spalte j von H ist die binäre Darstellung von j. Deshalb benennt das Syndrom s = Hr direkt die Fehlerposition.
Die Abbildung H: GF(2)^7 → GF(2)^3 ist eine lineare Abbildung (Matrixmultiplikation mod 2). Ihr Kern ker(H) = { r : Hr = 0 } ist genau die Menge der gültigen Codeworte.
Dimensionszählung: dim(ker H) = 7 − rank(H) = 7 − 3 = 4. Also gibt es 2^4 = 16 Codeworte. Dies bestätigt 4 Nachrichtenbits.
Der Code als ein Kern
Ein Wort c ∈ {0,1}^7 ist ein gültiges Codewort genau dann, wenn Hc = 0 (mod 2). Dies ist die definierende Gleichung eines linearen Codes.
Beispiel: c = 0011001. Überprüfen Sie Hc mod 2:
``
Zeile 1: 0·0+0·0+0·1+1·1+1·0+1·0+1·1 = 0+0+0+1+0+0+1 = 2 ≡ 0
Zeile 2: 0·0+1·0+1·1+0·1+0·0+1·0+1·1 = 0+0+1+0+0+0+1 = 2 ≡ 0
Zeile 3: 1·0+0·0+1·1+0·1+1·0+0·0+1·1 = 0+0+1+0+0+0+1 = 2 ≡ 0
``
Hc = 000. Also ist 0011001 ein gültiges Codewort.
Nebenklassen des Codes
Die Codeworte C = ker(H) bilden eine Untergruppe von GF(2)^7. Jedes andere Wort in GF(2)^7 gehört zu genau einer Nebenklasse von C.
Nebenklassendefinition: für jedes Wort e ist die Nebenklasse C + e = { c + e : c ∈ C }.
Zwei Worte gehören zur gleichen Nebenklasse genau dann, wenn ihre Differenz ein Codewort ist – äquivalent, wenn sie das gleiche Syndrom haben: H(r₁) = H(r₂) genau dann wenn H(r₁ − r₂) = 0 genau dann wenn r₁ − r₂ ∈ C.
Die Syndrom-Abbildung H induziert einen Isomorphismus GF(2)^7 / C ≅ GF(2)^3. Mit |C| = 16 und |GF(2)^7| = 128: es gibt genau 128/16 = 8 Nebenklassen, eine für jeden Syndromwert in GF(2)^3.
Standard-Array: listen Sie einen Nebenklassen-Führer pro Nebenklasse auf – das Wort minimaler Hamming-Gewicht in dieser Nebenklasse. Für die Korrektur einzelner Fehler entspricht jedes Nicht-Null-Syndrom eindeutig einem Gewicht-1-Fehlermuster (eine einzelne 1 an einer von 7 Positionen). Deshalb 7 Fehlermuster + 1 Kein-Fehler = 8 Nebenklassen = 2^3.
Decodierung über Nebenklassen-Führer
Decodierungsalgorithmus: empfangen Sie r → berechnen Sie s = Hr → schauen Sie den Nebenklassen-Führer e_s auf (das kanonische Fehlermuster für Syndrom s) → geben Sie r − e_s = r + e_s aus (gleich in GF(2)).
Für den (7,4)-Code sind die 8 Nebenklassen-Führer: 0000000 (Syndrom 000), 1000000 (Syndrom 001), 0100000 (Syndrom 010), 0010000 (Syndrom 011), 0001000 (Syndrom 100), 0000100 (Syndrom 101), 0000010 (Syndrom 110), 0000001 (Syndrom 111).
Warum (7,4) perfekt ist
Ein Code C ⊆ GF(2)^n mit Mindestabstand 3 korrigiert alle Einzelfehler. Jedes Codewort c hat einen Hamming-Ball mit Radius 1: das Zentrum c und seine n unmittelbaren Nachbarn (Gewicht-1-Fehlermuster). Ball-Volumen = 1 + n.
Für n = 7: Ball-Volumen = 8. Mit 16 Codewortern: 16 × 8 = 128 = 2^7. Die Bälle kacheln GF(2)^7 perfekt – kein Punkt bleibt unbedeckt, kein Punkt wird zweimal bedeckt.
Dies ist die Definition eines perfekten Codes: M · Vol(n, t) = 2^n. Perfekte Einzelfehler-korrigierende Codes (t=1) existieren nur für spezifische Parameter: (7,4), (15,11), (23,12) (der binäre Golay-Code), und trivial n = 2^r − 1, k = n − r für jedes r ≥ 2.
Die Geometrie: GF(2)^7 zerlegt sich in genau 8 Umlaufbahnen unter der Wirkung des Codes als Nebenklassen-Partition. Jede Umlaufbahn ist eine Nebenklasse; jede Nebenklasse hat ein eindeutiges Syndrom. Die Syndrom-Abbildung H ist eine Bijektion von Nebenklassen zu GF(2)^3.
Das Zählargument
Für einen perfekten Einzelfehler-korrigierenden Code auf n = 2^r − 1 Bits mit r Paritätsprüf-Bits:
- Anzahl der Codeworte: M = 2^k = 2^(n−r)
- Ball-Volumen: Vol(n, 1) = 1 + n = 1 + 2^r − 1 = 2^r
- Insgesamt bedeckt: M × Vol = 2^(n−r) × 2^r = 2^n ✓
Die Tatsache, dass Vol(n,1) = 2^r wenn n = 2^r − 1, ist das, was perfekte Codes bei diesen Längen möglich macht. Bei anderen Längen ist 1 + n keine Potenz von 2, und perfekte Einzelfehler-korrigierende binäre Codes können nicht existieren.
Generator-Matrix & Dualität
Die Paritätsprüfmatrix H definiert den Code über den Kern. Dual: eine Generator-Matrix G, deren Zeilen eine Basis für ker(H) bilden.
Für den (7,4)-Code: G ist eine 4×7-Matrix. Jedes Codewort c = mG für einen Nachrichtsvektor m ∈ GF(2)^4. Die Zeilen von G spannen den Code auf; die Zeilen von H spannen den Nullraum des Codes auf.
Schlüsselbeziehung: HG^T = 0 (mod 2). Jede Zeile von G liegt in ker(H); jede Zeile von H hebt jede Zeile von G auf.
Dualer Code: C⊥ = ker(G^T) = image(H^T). Für den (7,4)-Code ist der Dual ein (7,3)-Code – ein [7,3,4]-Code mit Mindestabstand 4.
Die Geometrie der Dualität: C und C⊥ sind orthogonale Untervektorräume von GF(2)^7. Der gesamte Raum zerlegt sich in den Code, seine Nebenklassen, und die duale Struktur, die die Syndrom-Abbildung codiert.