DECODAGE ALGEBRIQUE DES CODES

Introduction 

Le codage correcteur d’erreurs dont l’origine remonte à la fin des années 40, permet de transmettre de façon fiable l’information. On souhaite transmettre des informations via un canal de transmission. Celui-ci ne pouvant être parfait, l’information reçue par le destinataire peut être inexploitable ou erronée. Pour réduire au maximum la probabilité d’erreur, on construit une procédure de codage − décodage de l’information à transmettre qui, au prix d’éléments transmis supplémentaires, va permettre de détecter puis de corriger les altérations du message dues à l’imperfection du canal. On se base pour ceci essentiellement sur l’étude des corps finis et des polynômes sur ceux-ci. L’objet de la théorie de l’information est la description et l’étude de système de communication, où l’information est considérée comme une grandeur mathématique, à partir du travail de Claude Shannon (1948) « The mathematical theory of communication ». Le modèle général d’un système de communication comportant une protection contre les erreurs de transmission est le suivant : e l [Source] −→ [Encodeur] −→ [Canal] −→ [Décodeur] −→ [Recepteur] ↑ ↑ ↑ ↑ u c r = c + e u0 u : message émis c : mot de code émis (message codé) e : erreur r : mot reçu u 0 : message corrigé Le message à transmettre est un bloc de symboles tous issus d’un même alphabet. En tant que décodage algébrique, le travail est alors basé sur une méthode algébrique, c’est-à-dire qu’on a besoin de maîtriser la manipulation des polynômes à plusieurs variables, les idéaux, et surtout la résolution de systèmes 4 d’équations polynômiaux. Il faut introduire les bases de Groebner, puisque ce sont des outils fondamentaux de l’algèbre commutative pour l’étude des systèmes polynômiaux, elles permettent de résoudre nombreux problèmes concernant les systèmes polynômiaux : appartenance à un idéal, dimension et degré de l’espace des solutions, nombre de solutions dans le cas d’un nombre fini de solutions, calculs de ces solutions, etc… Dans ce mémoire, on présente la théorie des codes correcteurs d’erreurs, en particulier les codes cycliques et nous explicitons le décodage algébrique des codes cycliques et les liens avec la détermination des bases de Groebner. Le plan général de ce mémoire est alors comme suit : dans le premier chapitre, les fondements mathématiques permettant la construction de codes avec un rendement garanti sont présentés, en particulier les codes cycliques. On verra dans le chapitre deux quelques notions générales à propos de la base de Groebner. Le résultat de mon mémoire sera présenté dans le dernier chapitre, c’est le décodage des codes cycliques généraux et quelques exemples concrets. 

Codes linéaires 

