Hai letto il titolo e ti sei incazzato, vero? Ti sei detto, tra te e te:

ma come si permette questo str*** di correggere il mio codice?

E invece no. Prematurata la supercazzola. Del tuo codice sorgente non me ne frega assolutamente niente. Compilalo, interpretalo, pushalo fixalo: fa il cavolo che ti pare. Questo articolo non riguarda il tuo codice, ma i codici. Quelli che non finiscono su un repository. Riguarda le trasmissioni, i canali rumorosi e i bit che partono da leoni e finiscono da cog*****. Riguarda il fatto che l’ingegneria, a un certo punto, si sia arresa: la realtà fa schifo, introduce errori ovunque e l’unico modo sensato per conviverci non è evitarli, ma correggerli. Questo articolo parla di codici a correzione di errore, proprio quelli che ti permettono di cercare "bioparco" senza ricevere... ehm lasciamo perdere. Insomma quei meccanismi che sono dietro le conversazioni digitali di tutti noi e che usiamo costantemente, senza nemmeno saperlo. Gli eroi senza mantello dell'informazione. Insomma quelli che assicurano che una informazione arrivi integra o, nel peggiore dei casi, consentono la rettifica. Beh dai il perimetro è chiaro. In questo articolo faremo tre cose:

  1. vedremo perché la ridondanza è necessaria
  2. analizzeremo due tecniche classiche (ripetizione e parity check)
  3. formalizzeremo il tutto con il concetto di distanza minima

Possiamo iniziare...

Dannato Open Space

Avete presente gli uffici open space? Sapete quali, no? Quelli che siamo una azienda moderna e invece non vogliono cacciare due soldi per i divisori. Pidocchiosi. Come se me ne fregasse qualcosa delle call altrui. Vabbé, non divaghiamo.

Avete presente, no?! C’è Pinco che parla con Pallino, il tizio perennemente in call, quello che urla al telefono e poi c’è il tizio che spara dardi di plastica col Nerf 2.0 (quello sono io, e non sto scherzando, è stato il miglior acquisto del 2025). Insomma, una cazzo di lambada. Ecco: i canali di comunicazione sono uguali. Ci sono migliaia di motivi di distrazione: interferenze con altri canali di comunicazione, deterioramento delle apparecchiature, impulsi elettrici e chi più ne ha più ne metta. E quando un bit si distrae, parte che è \(0\) ed arriva che è \(1\) (o viceversa). Tutto questo si chiama rumore, ed è il Moriarty delle comunicazioni: criminale invisibile, ma sempre presente.

Così come sostenere una conversazione in un open space diventa sempre più difficile man mano che il rumore aumenta, allo stesso modo la trasmissione dei dati diventa più complessa quando il canale di comunicazione è più rumoroso. Per farsi capire o si alza la voce (magari bestemmiando), oppure si è costretti a ripetersi. Dato che i bit non possono bestemmiare (poveracci), non ci resta che passare per la seconda strada. E questa strada ha un nome preciso: ridondanza. Aggiungiamo informazione alla trasmissione affinché il ricevente possa ricostruire correttamente il messaggio, anche quando il canale fa di tutto per rovinarlo.

Finalmente, Un Divisorio

Iniziamo questo viaggio mostrando perché la ridondanza é necessaria. Intuitivamente é abbastanza semplice da capire. Mia nonna non ci sente quindi mi armo di buona pazienza e una stessa frase la ripeto tre volte e la terza (forse, altrimenti mi arrendo) va a buon fine. Ma vediamo la cosa non con un approccio geriatrico ma più matematico, e consideriamo il seguente diagramma:

Noise Channel Figura 1. Trasmissione Rumorosa

