Teoria dei codici, musica e compact disc

Teoria dei codici vs. Teoria dell'informazione


La teoria dell'informazione è una parte del Calcolo della Probabilità con estese applicazioni ai sistemi di comunicazione. E' stata iniziata da Claude Shannon nel 1948, in un lavoro che analizza i limiti fondamentali della compressione dei dati e della trasmissione su canali con rumore.

La teoria dei codici è invece connessa alla ricerca di metodi efficienti e affidabili di trasmissione e memorizzazione dei dati, che possono essere divisi all'incirca tra compressione dei dati e tecniche di controllo degli errori.

Possiamo quindi distinguere le due teorie al lavoro: la teoria dell'informazione studia come comprimere i dati, in modo da rendere efficiente la trasmissione o la memorizzazione: ad esempio, creando il formato ZIP per rendere i file più "leggeri". La seconda invece aggiunge bit extra, per rendere la trasmissione dei dati più sicura in canali con rumore. Gli utenti sono forse meno consci di questo, ma la sua applicazione è cruciale per lo sviluppo di internet, per l'utilizzo dei CD, per rendere stabili le comunicazioni telefoniche, ecc...

In effetti, la teoria dei codici richiede la teoria dell'informazione, e viceversa questa stabilisce i limiti teorici su quello che si può fare codificando in maniera opportuna l'informazione. Le due teorie sono intimamente legate, anche se nel passato si sono sviluppate per lo più separatamente.


Ref.: Stefan M. Moser, Po-Ning Chen, A student's guide to coding and information theory. Cambridge University Press, 2012


Compact disc

Che cosa succede quando ascoltiamo la musica da un CD? Perché il suono non è così rovinato come su un vinile o una audiocassetta? Perché entra in gioco la matematica, che consente di tradurre la musica in formato digitale, leggere i dati dal supporto, correggere gli errori e ricostruire il suono in maniera eccellente, senza errori.

Descrizione
Il compact disc è composto da un disco di policarbonato trasparente, generalmente di 12 centimetri di diametro, accoppiato nella parte superiore ad un sottile foglio di materiale metallico sul quale, nella parte inferiore vengono memorizzate le informazioni come una successione di salti tra pits (buchi) e lands (terre), letti in sequenza per mezzo di un laser (per questo motivo sono detti anche dischi ottici).



I pit sono larghi circa 0,5 micrometri (μm) lunghi da 0,83 fino a 3,55 μmprofondi tra 0,1 e 0,2 μm. Lo spazio tra due tracce è di circa 1,6 μm.




Contrariamente a quanto ci si potrebbe aspettare, land e pit non rappresentano le cifre binarie 0 e 1. Il metodo usato si basa invece sull'alternarsi di lands e pits. Ogni transizione  pit-land e land-pit viene interpretata come un bit 1, mentre le aree piane, che si trovano prima e dopo ogni transizione, sono qualificate come uno o più bit 0 consecutivi.

Le transizioni devono essere frequenti: in pratica, non si possono avere due 1 consecutivi ed il numero di zeri tra due bit a 1 può andare da un minimo di due ad un massimo di dieci.

I dati sono ordinati lungo un'unica traccia a forma di spirale, che parte al centro (contrariamente ai dischi in vinile) e procede verso l'esterno, permettendo così di avere CD più piccoli dello standard (per esempio i mini-CD o i CD a forma di carta di credito).

Dato che il laser deve leggere i dati a velocità uniforme, sia che si tratti della parte esterna sia quella interna del disco, si deve variare la velocità di rotazione del disco, che passa da 500 giri al minuto al centro a 200 giri al minuto all'esterno. Nel complesso, la spirale dei dati è lunga circa 5 km.

Come trasformare la musica in bit?

  1. Per codificare la musica, il segnale analogico viene campionato 44.100 volte al secondo. Questo tasso di 44,1 kHz è sufficiente per poter udire le frequenze fino a 20.000 Hz.
  2. Ogni campione viene codificato usando 16 bit, quindi, dato che vogliamo ascoltare in stereo, ogni campione richiede in realtà 32 bit (4 successivi byte).
  3. La successione dei byte viene creata usando gruppi di lunghezza fissata a cui vengono aggiunti i gruppi di byte di correzione. In un CD, ogni sequenza di 24 byte viene trasformata, in due passi, in una parola di lunghezza 32 byte. I codici che vengono usati sono codici di Reed-Solomon (vedi la sezione 3.2.2) di tipo [28,24] e [32,28], rispettivamente.
  4. Infine, viene aggiunto un 33-esimo byte (il subcode), che contiene le informazioni da visualizzare sul display.
 In definitiva: 6 campioni vengono trasformati in un frame di 33 byte di dati.

