Una delle applicazioni più sorprendenti e più utilizzate dei campi finiti (clicca qui per leggere il precedente articolo su questo argomento) è costituita dai cosiddetti codici correttori di errori. In questo primo post cercheremo di dare un’idea di cosa siano, mentre nel successivo vedremo come effettivamente sia possibile utilizzare campi finiti nella costruzione di codici correttori di errori.

internet-and-sources-cartoonPasted GraphicCodici correttori di errori sono utilizzati tutte le volte che si deve proteggere una certa informazione da possibili errori che potrebbero avvenire durante la trasmissione della informazione stessa. Ad esempio possiamo pensare alla trasmissione dei segnali digitali che sono alla base del Segnale Digitale per la televisione. Oppure alla semplice riproduzione di un CD musicale. Una qualsiasi seppur minima perturbazione dell’informazione iniziale può infatti danneggiare irreparabilmente la trasmissione o la riproduzione dell’informazione e rendere di fatto inutile l’informazione ricevuta. Eventuali fattori di “disturbo” possono essere nei nostri due esempi la presenza di nuvole o interferenze atmosferiche che disturbano il segnale oppure granelli di polvere o piccoli graffi presenti sulla superficie del CD.  Topo

CD rovinatoQuesti sono solamente due esempi, se ne potrebbero fare molti altri, che rivestono un ruolo fondamentale nella vita di tutti i giorni. Per cercare di spiegare meglio il funzionamento di questi codici e cercare di darne una trattazione più formale iniziamo da un breve esempio esplicativo.

Una questione di vita o di morte

Consideriamo il seguente scenario di guerra: un militare si trova in un terreno pieno di trappole e mine disseminate per impedirne l’attraversamento. Il nostro militare ha un collega che si trova in cima ad alto un palazzo o in un’altra postazione privilegiata e che quindi, grazie alla sua posizione, ha una visuale completa della situazione del terreno sottostante.

Topo campo minato

I due militari possono comunicare tra loro solo tramite un rudimentale marchingegno che può inviare e ricevere solo tre simboli, diciamo $$D,S,A$$: per loro convenzione questi tre simboli hanno significato rispettivamente Destra, Sinistra, Avanti, e servono per guidare il primo militare attraverso il terreno fino a fargli raggiungere una postazione sicura. A complicare ulteriormente la situazione, supponiamo che questi strumenti siano qualche volta difettosi, e che, di rado, avvenga qualche modifica tra ciò che viene inviato e ciò che  ricevuto. Ad un certo punto il primo militare si trova davanti un ostacolo e deve scegliere se andare a destra oppure a sinistra per aggirarlo: non ha la minima idea di quale alternativa si la migliore. Il secondo militare, vedendo che la strada a destra in realtà è un vicolo cieco, vuole comunicare al suo compagno di svoltare a sinistra. Quindi è intenzionato a mandare un messaggio scrivendo semplicemente $$S$$. Tuttavia, egli ha paura che un eventuale errore di trasmissione possa far sbagliare strada al collega e quindi si chiede cosa inviare invece di una semplice $$S$$ in modo tale da essere più sicuro che, anche nel caso avvengano degli errori durante la trasmissione, il suo collega abbia l’informazione corretta.

Una semplice soluzione

Il modo più semplice per ottenere in modo abbastanza sicuro che il soldato riceva la corretta informazione è il seguente: invece di inviare un solo simbolo ($$S$$) ne invia tre di fila $$SSS$$. Questo semplice stratagemma permette di incrementare la sicurezza della trasmissione: potrebbe accadere infatti che durante la trasmissione una di queste tre $$S$$ sia trasformata in qualcos’altro ma in questo caso il militare che riceve ad esempio $$SSD$$ oppure $$SAS$$ interpreterà il messaggio reputandolo come indicazione ad andare a sinistra, in quanto presuppone che sia più probabile che un solo errore durante la trasmissione piuttosto che due o più.

Facciamo un po’ di conti

 Cerchiamo ora di capire se la strategia adottata dal collega sia effettivamente conveniente per il militare che si trova sul campo. Per chiarire le idee supponiamo che il sistema di trasmissione sia “abbastanza buono” nel senso che la probabilità che inviando un certo simbolo questo arrivi mutato al destinatario sia inferiore al 50% (altrimenti, che tipo ti strumento sarebbe uno strumento che produce errori più di una volta su due?). Supponiamo ad esempio che mandando un qualsiasi simbolo, questo possa essere modificato nel secondo simbolo con probabilità del 20% e nel terzo simbolo con probabilità del 20% e che queste probabilità non cambino in base al simbolo inviato e a cosa si è inviato in precedenza. Queste assunzioni, per quanto abbastanza logiche, non sono quelle usuali, in quanto nei problemi pratici tutte queste probabilità cambiano in base alle condizioni, il che rende il tutto un po’ più complicato. Tuttavia per i nostri scopi divulgativi assumiamo che queste probabilità siano fissate ed immutabili.

Osserviamo quindi che se mandiamo un singolo simbolo, questo può essere ricevuto in maniera errata nel 40% dei casi. Se invece di un solo simbolo, ad esempio $$S$$, ne mandiamo tre copie $$SSS$$, il messaggio ricevuto può essere di vari tipi:

$$SSS,SSX,SXS,XSS,SXX,XSX,XXS,XXX$$ dove abbiamo indicato con $$X$$ un qualsiasi simbolo-errore diverso da $$S$$. Se calcoliamo quale sia la probabilità che queste otto combinazioni vengano effettivamente ricevute, otteniamo

$$\left(\frac{6}{10}\right)^3,\left(\frac{6}{10}\right)^2\times\left(\frac{4}{10}\right),\left(\frac{6}{10}\right)^2\times\left(\frac{4}{10}\right),$$