Supponiamo di avere un canale di comunicazione, magari due bicchieri collegati con uno spago, nel quale la probabilità di corruzione del messaggio è \(p=0.1\) cioè del \(10\%\) (che sembra bassa ma è altissima. Immaginate che una lettera ogni \(10\) in un testo, sia sbagliata). Supponiamo inoltre che Alice voglia inviare a Bob un messaggio, e che questo messaggio sia una molto esplicativa lettera \(C\). C'è il \(90\%\) di probabilità che il messaggio che arriva a Bob sia effettivamente \(C\), ma non possiamo esserne sicuri. Quindi Alice ha una grande idea: trasmette più volte lo stesso messaggio. Invia quindi il messaggio \(CCC\). Vediamo cosa succede: la probabilità di ricevere correttamente un messaggio è \(p=0.9\) per cui la probabilità di ricevere correttamente tutte e tre le \(C\), essendo eventi indipendenti, è:

$$ p \left( \text{zero errori} \right) = 0.9 \cdot 0.9 \cdot 0.9 = 0.729 $$

Supponiamo che avvenga un errore di trasmissione nei messaggi. Bob, che sa di aver ricevuto tre volte lo stesso messaggio, si affida alla maggioranza pensando: se ricevo due \(C\) e una \(B\), dato che la probabilità di trasmissione corretta è più alta di quella errata, è probabile che la \(B\) fosse in realtà una \(C\). La sa lunga il buon Bob. Quindi è confidente del fatto che il messaggio da ricevere sia la lettera \(C\), ed ha ragione. Ma vediamo perché. Supponendo che sia avvenuto uno, ed un solo errore di trasmissione, in cui la \(C\) è diventata una \(B\). Il messaggio ricevuto è necessariamente uno di questi: \(CCB\), \(CBC\), \(BCC\). Andiamo a vedere con quale probabilità si puó presentare ogni messaggio con esattamente un errore:

$$ \begin{aligned} p \left( CCB \right) &= 0.9 \cdot 0.9 \cdot 0.1 = 0.081 \\[6pt] p \left( CBC \right) &= 0.9 \cdot 0.1 \cdot 0.9 = 0.081 \\[6pt] p \left( BCC \right) &= 0.1 \cdot 0.9 \cdot 0.9 = 0.081 \\[6pt] \end{aligned} $$

E quindi la probabilità di ricevere uno, tra i messaggi errati è:

$$ p \left( \text{un errore} \right) = 3 \cdot 0.081 = 0.243 $$

Arrivati a questo punto sappiamo tre cose:

  1. La probabilità di ricevere il messaggio senza errori è \(p=0.729\).
  2. La probabilità di ricevere un messaggio con esattamente un errore è \(p=0.243\).
  3. Quando si riceve un messaggio con esattamente un errore, Bob riesce a ricostruire il messaggio correttamente.

Questo vuol dire che il messaggio arriva a destinazione e viene decodificato correttamente in quattro differenti casi. Possiamo quindi scrivere la probabilità che il messaggio sia decodificato correttamente come:

$$ p \left( \text{decodifica corretta} \right) = p \left( \text{un errore} \right) + p \left( \text{zero errori} \right) = 0.243 + 0.729 = 0.972 $$

Di conseguenza la probabilità di decodifica errata è:

$$ p \left( \text{decodifica errata} \right) = 1 - p \left( \text{decodifica corretta} \right) = 1 - 0.972 = 0.028 $$

Direi perfetto. Abbiamo visto come avere ridondanza nelle trasmissioni, ha portato a un calo della probabilità di errore dal \(10\%\) al \(2.8\%\). Bel risultato no?! In ogni caso, come tutti sappiamo, nelle trasmissioni non si inviano lettere ma sequenze binarie. Supponendo di avere dispositivi che inviano solo \(4\) simboli: \(A, \, B, \, C, \, D\), questi saranno codificati in questo modo:

  • \(A=00\)
  • \(B=01\)
  • \(C=10\)
  • \(D=11\)

Inviare un messaggio con uno di questi simboli, sfruttando la ridondanza vista in precedenza, vuol dire inviare:

  • \(000000\) per inviare la lettera \(A\)
  • \(010101\) per inviare la lettera \(B\)
  • \(101010\) per inviare la lettera \(C\)
  • \(111111\) per inviare la lettera \(D\)

