METRO, KILOGRAMMO, SECONDO, BIT Breve storia di una grande avventura: lo studio della misura e delle...

METRO, KILOGRAMMO, SECONDO, BITBreve storia di una grande avventura: lo studio della misura e delle

unità di misura

Lunedì 26 aprile 2004

BIT

La misura dell’informazione

Giorgio Goldoni

IL BITLA MISURA

DELL’INFORMAZIONE

bit = binary digit

(numero binario)

1

|

|||| |||| || || || | 1

1 0

||

|||| |||| || || || | 2

1 1

|||

|||| |||| || || || | 3

1 0 0

||||

|||| |||| || || || | 4

1 0 1

|||||

|||| |||| || || || | 5

1 1 0

||||||

|||| |||| || || || | 6

1 1 1

|||||||

|||| |||| || || || | 7

1 0 0 0

||||||||

|||| |||| || || || | 8

1 0 0 1

|||||||||

|||| |||| || || || | 9

1 0 1 0

||||||||||

|||| |||| || || || | 10

1 0 1 1

|||||||||| |

|||| |||| || || || | 11

1 1 0 0

|||||||||| ||

|||| |||| || || || | 12

1 1 0 1

|||||||||| |||

|||| |||| || || || | 13

1 1 1 0

|||||||||| ||||

|||| |||| || || || | 14

1 1 1 1

|||||||||| |||||

|||| |||| || || || | 15

+ 0 10 0 11 1 10

× 0 10 0 01 0 1

byte = sequenza di 8 bit

01100101

310 1010242

kilobyte

1.024 byte

8.192 bit

Megabyte

1.024 kilobyte

1.048.576 byte

8.388.608 bit

Gigabyte

1.024 Megabyte

1.073.741.824 byte

8.589.934.592 bit

binit = binary digit

Codifica binaria a lunghezza fissa

0

1

0 1

00

01

10

11

0 1

0 01 1

000001010011100101110111

0 1

0

0 0

0

0 0

1 1

1 1 1 1

Milano Messina

Sole 25% 50%

Pioggia 25% 25%

Coperto 25% 12,5%

Nebbia 25% 12,5%

messaggio codifica

Sole 00

Pioggia 01

Coperto 10

Nebbia 11

Esempio di codifica:

Sole-Coperto-Coperto-Pioggia:

00-10-10-01

00101001

Esempio di decodifica:

01110001

01-11-00-01

Pioggia-Nebbia-Sole-Pioggia

2 binit per messaggio

Milano Messina

Sole 25% 50%

Pioggia 25% 25%

Coperto 25% 12,5%

Nebbia 25% 12,5%

Codifica binaria a lunghezza variabile

Idea:

codifiche corte per messaggi frequenti

codifiche lunghe per messaggi rari

Messaggio Codifica Frequenza

Sole 1 50%

Pioggia 01 25%

Coperto 001 12,5%

Nebbia 0001 12,5%

Esempio di codifica:

Sole-Sole-Pioggia-Coperto:

1-1-01-001

1101001

Esempio di decodifica:

01110001

01-1-1-0001

Pioggia-Sole-Sole-Nebbia

Su 8 messaggi ce ne sono in media:4 di 1 binit2 di 2 binit1 di 3 binit1 di 4 binit

Lunghezza media di un messaggio

875,18

15

8

41312214

binit

Perché da Messina è possibile inviare messaggi con codifiche più brevi che da Milano?

È possibile ridurre ulteriormente la lunghezza media dei messaggi?

Esiste un limite inferiore alla lunghezza media dei messaggi?

La sequenza di binit usata per la codifica dei possibili messaggi di una sorgente può essere interpretata come una strategia di domande da porre ad un oracolo binario, cioè un essere onnisciente che risponde solo con dei “sì” e con dei “no”, al fine di indovinare un messaggio.

Sole oPioggia?

Sole?

sì no

Coperto?sì sìno no

Sole Pioggia Coperto Nebbia

