Codes correcteurs
Principes et exemples

Sommaire et contenu du livre "Codes correcteurs - Principes et exemples"

Table des matières
CHAPITRE 1 Transmission de messages 1 1 Erreurs de transmission 1
1.1 Codage d'une information 1
1.2 Décodage 2 2 Codes correcteurs 3
2.1 Codes par blocs 3
2.2 Codes sytématiques 4 3 Code de parité 4
3.1 Contrôle 5
3.2 Probabilité d'erreur détectée 5 4 Code de parités croisées 6
4.1 Codage 6
4.2 Décodage 7 Conclusion 9
CHAPITRE II Codes linéaires 11 1 Représentation vectorielle des mots 11
1.1 Structure de B = [O, 1} 11
1.2 Structure de BP 12
1.3 Définition d'un code linéaire 13 2 Codage linéaire systématique 13
2.1 Matrice génératrice normalisée 14
2.2 Matrice de contrôle normalisée 16 3 Cas général 18
3.1 Matrices génératrices 18
3.2 Matrices de contrôle 21 4 Détection d'erreur 24
4.1 Condition de détection d'erreur 25
4.2 Probabilité d'erreur détectée 26 Conclusion 27 Exercices 29
CHAPITRE III Correction automatique 39
1 Principe 39
2 Méthode de correction par syndromes 41
2.1 Relation d'équivalence entre vecteurs de B" .41
2.2 Tableau standard 42
2.3 Tableau standard réduit 45 3 Efficacité de la correction 46
3.1 Notion de distance entre vecteurs 46
3.2 Evaluation de la distance minimale d'un code 47
3.3 Capacité de détection d'un code 49
3.4 Fiabilité de la correction automatique 50
3.5 Capacité de correction d'un code 52
3.6 Probabilité d'exactitude après décodage 53 4 Codes de Hamming 54
4.1 Description 55
4.2 Propriétés : 57
4.3 Correction des messages : 58
4.4 Probabilité d'exactitude du message décodé 59 Conclusion 60 Exercices 61
CHAPITRE IV Codes polynomiaux 69 1 Représentation polynomiale des mots 69
1.1 Opérations sur les polynômes 70
o
1.2 Description des codes polynomiaux 71
1.3 Fonction de codage 72
1.4 Polynôme générateur 72 2 Codage 73
2.1 Codage par multiplication de polynômes 73
2.2 Matrice génératrice caractéristique 74


2.3 Codage systématique 75 3 Détection d'erreur 78
3.1 Contrôle par division de polynômes 79
3.2 Possibilités de détection d'erreur 80 4 Autre représentation des codes polynomiaux 82
4.1 Structure d'anneau de Pn-1 • . ••. •... •.•..... • ••. • •.... ••..... •..... 82
4.2 Structure d'idéal d'un code polynomial 83
4.3 Intérêt de cette représentation 86 Conclusion 88 Exercices 90
CHAPITRE V Présentation des codes cycliques 101 1 Définition 101
1.1 Cyclicité d'un code 101
1.2 Forme polynomiale d'un code cyclique 103
1.3 Matrice génératrice 104 2 Contrôle 105
2.1 Polynôme de contrôle 105
2.2 Matrice de contrôle caractéristique 107
3 Piégeage des erreurs corrigibles (Meggitt) 110 Conclusion 113 Exercices 115
CHAPITRE VI Générateurs des codes cycliques 121 1 Recherche des racines de (z" + 1) 121
1.1 Idée directrice 121
1.2 Méthode 122



1.3 Illustration 123 2 Corps fini d'extension de B 124
2.1 Construction 125
2.2 Structure de G = K(2m ) {O} :127
2.3 Corps des racines nèm es de l'unité 132 3 Décomposition de (z"1) sur B 134
3.1 Polynôme minimal 134
3.2 Racines conjuguées dans K 135
3.3 Facteurs de (z"1) irréductibles sur B 137
3.4 Expression d'un polynôme minimal dans B[x] 138 4 Générateurs des codes cycliques de longueur n 140 Conclusion 141 Exercices 143
CHAPITRE VII Codes BC?i Codes de Reed-Solomon 151 1 Codes cycliques de longueur impaire 151
1.1 Matrice de contrôle fonction des racines de g(x) 152
1.2 Distance apparente d'un code cyclique 153

1.3 Minoration de la capacité de correction 156 2 Codes BC1l 157
2.1 Construction et définition 157
2.2 Choix de la distance assignée 159
2.3 Codes BC1l au sens strict 159
2.4 Contrôle 161
2.5 Cas particulier: code de Hamming 162 3 Codes de Reed-Solomon 164
3.1 Caractéristiques et construction d'un code ns 165
3.2 Contrôle des messages 166
3.3 Correction des messages binaires 167 Conclusion 169 Exercices 170
Bibliographie 178 Index 179