Codici correttori d’errore: Hamming, CRC e codici moderni

Shannon ha dimostrato che si può trasmettere quasi senza errori fino alla capacità del canale, ma solo codificando i dati: aggiungendo bit di ridondanza calcolati in modo che il ricevitore possa scoprire e correggere gli errori. I codici correttori sono in ogni comunicazione digitale e in ogni memoria: CD, QR code, SSD, Wi-Fi, 5G, sonde spaziali. In questa lezione vediamo la distanza minima, il codice di Hamming con un esempio completo, i codici di rilevazione CRC e i codici moderni.

La distanza di Hamming

Un codice a blocco trasforma bit d’informazione in una parola di codice di bit; il rapporto è il tasso del codice. La distanza di Hamming tra due parole è il numero di bit in cui differiscono; la distanza minima del codice è la più piccola tra tutte le coppie di parole di codice.

Teorema. Un codice con distanza minima rileva fino a errori e ne corregge fino a

Dimostrazione. Se avvengono al più errori, la parola ricevuta non può coincidere con un’altra parola di codice (che dista almeno ), quindi l’errore si vede. Per la correzione si decide per la parola di codice più vicina. Se gli errori sono al più , con , la parola trasmessa dista al più da quella ricevuta, mentre ogni altra parola di codice ne dista almeno (disuguaglianza triangolare). La più vicina è quindi quella giusta. ∎

Geometricamente: attorno a ogni parola di codice c’è una “sfera” di raggio , e le sfere non si toccano.

Il codice di Hamming (7,4)

Quattro bit d’informazione e tre bit di parità , ciascuno uguale all’OR esclusivo di tre bit d’informazione. Il modo più chiaro di vederlo sono tre cerchi:

Ogni cerchio deve contenere un numero pari di 1. Un errore su un bit lo si individua da quali cerchi risultano dispari: ogni bit sta in una combinazione diversa di cerchi.

Esempio. Dati . Le parità: , , . Si trasmettono 7 bit. Se il canale inverte , il ricevitore ricalcola le parità: il cerchio verde () e quello rosso () risultano dispari, quello blu pari. L’unico bit che sta nel verde e nel rosso ma non nel blu è : lo si inverte e il dato è corretto.

In forma algebrica, i tre controlli formano la sindrome, un numero di 3 bit che vale zero se non ci sono errori e indica altrimenti quale dei 7 bit è sbagliato. Il codice ha : corregge un errore per parola, con un tasso di 4/7. Aggiungendo un bit di parità complessiva (codice esteso, ) si correggono gli errori singoli e si rilevano i doppi: è il codice SECDED delle memorie ECC dei server.

La rilevazione: il CRC

Spesso basta accorgersi dell’errore e chiedere di ritrasmettere. Il controllo di ridondanza ciclica (CRC) tratta il messaggio come un polinomio a coefficienti binari, lo divide per un polinomio generatore fissato e aggiunge il resto della divisione. Il ricevitore ripete la divisione: un resto non nullo indica un errore. Un CRC a 32 bit (quello di Ethernet, ZIP, PNG) rileva tutti gli errori a raffica fino a 32 bit e lascia passare un errore casuale con probabilità di circa . Si calcola con un registro a scorrimento e qualche porta XOR, o con una tabella in software.

I codici moderni

• Codici convoluzionali con decodifica di Viterbi: codificano il flusso continuo con un piccolo registro a scorrimento; usati per decenni nella telefonia mobile e nei satelliti.
• Reed-Solomon: lavorano su simboli di più bit e sono fortissimi contro gli errori a raffica. Sono nei CD e DVD (dove correggono graffi di millimetri), nei QR code (che restano leggibili anche se in parte coperti) e nelle trasmissioni dalle sonde spaziali.
• Turbo codici e LDPC: con decodifica iterativa, scambiando probabilità invece di decisioni nette, arrivano a pochi decimi di decibel dal limite di Shannon. Gli LDPC sono nel Wi-Fi, nel 5G, nella televisione satellitare e negli SSD; i codici polari, i primi a raggiungere la capacità in modo dimostrato, nei canali di controllo del 5G.

L’interallacciamento. I codici correggono bene errori sparsi, male quelli concentrati, e i canali con evanescenza producono proprio raffiche di errori. Prima di trasmettere si mescola l’ordine dei bit (interleaving), e il ricevitore lo ripristina: una raffica sul canale diventa una serie di errori isolati, che il codice corregge.

Quanto si guadagna. Con un buon codice a tasso 1/2, una probabilità d’errore di 10⁻⁵ si ottiene con circa 1-2 dB di invece dei 9,6 dB della BPSK non codificata: un guadagno di codifica di 7-8 dB, che vale come quintuplicare la potenza trasmessa, al prezzo della banda e del calcolo per la decodifica.