Andrea G. B. Tettamanzi, 2001 Teoria dellInformazione (Classica) Andrea G. B. Tettamanzi Università...

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


Lezione 1

3 ottobre 2002


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


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.


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”


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.


Che Cos’è l’Informazione?

SINTASSI

SEMANTICA

PRAGMATICA


significato

Informazione

informazione

apparatosimbolico

Rilevanza pratica dell’informazione (effetto, scopo, ecc.)


Informazione - semantica

• La quantità di informazione di un enunciato è tanto più grande quante più sono le alternative che esso esclude.

UA B


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?


Compressione

Immagazzinamento = Trasmissione

scrittura

lettura

t0

t1

invio ricezione

x0 x1


Funzioni convesse

)()()( 2121 xxfxfxf

0,

1

Diseguaglianza fondamentale:

1ln xx1ln

log b

xxb


Convessità del valore atteso

convessa

concava

)(Xg ])[()]([ XEgXgE

)(Xg ])[()]([ XEgXgE


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ì


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


Entropia informativa di Shannon

n

iii xPxPXH

1

)(log)()(

continua

simmetrica (commutativa)

additiva )()(),( YHXHYXH


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.:


Entropia delle lingue

testo

)Z""(

)A""(

P

P

Frequenzedei simboli

Z""

A""2 )P(

1)logP()testo(

H


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(


Informazione secondo KolmogorovMisura assoluta, non utilizza la probabilità

X Y

xyD )(

x y

descrizionioggetti

yxKxyD

)(

min)(

fn.parzialericorsiva


Equivalenza con entropia di Shannon

kkxKx 2)(:

cnXHxKxpXH n

x

nnn

n

log2)()()()(

)()( XnHXH n

)()(

lim XHn

xK n

n


Lezione 2

8 ottobre 2002


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)


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)


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


Modello della comunicazione

sorgente destinazione

rumore

canale


Modello dettagliatoSorgente di

informazioneDestinazione

riduzione ricostruzione

Codificasorgente

cifratura

Decodificasorgente

decifrazione

Codificacanale

Decodificacanale

modulazione demodulazioneCanale continuo

distorsione(rumore)

Canale discreto


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


Proprietà

1

011 )()(

110

r

jijkiiirkkk jr

xXPxxxXXXP

Indipendenza statistica e stazionarietà:

)(

1log)(

ii xp

xI autoinformazione


Il concetto di codice

Alfabeto sorgente

Alfabeto del codice

NsssS ,,, 21

nxxxX ,,, 21 nN

*Sz

*Xw

**:cod XS

)cod(zw

)(cod 1 wz


Esempio: codifica delle cifre decimali

Cifradecimale

Rappresentazionebinaria

0123456789

0000000100100011010001010110011110001001


Estensione di una sorgente

Alfabeto base

Alfabeto esteso

nxxxX ,,, 21

m

nnn

m

m xxxxxxX ,,111


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


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


Lezione 3

14 ottobre 2002


Classificazione dei codici

A blocco

Singolare Non singolare

Unicamentedecodificabile

Non unicamentedecodificabile

Istantaneo Non istantaneo


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


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


Diseguaglianza di Kraft

Condizione necessaria e sufficiente perché esista uncodice istantaneo con lunghezze di parola

è che

qlll ,,, 21

11

q

i

lir


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


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


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 :)(


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


Lezione 4

21 ottobre 2002


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:


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


Processi Markoviani

X t t( )

, ,

0 1

],,,|[

],,,|[

21

110

mtttt

tt

XXXxXP

XXXxXP

È un processo Markoviano di ordine m sse


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


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:


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)|(


Struttura statistica delle lingue

testo

)Z""(

)A""(

P

P

Distribuzionea memoria 0:

)Z"|"Z""(

)B"|"A""(

)A"|"A""(

P

P

P

Distribuzionea memoria 1:


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


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:


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


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


Teorema

)()()()(10 m

XHXHXHXH

L’entropia di una sorgente con memoria è tanto minore quantomaggiore è l’ordine della memoria.


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


Lezione 5

24 ottobre 2002


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.



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).



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


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


