Introduction la Théorie de l'Information et au Codage

De
Publié par


  • mémoire


Introduction à la Théorie de l'Information et au Codage Marc Lelarge 11 mai 2012

  • réciproque du théorème de codage de canal avec coût

  • algorithme de lempel-ziv

  • entropie conditionnelle

  • théorème de codage de canal

  • propriétés de l'entropie

  • propriétés générales des codes cycliques

  • canaux discrets sans mémoire

  • sources discrètes


Publié le : mardi 1 mai 2012
Lecture(s) : 111
Source : di.ens.fr
Nombre de pages : 108
Voir plus Voir moins

Introduction à la Théorie de
l’Information et au Codage
Marc Lelarge
22 mai 20122Table des matières
1 Suites typiques et compression de données avec pertes 7
1.1 Entropie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Ensemble typique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3 Codage de source avec perte . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4 Convexité et propriétés de l’entropie . . . . . . . . . . . . . . . . . . . . . 11
1.5 Entropie conditionnelle et Information mutuelle . . . . . . . . . . . . . . . 12
1.6 Test d’hypothèse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.7 Exercice : Définition axiomatique de l’entropie . . . . . . . . . . . . . . . . 15
2 Codage pour des sources discrètes 17
2.1 Mots code de longueur variable . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Un théorème de codage de source . . . . . . . . . . . . . . . . . . . . . . . 20
2.3 Un codage optimal : le codage de Huffman . . . . . . . . . . . . . . . . . . 21
2.3.1 Cas du code binaire :D =2 . . . . . . . . . . . . . . . . . . . . . . 21
2.3.2 Extension au casD>2 . . . . . . . . . . . . . . . . . . . . . . . . 23
2.4 Exercice : un test pour les codes non-ambigus . . . . . . . . . . . . . . . . 24
3 Codage de source universel 27
3.1 Codage universel pour une suite binaire . . . . . . . . . . . . . . . . . . . 27
3.2 Codage par automates à états finis . . . . . . . . . . . . . . . . . . . . . . 29
3.3 Algorithme de Lempel-Ziv . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.4 Exercice : optimalité de l’algorithme de Lempel-Ziv pour une source sans
mémoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4 Propriétés de l’entropie et de l’information mutuelle 37
4.1 Rappels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2 Règles de la chaîne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.3 Inégalités de convexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.3.1 Inégalité logsum et applications . . . . . . . . . . . . . . . . . . . . 41
4.4 Data Processing inequality . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.5 Inégalité de Fano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.6 Exercice : Lien entre théorie de l’information et courses de chevaux . . . . 44
34 TABLE DES MATIÈRES
5 Canaux discrets sans mémoire et leurs fonctions capacité-coût 47
5.1 Définitions et codes sans erreur . . . . . . . . . . . . . . . . . . . . . . . . 47
5.2 Inégalité de Fano et réciproque du théorème de codage de canal . . . . . . 49
5.3 La fonction capacité-coût . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.4 Réciproque du théorème de codage de canal avec coût . . . . . . . . . . . 53
5.5 Le théorème de codage de canal . . . . . . . . . . . . . . . . . . . . . . . . 54
5.6 Exercice : Canal avec feedback . . . . . . . . . . . . . . . . . . . . . . . . 58
6 Sources sans mémoire et leurs fonctions taux-distorsion 61
6.1 La fonction taux-distorsion . . . . . . . . . . . . . . . . . . . . . . . . . . 61
6.2 Théorème de codage de source de Shannon . . . . . . . . . . . . . . . . . . 64
7 Le théorème de codage source-canal 67
8 Codes linéaires 71
8.1 Décodage par maximum de vraisemblance . . . . . . . . . . . . . . . . . . 71
8.2 Géométrie de Hamming . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
8.3 Codes linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
8.4 Codes de Hamming (binaires) . . . . . . . . . . . . . . . . . . . . . . . . . 74
8.5 Décodage du syndrome . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
9 Codes cycliques 77
9.1 Propriétés générales des codes cycliques . . . . . . . . . . . . . . . . . . . 77
9.2 Classification des codes binaires cycliques de longueur 7 . . . . . . . . . . 81
10 Corps finis 83
10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
10.2 Polynômes minimaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
10.3 Comment trouver des polynômes irréductibles . . . . . . . . . . . . . . . . 88
10.4 Exercice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
11 Codes BCH (Bose-Chaudhuri-Hocquenghem) 91
11.1 Code de Hamming cycliques . . . . . . . . . . . . . . . . . . . . . . . . . . 91
11.2 Codes BCH corrigeant 2 erreurs . . . . . . . . . . . . . . . . . . . . . . . . 92
n11.3 Facteurs deX 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
11.4 Codes BCH corrigeant t erreurs . . . . . . . . . . . . . . . . . . . . . . . . 95
11.5 Codes de Reed-Solomon . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
11.6 Le polynôme de Mattson-Solomon . . . . . . . . . . . . . . . . . . . . . . 98
11.7 Décodage de codes BCH . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
11.8 Forme usuelle des identités de Newton et décodage de codes BCH . . . . . 101
11.9 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105TABLE DES MATIÈRES 5
Notations
Pour des variables aléatoires (v.a.) discrètes X et Y à valeurs dansX etY
resp., on utilisera les notations suivantes pour x2X et y2Y :
p(x) = P(X =x)
p(y) = P(Y =y)
p(x;y) = P(X =x;Y =y)
p(xjy) = P(X =xjY =y) =p(x;y)=p(y):
Lorsquecesnotationssontambigues,onpourraécrirep (x);p (y);p (x;y);p (xjy).X Y X;Y XjY6 TABLE DES MATIÈRESChapitre 1
Suites typiques et compression de
données avec pertes
1.1 Entropie
1Unesource (discrète) émetune suitede v.a.fUg àvaleurs dansunensemblei i=1
finiU appelé l’alphabet de la source. Si les U sont indépendants et identiquementi
distribués (i.i.d.) de loi P, la source est dite sans mémoire de distribution P.
Définition 1.1.1 Soit U une variable aléatoire à valeurs dans un ensemble fini
U, de distribution de probabilité :
p(u) =P(U =u); u2U:
Son entropie est, par définition, la quantité
X
H(U) = E[log(p(U))] = p(u)logp(u);
u2U
avec la convention 0log0 = 0.
Le choix de la base du logarithme correspond à un choix d’unité. Sauf mention du
contraire, on choisit par défaut la base 2. L’entropie s’exprime alors en bits.
78CHAPITRE1. SUITESTYPIQUESETCOMPRESSIONDEDONNÉESAVECPERTES
1.2 Ensemble typique
nDéfinition 1.2.1 Pour n2 et > 0, l’ensemble typique A par rapport à la
ndistribution p(u) est l’ensemble des suites (u ;:::;u )2U telles que :1 n
n(H(U)+) n(H(U) )2 p(u ;:::;u ) 2 :1 n
Théorème 1.2.1 Pour tout n2 , > 0, on a :
(n)
1. Si (u ;:::;u )2A alors1 n
1
H(U) logp(u ;:::;u )H(U)+:1 n
n
2. Pour tout > 0 et pour n suffisament grand, on a :

(n) (n)
P A =P (U ;:::;U )2A 1 :1 n
(n)
3. le cardinal de l’ensemble A est borné par :

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.