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: andrea.tettamanzi@unimi.it

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

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

invio ricezione

Funzioni convesse

)()()( 2121 xxfxfxf

Diseguaglianza fondamentale:

1ln xx1ln

Convessità del valore atteso

convessa

concava

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

Misura dell’Informazione

R. V. L. Hartley Alfabeto di s simboli

C I A O M M MA A, !

Messaggi possibilils

slssH ll loglog)( R. Hartley

)()( 1slHsH l Perché il logaritmo? Perché così

Unità di misura dell’Informazione

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

iii xPxPXH

)(log)()(

continua

simmetrica (commutativa)

additiva )()(),( YHXHYXH

Massimo dell’Entropia

nXH log)(

i iiii np

pnppnXH1 1

1loglogloglog)(

0log)11(

ba log

1log N.B.:

Entropia delle lingue

Frequenzedei simboli

A""2 )P(

1)logP()testo(

Ridondanza

1R Efficienza di codificaM

056,4)en(

046,4)de(

896,3)fr(

956,3)it(

853,0)en(

850,0)de(

839,0)fr(

887,0)it(

Informazione secondo KolmogorovMisura assoluta, non utilizza la probabilità

xyD )(

descrizionioggetti

yxKxyD

fn.parzialericorsiva

Equivalenza con entropia di Shannon

kkxKx 2)(:

cnXHxKxpXH n

log2)()()()(

)()( XnHXH n

lim XHn

Lezione 2

8 ottobre 2002

Assiomi dell’entropia (1)),,,( 21 npppH Misura d’incertezza,

max con eventi equiprobabili

),,,(),,,( )()2()1(21 nn pppHpppH

3 0),,,( 21 npppH

4 )0,,,,(),,,( 2121 nn pppHpppH

(simmetrica)

Assiomi dell’entropia (2)

6 continua

7 ),,(),,(),,( 1111 nnnn qpqpHqqHppH

),,(),,(),(

),,,,,(

ppHqpH

(diramazione)

Teorema

log),,(1

ppkppHn

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

)(,),(),()(

xpxpxpXP

S è un dispositivo che genera ad ogni istante t un simbolo x con

probabilità p(x), i.i.d.

xpxpxp

)()()( 21

Proprietà

011 )()(

jijkiiirkkk jr

xXPxxxXXXP

Indipendenza statistica e stazionarietà:

1log)(

xI autoinformazione

Il concetto di codice

Alfabeto sorgente

Alfabeto del codice

NsssS ,,, 21

nxxxX ,,, 21 nN

**: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 xxxxxxX ,,111

Teorema

Data una sorgente senza memoria, )()( XmHXH m

Dimostrazione:

1log)()(

mi mmi

iiXx Xxii

xxpxxpXH

iiXx Xxii

mi mmi

xpxpxpxp

1log)(

1log)()(

Nel caso X = {0, 1}

}1,0{21

1log}1,0{

Lezione 3

14 ottobre 2002

Classificazione dei codici

A blocco

Singolare Non singolare

Unicamentedecodificabile

Non unicamentedecodificabile

Istantaneo Non istantaneo

Esempi

Non unicamentedecodificabile:

Non istantaneo:

Codici a prefisso

Condizione necessaria e sufficiente perché un codicesia istantaneo è che nessuna parola del codice sia unprefisso di un’altra parola del codice.

Diseguaglianza di Kraft

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

è che

qlll ,,, 21

Dimostrazione - sufficienza

Costruiamo un codice istantaneo che soddisfa 11

llrnmax

lll rrn

rnrnrn lll

maxmax

rnrnrn lll

maxmax

Teorema di McMillan

Un codice unicamente decodificabile soddisfa la diseguaglianza di Kraft

l qi rrrr

nii llk 1

kllrr nii

Sviluppando la potenza, avremo qn termini della forma

maxnlkn

maxmax1

1maxmax

nlnnlrrrNrnl

kk rN ma allora deve essere 1

Teorema di codifica della sorgente

)(SHl r

iii pll

Sia la lunghezza media di un codice istantaneo

a r simboli. Allora,

ilir rpiSHl :)(

Dimostrazione

i irir

plSH1111

111 ln

1loglog

KraftProprietà fondamentale dei logaritmi

Lezione 4

21 ottobre 2002

Processi Stocastici

X t t( )

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

Processi Markoviani

X t t( )

],,,|[

XXXxXP

È un processo Markoviano di ordine m sse

Sorgente discreta con memoria

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

mtxtxtxPXP

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

jjjijjji xxxxp

Informazione condizionale:

1log)|()|(

21211 m

ijjjijjj xxxxp

xxxxpxxxXH

Entropia condizionale:

Proprietà dell’Entropia condizionale

)()|( YHXYH

0loglog)|(log)(log

)()|(log

)(log)|(

)(log)()|(

1log)|(

1 11 1

eexypeype

ypxype

ypypxyp

j ijij

Dimostrazione:

iji yxp

Struttura statistica delle lingue

Distribuzionea memoria 0:

)Z"|"Z""(

)B"|"A""(

)A"|"A""(

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

1 10 100

Memoria

Entropia

Esperimento di Shannon)(

1log)(

Entropia nelle sorgenti con Memoria

j jjjijjji

xxxxpxxxxp

1 1 11 2 21

21 )|(

1log)|(

21 )|(

1log),,,,(

X jjjijjji 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)

