Ridondanza, error correction, robustezza

Shannon dimostrò che i codici buoni esistono ma non disse quali. Hamming, frustrato da una macchina che ogni lunedì gli restituiva calcoli a metà, ne costruì uno: ridondanza disposta in modo così intelligente che il ricevitore non solo si accorge dell’errore, ma sa indicare con il dito quale bit è sbagliato. Questo capitolo è la storia di come si fabbrica quella ridondanza, e di come la stessa idea torni — come analogia — nel voto di maggioranza con cui un modello linguistico ragiona.

Perché questo capitolo

Una pagina prima, in Canali, rumore, capacità, abbiamo visto il teorema di codifica di canale di Claude Shannon (1916-2001, matematico americano dei Bell Telephone Laboratories): sotto la capacità $C$ di un canale rumoroso esistono codici che permettono di comunicare con probabilità d’errore arbitrariamente piccola. Ma quel teorema ha una caratteristica spiazzante: è non costruttivo. Dimostra che i codici buoni esistono senza esibirne uno. Per quasi mezzo secolo si è saputo quanto ci si potesse avvicinare a $C$ , senza saper come.

Questo capitolo entra in quel “come”. È la disciplina dei codici a correzione d’errore (error-correcting codes, ECC): l’arte di aggiungere a un messaggio una ridondanza strutturata — non bit a caso, ma bit calcolati secondo regole note — in modo che il ricevitore possa rilevare, e a volte ricostruire, ciò che il rumore ha corrotto.

Dove il capitolo precedente fissava il limite teorico, qui si fabbricano gli strumenti che lo avvicinano. È il passaggio dalla promessa (“i codici buoni esistono”) all’ingegneria (“ecco come se ne costruisce uno”).

Il problema è ovunque, anche dove non lo si vede. Un raggio cosmico capovolge un bit nella RAM di un server. Un graffio cancella qualche centesimo di millimetro di un CD. Un pacchetto attraversa una rete e arriva con qualche bit sbagliato. Una sonda a miliardi di chilometri trasmette immagini sepolte sotto il rumore termico, senza alcuna possibilità di farsele rispedire.

In tutti questi casi qualcuno, in qualche strato del sistema, ha aggiunto ridondanza in anticipo, perché il dato giusto si possa ricostruire dopo. Senza codici a correzione d’errore, gran parte dell’infrastruttura digitale semplicemente non funzionerebbe: i dischi perderebbero dati al primo difetto, le reti consegnerebbero file corrotti senza accorgersene, lo storage di lungo periodo si degraderebbe in modo silenzioso. È un’infrastruttura invisibile proprio perché funziona, e la si nota solo quando manca.

C’è poi un motivo che va oltre le telecomunicazioni, e che chiude il capitolo: la ridondanza come principio generale di robustezza. L’idea di proteggere un’informazione facendone più copie strutturate, e poi decidere a maggioranza, riappare — come analogia, non come teorema — nel modo in cui un modello linguistico può ragionare più affidabilmente generando molte risposte e tenendo la più frequente.

Capire bene il caso pulito dei bit, dove tutto è dimostrabile e le ipotesi sono esplicite, dà una lente onesta per giudicare dove quella lente smette di valere. È un esercizio di disciplina intellettuale tanto quanto di teoria dei codici: riconoscere quando una somiglianza insegna e quando inganna.

Contesto

Il capitolo si colloca dentro la Parte XIII subito dopo i due capitoli che lo rendono leggibile: Informazione come riduzione di incertezza, che misura quanta informazione c’è in un messaggio, e Canali, rumore, capacità, che fissa quanto se ne può far passare attraverso un mezzo rumoroso e con quale affidabilità. Da lì ereditiamo due idee senza ridimostrarle: che il canale è una regola probabilistica $p(y \mid x)$ , e che la ridondanza è l’esatto opposto della compressione — la compressione toglie il prevedibile per accorciare, la codifica di canale aggiunge il prevedibile per proteggere.

Cosa c’era prima è istruttivo. Fino agli anni ‘40, di fronte a una linea che sbagliava, l’ingegnere aveva due risposte: migliorare fisicamente il mezzo (più potenza, ripetitori migliori) oppure ripetere il messaggio finché non arrivava pulito.

La ripetizione cruda — manda tre volte, scegli a maggioranza — era già nota, ma è enormemente costosa: triplica il traffico per correggere un solo errore. Mancava l’idea che si potesse disporre la ridondanza in modo intelligente, ottenendo molta più protezione per ogni bit speso. È esattamente il salto che Hamming compie.

Quell’idea ha una data e un nome. Nel 1947 Richard Hamming (1915-1998, matematico americano dei Bell Labs) lavorava con i Model 5 Relay Computer, calcolatori a relè che giravano nei weekend senza supervisione. Con un paio di guasti di relè al giorno, un errore nei calcoli del venerdì sera bloccava la macchina, e il lunedì Hamming trovava il lavoro non fatto.

La macchina sapeva rilevare l’errore — aveva controlli di parità che la facevano fermare — ma non sapeva andare oltre. La frustrazione, nelle parole attribuite a Hamming, era diretta: se la macchina sa che c’è un errore, perché non sa anche dov’è e correggerlo? Da quella domanda nasce Error Detecting and Error Correcting Codes (Bell System Technical Journal, vol. 29, aprile 1950), il primo codice capace non solo di accorgersi dell’errore ma di localizzarlo e correggerlo.

Il filo non si ferma a Hamming. I codici di Reed-Solomon (1960) portano la correzione su simboli interi e finiscono dentro ogni CD e ogni QR code; l’algoritmo di Viterbi (1967) dà la decodifica ottima ai codici convoluzionali; i codici LDPC e turbo, già raccontati nel capitolo precedente, chiudono la corsa toccando il limite di Shannon. Questo capitolo ripercorre la parte costruttiva di quella storia, fermandosi dove il dettaglio algebrico richiederebbe strumenti che il lettore target non ha — l’algebra dei campi finiti — e tenendo invece l’intuizione operativa.

L’intuizione

Due modi di guardare la stessa idea prima di scrivere una sola formula: la ridondanza come regola che un errore viola, e la decodifica come ricerca della codeword più vicina.

Angolo 1: la ridondanza è una regola che l’errore tradisce

Immagina di voler proteggere un messaggio da errori che capovolgono bit a caso. La mossa più semplice: imporre una regola che il messaggio valido deve rispettare, scelta in modo che un errore la rompa.

L’esempio minimo è il bit di parità. Prendi i bit del messaggio e aggiungine uno scelto in modo che il numero totale di 1 sia pari. Se il messaggio è 1011 (tre 1, dispari), aggiungi un 1 e mandi 10111 (quattro 1, pari). La regola è: “le parole valide hanno un numero pari di uni”.

Ora, se il canale capovolge un bit qualsiasi durante il viaggio, il numero di uni diventa dispari, la regola è violata, e il ricevitore sa che qualcosa è andato storto. Il bit aggiunto non porta nuova informazione: porta un controllo su quella che c’è già.

