La Matrice di Controllo di Parità
Ogni codice lineare su GF(2) — il campo con solo 0 e 1, aritmetica modulo 2 — ha una matrice di controllo di parità H. Per il codice Hamming (7,4), H è una matrice 3×7 le cui colonne sono le rappresentazioni binarie da 1 a 7:
``
H = [ 0 0 0 1 1 1 1 ] ← bit 2 della rappresentazione della posizione
[ 0 1 1 0 0 1 1 ] ← bit 1 della rappresentazione della posizione
[ 1 0 1 0 1 0 1 ] ← bit 0 della rappresentazione della posizione
``
La colonna j di H è la rappresentazione binaria di j. Questo è il motivo per cui la sindrome s = Hr nomina direttamente la posizione dell'errore.
La mappa H: GF(2)^7 → GF(2)^3 è una mappa lineare (moltiplicazione matriciale mod 2). Il suo kernel ker(H) = { r : Hr = 0 } è esattamente l'insieme delle parole di codice valide.
Conteggio delle dimensioni: dim(ker H) = 7 − rank(H) = 7 − 3 = 4. Quindi ci sono 2^4 = 16 parole di codice. Questo conferma 4 bit di messaggio.
Il Codice come Kernel
Una parola c ∈ {0,1}^7 è una parola di codice valida se e solo se Hc = 0 (mod 2). Questa è l'equazione definitoria di un codice lineare.
Esempio: c = 0011001. Controlla Hc mod 2:
``
Riga 1: 0·0+0·0+0·1+1·1+1·0+1·0+1·1 = 0+0+0+1+0+0+1 = 2 ≡ 0
Riga 2: 0·0+1·0+1·1+0·1+0·0+1·0+1·1 = 0+0+1+0+0+0+1 = 2 ≡ 0
Riga 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. Quindi 0011001 è una parola di codice valida.
Coset del Codice
Le parole di codice C = ker(H) formano un sottogruppo di GF(2)^7. Ogni altra parola in GF(2)^7 appartiene esattamente a un coset di C.
Definizione di coset: per qualsiasi parola e, il coset C + e = { c + e : c ∈ C }.
Due parole appartengono allo stesso coset se e solo se la loro differenza è una parola di codice — equivalentemente, se hanno la stessa sindrome: H(r₁) = H(r₂) se e solo se H(r₁ − r₂) = 0 se e solo se r₁ − r₂ ∈ C.
La mappa di sindrome H induce un isomorfismo GF(2)^7 / C ≅ GF(2)^3. Con |C| = 16 e |GF(2)^7| = 128: ci sono esattamente 128/16 = 8 coset, uno per ogni valore di sindrome in GF(2)^3.
Array standard: elenca un leader di coset per coset — la parola di peso Hamming minimo in quel coset. Per la correzione di errore singolo, ogni sindrome non zero corrisponde univocamente a un pattern di errore di peso 1 (un singolo 1 in una delle 7 posizioni). Ecco perché 7 pattern di errore + 1 no-error = 8 coset = 2^3.
Decodifica via Leader di Coset
Algoritmo di decodifica: ricevi r → calcola s = Hr → cerca il leader di coset e_s (l'errore canonico per la sindrome s) → output r − e_s = r + e_s (uguale in GF(2)).
Per il codice (7,4), gli 8 leader di coset sono: 0000000 (sindrome 000), 1000000 (sindrome 001), 0100000 (sindrome 010), 0010000 (sindrome 011), 0001000 (sindrome 100), 0000100 (sindrome 101), 0000010 (sindrome 110), 0000001 (sindrome 111).
Perché (7,4) è Perfetto
Un codice C ⊆ GF(2)^n con distanza minima 3 corregge tutti gli errori singoli. Ogni parola di codice c ha una palla di Hamming di raggio 1: il centro c e i suoi n vicini immediati (pattern di errore di peso 1). Volume della palla = 1 + n.
Per n = 7: volume della palla = 8. Con 16 parole di codice: 16 × 8 = 128 = 2^7. Le palle tiling GF(2)^7 perfettamente — nessun punto rimasto scoperto, nessun punto coperto due volte.
Questa è la definizione di un codice perfetto: M · Vol(n, t) = 2^n. I codici binari perfetti correttori di errore singolo (t=1) esistono solo per parametri specifici: (7,4), (15,11), (23,12) (il codice Golay binario), e banalmente n = 2^r − 1, k = n − r per qualsiasi r ≥ 2.
La geometria: GF(2)^7 si decompone in esattamente 8 orbite sotto l'azione del codice come partizione di coset. Ogni orbita è un coset; ogni coset ha una sindrome unica. La mappa di sindrome H è una biiezione dai coset a GF(2)^3.
L'Argomento del Conteggio
Per un codice binario perfetto correttore di errore singolo su n = 2^r − 1 bit con r bit di controllo di parità:
- Numero di parole di codice: M = 2^k = 2^(n−r)
- Volume della palla: Vol(n, 1) = 1 + n = 1 + 2^r − 1 = 2^r
- Totale coperto: M × Vol = 2^(n−r) × 2^r = 2^n ✓
Il fatto che Vol(n,1) = 2^r quando n = 2^r − 1 è quello che rende possibili i codici perfetti a queste lunghezze. A altre lunghezze, 1 + n non è una potenza di 2, e i codici binari perfetti correttori di errore singolo non possono esistere.
Matrice Generatrice & Dualità
La matrice di controllo di parità H definisce il codice via il kernel. Il suo duale: una matrice generatrice G le cui righe formano una base per ker(H).
Per il codice (7,4): G è una matrice 4×7. Qualsiasi parola di codice c = mG per qualche vettore di messaggio m ∈ GF(2)^4. Le righe di G generano il codice; le righe di H generano lo spazio nullo del codice.
Relazione chiave: HG^T = 0 (mod 2). Ogni riga di G è in ker(H); ogni riga di H annulla ogni riga di G.
Codice duale: C⊥ = ker(G^T) = image(H^T). Per il codice (7,4), il duale è un codice (7,3) — un codice [7,3,4] con distanza minima 4.
La geometria della dualità: C e C⊥ sono sottospazi ortogonali di GF(2)^7. L'intero spazio si decompone nel codice, i suoi coset, e la struttura duale che la mappa di sindrome codifica.