Andrea G. B. Tettamanzi, 2001
Teoria dell’Informazione (Classica)Teoria dell’Informazione (Classica)
Andrea G. B. Tettamanzi
Università degli Studi di Milano
Dipartimento di Tecnologie dell’Informazione
Andrea G. B. Tettamanzi, 2001
Lezione 1
3 ottobre 2002
Andrea G. B. Tettamanzi, 2001
Programma del Corso
• Che cos’è l’Informazione e che cos’è la T.I.• Richiami di Teoria della Probabilità• Proprietà matematiche utilizzate nella T.I.• Misura dell’informazione: l’Entropia.• Codici• Comunicazione in presenza di rumore• Codici a correzione d’errore• Cenni sulla Teoria della Trasmissione• Cenni di Crittografia
Andrea G. B. Tettamanzi, 2001
Bibliografia
• E. ANGELERI: Informazione: significato e universalità, UTET, Torino, 2000. (libro di testo)
• J. VAN DER LUBBE: Information Theory, Cambridge University Press, 1988.
• J. R. PIERCE: An Introduction to Information Theory, Dover, 1980.
Andrea G. B. Tettamanzi, 2001
Ricevimento Studenti
• Giovedì, dalle ore 14.00 alle ore 16.00• Per appuntamento:
– e-mail: [email protected]
– tel.: 03 73 89 82 48
• Sito del corso: “http://mago.crema.unimi.it/Classes/TIC”
Andrea G. B. Tettamanzi, 2001
Modalità di Esame
• Scritto: 3 o 4 esercizi che coprono vari argomenti del corso.– Temi d’esame degli scritti degli anni passati, completi di correzione,
disponibili all’URL: “http://mago.crema.unimi.it/Classes/TIC/Temidesame”
• Orale: interrogazione su definizioni, enunciati di teoremi e alcune dimostrazioni, rielaborazione critica del materiale presentato a lezione.
Andrea G. B. Tettamanzi, 2001
Che Cos’è l’Informazione?
SINTASSI
SEMANTICA
PRAGMATICA
Andrea G. B. Tettamanzi, 2001
significato
Informazione
informazione
apparatosimbolico
Rilevanza pratica dell’informazione (effetto, scopo, ecc.)
Andrea G. B. Tettamanzi, 2001
Informazione - semantica
• La quantità di informazione di un enunciato è tanto più grande quante più sono le alternative che esso esclude.
UA B
Andrea G. B. Tettamanzi, 2001
Che cos’è la Teoria dell’Informazione?
• Una teoria matematica dell’aspetto simbolico dell’Informazione• Un approccio quantitativo alla nozione di Informazione• Risponde alle domande:
– Come immagazzinare e trasmettere informazione in modo compatto? (compressione)
– Qual’è la massima quantità di informazione che può essere trasmessa su un canale? (velocità di trasmissione)
– Come posso proteggere la mia informazione:
• dalla corruzione del suo supporto o da errori di trasmissione?
• da sguardi indiscreti?
Andrea G. B. Tettamanzi, 2001
Compressione
Immagazzinamento = Trasmissione
scrittura
lettura
t0
t1
invio ricezione
x0 x1
Andrea G. B. Tettamanzi, 2001
Funzioni convesse
)()()( 2121 xxfxfxf
0,
1
Diseguaglianza fondamentale:
1ln xx1ln
log b
xxb
Andrea G. B. Tettamanzi, 2001
Convessità del valore atteso
convessa
concava
)(Xg ])[()]([ XEgXgE
)(Xg ])[()]([ XEgXgE
Andrea G. B. Tettamanzi, 2001
Misura dell’Informazione
R. V. L. Hartley Alfabeto di s simboli
C I A O M M MA A, !
1 2 l
Messaggi possibilils
slssH ll loglog)( R. Hartley
)()( 1slHsH l Perché il logaritmo? Perché così
Andrea G. B. Tettamanzi, 2001
Unità di misura dell’Informazione
A A 2
1)()( APAP
La quantità di informazione che permette di distinguere unodi due eventi equiprobabili e mutuamente esclusivi è l’unitàdi misura dell’informazione: il bit.
Un simbolo di un alfabeto di s simboli equiprobabili porteràun’informazione di
s2log bit
Andrea G. B. Tettamanzi, 2001
Entropia informativa di Shannon
n
iii xPxPXH
1
)(log)()(
continua
simmetrica (commutativa)
additiva )()(),( YHXHYXH
Andrea G. B. Tettamanzi, 2001
Massimo dell’Entropia
nXH log)(
n
i
n
i iiii np
pnppnXH1 1
1loglogloglog)(
0log)11(
log1
log11
111
e
epn
enp
pn
ii
n
i
n
i ii
ab
ba log
1log N.B.:
Andrea G. B. Tettamanzi, 2001
Entropia delle lingue
testo
)Z""(
)A""(
P
P
Frequenzedei simboli
Z""
A""2 )P(
1)logP()testo(
H
Andrea G. B. Tettamanzi, 2001
Ridondanza
1R Efficienza di codificaM
XH
2log
)(
056,4)en(
046,4)de(
896,3)fr(
956,3)it(
H
H
H
H
853,0)en(
850,0)de(
839,0)fr(
887,0)it(
Andrea G. B. Tettamanzi, 2001
Informazione secondo KolmogorovMisura assoluta, non utilizza la probabilità
X Y
xyD )(
x y
descrizionioggetti
yxKxyD
)(
min)(
fn.parzialericorsiva
Andrea G. B. Tettamanzi, 2001
Equivalenza con entropia di Shannon
kkxKx 2)(:
cnXHxKxpXH n
x
nnn
n
log2)()()()(
)()( XnHXH n
)()(
lim XHn
xK n
n
Andrea G. B. Tettamanzi, 2001
Lezione 2
8 ottobre 2002
Andrea G. B. Tettamanzi, 2001
Assiomi dell’entropia (1)),,,( 21 npppH Misura d’incertezza,
max con eventi equiprobabili
),,,(),,,( )()2()1(21 nn pppHpppH
1
2
3 0),,,( 21 npppH
4 )0,,,,(),,,( 2121 nn pppHpppH
(simmetrica)
Andrea G. B. Tettamanzi, 2001
Assiomi dell’entropia (2)
5 )1
1,,
1
1,
1
1()
1,,
1,
1(
nnnH
nnnH
6 continua
7 ),,(),,(),,( 1111 nnnn qpqpHqqHppH
8
),,(),,(),(
),,,,,(
11
11
q
q
q
qqH
p
p
p
ppHqpH
qqppH
nn
nn
(diramazione)
Andrea G. B. Tettamanzi, 2001
Teorema
0
log),,(1
1
k
ppkppHn
iiin
Se H soddisfa gli otto assiomi,
Basterebbero 4 assiomi “minimali”:- continuità;- simmetria;- proprietà di diramazione
- H(1/2, 1/2) = 1
Andrea G. B. Tettamanzi, 2001
Modello della comunicazione
sorgente destinazione
rumore
canale
Andrea G. B. Tettamanzi, 2001
Modello dettagliatoSorgente di
informazioneDestinazione
riduzione ricostruzione
Codificasorgente
cifratura
Decodificasorgente
decifrazione
Codificacanale
Decodificacanale
modulazione demodulazioneCanale continuo
distorsione(rumore)
Canale discreto
Andrea G. B. Tettamanzi, 2001
Sorgente discreta senza memoria
)(,),(),()(
,,,
:
21
21
n
n
i
xpxpxpXP
xxxX
ZitT
n
iixp
1
1)(
S è un dispositivo che genera ad ogni istante t un simbolo x con
probabilità p(x), i.i.d.
P
X
xpxpxp
xxxS
n
n
)()()( 21
21
Andrea G. B. Tettamanzi, 2001
Proprietà
1
011 )()(
110
r
jijkiiirkkk jr
xXPxxxXXXP
Indipendenza statistica e stazionarietà:
)(
1log)(
ii xp
xI autoinformazione
Andrea G. B. Tettamanzi, 2001
Il concetto di codice
Alfabeto sorgente
Alfabeto del codice
NsssS ,,, 21
nxxxX ,,, 21 nN
*Sz
*Xw
**:cod XS
)cod(zw
)(cod 1 wz
Andrea G. B. Tettamanzi, 2001
Esempio: codifica delle cifre decimali
Cifradecimale
Rappresentazionebinaria
0123456789
0000000100100011010001010110011110001001
Andrea G. B. Tettamanzi, 2001
Estensione di una sorgente
Alfabeto base
Alfabeto esteso
nxxxX ,,, 21
m
nnn
m
m xxxxxxX ,,111
Andrea G. B. Tettamanzi, 2001
Teorema
Data una sorgente senza memoria, )()( XmHXH m
Dimostrazione:
)(
1log)()(
111
1
mi mmi
m
iiXx Xxii
m
xxpxxpXH
Xx ii
iiXx Xxii
i
mi mmi
m
XmHxp
xpm
xpxpxpxp
)()(
1log)(
)()(
1log)()(
111
1
Andrea G. B. Tettamanzi, 2001
Nel caso X = {0, 1}
}1,0{21
log1
log2
1log
1log2
1log
1log2
1log
1log
1log
1log2
1log2
1log
1log2
1log2
1log
1log
1log
1log}1,0{
11
00
101
1100
0
2110
110
20
0
1
21
110
010
0
20
1
21
1010
0
20
1111
0101
1010
0000
2
Hp
pp
p
ppp
pppp
p
pppp
pppp
pp
ppp
ppp
pp
pp
pppp
pp
pppp
pppp
pppp
ppppH
Andrea G. B. Tettamanzi, 2001
Lezione 3
14 ottobre 2002
Andrea G. B. Tettamanzi, 2001
Classificazione dei codici
A blocco
Singolare Non singolare
Unicamentedecodificabile
Non unicamentedecodificabile
Istantaneo Non istantaneo
Andrea G. B. Tettamanzi, 2001
Esempi
Non unicamentedecodificabile:
01
00
11
0
4
3
2
1
s
s
s
s
Non istantaneo:
0110
0111
01
0
4
3
2
1
s
s
s
s
Andrea G. B. Tettamanzi, 2001
Codici a prefisso
Condizione necessaria e sufficiente perché un codicesia istantaneo è che nessuna parola del codice sia unprefisso di un’altra parola del codice.
0
1
1
1
0
0
Andrea G. B. Tettamanzi, 2001
Diseguaglianza di Kraft
Condizione necessaria e sufficiente perché esista uncodice istantaneo con lunghezze di parola
è che
qlll ,,, 21
11
q
i
lir
Andrea G. B. Tettamanzi, 2001
Dimostrazione - sufficienza
Costruiamo un codice istantaneo che soddisfa 11
q
i
lir
qnl
ll
max
1
1max
1
l
l
llrnmax
max
max
1
ll
l
lll rrn
rnrnrn lll
l 11
1 max
maxmax
max
rn
rnrn
rnrnrn lll
l
1
12
2
22
11
1 max
maxmax
max
Andrea G. B. Tettamanzi, 2001
Teorema di McMillan
Un codice unicamente decodificabile soddisfa la diseguaglianza di Kraft
nlll
nq
i
l qi rrrr
21
1
nii llk 1
kllrr nii
1
Sviluppando la potenza, avremo qn termini della forma
maxnlkn
maxmax1
1maxmax
nlnnlrrrNrnl
nk
kknl
nk
kk
nq
i
li
kk rN ma allora deve essere 1
1
q
i
lir
1n
Andrea G. B. Tettamanzi, 2001
Teorema di codifica della sorgente
)(SHl r
n
iii pll
1
Sia la lunghezza media di un codice istantaneo
a r simboli. Allora,
ilir rpiSHl :)(
Andrea G. B. Tettamanzi, 2001
Dimostrazione
n
i
lri
n
i iri
n
iii
n
i irir
irpp
pplp
plSH1111
log1
log1
log)(
n
i
li
i
n
il
iri
n
i i
l
ri r
rpp
rpp
p
rp
i
i
i
111 ln
1ln
1loglog
01ln
11
1
ln
1
11
n
i
ln
il
ii
i
ir
rrpp
r
KraftProprietà fondamentale dei logaritmi
Andrea G. B. Tettamanzi, 2001
Lezione 4
21 ottobre 2002
Andrea G. B. Tettamanzi, 2001
Processi Stocastici
X t t( )
, ,
0 1
Un processo stocastico è una successione di v.a.
,,,, 21 tXXX
Ciascuna con la propria distribuzione di probabilità.
Notazione:
Andrea G. B. Tettamanzi, 2001
Catene di Markov
X t t( )
, ,
0 1Un processo stocastico
è una catena di Markov sse il suo stato dipende solo dallo
stato precedente, cioè, per ogni t,
P X x X X X P X x Xt t t t[ | , , , ] [ | ] 0 1 1 1
A B C
0.4
0.6
0.3
0.7
0.25
0.75
Andrea G. B. Tettamanzi, 2001
Processi Markoviani
X t t( )
, ,
0 1
],,,|[
],,,|[
21
110
mtttt
tt
XXXxXP
XXXxXP
È un processo Markoviano di ordine m sse
Andrea G. B. Tettamanzi, 2001
Sorgente discreta con memoria
)](,),1(|)([)(
,,,
:
21
mtxtxtxPXP
xxxX
ZitT
i
n
i
S è un dispositivo che genera ad ogni istante t un simbolo x con
probabilità condizionata dagli m simboli generati in precedenza
Stazionarietà: le probabilità sono costanti nel tempo
Andrea G. B. Tettamanzi, 2001
Informazione e Entropia condizionali
)|(
1log)|(
21
21
m
m
jjjijjji xxxxp
xxxxI
Informazione condizionale:
)|(
1log)|()|(
21
21211 m
mm
jjji
n
ijjjijjj xxxxp
xxxxpxxxXH
Entropia condizionale:
Andrea G. B. Tettamanzi, 2001
Proprietà dell’Entropia condizionale
)()|( YHXYH
0loglog)|(log)(log
1)|(
)()|(log
)|(
)(log)|(
)(log)()|(
1log)|(
)()|(
1 11 1
1 11 1
11 1
eexypeype
xyp
ypxype
xyp
ypxyp
ypypxyp
xyp
YHXYH
X
i
Y
jij
X
i
Y
jj
X
i
Y
j ij
jij
X
i
Y
j ij
jij
Y
jjj
X
i
Y
j ijij
Dimostrazione:
X
iji yxp
1
1)|(
Andrea G. B. Tettamanzi, 2001
Struttura statistica delle lingue
testo
)Z""(
)A""(
P
P
Distribuzionea memoria 0:
)Z"|"Z""(
)B"|"A""(
)A"|"A""(
P
P
P
Distribuzionea memoria 1:
Andrea G. B. Tettamanzi, 2001
Frequenze statistiche dell’italiano_ A E I O U N T R L C S D P M G V H F B Z Q
1583 988 945 863 849 255 684 670 539 512 395 376 303 202 193 174 120 93 82 72 72 30_ 343 381 281 343 3 48 9 27 122 3 24A 166 12 79 12 42 130 106 64 73 39 51 33 48 9 45 24 6 21 24E 94 36 27 98 134 91 82 23 61 101 48 39 21 30 42 3 9 6I 133 12 12 15 55 106 91 67 70 36 91 24 40 21 24 15 21 3 27O 42 42 36 121 112 62 46 142 61 27 36 33 21 9 12 27 12 3U 27 3 24 21 39 6 12 9 24 9 12 15 3 6 6 30N 88 148 97 95 160 36 18 18 24T 91 142 18 70 24 27 106 76 30 21 65R 52 54 128 12 124 33 64 12 3 27 6 6 12 6L 91 88 83 45 45 9 6 98 7 30 4 6C 163 18 6 61 12 3 33 33 15 51S 133 33 76 34 40 12 15 12 21D 164 9 42 12 6 64 6P 103 15 15 6 17 9 6 9 15 12M 49 33 27 15 36 9 21 3G 30 39 33 9 15 9 21 18V 21 24 18 21 18 6 6 3 3H 27 60 9F 55 3 6 12 3 3B 24 6 6 3 6 18 9Z 18 3 12 3 21 3 12Q 30 3 3 3
Andrea G. B. Tettamanzi, 2001
Approssimazioni
Memoria 0:E A IDAVEAPDIAOSPTRR OMR ELRROULEETDP AOOEPVUNCNCM AALPNESCIESI ...
Memoria 1:NFA EGI SSISA LE LERA SCHELA CILU GGILLE PRAPRANA ...
Memoria 2:OR IL SARSERA NE HAI GUE E LAMASSETTERRA DO E LASE AL MILA ...
Memoria 3:
Andrea G. B. Tettamanzi, 2001
Stima dell’Entropia con memoria infinita
00.5
1
1.52
2.53
3.54
4.5
1 10 100
Memoria
Entropia
Esperimento di Shannon)(
1log)(
1lim
xPxP
nH
nxn
Andrea G. B. Tettamanzi, 2001
Entropia nelle sorgenti con Memoria
n
j
n
j
n
j jjjijjji
m m
m
m
xxxxpxxxxp
XH
1 1 11 2 21
21 )|(
1log)|(
)(
1
21
21 )|(
1log),,,,(
mm
m
X jjjijjji xxxxp
xxxxp
Andrea G. B. Tettamanzi, 2001
Teorema
)()()()(10 m
XHXHXHXH
L’entropia di una sorgente con memoria è tanto minore quantomaggiore è l’ordine della memoria.
Andrea G. B. Tettamanzi, 2001
Dimostrazione(Per semplicità, solo nel caso a memoria di ordine 1)
n
i
n
j ijji xxp
xxpXXHXH1 1 12
2112 )|(
1log),()|()(
1
)()()|()(),( 2112121 XHXHXXHXHXXH
Inoltre,
)()()()|()(01 212 XHXHXHXXHXH
Andrea G. B. Tettamanzi, 2001
Lezione 5
24 ottobre 2002
Andrea G. B. Tettamanzi, 2001
Codici ottimali con probabilità note a priori
Osservazione: in un codice C ottimale, jiji llpp Dimostrazione: si supponga di scambiare le due parole in questione
))((
''11
ijji
jjiiijji
n
kkk
n
kkk
llpp
lplplplplplpll
Siccome C è ottimale, ll ' quindi deve essere per forza
0 ij ll c.v.d.
Andrea G. B. Tettamanzi, 2001
Codici ottimali con probabilità note a priori
Osservazione: in un codice istantaneo C ottimale a base r,
le r parole più lunghe hanno la stessa lunghezza.
Dimostrazione: se così non fosse, potrei sopprimere l’ultimaparte delle parole più lunghe senza perdere la proprietà di prefissoe ottenendo un codice migliore (assurdo).
Andrea G. B. Tettamanzi, 2001
Codici ottimali con probabilità note a priori
Osservazione: in un codice istantaneo C ottimale a base r,
le r parole più lunghe sono associate agli r simboli sorgentemeno probabili e differiscono solo per l’ultimo simbolo.
Dimostrazione: per
1p
2p
3p
4p
0
0
0
0
1
1
1
1p
2p
3p
4p
0
0
01
1
1
2r
Andrea G. B. Tettamanzi, 2001
Codice di Fano
• Ordinare i simboli sorgente in ordine di probabilità decrescente
• Dividere al meglio i simboli in r gruppi equiprobabili
• Assegnare a ciascun gruppo uno degli r simboli come prefisso
• Ripetere la divisione per gruppi in modo ricorsivo finché possibile
Andrea G. B. Tettamanzi, 2001
Esempio
simbolo probabilità codice
0123456789
1/41/41/81/81/161/161/321/321/321/32
00011001011100110111100111011111011111
Andrea G. B. Tettamanzi, 2001
Codice di Shannon
Calcolare le probabilità cumulative
1
1
)(k
iik sPP
Scriverle in notazione r-aria
Il numero di simboli per parola di codice è dato da
1)(
1log
)(
1log
ii
i sPl
sP
)(
1log
ii sP
lcioè
Andrea G. B. Tettamanzi, 2001
Esempio
simbolo probabilità prob. Cum. lunghezza codice
0123456789
1/41/41/81/81/161/161/321/321/321/32
01/41/25/83/413/167/829/3215/1631/32
2233445555
00011001011100110111100111011111011111
Andrea G. B. Tettamanzi, 2001
Codice di Huffman
• Ordinare i simboli sorgente per probabilità decrescente
• Raggruppare gli r simboli meno probabili e considerarli come un solo simbolo
• Ripetere il raggruppamento finché possibile
• Restano al massimo r simboli o gruppi di simboli
• Assegnare uno degli r simboli a ciascuno dei gruppi come prefisso
• Svolgere i gruppi all’indietro ripetendo l’assegnamento del prefisso finché tutti i simboli sorgente hanno una parola di codice associata
Andrea G. B. Tettamanzi, 2001
Esempio
simbolo probabilità
012345
0.40.30.10.10.060.04
01
0.40.30.10.10.1
01
0.40.30.20.1
01
0.40.30.3
01
0.60.4
01
10001101000101001011
codice
Andrea G. B. Tettamanzi, 2001
Ottimalità del codice di Huffman
nn sssC ,,, 11 ',,,' 21 sssC n nn sss 1'
nnnn
n
iii
nnnn
n
iii
pplpplp
lplplpl
11
1
1
111
2
1
')('
)1'()1'('
Andrea G. B. Tettamanzi, 2001
Codice alfabetico (o di Gilbert-Moore)
Ordinare i simboli sorgente secondo qualche criterio
La lunghezza di ciascuna parola di codice è data da
ii li
l sP 21 2)(2
Determinare la sequenza
).(2
1)()(
),(2
1)(
),(2
1
11
212
11
nnn sPsPsP
sPsP
sP
10 21 n
Rappresentare in base rciascuno di questi numerisecondo la lunghezzacalcolata
cioè
1
)(
1log
ii sP
l
Andrea G. B. Tettamanzi, 2001
Esempio
simbolo probabilità il i codice
AEIOUN...
0.09880.09450.08630.08490.02550.0684...
555575...
0.04940.146050.236450.322450.377250.4242...
00001001000011101010011000001101...
Andrea G. B. Tettamanzi, 2001
Codice aritmetico
0 1
)( 1sP )( 2sP )( 3sP
1s 2s 3s
1s 2s 3s
1s 2s 3s
)()()()()(0 21211321 sPsPsPsPsPsss
Andrea G. B. Tettamanzi, 2001
Codice Aritmetico: Algoritmo
s[1..n] è la stringa da codificare
c = 0;a = 1;for i = 1 to n dobegin
c = c +a*ProbCum(s[i]);a = a*Prob(s[i]);
end
c (scritto in base 2) èil codice cercato
c è il codice ricevuto
a = 1;for i = 1 to n dobegin
s[i] = FindSymbol(c);c = (c -ProbCum(s[i])) /Prob(s[i]);i = i + 1;
end
s[1..n] è la stringa cercata
Andrea G. B. Tettamanzi, 2001
Lezione 6
28 ottobre 2002
Andrea G. B. Tettamanzi, 2001
Algoritmo di Lempel e Ziv
1. Da sinistra a destra, scrivere ogni volta la parola più brevemai incontrata prima, fino alla fine del testo;
2. Per ogni parola, separare il prefisso (una parola già incontrata)dal simbolo finale;
3. Codificare ogni parola con una coppia formata dalla posizionesuo prefisso nella lista e dal simbolo finale che deve essereaggiunto.
Andrea G. B. Tettamanzi, 2001
Esempio
1011010011010...
(passo 1) 1, 0, 11, 01, 00, 110, 10, ...
(passo 2) 1, 0, 1.1, 0.1, 0.0, 11.0, 1.0, ...
(passo 3) (0, 1) (0, 0) (1, 1) (2, 1) (2, 0) (3, 0) (1, 0) ...
000 1 000 0 001 1 010 1 010 0 011 0 001 0 ...
Andrea G. B. Tettamanzi, 2001
Efficienza del codice di Lempel e Ziv
1)(log)()( nNnNnL ww
)(nNw parole in un messaggio di lunghezza n
)(log2 nNw bit necessari per codificare la posizione di un prefisso
Lunghezza della codifica di un messaggio di lunghezza n:
Efficienza del codice di Lempel-Ziv:
n
nNnN
n
nL wwLZ
1)(log)()(
Andrea G. B. Tettamanzi, 2001
Teorema
)()(log)(
suplim XHn
nNnN ww
n
Data una sorgente stazionaria ergodica con alfabeto X ed
entropia H(X), vale
q.c.
Andrea G. B. Tettamanzi, 2001
Diseguaglianza di Lempel e Ziv
n
nnNw
2log)1()(
0lim
ncon
22)1(2 1
1
l
l
i
il lin
Dimostrazione:
Lungh. Cum. parole lunghe al più l
1:: ll nnnln
112222)( 11
1
l
n
l
nnN lll
l
i
ilw
nlnn ll log2
)2(log2 21
nnn ll 2log
log2
n
nl
Andrea G. B. Tettamanzi, 2001
Diseguaglianza di Lempel e Ziv (segue)
2loglog2
n
nl Poniamo: 1
2loglog4
n
nn
nnn
n
nn
nn
n
n
nnl
log)1(loglog
4)log(log1
loglog
3)log2log(1log
log
3)2log(log1
3)2log(loglog1
n
n
l
nnNw log)1(1
)(
Se ne conclude che c.v.d.
Andrea G. B. Tettamanzi, 2001
Legge dei grandi numeri
1)()(
lim
i
i
nxf
n
xnP
Debole:
::0, N Forte:
1)(
)(i
i xfn
xnPNn
Andrea G. B. Tettamanzi, 2001
Diseguaglianza di Čebyšev
2
]var[)|][(|
C
XCXEXP
Dimostrazione:
|][| XEXZ 2
2 ][)(
C
ZECZP
iii
Czii
Czi
C
ZEzfz
C
zfzC
zfCZPii
2
22
2
22
][)(
1
)(1
)()(
)()( 22 zfzzfC
Andrea G. B. Tettamanzi, 2001
Messaggi più probabili
lnwwwW ,,, 21 tutti i messaggi di lunghezza l
iliii sssw 21)(wli Numero di occorrenze di si in w
n
i
li
isPwP1
)()(
l
iill
1
)()(log)(
)(log)(log)(log
1
1
)(
1
SlHsPsPl
sPsPwP
n
iii
n
i
slPi
n
i
li
ii
)( ii sPl
l per la legge dei grandi numeri
)()(
1log
1SH
wPl
Andrea G. B. Tettamanzi, 2001
Teorema di Shannon-McMillan
Data una sorgente discreta senza memoria S di entropia H(S),
:::0:0 LlL Le parole di lunghezza l ricadono in due classi:
I)
II)
w
w
w
wP )(
)()(
1log
1SH
wPl
Andrea G. B. Tettamanzi, 2001
Dimostrazione
2
2
xP
lSlHwP
w )()(
1log:
Čebyšev:
2
2
22
2
22
)(var)(
)(
1log)(
ll
l
l
wIlSlH
wPPP
2
11
2 )(log)()(log)()](var[
i
n
iii
n
ii sPsPsPsPwI
Non dipende da l.2
2
L
Andrea G. B. Tettamanzi, 2001
Lezione 7
31 ottobre 2002
Andrea G. B. Tettamanzi, 2001
Teorema
M))(())(( 22)1( SHlSHl M
Dimostrazione:
))(())(( 2)(2)()(
1log
1 SHlSHl wPSHwPl
w
SHl
w
SHl P ))(())(( 2)(2
))(())(( 2)(2 SHlSHl MPM 1)(1 P
12 ))(( SHlM ))((21 SHlM
Andrea G. B. Tettamanzi, 2001
I° Teorema di Shannon
Sia S una sorgente discreta senza memoria di entropia H(S).Siano messaggi di lunghezza l codificati in parole di codice di
lunghezza L in un alfabeto di codice con r simboli.
eP Probabilità che occorra un messaggio per cui non siadisponibile una parola di codice.
ePSlHrL )(log::0 l
Andrea G. B. Tettamanzi, 2001
Dimostrazione
))((log: SHlrL))((2 SHlLrovvero
))((2 SHlMMa: quindi LrM
Lr = numero di parole di codice di lunghezza L
Ogni messaggio tipico ha una parola di codice; i messaggi atipici,che non hanno una parola di codice associata, hanno probabilità dioccorrere pari a
)(PPe c.v.d.
Andrea G. B. Tettamanzi, 2001
Il canale discreto senza memoria (1)
n
i
m
iii ypxp
1 1
1)()(
C è un dispositivo in grado di associare in ogni istante t con
probabilità P(y | x) un simbolo y dell’alfabeto di destinazione
con un simbolo x dell’alfabeto sorgente.
)(,),(),()(
)(,),(),()(
,,,
,,,
:
21
21
21
21
m
n
m
n
i
ypypypYP
xpxpxpXP
yyyY
xxxX
ZitT
Andrea G. B. Tettamanzi, 2001
Il canale discreto senza memoria (2)
)|()|()|(
)|()|()|(
)|()|()|(
)(
2211
2222222121
1112121111
nmnmnnnn
mm
mm
ij
xyPpxyPpxyPp
xyPpxyPpxyPp
xyPpxyPpxyPp
pC
1)|(11
m
jij
m
jij xyPp
Andrea G. B. Tettamanzi, 2001
Esempio
0
1
0
1
?0.143
0.286
0.571
0.143
0.286
0.571
Andrea G. B. Tettamanzi, 2001
Estensione di un canale
N
N
m
N
n
N
Y
X
,,,
,,,
21
21
N
kijiijjij kkNN
xyPxxyyPP1
)|()|()|(11
Un canale è senza memoria sse:
Andrea G. B. Tettamanzi, 2001
Informazione mutua
)(
)|(log
)|(
1log
)(
1log);(
i
ji
jiiji xP
yxP
yxPxPyxI
)()(
),(log
)(
)(
)(
)|(log);(
ji
ji
j
j
i
jiji yPxP
yxP
yP
yP
xP
yxPyxI
Andrea G. B. Tettamanzi, 2001
Transinformazione
)(
)|(log)|();(
1 j
ijm
jiji yP
xyPxyPYxI
)(
)|(log)|();(
1 i
jin
ijij xP
yxPyxPyXI
)()(
),(log),(
),()(),()();(
1 1
11
ji
jin
i
m
jji
m
jjj
n
iii
yPxP
yxPyxP
yXIyPYxIxPYXI
Informazione mutua di sistema:
Andrea G. B. Tettamanzi, 2001
Capacità di canale
n
kkjk
ijn
i
m
jiji
xyPxP
xyPxyPxPYXI
1
1 1 )|()(
)|(log)|()();(
Dipende solo dalle caratteristiche del canale e dalla distribuzionein ingresso. Ipotesi di canale costante.
);(max YXIC
L’informazione mutua è max quando la transinformazione èindipendente dalla distribuzione in ingresso.
Andrea G. B. Tettamanzi, 2001
Equivocazione, Irrilevanza
)|( XYH
),( YXH )(XH
)|( YXH
)|( YXH
);( YXI)(YH
)|( XYH
),( YXH);( YXI
equivocazione irrilevanza
informazione mutua
Andrea G. B. Tettamanzi, 2001
Lezione 8
4 novembre 2002
Andrea G. B. Tettamanzi, 2001
Canale binario simmetrico
0
1
0
1
ep
ep
ep1
ep1
Andrea G. B. Tettamanzi, 2001
Capacità del canale binario simmetrico
)1log()1(log1);(max)(
BSC eeeeXP
ppppYXIC
)1log()1(log
)1log()1(log
)|()();(
0000
BSC
eeee pppp
qqqq
XYHYHYXI
ee pxPpxPyPq )1()1)(0()0(0
Andrea G. B. Tettamanzi, 2001
Capacità del canale binario simmetrico
ep
BSCC
0 0.5 1
1
Andrea G. B. Tettamanzi, 2001
Canale simmetrico a cancellazione
0
1
0
1
ep
ep
ep1
ep1
?
Andrea G. B. Tettamanzi, 2001
Capacità dei canali simmetrici
.)|(
1log)|(log
)|(
1log)|(
)(
1log)(max
)|(
1log)|()(
)(
1log)(max
)|()(max);(max
1
11)(
1 1 1)(
)()(SC
m
j ijij
m
j ijij
m
j jj
XP
m
j
n
i
m
j ijiji
jj
XP
XPXP
xyPxyPm
xyPxyP
yPyP
xyPxyPxP
yPyP
XYHYHYXIC
simmetria
Andrea G. B. Tettamanzi, 2001
Capacità del c.s.c.
ep
BECC
0 0.5 1
1
Andrea G. B. Tettamanzi, 2001
Canali in cascata
CANALE 1 CANALE 2X ZY
ix jy kz
Andrea G. B. Tettamanzi, 2001
Teorema
);();(
);();(
ZYIZXI
YXIZXI
(detto “Della Elaborazione dei Dati)
L’informazione mutua non può aumentare al crescere deicanali attraversati; semmai può diminuire.
In successive elaborazioni dei dati,si può solo verificare una perdita d’informazione,mai un guadagno.
Andrea G. B. Tettamanzi, 2001
Dimostrazione)|(),|( jkijk yzPxyzP )|(),|( kikji yxPzyxP
0)|(
),|(log),|(),(
)|(
)|(log),,(
)|(
1log),(
)|(
1log),(
)|()|(
j k ki
kjikj
iikj
i j k ki
jikji
i j jiji
i k kiki
zxP
zyxPzyxPzyP
zxP
yxPzyxP
yxPyxP
zxPzxP
YXHZXH
) | ( ) ( ) ; (Y X H X H Y X I diseguaglianzafondamentale
Andrea G. B. Tettamanzi, 2001
Probabilità di errore ed equivocazione
Sia YX (matrice di canale quadrata)
ji
jjjij yxPyxPyeP )|(1)|()|(
n
i
n
iiiiiie yxPyPyePyPp
1 1
)|(1)()|()(
n
i ijji
n
i
n
iiiiiii yxPyxPyPxyPxP
11 1
),()|(1)()|(1)(
Si può dimostrare che la probabilità di errore per il trasmittentee per il ricevente è identica:
Andrea G. B. Tettamanzi, 2001
Diseguaglianza di Fano
ee
eee p
pp
ppH
1
1log)1(
1log)(
)1log()()|( nppHYXH ee
equivocazioneprobabilità di errore
dove
L’incertezza media su X, se Y è noto, è al più l’incertezza sul fattoche sia stato commesso un errore e, in caso affermativo,l’incertezza su quale dei restanti simboli sia stato trasmesso.
Andrea G. B. Tettamanzi, 2001
Dimostrazione
e
n
iii
e
n
i ijji
ee
eeee
pyxP
p
nyxP
pp
p
npnppH
1
1log),(
1log),(
1
1log)1(
1log)1log()(
11
n
i iiii
ji
n
i ijji
ji
n
i
n
jji
yxPyxP
yxPyxP
yxPyxPYXH
11
1 1
)|(
1log),(
)|(
1log),(
)|(
1log),()|(
1
2
Andrea G. B. Tettamanzi, 2001
Dimostrazione (segue)
2 1–
0),()1(),(1)1(12ln
1
),()|(
),()1(
),()|(
),(
1
2ln
1
1)|(
1),(
2ln
11
)|()1(),(
2ln
1
)|(
1log),(
)|()1(log),(
11
11 1
1 1
11
11
n
iiie
n
iii
e
n
iii
n
j
n
i ii
iie
n
i ij
n
i ijji
ji
jie
n
i ii
eii
n
i ij ji
eji
ii
en
iii
ji
en
i ijji
yxPpyxPnn
p
yxPyxP
yxPp
yxPyxP
yxP
n
p
yxP
pyxP
yxPn
pyxP
yxP
pyxP
yxPn
pyxP
Andrea G. B. Tettamanzi, 2001
Corollario
)1log()()|( nppHYXH ee
quando
jip
jin
p
yxP
e
e
ji
1
1)|(
Andrea G. B. Tettamanzi, 2001
Lezione 9
7 novembre 2002
Andrea G. B. Tettamanzi, 2001
Distanza di Hamming
1,0X
l
iiiH wvwvd
1
][),(
lXwv , lvvvv 21 lwwww 21
2)00101010,00101100( HdEsempio:
0 0 1 0 1 1 0 0
0 0 1 0 1 0 1 0
Andrea G. B. Tettamanzi, 2001
Spazio di Hamming di dimensione n
lX Spazio di Hamming di dimensione l
1,0X
1
0 00 10
01 11
000 100
010 110010011
001101
111
0000 1000
Esempi:
Andrea G. B. Tettamanzi, 2001
II° Teorema di Shannon
Dato un canale discreto senza memoria di capacità C,
a) è possibile trasmettere una quantità di informazione H(X)con probabilità d’errore piccola a piacere, a patto che
CXH )(
b) Se CXH )(
comunque codifichiamo i messaggi, sarà
0 Le Pp
Andrea G. B. Tettamanzi, 2001
Dimostrazione di b)
Ipotesi:
Tesi:
CXH )( CXHpCXH e )()(
CYXHXHYXI )|()();(
)()1log()()|()(0 eee pfnppHYXHCXH
Fano
)1log()1log()1(log)( nzzzzzzf
nzf log)(0 0)()( CXHPf LPoniamo
0)()( Le PfpfAllora
Andrea G. B. Tettamanzi, 2001
Grafico di f(z)
nlog
)(zf
z
)( LPf
LP
)( epf
epn
n 1
)1log( n
1
LeLe PpPfpf )()(
Andrea G. B. Tettamanzi, 2001
Dimostrazione di a)
Ipotesi:
Tesi: epCXH )(
Assumiamo r = 2 senza perdita di generalitàParole di codice di lunghezza l l2 messaggi
)( 12 ClM
1)( CXHN.B.: bit/simbolo
Usiamo solo parole di codice dellel2
Costruiamo un codice “a caso” e dimostriamo che ep
Andrea G. B. Tettamanzi, 2001
Codice “casuale”
Estraiamo a caso)( 12 ClM parole di codice tra le
l2
Sia 2
1q la probabilità di errore del canale (per simbolo!)
w CANALE w
lqwwdE H )]ˆ,([
Andrea G. B. Tettamanzi, 2001
Errore
w
w
lq
),( dwS
d)( 2 qld
2l
Andrea G. B. Tettamanzi, 2001
Volume di una sfera di raggio d
dk
kldN )(
In uno spazio di Hamming di dimensione l
numero di parole binarie di lunghezza l che differiscono
da una data parola w (centro) in al più d posizioni.
...2
1)(
lldN
w 1)',(:' wwdw H
2)',(:" wwdw H
Andrea G. B. Tettamanzi, 2001
Lemma)( 22)( qlHdN)( 2 qld
Dimostrazione: )( 2 q ld 10
i) )()1(0
dNd
dkkldk
dkklk
l
kkll
ii)
lddN )1()(
)()1log(log 22)1( lHlld
0)1log()1()1log(
)1log(log)(
H
c.v.d.
diseguaglianzafondamentale
Andrea G. B. Tettamanzi, 2001
Probabilità di errore per un dato codice
])ˆ,([)],(ˆ[ dwwdPdwSwP H
Per il Teorema dei grandi numeri:
)],([
)],([)],(ˆ[
)],('[)],(ˆ[
)],('[)],(ˆ[)],(ˆ[
ˆ
ˆ
dwSvP
dwSvPdwSwP
dwSwPdwSwP
dwSwPdwSwPdwSwPp
wv
wv
e
Andrea G. B. Tettamanzi, 2001
Probabilità media di errore
))(1()(
ˆ
22 22
2
)()],([
)],([)1()],([
qHllqlH
l
wve
MM
dNMdwSvPM
dwSvPMdwSvPp
)( 22)( qlHdN Parole contenute in ),( dwS
)( 2 qld
Andrea G. B. Tettamanzi, 2001
Conclusione della dimostrazione
)()(
)()()(1)(1
2
22
qHqHC
qHqHqHqH
3222 )(1
log)()(')()(
qHq
qqHqHqHqH
Sviluppiamo in serie di Taylor, ricordando cheq
qqH
1log)('
32 )(1 CqHPer cui:
)(
)()())(1(
31
312
2
222l
ClClqHle Mp
c.v.d.
Andrea G. B. Tettamanzi, 2001
Andamento della probabilità di errore
)(XH0
ep
C
CXH )(
CXH )(
Top Related