La teoria dei codici a correzione di errore è molto ampia, perché ci sono vari tipi di errore possibile quando viene trasmessa una codifica (diciamo binaria) del dato, e il valore a priori della probabilità di un errore fa scegliere un metodo rispetto a un altro. Per esempio, i primi codici ASCII erano a 7 bit in modo da usare l’ottavo come codice di parità: in questo modo ci si poteva accorgere di un singolo errore, anche se non si sapeva su quale bit, e chiedere che il carattere venisse ritrasmesso. Naturalmente già quand’ero ragazzo io non valeva più la pena di testare per un errore la cui probabilità era infima, e così si passò alle codifiche che usavano tutti e otto i bit.
Ma cosa succede quando arrivano i segnali da una sonda spaziale? Come potete immaginare, il tasso di errore è molto più alto, e soprattutto farsi rispedire i dati non è in genere un’opzione usabile. Servono quindi altri tipi di codice: quello che per esempio è stato usato sulle sonde Voyager 1 e Voyager 2, che non avevano molta memoria a disposizione e quindi dovevano mandare subito via i dati ottenuti, è il codice di Golay. Esso trasforma un insieme di 12 bit in uno da 24. Raddoppiamo insomma il materiale da spedire: però se mandassimo due copie identiche potremmo al più accorgerci che c’è aualche errore, mentre in questo modo possiamo ricostruire qual era il messaggio originale se tra quei bit ce ne sono fino a tre svagliati, e se ce ne sono quattro possiamo comunque che c’è stato un errore. (Con più di quattro errori sbagliamo proprio a ricavare il messaggio originale, ma se ci sono così tanti errori possiamo fare davvero poco, a meno di creare codici enormi)
codice di Golay (immagine di Parcly Taxel, da Wikimedia Commons)
Come funziona in pratica un codice di Golay? Si prendono i bit di input a dodici per volta, si costruisce un vettore (a dodici elementi) e lo si moltiplica per la matrice 12×24 mostrata qui sopra, ottenendo un nuovo vettore a 24 elementi che è quello che spediamo. (La moltiplicazione è binaria, il che significa che il risultato della moltiplicazione è da prendere modulo 2.) La cosa bella è che se prendiamo due qualunque tra i 4096 possibili vettori di input di 12 elementi e consideriamo gli output corrispondenti possiamo essere certi che ci saranno almeno otto bit diversi. Questa misura di diversità è la distanza di Hamming: come dicevo sopra, se l’output ci è arrivato corrotto per al massimo tre bit ci sarà un unico codice tra i 4096 di output per cui la distanza di Hamming è al massimo 3, e che è dunque quello effettivamente spedito: con quattro bit errati sappiamo che c’è stato un errore, ma non siamo in grado di scegliere tra i due codici vicini.
Si può persino fare (leggermente) meglio. L’ultimo bit dell’output è semplicemente un controllo di parità: se lo eliminiamo ci resta un codice che ha vettori di 23 but come output ed è un codice perfetto, nel senso che se associamo a ciascun codice di output tutti quelli che hanno distanza da lui al massimo 3 completiamo tutto lo spazio dei possibili 2^23 vettori di output. I codici perfetti sono piuttosto rari: il fatto che Golay ne riuscì a trovare uno anche abbastanza complicato nel 1949 la dice lunga sulla sua abilità.
Un’ultima curiosità: John D. Cook ha segnalato come Golay abbia anche ideato un codice ternario, dove i valori dei “trit” possono essere 0, 1, 2 (o −1, se lo volete bilanciato: tanto le operazioni in base 3 sono le stesse). In questo caso il codice esteso con il bit di parità trasforma sei trit in dodici, che hanno una distanza almeno 6 tra loro, mentre quello perfetto li trasforma in undici trit, che hanno una distanza di almeno 5. Peccato che non abbiamo computer ternari…
I libri che raccontano la matematica hanno un problema di base: i temi trattati sono sempre più o meno gli stessi, e quindi il povero autore deve trovare un modo per riuscire a distinguersi nel mare magnum di queste opere. Secondo me Schneierman ci è riuscito. Io con i miei soliti tempi mi ero comprato il volume non appena era stato pubblicato, e ne lo sono tenuto otto anni in libreria prima di leggerlo. Ora che finalmente ce l’ho fatta, posso dire di apprezzare le “note laterali” che affiancano il testo vero e proprio, e ho trovato alcune chicche che non conoscevo nonostante la mia non certo banale esperienza, come una nuova dimostrazione dell’infinità dei numeri primi e il modo di costruire terne pitagoriche usando numeri complessi. Anche lo stile di scrittura è piacevole: insomma un ottimo acquisto.