Esempio

simbolo probabilità codice

0123456789

1/41/41/81/81/161/161/321/321/321/32

00011001011100110111100111011111011111


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è


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


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


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


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'('


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


Esempio

simbolo probabilità il i codice

AEIOUN...

0.09880.09450.08630.08490.02550.0684...

555575...

0.04940.146050.236450.322450.377250.4242...

00001001000011101010011000001101...


Codice aritmetico

0 1

)( 1sP )( 2sP )( 3sP

1s 2s 3s

1s 2s 3s

1s 2s 3s

)()()()()(0 21211321 sPsPsPsPsPsss


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


Lezione 6

28 ottobre 2002


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.


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 ...


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)()(


Teorema

)()(log)(

suplim XHn

nNnN ww

n

Data una sorgente stazionaria ergodica con alfabeto X ed

entropia H(X), vale

q.c.


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


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.


Legge dei grandi numeri

1)()(

lim

i

i

nxf

n

xnP

Debole:

::0, N Forte:

1)(

)(i

i xfn

xnPNn


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


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


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


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


Lezione 7

31 ottobre 2002


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


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


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.


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


Il canale discreto senza memoria (2)

)|()|()|(

)|()|()|(

)|()|()|(

)(

2211

2222222121

1112121111

nmnmnnnn

mm

mm

ij

xyPpxyPpxyPp

xyPpxyPpxyPp

xyPpxyPpxyPp

pC

1)|(11

m

jij

m

jij xyPp


Esempio

0

1

0

1

?0.143

0.286

0.571

0.143

0.286

0.571


Estensione di un canale

N

N

m

N

n

N

Y

X

,,,

,,,

21

21

N

kijiijjij kkNN

xyPxxyyPP1

)|()|()|(11

Un canale è senza memoria sse:


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


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:


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.


Equivocazione, Irrilevanza

)|( XYH

),( YXH )(XH

)|( YXH

)|( YXH

);( YXI)(YH

)|( XYH

),( YXH);( YXI

equivocazione irrilevanza

informazione mutua


Lezione 8

4 novembre 2002


Canale binario simmetrico

0

1

0

1

ep

ep

ep1

ep1


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


Capacità del canale binario simmetrico

ep

BSCC

0 0.5 1

1


Canale simmetrico a cancellazione

0

1

0

1

ep

ep

ep1

ep1

?


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


Capacità del c.s.c.

ep

BECC

0 0.5 1

1


Canali in cascata

CANALE 1 CANALE 2X ZY

ix jy kz


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.


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


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:


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.


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


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


Corollario

)1log()()|( nppHYXH ee

quando

jip

jin

p

yxP

e

e

ji

1

1)|(


Lezione 9

7 novembre 2002


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


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:


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


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


Grafico di f(z)

nlog

)(zf

z

)( LPf

LP

)( epf

epn

n 1

)1log( n

1

LeLe PpPfpf )()(


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


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 )]ˆ,([


Errore

w

w

lq

),( dwS

d)( 2 qld

2l


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


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


Probabilità di errore per un dato codice

])ˆ,([)],(ˆ[ dwwdPdwSwP H

Per il Teorema dei grandi numeri:

)],([

)],([)],(ˆ[

)],('[)],(ˆ[

)],('[)],(ˆ[)],(ˆ[

ˆ

ˆ

dwSvP

dwSvPdwSwP

dwSwPdwSwP

dwSwPdwSwPdwSwPp

wv

wv

e


Probabilità media di errore

))(1()(

ˆ

22 22

2

)()],([

)],([)1()],([

qHllqlH

l

wve

MM

dNMdwSvPM

dwSvPMdwSvPp

)( 22)( qlHdN Parole contenute in ),( dwS

)( 2 qld


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.


Andamento della probabilità di errore

)(XH0

ep

C

CXH )(

CXH )(

Andrea G. B. Tettamanzi, 2001 Teoria dellInformazione (Classica) Andrea G. B. Tettamanzi Università...

Documents

Transcript of Andrea G. B. Tettamanzi, 2001 Teoria dellInformazione (Classica) Andrea G. B. Tettamanzi Università...