Seminar TTI

Seminar 1. Surse discrete

I. Breviar teoretic

Elemente de teoria informatiei

· Fie variabila aleatoare (v.a.) discreta X, caracterizata de alfabetul finit X ={xi}, de cardinalitate

|X | si functia de masa a probabilitatilor (f.m.p.) () ( ) i i

i

px=åpdx-x , cu conditia 1 i

i

å p = .

Informatia proprie obtinuta în urma realizarii evenimentului k (v.a. X a luat valoarea i x ) este

definita ca:

2 ( ) log i i ix = - p, [biti].

Entropia v.a. X reprezinta valoarea medie a informatiei proprii asociata variabilei:

[ ] 2 ( ) ( ) ( ) log i i i i i

i i

H X =E ix =åp ix= -åp p, [biti].

· Fie doua v.a. X si Y, de alfabete X si Y , caracterizate de f.m.p. reunita p(x,y). Definim:

Entropia reunita a celor doua v.a. X si Y:

( , ) ( , )log ( , )

i j

i j i j

x y

H X Y p xy p x y

Î Î

= -å å

X Y

.

Entropiile conditionate:

( | ) ( , )log ( | )

i j

i j i j

x y

H X Y p xy p x y

Î Î

= -å å

X Y

, ( | ) ( , )log ( | )

i j

i j j i

x y

H Y X p xy p y x

Î Î

= -å å

X Y

.

Informatia mutuala :

( , )

( , ) ( , ) log

( ) ( ) i j

i j

i j

x y i j

p x y

I X Y p x y

p x p y Î Î

=å å ×

X Y

.

· Relatii între entropii:

I(X,Y)=H(X)+H(Y)-H(X,Y) ;

I(X,Y)=H(X)-H(X|Y)=H(Y)-H(Y |X).

Surse de informatie

· O sursa discreta de informatii X este complet definita de :

- alfabetul finit, 1 2 { , , , } M X = x x Kx , cu M =|X | simboluri posibil a fi emise de sursa;

- distributia de probabilitati (f.m.p.) asociata simbolurilor emise :

( ) ( ) 1 2 1 2 ( ) ( ), ( ), , ( ) , , , M M pX=p x pxKpx =p pKp ;

- durata simbolurilor emise i t ;

Seminar nr. 1. Surse discrete Rodica Stoian, TTI 1, 2005/2006, II C + II F

2

- dependenta probabilistica între simboluri.

· O sursa discreta fara memorie (SDFM) este caracterizata de faptul ca simbolurile emise sunt

statistic independente, emiterea unui simbol nedepinzând de simbolurile anterioare.

Daca v.a. X1,X2,K,Xi,K,Xn, emise de sursa X, sunt independent distribuite (i.d.), sursa

discreta este fara memorie si avem relatia:

( ) ( ) ( ) 1 2 1 1 2 2

1 1

, , , , , ( )

n n

n n n i i i

i i

p x x x P X x X x X x P X x p x

= =

K = = =K = =Õ = =Õ .

Daca v.a. sunt nu numai independente dar si identic distribuite (i.i.d.), atunci:

( ) 1 2 , , n( )

n p xx Kx =p x .

· O sursa discreta cu memorie (SDCM) este caracterizata de faptul ca simbolurile emise sunt

dependente statistic, aparitia unui simbol depinzând de simbolurile precedente.

Presupunând o memorie de ordin 1, emiterea unui simbol depinde numai de simbolul anterior si

în termenii densitatii de probabilitate conditionata putem scrie:

1 2 1 1 ( | , ,..., ) ( | ) n n n n p x x x x p x x - - = ,

densitatea de probabilitate reunita a celor n v.a. emise putând fi scrisa în termenii distributiilor de

ordinul unu si doi:

1 2 1 1

2

( , , , ) ( ) ( | )

n

n i i

i

p xx x px p x x-

=

K = Õ .

· O sursa de informatii este stationara daca distributia de probabilitati p(x) nu depinde de

originea de timp.

· Parametrii informationali ai sursei X :

- Informatia proprie simbolului i x : 2 ( ) log ( ) i i i x = - p x , [biti/simbol].

- Entropia: [ ] 2 ( ) ( ) ( ) log ( )

i

i i i

x

H X E i x px p x

Î

= =-å ×

X

, [biti/simbol];

- Debitul de informatie : ( )

( ) t

H X

H X =

t

, [biti/sec];

- Redundanta: max( ) ( ) X R =H X -H X , [biti/simbol];

- Eficienta (Randamentul):

max

( )

( )

H X

H X

h= ;

- Redundanta relativa:

max

( )

1 1

( )

H X

H X

r= -h= - , unde max 2 H (X)= logM.