Strategia ottimale per Milano

Sempre 2 domande per messaggio

sì no

sì

sì

no

no

Sole?

Sole Pioggia?

Pioggia Coperto?

Coperto Nebbia

Strategia ottimale per Messina

In media 1,75 domande per messaggio

Su 8 volte:4 volte 1 domanda2 volte 2 domande2 volte 3 domande


Sole 1 50%

Pioggia 01 25%

Coperto 001 12,5%

Nebbia 0001 12,5%


Sole 1 50%

Pioggia 01 25%

Coperto 001 12,5%

Nebbia 000 12,5%

sì no

sì

sì

no

no

Sole?

Sole Pioggia?

Pioggia Coperto?

Coperto Nebbia

Strategia non ottimale per Milano

In media 2,25 domande per messaggio

Su 4 volte:1 volta 1 domanda1 volta 2 domande2 volte 3 domande

Studio del caso di n messaggi

equiprobabili

0

1

0 1

00

01

10

11

0 1

0 01 1

000001010011100101110111

0 1

0

0 0

0

0 0

1 1

1 1 1 1

n 2n

1 2

2 4

3 8

4 16

5 32

6 64

log2m m

1 2

2 4

3 8

4 16

5 32

… …

× 2+ 1

1 2

2 4

3 8

4 16

5 32

… …

: 2- 1

… …

-3 0,125

-2 0,25

-1 0,5

0 1

1 2

2 4

3 8

4 16

5 32

… …

: 2- 1

+1 = +0,5 +0,5

×2 = ×1,4142 ×1,4142

… …

-2 0,25

-1,5 0,3536

-1 0,5

-0,5 0,7071

0 1

0,5 1,4142

1 2

1,5 2,8284

2 4

… …

×1,4142+ 0,5

+0,5 = +0,25 +0,25

×1,4142 =

×1,1892 ×1,1892

… …

-1 0,5

-0,75 0,5946

-0,5 0,7071

-0,25 0,8409

0 1

0,25 1,1892

0,5 1,4142

0,75 1,6818

1 2

… …

×1,1892+ 0,25

1 2 3 4 5 6 7 8

1

2

3

823

58496,13log2

32 58496,1

?

Strategia per indovinare uno di tre messaggi equiprobabili

1 domanda 1/3 delle volte

2 domande 2/3 delle volte

Media domande:

6667,13

52

3

21

3

1

3 messaggi:

A B C

9 coppie di messaggi:

AA AB AC BA BB BC CA CB CC

3 domande 7/9 delle volte4 domande 2/9 delle volte

Media domande:

2222,39

294

9

23

9

7

6111,12:2222,3

per 2 messaggi

per messaggio

27 terne di messaggi:

AAA AAB AAC ABA ABB ABC

ACA ACB ACC BAA BAB BAC

BBA BBB BBA BCA BCB BCC

CAA CAB CAC CBA CBB CBC

CCA CCB CCC

4 domande 5/27 delle volte5 domande 22/27 delle volteMedia domande:

8148,427

1305

27

224

27

5

6049,13:8148,4

3 messaggi

per messaggio

quaterne di messaggi.76 212881642

8134

176481

Ci sono

Essendo occorronodalle 6 alle 7 domande per indovinare una quaterna di messaggi.

per cui in 34 casi occorre fare 7

domande e 6 domande nei rimanenti 47 casi.

4198,681

5206

81

477

81

34

6049,14:4198,6

Gruppi di 5 messaggi: 24335 87 22562431282

115128243 2301152 13230243

Media domande:

9465,7243

19317

243

138

243

230

5893,15:9465,7

Per indovinare 1 tra n messaggi equiprobabili è possibile usare una

strategia il cui numero medio di domande per messaggio da formulare

a un oracolo binario si avvicini a piacere al valore

n2log

Analogamente è possibile codificare gli n messaggi equiprobabili usando

un numero medio di binit per messaggio che si avvicina a piacere al