Abbiamo 33 data byte: li trasformiamo ulteriormente in una successione di bit che infine dovremo trasferire sul supporto fisico.
  1.  8 data bit vengono trasformati in 17 channel bit;
  2.  una sequenza di 27 channel bit viene aggiunta ogni 33 sequenze di 17 channel bit (ossia, dopo 33 sequenze di 8 data bit); questa sequenza serve come sincronizzazione e viene usata per identificare l'inizio del prossimo blocco di dati. Dovremo quindi scegliere come sequenza di sincronizzazione una successione di bit che non può comparire tra i dati, in modo che non possa nascere alcuna confusione.
 Nel complesso, abbiamo allora questo schema:
  6 campioni → 33 × 8 = 264 data bit → 264 × (33 × 17 + 27)/(33 × 8) = 588 channel bit.
1 secondo → 44.100 × 588 / 6 = 4.321.800 bit

Quanti errori sul CD?

In conclusione, un secondo di musica corrisponde a 4.321.800 bit sulla traccia audio del vostro CD. Se il lettore CD legge il segnale facendo in media 1 errore ogni 1000 bit, avrete comunque migliaia di errori al secondo!

Ci sono molte cause di errore su un CD. Vi può essere dello sporco, la superficie può contenere bolle d'aria, possono essere stati fatti errori nella preparazione o nella scrittura della traccia, poi ditate, graffi, polvere...

Dato che è praticamente impossibile mantenere la superficie in condizioni perfette, non si può chiedere tanto agli utenti, né pensare che si debba gettare il disco quando il supporto diventa imperfetto. Ecco allora che si rende necessario consruire qualche meccanismo per proteggere i dati dagli errori: per questo scopo, la matematica ci mette a disposizione i codici a correzione di errore.


La matematica del compact disc

Parole e codici

Una sorgente di dati produce un numero finito di possibili simboli (messaggi di lunghezza unitaria). Questo è sicuramente vero per una sorgente digitale, mentre per una sorgente analogica (la musica!) sarà necessario intervenire con un convertitore analogico-digitale.

Definiremo alfabeto Q della sorgente l'insieme di tutti i possibili simboli in uscita.

Per contare il numero di errori (precisamente, di bit errati) in una parola che abbiamo ricevuto si usa la distanza di Hamming tra questa e la parola che è stata inviata. Questa distanza permette di confrontare sempre due stringhe della stessa lunghezza

La distanza di Hamming tra due stringhe di ugual lunghezza è il numero di posizioni nelle quali i simboli corrispondenti sono diversi. 
In altri termini, la distanza di Hamming misura il numero di sostituzioni necessarie per convertire una stringa nell'altra, o il numero di errori che hanno trasformato una stringa nell'altra.


La distanza di Hamming tra 1011101 e 1001001 è 2.
La distanza di Hamming tra 2143896 e 2413796 è 3.

Per una fissata lunghezza n, la distanza di Hamming è una metrica sull'insieme delle stringhe aventi quella lunghezza, poiché soddisfa le condizioni di non negatività, identità di due elementi aventi distanza nulla, simmetria, e disuguaglianza triangolare.

Diremo che una stringa a di lunghezza n su un alfabeto Q è una parola. Se la prossima parlla è scritta con una lettera sbagliata, allora sappiamo che ha distanza di Hamming 1 dalla parola corretta.
La ragione per cui possiamo riconoscere la parola corretta è che nel nostro linguaggio è l'unica ad avere una distanza così piccola dalla parlla scritta sbagliata.

