Contenu du cours
(cid:73) limites théoriques du taux de compression d’une source et du débit de trans-
mission dans un canal bruité,
(cid:73) algorithmes permettant d’atteindre de manière efficace ces limites.
1/15
Applications de la théorie de l’information
(cid:73) Transmission/stockage des données numériques
(cid:73) Cryptographie
(cid:73) Théorie des jeux
(cid:73) Bioinformatique
2/15
Système de communication
Source
(cid:45)
Codeur
(cid:63)
Canal
(cid:27)
Bruit
Utilisateur
(cid:27)
Décodeur
(cid:27)
Source : voix, musique, image (fixe ou animée), texte, . . .
Canal : radio, fil, fibre optique, support magnétique/optique,
Bruit : perturbations electromagnétiques, rayures, . . .
3/15
Codage de source et de canal
Source
(cid:45)
Codeur source
(cid:45)
Codeur canal
(cid:63)
Bruit
(cid:45)
Canal
Utilisateur
(cid:27)
Décod. source
(cid:27)
Décod. canal
(cid:27)
Efficacité : Pour faire parvenir une quantité donnée d’information à l’utilisa-
teur, utiliser le minimum de ressources.
Fiabilité : Restituer a l’utilisateur une information suffisamment fidele à celle
produite par la source.
Publicité
4/15
Codage source/canal
Problématique :
— Codage source : compresser efficacement une source donnée à un taux de
compression maximal. Ex :
x = x1 . . . xn, Prob(xi = 1) = p.
— Codage canal : transmettre efficacement le maximum d’information à travers
un canal bruité. Ex :
x = x1 . . . xn
canal(cid:32) y = y1 . . . yn, Prob(yi (cid:54)= xi) = p.
Une même quantité sert à quantifier cette limite : l’entropie.
5/15
Codage source/canal
Problématique :
— Codage source : compresser efficacement une source donnée à un taux de
compression maximal. Ex :
x = x1 . . . xn, Prob(xi = 1) = p.
⇒ compresser en une séquence de taille ≈ nh(p) bits.
— Codage canal : transmettre efficacement le maximum d’information à travers
un canal bruité. 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ême quantité sert à quantifier cette limite : l’entropie.
h(p)def= − p log2 p − (1 − p) log2(1 − p)
6/15
Entropie et séquences typiques
Un principe commun : se concentrer sur les réalisations 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éroter avec nh(p) bits les éléments de T et ne rien faire
pour les autres.
(cid:73) Codage canal :
log (nombre de mots pouvant être transmis) = nombre de bits d’information reçus
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érance.
log Prob(x)
(i)
= log Prob(x1) + · · · + log Prob(xn)
(ii)
≈ n (p log p + (1 − p) log(1 − p)) = −nh(p)(p.s.)
Publicité
⇒ Prob(x) ≈ 2−nh(p)(p.s.)
De manière générale 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 à répétition
Pour combattre les effets du bruit on ajoutera de la redondance. Par exemple, le
code à répétition de longueur 3 :
0 (cid:55)→ 000
1 (cid:55)→ 111
ou, plus généralement le code à répétition 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 à répétition
Si la probabilité d’erreur du canal p = 0.01 pour chaque symbole transmis, il se
produira 0 ou 1 erreur avec une probabilité
(1 − p)3 + 3p(1 − p)2 ≈ 0.9997
et il se produira 2 ou 3 erreurs avec une probabilité
3p2(1 − p) + p3 ≈ 3 × 10−4
Le symbole sera mal transmis avec une probabilité 3 × 10−4. Avec un code à
répétition de longueur 5, cette probabilité tombe à 10−5
10p3(1 − p)2 + 5p4(1 − p) + p5 ≈ 10−5
Ce code à un taux de transmission 0.2.
11/15
Rendement d’un code
Le code à répétition de longueur 3 a un taux de transmission 1/3 = 0.33 et corrige
une erreur.
Le code à répétition 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é d’erreur après
décodage.
Recherche du taux de transmission optimal : doit-il tendre vers 0 ?
Non ! Deuxieme théoreme de Shannon.
Notion de capacité C d’un canal.
12/15
Capacité du canal binaire symétrique
1
0.8
Publicité
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é
est
le
La
transmis-
taux de
sion maximal du code
à 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 à répétition ! ! !
13/15
Résultats importants du cours
Premier théorème 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éorème de Shannon (Codage de canal)
1. On peut transmettre de l’information de façon fiable en utilisant un
code correcteur d’erreur de taux de transmission inférieur à la capacité
du canal utilisé.
2. On ne peut pas faire mieux.
14/15
TD
Première séance : exercices sur feuille
Deuxième séance : TD en java ou langage de votre choix.
15/15