Elementi di Teoriadell’Informazione

classica e quantistica

DAL BIT AL QUBIT

Carlo Bianciardi

Copyright © MMIXARACNE editrice S.r.l.

www.aracneeditrice.itinfo@aracneeditrice.it

via Raffaele Garofalo, 133 A/B00173 Roma

(06) 93781065

ISBN 978–88–548–2486–7

I diritti di traduzione, di memorizzazione elettronica,di riproduzione e di adattamento anche parziale,

con qualsiasi mezzo, sono riservati per tutti i Paesi.

Non sono assolutamente consentite le fotocopiesenza il permesso scritto dell’Editore.

I edizione: aprile 2009

  

                                                                           7

Indice Prefazione 11 Capitolo I I fondamenti della teoria 13 1.1 I due problemi della comunicazione 13 1.2 Codifica dei messaggi 15 1.3 Informazione e unità di misura 18 1.4 Qualche esempio significativo 20 APPENDICE 1: complementi e problemi 21 A1.1 Sulla definizione dell’informazione e della sua misura 21 A1.2 Problemi proposti 23 Capitolo II Sorgenti classiche di informazione 27 2.1 Sorgenti senza memoria ed entropia 27 2.2 Sorgenti con memoria. Sorgente di Markov 30 2.3 Sorgenti ergodiche. Entropia della sorgente di Markov 32 2.4 Estensione della sorgente 34 2.5 La struttura dei linguaggi 36 2.6 Codifica di sorgente 37 2.7 Lunghezza delle parole del codice 39 2.8 Primo teorema di Shannon. Compressione dei messaggi 42 2.9 Codici di Huffman 44 2.10 Efficienza e ridondanza di un codice 45 2.11 Cenni sulla teoria della distorsione 46

8 Indice  

APPENDICE 2: complementi e problemi 48 A2.1 Informazione ed entropia termodinamica 48 A2.2 Generazione di sorgenti discrete con la moneta perfetta 51 A2.3 Problemi proposti 53 Capitolo III Canali di informazione 57 3.1 Trasmissione dell’informazione 57 3.2 Canali di trasmissione 58 3.3 Probabilità di un canale 62 3.4 Entropie a priori e a posteriori 63 3.5 Equivocazione del canale 65 3.6 Informazione mutua 68 3.7 Entropia congiunta 70 3.8 Canali senza rumore e canali deterministici 73 3.9 Canali in cascata 76 3.10 Canali ridotti e riduzioni sufficienti 78 3.11 Additività dell’informazione mutua 82 3.12 Capacità del canale 84 3.13 Probabilità d’errore e regole di decisione 87 3.14 Codifica di canale 90 3.15 Secondo teorema di Shannon 94 APPENDICE 3: complementi e problemi 97 A3.1 Il canale bianco gaussiano 97 A3.2 Sulla dimostrazione del secondo teorema di Shannon 101 A3.3 Problemi proposti 103 Capitolo IV Codici per canali con rumore 107 4.1 Limitazioni per una comunicazione affidabile 107 4.2 Necessità della codifica di canale 109 4.3 Codici lineari blocco 112 4.4 Matrice generatrice e matrice di ricerca di parità 113 4.5 Decodifica dei codici lineari blocco 117 4.6 La disposizione standard 119

Indice 9

4.7 Decodifica e probabilità d’errore 121 4.8 Rivelazione e correzione d’errore 125 4.9 Principali classi di codici lineari blocco 126 A) Codici di Hamming 127 B) Codici ciclici 128 C) Codici BCH e RS 132 D) Codici blocco correttori di burst 134 4.10 Codici convoluzionali 136 4.11 Funzione di trasferimento 141 4.12 Decodifica con algoritmo di Viterbi 144 4.13 Caso generale binario 149 4.14 Probabilità d’errore 154 APPENDICE 4: complementi e problemi 157 A4.1 Sui codici catastrofici 157 A4.2 Problemi proposti 158 Capitolo V Sorgenti quantistiche di informazione 161 5.1 La meccanica quantistica 161 5.2 Sorgenti classiche e sorgenti quantistiche 162 5.3 Gli spazi vettoriali e i vettori bra e ket 165 5.4 Operatori lineari e auto vettori 167 5.5 Il qubit 170 5.6 Evoluzione temporale dello stato del qubit 175 5.7 Sistemi composti: entanglement e no-cloning 178 5.8 Codifica della sorgente quantistica 181 5.9 Informazione accessibile e Holevo bound 188 5.10 Canali quantistici 191 5.11 Circuiti quantistici e applicazioni 193 A) Possibili applicazioni dell’informazione quantistica 194 B) Algoritmo di Shor: principi di funzionamento 196 C) Codifica superdensa 197 D) Criptografia sicura 198 APPENDICE 5: complementi e problemi 199 A5.1 Equazione caratteristica e auto vettori per n=2 199