Chi decodifica il messaggio, aspetta di ricevere il codeword cioè l'insieme (in questo caso) di sei bit, prima di iniziare la decodifica. Per concludere questo paragrafo, se ve lo steste chiedendo la formula generica per il calcolo della probabilità di errore di un singolo bit, è:

$$ p_e = \sum_{k=\lceil n/2\rceil}^{n} \binom{n}{k}\,p^k(1-p)^{\,n-k} $$

Formula 1. Probabilità Di Errore

dove:

  • \(p_e\) è la probabilità che la decodifica sia errata
  • \(n\) è il numero di ripetizioni
  • \(p\) è la probabilità che un bit venga flippato
  • \(k\) è il numero di bit errati
  • \(\binom{n}{k}\) numero di modi diversi in cui possono esserci \(k\) errori
  • \(p^k\) probabilità che quei \(k\) bit siano errati
  • \((1-p)^{\,n-k}\) probabilità che gli altri \(n-k\) siano corretti
  • \(\lceil n/2\rceil\) soglia di maggioranza oltre la quale la decodifica fallisce
  • \(\sum\) somma di tutti gli eventi che portano a errore

La formula fornisce la probabilità di errore di un singolo bit informativo, codificato mediante un codice a ripetizione di lunghezza \(n\), da cui otteniamo che la probabilità che un messaggio sia ricevuto correttamente è:

$$ p_c = 1-p_e $$

Se vogliamo calcolare la probabilità che un messaggio di lunghezza arbitraria sia decodificato correttamente, basta scrivere:

$$ p_c = (1-p_e)^L $$

dove \(L\) è il numero di bit del messaggio da inviare. Ad esempio se il messaggio è uno tra:

$$ 00, \, 01, \, 10, \, 11 $$

come visto in precedenza, abbiamo che \(L=2\).

Un Po’ Costoso Il Divisorio

Nel paragrafo precedente abbiamo visto un esempio molto semplice di ridondanza, che ha permesso non solo di rilevare un errore, ma anche di correggerlo. Ma questo a quale prezzo? Dovevamo inviare \(2\) bit e ne abbiamo inviati \(6\). Direi un pó costosetto, triplica la lunghezza del messaggio. Quindi la domanda è: davvero abbiamo bisogno di correggere l'errore? Magari siamo in una situazione in cui conviene reinviare il messaggio piuttosto che appesantirlo, e quindi ci basta anche solo accorgerci dell'errore. In questi casi possiamo sempre sfruttare l'ormai amica ridondanza, ma in maniera molto più economica.

Introduciamo quindi il parity check. È un semplicissimo meccanismo per stabilire se c'è stato un errore di trasmissione ma con l'aggiunta di un solo misero bit. Andiamolo a vedere con un esempio. Supponiamo di dover inviare un messaggio a \(7\) bit (è solo per fare un esempio, il numero di bit puó ovviamente essere arbitrario): \(0110010\). Quello che facciamo è aggiungere un bit, chiamato bit di parità che serve a rendere pari il numero di bit uguali a \(1\), nel messaggio da inviare. Da questa definizione quindi, possiamo formulare il bit di parità come:

$$ p = s \pmod 2 $$

Formula 2. Definizione Bit Di Parità

dove \(s\) è il numero di bit pari ad \(1\). Per cui:

  • se \(s\) è pari, \(p=0\)
  • se \(s\) è dispari, \(p=1\)

Se non sapete perché è evidente che non avete letto questo articolo dove parlo (anche) di aritmetica modulare. Nel messaggio precedente, ci sono tre bit pari ad \(1\) quindi, essendo notoriamente un numero dispari, abbiamo che \(p=1\). Il messaggio che sarà inviato per cui è: \(0110010\color{green}{1}\).

Se avviene un errore, o più in generale un numero dispari di errori, la parità cambia e quindi siamo in grado di dire che c'è stato un errore di trasmissione. Consideriamo il seguente messaggio: \(1110010\). In questo caso \(s=4\) e quindi \(p=0\), per cui il messaggio inviato sarà: \(11100100\). Supponiamo che avviene un errore di trasmissione e un bit passa da \(0\) a \(1\):

