Paritetskontrollmatrisen
Varje linjär kod över GF(2) — fältet med bara 0 och 1, aritmetik modulo 2 — har en paritetskontrollmatris H. För Hammingkoden (7,4) är H en 3×7-matris vars kolumner är de binära representationerna av 1 till 7:
``
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
``
Kolumn j för H är den binära representationen av j. Det är därför syndromet s = Hr direkt namnger felpositionen.
Avbildningen H: GF(2)^7 → GF(2)^3 är en linjär avbildning (matrismultiplikation mod 2). Dess kärna ker(H) = { r : Hr = 0 } är exakt mängden av giltiga kodord.
Dimensionsräkning: dim(ker H) = 7 − rank(H) = 7 − 3 = 4. Så det finns 2^4 = 16 kodord. Detta bekräftar 4 meddelandebitar.
Koden som en kärna
Ett ord c ∈ {0,1}^7 är ett giltigt kodord om och bara om Hc = 0 (mod 2). Detta är den definierande ekvationen för en linjär kod.
Exempel: c = 0011001. Kontrollera Hc mod 2:
``
Row 1: 0·0+0·0+0·1+1·1+1·0+1·0+1·1 = 0+0+0+1+0+0+1 = 2 ≡ 0
Row 2: 0·0+1·0+1·1+0·1+0·0+1·0+1·1 = 0+0+1+0+0+0+1 = 2 ≡ 0
Row 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. Så 0011001 är ett giltigt kodord.
Kosetter av koden
Kodorden C = ker(H) bildar en undergrupp av GF(2)^7. Varje annat ord i GF(2)^7 tillhör exakt en koset av C.
Koset definition: för något ord e, kosetten C + e = { c + e : c ∈ C }.
Två ord tillhör samma koset om och bara om deras skillnad är ett kodord — ekvivalent, om de har samma syndrom: H(r₁) = H(r₂) om och bara om H(r₁ − r₂) = 0 om och bara om r₁ − r₂ ∈ C.
Syndromkartan H inducerar en isomorfism GF(2)^7 / C ≅ GF(2)^3. Med |C| = 16 och |GF(2)^7| = 128: det finns exakt 128/16 = 8 kosetter, en för varje syndromvärde i GF(2)^3.
Standardmatris: lista en kosetledare per koset — ordet med minimalt Hammingvikt i den kosetten. För enkel felkorrigering motsvarar varje nollskilt syndrom unikt ett viktmönster för en felbit (en enda 1 på en av 7 positioner). Det är därför 7 felmönster + 1 ingen-fel = 8 kosetter = 2^3.
Dekodning via kosetledare
Dekodningsalgoritm: mottas r → beräkna s = Hr → slå upp kosetledare e_s (den kanoniska felen för syndrom s) → skriv ut r − e_s = r + e_s (samma i GF(2)).
För (7,4)-koden är de 8 kosetledarna: 0000000 (syndrom 000), 1000000 (syndrom 001), 0100000 (syndrom 010), 0010000 (syndrom 011), 0001000 (syndrom 100), 0000100 (syndrom 101), 0000010 (syndrom 110), 0000001 (syndrom 111).
Varför (7,4) är perfekt
En kod C ⊆ GF(2)^n med minimiavstånd 3 korrigerar alla singel fel. Varje kodord c har en Hammingsfär med radie 1: centrum c och dess n närmaste grannar (viktmönster för en felbit). Sfärvolym = 1 + n.
För n = 7: sfärvolym = 8. Med 16 kodord: 16 × 8 = 128 = 2^7. Sfererna tessellerar GF(2)^7 perfekt — ingen punkt kvar utan täckning, ingen punkt täckt två gånger.
Detta är definitionen på en perfekt kod: M · Vol(n, t) = 2^n. Perfekta singel-felkorrigerande binära koder (t=1) finns bara för specifika parametrar: (7,4), (15,11), (23,12) (Golaykoden), och trivialt n = 2^r − 1, k = n − r för något r ≥ 2.
Geometrin: GF(2)^7 delar upp sig i exakt 8 banor under kodernas verkan som en kosetpartition. Varje bana är en koset; varje koset har ett unikt syndrom. Syndromkartan H är en bijektion från kosetter till GF(2)^3.
Räkneeargumentet
För en perfekt singel-felkorrigerande kod på n = 2^r − 1 bitar med r paritetskontrollbitar:
- Antal kodord: M = 2^k = 2^(n−r)
- Sfärvolym: Vol(n, 1) = 1 + n = 1 + 2^r − 1 = 2^r
- Totalt täckt: M × Vol = 2^(n−r) × 2^r = 2^n ✓
Det faktum att Vol(n,1) = 2^r när n = 2^r − 1 är vad som gör perfekta koder möjliga vid dessa längder. Vid andra längder är 1 + n inte en potens av 2, och perfekta singel-felkorrigerande binära koder kan inte existera.
Generatormatris & dualitet
Paritetskontrollmatrisen H definierar koden genom kärnans. Sin dual: en generatormatris G vars rader bildar en bas för ker(H).
För (7,4)-koden: G är en 4×7-matris. Alla kodord c = mG för någon meddelandevektro m ∈ GF(2)^4. Raderna i G spänner upp koden; raderna i H spänner upp kodordens nollrum.
Nyckelförhållande: HG^T = 0 (mod 2). Varje rad av G är i ker(H); varje rad av H utsläcker varje rad av G.
Dualkod: C⊥ = ker(G^T) = image(H^T). För (7,4)-koden är dualen en (7,3)-kod — en [7,3,4]-kod med minimiavstånd 4.
Geometrin för dualitet: C och C⊥ är ortogonala delrum av GF(2)^7. Hela rummet delar upp sig i koden, dess kosetter, och dualstrukturen som syndromkartan kodar in.