10 Indice  

A5.2 Operatori unitari X,Y,Z 200 A5.3 Problemi proposti 203 Bibliografia 205 Indice analitico 209

  

11

Prefazione

Si usa datare la nascita della Teoria dell’Informazione con il fon-

damentale lavoro di C.E. Shannon The Mathematical Theory of Com-munication apparso nel 1948 sul Bell System Technical Journal. La teoria è basata su tre acquisizioni decisive che sintetizzano le risposte ai problemi incontrati nei decenni precedenti e durante il conflitto mondiale dagli ingegneri della comunicazione.

In primo luogo l’informazione, veicolata da un messaggio di cui è nota la probabilità di essere emesso, può essere definita e misurata, generalmente in bit (Cap.I). Inoltre la sorgente classica di informazio-ne è data quando sono noti i messaggi che può emettere e la probabili-tà con cui li emette. Essi devono essere rappresentati o codificati con simboli adatti ad essere inviati, per lo più elettricamente, al ricevitore attraverso il canale di trasmissione. Come i simboli binari, 0 e 1. Shannon scoprì una grandezza, l’entropia della sorgente, che indica il numero minimo e più economico di simboli necessari a rappresentare in media un messaggio (Cap.II). Infine: durante la trasmissione i mes-saggi codificati alla sorgente sono disturbati dal rumore di fondo del canale. La prima risposta al problema era stata quella di ripetere i messaggi, aumentando la probabilità di essere correttamente percepiti ma diminuendo, anche notevolmente, la velocità di trasmissione. Shannon individuò allora una seconda grandezza, la capacità del cana-le. E’sufficiente che la velocità, pur mantenendosi abbastanza elevata, non ne ecceda il valore perché, con una seconda codifica, la trasmis-sione sia affidabile quanto si vuole (Cap.III).

Nei decenni successivi gli sforzi degli ingegneri e dei fisici della comunicazione si sono concentrati nel progettare le opportune tecni-che di codifica di canale finalizzandole al raggiungimento della desi-derata affidabilità (Cap.IV). Nel frattempo la teoria dimostrava di non essere semplicemente una “sezione” del più generale problema della comunicazione come può lasciare intendere lo stesso titolo dell’opera di Shannon. Al contrario, la sua sinergia con discipline diverse dalla comunicazione testimonia semmai l’opposto. Dalla teoria del portfolio in economia, a quella della complessità di Kolmogoroff relativa alla

12 Prefazione 

scienza dei computer; dalle implicazioni termodinamiche a quelle bio-logiche e chimico-ambientali; dalle interazioni con la statistica e la teoria dei quanti a quelle con la matematica. Inoltre, negli ultimi lustri la teoria è stata rivitalizzata dalla sua estensione alle sorgenti quanti-stiche dove può essere codificata informazione classica. Infatti, per e-sempio, ai due stati dello spin dell’elettrone o a quelli della polarizza-zione di un fotone possono essere associati i simboli binari come ai messaggi di una sorgente classica. Il qubit è la più elementare delle sorgenti quantistiche di informazione (Cap.V).

La fortuna della teoria è stata paradossale. E’ la madre naturale del computer, di internet, del cellulare e della rivoluzione tecnologica nel-la comunicazione digitale e multimediale. Tutto funziona con l’associazione di “stringhe” di bit a parole, suoni e immagini. Ha sconvolto la cultura, l’economia, i costumi di miliardi di persone negli ultimi trenta anni ed è stata il motore principale della globalizzazione. Ma, come sovente capita alla scienza e alla sua ricaduta tecnologica, il grado di consapevolezza culturale delle persone in materia è inversa-mente proporzionale al suo uso strumentale. A partire dai rivenditori di PC, tutti si usa (e si parla di) bit e byte ma non si sa spesso di che si tratta. La teoria della relatività ha avuto un impatto assolutamente mi-nore nella vita quotidiana della gente. Tutti sanno chi è Einstein, quasi nessuno sa chi è Shannon.

