Surse discrete cu memorie (modele Markov)

In cazul modelului matematic de sursa discreta cu memorie, probabilitatea de furnizare a unui mesaj oarecare depinde de probabilitatea mesajelor furnizate anterior. O sursa cu memorie se spune ca este de ordin m, daca probabilitatea de furnizare a unui mesaj, depinde de probabilitatile de furnizare a m mesaje anterioare.

Se numeste stare la un moment dat a unei surse cu memorie de ordin m, succesiunea ultimilor m mesaje furnizate anterior momentului considerat. Conform acestei definitii, daca o sursa cu memorie de ordin m are n mesaje numarul de stari va fi n^m, deoarece fiecare stare este caracterizata de m mesaje fiecare mesaj putand fi oricare din cele n posibile.

Studiul surselor cu memorie se poate realiza relativ simplu, fie folosind grafurile, fie calculul matriceal. In cazul folosirii grafurilor, pentru descrierea surselor cu memorie sau matriceal, se considera sursa cu memorie de ordin doi (m=2) a sursei cu distributia , adica pentru n=2.

Inseamna ca sursa cu memorie respectiva va crea n^m=2²=4 stari, notate: S₁ s₁ s₁; S₂ s₁s₂; S₃ s₂s₁; S₄ s₂s₂;

Daca, de exemplu, din starea S₁ s-ar furniza mesajul s₁, cu probabilitatea p(s₁|S₁) sursa ar tece : s₁s₁:s₁ = s₁s₁ = S₁ (tot in S₁). Daca din aceeasi stare S₁ s-ar furniza s₂ cu p(s₁|S₁) sursa va trece in starea S₂ [s₁s₁:s₂ s₁s₂ S₂]. Conform conventiei de scriere simplificata, inseamna ca putem scrie ca p(s₁|S₁) = p₁₁ respectiv p(s₂|S₁) = p₁₂.

Graful atasat unei astfel de surse are topologia (structura):