Questa è la prima idea-chiave: la ridondanza non è informazione in più, è un vincolo in più. Le parole che rispettano il vincolo sono “valide”; tutte le altre sono “impossibili” se non fosse per il rumore. Quando il ricevitore vede una parola impossibile, ha rilevato un errore. Più vincoli imponi, più errori puoi catturare — al prezzo di mandare più bit.

Il bit di parità però mostra subito i suoi limiti, ed è istruttivo guardarli. Rileva ogni errore singolo, perché un flip rende dispari il conto degli uni. Ma è cieco a un numero pari di errori: due flip si compensano, il conto resta pari, la regola sembra rispettata.

E soprattutto: sa che c’è stato un errore, non dove. Può segnalare e basta. Per correggere — per sapere quale bit raddrizzare — serve di più, e quel “di più” è il salto che porta ai codici di Hamming.

Angolo 2: decodificare è cercare la codeword più vicina

Il secondo angolo è geometrico, e raccoglie l’intuizione delle “sfere lontane” già incontrata nel capitolo sui canali. Pensa a ogni possibile parola di $n$ bit come a un punto in uno spazio. La “distanza” tra due punti è il numero di bit in cui differiscono — la distanza di Hamming, dal nome di chi la introdusse. Capovolgere un bit significa spostarsi di un passo in questo spazio: da 10111 a 10110 c’è distanza 1.

Un codice sceglie un sottoinsieme di questi punti — le codeword valide — e lascia tutti gli altri “vuoti”. Quando una codeword attraversa il canale, il rumore la sposta di qualche passo. Decodificare significa, dato il punto ricevuto (probabilmente non una codeword valida), indovinare da quale codeword era partito: la risposta naturale è “la codeword valida più vicina”.

Questo funziona finché le codeword valide sono tenute lontane tra loro. Se due codeword distano almeno 3 passi, un singolo flip — un passo — produce un punto che resta più vicino alla codeword di partenza che a qualunque altra: lo si decodifica correttamente.

Se invece due codeword distassero solo 1 passo, un singolo flip potrebbe portare esattamente sull’altra, e l’errore diventerebbe invisibile e incorreggibile. La lontananza tra codeword non è un dettaglio estetico: è precisamente ciò che il rumore deve attraversare per ingannare il decodificatore.

Tutta la teoria che segue è questa intuizione resa precisa. La potenza di un codice — quanti errori rileva, quanti ne corregge — dipende da una sola quantità: quanto sono lontane, al minimo, le sue codeword. Costruire un buon codice significa impacchettare tante codeword nello spazio tenendole il più distanti possibile. La parità, Hamming, Reed-Solomon sono ricette diverse per fare esattamente questo, con efficienza crescente.

Angolo 3: rilevare e correggere sono due livelli di lontananza

Lo stesso quadro geometrico chiarisce, prima ancora delle formule, perché correggere costi più che rilevare. Sono due richieste diverse sulle distanze tra codeword.

Per rilevare un errore basta che la parola corrotta non coincida con un’altra codeword valida. Se le codeword distano almeno 2, qualunque flip singolo produce un punto “vuoto”, che non è una codeword: il ricevitore sa che è successo qualcosa, anche se non sa cosa fosse l’originale. La rilevazione chiede solo che il rumore non trasformi una codeword valida in un’altra codeword valida.

Per correggere la richiesta è più forte: la parola corrotta deve restare inequivocabilmente più vicina alla codeword di partenza che a ogni altra. Non basta che il punto sia vuoto; deve cadere nel territorio di un solo centro.

Questo richiede che le codeword siano abbastanza distanti da lasciare, attorno a ciascuna, un margine che nessun altro centro invade — e per un dato numero di errori serve circa il doppio della distanza che basta a rilevarli. Da qui il fattore due tra le due regole che vedremo tra poco.

È la stessa differenza, in termini umani, tra accorgersi che una parola scritta a mano è illeggibile (facile: non assomiglia a nessuna parola) e indovinare con certezza quale parola fosse (difficile: deve assomigliare a una sola).

La rilevazione segnala l’anomalia; la correzione la risolve. Tutto il resto del capitolo è il prezzo, in bit, di questi due livelli — e la ricerca di codici che paghino il meno possibile per il livello che serve.

La meccanica

Ora i numeri e le regole. Restiamo sull’intuizione operativa, lasciando il formalismo algebrico dei campi finiti fuori dalla portata di questo capitolo.

Distanza minima: il numero che governa tutto

La distanza di Hamming tra due parole della stessa lunghezza è il numero di posizioni in cui differiscono. Tra 10111 e 10001 la distanza è 2 (cambiano il terzo e il quarto bit). È una misura di “quanti flip servono per trasformare una parola nell’altra”.

La distanza minima $d_{\min}$ di un codice è la più piccola distanza di Hamming tra due qualsiasi delle sue codeword valide. È il singolo numero che riassume la robustezza del codice, e governa due capacità distinte secondo due regole pulite:

\text{errori rilevabili} = d_{\min} - 1, \qquad \text{errori correggibili} = \left\lfloor \frac{d_{\min} - 1}{2} \right\rfloor.

In parole povere, la prima regola dice: se le codeword distano almeno $d_{\min}$ , allora servono almeno $d_{\min}$ flip per trasformare una codeword valida in un’altra codeword valida. Qualsiasi numero di errori inferiore — fino a $d_{\min}-1$ — produce una parola “impossibile”, che il ricevitore riconosce come corrotta.

La seconda regola dice: per correggere non basta accorgersi, bisogna che la parola ricevuta resti inequivocabilmente più vicina alla codeword di partenza che a ogni altra. Questo è garantito solo se gli errori sono al più la metà della distanza minima, arrotondata per difetto: oltre quella soglia, la parola corrotta potrebbe avvicinarsi più a una codeword sbagliata che a quella giusta.

Il fattore due tra rilevazione e correzione è il cuore di tutto. Rilevare costa poco: basta che l’errore butti fuori dall’insieme delle codeword valide. Correggere costa il doppio: bisogna sapere verso quale codeword tornare, e questo richiede che nessun’altra codeword sia altrettanto vicina. È la differenza, in termini geometrici, tra “questo punto non è un centro” (facile) e “questo punto appartiene senza ambiguità al territorio di un centro preciso” (più esigente).

Si verifica subito sui due codici già incontrati. Il bit di parità ha $d_{\min} = 2$ : due codeword valide differiscono almeno in due posizioni, perché cambiare un bit di dati costringe a cambiare anche la parità. Quindi rileva $2-1 = 1$ errore e corregge $\lfloor 1/2 \rfloor = 0$ errori — esattamente ciò che avevamo osservato: rileva ma non corregge.

Il codice a ripetizione 000/111 ha invece $d_{\min} = 3$ : le due uniche codeword differiscono in tutte e tre le posizioni. Rileva $3-1 = 2$ errori e corregge $\lfloor 2/2 \rfloor = 1$ errore, il che giustifica la decodifica a maggioranza — un flip su tre si corregge tornando alla maggioranza, perché la parola corrotta resta più vicina alla codeword giusta.