E’ l’irrisolto nodo della cultura scientifica e del suo insegnamento. Questo libro vuole essere un piccolo contributo alla diffusione di que-sta cultura rispetto ad un consumo delle sue ricadute tanto massiccio quanto inconsapevole e alienato. Con un tono spesso discorsivo unito al giusto rigore concettuale, con i passaggi più complessi confinati nelle appendici, esso è rivolto in primo luogo agli studenti di teleco-municazioni e informatica. Tuttavia i modesti pre-requisiti richiesti (di scuola secondaria: un po’ di algebra, di fisica e di calcolo delle pro-babilità) lo rendono potenzialmente fruibile da una platea ben più am-pia.

Aprile, 2009 Carlo Bianciardi

13

Capitolo I I fondamenti della teoria

1.1 I due problemi della comunicazione La teoria classica dell’Informazione, come avviene sovente nella

Scienza, è stata originata da problemi pratici. In questo caso da quelli incontrati dagli scienziati e dagli ingegneri delle comunicazioni relati-vamente alla struttura statistica delle apparecchiature e dei sistemi di comunicazione. Infatti si ha a che fare con una sorgente di messaggi che devono essere inviati ad un utente attraverso un mezzo di trasmis-sione, il canale, che può disturbare e alterare casualmente i messaggi medesimi. In prima istanza possiamo supporre inoltre che ciascun messaggio sia emesso con una certa probabilità invariante con il tem-po e indipendente dai messaggi precedenti (sorgente senza memoria).

Allora, in questa situazione, il primo problema che si pone è quello di rappresentare (codificare) nella maniera più efficace ed economica i messaggi, che possono riguardare qualunque argomento, con i simboli di un alfabeto più semplice e più adatto alla trasmissione e alla rappre-sentazione elettrica. Il problema è in linea di principio identico a quel-lo di rappresentare un oggetto o un concetto con le lettere dell’ordinario alfabeto. Non c’è dubbio che l’alfabeto più semplice ed elettricamente elementare è quello costituito da due simboli (aperto o chiuso, 0 o 1) detto ovviamente binario, che si è imposto storicamente nella teoria e nella pratica. Ma, a prescindere dall’alfabeto usato, la vera questione è: qual è il numero medio minimo di simboli per mes-saggio necessario a rappresentare lo stesso senza perdere l’informazione che esso trasporta? Ovvero: quanto può essere com-pressa la rappresentazione del messaggio senza che questo perda il suo contenuto informativo? E’ evidente l’interesse teorico e pratico di questo problema della comunicazione.

La risposta a questo fondamentale quesito fu data dallo stesso Shannon nella sua opera basilare citata nella Prefazione. Il numero

14 Capitolo I

medio minimo, più “economico”, è rappresentato dal valore dell’entropia della sorgente in questione, misurata in unità r – dove r è il numero dei simboli dell’alfabeto usato – che si chiama bit nel caso binario. Se si usa un valore inferiore si perde parte dell’informazione del messaggio, se si usa un valore superiore si introduce un’inutile ri-dondanza nella rappresentazione dello stesso.

L’altro grande problema che ha originato la teoria è legato alla tra-smissione all’utente della rappresentazione del messaggio (detta paro-la del codice usato) attraverso il canale rumoroso. Esso può alterarla a caso e far confondere un messaggio con un altro. La prima idea che venne agli ingegneri fu quella di ripetere la parola trasmessa per au-mentare la probabilità che fosse correttamente percepita dal ricevitore. E’ evidente che così facendo si introduceva una ridondanza nella tra-smissione poiché l’informazione veicolata da una parola viene “spal-mata” su tutte le sue ripetizioni. Quanto deve essere questa ridondanza perché la trasmissione sia assolutamente affidabile? Deve essere infi-nita?

Fu ancora Shannon che dette la risposta al problema. Egli scoprì e definì una grandezza, legata al canale di trasmissione e denominata capacità C, che determinava una ridondanza finita e accettabile per cui la probabilità di errore nell’individuazione della parola (messag-gio) effettivamente trasmessa poteva essere resa piccola a piacere. Più in dettaglio, supponiamo che il messaggio sia costituito da k bit di in-formazione e che questa venga inviata nel canale attraverso n> k sim-boli binari: è evidente che si introduce la ridondanza (n-k) come avve-niva nel caso della ripetizione e che ciascuno degli n simboli binari ha una percentuale, un tasso di informazione pari a R= k/n (velocità di trasmissione relativa o bit-rate, con ovvia denominazione). Ebbene, Shannon dimostrò che non era necessario introdurre una ridondanza sempre maggiore per minimizzare la probabilità d’errore facendo così tendere a zero anche la velocità di trasmissione. Purché il tasso di in-formazione per simbolo o bit-rate R fosse inferiore a C, la probabilità d’errore poteva essere ridotta quanto si voleva e quindi la trasmissione poteva essere resa comunque affidabile pur mantenendo una apprez-zabile velocità.

