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.
Documentul este oferit gratuit,
trebuie doar să te autentifici in contul tău.