Il code rate: la moneta con cui si paga la protezione

Tutta questa protezione ha un prezzo, e il prezzo ha un nome. Se un codice trasforma $k$ bit di messaggio in $n$ bit di codeword (con $n > k$ , perché i $n-k$ bit in più sono ridondanza), il suo code rate è

R = \frac{k}{n}.

In parole povere: la frazione dei bit trasmessi che porta informazione vera. Un rate vicino a 1 significa poca ridondanza, alto throughput, poca protezione; un rate basso significa molta ridondanza, throughput basso, molta protezione. Il codice a ripetizione tripla ha $R = 1/3$ : tre bit di canale per ogni bit di informazione. Il codice di Hamming (7,4), che vedremo, ha $R = 4/7 \approx 0{,}57$ : protezione paragonabile (corregge un errore) a un terzo del costo. La differenza tra $1/3$ e $4/7$ è esattamente la differenza tra ridondanza stupida e ridondanza intelligente.

Questo rate è lo stesso oggetto del teorema di canale del capitolo precedente: avvicinarsi alla capacità $C$ significa spingere $R$ il più in alto possibile a parità di affidabilità. Il codice a ripetizione e il codice di Hamming sono due punti molto lontani da $C$ ; i codici LDPC e turbo lo sfiorano.

Ma la moneta è sempre questa: protezione contro rate. Ogni bit di ridondanza speso è un bit di dati non trasmesso, e l’arte della codifica è ottenere il massimo di protezione per il minimo di rate sacrificato.

La tabella seguente mette a confronto i codici elementari di questo capitolo sulle quattro grandezze che contano — quanti bit di dati, quanti bit totali, la distanza minima, il rate — e mostra in piccolo il salto dalla ridondanza bruta a quella intelligente.

Codice	$k$ (dati)	$n$ (totali)	$d_{\min}$	rate $R$	corregge / rileva
Bit di parità	4	5	2	$4/5 = 0{,}8$	0 / 1
Ripetizione 3x	1	3	3	$1/3 \approx 0{,}33$	1 / 2
Ripetizione 5x	1	5	5	$1/5 = 0{,}2$	2 / 4
Hamming (7,4)	4	7	3	$4/7 \approx 0{,}57$	1 / 2
Hamming esteso (8,4)	4	8	4	$4/8 = 0{,}5$	1 / 2 (con segnalazione del doppio)

Il confronto da cui imparare è tra ripetizione 3x e Hamming (7,4): entrambi correggono un solo errore, ma il primo lo fa a rate $0{,}33$ e il secondo a rate $0{,}57$ , quasi il doppio dell’efficienza. Stessa protezione, metà dello spreco: è precisamente questo il guadagno della ridondanza disposta con intelligenza.

Codici di Hamming: localizzare l’errore con la sindrome

Il salto di Hamming è passare dalla sola rilevazione (un bit di parità) alla correzione (sapere dove). L’idea: invece di un solo bit di parità che controlla tutto, usare più bit di parità, ciascuno dei quali controlla un sottoinsieme diverso e accuratamente scelto dei bit di dati. La combinazione dei controlli che falliscono indica la posizione dell’errore.

Il codice di Hamming (7,4) protegge 4 bit di dati con 3 bit di parità, per una codeword di 7 bit ( $R = 4/7$ ). I tre bit di parità sono disposti in modo che ogni posizione tra 1 e 7 sia “coperta” da una combinazione unica di controlli. Quando arriva la parola, il ricevitore ricalcola i tre controlli di parità e li confronta con quelli ricevuti: il risultato è un numero di 3 bit chiamato sindrome.

Vale la pena vedere la costruzione da vicino, perché spiega perché la sindrome funzioni invece di limitarsi a constatarlo. Le sette posizioni si numerano da 1 a 7. Le posizioni che sono potenze di due — 1, 2, 4 — ospitano i bit di parità ( $p_1$ , $p_2$ , $p_4$ ); le restanti — 3, 5, 6, 7 — ospitano i quattro bit di dati.

La regola che lega ciascun bit di parità ai dati nasce dalla scrittura binaria delle posizioni:

$p_1$ (posizione 1, binario 001) controlla tutte le posizioni il cui numero ha l’ultimo bit a uno: 3 (011), 5 (101), 7 (111).
$p_2$ (posizione 2, binario 010) controlla le posizioni con il bit centrale a uno: 3 (011), 6 (110), 7 (111).
$p_4$ (posizione 4, binario 100) controlla le posizioni con il bit alto a uno: 5 (101), 6 (110), 7 (111).

Ogni bit di parità si sceglie in modo che la somma (XOR) delle posizioni che controlla, lui incluso, sia zero. Concretamente, con dati $d = 1011$ piazzati nelle posizioni 3, 5, 6, 7, si calcola $p_1 = d_3 \oplus d_5 \oplus d_7$ , $p_2 = d_3 \oplus d_6 \oplus d_7$ , $p_4 = d_5 \oplus d_6 \oplus d_7$ , dove $\oplus$ è lo XOR. La codeword completa di 7 bit nasce intrecciando parità e dati in questo schema posizionale.

Il punto cruciale, da cui discende tutto: ogni posizione di dati è controllata da una combinazione distinta di bit di parità, e quella combinazione è esattamente la scrittura binaria della posizione. È questo intreccio progettato che fa puntare la sindrome al bit giusto.

Qui sta l’eleganza. La sindrome, letta come numero binario, è la posizione del bit sbagliato:

Sindrome 000: nessun controllo fallisce, nessun errore (o un errore non rilevabile, fuori portata).
Sindrome 101: cioè 5 in binario. L’errore è nel bit in posizione 5. Capovolgilo e hai corretto.

Non c’è ricerca, non c’è confronto con tutte le codeword: la sindrome punta direttamente al colpevole. Il motivo, in una riga e senza l’algebra completa: i controlli sono costruiti in modo che ogni posizione produca, quando è quella sbagliata, una sindrome uguale alla sua rappresentazione binaria. È un indirizzamento, non una caccia.

Perché funzioni così: ricorda che $p_1$ controlla le posizioni dispari (1, 3, 5, 7), $p_2$ le posizioni 2, 3, 6, 7, e $p_4$ le posizioni 4, 5, 6, 7. Se l’errore è in posizione 5, falliscono esattamente i controlli che includono la posizione 5 — cioè $p_1$ e $p_4$ , non $p_2$ . Scrivendo il fallimento di $p_4 p_2 p_1$ come bit si ottiene 101, cioè 5. La sindrome non è altro che l’elenco dei controlli falliti, e quell’elenco coincide con la scrittura binaria della posizione proprio perché ogni posizione è stata assegnata ai controlli secondo i suoi bit. È un sistema di coordinate camuffato da parità.