L’entropia della sorgente di informazione e la capacità del canale di trasmissione costituiscono le scoperte fondanti della teoria classica

I fondamenti della teoria 15

dell’Informazione. Ma, come vedremo nel Cap.V, anche nel caso delle sorgenti quantistiche di informazione si ha una generalizzazione di queste grandezze che pertanto rimangono il paradigma della teoria medesima.

1.2 Codifica dei messaggi Ogni sistema nel quale si genera, si trasmette e si usa

l’informazione può essere schematizzato nella forma più elementare e generale come in Fig.1.1

Si considerano insomma messaggi che trasportano informazione di

qualsiasi tipo o forma da una sorgente verso un ricevitore o utente at-traverso un qualsiasi mezzo di trasmissione o canale. La natura del messaggio informativo può essere di principio qualsiasi: parole, musi-ca, figure, immagini. Oppure, come avviene di frequente, la forma o il linguaggio può essere multimediale cioè un mix di parole, suoni e immagini: si tratta dei cosiddetti linguaggi sincretici. Ne sono esempi il Cinema e poi la televisione, Internet e appunto i comuni prodotti multimediali, ipertesti, ipermedia e cd-Rom. Va subito osservato che la cosiddetta comunicazione digitale consiste proprio nel trasmettere quest’informazione codificandola nel linguaggio binario ovvero nel trasformare parole, suoni e immagini in sequenze di 0 e 1 o viceversa – come fa il MODEM (Modulatore – Demodulatore) nei collegamenti Internet.

Prima di definire formalmente la quantità di informazione contenu-ta in un messaggio, è opportuno fare qualche esempio proprio della codifica binaria ovvero della corrispondenza che può essere stabilita fra messaggi e sequenze binarie. Osserviamo preliminarmente che una sequenza binaria è una disposizione con ripetizione di due oggetti, ap-

Sorgente / Tra-smettitore

Canale di trasmissione

Ricevitore / Utente

Figura1.1 Schema di generazione /trasmissione dell’informazione

16 Capitolo I

punto 0 e 1. La teoria del calcolo combinatorio ci informa che le di-sposizioni con ripetizione di n oggetti presi k alla volta (o di lunghez-za k) sono

Dn,k

® = nk ovvero, nel caso binario, 2k.

Pertanto le coppie binarie sono 4, le terne sono 8, …, le ottuple sono 256 e così via. Ad esempio, per codificare in binario i numeri da zero a nove, non sono sufficienti le terne ma occorrono le quaterne secondo uno schema come quello riportato

Consideriamo ora un altro semplice caso: lo stato del tempo a Ro-

ma in un certo intervallo di tempo, comunicato ad un utente di altra località attraverso i soliti messaggi binari. Se gli stati sono quattro (se-reno, nuvoloso, piovoso e nebbioso) e se siamo in un periodo dell’anno in cui sono praticamente equiprobabili ovvero ciascun stato ha probabilità ¼, allora potremmo usare nella comunicazione le quat-tro coppie binarie secondo lo schema seguente

stato probabilità Messaggio binario

sereno 1/4 00 nuvoloso 1/4 10 piovoso 1/4 01 nebbioso 1/4 11

Come si vede sono utilizzati due simboli binari o binit (da binary

digit) per messaggio ovvero, come si dice, parole della stessa lunghez-

numero codice 0 0000 1 0001 2 0010 3 0011 4 0100 5 0110 6 0101 7 0111 8 1000 9 1001

I fondamenti della teoria 17

za per messaggi assolutamente equivalenti sul piano della loro ricor-renza cioè della probabilità di essere trasmessi. Dato che si tratta di quattro messaggi equivalenti sembra impossibile usare meno di due binit/messaggio in trasmissione. Ma supponiamo ora di voler descri-vere sempre con quattro messaggi il tempo a Londra. In questo caso l’ultimo stato (nebbioso) è ragionevole classificarlo “con smog”. La configurazione delle probabilità è sicuramente diversa da stato a stato tanto che si può immaginare una più conveniente codifica binaria dei quattro messaggi secondo la tabella riportata

stato Probabilità Messaggio binario

sereno 1/8 1110 nuvoloso 1/8 110 piovoso 1/4 10 con smog 1/2 0

La ‘filosofia’ della seconda trasmissione ovvero del secondo codice

