Correzione Errori: VRC, LRC e Codice di Hamming
Da rilevare a correggere: come VRC e LRC costruiscono la prima matrice di controllo e perché Hamming(7,4) riesce a trovare e riparare un bit errato senza ritrasmissione.
1. 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 (ARQ).
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, ma indispensabile quando ritrasmettere è costoso o impossibile.
Un codice (n, k) trasmette k bit di dato in una codeword di n bit totali, aggiungendo r = n − k bit di ridondanza. Il rate di codifica è R = k/n. Più R è basso, più la ridondanza è alta.
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.
CRC / Checksum
Scopre l'errore, chiede ARQ. Overhead basso, adatto a reti cablate affidabili.
VRC + LRC
Struttura bidimensionale, incrocio riga/colonna per localizzare. Usato storicamente in nastri magnetici.
Hamming / ECC
Corregge sul posto senza ritrasmissione. Essenziale in RAM ECC, spazio, storage.
2. VRC — Vertical Redundancy Check
Il VRC è il più semplice: aggiunge un solo bit di parità a ogni carattere (di solito 7 bit ASCII). Il bit viene scelto in modo che il numero totale di 1 nel byte sia pari (parità pari) o dispari (parità dispari). Mittente e ricevitore devono concordare lo schema.
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 |
| '1' (49) | 011 0001 | 3 → dispari | 1 | 0110 0011 |
Il bit di parità singola rileva solo un numero dispari di errori nel byte. Se si corrompono 2 bit nello stesso byte, la parità torna pari e l'errore passa inosservato. Per questo VRC da solo non è affidabile su canali rumorosi.
3. LRC — Longitudinal Redundancy Check e matrice 2D
LRC aggiunge una riga di parità sull'intero blocco: per ogni colonna di bit si calcola la parità verticale su tutti i byte del blocco. Il risultato è un byte aggiuntivo detto BCC — Block Check Character.
Quando combiniamo VRC + LRC otteniamo un controllo bidimensionale:
Parità orizzontale
Ogni byte ha il suo bit di parità. Rileva l'errore sulla riga.
Parità longitudinale
Ogni colonna ha il suo bit di parità (BCC). Rileva l'errore sulla colonna.
L'intersezione tra riga in errore e colonna in errore localizza il bit sbagliato e ne permette la correzione invertendolo. È il primo vero ECC storico, usato nei nastri magnetici e nelle prime trasmissioni seriali.
| bit6 | bit5 | bit4 | bit3 | bit2 | bit1 | bit0 | VRC | |
|---|---|---|---|---|---|---|---|---|
| Byte1 'A' | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| Byte2 'B' | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| Byte3 'C' | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| LRC / BCC | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
Per ricordare LRC: pensa a un foglio Excel. VRC controlla ogni riga (un byte), LRC controlla ogni colonna (tutti i byte). Se si accende una spia sia su una riga che su una colonna, la cella all'incrocio è l'errore.
4. Codice di Hamming(7,4): struttura e posizionamento
Il codice di Hamming, inventato nel 1950 da Richard Hamming, è il primo codice in grado di correggere automaticamente un singolo errore. L'idea geniale è incastrare i bit di parità dentro il flusso di dati, in posizioni che sono potenze di 2.
In Hamming(n,k), i bit di parità sono nelle posizioni 1, 2, 4, 8, 16…. Ogni parità p_i controlla tutte le posizioni il cui indice binario ha il bit i a 1. Servono r bit tali che 2^r ≥ k + r + 1.
Per Hamming(7,4) abbiamo k=4 dati, r=3 parità, n=7 totale. Verifica: 2^3 = 8 ≥ 4+3+1 = 8 ✔. I dati D = d1 d2 d3 d4 e le parità P = p1 p2 p4.
| Posizione | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| Ruolo | p1 | p2 | d1 | p4 | d2 | d3 | d4 |
| Copertura p1 (1=001) | ✔ | ✔ | ✔ | ✔ | |||
| Copertura p2 (2=010) | ✔ | ✔ | ✔ | ✔ | |||
| Copertura p4 (4=100) | ✔ | ✔ | ✔ | ✔ |
Vogliamo trasmettere 4 bit: 1 0 1 1 (d1=1, d2=0, d3=1, d4=1). Mettiamoli nelle posizioni 3,5,6,7.
p1 copre 1,3,5,7 → d1+d2+d4 = 1+0+1=2 pari → p1=0
p2 copre 2,3,6,7 → d1+d3+d4 = 1+1+1=3 dispari → p2=1
p4 copre 4,5,6,7 → d2+d3+d4 = 0+1+1=2 pari → p4=0
Codeword: 0 1 1 0 0 1 1 → 0110011
5. Codifica, sindrome e correzione passo-passo
Il ricevitore ricalcola tutte le parità sulla codeword ricevuta. Se tutte sono pari → sindrome 000 → nessun errore. Se qualcosa non torna, la sindrome è il numero binario formato dai check falliti: indica esattamente la posizione dell'errore.
Trasmettiamo 0110011. Il canale flippa il bit 5: riceviamo 0110111 (pos5 da 0 → 1).
ricalcolo:
s1 = r1+r3+r5+r7 = 0+1+1+1=3 dispari → s1=1
s2 = r2+r3+r6+r7 = 1+1+1+1=4 pari → s2=0
s4 = r4+r5+r6+r7 = 0+1+1+1=3 dispari → s4=1
sindrome = 101₂ = 5₁₀ → errore in posizione 5! Invertiamo: 0110011 corretto → dati 1011 recuperati.
La sindrome indica la posizione 1-indexed. Molti studenti indicizzano da 0 e correggono il bit sbagliato. Ricorda: Hamming conta da 1, non da 0. Posizione 5 = quinto bit nella codeword, non indice array 5.
Tabella completa codifica Hamming(7,4) — tutti i 16 casi
| Dati d1 d2 d3 d4 | p1 | p2 | p4 | Codeword 1 2 3 4 5 6 7 |
|---|---|---|---|---|
| 0000 | 0 | 0 | 0 | 0000000 |
| 0001 | 1 | 1 | 1 | 1101001 |
| 0010 | 1 | 0 | 1 | 1001010 |
| 0011 | 0 | 1 | 0 | 0101011 |
| 0100 | 1 | 1 | 0 | 1100100 |
| 0101 | 0 | 0 | 1 | 0001101 |
| 0110 | 0 | 1 | 1 | 0101110 |
| 0111 | 1 | 0 | 0 | 1000111 |
| 1000 | 1 | 1 | 1 | 1110000 |
| 1001 | 0 | 0 | 0 | 0011001 |
| 1010 | 0 | 1 | 0 | 0100010 |
| 1011 | 0 | 1 | 0 | 0110011 (nostro esempio) |
| 1100 | 0 | 0 | 1 | 0010100 |
| 1101 | 1 | 1 | 0 | 1111101 |
| 1110 | 1 | 0 | 0 | 1011010 |
| 1111 | 0 | 1 | 1 | 0111011 |
6. Distanza di Hamming e capacità di correzione
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 (parità singola) | Rileva 1 errore | Non corregge |
d = 3 (Hamming base) | Rileva 2 errori | Corregge 1 errore |
d = 4 (Hamming esteso SECDED) | Rileva 3 errori | Corregge 1 + rileva 2 |
d = 2t+1 (generale) | 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, usata nelle RAM ECC moderne.
7. ECC nella pratica moderna
I codici di Hamming si trovano ancora oggi in memoria RAM ECC dei server, dove un singolo bit-flip causato da raggi cosmici può causare corruzione silenziosa dei dati. I moduli RAM ECC aggiungono chip extra (tipicamente 9 chip invece di 8) per memorizzare i bit di parità Hamming. La correzione avviene in hardware, trasparente al processore.
RAM ECC
Corregge bit-flip casuali, essenziale in data center e sistemi critici. SECDED.
NAND Flash SSD
Usa BCH o LDPC, evoluzioni di Hamming, tollera centinaia di errori pagina.
Voyager / Marte
Reed-Solomon + convoluzionali, canali con alta perdita. Hamming è il capostipite.
RAM ECC nei server — corregge bit-flip da raggi cosmici. NAND Flash nei SSD — usa BCH o LDPC. Voyager e sonde spaziali — Reed-Solomon + codici convoluzionali per canali con alta perdita. CD/DVD — CIRC (Cross-Interleaved Reed-Solomon) per correggere graffi. Hamming è il fondamento concettuale di tutti.
8. Verifica / Esercizio in classe
🔬 Attività pratica
Lavora su un blocco VRC+LRC e su Hamming(7,4). Usa la parità pari.
- Data la stringa ASCII "HI" (0x48 = 1001000, 0x49 = 1001001), calcola VRC per ogni byte e il BCC/LRC finale.
- Codifica in Hamming(7,4) il nibble 0110. Mostra p1,p2,p4 e la codeword completa.
- Ricevi
1011010(Hamming 7,4). Calcola sindrome s1 s2 s4, individua l'errore se presente e correggi. - Spiega perché VRC+LRC fallisce con 4 errori rettangolari (pattern a rettangolo).
1) "HI": H=1001000 → 3 uni → p=1 → 10010001. I=1001001 → 3 uni? 1001001 ha 3 uni → p=1 → 10010011. LRC colonna: bit per bit XOR/parità: b6:1+1=0 pari, b5:0+0=0, b4:0+0=0, b3:1+1=0, b2:0+0=0, b1:0+0=0, b0:0+1=1 → LRC = 0000001 + suo VRC pari=1 → BCC=00000011.
2) 0110: d1=0 d2=1 d3=1 d4=0. p1 = d1+d2+d4 =0+1+0=1 → p1=1. p2 = d1+d3+d4=0+1+0=1 → p2=1. p4 = d2+d3+d4=1+1+0=0 pari→0. Codeword: 1 1 0 0 1 1 0 = 1100110.
3) Ricevuto 1011010: s1=r1+r3+r5+r7=1+1+0+0=2 pari→0, s2=r2+r3+r6+r7=0+1+1+0=2 pari→0, s4=r4+r5+r6+r7=1+0+1+0=2 pari→0 → sindrome 000 nessun errore! I dati sono 1010 (pos 3,5,6,7).
4) Rettangolo: 2 errori su riga1 e 2 sulla stessa 2 colonne su riga2 → ogni riga e colonna ha parità pari ancora, quindi non rilevato. Serve Hamming o CRC per questi pattern.
9. Riepilogo e concetti chiave
📚 Prossimo passo - Controllo del flusso: ARQ e Sliding Window
Ora che sappiamo rilevare e correggere gli errori, dobbiamo decidere cosa fare quando c'è un errore: Stop-and-Wait, Go-Back-N e Selective Repeat. Preparati a simulare finestre scorrevoli e timeout.