IFT 6170 Théorie et pratique des codes correcteurs

Claude Crépeau

Département d’Informatique et R.O.,

Université de Montréal, C.P. 6128, succursale centre-ville,

Montréal (Québec), Canada H3C 3J7. e-mail: crepeau@iro.umontreal.ca.

Table of Contents

1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Objectifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Codes linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2 théorie des nombres et corps finis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.1 définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.2 opérations de base efficaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.3 calcul d’une exponentiation rapide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.4 calcul du PGCD et d’inverses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.5 Nombres premiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.6 corps premiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.7 polynômes sur un corps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.8 polynômes irréductibles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.9 Corps quelconques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.10 Éléments primitifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.11 Factorisation de q − 1... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3 Espaces vectoriels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.1 Combinaisons linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.2 Produit Scalaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

4 Algèbre Linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 4.1 opérations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 4.2 temps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 4.3 déterminant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 4.4 matrices échelonées réduites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

5 Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 5.1 taux de transmission d’un code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 5.2 distance minimale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 5.3 codes parfaits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 5.4 codes équivalents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

6 Codes Linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 6.1 distance minimale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 6.2 matrice génératrice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 6.3 codage et décodage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 6.4 forme systématique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 6.5 matrice de parité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 6.6 syndromes et cosets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 6.7 détection d’erreurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 6.8 correction d’erreurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 6.9 code dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

7 Codes de Hamming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 7.1 construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 7.2 distance minimale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 7.3 correction d’erreurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

8 Théorie de l’information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 8.1 Modèles d’erreurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 8.2 Entropie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 8.3 Entropie conditionelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 8.4 Information mutuelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 8.5 Capacité d’un canal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 8.6 Objectifs de la théorie des codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 8.7 Théorèmes de Shannon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 8.8 Outils utiles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

9 Limites sur les performances des codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 9.1 Borne supérieure de Singleton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 9.2 Borne inférieure de Varshamov-Gilbert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 9.3 Borne supérieure de Hamming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 9.4 Borne supérieure de Plotkin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 9.5 Borne supérieure de McEliece-Rodemich-Rumsey-Welch . . . . . . . . . . . . . . . . . . . . . 20

10 NP-complétude de problèmes sur les codes . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 10.1 NP-complet ou NP-ardu? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 10.2 correction d’erreurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 10.3 NP-complétude de PMCS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 10.4 poids des mots de code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 10.5 NP-complétude de PC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 10.6 Équivalence de codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

11 Codes de Hadamard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 11.1 Matrices de Hadamard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 11.2 construction de Sylvester . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 11.3 construction de Paley . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 11.4 codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

12 Codes cycliques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 12.1 polynome générateur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 12.2 polynome de parité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 12.3 code dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 12.4 facteurs de x^{n} − 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 12.5 cosets cyclotomiques et polynômes minimaux . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 12.6 borne de BCH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

13 Codes BCH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 13.1 Distance minimale effective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 13.2 Symboles d’information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 13.3 Les codes BCH sont mauvais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

14 Codes Reed-Solomon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 14.1 definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 14.2 codage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 14.3 codes binaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 14.4 les codes RS “binarisés” sont mauvais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 14.5 correction de paquets d’erreurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

15 Codes Concaténés et Justesen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 15.1 concaténation de codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 15.2 code interne aléatoire ou maximal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 15.3 codes multiplicatifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 15.4 les Codes multiplicatifs sont bons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 15.5 codes de Justesen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 15.6 décodage des codes concaténés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

décodage naïf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 décodage de Block-Zyablov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

15.7 codes de Forney . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

16 Codes Reed-Solomon généralisés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

16.1 le dual d’un code RSG est RSG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

17 Codes Alternants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 17.1 décodage des codes Alternants: algorithme de Berlekamp . . . . . . . . . . . . . . . . . . . . 35 17.2 les Codes Alternants sont bons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

18 Codes Classiques de Goppa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

19 Codes Géométriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

20 Graphes et codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 20.1 Graphes Expandeurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 20.2 Codes expandeurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 20.3 Codes superconcentrateurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

21 Applications à la cryptographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 21.1 partages de secrets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 21.2 Cryptosystème de McEliece . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 21.3 réductions entres protocoles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 21.4 Winer wire-tap channel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 21.5 Extension de Maurer et BBCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 21.6 Protocoles cryptographiques à partir d’un canal bruyant . . . . . . . . . . . . . . . . . . . . . 36

22 Codes quantiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

36 IFT6170 Claude Crépeau

19 Codes Géométriques

20 Graphes et codes

20.1 Graphes Expandeurs 20.2 Codes expandeurs 20.3 Codes superconcentrateurs

21 Applications à la cryptographie

21.1 partages de secrets 21.2 Cryptosystème de McEliece 21.3 réductions entres protocoles 21.4 Winer wire-tap channel 21.5 Extension de Maurer et BBCM 21.6 Protocoles cryptographiques à partir d’un canal bruyant

22 Codes quantiques

IFT6170 Devoir 5

à rendre avant la tombée de la nuit le vendredi 19 décembre 1997

Codes BCH sont Alternants [8 points]

Montrez de façon générale que les codes BCH sont des codes alternants. C’est-à-dire que les mots de codes peuvent être obtenus par la restriction sur F_{q} des mots d’un code RSG(α, v) sur F_{q^{m}}.

Prenez le code BCH binaire de longueur 23 et de distance de design 3. Un polynôme générateur de ce code est M^{(1)}(x). La dimension de ce code est de 12 et sa distance minimale réelle est de 7. En utilisant votre construction générale donnez le code RSG(α, v) dont ce code BCH est la restriction sur F_{2}.

Calculez le syndrome S du patron d’erreur (01000000000000000000000). Trouvez les polynômes σ et ω associés à ce patron. Vérifiez que ω(x) ≡ σ(x)S(x) (mod x^{r}).

Codes Intersectants [8 points]

1. Si on étend la définition de codes intersectants à tous les corps F_{q} il est possible sur certains corps de construire explicitement de tels codes. Montrez que pour des q > 2 assez grand certains codes Reed-Solomon sont intersectants sur F_{q}. suggestion: Tout code [n, k, d] pour d assez grand est intersectant.

2. Pourquoi est-ce que la suggestion du point 1 ne nous aide pas à montrer directement qu’il existe une bonne famille de codes intersectants sur F_{2}.

3. Montrez que la concaténation de deux codes intersectants est également un code intersectant.

4. Expliquez comment combiner les points précédents et ce que l’on connais déja sur les codes intersectants pour obtenir une construction efficace probabiliste d’une bonne famille de codes binaires (vérifiablement) intersectants. Donnez de façon explicite le lien entre k et n des codes binaires ainsi obtenus.

42 IFT6170 Claude Crépeau This article was processed using the L^{A}TEX macro package with LLNCS style