usato, a lunghezza di parola variabile, è che i messaggi più frequenti vengono rappresentati, per ovvi motivi, con parole più corte, mentre quelli meno frequenti con parole più lunghe. Inoltre, ciascuna parola termina con 0 di modo che la sequenza 1000110 non può che essere interpretata dal ricevitore come “piovoso, con smog, con smog, nuvo-loso”. Se allora chiamiamo codice1 quello usato per trasmettere lo sta-to del tempo di Roma e codice2 quello usato per trasmettere lo stato del tempo di Londra, viene spontaneo di domandarci quale sia più conveniente e cosa sarebbe successo se avessimo scambiato i due co-dici. E’ evidente che un termine di paragone è la cosiddetta lunghezza media delle parole del codice in binit per messaggio. Mentre, come abbiamo osservato, per il codice1 questa lunghezza media è di due bi-nit per messaggio, per il codice2 abbiamo,moltiplicando la lunghezza di ciascuna parola per la sua probabilità: L= 4. 1/8 + 3. 1/8 + 2. ¼ + 1.½ =1,7/8 binit/messaggio.

Pertanto, il codice2 sembra più efficiente del codice1 per quanto ri-guarda Londra perché, come è facile osservare, se avessimo usato il codice1 nel caso di Londra sarebbe stato ancora L= 2 binit/messaggio. E, viceversa, se avessimo usato il codice2 nel caso di Roma avremmo ottenuto L= 2,5 binit/messaggio. Insomma, sembra ragionevole chie-derci quali sono i parametri che definiscono l’efficienza di un codice

18 Capitolo I

per una data trasmissione e in che consiste l’apparente ‘economia’ di binit che si raggiunge usando il codice1 per Roma e il codice2 per Londra. Soprattutto in questo secondo caso, c’è da chiedersi perché, nonostante si abbiano quattro messaggi da trasmettere, sia possibile u-tilizzare meno di due binit per messaggio. Sembrerebbe che l’informazione da trasmettere fosse in media minore nel caso di Lon-dra.

Per poter impostare una ragionevole risposta a queste domande, emerge la necessità di definire una “misura della quantità di informa-zione”, contenuta in un messaggio, che abbia validità generale.

1.3 Informazione e unità di misura La base principale dell’intera teoria, originata dalle risposte ai pro-

blemi di cui al paragrafo 1.1, risiede nella possibilità di definire e mi-surare l’informazione o la quantità di informazione contenuta in un messaggio con il quale si comunica la realizzazione di un certo evento che, negli esempi del paragrafo precedente, era rappresentato da uno stato del tempo. Un messaggio recante la notizia della realizzazione di un evento o di un avvenimento (o, più semplicemente, un evento o un avvenimento) porta informazione.

Definizione. Si abbia un evento E che si verifichi con probabilità P(E). Se viene comunicato che l’evento E si è verificato, l’informazione ri-cevuta, contenuta nel messaggio, è definita come

1 I(E)=logb (1.1) P(E)

dove l’unità di misura è individuata dalla base b>1scelta per il loga-ritmo e ovviamente è 0≤ P(E)≤ 1.

Mentre rimandiamo all’APPENDICE 1.1 per un commento su que-

sta definizione che ha fatto scorrere fiumi di inchiostro negli ultimi 60 anni, definiamo le unità di misura dell’informazione I(E) come:

I fondamenti della teoria 19

1 I(E) = log 2 bit (binary unit) se la base è 2 (1.2) P(E) 1 I(E) = log e nat (natural unit) se la base è e (1.3) P(E) 1 I(E) = log10 Hartley [39] se la base è 10 (1.4) P(E)

dove ovviamente e è la base dei logaritmi naturali e 10 quella dei lo-garitmi decimali. Da ora in poi porremo log 2= log.

Uguagliando (1.4) a (1.2) oppure (1.3) a (1.2) e ponendo rispetti-vamente 1/P(E) uguale a 10 o uguale ad e si ottiene che

1Hartley= 3,22 bit 1nat =1,44 bit

1

Siccome è log a N = log b N , è possibile passare da un’unità di log b a

misura dell’informazione ad un’altra. L’unità di misura più usata è, come si sa, il bit. Dalla definizione,

per P(E)= ½, si ottiene l’importante conseguenza che: si riceve 1 bit di informazione quando ci viene comunicata la realizza-zione di un evento fra due possibili eventi ugualmente probabili ovve-ro riceviamo uno di due possibili messaggi equiprobabili.

