Chapitre 5 • Pro ces sus sto chas tiques et pro gram ma tion…
220
EXER CICES
I Chaînes de MaRKOV
*5.1 Qua lité d’un canal de trans mis sion
On consi dère un canal qui trans met, de façon conti nue, des bits d’infor ma tion. Mais ce
canal peut être affecté par des per tur ba tions qui altèrent les bits trans mis. Les erreurs
se pro duisent en géné ral par groupes, c’est àdire que lors qu’un bit est altéré par une
per tur ba tion, la pro ba bi lité que le bit sui vant soit aussi altéré est impor tante. Plus pré ci
sé ment, sup po sons qu’à un cer tain moment le der nier bit trans mis ait été cor rect : le bit
sui vant sera alors trans mis cor rec te ment avec la pro ba bi lité p 0 et altéré avec la pro ba bi
lité q 0 (p 0 1 q 0 5 1) ; sup po sons main te nant que l’avant der nier bit trans mis était cor rect
et que le der nier bit trans mis est faux : le bit sui vant sera trans mis cor rec te ment avec la
pro ba bi lité p 1 et altéré avec la pro ba bi lité q 1 1 p 1 1 q 1 5 12 ; ainsi de suite : si depuis le
der nier bit trans mis cor rec te ment, k bits erro nés ont été trans mis, la pro ba bi lité que le
bit sui vant soit cor rect est p k et qu’il soit faux, q k 1 p k 1 q k 2 5 1 où 0 < k < N.
Lorsque N bits consé cu tifs sont erro nés depuis le der nier trans mis cor rec te ment,
la pro ba bi lité que le sui vant soit cor rect est comme plus haut p N ; mais si le bit sui
vant est faux (pro ba bi lité q N ) une ré initialisation fait que tout se pas sera ensuite
comme si l’on venait de trans mettre un bit faux après un bit exact.
1. Modé li ser ce canal à l’aide d’une chaîne de Markov com por tant n 1 1
états, E 0 , E 1 , c , E k , c , E N : dans l’état E k , depuis le der nier bit trans mis
cor rec te ment k bits erro nés ont été trans mis.
Tra cer le graphe des tran si tions entre états lors de la trans mis sion d’un bit,
et le valuer.
À quel arc cor res pond la ré initialisation ? À cet arc près, dans quel pro
blème clas sique avez vous ren contré des graphes de ce type ?
2. Pour N 5 3, sachant que p 0 5 0,95 p 1 5 0,20 p 2 5 0,15 p 3 5 0,10,
a) don ner la matrice M des pro ba bi li tés de tran si tion pour une trans mis sion ;
b) en sup po sant qu’ini tia le ment un bit ait été trans mis cor rec te ment, don
ner le vec teur p(0) des pro ba bi li tés d’états ; cal cu ler la pro ba bi lité pour que
les deux sui vants soient faux, à l’aide de M, p(0), p(1) et p(2).
3. a) La chaîne pré cé dente admet elle un régime per manent, au bout d’un
grand nombre de trans mis sions de bits, indé pen dant de l’état ini tial ? (Jus
ti fier en détail votre réponse.)
b) Si oui, cal cu ler numé ri que ment les pro ba bi li tés p
*
k 1 0 < k < 32 de
chaque état en régime per manent (sup pri mer la pre mière équa tion qui est
redon dante ; expri mer les p
*
k en fonc tion de p
*
1 , puis cal cu ler p
*
1 ).
c) En déduire la pro ba bi lité pour qu’une trans mis sion de bit prise au hasard en
régime per manent soit cor recte. Que pensez vous de la qua lité de ce canal ?
220
EXER CICES
I Chaînes de MaRKOV
*5.1 Qua lité d’un canal de trans mis sion
On consi dère un canal qui trans met, de façon conti nue, des bits d’infor ma tion. Mais ce
canal peut être affecté par des per tur ba tions qui altèrent les bits trans mis. Les erreurs
se pro duisent en géné ral par groupes, c’est àdire que lors qu’un bit est altéré par une
per tur ba tion, la pro ba bi lité que le bit sui vant soit aussi altéré est impor tante. Plus pré ci
sé ment, sup po sons qu’à un cer tain moment le der nier bit trans mis ait été cor rect : le bit
sui vant sera alors trans mis cor rec te ment avec la pro ba bi lité p 0 et altéré avec la pro ba bi
lité q 0 (p 0 1 q 0 5 1) ; sup po sons main te nant que l’avant der nier bit trans mis était cor rect
et que le der nier bit trans mis est faux : le bit sui vant sera trans mis cor rec te ment avec la
pro ba bi lité p 1 et altéré avec la pro ba bi lité q 1 1 p 1 1 q 1 5 12 ; ainsi de suite : si depuis le
der nier bit trans mis cor rec te ment, k bits erro nés ont été trans mis, la pro ba bi lité que le
bit sui vant soit cor rect est p k et qu’il soit faux, q k 1 p k 1 q k 2 5 1 où 0 < k < N.
Lorsque N bits consé cu tifs sont erro nés depuis le der nier trans mis cor rec te ment,
la pro ba bi lité que le sui vant soit cor rect est comme plus haut p N ; mais si le bit sui
vant est faux (pro ba bi lité q N ) une ré initialisation fait que tout se pas sera ensuite
comme si l’on venait de trans mettre un bit faux après un bit exact.
1. Modé li ser ce canal à l’aide d’une chaîne de Markov com por tant n 1 1
états, E 0 , E 1 , c , E k , c , E N : dans l’état E k , depuis le der nier bit trans mis
cor rec te ment k bits erro nés ont été trans mis.
Tra cer le graphe des tran si tions entre états lors de la trans mis sion d’un bit,
et le valuer.
À quel arc cor res pond la ré initialisation ? À cet arc près, dans quel pro
blème clas sique avez vous ren contré des graphes de ce type ?
2. Pour N 5 3, sachant que p 0 5 0,95 p 1 5 0,20 p 2 5 0,15 p 3 5 0,10,
a) don ner la matrice M des pro ba bi li tés de tran si tion pour une trans mis sion ;
b) en sup po sant qu’ini tia le ment un bit ait été trans mis cor rec te ment, don
ner le vec teur p(0) des pro ba bi li tés d’états ; cal cu ler la pro ba bi lité pour que
les deux sui vants soient faux, à l’aide de M, p(0), p(1) et p(2).
3. a) La chaîne pré cé dente admet elle un régime per manent, au bout d’un
grand nombre de trans mis sions de bits, indé pen dant de l’état ini tial ? (Jus
ti fier en détail votre réponse.)
b) Si oui, cal cu ler numé ri que ment les pro ba bi li tés p
*
k 1 0 < k < 32 de
chaque état en régime per manent (sup pri mer la pre mière équa tion qui est
redon dante ; expri mer les p
*
k en fonc tion de p
*
1 , puis cal cu ler p
*
1 ).
c) En déduire la pro ba bi lité pour qu’une trans mis sion de bit prise au hasard en
régime per manent soit cor recte. Que pensez vous de la qua lité de ce canal ?