De pariteitscontrolematrix
Elke lineaire code over GF(2) — het lichaam met slechts 0 en 1, rekenkunde modulo 2 — heeft een pariteitscontrolematrix H. Voor de (7,4) Hamming-code is H een 3×7-matrix waarvan de kolommen de binaire representaties van 1 tot en met 7 zijn:
``
H = [ 0 0 0 1 1 1 1 ] ← bit 2 van positienummer
[ 0 1 1 0 0 1 1 ] ← bit 1 van positienummer
[ 1 0 1 0 1 0 1 ] ← bit 0 van positienummer
``
Kolom j van H is de binaire representatie van j. Dit is waarom het syndroom s = Hr direct de foutpositie benoemt.
De afbeelding H: GF(2)^7 → GF(2)^3 is een lineaire afbeelding (matrixvermenigvuldiging mod 2). Zijn kern ker(H) = { r : Hr = 0 } is precies de verzameling geldige codewoorden.
Dimensietelling: dim(ker H) = 7 − rang(H) = 7 − 3 = 4. Dus er zijn 2^4 = 16 codewoorden. Dit bevestigt 4 berichtenits.
De code als een kern
Een woord c ∈ {0,1}^7 is een geldig codewoord dan en slechts dan als Hc = 0 (mod 2). Dit is de definiërende vergelijking van een lineaire code.
Voorbeeld: c = 0011001. Controleer Hc mod 2:
``
Rij 1: 0·0+0·0+0·1+1·1+1·0+1·0+1·1 = 0+0+0+1+0+0+1 = 2 ≡ 0
Rij 2: 0·0+1·0+1·1+0·1+0·0+1·0+1·1 = 0+0+1+0+0+0+1 = 2 ≡ 0
Rij 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. Dus 0011001 is een geldig codewoord.
Nevenklassen van de code
De codewoorden C = ker(H) vormen een ondergroep van GF(2)^7. Elk ander woord in GF(2)^7 behoort tot precies één nevenklasse van C.
Nevenklassedefinitie: voor elk woord e, de nevenklasse C + e = { c + e : c ∈ C }.
Twee woorden behoren tot dezelfde nevenklasse dan en slechts dan als hun verschil een codewoord is — equivalent, als ze hetzelfde syndroom hebben: H(r₁) = H(r₂) iff H(r₁ − r₂) = 0 iff r₁ − r₂ ∈ C.
De syndrooomafbeelding H induceert een isomorfisme GF(2)^7 / C ≅ GF(2)^3. Met |C| = 16 en |GF(2)^7| = 128: er zijn precies 128/16 = 8 nevenklassen, één voor elke syndroom waarde in GF(2)^3.
Standaardarray: noem één nevenklasseleider per nevenklasse — het woord van minimaal Hamming-gewicht in die nevenklasse. Voor foutcorrectie van enkele fouten, correspondeert elk niet-nul syndroom uniek met een gewicht-1 foutpatroon (een enkele 1 op één van de 7 posities). Daarom zijn 7 foutpatronen + 1 geen-fout = 8 nevenklassen = 2^3.
Decodering via nevenklasseleiders
Decoderingsalgoritme: ontvang r → bereken s = Hr → zoek nevenklasseleider e_s op (het canonieke patroon voor syndroom s) → geef r − e_s = r + e_s uit (hetzelfde in GF(2)).
Voor de (7,4) code zijn de 8 nevenklasseleiders: 0000000 (syndroom 000), 1000000 (syndroom 001), 0100000 (syndroom 010), 0010000 (syndroom 011), 0001000 (syndroom 100), 0000100 (syndroom 101), 0000010 (syndroom 110), 0000001 (syndroom 111).
Waarom (7,4) perfect is
Een code C ⊆ GF(2)^n met minimale afstand 3 corrigeert alle enkele fouten. Elk codewoord c heeft een Hamming-bol met straal 1: het centrum c en zijn n onmiddellijke buren (gewicht-1 foutpatronen). Bolvolume = 1 + n.
Voor n = 7: bolvolume = 8. Met 16 codewoorden: 16 × 8 = 128 = 2^7. De bollen tegelen GF(2)^7 perfect — geen punt gelaten onbedekt, geen punt bedekt twee keer.
Dit is de definitie van een perfecte code: M · Vol(n, t) = 2^n. Perfecte foutcorrectie codes voor enkele fouten (t=1) bestaan alleen voor bepaalde parameters: (7,4), (15,11), (23,12) (de binaire Golay-code), en triviaal n = 2^r − 1, k = n − r voor elke r ≥ 2.
De geometrie: GF(2)^7 decomponeert in precies 8 banen onder de werking van de code als een nevenklassepartitie. Elke baan is een nevenklasse; elke nevenklasse heeft een uniek syndroom. De syndroomafbeelding H is een bijectie van nevenklassen naar GF(2)^3.
Het telargument
Voor een perfecte foutcorrectie code voor enkele fouten op n = 2^r − 1 bits met r controle bits:
- Aantal codewoorden: M = 2^k = 2^(n−r)
- Bolvolume: Vol(n, 1) = 1 + n = 1 + 2^r − 1 = 2^r
- Totaal bedekt: M × Vol = 2^(n−r) × 2^r = 2^n ✓
Het feit dat Vol(n,1) = 2^r wanneer n = 2^r − 1 is wat perfecte codes mogelijk maakt op deze lengtes. Op andere lengtes is 1 + n geen macht van 2, en perfecte foutcorrectie codes voor enkele fouten kunnen niet bestaan.
Generatormatrix & dualiteit
De pariteitscontrolematrix H definieert de code via de kern. Zijn duale: een generatormatrix G waarvan de rijen een basis voor ker(H) vormen.
Voor de (7,4) code: G is een 4×7 matrix. Elk codewoord c = mG voor enige berichtvector m ∈ GF(2)^4. De rijen van G spannen de code; de rijen van H spannen de nulruimte van de code.
Sleutelrelatie: HG^T = 0 (mod 2). Elke rij van G ligt in ker(H); elke rij van H annuleert elke rij van G.
Duale code: C⊥ = ker(G^T) = afbeelding(H^T). Voor de (7,4) code is de duale een (7,3) code — een [7,3,4] code met minimale afstand 4.
De geometrie van dualiteit: C en C⊥ zijn orthogonale deelruimten van GF(2)^7. De gehele ruimte decomponeert in de code, zijn nevenklassen, en de duale structuur die de syndroomafbeelding codeert.