# Hamming (7,4): la sindrome localizza il bit errato.
# Posizioni 1..7; le posizioni potenza di 2 (1,2,4) portano la parità.
def sindrome(parola):  # parola: lista di 7 bit, indice 0 = posizione 1
    s = 0
    for pos in range(1, 8):          # XOR delle posizioni con bit = 1
        if parola[pos - 1] == 1:
            s ^= pos
    return s                          # 0 = ok; altrimenti = posizione errata

cw = [1, 0, 1, 0, 0, 1, 0]            # una codeword valida (sindrome attesa 0)
print(sindrome(cw))                   # -> 0

cw[4] = 1 - cw[4]                     # il canale capovolge il bit in posizione 5
s = sindrome(cw)
print(s)                              # -> 5: errore nella posizione 5
cw[s - 1] = 1 - cw[s - 1]             # correzione: capovolgi quel bit
print(sindrome(cw))                   # -> 0: corretto

Il codice (7,4) ha $d_{\min} = 3$ : corregge un errore singolo, rileva due. Una variante molto usata aggiunge un ulteriore bit di parità globale, ottenendo il codice esteso (8,4) con $d_{\min} = 4$ : corregge un errore e ne rileva due distintamente (in gergo SEC-DED, single error correct, double error detect). È esattamente lo schema della ECC RAM dei server, la memoria che corregge al volo i bit capovolti dai raggi cosmici e segnala quando il danno è troppo grande per essere corretto.

Codici a blocchi lineari: la struttura dietro Hamming

I codici di Hamming sono un caso di codici a blocchi lineari, la famiglia su cui si regge gran parte della teoria. “A blocchi” perché operano su blocchi di lunghezza fissa; “lineari” perché ogni codeword è una combinazione lineare (in aritmetica modulo 2, dove la somma è lo XOR) dei bit di dati.

Due matrici riassumono un codice lineare. La matrice generatrice $G$ trasforma il messaggio in codeword: moltiplicando i $k$ bit di dati per $G$ si ottengono gli $n$ bit della codeword, ridondanza inclusa. La matrice di controllo di parità $H$ fa il lavoro inverso al ricevitore: è costruita in modo che ogni codeword valida $x$ soddisfi $H \cdot x^{\mathsf T} = 0$ .

La sindrome è esattamente $s = H \cdot y^{\mathsf T}$ calcolata sulla parola ricevuta $y$ : vale zero se e solo se $y$ è una codeword valida, e quando non lo è, identifica il pattern d’errore. La sindrome di Hamming che “punta alla posizione” è questo prodotto $H \cdot y^{\mathsf T}$ con $H$ costruita ad arte.

Il dettaglio di come si costruiscono $G$ e $H$ è materia di algebra lineare; qui basta sapere che la coppia esiste e che ogni codice a blocchi lineare — Hamming, BCH, Reed-Solomon — vive dentro questo schema. È il linguaggio comune che permette di trattare codici diversissimi con la stessa matematica.

CRC e checksum: rilevare ovunque, a basso costo

Spesso non serve correggere, basta rilevare: se un dato è corrotto, lo scarto e lo richiedo, oppure segnalo il guasto. Per la sola rilevazione lo strumento dominante in reti e storage è il checksum, e nella sua forma più potente il cyclic redundancy check (CRC).

Un checksum ingenuo somma tutte le parole del messaggio e trasmette la somma; il ricevitore ricalcola e confronta. Funziona, ma è debole su pattern strutturati — due errori che si compensano nella somma passano inosservati. Il CRC è più furbo. Tratta l’intero messaggio come un grande numero binario (un polinomio, nel linguaggio tecnico) e lo divide per un divisore fisso e concordato, il polinomio generatore. Il resto di questa divisione è il CRC, una manciata di bit appesa al messaggio. Al ricevitore si ridivide tutto — dati più CRC — per lo stesso divisore: se il resto è zero, nessun errore rilevato; se è diverso da zero, errore.

La “divisione” qui non è quella aritmetica usuale: è una divisione modulo 2, dove ogni sottrazione è uno XOR e non ci sono riporti. In concreto, con un messaggio 1101 e un polinomio generatore 1011 (4 bit, quindi CRC di 3 bit), si appendono al messaggio tre zeri — 1101000 — e si divide ripetutamente facendo lo XOR del generatore allineato al bit più significativo ancora a uno, finché non resta un numero più corto del generatore. Quel resto, 3 bit, è il CRC: lo si sostituisce ai tre zeri e si trasmette 1101 seguito dal CRC. Il ricevitore divide l’intera parola ricevuta per 1011: resto zero significa nessun errore rilevato. Il meccanismo è elementare — solo XOR e scorrimenti, realizzabile in hardware con pochi gate — ed è una delle ragioni della sua diffusione: costa pochissimo da calcolare a velocità di linea.

La proprietà che rende il CRC onnipresente è la sua forza sui burst error: sequenze contigue di bit sbagliati, il tipo di danno tipico di un graffio su disco o di un disturbo elettrico su un cavo. Un CRC a $n$ bit rileva ogni burst di lunghezza fino a $n$ bit, e una frazione $\bigl(1 - 2^{-n}\bigr)$ — vicinissima a 1 per $n$ ragionevole — di tutti i burst più lunghi.

È il motivo per cui CRC-32 (32 bit) è dentro Ethernet, USB, ZIP, PNG, e in pratica ogni protocollo che muove dati. La scelta del polinomio generatore non è arbitraria: i polinomi usati negli standard sono stati selezionati con cura per massimizzare proprio la copertura dei pattern d’errore più probabili sul mezzo.

Vale la pena notare cosa fa il CRC al modello del canale, riprendendo il linguaggio del capitolo precedente. Un errore non rilevato è un errore silenzioso: il dato sbagliato viene consegnato come se fosse buono, il caso peggiore del canale binario simmetrico.

Il CRC trasforma quell’errore silenzioso in una cancellazione dichiarata: il dato corrotto viene scartato, e gli strati superiori vedono “pacchetto mancante” invece di “pacchetto sbagliato di nascosto”. È il passaggio da un canale tipo BSC a un canale tipo BEC, e nel capitolo precedente abbiamo visto perché conviene tanto: sapere dove è il danno costa molto meno che subirlo in silenzio.

I codici che usi ogni giorno

Tre famiglie di codici, oltre a Hamming, coprono quasi tutto ciò che incontri nella pratica, e ciascuna risolve un pezzo diverso del problema.

I codici di Reed-Solomon (Irving Reed e Gustave Solomon, Polynomial Codes over Certain Finite Fields, Journal of the SIAM, vol. 8, 1960) operano non su singoli bit ma su simboli — tipicamente byte. È la loro forza segreta contro i burst: se un graffio rovina otto bit consecutivi che appartengono allo stesso byte, per Reed-Solomon è un errore di simbolo, non otto errori di bit.