j ijji xxp

xxpXXHXH1 1 12

2112 )|(

1log),()|()(

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

jjiiijji

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

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

iik sPP

Scriverle in notazione r-aria

Il numero di simboli per parola di codice è dato da

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

0.40.30.10.10.1

0.40.30.20.1

0.40.30.3

0.60.4

10001101000101001011

codice

Ottimalità del codice di Huffman

nn sssC ,,, 11 ',,,' 21 sssC n nn sss 1'

pplpplp

lplplpl

)1'()1'('

Codice alfabetico (o di Gilbert-Moore)

Ordinare i simboli sorgente secondo qualche criterio

La lunghezza di ciascuna parola di codice è data da

l sP 21 2)(2

Determinare la sequenza

nnn sPsPsP

10 21 n

Rappresentare in base rciascuno di questi numerisecondo la lunghezzacalcolata

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

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

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]);

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;

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:

nL wwLZ

1)(log)()(

Teorema

)()(log)(

suplim XHn

nNnN ww

Data una sorgente stazionaria ergodica con alfabeto X ed

entropia H(X), vale

Diseguaglianza di Lempel e Ziv

2log)1()(

22)1(2 1

il lin

Dimostrazione:

Lungh. Cum. parole lunghe al più l

1:: ll nnnln

112222)( 11

nnN lll

nlnn ll log2

)2(log2 21

nnn ll 2log

Diseguaglianza di Lempel e Ziv (segue)

2loglog2

nl Poniamo: 1

2loglog4

log)1(loglog

4)log(log1

loglog

3)log2log(1log

3)2log(log1

3)2log(loglog1

nnNw log)1(1

Se ne conclude che c.v.d.

Legge dei grandi numeri

Debole:

::0, N Forte:

Diseguaglianza di Čebyšev

]var[)|][(|

XCXEXP

Dimostrazione:

|][| XEXZ 2

2 ][)(

zfCZPii

)()( 22 zfzzfC

Messaggi più probabili

lnwwwW ,,, 21 tutti i messaggi di lunghezza l

iliii sssw 21)(wli Numero di occorrenze di si in w

isPwP1

)()(log)(

)(log)(log)(log

SlHsPsPl

sPsPwP

)( ii sPl

l per la legge dei grandi numeri

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:

Dimostrazione

lSlHwP

w )()(

Čebyšev:

)(var)(

1log)(

wIlSlH

2 )(log)()(log)()](var[

ii sPsPsPsPwI

Non dipende da l.2

Lezione 7

31 ottobre 2002

Teorema

M))(())(( 22)1( SHlSHl M

Dimostrazione:

))(())(( 2)(2)()(

1 SHlSHl wPSHwPl

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)

iii ypxp

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.

)(,),(),()(

ypypypYP

xpxpxpXP

Il canale discreto senza memoria (2)

)|()|()|(

2222222121

1112121111

nmnmnnnn

xyPpxyPpxyPp

1)|(11

jij xyPp

Esempio

?0.143

Estensione di un canale

kijiijjij kkNN

xyPxxyyPP1

)|()|()|(11

Un canale è senza memoria sse:

Informazione mutua

)|(log

1log);(

jiiji xP

yxPxPyxI

),(log

)|(log);(

jiji yPxP

yxPyxI

Transinformazione

)|(log)|();(

jiji yP

xyPxyPYxI

)|(log)|();(

ijij xP

yxPyxPyXI

),(log),(

),()(),()();(

yxPyxP

yXIyPYxIxPYXI

Informazione mutua di sistema:

Capacità di canale

xyPxyPxPYXI

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

);( YXI)(YH

)|( XYH

),( YXH);( YXI

equivocazione irrilevanza

informazione mutua

Lezione 8

4 novembre 2002

Canale binario simmetrico

Capacità del canale binario simmetrico

)1log()1(log1);(max)(

BSC eeeeXP

ppppYXIC

)1log()1(log

)|()();(

eeee pppp

XYHYHYXI

ee pxPpxPyPq )1()1)(0()0(0

Capacità del canale binario simmetrico

0 0.5 1

Canale simmetrico a cancellazione

Capacità dei canali simmetrici

1log)|(log

1log)|(

1log)(max

1log)|()(

1log)(max

)|()(max);(max

1 1 1)(

)()(SC

j ijij

j ijiji

xyPxyPm

xyPxyP

xyPxyPxP

XYHYHYXIC

simmetria

Capacità del c.s.c.

0 0.5 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

),|(log),|(),(

)|(log),,(

1log),(

)|()|(

j k ki

i j k ki

i j jiji

i k kiki

zyxPzyxPzyP

yxPzyxP

yxPyxP

zxPzxP

YXHZXH

) | ( ) ( ) ; (Y X H X H Y X I diseguaglianzafondamentale

Probabilità di errore ed equivocazione

Sia YX (matrice di canale quadrata)

jjjij yxPyxPyeP )|(1)|()|(

iiiiiie yxPyPyePyPp

)|(1)()|()(

i ijji

iiiiiii yxPyxPyPxyPxP

),()|(1)()|(1)(

Si può dimostrare che la probabilità di errore per il trasmittentee per il ricevente è identica:

Diseguaglianza di Fano

1log)1(

1log)(

)1log()()|( nppHYXH ee

equivocazioneprobabilità di errore

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

i ijji

npnppH

1log),(

1log)1(

1log)1log()(

i iiii

i ijji

yxPyxP

yxPyxPYXH

1log),(

1log),()|(

Dimostrazione (segue)

2 1–

0),()1(),(1)1(12ln

),()|(

),()1(

),()|(

)|()1(),(

1log),(

)|()1(log),(

i ijji

i ij ji

i ijji

yxPpyxPnn

yxPyxP

Corollario

)1log()()|( nppHYXH ee

quando

Lezione 9

7 novembre 2002

Distanza di Hamming

iiiH wvwvd

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

0 00 10

000 100

010 110010011

001101

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:

CXH )( CXHpCXH e )()(

CYXHXHYXI )|()();(

)()1log()()|()(0 eee pfnppHYXHCXH

)1log()1log()1(log)( nzzzzzzf

nzf log)(0 0)()( CXHPf LPoniamo

0)()( Le PfpfAllora

Grafico di f(z)

)( LPf

)( epf

)1log( n

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

1q la probabilità di errore del canale (per simbolo!)

w CANALE w

lqwwdE H )]ˆ,([

Errore

),( dwS

d)( 2 qld

Volume di una sfera di raggio d

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.

w 1)',(:' wwdw H

2)',(:" wwdw H

