Seminarii TTI

1. Obiectivul lucrarii

În aceasta lucrare se studiaza sursele discrete Markov cu memorie de ordinul întâi cu 2, 3 si 4 stari si modul în care acestea evolueaza pornind de la conditii impuse. De asemenea, în lucrare sunt prezentate exemple de stationarizare a surselor cu doua si trei stari.

2. Introducere teoretica

O sursa discreta de informatie debiteaza mesaje la momente discrete de timp, fiecare mesaj fiind reprezentat printr-un numar finit de simboluri. Multimii de simboluri i se pune în corespondenta o multime finita de semnale sub forma de impulsuri. Rata de emisie a unei surse discrete este deci finita.

Sursa discreta se caracterizeaza prin simbolurile x1,x2,...,xi,...., pe care le emite, cuvintele care se constituie cu aceste simboluri în numar finit, alfabetul aferent ca totalitatea simbolurilor si limba sursei ca totalitatea cuvintelor pe care le poate debita sursa în alfabetul sau.

O sursa discreta cu memorie furnizeaza câte un simbol a carui probabilitate de aparitie depinde de simbolul precedent sau de un sir de simboluri precedente, numarul acestora determinând ordinul memoriei.

O sursa discreta stationara sau omogena genereaza simboluri ale caror probabilitati nu depind de originea timpului, ci doar de pozitiile lor relative. Probabilitatile sunt invariante la orice translatie de-a lungul sirului.

Într-o diagrama a tranzitiilor de stare, nodurile reprezinta starile, iar arcele, tranzitiile. Arcele sunt etichetate prin probabilitatile conditionate asociate tranzitiilor p(xi/xj).

Daca un simbol este conditionat de mai multe simboluri precedente, numarul de stari creste. Astfel, o sursa binara care furnizeaza simboluri conditionate de câte doua simboluri precedente se caracterizeaza prin patru stari corespunzatoare grupurilor de câte doua simboluri precedente: S1 => 00, S2 => 01, S3 => 10 si S4 => 11. Se spune ca starii S1 i se asigneaza dubletul 00, starii S2 = 01 etc.

O sursa cu memorie de ordinul m este o sursa cu constrângeri probabilistice, distributia de probabilitate având elemente de forma:

,

adica emisia unui simbol este conditionata de m simboluri precedente. Daca alfabetul sursei contine D simboluri, o sursa cu memorie de ordinul m are stari.

Starii sursei i se asigneaza secventa de m simboluri:

.

Daca emiterea unui simbol de iesire este conditionata numai de starea precedenta, sursa poate fi modelata cu ajutorul unui lant Markov finit si se numeste sursa Markov.

Un lant Markov finit este definit ca un proces aleator discret , unde elementele , numite stari, sunt variabile aleatoare discrete care iau valori în alfabetul starilor , iar dependenta satisface conditia Markov:

Aceasta înseamna ca probabilitatea ca o variabila aleatoare sa ia valoarea unei stari, conditionata de un trecut infinit, este egala cu probabilitatea conditionata de cel mai recent trecut (ultima stare parasita).

Daca probabilitatea de trecere dintr-o stare în alta nu depinde de timp, lantul Markov este omogen (stationaritatea conditiei Markov).

O sursa Markov consta într-un lant Markov intern împreuna cu o functie care aplica alfabetul starilor în alfabetul sursei.

O sursa de informatie Markov este un sir de v.a. discrete