TEORIA DELL’INFORMAZIONE ED

ENTROPIA

DI

FEDERICO MARINI

1

OBIETTIVO DELLA TEORIA DELL’INFORMAZIONE

Dato un messaggio prodotto da una sorgente, l’OBIETTIVO è

capire come si deve rappresentare tale messaggio per

ottenere una trasmissione efficiente ed affidabile

dell’informazione in essa contenuta su un canale di

comunicazione reale.

2

Il primo passo da analizzare è definire il tipo di sorgente:

SORGENTE DISCRETA

E’ un tipo di sorgente che emette simboli che

appartengono ad un alfabeto finito

ciascuno caratterizzato da una probabilità e

autoinformazione .

1 2, ,....., MX x x x=

iIiP

3

Pertanto la teoria dell’ Informazione utilizza tre concetti base:

Misura d’informazione di una sorgente

Capacità d’informazione di un canale

Codifica: mezzo per utilizzare la capacità di canale per trasferire

informazione. informazione.

4

CODIFICA

SORGENTE CANALE

Governata dal I° teorema

di Shannon. Governata dal II° teor. di Shannon

5

La misura dell’informazione è legata all’incertezza

associata all’emissione di ciascun simbolo . Pertanto

l’informazione associata ad un messaggio è legata alla sua

probabilità.

Shannon definisce la misura d’informazione, la seguente

quantità:

ix

Dove rappresenta l’ autoinformazione del messaggio e b è

la base del logaritmo.

Se b=2 l’autoinformazione si misura in bit.

6

iI

MISURA D’INFORMAZIONE – PROPRIETA’

per

per

per

0iI ≥ 0 1iP≤ ≤

0iI → 1iP →

I I> P P< per

i jI I>i jP P<

( )log , log log logij b i j b i j b i b j i jI P x x PP P P I I=− =− =− − = +

ENTROPIA DI UNA SORGENTE

Tale quantità si definisce Entropia della sorgente e

rappresenta l’informazione media per simbolo che è data

dalla media statistica delle autoinformazioni dei simboli

della sorgente .

Per M=2, l’entropia vale:

8

( )1 2, , ...., MI I I

ENTROPIA DI UNA SORGENTE M-ARIA

iP

Nel caso di sorgente M-aria, l’entropia

H(x) dipende dalla probabilità dei

simboli emessi dalla sorgente e dalla

dimensione M dell’alfabeto con M numero

di simboli.

9

iP

ENTROPIA DI SORGENTE BINARIA

Definite le due probabilità di emissione dei simboli

e :1P p= 2 1P p= −

10

TEOREMA DELLA CODIFICA DI SORGENTE

Sorgente

discreta senza

memoria

Codificatore

binario br R≥

( )R rH X= ( )bR r p= Ω

11

I° TEOREMA DI SHANNON

N

Con che rappresenta il valor medio delle

lunghezze delle parole di codice che

rappresentano i simboli emessi dalla sorgente e

con H(X) l’entropia di una sorgente discreta

senza memoria.

12

N

EFFICIENZA DI UN CODICE

Un codice per cui vale si dice

( )1

H x

Nη = ≤

( )N H x=Un codice per cui vale si dice

assolutamente ottimo.

Un codice per cui si ottiene il valore minimo

possibile di per una determinata sorgente si

dice ottimo.

Un codice con valore di superiore a quello di

un codice ottimo si dice sub-ottimo.

( )N H x=

N

N

CODICE DI HUFFMAN

E’ un esempio di codice ottimo , in quanto si

riesce ad ottenere il minimo possibile per

una determinata sorgente (ma non necessariamente

assolutamente ottimo =1).η

N

14

CODIFICA DI CANALE

1) L’obiettivo consiste nell’aumentare la resistenza di un

sistema di telecomunicazione al rumore presente sul

canale.

2) La codifica di canale “trasforma” la sequenza di dati in

ingresso al canale in una nuova sequenza ingresso al canale in una nuova sequenza

intrinsecamente più robusta agli effetti del rumore.

3) La decodifica di canale effettua l’operazione inversa in

uscita dal canale per ricostruire la sequenza originale.

15