E’ fin troppo scontato l’esempio, cui ci riferiremo anche in seguito, di una moneta perfetta che viene lanciata e nella quale la probabilità di uscita di “testa” è identica a quella di “croce” ovvero è pari a ½. Al-trimenti parleremo di moneta truccata. Esistono tuttavia altre unità di misura usate nella pratica informatica che sono multiple del bit .

La principale è 1Byte= 8 bit, scelta anche perché il numero dei Byte distinti, 28 = 256, è dell’ordine di grandezza del numero delle funzioni da poter attivare in un PC. Conseguentemente sono in uso anche suoi multipli come il KiloByte(KB)= 1024 Byte (invece di 1000 poiché

20 Capitolo I

1024 è pari a 210) o il MegaByte (MB) = 106Byte oppure anche il Gi-gaByte (GB) = 109Byte.

A prescindere dall’unità di misura, la quantità di informazione con-tenuta in un messaggio è allora legata all’inverso della probabilità che esso venga inviato ovvero all’incertezza che si ha “a priori” su quale messaggio verrà emesso. Maggiore è questa incertezza maggiore è l’informazione che si riceve poiché la ricezione del messaggio elimina giusto l’incertezza. Insomma l’incremento di informazione recato da un evento coincide con la diminuzione dell’incertezza che si ha a prio-ri sul suo verificarsi. Si può anche dire che un messaggio contiene tan-ta più informazione quanto più è inaspettato, ciò che del resto è intui-tivo. L’incertezza a sua volta è legata alla probabilità a priori e l’insieme delle probabilità che caratterizzano gli eventi connessi ad una certa sorgente di informazione definiranno l’entropia della mede-sima. 1.4 Qualche esempio significativo

Come è noto, nel popolare gioco del SuperEnalotto, viene sorteg-

giata una sestupla di numeri compresi fra 1 e 90. Il numero delle se-stuple possibili è dato dalle combinazioni semplici di 90 oggetti presi 6 alla volta ovvero C90,6= 622614630. Pertanto l’uscita di una sestupla porta un’informazione I(E)= log 622614630 pari a 29,15 bit. Sembre-rebbe una quantità di informazione neanche tanto rilevante rispetto a 1 bit considerato che ora si hanno oltre seicento milioni di possibilità ri-spetto a due. Ma bisogna tener conto della scala logaritmica. Tuttavia non c’è dubbio che il significato o, meglio, l’importanza attribuita ad essa è straordinariamente diverso a seconda che si tratti di un giocato-re che non ha avuto successo o del vincitore di qualche milione di eu-ro.

Nel vecchio “standard americano “ in bianco e nero, un’immagine televisiva è costituita come insieme di tracce elementari, bianche, nere o grigie, mediante l’intersezione di circa 500 righe e 600 colonne sullo schermo TV. Si può supporre che ciascuno di questi 300000 picture element possa assumere 10 livelli di luminosità in modo che vi siano circa 10 300000 possibili immagini televisive. Pertanto una ‘schermata’

I fondamenti della teoria 21

televisiva in bianco e nero porta un’informazione I(E)=3.10log10 bit ≈ 106 bit, ove naturalmente tutte le immagini siano equiprobabili e quin-di con P(E)= 1/(10)300000. Va osservato però che non tutte le immagini sarebbero significative per il teleutente.

E’quello che succede anche nel caso del radiocronista sportivo. Supponiamo che il giornalista della radio abbia a disposizione un vo-cabolario di 10000 parole per descrivere tutti gli accadimenti di una partita e consideriamo una sequenza di 1000 parole di radiocronaca scelte completamente a caso dal vocabolario. Con il solito computo delle Dr

10000,1000 =100001000 abbiamo che ciascuna di queste sequenze ha una probabilità che è l’inverso di questo numero e pertanto porta un’informazione I(E)=1000 log10000 bit ≈ 1,3.104 bit. Anche in que-sto caso una sequenza casuale di 1000 parole può non avere significa-to per l’ascoltatore. Si può tuttavia arguire che, con queste approssi-mazioni, una schermata televisiva in bianco e nero equivale a circa 100 parole dal punto di vista informativo – presumibilmente quelle che occorrerebbero per descrivere l’immagine con il linguaggio verba-le ovvero con il discorso parlato o scritto.

APPENDICE 1: complementi e problemi A1.1 Sulla definizione dell’Informazione e della sua misura

