Codice di Hamming — Spiegato Passo per Passo

Il problema: i bit viaggiano su fili fisici

Quando un computer manda dati a un altro (su un cavo, via WiFi, su internet), i dati viaggiano come una sequenza di 0 e 1 — i bit. Ma i fili non sono perfetti: interferenze, rumore elettrico o un raggio cosmico possono capovolgere un bit (da 0 a 1 o viceversa) senza che nessuno se ne accorga.

La soluzione: aggiungere bit "guardiani"

Richard Hamming (1950) ha inventato un modo brillante: prima di trasmettere i dati, aggiungi qualche bit extra che "riassumono" gli altri attraverso l'operazione XOR. Se un bit si rompe durante il viaggio, questi bit guardiani ti dicono esattamente quale.

L'operazione XOR (⊕) — la "somma strana"

XOR restituisce 1 se i due bit sono diversi, 0 se sono uguali:

0 ⊕ 0 = 0 | 0 ⊕ 1 = 1
1 ⊕ 0 = 1 | 1 ⊕ 1 = 0

Trucco utile: se fai XOR di tanti bit, il risultato è 0 se il numero di 1 è pari, 1 se è dispari. Questo si chiama bit di parità.

Hamming(12,8) — il nostro formato

Noi usiamo Hamming(12,8): partiamo da 8 bit di dati e aggiungiamo 4 bit guardiani, per un totale di 12 bit da trasmettere. I bit guardiani occupano le posizioni 1, 2, 4, 8 (potenze di 2). I bit di dati occupano le posizioni 3, 5, 6, 7, 9, 10, 11, 12.

Posizioni: [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12]
Tipo: [P1][P2][d1][P4][d2][d3][d4][P8][d5][ d6][ d7][ d8]
(P = parità, d = dato)

Cosa controlla ogni bit guardiano?

Ogni Pn controlla tutte le posizioni il cui numero ha il bit n acceso in binario:

P1 (pos.1) → controlla posizioni 1,3,5,7,9,11 (numero dispari in binario ha bit 1)
P2 (pos.2) → controlla posizioni 2,3,6,7,10,11 (numero con bit 2 acceso)
P4 (pos.4) → controlla posizioni 4,5,6,7,12 (numero con bit 4 acceso)
P8 (pos.8) → controlla posizioni 8,9,10,11,12 (numero con bit 8 acceso)

Come funziona la correzione?

Il ricevitore ricalcola i 4 bit di parità. Se tutti danno 0 → nessun errore. Se uno o più danno 1 → c'è un errore. I 4 risultati formano un numero binario a 4 cifre: quel numero è la posizione del bit sbagliato! Esempio: S8=0, S4=1, S2=1, S1=0 → 0110 in binario = 6 → il bit sbagliato è alla posizione 6. Basta invertirlo e il messaggio è riparato. 🎉

02 · codeword completa (12 bit)

🔵 I bit in blu sono i bit guardiani (di parità) calcolati automaticamente. I bit bianchi sono i tuoi 8 bit originali, incastrati nelle posizioni di dati. Insieme formano la codeword di 12 bit che viene trasmessa.

bit guardiano (calcolato con XOR)

bit di dato (il tuo messaggio)

03 · clicca un bit per simulare un errore

⚡ Cosa succede ora? Immagina che durante la trasmissione uno dei bit si "capovolga" per colpa del rumore sulla rete. Clicca qualsiasi bit nella codeword sopra per invertirlo e simulare questo errore. Poi premi il bottone rosso.