METRO, KILOGRAMMO, SECONDO, BIT
Breve 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 BIT
LA 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
1
0 1
0 1
1 10
×
0
1
0
0
0
1
0
1
byte = sequenza di 8 bit
01100101
2  1024  10
10
3
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
0
00
1
01
0
1
0
1
10
11
0
0
0
1
1
1 0
0
1 0
1
1 0
1
000
001
010
011
100
101
110
111
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 binit
2 di 2 binit
1 di 3 binit
1 di 4 binit
Lunghezza media di un messaggio
4 1  2  2  1 3  1 4 15
  1,875 binit
8
8
 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.
Strategia ottimale per Milano
sì
sì
Sole
Sole?
Sole o
Pioggia?
no
Pioggia
no
sì
Coperto?
Coperto
no
Nebbia
Sempre 2 domande per messaggio
Strategia ottimale per Messina
Su 8 volte:
sì
no
Sole?
4 volte 1 domanda
2 volte 2 domande
no
sì
Sole
Pioggia?
2 volte 3 domande
Pioggia
sì
Coperto
Coperto?
no
Nebbia
In media 1,75 domande per messaggio
Messaggio Codifica Frequenza
Sole
1
50%
Pioggia
01
25%
Coperto
001
12,5%
Nebbia
0001
12,5%
Messaggio Codifica Frequenza
Sole
1
50%
Pioggia
01
25%
Coperto
001
12,5%
Nebbia
000
12,5%
Strategia non ottimale per Milano
Su 4 volte:
sì
no
Sole?
1 volta 1 domanda
1 volta 2 domande
no
sì
Sole
Pioggia?
2 volte 3 domande
Pioggia
sì
Coperto
Coperto?
no
Nebbia
In media 2,25 domande per messaggio
Studio del caso di n
messaggi
equiprobabili
0
1
0
1
0
00
1
01
0
1
0
1
10
11
0
0
0
1
1
1 0
0
1 0
1
1 0
1
000
001
010
011
100
101
110
111
n
1
2
3
4
5
6
log2m
2n
2
4
8
16
32
64
m
+1
1
2
3
4
5
…
2
4
8
16
32
…
×2
-1
1
2
3
4
5
…
2
4
8
16
32
…
:2
-1
…
-3
-2
-1
0
1
2
3
4
5
…
…
0,125
0,25
0,5
1
2
4
8
16
32
…
:2
+1 = +0,5 +0,5
×2 = ×1,4142 ×1,4142
+ 0,5
…
-2
-1,5
-1
-0,5
0
0,5
1
1,5
2
…
…
0,25
0,3536
0,5
0,7071
1
1,4142
2
2,8284
4
…
×1,4142
+0,5 = +0,25 +0,25
×1,4142 =
×1,1892 ×1,1892
+ 0,25
…
-1
-0,75
-0,5
-0,25
0
0,25
0,5
0,75
1
…
…
0,5
0,5946
0,7071
0,8409
1
1,1892
1,4142
1,6818
2
…
×1,1892
2 8
3
1
2
3
1
2
3
4 5
6
7
8
2
3
log 2 3  1,58496
1, 58496
?
Strategia per indovinare uno di tre
messaggi equiprobabili
1 domanda 1/3 delle volte
2 domande 2/3 delle volte
Media
1
2
5
1   2   1,6667
domande: 3
3
3
3 messaggi:
A B C
9 coppie di messaggi:
AA AB AC BA BB BC CA CB CC
3 domande 7/9 delle volte
4 domande 2/9 delle volte
Media domande:
7
2
29
3  4 
 3,2222 per 2 messaggi
9
9
9
3,2222 : 2  1,6111 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 volte
5 domande 22/27 delle volte
Media domande:
5
22
130
4  5 
 4,8148
27
27
27
4,8148 : 3  1,6049
3 messaggi
per messaggio
Ci sono 3  81 quaterne di messaggi.
Essendo 26  64  81  128  27 occorrono
dalle 6 alle 7 domande per indovinare una
quaterna di messaggi.
81  64  17 per cui in 34 casi occorre fare 7
domande e 6 domande nei rimanenti 47 casi.
34
47
520
7  6 
 6,4198
81
81
81
4
6,4198 : 4  1,6049
Gruppi di 5 messaggi: 3  243
5
2  128  243  256  2
7
243 128  115
8
2 115  230
243  230  13
Media domande:
230
13
1931
8 
7 
 7,9465
243
243
243
7,9465 : 5  1,5893
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
log 2 n
Analogamente è possibile codificare
gli n messaggi equiprobabili usando
un numero medio di binit per
messaggio che si avvicina a piacere al
valore
log 2 n
Probabilità di ciascun messaggio:
1
p
n
Limite inferiore al numero medio di
domande da porre all’oracolo binario
per indovinare il messaggio:
1
log 2 n  log 2
p
Più in generale affermiamo che
il verificarsi di un evento casuale
di probabilità p fornisce
un’informazione di
1
log 2
p
bit
La quantità di informazione è
tanto maggiore quanto più
l’evento è raro.
Un evento certo fornisce una
quantità nulla di informazione.
SORGENTE DI INFORMAZIONE
SENZA MEMORIA
Trasmette n tipi di messaggi diversi,
ciascuno indipendente dal precedente,
e con una determinata probabilità.
ENTROPIA DI INFORMAZIONE
Quantità media di informazione
ricevuta da un messaggio
1
1
1
H  p1 log 2  p2 log 2  ...  pn log 2
p1
p2
pn
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
Messaggio
Sole
Pioggia
Coperto
Nebbia
Probabilità
1/4
1/4
1/4
1/4
H  log 2 4  2 bit
Stazione meteorologica di Messina
Messaggio
Probabilità
Sole
1/2
Pioggia
1/4
Coperto
1/8
Nebbia
1/8
1
1
1
1
H  log 2 2  log 2 4  log 2 8  log 2 8 
2
4
8
8
1
1
1
1
7
 1   2   3   3   1,75 bit
2
4
8
8
4
Quando, per la stazione
meteorologica di Messina,
utilizziamo una codifica di 2 binit per
messaggio, ogni binit non trasporta
un bit di informazione, ma
1,75 : 2  0,875 bit
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)
D
DD
DDD
DDDB
DDDBD
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
D D D B D B S S A S S A
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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.
2  m  c 1
c
Con c binit di controllo posso tentare
di proteggere un messaggio di
lunghezza
m  2  c 1
c
c
m  2  c 1
1
0
2
1
3
4
4
11
c
c
m  2  c 1
1
0
2
1
3
4
4
11
c
Sole-Sole-Pioggia
1-1-01
1101
1
1101 100
1
1
1
0
0
0
1
1001 100
1
0
1
0
0
0
1
1001 100
1
0
1
0
0
0
1
1001 100
1
0
1
0
0
0
1
1001 100
1
0
1
0
0
0
1
1001 100
1
0
1
0
0
0
1
1001 100
1
0
1
0
0
0
1
1001 100
1
0
1
0
0
0
1
1101 100
1
1
1
0
0
0
1
1101 100
1
1
1
0
0
0
1
1101 110
1
1
1
0
1
0
1
1101 110
1
1
1
0
1
0
1
1101 110
1
1
1
0
1
0
1
1101 110
1
1
1
0
1
0
1
1101 110
1
1
1
0
1
0
1
1101 110
1
1
1
0
1
0
1
1101 110
1
1
1
0
1
0
1
1101 100
1
1
1
0
0
0
Richard W. Hamming
(1915 – 1998)
www.itisvinci.com