L’informazione di cui si occupa la teoria può essere definita e su questa base si conviene di definirne anche le unità di misura. La defi-nizione, e quindi la teoria, riguardano l’informazione condotta da e-venti di cui è nota la probabilità di verificarsi. Inoltre si prescinde completamente dall’aspetto semantico (significato) dei messaggi per non parlare dell’importanza, del tutto soggettiva, che usualmente gli si attribuisce. Queste tre osservazioni sono sufficienti a marcare la netta differenza esistente fra il significato che bisogna attribuire all’informazione di cui si occupa la teoria e quello che invece connota la stessa parola usata nelle relazioni umane e nei media dell’attuale “società dell’informazione”. Normalmente non è nota la probabilità degli eventi, che quasi sempre, come si dice, non sono matematizzabi-li. Per cui bisogna concludere che l’informazione di cui parla la teoria

22 Capitolo I

ha un significato molto più ristretto di quello attribuito all’informazione comunemente intesa. Anche se non c’è dubbio che le notizie che informano di più sono quelle più improbabili e inattese, pur non potendone precisare la probabilità. Al contrario, non ricevia-mo informazione se non abbiamo alcuna incertezza su un evento – che sia certo, P(E)=1 oppure impossibile, P(E)=0: evitiamo di accendere la radio o la TV per sapere se si è verificato giacché la notizia non ri-muoverebbe alcuna incertezza da parte nostra.

Un altro aspetto interessante riguarda la definizione di I(E) in quan-to tale, dal momento che è legata all’inverso della probabilità dell’evento E e che compare proprio la funzione logaritmo. Intanto c’è da osservare che si sarebbe dovuto porre I(E)= k logb[1/P(E)], con k pari all’informazione ricevuta da un evento di P(E)=1/b. Si è convenu-to invece di porre k=1, naturalmente nell’unità usata.

La definizione è poi ancorata al parametro statisticamente oggetti-vo della probabilità e stabilisce, come già sottolineato, che un messag-gio informa tanto più quanto più è improbabile. Ovviamente bisogna tener conto che interviene il logaritmo e che, quindi, l’informazione cresce ‘lentamente’ al diminuire della probabilità: se quest’ultima di-mezza l’informazione aumenta ‘solo’ di un bit, se diventa un quarto l’informazione aumenta di due bit e così via.

L’ulteriore osservazione riguarda la ragione della comparsa del lo-garitmo nella definizione. Supponiamo che una sorgente sia capace di emettere M messaggi equiprobabili e dunque che ciascun messaggio abbia una probabilità p=(1/M). E’ ragionevole supporre che, se ven-gono emessi due, tre, …,n messaggi, essi debbano contenere due vol-te, tre volte ,…, n volte l’informazione di un messaggio. E infatti, sic-come la probabilità di una n-pla, per il Teorema delle probabilità composte, è P= (1/M)n sostituendo nella (1.2) e ricordando le note proprietà dei logaritmi si ottiene: I(n messaggi) = log Mn = n.I (1 messaggio). Così si giustifica l’introduzione della funzione logaritmica nella defi-nizione che, altrimenti, poteva sembrare del tutto arbitraria.

I fondamenti della teoria 23

A1.2 Problemi proposti A1.2.1 (Unità di misura) Dimostrare che 1 nat = 1,44 bit e che 1 Har-tley = 3,32 bit Soluzione. L’informazione contenuta in un messaggio deve prescinde-re dalla sua unità di misura come del resto avviene per la lunghezza di una strada o la massa di un corpo. Pertanto, dato un evento E che si verifica con probabilità P(E), deve accadere che I(E) = log[1/P(E)] bit = ln[1/P(E)] nat, con ln=loge . Ricordando le definizioni (1.2) e (1.3), se si pone nell’uguaglianza P(E)= 1/e scrivendo il secondo membro al posto del primo, si ottiene 1 nat = (log e) bit= 1,44 bit e quindi 1bit= 0,69 nat, che può anche ottenersi ponendo nell’uguaglianza P(E) = ½. Analogamente si dimostra che 1Hartley = 3,32 bit ovvero che 1 bit = 0,30 Hartley. A1.2.2(Unità di misura)Sviluppare in nat l’espressione (log x+log y) bit in due modi: sulla base dell’uguaglianza dell’informazione e usan-do le formule di passaggio fra logaritmi di basi diverse. A1.2.3(Unità di misura) Esprimere 3.109nat in GigaByte, in MegaBy-te, in KiloByte, in Byte e in bit A1.2.4(SuperEnalotto)Calcolare l’informazione in bit contenuta nei messaggi che comunicano gli eventi: a) fare 5 al SuperEnalotto, b) fa-re 4 al SuperEnalotto, c) fare 3 al SuperEnalotto, sempre giocando una sestupla e confrontare l’informazione di questi messaggi con quella calcolata relativa al fare 6 nello stesso gioco. Soluzione. Si voglia, ad esempio, calcolare l’informazione contenuta nella notizia di aver fatto 3 al SuperEnalotto giocando una sestupla. La probabilità P(3) di questo evento sarà data dalla probabilità di usci-