$$ 11100100 \rightarrow 111\color{red}{1}0100 $$

Vediamo che l'ultimo bit è \(0\) quindi il numero di \(1\) dovrebbe essere pari, ma invece è dispari perché con la corruzione non sono più quattro, ma cinque. C'è quindi un errore, e anche se non sappiamo dove chissene, chiediamo la ritrasmissione. Ma vediamo cosa succede con due errori:

$$ 11100100 \rightarrow 111\color{red}{11}100 $$

L'ultimo bit è sempre \(0\) ma essendoci stati due errori abbiamo sei bit pari ad \(1\). La parità non è cambiata e quindi non ci accorgiamo dell'errore.

Il parity check è quindi un codice che usa ridondanza per accorgersi degli errori, ma non per correggerli. È economico, veloce, e profondamente limitato.

Un Divisorio, Ma Meglio

Abbiamo visto che il parity check è economico, veloce e limitato. Sa dirci che qualcosa è andato storto, ma non ha la minima idea di dove. Ci lascia un po' con l'amaro in bocca no?! Sembra che siamo in un impasse. Se ripetiamo i bit il costo aumenta, se non ripetiamo i bit non sappiamo dove andare a correggere. Per fortuna che esistono le vie di mezzo. Questa via di mezzo consiste non nell'aggiungere più informazione, ma nell'organizzarla meglio. L’idea è semplice: invece di trattare il messaggio come una sequenza di bit in fila indiana, lo disponiamo sotto forma di matrice. Non perché abbiamo il feticcio delle tabelle, ma perché una matrice ci permette di controllare il messaggio in due direzioni indipendenti: righe e colonne. A questo punto aggiungiamo bit di parità e non uno solo, ma per ogni riga e per ogni colonna. La ridondanza non cresce in modo esplosivo, ma viene distribuita. Il risultato è che un singolo errore rompe una riga e una colonna ben precise, individuando le coordinate dell'errore stesso. Ma bando alle parole e mostriamo un esempio. Supponiamo di dover inviare un messaggio da \(20\) bit: \(10011011001100101011\), usare la ridondanza è un bagno di sangue per cui disponiamo i bit in una matrice \(4 \times 5\).

$$ \begin{pmatrix} 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 \end{pmatrix} $$

Calcoliamo i bit di parità sulle righe e sulle colonne ed otteniamo

$$ \begin{pmatrix} 1 & 0 & 0 & 1 & 1 & \color{green}{1} \\ 0 & 1 & 1 & 0 & 0 & \color{green}{0} \\ 1 & 1 & 0 & 0 & 1 & \color{green}{1} \\ 0 & 1 & 0 & 1 & 1 & \color{green}{1} \\ \color{green}{0} & \color{green}{1} & \color{green}{1} & \color{green}{0} & \color{green}{1} & \color{green}{1} \end{pmatrix} $$

Ed abbiamo ottenuto una matrice \(5 \times 6\). Su \(20\) bit abbiamo aggiunto \(10\) bit di ridondanza (e non \(40\)). Supponiamo che il ricevente ottenga la seguente matrice:

$$ \begin{pmatrix} 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & \color{red}{1} & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 \\ \end{pmatrix} $$

andando a controllare i bit di parità sull'ultima riga e l'ultima colonna, vediamo che sulla terza riga c'è un numero dispari di \(1\), e stessa cosa nella quarta colonna. Per cui l'errore è avvenuto nelle coordinate \((3, \, 4)\). Non solo abbiamo riconosciuto un errore, ma possiamo anche correggerlo. Supponiamo ora di ricevere questa matrice:

$$ \begin{pmatrix} 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & \color{red}{0} & \color{red}{0} & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 \\ \end{pmatrix} $$

In questo caso sono avvenuti due errori, in particolare nella colonna due e colonna tre della seconda riga. Il bit di parità sulla riga peró rimane corretto, mentre quelli delle colonne due e tre sono sbagliati. Per cui sappiamo che è avvenuto un errore, ma non siamo in grado di identificare una posizione. Quindi questo metodo è più intelligente ma ha dei limiti. Riesco ad accorgermi che qualcosa è andato storto anche con più errori, ma posso correggerne uno solo.

