Théorie de l'information

Support de cours de th´eorie de l’information

et codage correcteur d’erreurs

Enseignant : Hatem Boujemˆaa

SUPCOM, Septembre 2005

ii

Table des mati`eres

Table des mati`eres v

Table des figures viii

1 Th´eorie de l’information 1

1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 Quantit´e d’information et entropie d’une source . . . . . . . . . . . . . . . . . . . . . . 1

1.3 Information mutuelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.3.1 Entropie conditionnelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.3.2 Information mutuelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.4 Th´eor`eme de Shannon pour le codage de source . . . . . . . . . . . . . . . . . . . . . . 4

1.4.1 Codage de source sans perte . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.4.2 Codage de source avec perte . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.5 Th´eor`eme de Shannon pour le codage de canal . . . . . . . . . . . . . . . . . . . . . . . 6

2 Le codage de source 9

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.2 Caract´eristiques des codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.2.1 Le th´eor`eme de Mac Millan . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.2.2 Le th´eor`eme de Kraft . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.3 Construction des codes instantan´es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.4 Construction des codes optimaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.4.1 Quelques conditions n´ecessaires sur les longueurs optimales . . . . . . . . . . . 12

2.4.2 Les longueurs optimales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.4.3 L’algorithme de Huffman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.5 TD 1 : Codage de source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

iv TABLE DES MATI ` ERES

3 Les codes en bloc lin´eaires 17

3.1 G´en´eralit´es sur les codes correcteurs et d´etecteurs d’erreurs . . . . . . . . . . . . . . . . 17

3.2 D´efinition des codes en bloc lin´eaires . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.3 La matrice g´en´eratrice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.4 Code dual et matrice de contrˆole de parit´e . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.5 Principe de la d´etection et de la correction d’erreurs . . . . . . . . . . . . . . . . . . . . 21

3.5.1 D´etection d’erreurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3.5.2 R´egle de d´ecodage et de correction d’erreurs . . . . . . . . . . . . . . . . . . . 22

3.5.3 Pouvoir de correction et de d´etection d’erreurs . . . . . . . . . . . . . . . . . . 23

3.5.4 D´etermination de d(C) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

3.6 Exemple de codes en bloc lin´eaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.6.1 Le code de parit´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.6.2 Le code `a r´ep´etition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.6.3 Le code de Hamming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.6.4 Le code `a longueur maximale . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3.7 Performances des codes en bloc lin´eaires . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3.8 TD 2 : Les codes en bloc lin´eaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

4 Les codes cycliques 33

4.1 D´efinition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.2 Forme syst´ematique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

4.3 D´ecodage des codes cycliques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

4.4 Exemples de codes cycliques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

4.4.1 Les codes BCH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

4.4.2 Les codes de Golay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

4.4.3 Les codes de Reed Solomon . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

4.5 TD 3 : Les codes cycliques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

5 Les codes convolutifs 39

5.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

5.2 Repr´esentation des codes convolutifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

5.2.1 Le diagramme en arbre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

5.2.2 Le diagramme d’´etat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

5.2.3 Le diagramme en treillis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

5.3 D´ecodage : Algorithme de Viterbi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

Table des mati`eres v

5.3.1 Le crit`ere de Maximum de Vraisemblance : . . . . . . . . . . . . . . . . . . . . 42

5.3.2 L’algorithme de Viterbi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

5.4 Performances th´eoriques des codes convolutifs . . . . . . . . . . . . . . . . . . . . . . 49

5.4.1 Fonction de transfert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

5.4.2 Probabilit´e d’occurrence d’un premier ´ev´enement d’erreur . . . . . . . . . . . . 50

5.4.3 Probabilit´e d’erreur binaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

5.5 TD 4 : Les codes convolutifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

A Corrig´e du TD 1 61

B Corrig´e du TD 2 65

C Corrig´e du TD 3 71

D Corrig´e du TD 4 73

Bibliographie 81

vi Table des mati`eres

...