Domenica scorsa è stata Pasqua. Ma come si sapeva che proprio quel giorno era Pasqua? No, non venitemi a dire “la prima domenica dopo il primo plenilunio di primavera”, perché comincio a chiedervi “quando comincia la primavera?” (astronomicamente per esempio in questi anni cade il 20 marzo, e addirittura avremo degli anni in cui cadrà il 19 marzo) e “quando è domenica?” (ecclesiasticamente la domenica comincia al tramonto del sabato, con i primi vespri). A differenza degli islamici, almeno quelli sauditi, per cui boskovianamente “Ramadan comincia con prima falce di luna” (e quest’anno ci sono state due date diverse per l’inizio, quella astronomica e quella visuale), per i cristiani è necessario sapere già all’Epifania quando sarà Pasqua e quindi si è preparato tutto un armamentario di conteggi, con epatta e numero aureo, per avere la data sempre a disposizione. Ah, per definizione la primavera inizia il 21 marzo. Ma per fare questi conti occorre avere una serie di tabelle, e soprattutto tenere conto che l’approssimazione del ciclo di Metone, per cui 19 anni corrspondono esattamente a 235 mesi lunari, è per l’appunto un’approssimazione… oltre a incasinare il tutto passando al calendario gregoriano che segue sì più correttamente le stagioni ma complica parecchio i conti.

A questo punto entra in scena uno che i conti li sapeva fare sin troppo bene: Carl Friedrich Gauss. Il burbero genio aveva probabilmente qualche ora di svago e nel 1800 preparò un metodo che permette di calcolare a mente (d’accordo, se ti chiami Gauss…) la data della Pasqua per tutto un secolo; con il calendario giuliano in realtà il conto è perpetuo, mentre con quello gregoriano occorre imparare anche due numeri specifici per ciascun secolo. La buona notizia è che dal 1900 al 2099 quei due numeri restano identici, quindi per quanto ci riguarda il problema non si pone. Ma veniamo al conteggio, che richiede di usare l’aritmetica modulare, cioè il resto della divisione per un qualche numero intero. Dato un anno X, calcoliamo a = X mod 19, b = X mod 4, c = X mod 7; poi calcoliamo d = (19a + M) mod 30 ed e = (2b + 4c + 6d + N) mod 7. A questo punto sappiamo che Pasqua sarà il (22 + d + e) marzo, dove ovviamente il 32 marzo è il primo aprile e così via.

I più perspicaci di voi, cioè tutti, avranno notato che ho aggiunto altre due variabili, M e N. Nel calendario giuliano le cose erano semplici: valevano rispettivamente 15 e 5. Per il calendario gregoriano i loro valori cambiano di secolo in secolo: come dicevo sopra, però, dal 1900 al 2099 abbiamo M=24 e N=6. A questo punto possiamo fare la controprova: nel 2026 abbiamo a = 2026 mod 19 = 12, b = 2026 mod 4 = 2, c = 2026 mod 7 = 3, d = (19·12 + 24) mod 30 = 12 ed e = (2·2 + 4·3 + 6·12 + 5) mod 7 = 2. Infine 22+12+2 = 36, pertanto Pasqua è il “36 marzo” vale a dire il 5 aprile. Per il 2027 abbiamo a = 2027 mod 19 = 13, b = 2027 mod 4 = 3, c = 2027 mod 7 = 4, d = (19·13 + 24) mod 30 = 1 ed e = (2·3 + 4·4 + 6·1 + 5) mod 7 = 5, quindi Pasqua è il 22+1+5 cioè il 28 marzo. Per completezza aggiungo due eccezioni: se il conto dà 26 aprile allora Pasqua è il 19 aprile, mentre se dà 25 aprile con d = 28, e=6 e a=10 allora è il 18 aprile. Sempre per completezza, la prima formula di Gauss valeva solo dal 1700 al 1899; nel 1807 la generalizzò aggiungendo una formula per calcolare M e N e nel 1816 corresse un errore.

Come ha fatto Gauss a trovare questa formula? Per una volta ce l’ha spiegato: la prima parte serve ad approssimare la posizione della luna e la seconda per aggiustare le cose secondo il computo ecclesiastico. Se siete persone amanti del rischio, Wikipedia in inglese ha la spiegazione… oppure vi leggete il testo originale in tedesco. Può infine essere divertente notare che secondo il calendario gregoriano le date della Pasqua si ripeterebbero ogni 5 milioni e 700000 anni, che la daa più frequente è il 19 aprile mentre quella meno probabile è il 22 marzo che capita meno di una volta ogni 200 anni. Pensate solo a cosa succederebbe se si fissasse una volta per tutte la data della Pasqua, tipo alla seconda domenica di aprile: tutto questo lavoro per nulla!

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’è qualche errore, mentre in questo modo possiamo ricostruire qual era il messaggio originale se tra quei bit ce ne sono fino a tre sbagliati, e se ce ne sono quattro possiamo comunque sapere 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…