Raddrizziamo Sti Divisori

A questo punto la domanda sorge spontanea: esiste una legge che metta in relazione il numero di bit che aggiungiamo e la nostra capacità di correggere gli errori? Cioè, possiamo quantificare quanto un codice sia robusto al rumore? Partiamo da una situazione volutamente banale. Supponiamo che gli unici messaggi validi siano

$$ 000000 \text{ e } 111111 $$

Se il ricevente ottiene

$$ 000\color{red}{1}00 $$

non ci sono grandi dubbi: questo messaggio assomiglia molto di più a \(000000\) che a \(111111\) e quindi è semplice intuire il messaggio originale. Ma se invece ricevesse

$$ 000\color{red}{111} $$

che facciamo?! Non possiamo più sapere quale dei due è quello originale. Il problema non è l’errore in sé, ma l’ambiguità: il messaggio ricevuto è compatibile con due messaggi validi diversi. Quello che stiamo facendo, anche se non lo stiamo ancora chiamando per nome, è contare in quanti bit i messaggi differiscono, stiamo cioè misurando la distanza di Hamming. Nel nostro esempio abbiamo due soli messaggi inviabili che differiscono tra loro in tutti e sei i bit, la distanza minima del codice è quindi \(d_{min}=6\). La distanza minima del codice è il numero minimo di bit che devono essere alterati per trasformare un messaggio valido in un altro messaggio valido. Quando un messaggio viene ricevuto quello che facciamo è applicare il nearest neighbor decoding, cioè scegliere il messaggio valido più vicino in termini di bit diversi. Finché il messaggio ricevuto è più vicino a una sola codeword, la decodifica è possibile. Quando invece finisce esattamente “a metà strada”, ogni decisione diventa arbitraria. Vediamo in numeri cosa si intende:

$$ d(000000, 000\color{red}{1}00) = 1 \\ d(111111, 000\color{red}{1}00) = 5 $$

Nel caso di un solo errore, la distanza di Hamming minore tra \(000100\) e le codewords possibili è \(1\) per cui sappiamo che la codeword corretta è \(000000\).

$$ d(000000, 000\color{red}{11}0) = 2 \\ d(111111, 000\color{red}{11}0) = 4 $$

Nel caso di due errori, la distanza di Hamming minore è \(2\), per cui vale lo stesso discorso di prima.

$$ d(000000, 000\color{red}{111}) = 3 \\ d(111111, 000\color{red}{111}) = 3 $$

Nel caso di tre errori, non c'è una distanza di Hamming minore, per cui abbiamo una ambiguità. Da qui discende una prima conseguenza importante. Diciamo che un codice è in grado di rilevare (e non correggere) fino a \(s\) errori, se cambiando al più \(s\) bit non è possibile trasformare una codeword valida in un’altra. Questo accade quando

$$ d_{min} \geq s + 1 $$

Torniamo al nostro esempio. La diseguaglianza ci dice che fino a \(s=5\) possiamo accorgerci che è avvenuto un errore, infatti la condizione

$$ 6 \geq 5 + 1 $$

è vera, e quindi fino a \(s=5\) abbiamo una codeword non valida rispetto quelle possibili. Se invece \(s=6\), stiamo trasformando tutti i bit e quindi passiamo dalla codeword valida \(000000\) all'altra valida \(111111\) e non siamo più in grado di dire se è avvenuto un errore.

Abbiamo trovato una condizione che collega la rilevazione degli errori alla distanza minima, ma correggerli è tutta un'altra storia. Non basta sapere che qualcosa è andato storto, bisogna anche sapere da che parte tornare indietro. Per evitare ambiguità, il messaggio ricevuto deve rimanere più vicino a una sola codeword valida. Questo è possibile solo finché il numero di errori è strettamente minore di metà della distanza minima. Il numero massimo di errori correggibili è quindi

$$ t = \left\lfloor \frac{d_{min} - 1}{2} \right\rfloor $$

