Codici a correzione d'errore spiegati

Nessun canale è perfetto. I raggi cosmici invertono bit nella memoria, i graffi cancellano parti di un disco e i segnali radio si affievoliscono. Invece di sperare per il meglio, i sistemi digitali aggiungono ridondanza in modo ingegnoso, così che il destinatario possa ricostruire ciò che è stato inviato anche quando una parte arriva sbagliata. La matematica di questi codici, nata alla fine degli anni Quaranta, protegge silenziosamente quasi ogni bit che memorizziamo o inviamo.

Tre cerchi sovrapposti con i sette bit di una parola di codice di Hamming, con un cerchio evidenziato dove un controllo di parità fallisce
Tre cerchi sovrapposti con i sette bit di una parola di codice di Hamming, con un cerchio evidenziato dove un controllo di parità fallisce

Rilevare gli errori con la parità

La protezione più semplice è un singolo bit di parità: si aggiunge un 1 o uno 0 in modo che il numero totale di 1 sia pari. Se un bit si inverte lungo il percorso, il conteggio diventa dispari e il destinatario sa che qualcosa è andato storto. La parità non può dire quale bit è sbagliato, e due inversioni si annullano senza essere notate, ma costa poco ed è stata usata per decenni nelle memorie e nei collegamenti seriali. Rilevare un errore, però, è solo metà del lavoro: poi i dati vanno inviati di nuovo.

Correggere con la ripetizione

Per correggere un errore senza chiedere di nuovo, il destinatario ha bisogno di abbastanza ridondanza da metterlo in minoranza. Inviare ogni bit tre volte, 000 o 111, gli permette di seguire la maggioranza: un'inversione in una terna viene corretta. Il prezzo è alto: tre bit per ogni bit di dati, e due inversioni nella stessa terna vincono comunque. La domanda da cui nacque la teoria dei codici era se si potesse fare di meglio.

Il codice di Hamming

Nel 1947 Richard Hamming lavorava ai Bell Labs su un calcolatore a relè che leggeva i programmi da schede perforate. Quando la macchina trovava un errore durante il fine settimana si fermava e basta, e il lunedì Hamming tornava trovando solo elaborazioni sprecate. Se una macchina può rilevare un errore, si chiese, perché non può localizzarlo e correggerlo? La sua risposta, pubblicata nel 1950, invia 4 bit di dati come 7. Tre bit di parità, nelle posizioni 1, 2 e 4, controllano ciascuno un diverso gruppo di posizioni sovrapposte, scelto in modo che ogni errore singolo faccia fallire una combinazione unica di controlli.

La sindrome

Il destinatario ricalcola i tre controlli. Se vengono superati tutti, la parola è accettata. Se alcuni falliscono, scrivendo i controlli falliti come cifre binarie, con il controllo 4 come cifra più significativa, si ottiene un numero da 1 a 7: la sindrome, che è esattamente la posizione del bit invertito. Ripristinarlo restituisce la parola di codice. Il trucco funziona perché le posizioni sono numerate in modo che lo sviluppo binario di ciascuna elenchi i controlli a cui appartiene, ed è per questo che il codice appare così ordinato quando lo si disegna come tre cerchi sovrapposti.

La distanza di Hamming

La distanza di Hamming tra due parole è il numero di posizioni in cui differiscono. Nel codice (7,4) due parole di codice qualsiasi distano almeno 3. Una parola con un errore è ancora a distanza 1 dalla parola di codice inviata e ad almeno 2 da tutte le altre, quindi decodificarla nella parola di codice più vicina la corregge. In generale un codice le cui parole di codice distano almeno d rileva d − 1 errori e ne corregge (d − 1)/2, arrotondato per difetto. Aggiungere un bit di parità complessivo porta la distanza a 4, e si ottiene il codice esteso che corregge un errore e ne rileva due.

Il limite di Shannon

Nel 1948, due anni prima dell'articolo di Hamming, Claude Shannon dimostrò un teorema sorprendente. Ogni canale rumoroso ha una capacità, e a qualsiasi velocità inferiore a essa i dati si possono inviare con pochi errori quanto si vuole, usando codici abbastanza lunghi; al di sopra, gli errori non si possono evitare. Shannon dimostrò che tali codici esistono, ma non come costruirli. Trovare codici pratici che si avvicinino al suo limite ha richiesto mezzo secolo, dai codici di Reed-Solomon nel 1960 ai turbo codici nel 1993 e alla riscoperta dei codici LDPC (low-density parity-check, a controllo di parità a bassa densità).

Claude Shannon, che nel 1948, ai Bell Labs, precisò quanta informazione contiene un messaggio e la misurò in bit.
Claude Shannon, che nel 1948, ai Bell Labs, precisò quanta informazione contiene un messaggio e la misurò in bit.

Codici tutt'intorno a noi

I codici di Reed-Solomon permettono ai CD di suonare nonostante i graffi e ai codici QR di essere letti con fino al 30% del simbolo danneggiato. La memoria dei server usa codici di Hamming estesi per correggere i singoli bit invertiti dai raggi cosmici. Le immagini dei pianeti esterni inviate da Voyager erano protette da codici di Golay e poi di Reed-Solomon, e i codici LDPC e polari del 5G e del Wi-Fi spremono quasi ogni bit che il canale consente. Perfino il codice a barre di un libro e l'ultima cifra di un numero di conto bancario sono semplici codici a rilevamento d'errore.

Esploralo

Apri il simulatore di codici a correzione d'errore per codificare quattro bit di dati qualsiasi con il codice di Hamming (7,4), invertire i bit facendo clic su di essi nei cerchi o nella riga, e guardare i cerchi falliti e la sindrome indicare l'errore prima che il decodificatore lo ripari. Attiva il bit di parità extra per vedere rilevati gli errori doppi, e invia un messaggio attraverso un canale rumoroso per confrontare ciò che arriva con e senza il codice.

Domande frequenti

Qual è la differenza tra rilevamento e correzione degli errori?

Il rilevamento dice soltanto al destinatario che qualcosa non va, quindi deve richiedere di nuovo i dati; un bit di parità o un checksum fanno questo. La correzione permette al destinatario di ricostruire l'originale senza chiedere, il che richiede più ridondanza. I sistemi che non possono chiedere di nuovo, come una sonda spaziale a milioni di chilometri di distanza o un DVD, si affidano alla correzione.

Perché non inviare semplicemente tutto due volte?

Due copie mostrano che si è verificato un errore ma non quale copia sia giusta, e raddoppiano il costo. Tre copie permettono un voto a maggioranza ma lo triplicano. Il codice di Hamming corregge un errore singolo per blocco di sette con meno del doppio dei bit, e i codici più lunghi fanno molto meglio.

Chi era Richard Hamming?

Un matematico statunitense, 1915-1998, che lavorò al Progetto Manhattan e poi per trent'anni ai Bell Labs. Oltre che per i suoi codici, è noto per la finestra di Hamming nell'elaborazione dei segnali, per la distanza di Hamming e per la sua conferenza «You and Your Research». Ricevette il premio Turing nel 1968.

Un codice può correggere un numero qualsiasi di errori?

Solo con abbastanza ridondanza. Un codice può correggere fino a (d − 1)/2 errori per blocco, dove d è la distanza minima tra le parole di codice, e i codici più lunghi con più bit di controllo raggiungono un d maggiore. Il teorema di Shannon fissa il limite ultimo: nessun codice può superare la capacità del canale.

Pronto a provarlo?

Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.

Apri il simulatore di codici a correzione d'errore