La teoria dei codici si occupa (fra l'altro) di costruire linguaggi (codici), ossia collezioni di parole, che siano stabili nel caso di trasmissione di messaggi in presenza di rumore nel canale.
Fissiamo una soglia e per il numero di errori possibili nella trasmissione di una parola. Se il linguaggio che costruiamo è tale che la distanza tra due parole a caso sia almeno 2e+1, allora
se una parola è scritta con al massimo e errori, esiste una unica parola nel codice che ha distanza minima dalla parola data.


Esempio. Il codice a barre è un esempio di linguaggio in cui la distanza tra le parole è 2; in questo modo, quando il prodotto viene passato dallo scanner del supermercato, può accadere che un bit (ossia una barra, ossia uno 0 o un 1) sia letto incorrettamente. Il lettore si accorge dell’errore e dà un segnale alla cassiera di ripetere la lettura.

Codici a correzione di errore

Cominciamo ora a parlare dei codici a correzione di errore. 
Per prima cosa, osserviamo che è impossibile creare tale codice senza aumentare la dimensione delle parole.

Supponiamo di avere un codice C di parole aventi lunghezza k. Codificare vuol dire creare una mappa da C ad un altro codice C' di parole di lunghezza n, e se non vogliamo aumentare la lunghezza delle parole, dobbiamo imporre che anche C' abbia parole di lunghezza n=k. Dovremo richiedere che la mappa sia iniettiva (vogliamo poter riconoscere, da una parola in C', la corrispondente parola in C) e surgettiva (se leggiamo una parola in C', deve esistere almeno una parola in C da ricostruire).
Allora la mappa che costruiamo è una bigezione. Ma è evidente che l'inversa di questa mappa è definita solo su C', quindi se leggiamo una parola x corrotta, quindi non in C', non è possibile riconoscere quale era la sua pre-immagine corretta s.

Allora, la lunghezza di x (ossia, il valore n) dovrà essere maggiore di quella di s: in questo modo, se x è corrotta, c'è la speranza che s sia ricostruita grazie agli (n-k) bit dove possiamo mettere informazione extra.

Iniziamo a presentare i più semplici esempi di codici a correzione di errore.

Il primo è il codice a ripetizione.
Se devo inviare la parola CASA, posso inviare CCCAAASSSAAA. Se anche una lettera arrivasse corrotta, ad esempio CCCASASSSAAA, potrei recuperare la parola corretta scegliendo nella tripletta ASA il simbolo maggiormente ripetuto.
Nella sua semplicità, questo è un codice molto inefficiente: è infatti necessario triplicare la lunghezza della parola.
Negli anni '40 dello scorso secolo, Richard Hamming trovò un modo brillante per migliorare la situazione.

Il codice di Hamming

Come funziona l'idea di Hamming? Si tratta di applicare un po' di matematica modulo 2.
Consideriamo un blocco di 4 cifre binarie: l'idea è di aggiungere un blocco di 3 bit di correzione, in questo modo.

I quattro bit sono scritti nelle parti con i numeri da 1 a 4; i bit di correzione si trovano nei posti 5,6 e 7. La regola vuole che ogni cerchio deve contenere un numero pari di 1 (ossia, la somma modulo 2 è 0).

Una configurazione di 7 bit che contiene un errore produrrà uno o più cerchi con un numero dispari di 1. Allora, il bit che appartiene a tutti i cerchi con la parità sbagliata e a nessun cerchio con parità corretta è sbagliato e deve essere modificato.


Il codice di Hamming è un codice in cui ogni parola di lunghezza 7 contiene 4 bit di informazione. Diremo che è un codice binario [7,4]. Per confronto, il codice a ripetizione è un codice [3,1]. 

Il codice Reed-Salomon

Come abbiamo detto, non è il codice di Hamming che viene usato nella scrittura della musica sui CD, ma il codice Reed-Solomon. Questo codice fu inventato nel 1960 da Irving S. Reed e Gustave Solomon, che al tempo lavoravano al Lincoln Laboratory del Massachusetts Institute of Technology. 
Non è solo nella scrittura dei compact disc che i codici Reed-Solomon sono stati applicati. E' di questo tipo la codifica usata per le comunicazioni con le sonde del programma spaziale Voyager, lanciate dalla NASA nel 1977.

Il codice Reed-Solomon è un tipo di codice lineare (ciclico) non binario di rilevazione e correzione d'errore.
Perché non binario? perché questo codice lavora con byte e non bit.

Un codice di Reed-Solomon [N,K] ha distanza minima del codice pari a d = N - K + 1 e riesce a correggere fino a ⌊d/2⌋ errori e d cancellature. Quando una parola viene decodificata si possono verificare tre situazioni:
  1. se 2s + r < d (s errori e r cancellature) allora la parola  di codice viene decodificata correttamente;
  2. il decodificatore riconosce che non può decodificare la parola e lo segnala;
  3. il decodificatore decodifica la parola in modo errato.
Esempio. Più recenti, e più evoluti dei codici a barre, sono i QR-code, quei quadratini pieni di punti che vengono usati per fornire link o altre informazioni. I dati sono codificati sul QR-code utilizzando un codice Reed-Solomon, per permettere di utilizzare le informazioni contenute anche quando il supporto sia parzialmente danneggiato, o poco leggibile, oppure macchiato.

Esempio. Stampare un libro

Per semplificare la notazione, consideriamo un alfabeto di 31 elementi; l'algebra è quella, usuale, modulo 31 (ad esempio, 6 × 9 = 23). Possiamo pensare all'alfabeto come dato dalle lettere (i numeri da 1 a 26), lo spazio (0), e 4 altri simboli tipografici.

Vogliamo stampare un libro di 200 pagine, 3000 battute per pagina.  Ci è stato detto che il processo tipografico fa errori con una probabilità dello 0,1% per ogni battuta: in media, 3 errori per pagina.

Per migliorare la leggibilità del libro, decidiamo di applicare un codice Reed-Solomon [6,4].
Iniziamo con il dividere la nostra opera in una successione di simboli e di raggrupparli 4 a 4. Prima di ogni gruppo aggiungiamo 2 simboli di correzione e otteniamo la parola a = (a0, a1, a2, . . . , a5) dove a0 e a1 sono i codici di correzione mentre a2, . . . , a5 sono i dati (tutti nell'alfabeto F31).

Consideriamo la parola SALE. Questa corrisponde ai simboli a2 = 19, a3 = 1, a4 = 12, a5 = 5.
Le regole per calcolare a0 e a1 sono:

a+ a+ a2 + . . . + a5 = 0 (modulo 31), e
0 × a+ 1 × a+ 2 × a2 + . . . + 5 × a5 = 0 (modulo 31).

Risolvendo il sistema si ha Allora si ha a0 = 15 e a1 = 10, quindi la parola SALE si codifica come OJSALE.

Supponiamo di aver ricevuto OJTALE. Se non consideriamo i codici di correzione, leggiamo la parola TALE. Ma, se guardiamo alla parola nel complesso, vediamo che deve esserci stato un errore, infatti
15 + 10 + 20 + 1 + 12 + 5 = 1 (modulo 31)
possiamo supporre che un simbolo sia stato sostituito dal successivo... ma quale? 

Osserviamo che se un simbolo ak  viene inviato come ak +1, allora la seconda equazione del sistema precedente ci dà come somma k; nel nostro esempio, otteniamo
10 + 40 + 3 + 48 + 25 = 2
quindi l'errore è nel simbolo a2 che è stato inviato come a2 + 1=T e recuperiamo il valore corretto, ossia a2 = S.

Osserviamo che il codice che stiamo usando corregge un errore in un gruppo di 6 simboli, con un tasso di informazione pari a 4/6; se però vogliamo che il numero di pagine non cambi, è chiaro che dobbiamo aumentare di una volta e mezzo il numero di simboli stampati per pagina. 
Il tipografo ci informa che diminuire la dimensione dei simboli porta a raddoppiare la probabilità di errore per ogni simbolo! In altre parole: prima dell'applicazione del codice di correzione, dobbiamo aspettarci 9 errori per pagina.

E dopo le correzioni portate dal codice? Abbiamo visto che una parola di sei simboli viene correttamente interpretata se ha al più un errore. La probabilità che una parola abbia più di un errore è

Il numero medio di parole che non potremo correggere è inferiore a uno per pagina, anzi, ci saranno in media non più di dieci parole sbagliate in tutto il libro: un miglioramento mica male!

Rimanendo nell'ambito dei codici Reed-Solomon, possiamo ulteriormente migliorare la situazione. Raggruppiamo i simboli in parole di lunghezza 8 e aggiungiamo 4 simboli di correzione. Otteniamo un codice [12,8] il cui tasso di informazione è 8/12 = 2/3, come il precedente.


In questo caso, le regole per determinare i simboli di correzione sono
le seguenti (i codici di correzione sono a0, a1, a2 e a3 e i dati a4, a5, . . . , a11:
a0 + a+ a2 + . . . + a5 = 0 (modulo 31), 
0 × a+ 1 × a+ 2 × a2 + . . . + 5 × a5 = 0 (modulo 31),
02 × a0 12 × a22 × a2 + . . . + 52 × a5 = 0 (modulo 31), e
03 × a+ 13 × a+ 23 × a2 + . . . + 53 × a5 = 0 (modulo 31).

Risolvere queste 4 equazioni è un po' più complicato, ma ne vale la pena: questo codice infatti corregge 2 errori in ogni parola.

Non ci sono ulteriori problemi per la stampa, in quanto il numero di simboli necessari non cambia rispetto al codice precedente. Ora, però, la parola viene decodificata in maniera errata solo se contiene almeno 3 errori. La probabilità che questo accada è inferiore a 2 ×10-6.

Dato che un libro contiene 600 mila simboli, ossia 75 mila parole di lunghezza 8 simboli, il numero medio di parole errate nel libro è pari a 0,15: è improbabile trovare anche un solo errore in tutto il libro.


Scrivere un CD


Abbiamo visto che la codifica di un CD prevede l'utilizzo di due codici Reed-Solomon, con parametri [28,24] e [32,28] rispettivamente. Il tasso di informazione in un CD è pari a 24/32 = 3/4; aver aggiunto un codice di correzione fa sì che la probabilità di avere un errore in un singolo bit è aumentata (è necessario scrivere un terzo di dati in più nello stesso supporto fisico).

Un tipico CD contiene fino a mezzo milione di bit sbagliati. Inoltre, questi errori non avvengono a caso, ma sono raggruppati in singole zone dove sono molto numerosi: può facilmente accadere che qualche migliaio di bit consecutivi sia errato. Per ridurre questo problema, i CD vengono scritti in modo che i simboli vicini appartengano a parole diverse (interleaving).

Come abbiamo visto nell'esempio del libro, usare un codice migliore aumenta la precisione, ma richiede anche più calcoli. Nel caso del CD, ovviamente, il numero di calcoli non deve superare una certa soglia, altrimenti non si riuscirebbe a sentire la musica nei tempi corretti.

Una delle ragioni per cui si è scelto di usare un doppio codice di tipo Reed-Solomon è che è possibile mostrare che i due codici lavorano insieme.
Per descrivere la situazione, consideriamo i due codici C1, C2 di tipo Reed-Solomon con parametri [28,24] e [32,28] rispettivamente; sappiamo che entrambi hanno distanza di errore 5. 

Invece di applicare il primo codice ad un blocco di 24 dati, li applichiamo insieme ad un blocco di 24 × 28 = 672 dati. Scriviamo i dati in una matrice 24 × 28; questa matrice viene considerata come la parte iniziale di una matrice 28 × 32. I restanti simboli sono scritti facendo in modo che ogni colonna (lunghezza 28) sia scritta nel codice C1 e ogni riga (lunghezza 32) sia scritta nel codice C2.
Il codice ``prodotto'' che abbiamo ottenuto ha teoricamente distanza di errore 25 e quindi può correggere fino a 12 errori in una parola (che, ricordiamo, è una matrice 28 × 32).
In realtà, il codice è più potente di così. Consideriamo il caso in cui vi siano 21 errori. Ad esempio, 12 colonne con un errore, una con 2, una con 3 e una con 4 errori. Beh, a prima vista non è possibile trattare questo caso. Decidiamo, comunque, di usare C1 per correggere un solo errore. In questo modo, correggiamo le 12 colonne con un solo errore, ci accorgiamo che esistono due colonne con più di un errore e, infine, la cosa peggiore che può succedere è che il codice creda di aver corretto la colonna con 4 errori, portandoli invece a 5.
Ora, vediamo qual è il trucco che sistema tutto. Cancelliamo le colonne con più di un errore e ci troviamo con 32 righe di lunghezza 28, che hanno tutte 2 elementi cancellati e di cui 27 non hanno altri errori mentre altre 5 hanno un solo altro errore. Dato che il codice C2 corregge contemporaneamente 2 cancellature e un errore, allora possiamo recuperare tutti i dati corretti.