Il canale è considerato come operatore stocastico che

trasforma i simboli in ingresso in simboli in diversi in

uscita in modo probabilistico.

Il canale è descritto dalla matrice di canale i cui elementi

sono le probabilità condizionate : ( )/N MP y x

16

CANALE

(RUMOROSO)

1 2, ,....., Mx x x X= 1 2, ,....., Ny y y Y=

EQUIVOCAZIONE DI CANALE

L’Equivocazione di Canale rappresenta

l’incertezza che rimane in media sul simbolo

trasmesso, dopo l’osservazione del simbolo

( ) ( ), 2/

1/ log

/X YX Y

H X Y EP x y

=

trasmesso, dopo l’osservazione del simbolo

ricevuto.

INFORMAZIONE MUTUA

L’Informazione Mutua mi dice di quanto sia

ridotta in media l’incertezza sul simbolo emesso

dalla sorgente una volta osservato il simbolo

ricevuto.17

( ) ( ) ( ), /I X Y H X H X Y= = −

CAPACITA’ DI CANALE PER SIMBOLO Cs

E’ il tasso d’informazione massimo consentito da

un dato canale:

( ) ( ) [ ], /maxs

P x

C I X Y bit simbolo=

CAPACITA’ DI CANALE PER UNITA’ DI TEMPO C

Dove mi indica la massima velocità dei simboli

permessi dal canale.

18

sC C S= ⋅

( ) iP x

S

CANALE DISCRETO SIMMETRICO

Un canale discreto simmetrico è un canale

in cui le probabilità di transizione sono

tali per cui la probabilità di transire

risulta uguale per tutti i simboli

(quindi l’entropia condizionata è ( )/H Y x(quindi l’entropia condizionata è

indipendente dal simbolo ).

19

( )/ iH Y x

ix

CAPACITA’ DI UN CANALE BINARIO SIMMETRICO

( ) ( ) ( ) ( ) ( ); / 2I X Y H Y H Y X p pα α α= − = Ω + − − Ω

Ponendo p=0.5, ottengo:

( ) ( ) ( )2 1sC p pα α α α= Ω + − − Ω = − Ω

Quindi dipende dalla probabilità di

transizione :

Per , e si ha un canale ideale (canale

senza rumore).

Per , e si ha un canale rumoroso.

21

sCα

0α = 1sC =

0.5α → 0sC =

II° TEOREMA DI SHANNON (CODIFICA DI

CANALE)

Si suppone di avere una sorgente discreta senza

memoria con alfabeto X, entropia H(X) e symbol

rate r.

L’information rate vale R=rH(X) L’information rate vale R=rH(X)

Si suppone di disporre un canale discreto senza

memoria con capacità per unità di tempo pari a

C [bit/sec].

22

Se allora esiste un sistema di

codifica tale da permettere la

trasmissione dell’informazione emessa

dalla sorgente sul canale con una

probabilità di errore arbitrariamente

piccola.

R C≤

Se non è possibile trasmettere

l’informazioni senza errori.

23

R C>

SORGENTE CONTINUA

La sorgente può produrre un insieme di possibili segnali

nel tempo che può essere visto come un processo

aleatorio ergodico.

La capacità del canale sarà espressa intermini di

larghezza di banda e di rapporto segnale-rumore.

( )x t

larghezza di banda e di rapporto segnale-rumore.

Ad ogni istante di campionamento si ha una variabile

aleatoria continua descritta da una funzione di densità

di probabilità .

24

x( )xp x

ENTROPIA DI UNA SORGENTE CONTINUA

CAPACITA’ DI UN CANALE CONTINUO

( ) ( ) ( )2

1logx

x

H X p x dxp x

∞

−∞

= ⋅∫

CAPACITA’ DI UN CANALE CONTINUO A BANDA

LIMITATA

25

( ) ( ) [ ]; /max

x

sP x

C I X Y bit campione=

2 sC B C= ⋅

LEGGE DI HARTLEY-SHANNON

[ ]2log 1 / secS

C B bitN

= ⋅ +

La legge di Hartley-Shannon descrive la capacità

di un canale continuo che introduce un rumore

additivo Gaussiano Bianco con banda limitata.

26