Surse cu memorie ergodice

Surse cu memorie ergodice

Sa presupunem o sursa cu memorie de ordin m, ce poate furniza n mesaje si sa notam cu p₁(t), p₂(t), p_nm(t), probabilitatile studiilor la momentul t. Matricea ญญญญญ[P(t)] = [p₁(t), p₂(t), p_nm(t)] se numeste matricea distributiei probabilitatilor starilor.

Se pune problema ca daca se noteaza cu S_i starea se considera nodurile in graf, starile surselor, iar transmitantele ramurilor orientate - probabilitatile de trecere dintr-o stare in alta.

Astfel, daca se considera o sursa cu memorie de ordin m ce are n mesaje si se considera starea S_k formata din succesiunea s_k1 s_k2 s_km atunci prin p(s_j| s_k1 s_k2 s_km) = p(s_j | S_k) se intelege probabilitatea de a se limita mesajul s_j din starea S_k, sursa trecand in alta stare S_j s_k1 s_k2 s_km s_j.

Pentru simplificarea scrierii se va nota cu p_kj probabilitatea de trecere din starea S_k in starea S_j. In felul acesta, se poate reprezenta situatia:

Sj

Sk

Figura 1.6.

In mod analog se poate realiza descrierea surselor cu memorie folosind calculul matriceal, obtinandu-se pentru fiecare sursa cu memorie o matrice patratica, in care fiecare linie a acesteia reprezinta probabilitatile conditionate de aceeasi stare. Daca sursa este cu memorie de ordin m si poate furniza n mesaje, cum fiecare linie contine probabilitatile conditionate de aceeasi stare inseamna ca matricea va avea un numar de lini = n^m.

Deoarece, dintr-o stare se poate ajunge in una din starile posibile din cele n^m, inseamna ca numarul de coloane a matricii respective este tot n^m, deci matricea este patrata. Mai mult, deoarece dintr-o anumita stare, se trece cu certitudine in una din cele n^m stari, insemnand ca suma probabilitatilor conditionale de pe fiecare linie a unei matrice astfel intocmite este egala cu 1, motiv pentru care matricea se numeste stocastica.

Daca elementele unei astfel de matrice sunt invariante in timp, sursa cu memorie se numeste stationar. Pentru amplificarea descrierii surselor cu memorie cu ajutorul grafurilor la momentul t+1 a unei surse cu memorie de ordin m, sa se calculeze probabilitatea acestei stari, adica p_i(t+1).

Probabilitatea ca suma sa treaca in starea S_i la momentul t va fi egala cu produsul dintre probabilitatea ca sursa sa se gaseasca in starea S_j la momentul t, notat p_j(t) si probabilitatea de trecere p_ji, din starea S_j in starea S_i.

Deoarece insa in starea S_i se poate ajunge din cele n^m stari posibile, inseamna ca probabilitatea starii S_i la momentul t+1, se calculeaza cu relatia:

(1.18)

In relatia (1.18) s-ar putea ca o parte din probabilitatile p_ji sa fie nule, ceea ce semnifica faptul ca din starea respectiva nu se poate ajunge in starea S_i (de exemplu de a starea S_i la starea S_n).

Daca se noteaza cu: matricea distributiei probabilitatilor starilor la momentul (t+1) si cu

numita matrice de tranzitie atasata sursei cu memorie, atunci relatia (1.18) se poate scrie compact sub forma matricelor:

[P(t+1)] = [P(t)][T] (1.19)

Daca in relatia (2.2) se considera succesiv t=0, t=1, se obtine succesiv: [P(1)] = [P(0)][T]

prin [P(0)] intelegandu-se matricea distributiei probabilitatilor starilor initiale ale surselor cu memorie, iar prin [P(1)], aceiasi matrice la momentul urmator; Analog, t=1 T

[P(2)] = [P(1)][T] = [P(0)][T]²

[P(3)] = [P(2)][T] = [P(0)][T]³

..

[P(t)] = [P(0)][T] = [P(0)][T]^t (1.20)

Prin definitie o sursa cu memorie se numeste ergodica. daca , unde [k] are toate elementele finite, invariante in timp.

Asa cum se va vedea, proprietatea de ergodicitate este foarte importanta, deoarece daca o sursa se doreste a fi neergodica nu i se poate calcula entropia, deci nu i se poate calcula cantitatea medie de informatie ce o poate furniza . Din fericire, foarte multe surse reale sunt ergodice.

Pentru a stabili daca o sursa este ergodica sau nu este greu a folosi relatia de definitie, motiv pentru care se folosesc metode echivalente, dar mai usoare si mai operante (sa ridicam la " dificil, nu este operant).

Se reaminteste ca daca o functie f(t) = 0, t < 0 si daca | f(t) | C e^at    C,a constante arbitrare, atunci transformata Laplace a f(t), . Se numeste esantionare a functiei f(t), in multimea f(t) cu , unde d(t) este distributia Dirac, d_T(t) = functie d periodica.

Daca notam f^*(t) functia esantionata, aceasta este data de:

Transformata Laplace a functiei esantionate (discretizate) poarta denumirea de transformata Laplace discreta:

Prin definitie se numeste redundanta unei surse, diferenta dintre entropia maxima posibila a unei surse si entropia sa reala.

Notand R_S redundanta sursei, rezulta:

R_S = max [H(s)] - H(S)

Uneori se foloseste redundanta relativa r_S

Fizic, redundanta ar masura cu cat se agate o sursa reala, in privinta transmiterii informatiei medii pe mesaj, fata de transmitere a informatiei maxime posibile pe mesaj.