Admin CliCours
DES CODES CORRECTEURS POUR
SÉCURISER L’INFORMATION NUMÉRIQUE
Codes algébriques
Nous allons tout d’abord présenter quelques structures algébriques. Nous nous servirons de ces objets mathématiques par la suite et ce, aussi bien en théorie des codes qu’en cryptologie. Nous donnerons également un certain nombre de propriétés que possèdent ces objets. Nous allons définir certaines familles de codes linéaires en bloc avec lesquelles nous aurons à travailler. Nous nous intéresserons essentiellement aux familles des codes cycliques ainsi qu’à celles des codes alternants. Il existe bon nombre de codes linéaires, nous en recensons certains dans la Figure 2.1. Nous n’expliciterons pas tous les liens qui les relient car cela sortirait du cadre de ce document. Mais, pour commencer, nous allons devoir définir ce qu’est un code linéaire en blocs ainsi que les paramètres essentiels qui permettent de les caractériser. Nous nous intéresserons encore à certaines des propriétés de ces codes. Définition 1 (Structure Algébrique). Un ensemble est muni d’une structure algébrique si une ou plusieurs lois de composition sont définies sur cet ensemble. Exemple 1. De très nombreuses structures algébriques ont été étudiées. Il n’est pas question de les recenser ici. On peut néanmoins citer : les groupes, les anneaux, les corps, les espaces vectoriels.
Structures algébriques Définition 2 (Monoïde)
Un monoïde est un ensemble muni d’une loi de composition interne associative admettant un élément neutre. Exemple 2. L’ensemble des entiers positifs muni de l’addition (N,+) forme un monoïde. Définition 3 (Groupe). Un groupe est monoïde admettant pour chaque élément de l’ensemble, un élément symétrique. Remarque 1. Un groupe (G, +) est dit abélien ou commutatif si a + b = b + a, ∀a, b ∈ G. Exemple 3. L’ensemble des entiers relatifs munis de l’addition (Z,+) forme un groupe. L’ensemble Sn des permutations de J1, nK muni de la loi de composition forme le groupe symétrique d’indice n. Notation 1. En notation additive, l’élément symétrique d’un élément x d’un groupe (G, +) est appelé l’opposé de x, on le note −x. En notation multiplicative, l’élément symétrique d’un élément x d’un groupe (G, ×) est appelé l’inverse de x, on le note x −1 . Définition 4 (Groupe Cyclique). En notation multiplicative, un groupe cyclique est un groupe dont tous les éléments sont des puissances d’un certain élément α. L’élément α est un générateur du groupe. Il est encore appelé élément primitif du groupe. Il n’est pas nécessairement unique. Certains auteurs considèrent qu’un groupe cyclique doit de surcroît posséder un nombre fini d’éléments. Exemple 4. L’ensemble des entiers modulo n munis de l’addition (Zn,+) forme un groupe cyclique. Il s’agit de l’unique groupe cyclique d’ordre n, à isomorphisme près. Définition 5 (Groupe Multiplement Transitif). Un sous-groupe H de Sn est k-fois transitif si pour tout choix de k éléments distincts i1, . . . , ik ∈ J1, nK, il existe une permutation σ ∈ H avec : σ(1) = i1, . . . , σ(k) = ik. Définition 6 (Semi-anneau). Un semi-anneau (A, +, ×) est un ensemble où : – (A, +) est un monoïde commutatif, – (A, ×) est un monoïde, – la multiplication est distributive par rapport à l’addition, – l’élément neutre pour l’addition est absorbant pour le produit. Exemple 5. La structure ({0, 1, X}, +, ∗) définie par les tables suivantes est un semi-anneau commutatif. Je la présente à dessein puisqu’on la rencontrera dans la suite de ce document. On peut se familiariser facilement avec cette structure. Pour anecdote, il est reconnu qu’en des temps anciens, l’Homme ne savait pas compter au delà de trois. Tout entier supérieur à trois était considéré comme « beaucoup » . Considérons que le symbole X désigne la quantité « beaucoup » . Lorsqu’on travaille dans la structure présentée ci-dessus, on est dans une situation très proche, tout entier supérieur à deux est alors considéré comme « beaucoup » . Définition 7 (Anneau). Un anneau (A, +, ×) est un ensemble tel que (A, +) est un groupe abélien, (A, ×) est un monoïde et tel que la loi × soit distributive par rapport à la loi +. L’anneau est dit commutatif si la loi × est commutative. Notation 2. 0 désigne l’élément neutre de la loi + et 1 représente l’élément neutre de la loi ×. Définition 8 (Caractéristique d’un anneau). Soit un anneau (A, +, ×). La caractéristique de A est le plus petit entier non nul n tel que n.1 = 0. S’il n’existe pas de tel entier, la caractéristique de A est dite nulle. Définition 9 (Anneau intègre). Un anneau intègre est un anneau commutatif qui ne possède pas de diviseur de zéro et tel que 1 6= 0. Exemple 6. La caractéristique de Zn est n. L’anneau Zn est intègre ⇔ n est premier. Définition 10 (Corps commutatif). Un corps (K, +, ×) est un anneau tel que (K, ×) soit un groupe. Le corps est dit commutatif si (K, ×) est un groupe abélien. Notation 3. Soit p un nombre premier. Soit m un entier positif et q = p m. Exemple 7. L’ensemble Zp[X] des polynômes univariés, à coefficients dans le corps Zp des entiers modulo p, forme un anneau. L’ensemble des fonctions booléennes à n variables forme un anneau. Définition 11 (Corps premier). Un corps est premier s’il ne contient aucun sous-corps strict. Proposition 1. Il n’existe que deux types de corps premiers. 1. Un corps premier de caractéristique 0 est isomorphe à Q. 2. Un corps premier de caractéristique p est isomorphe à Zp. Dans la suite de ce document, nous manipulerons la structure des corps finis (également appelés corps de Galois). Il existe plusieurs manières de construire ces objets. Il existe une littérature conséquente sur le sujet, il est d’usage de citer l’encyclopédique [LN97]. Théorème 1 (Wedderburn). Tout corps fini est commutatif. Proposition 2. Il existe un unique corps de Galois d’ordre donné, à isomorphisme près. Proposition 3. La caractéristique du corps à q éléments est p. Définition 12 (Polynôme minimal). Soit K, un corps commutatif et L une extension algébrique de K. Le polynôme minimal d’un élément a de L sur K est le polynôme unitaire à coefficients dans K de plus bas degré qui admet a pour racine. Caractérisation 1. Le corps de Galois Fq d’ordre q est un corps fini de la forme Zp[X]/f, où f ∈ Zp[X] est le polynôme minimal sur Fp d’un élément primitif de Fq. Définition 13 (Corps des racines). Le corps des racines d’un polynôme à coefficients dans K est la plus petite extension de K contenant toutes les racines du polynôme. Caractérisation 2. Le corps de Galois Fq d’ordre q est l’ensemble des racines du polynôme Xq − X dans son corps des racines. Exemple 8. Le corps Zp des entiers modulo p est isomorphe au corps de Galois Fp. Proposition 4. Soit φ l’indicatrice d’Euler. Le groupe multiplicatif F × q est cyclique, il possède φ(q − 1) éléments primitifs. Définition 14 (Groupe Affine). Soient m > 0 et α un élément primitif du groupe multiplicatif F × 2m. Le groupe affine des permutations de F2m est l’ensemble : ( α i 7→ uαi + v, 0 7→ v : u, v ∈ F2m, u 6= 0) . Remarque 2. Le groupe affine est un groupe 2-transitif. On peut consulter [BM75, pp. 58- 63] pour de plus amples informations sur des groupes de transformations tels que le groupe affine. Définition 15 (Algèbre sur un corps). Une K-algèbre (A, +, ×, ·) est un ensemble tel que (A, +, ×) soit un anneau, (A, +, ·) soit un K-espace vectoriel et tel que la propriété (λ · a)×(µ · b) = (λ · µ) · (a×b) soit vérifiée pour tout λ, µ dans K et pour tout a, b dans A. Exemple 9. L’ensemble Fq[X]/(Xn − 1) est une Fq-algèbre. Cet objet sera notamment utile pour la construction des codes cycliques.
Notions générales en théorie des codes
Notation 4. Soit A, un alphabet. Soient k, m, n des entiers positifs. Pour tout i > 0, on note Ai , l’ensemble des messages de longueur i sur A. Définition 16 (Code correcteur). Un code correcteur est l’image d’une application injective définie sur le produit cartésien m-ième de Ak et à valeurs dans An . Le terme mot de code désigne un élément de cet ensemble. Remarque 3. Dans un souci de légèreté, nous parlerons dorénavant de codes et non pas de codes correcteurs. Attention à ne pas confondre ces codes là avec les « codes secrets » utilisés en cryptographie. Remarque 4. Il existe également des codes détecteurs. Leur rôle consiste à détecter la présence d’erreurs et le cas échéant, à retransmettre le message erroné. Remarque 5. Nous traiterons uniquement des codes correcteurs d’erreurs. Une erreur désigne une modification d’un symbole en un autre. Il existe encore les codes correcteurs d’erreurs en rafale ainsi que les codes correcteurs d’effacements. Le rôle de ces derniers consiste à reconstituer un mot de code émis à partir de l’ensemble des symboles reçus. Un effacement désigne la disparition d’un symbole. Remarque 6. Nous traiterons uniquement des codes en blocs, pour lesquels, les opérations de codage et décodage d’un bloc dépendent uniquement des symboles d’information de ce bloc. Cela se traduit par m = 1 dans la Définition 16. L’autre famille de codes est celle des codes convolutifs. Pour ces derniers, le codage et le décodage d’un bloc dépendent des symboles d’information d’autres blocs (généralement de blocs précédemment transmis). On peut naturellement faire l’analogie avec le chiffrement par blocs et le chiffrement à flot en cryptographie. Définition 17 (Code linéaire). Un code linéaire est l’image d’une application linéaire injective définie sur F k q et à valeurs dans F n q . On appelle k, la dimension du code et n, la longueur de blocs du code. Le code est dit q-aire. En particulier, le code est dit binaire si q = 2 et ternaire si q = 3. Proposition 5. Un code linéaire est un Fq-sous-espace vectoriel de F n q de dimension k. Remarque 7. On pourrait très bien définir les codes sur des anneaux finis mais nous n’en aurons pas l’utilité ici. Les mots d’un code linéaire peuvent s’écrire de plusieurs manières selon le choix de la base du code. Cette base n’est pas unique. On représente une base d’un code linéaire sous forme matricielle. Notation 5. Soit C, un code linéaire q-aire de dimension k et de longueur n. Définition 18 (Matrice génératrice). Une matrice génératrice de C est une matrice notée généralement G de taille k ×n et à coefficients dans Fq dont les lignes forment une base de C. Propriété 1. Pour toute matrice inversible M d’ordre k et à coefficients dans Fq, MG est une matrice génératrice de C. Définition 19 (Distance de Hamming). La distance de Hamming de deux mots x et y de longueur fixe est le nombre d(x, y) de positions où ces deux mots diffèrent. Définition 20 (Espace de Hamming). L’espace F n q munie de la distance de Hamming est appelé espace de Hamming. Définition 21 (Support d’un mot). Le support d’un mot x = (x1, x2, . . . , xn) de F n q est l’ensemble des positions qui indexent les composantes non nulles de ce mot. Définition 22 (Support d’un code). Le suppport d’un code est l’union des supports de ses mots. Définition 23 (Poids de Hamming). Le poids de Hamming d’un mot est le cardinal de son support. On notera w(x) le poids de Hamming d’un mot x. Propriété 2. Pour tout x, y ∈ F n q , d(x, y) = w(x − y). Remarque 8. La distance de Hamming est une métrique ou distance (au sens mathématique du terme) sur F n q . Nous utiliserons seulement cette métrique, néanmoins il en existe d’autres. On pourra citer la métrique rang, la métrique de Lee, la métrique arithmétique ainsi que la métrique de Hamming généralisée. Définition 24 (Distance minimale). La distance minimale d d’un code est le plus petit poids non nul d’un mot du code. Il s’agit d’un paramètre essentiel d’un code. Définition 25 (Capacité de détection). La capacité de détection d’un code est la quantité d−1. Définition 26 (Capacité de correction). La capacité de correction t d’un code est la quantité ⌊ d − 1 2 ⌋. Elle désigne le nombre maximal d’erreurs que peut corriger un code sans ambiguïté. Corriger signifie dans notre contexte, choisir le mot de code le plus proche, en termes de distance de Hamming, du mot reçu. On parle de décodage suivant la règle du plus proche voisin. Il y a ambiguïté s’il existe plusieurs possibilités de correction. Auquel cas, on peut soit choisir un mot au hasard parmi les mots de code les plus proches du mot reçu, soit demander une retransmission. Remarque 9. Il existe d’autres types de décodage ; on citera le décodage à vraisemblance maximale et le décodage en liste [Eli57]. Notation 6. Un code [n, M, d]q est un code q-aire de longueur n, de cardinal M et de distance minimale d. Un code linéaire [n, k, d]q est un code linéaire q-aire de longueur n, de dimension k et de distance minimale d. On a l’égalité : M = q k . Il existe plusieurs critères d’optimalité sur les paramètres du code. Nous allons en définir certains dont nous reparlerons dans la Figure 2.1. Définition 27 (Code parfait). Un code [n, M, d]q est dit parfait si l’ensemble des boules fermées de rayon t pour la distance de Hamming et centrées sur les mots du code forment une partition de F n q . Intuitivement, cela signifie que toute erreur détectée soit corrigée. Cela ne signifie néanmoins pas que l’erreur soit correctement corrigée. Définition 28 (Code MDS). Un code [n, k, d]q est dit MDS (maximum distance separable) s’il n’existe pas de code linéaire [n, k]q possédant une distance minimale strictement plus grande. Formellement, cela signifie que l’on a l’égalité d = n − k + 1.
1 Par où commencer ? |