Sono inoltre ottimali in un senso preciso (in gergo MDS, maximum distance separable): raggiungono la massima distanza minima possibile per dati $n$ e $k$ . È la ragione per cui stanno nel CD audio — un graffio che cancella centinaia di bit consecutivi corrisponde a pochi simboli persi, ricostruibili — e nei QR code, che restano leggibili anche quando il 30% circa del codice è danneggiato o coperto.

I codici convoluzionali abbandonano l’idea del blocco. Invece di codificare $k$ bit alla volta, fanno scorrere il flusso di dati attraverso un piccolo registro a scorrimento, e ogni bit di uscita dipende da una finestra di bit di ingresso recenti. La codeword non ha confini netti: è un flusso continuo intrecciato con la sua stessa storia.

La decodifica ottima di questi codici è l’algoritmo di Viterbi, che cerca, su un grafo a traliccio (trellis), il percorso di bit più probabile dato ciò che è arrivato. È esattamente lo stesso algoritmo di programmazione dinamica che Viterbi e decodifica su HMM descrive per i modelli di Markov nascosti: Andrew Viterbi lo introdusse nel 1967 proprio per i codici convoluzionali, e solo in seguito venne applicato agli HMM. Non è un’analogia tra due algoritmi simili: è la stessa macchina di decodifica a massima verosimiglianza su trellis, usata in due domini.

I codici LDPC e turbo, già raccontati nel capitolo precedente, sono il punto di arrivo: ridondanza così ben disposta, e decodifica iterativa così efficace, da avvicinarsi a frazioni di decibel dal limite di Shannon. Sono dentro 4G, 5G, Wi-Fi, TV satellitare e SSD. Qui basti collocarli: dove Hamming è elegante ma lontano da $C$ , e Reed-Solomon è robusto sui burst, LDPC e turbo sono i codici che spremono il canale fino quasi al limite teorico.

Una mossa ricorrente nella pratica è concatenare codici diversi, perché ciascuno copre la debolezza dell’altro. Un codice convoluzionale interno, decodificato con Viterbi, ripulisce bene gli errori sparsi ma ogni tanto sbaglia in modo concentrato, producendo un piccolo burst; un codice di Reed-Solomon esterno, forte proprio sui burst, ripulisce quei residui. La combinazione corregge sia gli errori sparsi sia quelli a raffica meglio di quanto ciascun codice farebbe da solo. È lo schema con cui le sonde spaziali hanno trasmesso per decenni, ed è un esempio concreto di come la scelta del codice dipenda dal tipo di errore che il canale produce, non solo dalla loro quantità.

Dal weekend di Hamming alle sonde

Il filo storico della costruzione dei codici merita di essere ripercorso, perché lega la frustrazione di un matematico negli anni ‘40 alla voce delle sonde nello spazio profondo.

Il punto di partenza è il 1948 e il teorema di Shannon: i codici buoni esistono. Ma è una promessa senza istruzioni. Il primo a costruire qualcosa di concreto è Hamming nel 1950, spinto dai calcolatori a relè di Bell Labs che si fermavano nei weekend. Il suo codice corregge un errore singolo per blocco, ed è la prova che la correzione — non solo la rilevazione — è possibile con ridondanza modesta. Per oltre un decennio i codici di Hamming e le loro generalizzazioni (i codici BCH) sono lo stato dell’arte: eleganti, decodificabili in fretta, ma lontani dalla capacità di Shannon.

Il 1960 porta i codici di Reed-Solomon, e con essi un’idea diversa: lavorare su simboli invece che su bit, per dominare i burst. Per anni restano una curiosità teorica in cerca di un’applicazione. La trovano nello spazio e nell’elettronica di consumo.

Le sonde Voyager, lanciate nel 1977 verso i pianeti esterni, usano codici concatenati — Reed-Solomon esterno, convoluzionale interno — per inviare immagini di Giove e Saturno con una potenza di poche decine di watt, da distanze dove il segnale arriva sepolto sotto il rumore. Senza quei codici, le immagini sarebbero rumore indistinguibile.

Pochi anni dopo, nel 1982, il Compact Disc porta Reed-Solomon nelle case di tutti: lo schema CIRC è la ragione per cui un graffio non fa saltare la musica.

Il 1994 aggiunge un’applicazione che oggi è sotto gli occhi di chiunque inquadri uno schermo o un volantino: il QR code, sviluppato in Giappone da Denso Wave, incorpora Reed-Solomon con livelli di ridondanza selezionabili, così che il codice resti leggibile anche con un angolo strappato o un logo stampato sopra. Lo strappo è il rumore; la ridondanza, calcolata quando il codice è generato, è ciò che lo sconfigge.

La corsa al limite di Shannon — turbo code nel 1993, codici LDPC riscoperti a metà anni ‘90, polar code nel 2009 — è raccontata nel capitolo sui canali. Qui basti il filo: dal weekend perso di Hamming a una sonda che, decenni dopo il lancio, continua a farsi capire dall’altra parte del sistema solare, la storia dei codici è la storia di una promessa teorica del 1948 trasformata, pezzo dopo pezzo, in ingegneria che funziona.

Esempi

Cinque esempi eterogenei: uno numerico (parità e ripetizione su un canale che sbaglia), uno in codice che simula il canale e la decodifica a maggioranza, uno in codice sulla sindrome di Hamming che localizza l’errore, uno scenario reale (CD, ECC RAM, QR), e un ponte verso l’AI marcato esplicitamente come analogia.

Esempio 1 (numerico): parità contro ripetizione su un canale rumoroso

Riprendi il canale binario simmetrico (BSC) del capitolo precedente, che capovolge ogni bit con probabilità $p = 0{,}1$ . Vuoi proteggere un singolo bit di informazione. Confrontiamo tre strategie.

Bit nudo. Mandi il bit così com’è. Probabilità di errore: $0{,}1$ . Dieci messaggi su cento arrivano sbagliati, e non lo sai.

Bit di parità (rilevazione). Aggiungi un bit di parità: mandi 2 bit. La regola “numero pari di uni” rileva un flip singolo. Ma con $d_{\min} = 2$ non corregge: se rilevi l’errore, puoi solo scartare e richiedere.

La probabilità che almeno un flip avvenga e venga rilevato è alta, ma resta il buco dei due flip simultanei ( $0{,}1 \times 0{,}1 = 0{,}01$ ) che passano inosservati. La parità riduce gli errori silenziosi, non li azzera.

Ripetizione tripla (correzione). Mandi 000 o 111, 3 bit, e decidi a maggioranza. Con $d_{\min} = 3$ correggi un flip. Sbagli solo se il rumore capovolge almeno due dei tre bit.

La probabilità è quella di due flip esatti, $3 \times 0{,}1^2 \times 0{,}9 = 0{,}027$ , più quella di tre flip, $0{,}1^3 = 0{,}001$ , in totale $0{,}028$ . L’errore scende da $0{,}1$ a meno del 3% — ma il code rate crolla a $1/3$ , il prezzo di questa correzione rozza.