Lemma)( 22)( qlHdN)( 2 qld

Dimostrazione: )( 2 q ld 10

i) )()1(0

dkkldk

lddN )1()(

)()1log(log 22)1( lHlld

0)1log()1()1log(

)1log(log)(

c.v.d.

diseguaglianzafondamentale

Probabilità di errore per un dato codice

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

Per il Teorema dei grandi numeri:

)],([)],(ˆ[

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

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

dwSvPdwSwP

dwSwPdwSwP

dwSwPdwSwPdwSwPp

Probabilità media di errore

))(1()(

)()],([

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

qHllqlH

dNMdwSvPM

dwSvPMdwSvPp

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

)( 2 qld

Conclusione della dimostrazione

)()()(1)(1

qHqHqHqH

3222 )(1

log)()(')()(

qqHqHqHqH

Sviluppiamo in serie di Taylor, ricordando cheq

1log)('

32 )(1 CqHPer cui:

)()())(1(

ClClqHle Mp

c.v.d.

Andamento della probabilità di errore

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

Il flusso dellinformazione: lespressione genica La traduzione.

ECDL Mod. 11 Modulo 1 Concetti teorici di base della tecnologia dellinformazione.

1 Università di Parma Dipartimento di Ingegneria dellInformazione Università di Parma Dipartimento di Ingegneria dellInformazione Prof. Alberto Bononi.

Crittografia Monica Bianchini monica@ing.unisi.it Dipartimento di Ingegneria dellInformazione Università di Siena.

Diritto della comunicazione e dellinformazione Prof. Andrea Gratteri agratteri@unite.it.

La Ricerca Dellinformazione Sul Web Motori Di Ricerca Valutare Informazione

1 Traduzione dellinformazione genetica (1). 2 Traduzione dellinformazione genetica (2) Il processo negli eucarioti richiede: 70 diverse proteine ribosomiali.

Settimana della chiesa mantovana Intervento del card ... · Settimana della chiesa mantovana Intervento del card. Dionigi Tettamanzi ... ma è dei laici che vivono nella famiglia,

Introduzione alla teoria dellinformazione misura dellinformazione ridondanza codifica di sorgente robustezza codifica di canale decodifica dellinformazione.

IV CONVEGNO NAZIONALE LA PERSONA DOWN ......M. Tettamanzi Amicorum: una margherita per l’autonomia e l’integrazione G. Macchi Formazione ed integrazione lavorativa in ristorante

1 Facoltà di Ingegneria dellInformazione, Informatica e Statistica Dip. di Informatica e Sistemistica A. Ruberti Dip. di Ing. DellInformazione, Elettronica.

Relatore Marino Tettamanzi Infermiere Professionale Operatore Olistico Counselor in Naturopatia.

Dottorato in Società dellInformazione Università degli Studi di Milano-Bicocca Una rete per la scuola in ospedale Andrea Marcante.

ANTISPAM Corso di Sistemi di elaborazione dellinformazione: Sicurezza Christian Murgia.

Andrea G. B. Tettamanzi, 2003 Filogenetica Andrea G. B. Tettamanzi.

Il Ruolo dellInformazione Brevettuale come Strumento di Competitività per le PMI.

Società dellinformazione 1 Società dellInformazione Ottobre 2004.

ASSEMBLEA per la costituzione del CONSIGLIO …...PREGHIAMO INSIEME PREGHIERA AL CUORE DI CRISTO PER L'ORATORIO DELL'ARCIVESCOVO DIONIGI TETTAMANZI Cuore immenso di Cristo, affidiamo

Codifica dellInformazione. Problema Abbiamo dellinformazione (testi, numeri, immagini, ecc.) che vogliamo rappresentare in un calcolatore. Vincolo Per.

Master iDTV 2007-2008 Area Diritto dellInformazione.