$$\left(\frac{6}{10}\right)^2\times\left(\frac{4}{10}\right),\left(\frac{6}{10}\right)\times\left(\frac{4}{10}\right)^2,$$

$$\left(\frac{6}{10}\right)\times\left(\frac{4}{10}\right)^2,\left(\frac{6}{10}\right)\times\left(\frac{4}{10}\right)^2,\left(\frac{4}{10}\right)^3.$$

Se interpretiamo le prime quattro possibilità come effettivamente derivanti da $$SSS$$, avremo una giusta interpretazione del messaggio con probabilità $$\frac{648}{1000}=64,8\%$$, che è superiore al $$60\%$$ iniziale. Supponendo invece che la probabilità di avere un errore su uno simbolo pari al $$10\%$$ invece che al $$40\%$$, passiamo dal $$90\%$$ iniziale di avere la giusta informazione al $$97,2\%$$ se decidiamo di adottare questo metodo di “ripetizione”.

Cercare un compromesso

Si potrebbe allora pensare che basti aumentare il numero di copie dello stesso simbolo da mandare per aumentare indefinitivamente la probabilità di una sua corretta ricezione. Se da una parte questo teoricamente è vero, dall’altra ciò si scontra con problemi derivanti dalle particolari limitazioni intrinseche nel tipo di trasmissione, come ad esempio il tempo di trasmissione (che non deve essere troppo elevato) o la quantità di informazione trasmessa (che spesso è limitata). In generale quello che si fa è cercare un metodo per trasferire informazione in maniera sicura ed efficiente a seconda dei casi.

Prime definizioni

Cerchiamo ora di dare qualche definizione matematica. Nell’esempio appena descritto possiamo usare 3 simboli ($$D,S,A$$) e abbiamo deciso di inviare stringhe formate da 3 simboli uguali. Il codice utilizzato allora è il seguente

$$\mathcal{C}=\{SSS,AAA,DDD\}$$ e le tre stringhe prendono il nome di parole codice. Diremo inoltre che la lunghezza del codice è 3, in quanto le stringhe sono formate da 3 simboli. Il codice inoltre ha un alfabeto di cardinalità 3 in quanto abbiamo a disposizione 3 simboli.  Ripetendo la costruzione precedente possiamo ad esempio formare i seguenti codici

$$\mathcal{C}_4=\{SSSS,AAAA,DDDD\}$$ oppure $$\mathcal{C}_5=\{SSSSS,AAAAA,DDDDD\}$$, che sono codici di lunghezza rispettivamente 4 e 5. Questi tre codici sono chiamati repetition codes, beh il motivo è facilmente intuibile!

Un importante parametro

Come abbiamo visto dal nostro esempio, quello che cerchiamo di fare  “correggere degli errori”, ovvero incrementare la probabilità di una corretta decodifica, anche in presenza di alcuni errori. La prima domanda a cui dovremmo dare risposta è: quanti errori al massimo possiamo correggere? Nel primo esempio abbiamo detto che interpretiamo le quattro stringhe $$SSS,SSX,SXS,XSS$$ come provenienti da $$SSS$$. Ovvero correggiamo al più un errore avvenuto nella trasmissione: supponiamo cioè che sia più facile che sia avvenuto un solo scambio di simboli, da $$S$$ a $$X$$, piuttosto che due. Questo è ragionevole tutte le volte che supponiamo che la probabilità di errore sia più bassa del $$50\%$$. Per calcolare il numero massimo di errori che il nostro codice riesce a correggere abbiamo bisogno di introdurre un nuovo concetto.

Distanza di Hamming

Prese due parole codice, ovvero due elementi del codice, possiamo definire la loro distanza come il numero di “posti” in cui esse differiscono. Consideriamo le nostre due parole codice come delle $$n$$-uple ordinate $$(a_1,a_2,\ldots,a_n)$$ e $$(b_1,b_2,\ldots,b_n)$$, dove $$n$$ è la lunghezza del codice, e quindi definiamo la distanza come

$$\#\{ i : i \in \{1,\ldots,n\} | a_i\neq b_i\}.$$

Possiamo quindi definire la distanza minima del codice $$\mathcal{C}$$ come il minimo delle distanze delle parole codice distinte, ovvero

$$d(\mathcal{C}):= \min_{w\neq w^{\prime} \in \mathcal{C}} d(w,w^{\prime}).$$

La distanza minima $$d(\mathcal{C})$$ è collegata al numero massimo di errori $$t$$ che un codice $$\mathcal{C}$$ può correggere dalla seguente formula:

$$t =\left\lfloor \frac{d(\mathcal{C})-1}{2}\right \rfloor$$, dove $$\left\lfloor a \right \rfloor$$ di un numero $$a$$ indica il numero intero più grande che sia minore o uguale di $$a$$. Con questa formula possiamo facilmente calcolare che, essendo la distanza minima del codice del nostro esempio pari a 3, il codice può correggere esattamente al più un errore. Con semplici calcoli possiamo ottenere che $$d(\mathcal{C}_4)=4$$ e $$d(\mathcal{C}_5)=5$$ e che quindi questi due codici possono correggere rispettivamente 1 e 2 errori. In questo caso è evidente che usare il codice $$\mathcal{C}_4$$ invece di $$\mathcal{C}$$ non porta nessun miglioramento, in quanto la capacità di correzione è sempre la stessa (ovvero 1), mentre chiaramente $$\mathcal{C}_4$$ è più “pesante” di $$\mathcal{C}$$, in quanto richiede la trasmissione di 4 simboli invece che 3.

Nel prossimo post vedremo come cercare di confrontare tra loro diversi codici e come possiamo creare codici utilizzando campi finiti.

CC BY-NC-SA 4.0
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.