La lezione è il contrasto. La parità costa un bit e dà solo rilevazione. La ripetizione costa due bit e dà correzione, ma a un rate misero. Un codice di Hamming darebbe correzione a $R = 4/7$ , cioè quasi il doppio dell’efficienza della ripetizione: è il guadagno della ridondanza intelligente sulla ridondanza bruta.

Esempio 2 (in codice): simulare il canale e la decodifica a maggioranza

Il calcolo dell’esempio precedente si può verificare con una simulazione, che rende tangibile il salto dall’errore del bit nudo a quello del codice a ripetizione. Si codifica ogni bit triplicandolo, lo si passa attraverso un BSC che capovolge con probabilità $p$ , e si decodifica a maggioranza.

import random

def bsc(bit, p):                       # canale binario simmetrico
    return 1 - bit if random.random() < p else bit

def trasmetti_ripetizione(bit, p):
    ricevuti = [bsc(bit, p) for _ in range(3)]   # tre copie nel canale
    return 1 if sum(ricevuti) >= 2 else 0        # decodifica a maggioranza

random.seed(0)
p = 0.1
N = 200_000

# bit nudo: errore atteso ~ p
err_nudo = sum(bsc(0, p) != 0 for _ in range(N)) / N

# ripetizione 3x: errore atteso ~ 0.028
err_rip = sum(trasmetti_ripetizione(0, p) != 0 for _ in range(N)) / N

print(f"bit nudo:      {err_nudo:.3f}")   # ~ 0.100
print(f"ripetizione 3x:{err_rip:.3f}")    # ~ 0.028

La frequenza d’errore misurata si assesta intorno a $0{,}1$ per il bit nudo e a circa $0{,}028$ per la ripetizione tripla, esattamente i numeri calcolati a mano. La simulazione mostra anche, se la si modifica per contare i casi, che il codice sbaglia solo quando almeno due delle tre copie vengono capovolte: la decodifica a maggioranza è la realizzazione operativa della regola “torna alla codeword più vicina” su un codice con $d_{\min} = 3$ .

Esempio 3 (in codice): la sindrome che punta al bit sbagliato

L’esempio in codice è il frammento Python già visto nella sezione sulla meccanica: il calcolo della sindrome di Hamming (7,4). Vale la pena rileggerlo con l’occhio dell’esempio, perché mostra in poche righe la differenza tra rilevare e localizzare. Quando il canale capovolge il bit in posizione 5, la funzione sindrome non restituisce un generico “errore”, ma il numero 5: la posizione esatta. La correzione è allora una sola riga — capovolgi quel bit — e la sindrome ricalcolata torna a zero.

Il punto didattico è che non c’è nessuna ricerca: nessun confronto del messaggio ricevuto con le 16 codeword valide, nessun tentativo. La sindrome è l’indirizzo del colpevole, per costruzione. È questo che separa Hamming dalla pura rilevazione: lo stesso costo di calcolo del controllo di parità, ma con in più l’informazione su dove guardare.

Esempio 4 (scenario reale): il graffio sul CD, il raggio cosmico nella RAM, l’angolo strappato del QR

Tre scene quotidiane, tutte rette dallo stesso principio costruttivo. Il capitolo sui canali le ha già evocate dal lato della capacità; qui le guardiamo dal lato della costruzione.

Un CD graffiato continua a suonare pulito perché incorpora codici di Reed-Solomon (nello schema chiamato CIRC). Il graffio cancella un burst di bit consecutivi; ma quei bit, sparpagliati su simboli diversi grazie a un interleaving deliberato, diventano pochi errori di simbolo isolati, che Reed-Solomon ricostruisce.

La musica non salta perché il decodificatore, in tempo reale, riempie i buchi con i dati ricostruiti dalla ridondanza. L’interleaving è una mossa fine: distribuisce deliberatamente i bit vicini su simboli lontani, così che un danno concentrato nello spazio fisico diventi un danno sparso nello spazio dei simboli, dove il codice lo gestisce meglio.

La ECC RAM di un server corregge silenziosamente i bit che un raggio cosmico o un disturbo elettrico capovolgono. Usa un codice di Hamming esteso (SEC-DED): ogni parola di memoria porta bit di parità sufficienti a correggere un bit capovolto al volo e a rilevare (segnalando, senza correggere) un doppio errore.

È la sindrome di Hamming applicata milioni di volte al secondo, invisibile finché tutto va bene. Nei data center, dove la quantità di memoria è enorme e i bit capovolti sono statisticamente inevitabili, è la differenza tra un sistema che corregge da solo e uno che accumula corruzione silenziosa.

Un QR code con un angolo strappato si legge ancora perché Reed-Solomon protegge i dati fino a poter ricostruire una frazione consistente del codice mancante. Lo strappo è il rumore; la ridondanza, calcolata in anticipo quando il codice è stato generato, è ciò che permette allo scanner di recuperare il messaggio.

È la stessa idea della ripetizione, in forma enormemente più efficiente: dove la ripetizione triplicherebbe ogni bit, Reed-Solomon spende solo la ridondanza necessaria per il livello di danno che si vuole tollerare, scelto quando si genera il codice.

Esempio 5 (ponte AI, analogia): self-consistency come ripetizione + voto di maggioranza

L’ultimo esempio è dichiaratamente un’analogia, non un calcolo, e va marcata come tale con cura — perché è esattamente il tipo di salto concettuale che, se trattato come equivalenza, inganna.

Quando un modello linguistico risolve un problema di ragionamento, una tecnica efficace è la self-consistency, introdotta in Self-Consistency Improves Chain of Thought Reasoning in Language Models (Xuezhi Wang, Jason Wei e colleghi di Google; arXiv 2022, presentato a ICLR 2023). Invece di prendere l’unica catena di ragionamento prodotta dalla decodifica greedy, si campionano molte catene di ragionamento diverse (con sampling stocastico) e si tiene la risposta finale che compare più spesso: un voto di maggioranza.

I guadagni misurati sono consistenti — per esempio +17,9 punti percentuali sul benchmark di problemi matematici GSM8K, e miglioramenti analoghi su una gamma di compiti di ragionamento aritmetico e di senso comune. La tecnica è semplice da applicare e non richiede addestramento aggiuntivo: solo più campioni a tempo di inferenza.

L’analogia col codice a ripetizione è immediata e illuminante. Generare $N$ risposte e prendere la maggioranza somiglia a mandare un bit $N$ volte e decidere a maggioranza. La “ridondanza” è il calcolo ripetuto; il “rumore” è la variabilità stocastica del sampling.

Il voto di maggioranza filtra gli errori, come la maggioranza su 000/111 corregge un flip singolo. Visto così, self-consistency è una decodifica robusta applicata al ragionamento, dove il code rate analogo è ” $N$ campioni per una risposta”.

Ma l’analogia ha un punto di rottura preciso, ed è il più istruttivo del capitolo. Il codice a ripetizione funziona perché assume che gli errori siano indipendenti: ogni flip avviene per conto suo, quindi è improbabile che la maggioranza dei bit sbagli nello stesso modo. Gli errori di un modello linguistico non sono indipendenti.