valore

n2log

np

1

pn

1loglog 22

Probabilità di ciascun messaggio:

Limite inferiore al numero medio di domande da porre all’oracolo binario

per indovinare il messaggio:

Più in generale affermiamo che il verificarsi di un evento casuale

di probabilità p fornisce un’informazione di

p

1log2 bit

La quantità di informazione è tanto maggiore quanto più

l’evento è raro.

Un evento certo fornisce una quantità nulla di informazione.

SORGENTE DI INFORMAZIONESENZA MEMORIA

Trasmette n tipi di messaggi diversi, ciascuno indipendente dal precedente, e con una determinata probabilità.

nn p

pp

pp

pH1

log...1

log1

log 22

221

21

ENTROPIA DI INFORMAZIONE

Quantità media di informazione

ricevuta da un messaggio

L’entropia di informazione rappresenta il limite inferiore,

approssimabile a piacere, del numero medio di domande da porre ad un oracolo binario per indovinare il

messaggio trasmesso dalla sorgente o, equivalentemente, il limite inferiore,

approssimabile a piacere, del numero medio di binit per codificare un

messaggio.

Stazione meteorologica di Milano

bitH 24log2

Messaggio Probabilità

Sole 1/4

Pioggia 1/4

Coperto 1/4

Nebbia 1/4

Stazione meteorologica di Messina

bit

H

75,14

73

8

13

8

12

4

11

2

1

8log8

18log

8

14log

4

12log

2

12222

Messaggio Probabilità

Sole 1/2

Pioggia 1/4

Coperto 1/8

Nebbia 1/8

Quando, per la stazione meteorologica di Messina,

utilizziamo una codifica di 2 binit per messaggio, ogni binit non trasporta

un bit di informazione, ma

bit875,02:75,1

con un rendimento dell’87,5% e una ridondanza del 12,5%.

UN BINIT TRASPORTA AL MASSIMO UN BIT DI

INFORMAZIONE

Claude E. Shannon

(1916 – 2001)

DDDBDB

DDDBDBS

DDDBDBSS

DDDBDBSSA

DDDBDBSSAS

DDDBDBSSASS

DDDBDBSSASSA

Spostamento Codifica

Destra 00

Sinistra 01

Alto 10

Basso 11

D D D B D B S S A S S A

00 00 00 11 00 11 01 01 10 01 01 10

000000110011010110010110


00 00 00 11 00 10 01 01 10 01 01 10

000000110010010110010110

D D D B D A S S A S S A

00 00 00 11 00 10 01 01 10 01 01 10

000000110010010110010110


00 00 00 11 00 11 01 01 10 01 01 10

000000110011010110010110

Idea:

1. Eliminare tutta la ridondanza, ricorrendo ad una codifica idealmente coincidente con l’entropia di informazione

2. Aggiungere una ridondanza “organizzata” per proteggere il messaggio dal rumore

Ogni m binit di messaggio aggiungo c binit di controllo. I c binit di controllo possono assumere 2c configurazioni diverse, le quali

devono poter indicare quale degli

m + c binit è stato ricevuto in modo errato oppure se il messaggio non

contiene errori.

12 cmc

Con c binit di controllo posso tentare di proteggere un messaggio di lunghezza

12 cm c

1 0

2 1

3 4

4 11

12 cm cc

Sole-Sole-Pioggia

1-1-01

1101

1101 1

1

10

1 0

0

100

1001 1

0

10

1 0

0

100

1101 1

1

10

1 0

0

100

1101 1

1

10

1 1

0

110

1101 1

1

10

1 0

0

100

Richard W. Hamming

(1915 – 1998)

www.itisvinci.com

METRO, KILOGRAMMO, SECONDO, BIT Breve storia di una grande avventura: lo studio della misura e delle...

Documents

Transcript of METRO, KILOGRAMMO, SECONDO, BIT Breve storia di una grande avventura: lo studio della misura e delle...