Rilevare vs Correggere
Nella lezione precedente abbiamo visto come CRC e checksum rilevano gli errori: il ricevitore sa che qualcosa è andato storto, ma non sa dove né come rimediare. La reazione possibile è una sola — chiedere la ritrasmissione.
Esiste però una categoria di codici più potenti, i codici a correzione di errori (ECC — Error Correcting Codes), che aggiungono abbastanza ridondanza da permettere al ricevitore di identificare il bit sbagliato e correggerlo senza ritrasmissione. Il prezzo è un overhead di bit più elevato.
Tre parametri guidano la scelta del codice: la probabilità di errore del canale, il costo della ritrasmissione (latenza, banda), e la complessità hardware/software accettabile.
VRC — Vertical Redundancy Check
Il VRC è il più semplice dei codici di correzione/rilevazione: aggiunge un solo bit di parità a ogni carattere (di solito 7 bit ASCII). Il bit di parità viene scelto in modo che il numero totale di 1 nel byte sia pari (parità pari) o dispari (parità dispari). Il protocollo deve concordare quale schema usare.
Esempio pratico — parità pari
| Carattere | Bit dato (7) | N. di 1 | Bit parità | Byte trasmesso (8 bit) |
|---|---|---|---|---|
| ‘A’ (65) | 100 0001 | 2 → già pari | 0 | 1000 0010 |
| ‘B’ (66) | 100 0010 | 2 → già pari | 0 | 1000 0100 |
| ‘C’ (67) | 100 0011 | 3 → dispari | 1 | 1000 0111 |
| ‘K’ (75) | 100 1011 | 4 → già pari | 0 | 1001 0110 |
Il ricevitore ricalcola la parità sull’intero byte: se il numero di 1 è dispari (schema pari) c’è errore.
VRC rileva solo un numero dispari di errori nel byte. Se si invertono 2 bit, la parità rimane invariata e l’errore passa inosservato. Non corregge: il ricevitore sa che c’è un errore, ma non può identificare quale bit è sbagliato.
LRC — Longitudinal Redundancy Check
LRC estende il concetto di parità all’intero blocco di dati: invece di calcolare la parità colonna per colonna (VRC), la calcola riga per riga, producendo un byte di controllo aggiuntivo (BCC — Block Check Character) alla fine del blocco.
Visivamente, immagina il blocco come una matrice di byte: VRC controlla ogni colonna (bit per bit nel singolo byte), LRC controlla ogni riga (lo stesso bit-position in tutti i byte del blocco).
Esempio — blocco di 4 byte
| Byte | b7 | b6 | b5 | b4 | b3 | b2 | b1 | b0 | VRC |
|---|---|---|---|---|---|---|---|---|---|
| ‘T’ 84 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |
| ‘E’ 69 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
| ‘S’ 83 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
| ‘T’ 84 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |
| BCC (LRC) | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | — |
Ogni colonna del BCC è la parità XOR dei bit di quella posizione in tutti i byte del blocco. Combinando VRC e LRC insieme, il ricevitore può spesso localizzare il bit errato come intersezione di riga e colonna.
VRC + LRC insieme offrono una capacità di correzione di singolo errore: la riga (LRC) identifica il byte errato, la colonna (VRC) identifica il bit errato. Tuttavia questa tecnica è stata in gran parte sostituita da CRC per la rilevazione e da Hamming per la correzione.
Il Codice di Hamming
Nel 1950 Richard Hamming, lavorando ai Bell Labs, sviluppò un sistema elegante per inserire bit di parità in posizioni strategiche all’interno della codeword, in modo che ogni bit di parità copra un sottoinsieme diverso dei bit di dato. Questo permette, in caso di errore singolo, di identificare esattamente la posizione del bit errato e correggerla.
2ʳ ≥ r + k + 1. I bit di parità occupano le posizioni che sono potenze di 2: 1, 2, 4, 8, 16… Le posizioni rimanenti ospitano i bit di dato.Hamming(7,4): 4 bit di dato → 7 bit totali
Caso più noto: k=4 bit dati, r=3 bit parità → n=7 bit totali. Verifica: 2³ = 8 ≥ 3+4+1 = 8 ✓
| Posizione | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| Tipo | P1 | P2 | d1 | P3 | d2 | d3 | d4 |
| Copre posiz. | 1,3,5,7 | 2,3,6,7 | — | 4,5,6,7 | — | — | — |
001) → copre tutte le posizioni con il bit 0 = 1 → pos 1,3,5,7010) → copre tutte le posizioni con il bit 1 = 1 → pos 2,3,6,7100) → copre tutte le posizioni con il bit 2 = 1 → pos 4,5,6,7Codifica: esempio con dato 1011
Dato da trasmettere: d1=1, d2=0, d3=1, d4=1 → inseriti nelle posizioni 3, 5, 6, 7.
| Pos | 1 (P1) | 2 (P2) | 3 (d1) | 4 (P4) | 5 (d2) | 6 (d3) | 7 (d4) |
|---|---|---|---|---|---|---|---|
| Valore dato | ? | ? | 1 | ? | 0 | 1 | 1 |
| Calcolo parità (pari) | P1: pos 1,3,5,7 → ?,1,0,1 → tre 1 → P1=1 | P2: pos 2,3,6,7 → ?,1,1,1 → tre 1 → P2=1 | P4: pos 4,5,6,7 → ?,0,1,1 → due 1 → P4=0 | ||||||
| Codeword finale | 1 | 1 | 1 | 0 | 0 | 1 | 1 |
La codeword trasmessa è: 1110011
Decodifica e correzione dell’errore
Supponiamo che durante la trasmissione si alteri il bit in posizione 5 (cambia da 0 a 1). Il ricevitore ottiene: 1110111.
Il ricevitore ricalcola le sindromi (parità dei gruppi): se il risultato è 0 tutto ok, se è 1 c’è un errore nel gruppo.
Il ricevitore inverte il bit in posizione 5 e ottiene la codeword corretta: 1110011. Estrae i bit di dato dalle posizioni 3,5,6,7: 1,0,1,1 → dato originale recuperato correttamente.
La sindrome è esattamente la posizione binaria del bit errato. Se sindrome = 000 non ci sono errori. Se sindrome ≠ 000, il suo valore decimale indica il bit da invertire. Questo è il meccanismo elegante di Hamming: le posizioni delle parità non sono casuali, sono le potenze di 2 proprio per sfruttare la rappresentazione binaria come “indirizzo” dell’errore.
Distanza di Hamming
La distanza di Hamming tra due codeword è il numero di bit in cui differiscono. Per un codice con distanza minima d:
| Distanza minima d | Capacità di rilevazione | Capacità di correzione |
|---|---|---|
| d = 2 | Rileva 1 errore | Non corregge |
| d = 3 | Rileva 2 errori | Corregge 1 errore (Hamming base) |
| d = 4 | Rileva 3 errori | Corregge 1 + rileva 2 (Hamming esteso con bit globale) |
| d = 2t+1 | Rileva 2t errori | Corregge t errori |
Hamming(7,4) ha distanza minima d=3: corregge 1 errore e rileva 2. La variante Hamming(8,4) esteso aggiunge un bit di parità globale (SECDED — Single Error Correction, Double Error Detection), con d=4.
ECC nella pratica moderna
I codici di Hamming si trovano ancora oggi in memoria RAM ECC dei server, dove un singolo bit-flip può causare corruzione silenziosa dei dati. I moduli RAM ECC aggiungono chip extra (tipicamente 8 o 9 chip invece di 8) per memorizzare i bit di parità Hamming. La correzione avviene in hardware, in modo trasparente al processore.
RAM ECC nei server — corregge bit-flip causati da raggi cosmici. NAND Flash nei SSD — usa BCH o LDPC (evoluzioni di Hamming). Voyager e sonde spaziali — Reed-Solomon + codici convoluzionali per canali con alta perdita di segnale. CD/DVD — CIRC (Cross-Interleaved Reed-Solomon) per correggere i graffi. Hamming è il capostipite di tutti questi sistemi.
- VRC: parità su singolo byte. Rileva errori in numero dispari nel byte. Semplice, overhead 1 bit/byte.
- LRC: parità longitudinale sul blocco (BCC). Combinato con VRC permette di localizzare il bit errato.
- Hamming(n,k): i bit di parità occupano le posizioni potenze di 2. Ogni bit di parità copre le posizioni il cui indice ha quel bit a 1 in binario.
- La sindrome è l’indirizzo binario del bit errato: se non è zero, il suo valore decimale indica esattamente quale bit invertire.
- Hamming(7,4): distanza minima 3 → corregge 1 errore, rileva 2. Efficienza k/n = 4/7 ≈ 57%.
- Applicazioni reali: RAM ECC, NAND Flash, sonde spaziali, storage. È il fondamento concettuale di tutti i codici ECC moderni.