Se il modello ha un misconcetto sistematico — fraintende sempre un certo tipo di problema allo stesso modo — quel misconcetto si presenta nella maggioranza delle catene campionate, e il voto di maggioranza lo amplifica invece di correggerlo. La maggioranza corregge il rumore casuale; di fronte a un errore sistematico, vota compatta per la risposta sbagliata. Questa è la differenza tra un’analogia che insegna e un’equivalenza che mentirebbe: il meccanismo somiglia, l’ipotesi cruciale (indipendenza) no.

L’intuizione su cui poggia self-consistency, esplicitata nel paper, illumina anche perché funziona quando funziona: un problema di ragionamento complesso ammette molti percorsi diversi che convergono sulla stessa risposta corretta, mentre i percorsi sbagliati tendono a sbagliare in modi diversi tra loro e quindi a disperdersi. Quando questa condizione vale, la risposta giusta è quella concentrata e il voto la trova; è una versione probabilistica della stessa idea geometrica della decodifica — la risposta giusta come “centro” attorno a cui i campioni si addensano. Quando invece il modello è confidentemente e sistematicamente in errore, la condizione si rovescia e il voto consolida l’errore. L’analogia col codice non solo somiglia: indica anche, onestamente, dove smette di valere.

Applicazioni pratiche

I codici a correzione d’errore sono l’infrastruttura invisibile di quasi ogni bit che viaggia o riposa. Storage e telecomunicazioni li danno per scontati: ECC RAM nei server, Reed-Solomon nei dischi ottici e nei codici a barre bidimensionali, LDPC negli SSD e nel Wi-Fi recente, turbo code e LDPC nelle reti mobili, codici concatenati nelle comunicazioni con lo spazio profondo. Ogni volta che un download arriva integro su una rete imperfetta, o un disco restituisce dati scritti anni fa, qualche codice ha lavorato sotto il cofano.

Oltre l’ingegneria delle comunicazioni, il principio della ridondanza strutturata per la robustezza riappare in domini che questa wiki tratta altrove, e i legami vanno marcati con cura nella loro classe.

Nei sistemi di controllo e nella fusione di sensori, la ridondanza è la base della tolleranza ai guasti. Un sistema che legge la stessa grandezza da più sensori può rilevare e scartare un sensore impazzito facendo “votare” gli altri — la stessa logica della maggioranza, applicata a misure fisiche. È il legame, da intendere come richiamo concettuale e non come equivalenza formale, con Fondere misure imperfette da sensori diversi e con Robustezza a rumore, incertezza e disturbi: in entrambi la ridondanza (sensori in più, margini di controllo) è il prezzo pagato per resistere a disturbi e incertezza. La matematica specifica dei codici — distanza di Hamming, campi finiti — non si trasferisce; il principio “ridondanza disposta bene compra robustezza” sì.

La stessa logica del voto a maggioranza è il cuore della ridondanza nei sistemi critici: l’avionica e i sistemi di controllo industriale usano architetture con più calcolatori che eseguono lo stesso compito in parallelo e decidono per votazione (tipicamente due su tre), così che il guasto di una unità venga rilevato e scavalcato dalle altre. È, di nuovo, un codice a ripetizione applicato non a bit ma a interi computer, e ne eredita la stessa virtù e lo stesso limite: protegge dai guasti indipendenti, non da un difetto di progetto comune a tutte le unità (il guasto sistematico, che fa votare tutte allo stesso modo sbagliato). È la trama della difesa a strati che la safety engineering chiama defense in depth (in preparazione).

Negli agenti basati su modelli linguistici, due idee del capitolo si trasportano come analogie utili. La prima è la self-consistency dell’esempio precedente: il voto di maggioranza su risposte multiple come decodifica robusta, con il limite dell’indipendenza degli errori sempre da tenere presente.

La seconda riguarda la rilevazione: in un agent loop, un test che fallisce, un linter, un type-checker o la validazione di uno schema sono l’analogo del bit di parità — rilevano che qualcosa non torna, senza necessariamente saperlo correggere, e innescano un retry, l’analogo della ritrasmissione su un canale a cancellazione. Strutturare un agente attorno a controlli di consistenza espliciti è applicare l’idea che rilevare l’errore è il primo passo, economico, prima di tentare di correggerlo. Anche questa è analogia, non un codice formale: non c’è una distanza minima da calcolare, ma la disciplina di pensiero — separare rilevazione da correzione, sapere che la prima è più facile della seconda — si trasferisce intatta.

C’è infine un cenno da fare al watermarking dell’output generato. I metodi che inseriscono un segnale statisticamente rilevabile nella scelta dei token di un modello (per riconoscere a posteriori che un testo è stato generato da una macchina) sono imparentati, concettualmente, con l’idea di nascondere informazione ridondante e rilevabile dentro un messaggio. È solo un cenno: il tema ha un capitolo dedicato, watermarking-output (in preparazione).

Dove si rompe

I codici a correzione d’errore sono solidi e ben compresi. Ciò che si rompe è l’intuizione di chi li applica oltre le loro ipotesi, o ne confonde le garanzie. Questa sezione raccoglie i fraintendimenti che fanno più danni.

Rilevare non è correggere. È la confusione più comune. Un bit di parità, un checksum, un CRC rilevano che qualcosa non torna, ma non sanno ricostruire il dato giusto. Trattare un CRC come se proteggesse i dati — “ho il checksum, sono al sicuro” — è un errore: il checksum dice solo se scartare o no, non ripara.

Per riparare senza ritrasmissione serve un codice a correzione (FEC, forward error correction), che costa più ridondanza. La scelta tra rilevare-e-ritrasmettere e correggere-sul-posto è una decisione di sistema, non un dettaglio: la ritrasmissione costa un viaggio di andata e ritorno — inaccettabile per una sonda spaziale dove il ritardo è di ore — mentre la correzione costa ridondanza permanente su ogni messaggio, anche quando arriva intatto.

Il bit di parità è cieco agli errori pari. Due flip si compensano: il conto degli uni resta pari, la regola sembra rispettata, l’errore passa. Con $d_{\min} = 2$ un singolo bit di parità rileva solo un errore. Chi si fida di un bit di parità su un canale che produce errori a raffica si fida del nulla.

La sindrome localizza solo entro la capacità di correzione. La sindrome di Hamming “punta al bit sbagliato” finché l’errore è singolo. Se avvengono due flip su un codice che ne corregge uno, la sindrome punta comunque a una posizione — quella sbagliata. Il codice “corregge” verso la codeword più vicina, che però non è quella di partenza: il risultato è una miscorrection, un dato alterato presentato con sicurezza come corretto.

Oltre la capacità di correzione, quindi, un codice non si limita a fallire onestamente: può sbagliare in silenzio, peggiorando il dato invece di lasciarlo intatto. È il motivo per cui gli schemi critici aggiungono rilevazione oltre la correzione (SEC-DED): correggi un errore, ma se ne arrivano due almeno te ne accorgi invece di corrompere senza avvertire.

