Lezione 8 Codifica e crittografia

X

ed n, sono quelle la cui distribuzione di probabilità è:

X

¿+ε

H ( )

¿

X

¿−ε

H ( )

¿

−n ¿

−n ¿ ¿

n

( )

n ≙ ϵ

{

A ε x , … , x X :2

1 n

Dove è l’approssimazione con la quale stiamo considerando la

ε

distribuzione di probabilità.

Le conseguenze dell’AEP sono:

( ) ( )+ ¿

P x , … , x ≤ H X ε

X ,… , X 1 n

1 n

I. 1

( )

n ( )−ε

ϵ ⇒ ¿

x , … , x A ε H X ≤− log

1 n n

II. P[( per n sufficientemente grande, la probabilità

( )

n

¿ϵ ¿>1−ε

X , … X A ε

1 n

di trovare una sequenza tipica è molto alta.

X

¿+ε

H ( )

III. Fornisce un limite superiore n¿

( ) ¿

n

¿ ∨≤

A ε 2

X

¿−ε

H ( )

IV. Fornisce un limite inferiore per n sufficientemente grande

n¿

( ) ¿

n

¿ ∨≥

A ε 2

Proprietà 1

È un modo alternativo di caratterizzare le sequenze tipiche. Per la definizione

di ( )

n

A ε X

¿+ε

H ( )

¿

X

¿−ε

H ( )

−n ¿

−n ¿ ( ) ¿

n

∈ ⇔2

x , … , x A ε

1 n

( ) ( )

( )

( )+ ( )−ε

−n H X ε ≤ log P x ,… , x ≤−n H X

2 X ,… , X 1 n

1 n −1

Divido tutti i membri per n

( ) ( ) +¿

P x , … , x ≤ H X ε

X , …, X 1 n

1 n 1

( ) −ε

H X ≤− log¿

n

Proprietà 2

Applicando la definizione di convergenza in probabilità sappiamo che:

−1 ( ) ( )

log P X , … , X → H X per n→ ∞

X ,… , X 1 n

n 1 n

1 ]

|

( ) ( )

¿− −H ¿ =1

P log P X , … , X X e

X ,… , X 1 n 0

n 1 n

∀ >0 ¿

e lim

0 n→∞

ed sono arbitrari, allora posso scegliere , quindi

=ε

e e

ε

1 1

nell’argomento della probabilità risulta per che:

n>n ε , e

1

| |

−1 ( ) ( )

−H <

log P X , … , X X ε

X ,… , X 1 n

n 1 n

1 ( ) ( )<

−ε ← −H

log P X , … , X X ε

X , …, X 1 n

n 1 n

Sommando ai 2 membri abbiamo:

( )

H X

( ) ( ) +¿

P x , … , x ≤ H X ε

X , …, X 1 n

1 n 1

( ) −ε

H X ≤− log¿

n

Per la proprietà 1 è proprio la condizione che la sequenza è una

x , … , x

1 n

sequenza tipica; quindi, comunque scegliamo positivo la probabilità che

ε

la sequenza sia tipica è 1, ovvero:

[ ]

( )

n

( ) ϵ <ε

1−P X , … X A ε

1 n

[ ]

( )

n

( ) ϵ >

P X , … X A ε 1−ε per n suff . grande

1 n

Per n grande la probabilità di incontrare sequenze tipiche è molto alta.

Proprietà 3

Definito , ( ; inoltre definita la

=[ ] ¿

X X , … , X x , … , x

x=¿

1 n 1 n

[ ] allora la somma di tutte le

( )=P ( )

=P =x =x

P x x , … , x X , … , X

X X , …, X 1 n 1 1 n n

1 n

distribuzioni di probabilità sarà 1 e inoltre sarà sicuramente maggiore della

somma solo sulle sequenze tipiche.

∑ ∑

( ) ( )

1= p x ≥ p x

X X

( )

n n

x∈ X x∈ A ε

Ricordando la definizione di sequenza tipica:

X

¿+ε

H ( )

¿

X

¿−ε

H ( )

−n ¿

−n ¿

( ) ¿

n

∈ ⇔

x A ε 2

Allora possiamo scrivere che:

X

¿+

H ε

( )

¿

−n ¿

¿

2

∑ ∑

( ) ¿

p x ≥

X ( )

n n

∈ ∈

x X x Aε X

¿+ε

H ( )

Facendo la sommatoria di termini costanti ( ) si ottiene la costante per

−n ¿

¿

2

il numero di elementi dell’insieme quindi:

( )

n

A ε

X

¿+ε

H ( )

¿

X

¿+ε

H ( )

−n ¿

−n ¿

¿

2

∑ ¿

( )

n

x∈ A ε X

¿+

H ε

( )

¿

n

| |

( ) ¿

n

⇒ A ε ≤ 2

Ottengo un limite superiore per la cardinalità dell’insieme delle sequenze

tipiche.

Proprietà 4 [ ]

Per la proprietà 2 sappiamo che: ( )

n

ϵ >1−ε

P X A ε per n suff . grande

Quindi per n grande abbiamo che:

[ ]

( )

n

ϵ

<

1−ε P X A ε X

¿−ε

H ( )

¿

−n¿

¿

2

[ ] ∑ ∑

( )

n ( )

ϵ = ¿

P X A ε p x ≤

X

( ) ( )

n n

∈ ∈

x A ε x A ε

X

¿−ε

H ( )

Dato che è un termine costate la sua sommatoria sarà il prodotto del

−n ¿

¿

2

termine costante per il numero di elementi nell’insieme ( )

n

A ε

X

¿−ε

H ( )

¿

X

¿−ε

H ( )

−n ¿

−n ¿

¿

2

∑ ¿

( )

n

x∈ A ε X

¿−ε

H ( )

−n ¿

| |

( ) ¿

n )2

A ε ≥(1−ε

Tale proprietà fornisce il limite inferiore per la cardinalità dell’insieme ( )

n

A ε

.

PROBLEMA

Supponiamo di avere la sequenza v.a. iid, e . Si

∈

X , … , X x X ( )

p x

X

1 n i

vuole trovare una descrizione breve per la sequenza di v.a., quindi preso

qualsiasi ( )

∈

x x , … , x →C x

1 n

Dove è una parola codice binaria, cioè una sequenza di bi con una

( )

C x

certa lunghezza . La cosa importante è che la corrispondenza tra

( )

l x

sequenza e parola codice

( )

x↔C x

deve essere biunivoca.

è una v.a. perché è la lunghezza della parola codice associata ad

( ) ( )

l X C X

che è aleatoria, di conseguenza è possibile calcolare la media usando il

X

teorema fondamentale del calcolo della media (prende il nome di lunghezza

media del codice):

∑

{ }

( ) ( ) ( )

=

L=E l X p x l x

X

n

∈

x X

Trovare una descrizione breve significa rende la lunghezza media la più

piccola possibile. Indichiamo n

¿ x∨¿

Dove l’insieme più esterno è cioè l’insieme di tutte le sequenze

n

X ¿

elementi, mentre l’insieme interno corrisponde a l’insieme delle

( )

n

A ε

X

¿+ε

H ( )

sequenze tipiche che avrà una cardinalità , il residuo sarà pari a

¿

n

| |

( ) ¿

n

A ε ≤2

che prende il nome di insieme non tipico.

( ) ( )

n c n n

=X −A

Aε ε

Per la strategia di codifica verranno trattate diversamente le sequenze tipiche

e quelle non tipiche. Per quanto riguarda le sequenze tipiche sono al più

X

¿+ε

H ( ) , quindi per codificare in binario una sequenza tipica servono un

n¿

¿

2 X

numero di bit corrispondenti a , prendere la parte intera più 1 bit più

¿+ε

H ( )

n¿

un bit 0 di prefisso che caratterizza le sequenze tipiche. La lunghezza parola

X ( )

( ) ( )+

¿+ε +2 +2

codice n H ≤n H x ε

( ) ∫

( )= ¿

l x | |

Per quanto riguarda le sequenze non tipiche, esse sono , con

( )

n n

¿ ∨−

X A ε

n ∨¿

X ¿

¿

grossolana approssimazione posso dire che bastano . Per

¿

log 2

∫ ¿

caratterizzare le sequenze non tipiche si usa il prefisso 1.

n ∨¿

X ¿

¿ X∨¿+2

La lunghezza della parola codice .

¿ ¿

log 2

∫

( )= ¿

l x

La lunghezza media del codice, quindi, sarà suddivisa in 2 sommatorie, una

delle sequenze tipiche e l’altra di quelle non tipiche:

∑ ∑

( ) ( )+ ( ) ( )

L= p x l x p x l x

X X

( ) ( )

n n n

∈ −

x∈ A ε x X A ε

Precedentemente è stato individuato il limite superiore per le lunghezze della

parola codice di entrambe le sequenze quindi possiamo scrivere che le 2

sommatorie saranno:

∑ [ ]

] | |

( ( ) ( )

+ε +2 +¿ +

n H X p x n log X 2

X 2

( )

n c

x∈ A ε

( ) ¿

p x

X

∑ ¿

≤ ( )

n

∈

x A ε

∑ ( )

p x corrisponde alla probabilità che la sequenza sia tipica, mentre

X

( )

n

∈

x Aε

∑ ( )

p x è la somma di tutte le x appartenenti a , cioè la probabilità

( )

n c

A ε

X

( )

n c

∈

x Aε

che la sequenza non sia tipica.

[ ] [ ] [ ]

( )

( ) ( ) ( ) ( )

( )

n n c n n c

| |

( )

∈ ∈ ∈ ∈

¿ +ε + [x ]n +2 +

P x A ε n H X P A ε log X P x A ε P x A ε

2

[ ] [ ]

( ) ( )

n n c

∈ ∈

+ =1

P x A ε P x A ε

[ ]

( )

n

∈

P x A ε ≤1

[ ] [ ]

( ) ( )

n c n

∈ ∈

=1−P