Définition 1.1. Un ensemble K muni de deux lois de composition interne + et • est un corps si : – (K, +, •) est un anneau ; – (K∗ , •) est un groupe où K∗=K − {0}. Si la loi • est commutatif, on dit que le corps est commutatif. Si le cardinal de K est fini, alors le corps est dit f ini. On rappelle que si p est premier, alors Z/pZ est un corps (voir [15]). Notation 1. Soient p ∈ P (p premier), l ∈ N ∗ , et q = p l . Un corps fini de cardinal q est noté Fq. Définition 1.2. Soient Fq un corps fini et n ∈ N ∗ tels que (n, q) =1. Le plus petit entier positif m tel que n|q m − 1 est appelé ordre de q modulo n et on écrit m = Oq[n]. Dans la théorie de codage, on utilise le corps fini à q éléments Fq comme alphabet et le plus utilisé est F2 . Pour transmettre des messages, qui sont de longueur k, c’est-à-dire des vecteurs u = (u1, u2, …, uk) ∈ (Fq) k , on fait passer d’abord ces messages dans un encodeur qui est une application injective E : (Fq) k −→ (Fq) n avec n > k. L’image C=E((Fq) k ) s’appelle le code utilisé et les éléments x = (x1, x2, …, xn) ∈ C sont des mots de code. On sait que le nombre de mots de code est q k . Si E est linéaire, le sous espace vectoriel C de (Fq) n est appelé code linéaire 6 de dimension k, de longueur n, et de redondance n − k. Plus précisément C est un code linéaire si et seulement si ∀ m1, m2 ∈ C; ∀ a1, a2 ∈ Fq, a1m1 + a2m2 ∈ C. Le poids d’un mot x = (x1, x2, …, xn) ∈ (Fq) n est défini par |x| = card { i /xi 6= 0 ; 1 ≤ i ≤ n} (1.1) Définition 1.3. (cf. [15]) La distance de Hamming entre deux points x, y ∈ (Fq) n (x 6= y) est définie par d(x, y) = |x − y| (1.2) Définition 1.4. (cf. [15]) la distance minimale d’un code linéaire C est définie par d = min{d(x, y)/x, y ∈ C, x 6= y} = min{|x|/x ∈ C, x 6= 0} (1.3) On transmet le mot de code x ∈ C à travers un canal bruité, et à la sortie du canal, on reçoit un vecteur y ∈ (Fq) n . La différence z = y − x est appelée erreur commise. Si C est un code linéaire de longueur n, de dimension k, et de distance minimale d sur Fq, alors C est appelé code du type (n, k, d)q. Il y a deux manières de représenter un code linéaire à l’aide de matrices : soit on introduit un homomorphisme dont le code est l’espace vectoriel image, on obtient ainsi la notion de matrice génératrice, soit on introduit un homomorphisme dont le code est le noyau, on obtient ainsi la notion de matrice de contrôle. Pour connaitre le code en tant que sous espace vectoriel de (Fq) n , il suffit d’en avoir une base. Soit (m1, m2, …, mk) une base de C, chaque mi est ainsi composé de n lettres : on les note sous la forme de vecteurs ligne. Tous les mots de C peuvent ainsi s’écrire comme combinaison linéaire des mi . Définition 1.5. (Matrice génératrice) Soit (m1, m2, …, mk) une base de C dans (Fq) n , la matrice G =   m1 m2 . mk   de (Fq) k∗n est appelée matrice génératrice de C. 7 Pour former un mot de code, on calcule le produit d’un vecteur ligne (u1, . , uk) et de la matrice génératrice. Ainsi, m ∈ C ⇐⇒ ∃ u ∈ (Fq) k , m = u.G (1.4) Remarque 1.1. Soit C un code linéaire du type (n, k, d)q. L’encodage se fait en multipliant le mot source par la matrice génératrice du code. Le mot source doit être de longueur k. La redondance est de n − k symboles. Une autre façon de définir un code linéaire est de donner une application linéaire dont il est le noyau. On obtient ainsi une matrice H telle que C = {(x1, . , xn); H ∗   x1 x2 . xn   = 0} où 0 désigne le vecteur nul. Définition 1.6. (Matrice de contrôle) (cf. [13]) H est une matrice de contrôle pour le code C si elle vérifie ∀ m ∈ (Fq) n , (m ∈ C ⇐⇒ m.HT = 0) (1.5) Remarque 1.2. (cf.[13]) Le rang de cette matrice de contrôle est n − k. Définition 1.7. (Code dual)(cf. [15]) Soit C ⊂ (Fq) n un code linéaire. On définit le code dual de C par C ⊥ = {y ∈ (Fq) n / < x, y >= 0, ∀ x ∈ C} (1.6) où < x, y >= x1y1 + x2y2 + … + xnyn avec x = (x1, x2, …, xn) et y = (y1, y2, …, yn). Si C = C ⊥, on dit que C est un code auto-dual. Lemme 1.1. Soit C un code de matrice génératrice G et de matrice de contrôle H. Son code dual C ⊥ est engendré par H et admet G comme matrice de contrôle. 

Codes cycliques 

Les codes cycliques forment une sous classe des codes linéaires, et ils sont les plus utilisés en pratique. Ils conjuguent en effet de nombreux avantages : leur mise en œuvre(codage /décodage) est facile, ils offrent une gamme étendue de codes, avec de nombreux choix de paramètres (n, k, d), et enfin permettent de corriger différents types d’erreurs, isolées ou par paquets. 8 Définition 1.8. (voir [2] ou [15]) Un code linéaire C ⊆ (Fq) n est dit cyclique si pour tout (c0, c1, …, cn−1) ∈ C, on a (cn−1, c0, c1, …, cn−2) ∈ C, c’est-à-dire s’il est stable par permutation circulaire des lettres dans chaque mot. Il est commode de représenter (Fq) n par l’anneau (cf. [15]) A = Fq[X]/(Xn − 1) = Fq + FqX + … + FqXn−1 = {a0 + a1X + … + an−1Xn−1 /ai ∈ Fq} On utilise alors l’identification (a0, a1, …, an−1) ∈ (Fq) n ↔ a0 + a1X + … + an−1Xn−1 ∈ A Théorème 1.2. ([2] ou [15]) Un code linéaire C ⊂ (Fq) n est cyclique si est seulement si C est un idéal de A. Démonstration. (⇒) Supposons que C est cyclique. Soit c = (c0, c1, …, cn−1) ∈ C, alors (cn−1, c0, c1, …, cn−2) ∈ C Dans A, ce fait se traduit par c(X) = c0 + c1X + … + cn−1Xn−1 ∈ C implique X.c(X) = cn−1 + c0X + … + cn−2Xn−1 ∈ C Et d’une manière générale, on a Xi .c(X) ∈ C, pour tout i Et comme C est linéaire, alors f(X).c(X) ∈ C, ∀ f(X) ∈ A Ainsi, C est un idéal de A. (⇐) Supposons que C est un idéal de A et soit c(X) = c0 + c1X + · · · + cn−1Xn−1 ∈ C On a alors X.c(X) ∈ C or X.c(X) = cn−1 + c0X + … + cn−2Xn−1 ∈ C D’où C est cyclique. Tout idéal de Fq[X]/(Xn − 1) est engendré par un seul élément [15] ; cela tient à l’existence d’une division euclidienne dans cet anneau. Définition 1.9. (Polynôme générateur) Le polynôme générateur du code cyclique C est le polynôme normalisé de plus bas degré de C. On le note génériquement g(X).