codici e scrittura di un compact disc

La matematica del compact disc (J. van Lint)
S. Bonaccorsi
Corso di Mathematical model for the Physical, Natural and Social Sciences
Outline
Indice
1
Introduzione.
1
2
La matematica del compact disc.
2.1 Parole e codici. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Codici a barre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
2
2
3
Dalla musica ai bit.
3.1 Come trasformare la musica in bit? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Il codice Reed-Salomon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
3
4
4
QR code
6
1
Introduzione.
Introduzione.
Che cosa succede quando ascoltiamo la musica da un CD? Perché il suono non è così rovinato come su un vinile
o una audiocassetta?
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 successioni di “buchi” e “terre” (in inglese pits e lands) successivamente letti per
mezzo di un laser (per questo motivo sono detti anche dischi ottici).
I pit sono larghi circa 0,5 µm, lunghi da 0,83 fino a 3,55 µm, profondi
tra 0,1 e 0,2 µm. Lo spazio tra due tracce è di circa 1, 6µm.
Contrariamente a quanto ci si potrebbe aspettare, lands e pits 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).
1
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.
2
La matematica del compact disc.
2.1
Parole e codici.
Distanza di Hamming
Iniziamo con un alfabeto Q di simboli.
Definizione.
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.
Example 2.1. 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.
Wikipedia dice che...
Viene usata nelle telecomunicazioni per contare il numero di bit errati in una parola binaria a lunghezza fissa, allo
scopo di stimare l’errore. Per questo motivo viene anche chiamata distanza del segnale.
Parole e codici
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.
Il nostro scopo è costruire un linguaggio (ossia, un codice) tale che la distanza tra due parole a caso sia almeno
2e + 1, dove e ≥ 1 è un intero.
• 2e + 1 è detta la distanza minima del codice;
• se una parola è scritta con al massimo e errori, allora esiste una unica parola nel codice che ha distanza minima
dalla parola data.
2.2
Codici a barre
Consideriamo ad esempio i codici a barre:
• ad ogni prodotto viene assegnato un numero di 12 cifre (decimali);
• ogni cifra viene rappresentata da una stringa di lunghezza 7 sull’alfabeto binario;
• ogni 0 viene rappresentato da un sottile barra vuota, ogni 1 da una sottile barra piena.
2
Example 2.2. Ad esempio, 4 si codifica come 0100011, quindi una barra bianca (di una unità di larghezza), poi una
barra nera (di una unità), quindi una barra biancha (di 3 unità) e una nera (di due unità).
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 codice scelto per gli errori e per i prodotti è tale che il lettore si accorge
dell’errore e dà un segnale alla cassiera di ripetere la lettura.
Codici a correzione di errore
Il primo codice a correzione di errore efficiente fu scoperto da R. W. Hamming, presso i laboratori Bell, nel 1948.
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.
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].
Se avessimo semplicemente ripetuto le cifre, avremmo ottenuto un codice [8,4] che quindi aveva un tasso di informazione pari a 84 < 47 del codice di Hamming, e in più
questo codice può determinare l’esistenza di un errore ma non correggerlo.
3
Dalla musica ai bit.
3.1
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
bytee. I codici che vengono usati sono codici di Reed-Solomon di tipo [28,24] e [32,28], rispettivamente.
4. Infine, un 33-esimo byte (il subcode) viene aggiunto, che contiene le informazioni da visualizzare sul display.
In definitiva:
6 campioni vengono trasformati in un frame di 33 byte di dati.
3
Come trasferire la musica sul CD?
Abbiamo 33 data byte: li trasformiamo ulteriormente in una successione di bite 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.
3. Nel complesso, abbiamo allora questo schema:
6 campioni −→ 33 × 8 = 264 data bit −→ 264 ×
33×17+27
33×8
= 588 channel 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...
Di solito, gli errori si accumulano e si trovano tutti vicini; dato che i codici a correzione di errore servono per
salvarci dagli errori casuali, dovremo scrivere i dati in maniera “casuale”, in modo che i nostri codici possano aiutarci
a salvare l’ascolto.
3.2
Il codice Reed-Salomon
Il codice fu inventato nel 1960 da Irving S. Reed e Gustave Solomon, che al tempo lavoravano al Lincoln laboratory del
Massachusetts Institute of Technology. Nel 1977 i codici Reed-Solomon furono applicati mirabilmente nel programma
spaziale Voyager, sotto forma di codici concatenati per il controllo degli errori.
Il codice Reed-Solomon è un tipo di codice lineare (ciclico) non binario di rilevazione e correzione d’errore.
Principali proprietà.
Un codice di Reed-Solomon [N,K] ha distanza minima del codice pari a d = N − K + 1 e riesce a correggere fino a
bd/2c errori e d cancellature. Quando una parola viene decodificata si possono verificare tre situazioni:
• se 2s + r < d (s errori e r cancellature) allora la parola di codice viene decodificata correttamente;
• il decodificatore riconosce che non può decodificare la parola e lo segnala;
• il decodificatore decodifica la parola in modo errato.
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.
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 e i rimanenti 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:
4
1. a0 + a1 + a2 + a3 + a4 + a5 = 0 (modulo 31), e
2. 0 · a0 + 1 · a1 + 2 · a2 + 3 · a3 + 4 · a4 + 5 · a5 = 0 (modulo 31).
Allora si ha a0 = 15, a1 = 10 e 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 formula (2) precedente ci dà come somma
k; se sostituiamo i valori ottenuti nella formula (2) precedente, 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 è
6
2 k 998 6−k
P
6
' 6 × 10−5 .
1000
1000
k
k=2
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: un miglioramento mica male!
Con un ulteriore passaggio a un secondo codice, possiamo ulteriormente migliorare la situazione. Raggruppiamo
i simboli in parole di lunghezza 8 e aggiungiamo 4 simboli di correzione. Otteniamo ancora un codice 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 (codici di correzione a0 , . . . , d3
e dati a4 , . . . , a11 :
1. a0 + a1 + a2 + a3 + a4 + a11 = 0 (modulo 31), e
2. 0 · a0 + 1k · a1 + 2k · a2 + · · · + 11k · a11 = 0 (modulo 31) per ogni k = 1, 2, 3.
Risolvere queste 4 equazioni è un pò più complicato, tuttavia questo codice corregge 2 errori!
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 bit, 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 il tasso di informazione in un CD è pari a 28/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.
5
Scrivere un CD.
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 e C2 , di tipo Reed-Solomon con parametri [28,24] e
[32,28] rispettivamente; sappiamo che entrambi hanno distanza di errore 5.
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 distanza di errore 25 e quindi può correggere fino a 12 errori in una
parola (che, ricordiamo, è una matrice 28 × 32).
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.
4
QR code
Negli anni ’90 la compagnia giapponese Denso Wave, allo scopo di tracciare i pezzi delle automobili nelle fabbriche
Toyota, svilupparono un codice a barre bidimensionale che permetteva di memorizzare più dati rispetto ai codici a
barre tradizionali.
Nel 1995 Denso Wave ha rilasciato i codici QR sotto licenza libera e la NTT DoCoMo
ha creato i-mode, un sistema per l’utilizzo del web tramite telefono cellulare: in breve
tempo i codici QR code divennero pervasivi nella vita giapponese.
In Europa e negli Stati Uniti la diffusione dei codici QR è stata più lenta; una accelerazione è stata favorita anche
dalla diffusione degli smartphone: sono molte le applicazioni gratuite di lettura dei QR distribuite sia dall’Android
Market, che da App Store o da altri siti web. Inoltre diversi siti offrono l’opportunità di generare i codici gratuitamente.
Al contrario dei precedenti barcode unidimensionali, che erano stati disegnati per essere passati meccanicamente
da un raggio luminoso sottile e concentrato, un QR code è analizzato da un sensore di immagine bi-dimensionale e
successivamente analizzato tramite un apposito programma.
Il processo di codifica permette di realizzare un sistema abbastanza solido rispetto alle letture. Innanzitutto,
il processo identifica i tre quadrati distintivi agli angoli dell’immagine, usando un quadrato più piccolo (o un
sistema di quadrati) vicino al quarto angolo per normalizzare l’immagine rispetto alla dimensione, all’orientamento e all’angolo di visuale. I piccoli punti interni
al QR code sono, successivamente, convertiti in numeri
binari e validati con un codice a correzione di errore.
Le parole usate dal codice sono di 8 bit e viene usato
un codice Reed-Solomon con quattro possibili livelli di
6
correzione di errore. Ovviamente, la scelta è economica: maggiore la capacità di correggere errori, minore la
capacità di stimare dati. La seguente tabella fornisce la capacità (indicativa) di correzione ad ogni livello:
Livello
L (basso)
M (medio)
Q (quartile)
H (alto)
percentuale di parole che possono essere corrette
7%
15%
25%
30%.
Nei QR code più grandi, il messaggio è spezzato in numerosi blocchi, in ognuno dei quali si possono correggere
fino a un massimo di 15 errori (questo, per poter gestire la complessità dell’algoritmo di decodifica). I blocchi sono
quindi interlacciati, facendo in modo che un danno localizzato in un QR code non impedisca la decodifica di nessun
blocco.
7

Download Report