THEORIE DE L’INFORMATION & CODAGE
Sources d’Information de Markov
ABDI.M –ENSTTIC-Oran
VI-3 Sources d'information de Markov:
VI-3-1 Définitions:
Définition1:(Source d'information de Markov). Étant donné une chaîne de Markov Z0,Z1,Z2,...
et une fonction f : S ( appelé alphabet de la source).
Si l'état initiale Z0 correspond à la distribution de probabilité P=[P1 ,...,Pr ] ie; P{ Z0= Ej}= Pj j
Alors la séquence stationnaire Xn=f(Zn) n = 0,1,... est appelée source d'information de
Markov
de la chaîne Z0,Z1,Z2,...de la fonction f et, de la distribution P=[P1 ,...,Pr ]
Définition2:(Source régulière).Si la chaîne possède un vecteur de probabilités en régime stable,
alors la source résultante est appelée source d'information de Markov régulière.
Définition3:(Source de Markov unifilaire).
Soit une source d'information de Markov avec un ensemble d'états E={E1 ,E2 ,...,Ei ,...,Er}, un
alphabet , une fonction f : S et une distribution de probabilités P=[P1 ,...,Pr ].
Soit Ek1 , Ek 2 ,..., Eknk les états qui peuvent être atteintes en un seul pas à partir de E k ie; Pkj 0
La source est dite unifilaire si, pour chaque état E k , les lettres f Ek 1 ,..., f Ek 1 sont distinctes.
Exemple: Soit une source de Markov d'alphabet ={A,B}
Une telle source est :
1. Unifilaire si on prend: f(E1)=f(E4)=A et f(E2)=f(E3)=B
2. Non unifilaire si on prend : f(E1)=f(E2)=f(E4)=A et f(E3)=B
3. B
B
E2 B
A
A
B
A
E1 A E3 B
A
A B
A
A E4 A
A
Explication: Chaque état atteint directement à partir de E k , lui est associé une lettre distincte de
l'alphabet.
D'une façon équivalente, l'état à l'instant t et le symbole produit à l'instant t+1 déterminent l'état
à l'instant t+1.
VI-3-2 Entropie d'une source de Markov:
Définition: Étant donné une source de Markov unifilaire, et Ek1 , Ek 2 ,..., Eknk les états
directement atteints à partir de E k k=1,2,....,r
On définit alors l'entropie de l'état Ek par: H k H p k1 , p k 2 ..., p knk .
1
THEORIE DE L’INFORMATION & CODAGE
Sources d’Information de Markov
ABDI.M –ENSTTIC-Oran
Théorème: L'entropie d'une source de Markov unifilaire est donnée par
pk sont les probabilités stationnaires.
Remarque: Si la source est régulière, alors:
VI-3-3 Ordre d'une source:
Remarque: (Approximation d'une source d'information générale par une source d'ordre finie)
On aimerait voir la dépendance statistique du symbole Xn produit par une source d'information
des symboles précédents X1 , X2 ,... Xn-1 disparaître quand n tend vers l'infini.
Soit alors une source unifilaire dans laquelle la distribution de X n est déterminée par un nombre
(fini) M de symboles précédents Xn-1,...,Xn-M , une telle source est dite d'ordre fini ou de
mémoire finie.
Analysons la source de la figure suivante :
E1 E2
A
B
A B
B
E4 E3
f(E1)=f(E4)=A
A f(E2)=f(E3)=B
Description: Dans le diagramme on remarque que si f(E1)= alors, toutes les flèches entrant
l'état Ej sont marquées par .Les probabilités de transition ne sont pas spécifiées dans la
figure(sauf le fait que l'on suppose que Pij 0 si les états Si et Sj sont connectés directement).
Pour pouvoir conclure sur l'ordre d'une source de Markov, on peut dresser un tableau dans
lequel on met la liste de toutes les séquences possibles de deux ou plusieurs symboles, avec les
états finaux correspondant pour un état initial donné.
Exemple: Si Zt-3=E2 , Xt-2=B, Xt-1=A, Xt=A, alors Zt=E1.
Les cases marquées d'un trait correspondent à des transitions impossibles.
2
THEORIE DE L’INFORMATION & CODAGE
Sources d’Information de Markov
ABDI.M –ENSTTIC-Oran
Exemple: Si Zt-2=E3 alors, il est impossible que Xt-1=B et Xt=B
Xt-2 Xt-1 Xt Xt-1 Xt
Zt-3 AAA AAB ABA ABB BAA BAB BBA BBB Zt-2 AA AB BA BB
E1 E 1 E2 E1 E 3 E1 E2 E 4 - E1 E1 E2 E1 E3
E2 E 1 E2 E1 E 3 E1 E2 - - E2 E1 E2 E4 -
E3 E1 E2 E1 E 3 - - - - E3 E1 E2 - -
E4 E 1 E2 E1 E 3 E1 E2 E 4 - E4 E1 E2 E1 E3
Définition: On dira qu'une source unifilaire de Markov est d'ordre M si l'état Zt est déterminée
par les symboles Xt , Xt-1 ,..., Xt-M+1,mais pas par les symboles Xt , Xt-1 ,..., Xt-i pour i M-1
Conclusion: Pour déterminer l'ordre d'une source, on examine les états finaux associés aux
séquences de symboles de longueur 1,2,3,..., jusqu'à trouver un nombre M, tel que pour toutes
les séquences de longueur M, l'état final est indépendant de l'état initial .M sera alors l'ordre de
la source.
Le théorème suivant permet d'arrêter la recherche, lorsque l'ordre est infini.
Théorème: Si une source d'information de Markov unifilaire de r états , est d'ordre fini M
alors M 0,5 r(r-1)
Exemple: (source de Markov d'ordre infini).
B B
E3
f(E1)=f(E2)=A
f(E3)=B
A f(E4)=C
A
E1 E2
A C
C C
A
E4
Entropie d'une source d'ordre M: Si une source est d'ordre M, alors:
PX t t / X t 1 t 1 ,...,X t M t M
PX t t / X t 1 t 1 ,...,X t n t nn M
donc : H X H X t / X t 1 ,...,X t M
= H X t , X t 1 ,...,X t M H X t 1 ,...,X t M
J M +1 JM
J1:unigramme
J2:digramme