Più ridondanza non è sempre meglio. L’intuizione “se un po’ di ridondanza protegge, molta protegge di più” è falsa oltre un certo punto. Nei codici, aumentare la ridondanza fa crollare il rate senza un guadagno proporzionale di affidabilità una volta superata la soglia giusta per il rumore atteso.

Esiste un punto ottimale legato alla statistica del canale; oltre quello si paga throughput senza comprare protezione utile. La ridondanza è una medicina con un dosaggio, non un nutriente da somministrare a volontà — e lo stesso vale, come si vedrà, per il numero di campioni nel voto di maggioranza di un modello.

L’analogia self-consistency / codice a ripetizione assume indipendenza degli errori. Vale la pena ribadirlo qui perché è l’errore concettuale più pericoloso del capitolo. Il voto di maggioranza corregge gli errori casuali e indipendenti. Gli errori di un modello linguistico sono spesso correlati e sistematici: un misconcetto ricorrente appare nella maggioranza dei campioni, e il voto lo conferma invece di eliminarlo.

Generare più risposte e votare aiuta contro la variabilità stocastica, non contro un bias che il modello ha “imparato bene”. Chi assume che basti campionare di più per correggere qualsiasi errore proietta sulle reti neurali una proprietà — l’indipendenza — che vale per i bit di un canale ma non per i token di un ragionamento. È il salto da analogia a presunta equivalenza che la disciplina delle classi di affermazioni esiste proprio per impedire.

Più campioni hanno rendimenti decrescenti. Anche restando nel regime in cui il voto aiuta, raddoppiare il numero di campioni non dimezza l’errore indefinitamente: il guadagno si appiattisce, esattamente come allungare un codice a ripetizione da 3 a 5 a 7 ripetizioni dà miglioramenti sempre più piccoli a costo sempre crescente. C’è un punto oltre il quale generare un’altra risposta costa token e latenza senza spostare la maggioranza.

Reed-Solomon conta simboli, non bit. Confondere “errori di bit” ed “errori di simbolo” porta a stime sbagliate della robustezza. Un burst che corrompe otto bit dentro lo stesso byte è un errore di simbolo per Reed-Solomon, non otto. È la sua forza sui burst, ma vale solo se gli errori si concentrano nei simboli; errori sparsi su molti simboli diversi consumano la capacità di correzione molto più in fretta.

Un codice presuppone un modello del canale. La scelta di un codice — quanti errori correggere, quale rate — dipende da quanti e che tipo di errori il canale produce. Un codice progettato per errori sparsi e indipendenti fallisce su un canale a raffiche, e viceversa.

Applicare un codice senza un modello del canale che assomigli alla realtà significa proteggersi dal tipo di errore sbagliato: si spende ridondanza dove non serve e si resta scoperti dove serviva. Prima del codice viene sempre il modello del canale, ed è la parte difficile e poco appariscente dell’ingegneria delle comunicazioni.

La ridondanza protegge i dati, non la loro correttezza semantica. Un codice garantisce che i bit ricevuti siano i bit trasmessi, non che fossero i bit giusti. Se il messaggio era sbagliato alla sorgente, nessun codice a correzione lo aggiusta: trasmette fedelmente l’errore.

È un confine ovvio ma facile da dimenticare nel ponte verso l’AI: la verifica di consistenza di un agente può garantire che l’output rispetti uno schema, non che la risposta sia vera. Rilevazione e correzione operano sul canale, non sul significato — e confondere “il dato è arrivato integro” con “il dato è corretto” è un errore che attraversa intatto dai bit ai token.

Collegamenti

Canali, rumore, capacità: il capitolo precedente della Parte, che dimostra il teorema di codifica di canale in forma non costruttiva. Questo capitolo ne è il complemento costruttivo: come si fabbricano i codici che quel teorema promette.
Informazione come riduzione di incertezza: la ridondanza come opposto della compressione, e l’entropia come misura di quanta ridondanza un messaggio porta naturalmente.
Viterbi e decodifica su HMM: l’algoritmo di Viterbi nasce nel 1967 per decodificare i codici convoluzionali; è la stessa macchina di decodifica su trellis usata poi per i modelli di Markov nascosti.
Robustezza a rumore, incertezza e disturbi: la ridondanza come prezzo della robustezza, in chiave controllo. Richiamo concettuale, non equivalenza formale.
Fondere misure imperfette da sensori diversi: il voting tra sensori ridondanti per rilevare e scartare misure guaste, parente concettuale della decodifica a maggioranza.
self-consistency (in preparazione): il ponte AI centrale, il voto di maggioranza su catene di ragionamento campionate visto come decodifica robusta, con il limite dell’indipendenza degli errori.
compressione-mdl (in preparazione): l’altra faccia della ridondanza, dove toglierla fino all’osso diventa un criterio per scegliere tra modelli.
rate-distortion (in preparazione): la compressione lossy, dove si decide quanta perdita è accettabile, complementare alla protezione contro la perdita di questo capitolo.
watermarking-output (in preparazione): nascondere un segnale rilevabile nei token generati, concettualmente imparentato con la ridondanza rilevabile dei codici.

Per andare oltre

Hamming, R. W. (1950). Error Detecting and Error Correcting Codes, Bell System Technical Journal, vol. 29, n. 2, pp. 147-160. Il paper fondante, sorprendentemente leggibile. Introduce la distanza di Hamming, i codici a parità multipla e la sindrome che localizza l’errore. Nato dalla frustrazione dei calcolatori a relè che si fermavano nei weekend.
Reed, I. S. & Solomon, G. (1960). Polynomial Codes over Certain Finite Fields, Journal of the Society for Industrial and Applied Mathematics, vol. 8, pp. 300-304. Cinque pagine che hanno dato i codici dietro CD, DVD, QR code e dischi: codici su simboli, ottimali rispetto alla distanza.
MacKay, D. J. C. (2003). Information Theory, Inference, and Learning Algorithms, Cambridge University Press. Disponibile gratuitamente online. Il riferimento ideale per l’intuizione: la decodifica del codice (7,4), l’immagine geometrica delle sfere di decodifica, i codici a ripetizione e LDPC, di cui MacKay è tra i riscopritori.
Cover, T. M. & Thomas, J. A. (2006). Elements of Information Theory, 2a ed., Wiley. Il riferimento formale per distanza minima, capacità di rilevazione e correzione, e il legame con la capacità di canale.
Wang, X., Wei, J., Schuurmans, D., Le, Q., Chi, E., Narang, S., Chowdhery, A. & Zhou, D. (2022/2023). Self-Consistency Improves Chain of Thought Reasoning in Language Models, arXiv:2203.11171, presentato a ICLR 2023. Il voto di maggioranza su catene di ragionamento campionate; da leggere tenendo a mente che l’analogia con il codice a ripetizione regge solo finché gli errori sono indipendenti.