Scribd
Importer
6 vues2 pages

Solutions Exercices Théorie de l'Information

Ce document contient les solutions à quatre exercices portant sur la théorie de l'information et du codage. Les exercices concernent notamment les canaux à mémoire, la fonction capacité-coût d'un canal à effacement, la construction d'un code pour un canal particulier, et la relation entre la distance de Hamming et l'ensemble T dans la preuve du théorème du codage canal pour un canal binaire symétrique.

Transféré par

Malick THIAM
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
6 vues2 pages

Solutions Exercices Théorie de l'Information

Ce document contient les solutions à quatre exercices portant sur la théorie de l'information et du codage. Les exercices concernent notamment les canaux à mémoire, la fonction capacité-coût d'un canal à effacement, la construction d'un code pour un canal particulier, et la relation entre la distance de Hamming et l'ensemble T dans la preuve du théorème du codage canal pour un canal binaire symétrique.

Transféré par

Malick THIAM
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Solutions des Exercices du cours de Théorie de l’Information et Codage

cours 6 du 22 mars 2011.


1. Canal avec mémoire. Soit A P = (aij ) une matrice stochastique r × r. Soit p le vecteur de
probabilité stable par A: pj = i pi aij . Soit Z1 , Z2, . . . la chaı̂ne de Markov associée à A avec
Z1 de loi p. L’entropie de la chaı̂ne est définie par
1
H = lim H(Z1 , . . . , Zn ).
n→∞ n
On considère le canal avec alphabets X = Y = {0, 1, . . . , r − 1} donné par

Yi = Xi + Zi (mod) r.
n
On définit alors Cmax = max{I(X; Y)} où X est une source test de dimension n. Montrer que
la capacité du canal vaut
Cn
Cmax = sup max = log r − H.
n
• Pour n fixé, on a I(X; Y) = H(Y)−H(Y|X) = H(Y)−H(Z). En prenant les composantes
n
de X iid uniformément distribués sur AX , on obtient: Cmax = n log r − H(Z1, . . . , Zn ) et
donc le résultat demandé.

2. Calculer la fonction capacité-coût du canal à effacement:


 
q p 0
Q= , b(0) = 0, b(1) = 1.
0 p q

• On a βmin = 0 et C(0) = 0. Pour 0 ≤ β ≤ βmax , un petit calcul donne C(β) = qH(β) et


donc βmax = 1/2 et Cmax = q.

3. Pour le canal avec X = {0, 1/2, 1} et Y = {0, 1},


 
1 0
Q =  1/2 1/2  , et b(0) = b(1) = 1, b(1/2) = 0,
0 1

expliciter un code qui satisfait les conditions du théorème de codage de canal.

• Avec les notations du cours, on prend β0 ≥ 0 puis β > β0 , R < min(β0 , 1) et ǫ > 0. On
choisit maintenant n ≥ 1/(min(β, 1) − R) et le code C = {(x1 , . . . , x⌈Rn⌉ , 12 , . . . , 12 )} de
longueur n avec la règle de décodage vue en cours.

4. Dans le cas du canal binaire symétrique, montrer que l’ensemble T défini dans la preuve du
Théorème 5.4 est de la forme T = {(x, y), dH (x, y) ≤ r}, où dH est la distance de Hamming.
Exprimer r en fonction de n, R′ et ǫ la probabilité d’erreur du canal. (On supposera p(x =
0) = p(x = 1) = 1/2.)

1
• On a I(x; y) = log2 (p(y|x)p(y)−1) de plus: p(y|x) = ǫdH (x,y) (1 − ǫ)n−dH (x,y) et d’après
l’hypothèse faite sur x, p(y) = 2−n . On a donc

I(x; y) = dH (x, y) log ǫ + (n − dH (x, y)) log(1 − ǫ) + n,

et donc:
log(1 − ǫ) + 1 − R′
r=n .
log(1 − ǫ) − log ǫ

Vous aimerez peut-être aussi