Théorie de la compression et transmission d'information dans canaux bruyants

(cid:27)

D´ecod. source

(cid:27)

D´ecod. canal

(cid:27)

Efficacit´e : Pour faire parvenir une quantit´e donn´ee d’information `a l’utilisa-

teur, utiliser le minimum de ressources.

Fiabilit´e : Restituer a l’utilisateur une information suffisamment fidele `a celle

produite par la source.

4/15

Codage source/canal

Probl´ematique :

— Codage source : compresser efficacement une source donn´ee `a un taux de

compression maximal. Ex :

x = x1 . . . xn, Prob(xi = 1) = p.

— Codage canal : transmettre efficacement le maximum d’information `a travers

un canal bruit´e. Ex :

x = x1 . . . xn

canal(cid:32) y = y1 . . . yn, Prob(yi (cid:54)= xi) = p.

Une mˆeme quantit´e sert `a quantifier cette limite : l’entropie.

5/15

Codage source/canal

Probl´ematique :

— Codage source : compresser efficacement une source donn´ee `a un taux de

compression maximal. Ex :

x = x1 . . . xn, Prob(xi = 1) = p.

⇒ compresser en une s´equence de taille ≈ nh(p) bits.

— Codage canal : transmettre efficacement le maximum d’information `a travers

un canal bruit´e. Ex :

x = x1 . . . xn

canal(cid:32) y = y1 . . . yn, Prob(yi (cid:54)= xi) = p.

⇒ transmettre ≈ n(1 − h(p)) bits d’information.

Une mˆeme quantit´e sert `a quantifier cette limite : l’entropie.

h(p)def= − p log2 p − (1 − p) log2(1 − p)

6/15

Entropie et s´equences typiques

Un principe commun : se concentrer sur les r´ealisations typiques

T = {x; |x| ≈ pn}

Prob(x ∈ T ) ≈ 1

|T | ≈ 2nh(p)

log2 |T | ≈ Entropie

7/15

{0,1}nT(cid:73) Codage source : num´eroter avec nh(p) bits les ´el´ements de T et ne rien faire

pour les autres.

(cid:73) Codage canal :

log (nombre de mots pouvant ˆetre transmis) = nombre de bits d’information re¸cus

8/15

2 mots pouvant être transmisn(1−h(p))mot transmisensemble de réalisationstypiques correspondantau mot transmis{0,1}ntaille des boules : 2nh(p)Entropie

Formule s’explique par deux faits

(i) log transforme un produit en somme,

(ii) concentration de la somme de v.a. i.i.d. autour de son esp´erance.

log Prob(x)

(i)

= log Prob(x1) + · · · + log Prob(xn)

(ii)

≈ n (p log p + (1 − p) log(1 − p)) = −nh(p)(p.s.)

⇒ Prob(x) ≈ 2−nh(p)(p.s.)

De mani`ere g´en´erale pour une v.a.d. X prenant ses valeurs dans A :

Entropie(X)def= −

(cid:88)

a∈A

Prob(X = a) log Prob(X = a).

9/15

Code `a r´ep´etition

Pour combattre les effets du bruit on ajoutera de la redondance. Par exemple, le

code `a r´ep´etition de longueur 3 :

0 (cid:55)→ 000

1 (cid:55)→ 111

ou, plus g´en´eralement le code `a r´ep´etition de longeur 2m + 1.

0 (cid:55)→

1 (cid:55)→

2m+1

(cid:122) (cid:125)(cid:124) (cid:123)

0 . . . 0

2m+1

(cid:122) (cid:125)(cid:124) (cid:123)

1 . . . 1

10/15

Code `a r´ep´etition

Si la probabilit´e d’erreur du canal p = 0.01 pour chaque symbole transmis, il se

produira 0 ou 1 erreur avec une probabilit´e

(1 − p)3 + 3p(1 − p)2 ≈ 0.9997

et il se produira 2 ou 3 erreurs avec une probabilit´e

3p2(1 − p) + p3 ≈ 3 × 10−4

Le symbole sera mal transmis avec une probabilit´e 3 × 10−4. Avec un code `a

r´ep´etition de longueur 5, cette probabilit´e tombe `a 10−5

10p3(1 − p)2 + 5p4(1 − p) + p5 ≈ 10−5

Ce code `a un taux de transmission 0.2.

11/15

Rendement d’un code

Le code `a r´ep´etition de longueur 3 a un taux de transmission 1/3 = 0.33 et corrige

une erreur.

Le code `a r´ep´etition de longueur 5 a un taux de transmission 1/5 = 0.2 et corrige

deux erreurs.

En diminuant le taux de transmission, on fait baisser la probabilit´e d’erreur apr`es

d´ecodage.

Recherche du taux de transmission optimal : doit-il tendre vers 0 ?

Non ! Deuxieme th´eoreme de Shannon.

Notion de capacit´e C d’un canal.

12/15

Capacit´e du canal binaire sym´etrique

1

0.8

0.6

0.4

0.2

0

0

C = 1 + p log2(p) + (1 − p) log2(1 − p)

0.2

0.4

p

0.6

0.8

1

capacit´e

est

le

La

transmis-

taux de

sion maximal du code

`a utiliser pour trans-

mettre de l’informa-

tion (cid:28) dans de bonnes

conditions (cid:29).

ex. C(0.01) =

Par

Il y a donc

0.919.

moyen de faire (beau-

coup) mieux que le

code `a r´ep´etition ! ! !

13/15

R´esultats importants du cours

Premier th´eor`eme de Shannon (Codage de source)

1. On peut coder toute source en utilisant un nombre de bits par lettre

aussi proche que l’on veut de son entropie.

2. On ne peut pas faire mieux.

Second th´eor`eme de Shannon (Codage de canal)

1. On peut transmettre de l’information de fa¸con fiable en utilisant un

code correcteur d’erreur de taux de transmission inf´erieur `a la capacit´e

du canal utilis´e.

2. On ne peut pas faire mieux.

14/15

TD

Premi`ere s´eance : exercices sur feuille

Deuxi`eme s´eance : TD en java ou langage de votre choix.

15/15