Nel nostro esempio, con \(d_{min} = 6\), otteniamo:

$$ t = \left\lfloor \frac{6 - 1}{2} \right\rfloor = 2 $$

Il che significa che fino a due errori il messaggio ricevuto resta sempre più vicino a una sola codeword, il che torna con quanto visto in precedenza.

Per riassumere questo ginepraio di numeri e lettere, possiamo dire che la distanza minima di un codice \(d_{min}\), governa la robustezza al rumore e ci permette di definire due condizioni:

$$ d_{min} \geq 2t + 1 $$

Formula 3. Condizione Di Correzione

e

$$ d_{min} \geq s + 1 $$

Formula 4. Condizione Di Rilevazione

Se vera, la condizione di correzione ci dice che il codice può correggere fino a \(t\) errori e, se vera la condizione di rilevazione, ci dice che il codice può rilevare fino a \(s\) errori.

Facciamo un piccolo passo indietro e applichiamo le leggi appena trovate.

Caso 1

Riprendiamo questo esempio. Il codice definito era:

  • \(000000\) per inviare la lettera \(A\)
  • \(010101\) per inviare la lettera \(B\)
  • \(101010\) per inviare la lettera \(C\)
  • \(111111\) per inviare la lettera \(D\)

quindi la distanza minima (che trasformi ad esempio \(A\) in \(B\)) è \(d_{min}=3\) (e piú in generale, \(d_{min}\) è pari al numero di ripetizioni). Questa ci permette di ricavare dalla condizione di rilevazione, che possiamo riconoscere fino a \(s=2\) errori, e da quella di correzione che possiamo correggere \(t=1\) errore, che torna con quanto visto.

Caso 2

Riprendiamo gli esempi visti qui. Nel caso monodimensionale avevamo messaggi di lunghezza \(8\) con bit di parità. La distanza minima è \(d_{min}=2\), se prima era più intuitivo questa volta lo spiego. Consideriamo il messaggio \(00000000\), supponendo che un bit venga corrotto otteniamo \(\color{red}{1}0000000\) che non è valido in quanto non torna con la parità e quindi non fa parte dell'insieme dei codewords. Invece con due errori potremmo ottenere \(\color{red}{1}000000\color{red}{1}\) che è un messaggio valido, e dista \(2\). Applicando le solite condizioni abbiamo che \(s=1\) e \(t=0\) e quindi ci accorgiamo di un errore ma non ne correggiamo nessuno.

Considerando il caso bidimensionale invece, per passare da una codeword valida ad un'altra valida, devo rompere almeno due righe e due colonne e quindi \(d_{min}=4\) da cui abbiamo che rileviamo fino a \(s=3\) errori, e correggiamo fino a \(t=1\) errore.

In questi ultimi due esempi c'è da fare una riflessione. Infatti se nell'esempio riportato (ma un discorso simile si puó fare anche per il caso monodimensionale) avvenisse un errore per colonna, noi ci accorgeremmo di tutti gli errori superando il valore di \(s\) trovato. Ma questo non rompe la condizione perché mentre la condizione ci dà una garanzia, rilevare più di \(s\) errori non è sempre garantito, infatti ce ne accorgiamo solo in casi particolari (come appunto un errore per colonna).

Conclusioni

Siamo arrivati alla fine di questo primo articolo. Vi dirò, la strada è ancora tanta e qui si è solo scalfita la superficie. Abbiamo visto, con esempi semplici ma concreti, cosa sono i codici a correzione di errore. Abbiamo capito perché la ridondanza è necessaria, e come una migliore organizzazione dell’informazione possa permetterci non solo di rilevare gli errori, ma anche di correggerli, spesso con uno sforzo sorprendentemente contenuto. Nei prossimi articoli entreremo nel vivo con esempi più strutturati e potenti: codice di Hamming, Reed-Solomon e compagnia bella. Lì vedremo come queste tengono in piedi il mondo digitale di tutti i giorni. Per chi volesse smanettare un po’, ho scritto gli esempi visti in questo repo così potete sporcarvi le mani senza dover reinventare la ruota.

Alla Prossima.