24 Capitolo I

ta di una sestupla per il numero delle sestuple contenenti 3 dei 6 nu-meri giocati. La probabilità di uscita di una sestupla è già stata calco-lata ed è pari a 1/622614630. Il numero di sestuple contenenti 3 dei 6 numeri giocati è pari a C6,3 – che sono le terne estraibili dalla sestupla giocata – per C87,3 – che sono le terne che possiamo comporre con gli altri 87 numeri. Essendo C6,3= 20 e C87,3= 105995 avremo in definitiva I(3) = log[1/P(3)] =log[ 622614630 /(20.105995)]= 8,18 bit circa 21 bit di informazione in meno rispetto alla notizia che annuncia l’effettuazione di un 6, come era facilmente intuibile. Analogamente si ragiona per il 4 e per il 5. A1.2.5 (SuperEnalotto)Calcolare l’informazione in bit contenuta nel messaggio che comunica l’effettuazione del 5+1 nel gioco del Super-Enalotto giocando una sestupla - uscita di cinque numeri giocati nella sestupla estratta e del sesto giocato come settimo estratto (numero Jolly) - e confrontarla con quella calcolata riguardante il 6. (Risulta-to:26,58bit) A1.2.6 (Totocalcio)Calcolare l’informazione in bit contenuta nei mes-saggi che comunicano l’effettuazione di un 13 o di un 12 al Totocalcio supponendo che ciascuna partita abbia tre possibili risultati equipro-babili. (Suggerimento: nel caso del 13, la probabilità di indovinare il risultato di una partita è 1/3 e pertanto quella di indovinare i risultati di 13 par-tite è (1/3)13…In maniera analoga per il 12). A1.2.7(Schermo TV)Consideriamo ancora il vecchio standard ameri-cano già citato in 1.4, però a colori; supponiamo allora lo schermo te-levisivo diviso in 300000 picture element (500 righe e 600 colonne) con 7 colori più il bianco e 5 variazioni per colore con i soliti 10 livelli di luminosità. Calcolare l’informazione media portata da una scherma-ta TV a colori ammettendo che tutte le immagini siano equiprobabili – anche se non tutte significative per il teleutente.

I fondamenti della teoria 25

Soluzione.Ogni picture element può assumere allora 360 configura-zioni e 300000 pixel alla volta danno luogo ad una delle possibili (360) 300000 schermate, tante quante sono le disposizioni con ripetizio-ne di 360 oggetti presi 300000 alla volta. Se queste sono equiprobabi-li, ciascuna avrà una probabilità di verificarsi pari a 1/(360)300000 e per-tanto porterà un’informazione pari a I(E) = 300000 log 360 bit= 300000.8,47 = 2,54 Mbit ovvero più di due volte e mezzo quella condotta dal bianco e nero. Ovviamente le schermate significative per il teleutente sono molte di meno. A1.2.8 (Lotto)Calcolare l’informazione connessa alla realizzazione di un terno sulla ruota di Firenze nel popolare gioco del Lotto. A1.2.9(Dadi)Considerando un dado non truccato, determinare l’informazione in nat connessa all’uscita del 4. A1.2.10(Dadi)Determinare l’informazione media misurata in bit por-tata dall’uscita di una faccia senza fare alcun calcolo sulla base del problema precedente. A1.2.11(Dadi)Supponiamo di considerare un dado truccato con pro-babilità delle 6 facce così distribuita:p(1)=1/6, p(2)=1/3, p(3)=p(4)=p(5)= 1/12, p(6)=1/4. Determinare l’informazione in bit portata dall’uscita di ciascuna faccia commentando il risultato. Deter-minare anche l’informazione media in bit portata dall’uscita di una faccia. A1.2.13(Moneta)Una moneta è truccata in maniera tale che p(testa)=3/4 e p(croce)=1/4. Determinare l’informazione in bit che si consegue rispettivamente quando esce “testa” e quando esce “croce” nonché l’informazione media conseguita con l’uscita di una faccia. Discutere i risultati.

26 Capitolo I

A1.2.14(Poker) Durante una partita a poker si riceve più informazione quando ci viene servito un poker di regine oppure un “full”di regine con assi? A1.2.15(Poker)Calcolare la differenza di informazione in bit quando si riceve una scala reale servita oppure un colore servito.