CODES CORRECTEURS AVEC MAPLE Pascal Kaeser, Genève, 1997 Attention : ce fichier doit être lu avec une police non proportionnelle, par exemple Courier New 10. ********************************************************************* Tables des matières : 1. Introduction, définition, distance minimale 2. Calculs dans les corps finis 3. Codes linéaires, codes de Hamming et de Reed-Muller, décodage 4. Codes cycliques, générateur, décodage 5. Codes BCH, codes de Reed-Solomon, transformée de Mattson-Solomon 6. Codes d'Hadamard 7. Codes et designs 8. Groupe d'automorphismes d'un code ********************************************************************* 1. Introduction, définition, distance minimale Introduction Max envoie un livre et une bouteille de whisky à Victor pour son anniversaire. Une semaine plus tard, Max reçoit un E-mail de Victor ainsi libellé : J'ai ?u le li*re. Magni@ique ! Manifestement, trois erreurs au moins se sont produites lors de la transmission. Impossible de savoir si l'original du message est : J'ai lu le livre. Magnifique ! ou J'ai bu le litre. Magnifique ! La raison en est que le vocabulaire de la langue française contient des mots distincts formés parfois d'une succession presque identique de lettres. La théorie des codes correcteurs se propose d'élaborer mathématiquement des vocabulaires tels que le message original puisse être automatiquement reconstitué à partir du message reçu, moyennant bien sûr une évaluation correcte du taux de fiabilité du canal de transmission utilisé. L'idée est de fabriquer des vocabulaires dont les différents mots soient suffisamment distants les uns des autres. Naturellement, il y a encore d'autres contraintes à respecter, ce qui rend la tâche moins facile qu'elle ne peut paraître au premier abord. Cette théorie est née à la fin des années quarante avec les oeuvres de Shannon, Hamming et Golay. Les codes de Reed-Muller, les codes cycliques, BCH et Reed-Solomon sont apparus dans les années cinquante et début soixante. En 1965, le premier code non linéaire intéressant voit le jour. De très nombreux codes ont été inventés depuis et les découvertes continuent. La théorie algébrique des codes est non seulement abondamment utilisée pour la transmission d'informations, mais présente aussi un intérêt élevé dans le domaine des mathématiques pures, de par ses liens avec des probèmes tels que la classification des groupes finis simples, la détermination d'empilements de hautes densités de sphères et la construction de configurations combinatoires. En outre, même si son but est diamétralement opposé, la cryptographie partage bon nombre de ressources avec la théorie des codes correcteurs. Le but de ce document est de fournir succinctement quelques définitions et algorithmes, et de les illustrer à l'aide de Maple. L'approche est pragmatique et non pas démonstrative. Définition d'un code Un code z-aire C de longueur n sur un alphabet A est un sous-ensemble de A^n, où A est un ensemble de cardinal z. Un mot de C est un élément de C. La s-ième lettre d'un mot c[i] est la s-ième composante du vecteur c[i]. La taille de C est son cardinal. Définition de la distance La distance de Hamming entre deux mots c[i] et c[j] est le cardinal de l'ensemble des entiers s tels que (1<=s et s<=n et s-ième lettre de c[i] différente de s-ième lettre de c[j]). La distance minimale du code C est l'entier d défini comme étant le minimum sur C des distances de Hamming entre c[i] et c[j], pour i<>j. L'importance de la distance minimale tient en ceci : si, lors d'une transmission, un élément reçu v comporte e erreurs avec e<=2*d+1, alors on est assuré qu'il existe dans C un seul mot u qui est le plus proche voisin de v pour la distance de Hamming, et il est naturel de décoder v en u. Procédure pour le calcul de la distance minimale > restart; > with(combinat,choose): > distM:=proc(C,n) local T,t,d,k,couple,ci,cj,dH,s,Li,Lj; > T:=choose(C,2);t:=nops(T);d:=n; > for k from 1 to t do; > couple:=op(k,T);ci:=op(1,couple);cj:=op(2,couple);dH:=0; > for s from 1 to n do; > Li:=op(s,ci);Lj:=op(s,cj); > if Li<>Lj then dH:=dH+1 fi; > od; > if dH od; > d; > end: Exemple simple > n:=4; n := 4 > C:={[1,2,3,1],[1,3,2,2],[3,1,1,3],[2,3,3,3]}; C := {[1, 2, 3, 1], [1, 3, 2, 2], [3, 1, 1, 3], [2, 3, 3, 3]} > d:=distM(C,n); d := 3 Exemple plus pointu Soient p un nombre premier et m un entier strictement positif. Posons q=p^m et choisissons n un entier plus petit ou égal à q+1. Considérons une liste de n - 2 carrés latins L[k] de dimensions q sur q, mutuellement orthogonaux et construits avec les entiers de 1 à q. Dans ces conditions, l'ensemble des vecteurs (i, j, L[1][i, j], L[2][i, j], ..., L[n-2][i, j]), où i et j varient de 1 à q, forme un code de longueur n, de taille q^2 et, ainsi qu'on peut le démontrer, de distance minimale n - 1. Construisons un tel code pour q = 3^2 et n = 7, et vérifions sa distance minimale à l'aide du programme précédemment créé. > MOLScode:=proc(p,m,n) local q,L,C,i,j,mot,k; > q:=p^m; > readlib(MOLS); > L:=MOLS(p,m,n-2); > C:={}; > for i from 1 to q do; > for j from 1 to q do; > mot:=[i,j,seq(1+L[k][i,j],k=1..n-2)]; > C:=C union {mot}; > od; > od; > C; > end: > C:=MOLScode(3,2,7); C := {[1, 1, 1, 1, 1, 1, 1], [1, 2, 2, 2, 2, 2, 2], [1, 3, 3, 3, 3, 3, 3], [1, 4, 4, 4, 4, 4, 4], [1, 5, 5, 5, 5, 5, 5], [1, 6, 6, 6, 6, 6, 6], [1, 7, 7, 7, 7, 7, 7], [1, 8, 8, 8, 8, 8, 8], [1, 9, 9, 9, 9, 9, 9], [2, 1, 2, 3, 4, 5, 6], [2, 2, 3, 1, 5, 6, 4], [2, 3, 1, 2, 6, 4, 5], [2, 4, 5, 6, 7, 8, 9], [2, 5, 6, 4, 8, 9, 7], [2, 6, 4, 5, 9, 7, 8], [2, 7, 8, 9, 1, 2, 3], [2, 8, 9, 7, 2, 3, 1], [2, 9, 7, 8, 3, 1, 2], [3, 1, 3, 2, 7, 9, 8], [3, 2, 1, 3, 8, 7, 9], [3, 3, 2, 1, 9, 8, 7], [3, 4, 6, 5, 1, 3, 2], [3, 5, 4, 6, 2, 1, 3], [3, 6, 5, 4, 3, 2, 1], [3, 7, 9, 8, 4, 6, 5], [3, 8, 7, 9, 5, 4, 6], [3, 9, 8, 7, 6, 5, 4], [4, 1, 4, 7, 5, 8, 2], [4, 2, 5, 8, 6, 9, 3], [4, 3, 6, 9, 4, 7, 1], [4, 4, 7, 1, 8, 2, 5], [4, 5, 8, 2, 9, 3, 6], [4, 6, 9, 3, 7, 1, 4], [4, 7, 1, 4, 2, 5, 8], [4, 8, 2, 5, 3, 6, 9], [4, 9, 3, 6, 1, 4, 7], [5, 1, 5, 9, 8, 3, 4], [5, 2, 6, 7, 9, 1, 5], [5, 3, 4, 8, 7, 2, 6], [5, 4, 8, 3, 2, 6, 7], [5, 5, 9, 1, 3, 4, 8], [5, 6, 7, 2, 1, 5, 9], [5, 7, 2, 6, 5, 9, 1], [5, 8, 3, 4, 6, 7, 2], [5, 9, 1, 5, 4, 8, 3], [6, 1, 6, 8, 2, 4, 9], [6, 2, 4, 9, 3, 5, 7], [6, 3, 5, 7, 1, 6, 8], [6, 4, 9, 2, 5, 7, 3], [6, 5, 7, 3, 6, 8, 1], [6, 6, 8, 1, 4, 9, 2], [6, 7, 3, 5, 8, 1, 6], [6, 8, 1, 6, 9, 2, 4], [6, 9, 2, 4, 7, 3, 5], [7, 1, 7, 4, 9, 6, 3], [7, 2, 8, 5, 7, 4, 1], [7, 3, 9, 6, 8, 5, 2], [7, 4, 1, 7, 3, 9, 6], [7, 5, 2, 8, 1, 7, 4], [7, 6, 3, 9, 2, 8, 5], [7, 7, 4, 1, 6, 3, 9], [7, 8, 5, 2, 4, 1, 7], [7, 9, 6, 3, 5, 2, 8], [8, 1, 8, 6, 3, 7, 5], [8, 2, 9, 4, 1, 8, 6], [8, 3, 7, 5, 2, 9, 4], [8, 4, 2, 9, 6, 1, 8], [8, 5, 3, 7, 4, 2, 9], [8, 6, 1, 8, 5, 3, 7], [8, 7, 5, 3, 9, 4, 2], [8, 8, 6, 1, 7, 5, 3], [8, 9, 4, 2, 8, 6, 1], [9, 1, 9, 5, 6, 2, 7], [9, 2, 7, 6, 4, 3, 8], [9, 3, 8, 4, 5, 1, 9], [9, 4, 3, 8, 9, 5, 1], [9, 5, 1, 9, 7, 6, 2], [9, 6, 2, 7, 8, 4, 3], [9, 7, 6, 2, 3, 8, 4], [9, 8, 4, 3, 1, 9, 5], [9, 9, 5, 1, 2, 7, 6]} > d:=distM(C,7); d := 6 Exercice Soit C un code de longueur n sur un alphabet A, de capacité de correction : e := partie entière de (d-1)/2, où d est la distance minimale. Démontrer l'inégalité suivante, appelée borne d'empilement de sphères : card(C)*sum((card(A)-1)^r*binomial(n,r), r=0..e)<=card(A)^n. Référence Steven Roman : Introduction to coding and information theory, Springer-Verlag 1997. 2. Calculs dans les corps finis Ce qu'il faut savoir Calculer dans GF(p), avec p premier, est un jeu d'enfant. Les choses sont un peu plus compliquées dans GF(p^r). Rappelons que ce dernier peut être construit comme quotient de l'anneau des polynômes à coefficients dans GF(p) par un polynôme irréductible de degré r. Si, de plus, ce polynôme en alpha divise alpha^(p^r-1)-1 et ne divise pas alpha^s-1 quand s restart; GF(5^3) a pour paramètres : > p:=5;r:=3; p := 5 r := 3 et peut être décrit à l'aide du polynôme primitif suivant : > poly:=alpha^3+alpha^2+2; 3 2 poly := alpha + alpha + 2 Vérification qu'il est bien primitif : > Primitive(poly) mod p; true Posons alpha := une racine de poly : > alias(alpha=RootOf(poly)): Soient deux éléments du corps : > T1:=3*alpha^3+4*alpha+2;T2:=4*alpha^3+alpha^2+2*alpha+1; 3 T1 := 3 alpha + 4 alpha + 2 3 2 T2 := 4 alpha + alpha + 2 alpha + 1 T1 + T2 donne : > somme:=simplify(T1+T2) mod p; 2 somme := 4 + alpha + 4 alpha T1 * T2 donne : > produit:=simplify(T1*T2) mod p; 2 produit := 2 + 3 alpha + alpha Ecrivons une petite procédure pour convertir un élément non nul en puissance de alpha : > cpuiss:=proc(t) local pal,j,flag; > if t=0 or t=1 then pal:=t fi; > j:=1;flag:=1; > while flag=1 do; > if simplify(t-alpha^j) mod p = 0 then pal:=alpha^j; flag:=0; fi; > j:=j+1; > od; > pal; > end: Appliquons-la aux éléments précédents : > 'T1'=cpuiss(T1); 10 T1 = alpha > 'T2'=cpuiss(T2); 5 T2 = alpha > 'somme'=cpuiss(somme); 26 somme = alpha > 'produit'=cpuiss(produit); 15 produit = alpha Exercice Trouver tous les polynômes primitifs unitaires de degré 3 sur GF(5). Référence Odile Papini et Jacques Wolfmann : Algèbre discrète et codes correcteurs, Springer-Verlag 1995. 3. Codes linéaires, codes de Hamming et de Reed-Muller, décodage Codes linéaires Soit q une puissance d'un nombre premier p (dans les exemples, nous choisirons q = p). Soit l'alphabet A=GF(q). A^n est alors un espace vectoriel de dimension n sur A. Un sous-espace vectoriel de dimension k de A^n s'appelle un (n, k)-code linéaire (ou un (n, k, d)-code linéaire, si l'on souhaite mettre en évidence sa distance minimale d). Sa taille est alors égale à q^k. On peut démontrer l'inégalité suivante : d<=n-k+1, appelée borne de singleton. Un code pour lequel cette borne est atteinte (c-à-d l'égalité est réalisée) est dit Maximum Distance Separable (MDS). Le poids d'un mot de code est le nombre de ses lettres différentes de zéro. Dans le cas d'un code linéaire, il est facile de montrer que sa distance minimale est égale au minimum des poids des mots autres que (0, 0, ..., 0). Matrice génératrice Une matrice G à éléments dans A, possédant k lignes et n colonnes (k<=n), de rang k, s'appelle une matrice génératrice d'un (n, k)-code linéaire C. Le code C est alors l'ensemble des vecteurs-lignes uG, où u est un vecteur-ligne quelconque de A^k. Si la sous-matrice formée par les k premières colonnes de G est une matrice identité, le code C est dit systématique. On a alors (u[1], u[2], ..., u[k])G = (u[1], u[2], ..., u[k], x[k+1], x[k+2], ..., x[n]). Les k premières composantes s'appellent symboles d'information et les n - k suivantes symboles de contrôle ou de redondance. On peut montrer que tout code linéaire est équivalent à un code systématique. Exemple > restart; > with(linalg): Warning, new definition for norm Warning, new definition for trace Choix des paramètres : > p:=5;n:=7;k:=4; p := 5 n := 7 k := 4 Construction d'une matrice génératrice G d'un (n, k)-code linéaire systématique sur GF(p) : > id:=y->diag(seq(1,i=1..y)): > id1:=id(k); [1 0 0 0] [ ] [0 1 0 0] id1 := [ ] [0 0 1 0] [ ] [0 0 0 1] > B:=randmatrix(k,n-k,entries=rand(0..p-1)); [2 0 4] [ ] [0 1 1] B := [ ] [2 4 1] [ ] [3 1 4] > G:=concat(id1,B); [1 0 0 0 2 0 4] [ ] [0 1 0 0 0 1 1] G := [ ] [0 0 1 0 2 4 1] [ ] [0 0 0 1 3 1 4] Calcul de uG où u quelconque : > u:=vector(k): > uG:=evalm(u&*G); uG := [u[1], u[2], u[3], u[4], 2 u[1] + 2 u[3] + 3 u[4], u[2] + 4 u[3] + u[4], 4 u[1] + u[2] + u[3] + 4 u[4]] Détermination de tous les mots du code C de matrice génératrice G : > Lcode:=proc(G) local C,i,t,b,x,j; > C:=array[1..p^k]; > for i from 0 to p^k-1 do; > t:=convert(i,base,p); > b:=seq(0,j=1..k-nops(t)); > x:=convert([op(t),b],vector); > C[i+1]:=convert(evalm(x&*G),list) mod p; > od; > convert(C,set); > end: > C:=Lcode(G): NB : Je n'ai pas fait afficher le résultat qui est trop volumineux. Calcul de la distance minimale : > Lpoids:=proc(C) local Cstar,Pmin,i,mot,Pmot,t; > Cstar:=C minus {[seq(0,j=1..n)]};Pmin:=n; > for i from 1 to p^k-1 do; > mot:=op(i,Cstar);Pmot:=0; > for t from 1 to n do; > if op(t,mot)<>0 then Pmot:=Pmot+1 fi; > od; > if Pmot od; > Pmin; > end: > d:=Lpoids(C); d := 2 Vérification de la borne de singleton : > d<=n-k+1; 2 <= 4 Matrice de contrôle Une matrice H qui est génératrice de l'espace vectoriel orthogonal de C (pour le produit scalaire usuel) s'appelle une matrice de contrôle de C. C est alors le noyau de l'application linéaire définie par H. Une matrice de contrôle est particulièrement utile pour le décodage. H et G sont liées par la relation suivante : GH' = 0, où H' désigne la transposée de H. Réciproquement, toute matrice H de rang maximal vérifiant cette relation est une matrice de contrôle de C. Dans le cas d'un code systématique C engendré par une matrice G = (concaténation de la matrice identité à k colonnes et d'une matrice B à n - k colonnes), alors une matrice de contrôle peut être ainsi formée : H = (concaténation de la transposée de B et de l'opposée de la matrice identité à n - k colonnes). Suite de l'exemple Construction de H : > tB:=evalm(transpose(B)); [2 0 2 3] [ ] tB := [0 1 4 1] [ ] [4 1 1 4] > id2:=id(n-k); [1 0 0] [ ] id2 := [0 1 0] [ ] [0 0 1] > H:=concat(tB,-id2); [2 0 2 3 -1 0 0] [ ] H := [0 1 4 1 0 -1 0] [ ] [4 1 1 4 0 0 -1] Vérification de la relation GH' = 0 : > evalm(G&*transpose(H)); [0 0 0] [ ] [0 0 0] [ ] [0 0 0] [ ] [0 0 0] Vérification que les mots de C appartiennent au noyau de H : > verif:=proc(C) local ze,out,i,x,Hx,j; > ze:=[seq(0,j=1..n-k)];out:='vrai'; > for i from 1 to p^k do; > x:=convert(op(i,C),vector); > Hx:=convert(evalm(H&*x),list) mod p; > if Hx<>ze then out:='faux';i:=p^k+1;fi; > od; > out; > end: > verif(C); vrai Remarque La distance minimale d'un code linéaire peut aussi s'obtenir directement à partir d'une matrice de contrôle. En effet, elle est égale au plus petit entier non nul d tel qu'il existe d colonnes de H linéairement dépendantes. Dans l'exemple considéré, on voit que la troisième et la quatrième colonnes sont linéairement dépendantes. Exercice Construire et déterminer la distance minimale du (6, 2, d)-code linéaire sur GF(5^2) engendré par la matrice G:=MATRIX([[1,0,1, alpha,alpha^7,alpha^5,alpha^17],[0,1,alpha^8,0,alpha^2,alpha^9,1]]), où alpha est une racine du polynôme primitif suivant : poly:=alpha^2+alpha+2. Codes de Hamming On appelle code de Hamming binaire de longueur 2^m-1 tout code admettant comme matrice de contrôle H une matrice dont les 2^m-1 colonnes sont tous les vecteurs de GF(2)^m sauf le vecteur nul. Un code de Hamming est un (2^m-1, 2^m-1-m, 3)-code linéaire. Procédure pour construire une matrice de contrôle > restart; > with(linalg): Warning, new definition for norm Warning, new definition for trace > hamming:=proc(m) local LC,j,co,h,ze,i; > LC:=array(1..2^m-1); > for j from 1 to 2^m-1 do; > co:=convert(j,base,2);h:=nops(co); > ze:=seq(0,i=1..m-h); > LC[j]:=[op(co),ze]; > od; > LC:=convert(LC,list); > evalm(transpose(matrix(LC))); > end: Exemples > 'H(3)'=hamming(3); [1 0 1 0 1 0 1] [ ] H(3) = [0 1 1 0 0 1 1] [ ] [0 0 0 1 1 1 1] > 'H(4)'=hamming(4); [1 ,0 ,1 ,0 ,1 ,0 ,1 ,0 ,1 ,0 ,1 ,0 ,1 ,0 ,1] [ ] [0 ,1 ,1 ,0 ,0 ,1 ,1 ,0 ,0 ,1 ,1 ,0 ,0 ,1 ,1] H(4) = [ ] [0 ,0 ,0 ,1 ,1 ,1 ,1 ,0 ,0 ,0 ,0 ,1 ,1 ,1 ,1] [ ] [0 ,0 ,0 ,0 ,0 ,0 ,0 ,1 ,1 ,1 ,1 ,1 ,1 ,1 ,1] Exercice Etudier les codes simplexes qui sont définis comme étant les orthogonaux des codes de Hamming. Codes de Reed-Muller On appelle code de Reed-Muller du premier ordre de longueur 2^m tout code binaire admettant comme matrice génératrice G une matrice dont les m+1 lignes sont ainsi définies : pour i variant de 1 à m, la i-ième ligne est formée d'une alternance de blocs de 0 et de blocs de 1, de longueur constante 2^(m-i); la (m+1)-ième ligne est entièrement constituée de 1. Un code de Reed-Muller du premier ordre est un (2^m, m+1, 2^(m-1))-code linéaire. Procédure pour construire une matrice génératrice > reedM:=proc(m) local LC,i,ze,un,bl,j1,j2,j3,j4; > LC:=array(1..m+1); > for i from 1 to m do; > ze:=seq(0,j1=1..2^(m-i));un:=seq(1,j2=1..2^(m-i));bl:=ze,un; > LC[i]:=[seq(bl,j3=1..2^(i-1))]; > od; > LC[m+1]:=[seq(1,j4=1..2^m)]; > LC:=convert(LC,list); > matrix(LC); > end: Exemples > 'G(3)'=reedM(3); [0 0 0 0 1 1 1 1] [ ] [0 0 1 1 0 0 1 1] G(3) = [ ] [0 1 0 1 0 1 0 1] [ ] [1 1 1 1 1 1 1 1] > 'G(4)'=reedM(4); G(4) = [0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1] [0 , 0 , 0 , 0 , 1 , 1 , 1 , 1 , 0 , 0 , 0 , 0 , 1 , 1 , 1 , 1] [0 , 0 , 1 , 1 , 0 , 0 , 1 , 1 , 0 , 0 , 1 , 1 , 0 , 0 , 1 , 1] [0 , 1 , 0 , 1 , 0 , 1 , 0 , 1 , 0 , 1 , 0 , 1 , 0 , 1 , 0 , 1] [1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1] Méthode de décodage des codes linéaires Soient C un (n, k, d)-code linéaire sur l'alphabet A = GF(q), G une matrice génératrice et H une matrice de contrôle. Construisons une matrice S de q^(n-k) lignes et 2 colonnes. Définissons : S[1,1] := le vecteur 0 de C. S[2,1] := un vecteur de poids minimal de A^n moins C. S[3,1] := un vecteur de poids minimal de A^n moins la réunion de C et de l'ensemble obtenu en ajoutant S[2,1] aux éléments de C. S[4,1] := un vecteur de poids minimal de A^n moins la réunion de C, de l'ensemble obtenu en ajoutant S[2,1] aux éléments de C et de l'ensemble obtenu en ajoutant S[3,1] aux éléments de C. Etc. S[i,2], lui, est défini par H*S[i,1]. Le décodage d'un mot reçu y de A^n peut se faire ainsi : calcul de H*y (le syndrome de y), détermination de S[i,1] (mot-erreur) tel que H*y=S[i,2], affichage de x := y-S[i,1]. Soit e := la partie entière de (d-1)/2. Si y est porteur d'au plus e erreurs, alors x est bien le mot envoyé. Nous traiterons ici le cas q=p premier. Procédures > restart; > with(linalg): Warning, new definition for norm Warning, new definition for trace Pour déterminer un élément de poids minimum dans un ensemble : > elmin:=proc(ens,p,n) local Pmin,Emin,i,mot,Pmot,t; > Pmin:=n;Emin:=op(1,ens); > for i from 1 to nops(ens) do; > mot:=op(i,ens);Pmot:=0; > for t from 1 to n do; > if op(t,mot)<>0 then Pmot:=Pmot+1 fi; > od; > if Pmot od; > Emin; > end: Pour construire un tableau des mots-erreurs et de leurs syndromes : > syndrome:=proc(p,n,k,G,H) local An,C,i,t,b,x,S,ens,u,j,el,s; > An:=array(1..p^n);C:=array(1..p^k); > for i from 0 to p^n-1 do; > t:=convert(i,base,p); > b:=seq(0,j=1..n-nops(t)); > An[i+1]:=[op(t),b]; > if i C[i+1]:=convert(evalm(x&*G),list) mod p;fi; > od; > An:=convert(An,set); > C:=convert(C,set); > S:=array(1..p^(n-k),1..2); > S[1,1]:=[seq(0,s=1..n)]; > S[1,2]:=[seq(0,s=1..n-k)]; > ens:=An minus C; > for i from 2 to p^(n-k) do; > S[i,1]:=elmin(ens,p,n); > u:=convert(S[i,1],vector); > S[i,2]:=convert(evalm(H&*u),list) mod p; > for j from 1 to p^k do; > el:=S[i,1]+op(j,C) mod p; > ens:=ens minus {el}; > od; > od; > convert(S,matrix); > end: Pour décoder un mot reçu : > Ldecode:=proc(y,p,H,S) local s,flag,i,u; > s:=convert(evalm(H&*y),list) mod p; > flag:=1;i:=1; > while flag=1 do; > if S[i,2]=s then u:=S[i,1];flag:=0;fi; > i:=i+1; > od; > y-u mod p; > end: Exemple > p:=2;n:=5;k:=2; p := 2 n := 5 k := 2 > G:=matrix([[1,0,1,1,0],[0,1,1,0,1]]); [1 0 1 1 0] G := [ ] [0 1 1 0 1] > H:=matrix([[0,1,-1,0,0],[1,0,0,-1,0],[1,1,0,0,-1]]); [0 1 -1 0 0] [ ] H := [1 0 0 -1 0] [ ] [1 1 0 0 -1] NB : Le code ainsi défini a pour distance minimale 3. Il peut donc corriger 1 erreur. > S:=syndrome(p,n,k,G,H); [[0, 0, 0, 0, 0] [0, 0, 0]] [ ] [[1, 0, 0, 0, 0] [0, 1, 1]] [ ] [[0, 1, 0, 0, 0] [1, 0, 1]] [ ] [[0, 0, 1, 0, 0] [1, 0, 0]] S := [ ] [[0, 0, 0, 1, 0] [0, 1, 0]] [ ] [[0, 0, 0, 0, 1] [0, 0, 1]] [ ] [[1, 1, 0, 0, 0] [1, 1, 0]] [ ] [[0, 1, 0, 1, 0] [1, 1, 1]] > y:=[1,1,1,0,1]; y := [1, 1, 1, 0, 1] > x:=Ldecode(y,p,H,S); x := [0, 1, 1, 0, 1] On constate que le mot x appartient à C, car : > 'Hx'=convert(evalm(H&*x),list) mod p; Hx = [0, 0, 0] Par conséquent, le décodage a corrigé une erreur qui portait sur le premier bit. Exercice Décoder quelques mots au hasard du code de Reed-Muller G(4) vu précédemment. Références Odile Papini et Jacques Wolfmann : Algèbre discrète et codes correcteurs, Springer-Verlag 1995. Steven Roman : Introduction to coding and information theory, Springer-Verlag 1997. 4. Codes cycliques, générateur, décodage Codes cycliques Les codes cycliques sont des codes linéaires particuliers, représentés généralement sous forme polynomiale. Soient q une puissance d'un nombre premier p et n un entier. Un code cyclique de longueur n sur F = GF(q) est un idéal de F[x]/((x^n-1)). Soit g(x) un diviseur de degré t de x^n-1. Alors g(x) est un générateur d'un tel idéal. Posons k = n - t. En multipliant g(x) par l'ensemble des polynômes de degrés < k, on obtient un code de dimension k. Un tel code est qualifié de cyclique, car, si a[0]+a[1]*x+a[2]*x^2+etc+a[n-1]*x^(n-1) appartient au code, alors a[n-1]+a[0]*x+a[1]*x^2+etc+a[n-2]*x^(n-1) aussi.Pour simplifier, nous nous limiterons au cas q = p, plus facile à traiter. Procédures Une première procédure nous permettra de construire in extenso un code cyclique à partir d'un générateur. Une seconde procédure est destinée au calcul de la distance minimale d du code ainsi construit. > restart; > Ccode:=proc(p,n,g) local t,k,V,i,a,h,pol,j; > t:=degree(g,x);k:=n-t;V:=array(1..p^k); > for i from 0 to p^k-1 do; > a:=convert(i,base,p);h:=nops(a);pol:=0; > for j from 1 to h do; > pol:=pol+op(j,a)*x^(j-1) mod p; > od; > V[i+1]:=expand(pol*g) mod p; > od; > convert(V,list); > end: > Cpoids:=proc(C) local h,S,i,pol,dpol,Ppol,j,w; > h:=nops(C);S:={}; > for i from 1 to h do; > pol:=op(i,C);dpol:=degree(pol,x);Ppol:=0; > for j from 0 to dpol do; > if coeff(pol,x,j)<>0 then w:=1 else w:=0 fi; > Ppol:=Ppol+w; > od; > S:=S union {Ppol}; > od; > min(op(S minus {0})); > end: Exemples Premier exemple : > p:=2;n:=7; p := 2 n := 7 > Factor(x^n-1) mod p; 3 3 2 (x + x + 1) (x + 1) (x + x + 1) > g:=op(3,"); 3 2 g := x + x + 1 > C:=Ccode(p,n,g); 3 2 4 3 4 2 5 4 2 C := [0, x + x + 1, x + x + x, x + x + x + 1, x + x + x , 3 5 4 3 5 2 5 6 5 3 x + 1 + x + x , x + x + x + x , x + 1 + x , x + x + x , 2 6 5 4 6 5 x + 1 + x + x , x + x + x + x , 6 5 3 4 2 4 2 6 3 6 4 x + x + x + x + x + x + 1, x + x + x + x , x + x + 1, 2 6 3 6 x + x + x , x + x + 1 + x ] > d:=Cpoids(C); d := 3 Deuxième exemple : > p:=2;n:=15; p := 2 n := 15 > Factor(x^n-1) mod p; 4 4 3 2 4 3 (x + x + 1) (x + x + x + x + 1) (x + 1) (x + x + 1) 2 (x + x + 1) > g:=expand(op(2,")*op(4,")) mod p; 8 4 2 g := x + x + x + x + 1 > C:=Ccode(p,n,g); 8 4 2 9 5 3 2 C := [0, x + x + x + x + 1, x + x + x + x + x, 9 5 3 8 4 10 6 4 3 2 x + x + x + x + x + 1, x + x + x + x + x , 8 10 6 3 9 5 10 6 4 x + x + 1 + x + x + x , x + x + x + x + x + x , 10 6 2 9 5 8 11 7 5 4 3 x + x + x + x + x + x + 1, x + x + x + x + x , 8 2 11 7 5 3 9 2 11 7 4 x + x + x + 1 + x + x + x + x , x + x + x + x + x + x , 9 8 11 7 10 6 2 11 7 5 x + x + 1 + x + x , x + x + x + x + x + x , 11 7 5 4 10 6 8 x + x + x + x + x + x + x + x + 1, 9 3 10 6 11 7 x + x + x + x + x + x + x , 10 6 4 3 2 9 8 11 7 x + x + x + x + x + x + x + 1 + x + x , 12 8 6 5 4 2 12 6 5 x + x + x + x + x , x + x + 1 + x + x + x , 9 3 2 12 8 6 4 12 6 9 3 x + x + x + x + x + x + x + x , x + x + x + x + 1, 10 3 2 12 8 5 4 10 3 12 5 x + x + x + x + x + x , x + x + 1 + x + x + x + x , 9 10 12 8 12 4 9 2 10 x + x + x + x + x , x + x + x + x + x + 1, 11 7 3 12 8 6 x + x + x + x + x + x , 12 6 4 11 7 3 2 x + x + x + x + x + x + x + x + 1, 12 8 6 5 11 7 9 2 x + x + x + x + x + x + x + x + x, 9 5 4 11 7 12 6 x + x + x + 1 + x + x + x + x , 10 4 2 11 7 12 8 11 7 10 12 x + x + x + x + x + x + x , x + x + x + x + 1 + x , 9 5 3 10 4 11 7 12 8 x + x + x + x + x + x + x + x + x + x , 3 2 5 11 7 9 10 12 1 + x + x + x + x + x + x + x + x , 13 9 7 6 5 x + x + x + x + x , 8 4 2 13 9 7 6 5 x + x + x + x + 1 + x + x + x + x + x , 3 2 13 7 6 3 8 4 13 7 6 x + x + x + x + x + x , x + x + x + 1 + x + x + x , 10 4 3 2 13 9 7 5 x + x + x + x + x + x + x + x , 8 10 3 13 9 7 5 x + x + 1 + x + x + x + x + x + x , 10 4 13 7 10 2 8 13 7 x + x + x + x + x , x + x + x + 1 + x + x , 11 4 3 13 9 6 x + x + x + x + x + x , 8 2 11 3 13 9 6 x + x + x + 1 + x + x + x + x + x , 5 2 11 4 13 6 5 8 11 13 6 x + x + x + x + x + x + x , x + x + 1 + x + x + x , 10 2 11 13 9 8 4 10 11 13 9 x + x + x + x + x , x + x + x + 1 + x + x + x + x , 5 3 10 11 13 x + x + x + x + x + x , 13 3 2 4 5 11 8 10 x + 1 + x + x + x + x + x + x + x , 12 8 4 13 9 7 2 12 13 9 7 x + x + x + x + x + x , x + x + 1 + x + x + x + x , 5 3 2 12 8 4 13 7 x + x + x + x + x + x + x + x + x , 12 5 3 13 7 x + x + x + 1 + x + x , 10 6 3 2 12 8 13 9 7 x + x + x + x + x + x + x + x + x , 4 10 6 3 12 13 9 7 x + x + 1 + x + x + x + x + x + x + x , 5 10 6 12 8 13 7 x + x + x + x + x + x + x + x , 13 2 4 5 6 7 10 12 x + 1 + x + x + x + x + x + x + x , 11 5 3 12 8 13 9 x + x + x + x + x + x + x , 12 5 4 11 3 2 13 9 x + x + x + x + x + x + x + 1 + x + x , 2 11 12 8 13 13 4 11 12 x + x + x + x + x + x , x + 1 + x + x + x , 10 6 4 2 11 5 12 8 13 9 x + x + x + x + x + x + x + x + x + x , 13 5 6 11 9 10 12 x + 1 + x + x + x + x + x + x + x , 13 3 4 6 11 8 10 12 x + x + x + x + x + x + x + x + x , 13 3 2 6 11 10 12 x + 1 + x + x + x + x + x + x , 14 10 8 7 6 4 2 14 10 7 6 x + x + x + x + x , x + x + x + 1 + x + x + x + x , 9 5 3 2 14 10 8 7 6 x + x + x + x + x + x + x + x + x + x , 9 5 3 4 14 10 7 6 x + x + x + x + 1 + x + x + x + x , 4 3 2 14 8 7 3 14 7 x + x + x + x + x + x , x + 1 + x + x + x , 9 5 4 14 8 7 2 9 5 14 7 x + x + x + x + x + x + x , x + x + x + 1 + x + x , 11 5 4 3 14 10 8 6 x + x + x + x + x + x + x + x , 2 11 5 3 14 10 6 x + x + 1 + x + x + x + x + x + x , 9 2 11 4 14 10 8 6 x + x + x + x + x + x + x + x + x , 9 11 14 10 6 2 11 5 14 8 x + 1 + x + x + x + x , x + x + x + x + x , 4 11 5 14 9 3 11 14 8 x + x + 1 + x + x + x , x + x + x + x + x + x , 3 2 4 11 9 14 12 5 4 14 10 7 1 + x + x + x + x + x + x , x + x + x + x + x + x , 8 2 12 5 14 10 7 x + x + x + 1 + x + x + x + x + x , 9 3 2 12 4 14 10 7 x + x + x + x + x + x + x + x + x , 12 8 9 3 14 10 7 x + x + x + x + 1 + x + x + x , 6 3 2 12 5 14 7 x + x + x + x + x + x + x , 8 4 6 3 12 5 14 7 x + x + x + 1 + x + x + x + x + x + x , 9 6 12 14 7 x + x + x + x + x + x , 2 4 6 8 7 9 12 14 1 + x + x + x + x + x + x + x + x , 11 3 12 14 10 x + x + x + x + x , 12 8 4 11 3 2 14 10 x + x + x + x + x + x + x + 1 + x + x , 9 5 2 11 12 14 10 x + x + x + x + x + x + x + x , 4 5 11 8 9 10 12 14 1 + x + x + x + x + x + x + x + x , 6 4 2 11 12 14 6 11 8 12 14 x + x + x + x + x + x , 1 + x + x + x + x + x + x , 3 4 5 6 11 9 12 14 x + x + x + x + x + x + x + x + x , 3 2 5 6 11 8 9 12 14 1 + x + x + x + x + x + x + x + x + x , 13 9 5 14 10 8 x + x + x + x + x + x , 4 2 13 9 5 14 10 x + x + x + 1 + x + x + x + x + x , 3 2 13 14 10 8 3 4 13 14 10 x + x + x + x + x + x + x , x + x + 1 + x + x + x , 6 4 3 2 13 9 5 14 8 x + x + x + x + x + x + x + x + x , 6 3 13 9 5 14 x + 1 + x + x + x + x + x + x , 6 4 13 14 8 13 2 6 14 x + x + x + x + x + x , x + 1 + x + x + x , 11 7 4 3 13 9 14 10 8 x + x + x + x + x + x + x + x + x , 2 11 7 3 13 9 14 10 x + x + 1 + x + x + x + x + x + x + x , 5 2 11 7 4 13 14 10 8 x + x + x + x + x + x + x + x + x + x , 13 5 11 7 10 14 x + 1 + x + x + x + x + x , 6 2 11 7 13 9 14 8 x + x + x + x + x + x + x + x , 13 4 6 11 7 9 14 x + 1 + x + x + x + x + x + x + x , 13 3 5 6 11 8 7 14 x + x + x + x + x + x + x + x + x , 13 3 2 4 5 6 11 7 14 x + 1 + x + x + x + x + x + x + x + x , 12 6 4 13 9 14 10 x + x + x + x + x + x + x , 8 2 12 6 13 9 14 10 x + x + x + 1 + x + x + x + x + x + x , 5 3 2 12 6 4 13 14 10 x + x + x + x + x + x + x + x + x + x , 13 3 5 6 8 10 12 14 x + 1 + x + x + x + x + x + x + x , 3 2 12 13 9 14 x + x + x + x + x + x , 13 3 4 8 9 12 14 x + 1 + x + x + x + x + x + x + x , 13 5 12 14 13 2 4 5 8 12 14 x + x + x + x + x , x + 1 + x + x + x + x + x + x , 11 7 5 3 12 6 13 9 14 10 13 x + x + x + x + x + x + x + x + x + x , x + 1 + x 3 2 4 5 6 11 8 7 9 10 12 14 + x + x + x + x + x + x + x + x + x + x + x + x , 13 2 6 11 7 10 12 14 x + x + x + x + x + x + x + x + x , 13 4 6 11 8 7 10 12 14 x + 1 + x + x + x + x + x + x + x + x , 13 2 4 5 11 7 9 12 14 x + x + x + x + x + x + x + x + x , 13 5 11 8 7 9 12 14 x + 1 + x + x + x + x + x + x + x + x , 13 3 4 11 7 12 14 x + x + x + x + x + x + x + x , 13 3 2 11 8 7 12 14 x + 1 + x + x + x + x + x + x + x ] > d:=Cpoids(C); d := 5 Troisième exemple : > p:=7;n:=10; p := 7 n := 10 > Factor(x^n-1) mod p; 4 3 2 4 3 2 (x + 6 x + x + 6 x + 1) (x + x + x + x + 1) (x + 1) (x + 6) > g:=expand(op(1,")*op(2,")) mod p; 2 4 6 8 g := 1 + x + x + x + x > C:=Ccode(p,n,g); 2 4 6 8 2 4 6 8 C := [0, 1 + x + x + x + x , 2 + 2 x + 2 x + 2 x + 2 x , 2 4 6 8 2 4 6 8 3 + 3 x + 3 x + 3 x + 3 x , 4 + 4 x + 4 x + 4 x + 4 x , 2 4 6 8 2 4 6 8 5 + 5 x + 5 x + 5 x + 5 x , 6 + 6 x + 6 x + 6 x + 6 x , 3 5 7 9 x + x + x + x + x , 3 5 7 9 2 4 6 8 x + x + x + x + x + 1 + x + x + x + x , 2 4 6 8 3 5 7 9 2 + 2 x + 2 x + 2 x + 2 x + x + x + x + x + x , 2 4 6 8 3 5 7 9 3 + 3 x + 3 x + 3 x + 3 x + x + x + x + x + x , 2 4 6 8 3 5 7 9 4 + 4 x + 4 x + 4 x + 4 x + x + x + x + x + x , 2 4 6 8 3 5 7 9 5 + 5 x + 5 x + 5 x + 5 x + x + x + x + x + x , 3 5 7 9 2 4 6 8 x + x + x + x + x + 6 + 6 x + 6 x + 6 x + 6 x , 3 5 7 9 2 x + 2 x + 2 x + 2 x + 2 x , 2 4 6 8 3 5 7 9 1 + x + x + x + x + 2 x + 2 x + 2 x + 2 x + 2 x , 2 4 6 8 3 5 7 9 2 + 2 x + 2 x + 2 x + 2 x + 2 x + 2 x + 2 x + 2 x + 2 x , 2 4 6 8 3 5 7 9 3 + 3 x + 3 x + 3 x + 3 x + 2 x + 2 x + 2 x + 2 x + 2 x , 2 4 6 8 3 5 7 9 4 + 4 x + 4 x + 4 x + 4 x + 2 x + 2 x + 2 x + 2 x + 2 x , 2 4 6 8 3 5 7 9 5 + 5 x + 5 x + 5 x + 5 x + 2 x + 2 x + 2 x + 2 x + 2 x , 2 4 6 8 3 5 7 9 6 + 6 x + 6 x + 6 x + 6 x + 2 x + 2 x + 2 x + 2 x + 2 x , 3 5 7 9 3 x + 3 x + 3 x + 3 x + 3 x , 2 4 6 8 3 5 7 9 1 + x + x + x + x + 3 x + 3 x + 3 x + 3 x + 3 x , 2 4 6 8 3 5 7 9 2 + 2 x + 2 x + 2 x + 2 x + 3 x + 3 x + 3 x + 3 x + 3 x , 2 4 6 8 3 5 7 9 3 + 3 x + 3 x + 3 x + 3 x + 3 x + 3 x + 3 x + 3 x + 3 x , 2 4 6 8 3 5 7 9 4 + 4 x + 4 x + 4 x + 4 x + 3 x + 3 x + 3 x + 3 x + 3 x , 2 4 6 8 3 5 7 9 5 + 5 x + 5 x + 5 x + 5 x + 3 x + 3 x + 3 x + 3 x + 3 x , 2 4 6 8 3 5 7 9 6 + 6 x + 6 x + 6 x + 6 x + 3 x + 3 x + 3 x + 3 x + 3 x , 3 5 7 9 4 x + 4 x + 4 x + 4 x + 4 x , 2 4 6 8 3 5 7 9 1 + x + x + x + x + 4 x + 4 x + 4 x + 4 x + 4 x , 2 4 6 8 3 5 7 9 2 + 2 x + 2 x + 2 x + 2 x + 4 x + 4 x + 4 x + 4 x + 4 x , 2 4 6 8 3 5 7 9 3 + 3 x + 3 x + 3 x + 3 x + 4 x + 4 x + 4 x + 4 x + 4 x , 2 4 6 8 3 5 7 9 4 + 4 x + 4 x + 4 x + 4 x + 4 x + 4 x + 4 x + 4 x + 4 x , 2 4 6 8 3 5 7 9 5 + 5 x + 5 x + 5 x + 5 x + 4 x + 4 x + 4 x + 4 x + 4 x , 2 4 6 8 3 5 7 9 6 + 6 x + 6 x + 6 x + 6 x + 4 x + 4 x + 4 x + 4 x + 4 x , 3 5 7 9 5 x + 5 x + 5 x + 5 x + 5 x , 2 4 6 8 3 5 7 9 1 + x + x + x + x + 5 x + 5 x + 5 x + 5 x + 5 x , 2 4 6 8 3 5 7 9 2 + 2 x + 2 x + 2 x + 2 x + 5 x + 5 x + 5 x + 5 x + 5 x , 2 4 6 8 3 5 7 9 3 + 3 x + 3 x + 3 x + 3 x + 5 x + 5 x + 5 x + 5 x + 5 x , 2 4 6 8 3 5 7 9 4 + 4 x + 4 x + 4 x + 4 x + 5 x + 5 x + 5 x + 5 x + 5 x , 2 4 6 8 3 5 7 9 5 + 5 x + 5 x + 5 x + 5 x + 5 x + 5 x + 5 x + 5 x + 5 x , 2 4 6 8 3 5 7 9 6 + 6 x + 6 x + 6 x + 6 x + 5 x + 5 x + 5 x + 5 x + 5 x , 3 5 7 9 6 x + 6 x + 6 x + 6 x + 6 x , 2 4 6 8 3 5 7 9 1 + x + x + x + x + 6 x + 6 x + 6 x + 6 x + 6 x , 2 4 6 8 3 5 7 9 2 + 2 x + 2 x + 2 x + 2 x + 6 x + 6 x + 6 x + 6 x + 6 x , 2 4 6 8 3 5 7 9 3 + 3 x + 3 x + 3 x + 3 x + 6 x + 6 x + 6 x + 6 x + 6 x , 2 4 6 8 3 5 7 9 4 + 4 x + 4 x + 4 x + 4 x + 6 x + 6 x + 6 x + 6 x + 6 x , 2 4 6 8 3 5 7 9 5 + 5 x + 5 x + 5 x + 5 x + 6 x + 6 x + 6 x + 6 x + 6 x , 2 4 6 8 3 5 7 9 6 + 6 x + 6 x + 6 x + 6 x + 6 x + 6 x + 6 x + 6 x + 6 x ] > d:=Cpoids(C); d := 5 Remarque Lorsque q=p^m avec m>1, voici un exemple montrant comment travailler avec Maple : > n:=5; n := 5 > p:=3; p := 3 > m:=4; m := 4 > poly:=alpha^4+alpha+2; 4 poly := alpha + alpha + 2 > Primitive(poly) mod p; true > alias(alpha=RootOf(poly)): > Factor(x^n-1,alpha) mod p; 2 2 3 (x + alpha + alpha + 1) (x + alpha + 1) (x + alpha + 2 alpha + 1) 3 2 (x + 2 alpha + alpha + 1) (x + 2) > g:=collect(simplify(op(1,")*op(2,")*op(3,")) mod p,x); 3 2 3 2 2 3 g := x + (2 alpha + alpha ) x + (alpha + 2 + alpha ) x + 1 2 + alpha + alpha Exercice Déterminer les distances minimales de plusieurs (6, 2, d)- codes cycliques sur GF(5^2) décrit par le polynôme primitif suivant : poly:=alpha^2+alpha+2. Méthode de décodage des codes cycliques Voici l'algorithme du piégeage d'erreurs. Notons par w( ) la fonction donnant le poids d'un polynôme (c-à-d le nombre de ses coefficients non nuls). Désignons par S( ) la fonction qui associe à un polynôme le reste de sa division par g(x) := un générateur d'un code cyclique. Soit encore emax := la partie entière de (d-1)/2, où d est la distance minimale du code. Maintenant, considérons un mot reçu y(x). Il s'agit de chercher le mot-erreur u(x) qui, retranché de y(x), livrera le mot envoyé si au plus emax erreurs se sont produites. Il peut être déterminé ainsi : Calcul de S(y(x)). Si S(y(x)) = 0 alors u(x) := 0. Sinon et si w(S(y(x)))<=emax alors u(x) := S(y(x)). Sinon on cherche le plus petit entier s tel que w(S(x^s*y(x)))<=emax et alors u(x) := x^(n-s)*S(x^s*y(x)). Tous les calculs doivent être effectués dans le corps de base (qu'on supposera être GF(p) avec p premier) avec en plus une réduction modulo x^n-1 si nécessaire. Procédures > restart; Poids d'un polynôme : > w:=proc(pol) local dpol,wpol,j,wj; > dpol:=degree(pol,x);wpol:=0; > for j from 0 to dpol do; > if coeff(pol,x,j)<>0 then wj:=1 else wj:=0 fi; > wpol:=wpol+wj; > od; > wpol; > end: Algorithme de décodage : > Cdecode:=proc(p,n,k,d,g,y) local emax,Sy,u,flag,s,Syxs; > emax:=floor((d-1)/2); > Sy:=Rem(y,g,x) mod p;u:=0; > if Sy=0 then u:=0; > elif w(Sy)<=emax then u:=Sy; > else flag:=1;s:=1;while flag=1 and s Syxs:=Rem(y*x^s,g,x) mod p; > if w(Syxs)<=emax then u:=Syxs*x^(n-s);flag:=0; fi; > s:=s+1; > od; > fi; > simplify(y-u,[x^n=1]) mod p; > end: Exemple > p:=7;n:=10;k:=2;d:=5;g:=1+x^2+x^4+x^6+x^8; p := 7 n := 10 k := 2 d := 5 2 4 6 8 g := 1 + x + x + x + x Considérons le mot suivant appartenant au code : > c:=5*x^9+3*x^8+5*x^7+3*x^6+5*x^5+3*x^4+5*x^3+3*x^2+5*x+3; 9 8 7 6 5 4 3 2 c := 5 x + 3 x + 5 x + 3 x + 5 x + 3 x + 5 x + 3 x + 5 x + 3 Imaginons que deux erreurs se sont produites lors de la transmission et que le mot reçu est : > y:=2*x^9+3*x^8+5*x^7+3*x^6+3*x^4+5*x^3+3*x^2+5*x+3; 9 8 7 6 4 3 2 y := 2 x + 3 x + 5 x + 3 x + 3 x + 5 x + 3 x + 5 x + 3 Le décodage de y devrait donner c. Vérifions : > Cdecode(p,n,k,d,g,y); 9 8 7 6 5 4 3 2 5 x + 3 x + 5 x + 3 x + 5 x + 3 x + 5 x + 3 x + 5 x + 3 C'est OK ! Exercice Soit C le code cyclique binaire de longueur 15 et de générateur g(x):=x^8+x^7+x^6+x^4+1. Décoder le mot reçu suivant : y:= x^14+x^13+x^10+x^7+x^3+1 et vérifier que son décodage livre bien un mot du code C. Références Odile Papini et Jacques Wolfmann : Algèbre discrète et codes correcteurs, Springer-Verlag 1995. Norman L. Biggs : Discrete Mathematics, Oxford Science Publications, Revised Edition 1989. 5. Codes BCH, codes de Reed-Solomon, transformée de Mattson-Solomon Codes BCH Les codes BCH (Bose, Chaudhuri, Hocquenghem) sont des cas particuliers de codes cycliques. Ils permettent de prévoir la distance minimum avant la construction, ce qui en fait un outil très utilisé dans la pratique. Soit q une puissance d'un nombre premier p. Un code BCH de longueur n (où n est premier avec p) et de distance construite delta est un code cyclique sur F = GF(q), dont le générateur g(x) est le ppcm des polynômes minimaux de : beta, beta^2, ..., beta^(delta-1) , où beta est une racine n-ième primitive de l'unité. Sa distance minimale vaut au moins delta. Pour simplifier les calculs, on examinera ici le cas où q = p. Exemple explicatif Choix de p, q, n et delta : > restart; > p:=3;q:=p;n:=22;delta:=7; p := 3 q := 3 n := 22 delta := 7 Le corps des racines n-ièmes de l'unité sur F est l'extension L = GF(q^(r)) où r est le plus petit entier tel que n divise q^(r)-1, c-à-d r est l'ordre multiplicatif de q modulo n. Posons encore s tel que n*s=q^(r)-1. Calcul de r : > r:=numtheory[order](q,n); r := 5 Calcul de s : > s:=(q^r-1)/n; s := 11 Construction du corps des racines de l'unité : L est totalement déterminé par la connaissance d'un polynôme irréductible primitif de degré r à coefficients dans F. Il est possible de trouver un tel polynôme grâce à Maple, mais, pour simplifier le propos, je me contenterai de reporter un tel polynôme que j'ai trouvé dans une table de corps finis. > poly:=alpha^5+2*alpha^3+alpha^2+1; 5 3 2 poly := alpha + 2 alpha + alpha + 1 > alias(alpha=RootOf(poly)): Une racine n-ième primitive de l'unité sur F est alors beta=alpha^s. > beta:=alpha^s; 11 beta := alpha Procédure pour déterminer la classe cyclotomique de beta^j : > cyclo:=proc(j) local C,i; > C:={}; > for i from 0 to r-1 do; > C:=C union {j*q^i mod n} > od; > sort(convert(C,list)); > end: Calcul des différentes classes associées aux beta^j : > ensC:=proc() local ens,j; > ens:={}; > for j from 1 to delta-1 do; > ens:=ens union {cyclo(j)}; > od; > ens; > end: > CC:=ensC(); CC := {[4, 12, 14, 16, 20], [1, 3, 5, 9, 15], [2, 6, 8, 10, 18]} Procédure pour calculer le polynôme minimal associé à une classe cyclotomique : > minpol:=proc(C) local h; > h:=nops(C); > simplify(product(x-beta^op(k,C),k=1..h)) mod p; > end: Enfin, calcul du générateur g(x) : > gen:=proc(CC) local v,prod,j; > v:=nops(CC);prod:=1; > for j from 1 to v do; > prod:=prod*minpol(op(j,CC)); > od; > sort(expand(prod) mod p); > end: > g:=gen(CC):'g(x)'=g; 15 13 12 11 10 9 8 7 6 g(x) = x + 2 x + x + x + 2 x + 2 x + 2 x + 2 x + 2 x 5 4 3 + 2 x + x + 2 x + x + 1 Le code engendré par g(x) est donc un (n, k, d)-code avec : > 'PARAMETRES';'n'=n;'k'=n-degree(g,x);'d'>=delta; PARAMETRES n = 22 k = 7 7 <= d Vérification que g(x) est bien un diviseur de x^n-1 dans F[x] : > Rem(x^n-1,g,x) mod p; 0 Exercice Trouver un générateur d'un code BCH de longueur 63 et de distance construite 11 sur GF(2). Codes de Reed-Solomon Une classe particulière de codes BCH (voir l'article correspondant) est formée par les codes de Reed-Solomon. Ils correspondent aux paramètres suivants : q=p ^m et n=q-1 (delta pouvant être quelconque). Dans ces conditions, on peut montrer que la distance minimale d d'un tel code vaut exactement delta et que sa dimension k vaut q-delta. Nous nous proposons d'effectuer le calcul de son générateur pour p=2, q=2^8 et delta=33 (ces paramètres ont été adoptés comme norme par le Consultative Committee for Space Data System). Exemple explicatif Choix des paramètres : > p:=2;m:=8;q:=p^8;n:=q-1;delta:=33; p := 2 m := 8 q := 256 n := 255 delta := 33 Un générateur g(x) du code aura ses coefficients dans F. Ce corps peut être décrit comme le quotient de GF(p) [alpha] par un polynôme irréductible de degré m. Si, de plus, ce polynôme est primitif, alors alpha est une racine primitive de F. Le polynôme suivant remplit ces conditions : > poly:=alpha^8+alpha^6+alpha^5+alpha^4+1; 8 6 5 4 poly := alpha + alpha + alpha + alpha + 1 NB : dans la section consacrée aux codes BCH, il est procédé à la construction du corps L des racines de l'unité de F, qui constitue une extension de degré r de F. Dans le cas des codes de Reed-Solomon, on a évidemment : r = 1, ce qui implique que L = F; et : s = 1, ce qui implique que beta=alpha. Un générateur s'obtient en effectuant le produit des x-alpha^j, pour j variant de 1 à delta-1 : > G:=proc(x) local prod,j; > prod:=1; > for j from 1 to delta-1 do; > prod:=prod*(x-alpha^j); > od; > prod:=simplify(prod,[poly=0]); > sort(collect(prod mod p,x),x); > end: > g:=G(x):'g(x)'=g; 32 4 5 2 31 g(x) = x + (alpha + alpha + alpha ) x 4 7 3 5 30 + (alpha + 1 + alpha + alpha + alpha + alpha ) x 4 3 29 + (alpha + alpha + 1) x 5 4 6 2 7 28 + (alpha + alpha + alpha + alpha + alpha ) x 7 3 4 27 + (alpha + alpha + alpha + 1 + alpha ) x 7 4 6 26 + (alpha + 1 + alpha + alpha ) x 5 3 7 2 25 + (1 + alpha + alpha + alpha + alpha ) x 6 4 24 5 23 + (alpha + alpha + 1 + alpha) x + (1 + alpha + alpha ) x 4 5 2 3 7 22 + (alpha + alpha + 1 + alpha + alpha + alpha + alpha ) x 5 6 21 3 7 20 + (alpha + alpha + alpha ) x + (alpha + 1 + alpha ) x 2 4 5 6 3 19 + (alpha + alpha + alpha + alpha + alpha + alpha + 1) x 6 18 5 2 6 17 + (1 + alpha ) x + (alpha + alpha + alpha + alpha ) x 3 4 7 5 16 + (alpha + 1 + alpha + alpha + alpha ) x 2 3 6 5 15 + (1 + alpha + alpha + alpha + alpha ) x 5 2 6 14 + (alpha + alpha + alpha + alpha ) x 3 4 2 6 13 + (1 + alpha + alpha + alpha + alpha + alpha) x 5 6 7 2 12 + (alpha + alpha + alpha + alpha ) x 7 2 11 + (alpha + alpha ) x 5 3 4 6 10 + (alpha + 1 + alpha + alpha + alpha ) x 6 2 5 9 + (alpha + alpha + alpha + 1) x 4 7 3 5 6 8 + (alpha + alpha + alpha + alpha + alpha + alpha ) x 7 7 + alpha x 4 5 2 6 3 7 6 + (1 + alpha + alpha + alpha + alpha + alpha + alpha ) x 4 7 2 3 5 5 + (alpha + alpha + alpha + alpha + alpha + alpha ) x 5 4 7 6 3 + (1 + alpha + alpha ) x + (alpha + alpha + alpha ) x 4 5 2 7 2 7 + (1 + alpha + alpha + alpha + alpha ) x + alpha x + 1 2 3 6 4 + alpha + alpha + alpha + alpha + alpha > 'PARAMETRES';'n'=n;'k'=n-degree(g,x);'d'=delta; PARAMETRES n = 255 k = 223 d = 33 Il serait bien sûr plus agréable d'obtenir les coefficients sous forme d'une seule puissance de alpha, ce qui est possible puisque alpha est une racine primitive. Cela nécessite néammoins encore un peu de travail. Commençons par extraire tous les coefficients dans une liste : > LC:=[seq(coeff(g,x,j),j=0..degree(g,x))]: Utilisons la librairie GF de Maple qui permet de calculer directement sur un corps fini : > readlib(GF): > F:=GF(p,m,poly): > a:=F[ConvertIn](alpha): > F[isPrimitiveElement](a); true Voici maintenant une procédure qui transformera LC en une liste de puissances de alpha : > puiss:=proc(LC) local LP,i,c,j,flag,aj; > LP:=array(1..nops(LC)); > for i from 1 to nops(LC) do; > c:=F[ConvertIn](op(i,LC)); > if c=0 or c=1 then LP[i]:=c > else j:=1; flag:=1; > while flag=1 do; > aj:=F[`^`](a,j); > if F[`-`](aj,c)=0 then LP[i]:=alpha^j; flag:=0; fi; > j:=j+1; > od; > fi; > od; > convert(LP,list); > end: > LC:=puiss(LC); 18 7 10 164 79 19 100 LC := [alpha , alpha , alpha , alpha , alpha , alpha , alpha , 7 198 55 125 124 229 18 alpha , alpha , alpha , alpha , alpha , alpha , alpha , 136 169 230 136 70 174 alpha , alpha , alpha , alpha , alpha , alpha , 97 214 182 79 189 220 25 alpha , alpha , alpha , alpha , alpha , alpha , alpha , 166 193 245 58 22 alpha , alpha , alpha , alpha , alpha , 1] Maintenant, réécrivons g(x) avec cette nouvelle forme pour les coefficients : > gg:=sort(sum(op(j+1,LC)*x^j,j=0..degree(g,x)),x):'g(x)'=gg; 32 22 31 58 30 245 29 193 28 g(x) = x + alpha x + alpha x + alpha x + alpha x 166 27 25 26 220 25 189 24 + alpha x + alpha x + alpha x + alpha x 79 23 182 22 214 21 97 20 + alpha x + alpha x + alpha x + alpha x 174 19 70 18 136 17 230 16 + alpha x + alpha x + alpha x + alpha x 169 15 136 14 18 13 229 12 + alpha x + alpha x + alpha x + alpha x 124 11 125 10 55 9 198 8 + alpha x + alpha x + alpha x + alpha x 7 7 100 6 19 5 79 4 + alpha x + alpha x + alpha x + alpha x 164 3 10 2 7 18 + alpha x + alpha x + alpha x + alpha Vérification de l'équivalence des deux formes : > simplify(g-gg,[poly=0]) mod p; 0 Exercice Trouver un générateur d'un code de Reed-Solomon de longueur 6 et de distance minimale 5 sur GF(7). Donner la forme générale des mots de ce code. Transformée de Mattson-Solomon La transformation de Mattson-Solomon est une transformation de Fourier discrète sur un corps fini. Elle est utilisée pour le décodage des codes de Reed-Solomon. Exemple explicatif > restart; Construisons d'abord F = GF(p) pour une valeur de p donnée, mettons p = 31. > p:=31; p := 31 > readlib(GF): > F:=GF(p,1): Le corps des racines n-ièmes de l'unité sur F est l'extension L = GF(p^r) , où r est le plus petit entier tel que n divise p^r-1, c-à-d r est l'ordre multiplicatif de p modulo n. Posons encore s tel que n*s=p^r-1. Valeur numérique choisie pour n : 13. NB : n et p doivent être premiers entre eux. > n:=13; n := 13 Calcul de r : > r:=numtheory[order](p,n); r := 4 Calcul de s : > s:=(p^r-1)/n; s := 71040 Construction du corps des racines de l'unité : > L:=GF(p,r): Procédure d'affichage des éléments de L, sous forme de polynômes en t : > aff:=proc(T); > subs(`?`=t,L[ConvertOut](T)); > end: L est construit à partir du polynôme irréductible suivant : > poly:=L[extension]():'poly'=aff(poly); 4 3 2 poly = t + 9 t + 9 t + 14 t + 11 Cherchons une racine primitive alpha de L (générateur du groupe multiplicatif cyclique de L) : > alpha:=L[PrimitiveElement]():'alpha'=aff(alpha); 3 alpha = 21 t + 9 t + 19 Une racine n-ième primitive de l'unité sur F est alors beta=alpha^s. > beta:=L[`^`](alpha,s):'beta'=aff(beta); 3 2 beta = 25 t + 14 t + 25 t + 27 Formons la liste des éléments du groupe cyclique G engendré par beta : > G:=[seq(L[`^`](beta,k),k=0..n-1)]:'G'=map(aff,G); 3 2 3 2 G = [1, 25 t + 14 t + 25 t + 27, 13 t + 21 t + 21 t + 5, 3 2 3 2 18 t + 15 t + 18 t + 1, 26 t + 25 t + 18, 3 2 3 2 24 t + 9 t + 3 t + 25, 29 t + 11 t + 19 t + 3, 3 2 3 2 25 t + 21 t + 28 t + 12, 17 t + 13 t + 8 t + 18, 3 2 3 2 13 t + 5 t + 15 t + 7, 4 t + 21 t + 2, 3 2 3 2 27 t + 5 t + 23 t + 17, 27 t + 26 t + 26 t + 19] Définition de la transformation de Mattson-Solomon : Soit : u(x,a)=sum(a[k]*x^k,k = 0 .. n-1) un polynôme de F[x]/( x^n-1). L'application qui lui associe le polynôme de L[x]/((x^n-1)) : v(x,b)=b[0]+sum(b[k]*x^(n-k),k = 1 .. n-1) , avec b[k]=u(beta^k,a), s'appelle la transformée de Mattson-Solomon. La transformation inverse s'effectue ainsi : a[k]=n^(-1)*v(beta^k,b). Procédure pour évaluer u : > u:=proc(x,a) local rep,j; > rep:=L[0]; > for j from 1 to n do; > rep:=L[`+`](rep,L[`*`](op(j,a),L[`^`](x,j-1))); > od; > rep; > end: Procédure pour évaluer v : > v:=proc(x,b) local rep,j; > rep:=op(1,b); > for j from 2 to n do; > rep:=L[`+`](rep,L[`*`](op(j,b),L[`^`](x,n-j+1))); > od; > rep; > end: Propriété de convolution : Soient u(x,a1) et u(x,a2) deux polynômes de F[x]/(x^n-1), v(x,b1) et v(x,b2) leurs transformées. Définissons le produit de convolution (produit d'Hadamard) des transformées de la façon suivante : v(x,b1) &* v(x,b2) = b1[0]*b2[0]+sum(b1[k]*b2[k]*x^(n-k),k=1..n-1). Alors la transformée du produit usuel (modulo x^n-1) de u(x,a1) par u(x,a2) est le produit de convolution de leurs transformées. EXEMPLE : Prenons a au hasard : > a:=[seq(F[random](),j=1..n)]; a := [16, 11, 7, 17, 3, 15, 2, 23, 25, 24, 10, 7, 17] Calculons b pour que v soit la transformée de u : > b:=[seq(u(op(j,G),a),j=1..n)]:'b'=map(aff,b); 3 2 3 2 b = [22, 6 t + 16 t + 14 t + 17, 5 t + 10 t + 23 t + 28, 3 2 3 15 t + 20 t + 29 t + 26, 6 t + 22 t + 8, 3 2 3 2 2 t + 10 t + 23 t + 30, 23 t + 29 t + 24 t + 25, 3 2 3 2 4 t + 18 t + 15 t + 26, 10 t + 4 t + 15 t, 3 2 3 2 29 t + 15 t + t + 17, 22 t + 18 t + 21 t + 18, 3 2 3 2 20 t + 14 t + 20 t + 24, 13 t + t + 10 t + 29] Définissons encore c par c[k]=(n)^(-1)*v(beta^k,b) : > c:=[seq(L[`*`](L[inverse](n mod p),v(op(j,G),b)),j=1..n)]; c := [16, 11, 7, 17, 3, 15, 2, 23, 25, 24, 10, 7, 17] Nous constatons que c=a, conformément à ce qui a été annoncé : > check:=[seq(L[`-`](op(j,c),op(j,a)),j=1..n)]; check := [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] Vérification de la propriété de convolution : Prenons a1 et a2 au hasard : > a1:=[seq(F[random](),j=1..n)];a2:=[seq(F[random](),j=1..n)]; a1 := [19, 26, 11, 7, 0, 25, 0, 15, 17, 30, 29, 22, 18] a2 := [9, 25, 23, 27, 17, 6, 30, 15, 27, 30, 12, 2, 7] Calculons b1 et b2 : > b1:=[seq(u(op(j,G),a1),j=1..n)]:'b1'=map(aff,b1); > b2:=[seq(u(op(j,G),a2),j=1..n)]:'b2'=map(aff,b2); 3 2 3 2 b1 = [2, 18 t + 8 t + 24 t + 26, 12 t + 22 t + 30 t + 11, 3 2 3 2 13 t + 19 t + 22 t + 25, 4 t + 9 t + 3 t + 4, 3 2 3 2 7 t + 10 t + 16 t + 28, 27 t + 8 t + 18 t + 5, 3 2 3 2 29 t + 16 t + 25 t + 27, 13 t + 3 t + 6 t + 1, 3 2 3 2 2 t + 29 t + 16 t + 20, 29 t + 30 t + 18 t + 25, 3 2 3 2 8 t + 22 t + 23 t + 2, 24 t + 10 t + 16 t + 9] 3 2 3 2 b2 = [13, 10 t + 21 t + 24 t + 21, 27 t + 17 t + 22 t, 3 2 3 2 13 t + 19 t + 25 t + 26, 16 t + 24 t + 3 t + 20, 3 2 3 2 10 t + 30 t + 12 t + 15, 15 t + 16 t + 30 t + 5, 3 2 3 2 27 t + 2 t + 10 t + 13, 28 t + 4 t + 5 t + 18, 3 2 3 2 4 t + 20 t + 19 t + 23, 26 t + 11 t + 21 t + 30, 3 2 3 2 27 t + 15 t + 25 t + 15, 14 t + 7 t + 21 t + 11] Effectuons le produit de convolution : > conv:=[seq(L[`*`](op(j,b1),op(j,b2)),j=1..n)]:'conv'=map(aff,conv); 3 2 3 2 conv = [26, 11 t + 24 t + 15, 9 t + 29 t + 21 t + 30, 3 2 3 2 30 t + 24 t + 22 t, 20 t + 12 t + 11 t, 3 2 3 2 28 t + 20 t + 10 t + 4, 21 t + 7 t + 9 t + 28, 3 2 3 2 4 t + 17 t + 3 t, 12 t + 6 t + 3 t + 11, 3 2 3 2 17 t + 26 t + 8 t + 20, 11 t + 29 t + 20 t + 5, 3 2 3 2 12 t + 11 t + 30 t + 9, 11 t + 12 t + 18 t + 12] Effectuons le produit usuel de u(x,a1) par u(x,a2) : > prod:=sort(simplify(sum(op(j,a1)*x^(j-1),j=1..n)*sum(op(j,a2)*x^(j-1),j=1..n),[x^n=1]) mod p,x); 12 11 10 9 8 7 6 prod := 29 x + 11 x + 23 x + 10 x + 16 x + 6 x + 23 x 5 4 3 2 + 27 x + 22 x + 12 x + 6 x + 29 x + 29 Déterminons la liste ordonnée A de ses coefficients : > A:=[seq(coeff(prod,x,j),j=0..n-1)]; A := [29, 29, 6, 12, 22, 27, 23, 6, 16, 10, 23, 11, 29] Calculons sa transformée sous forme d'une liste B : > B:=[seq(u(op(j,G),A),j=1..n)]:'B'=map(aff,B); 3 2 3 2 B = [26, 11 t + 24 t + 15, 9 t + 29 t + 21 t + 30, 3 2 3 2 30 t + 24 t + 22 t, 20 t + 12 t + 11 t, 3 2 3 2 28 t + 20 t + 10 t + 4, 21 t + 7 t + 9 t + 28, 3 2 3 2 4 t + 17 t + 3 t, 12 t + 6 t + 3 t + 11, 3 2 3 2 17 t + 26 t + 8 t + 20, 11 t + 29 t + 20 t + 5, 3 2 3 2 12 t + 11 t + 30 t + 9, 11 t + 12 t + 18 t + 12] Enfin vérifions que B = conv : > check:=[seq(L[`-`](op(j,B),op(j,conv)),j=1..n)]; check := [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] REMARQUE : La transformation de Mattson-Solomon est définie de manière générale sur F = GF(q), où q est une puissance d'un nombre premier p. J'ai choisi q = p dans un souci de simplification. Exercice Etudier la transformée de Fourier discrète sur le corps des complexes, définie ainsi : Soit omega:=exp(2*z*I*Pi/n) une racine n-ième primitive de l'unité sur le corps C des nombres complexes (avec pgcd(z, n) = 1). Soit u(x,a):=sum(a[k]*x^k,k=0..n-1) un polynôme de C[x]/(x^n-1). L'application qui lui associe le polynôme de C[x]/(x^n-1) : v(x,b):=sum(b[k]*x^k,k=0..n-1), avec b[k]:=u(omega^(-k),a), est la transformée dont il est ici question. Expliciter la transformée inverse et définir un produit de convolution de telle sorte que la transformée du produit usuel soit le produit de convolution des transformées. Références Odile Papini et Jacques Wolfmann : Algèbre discrète et codes correcteurs, Springer-Verlag 1995. Lekh R. Vermani : Elements of algebraic coding theory, Chapman & Hall 1996. 6. Codes d'Hadamard Matrice et codes d'Hadamard Une matrice d'Hadamard d'ordre n est une matrice carrée H, composée de 1 et de -1, telle que HH^t=nI, où H^t désigne la transposée de H et I la matrice identité d'ordre n. Pour n=2^m, il existe un procédé récursif simple de construction d'une matrice d'Hadamard d'ordre n, basé sur le fait que, si M est une matrice d'Hadamard, alors la matrice-blocs suivante aussi : MATRIX([[M, M], [M, -M]]) . A partir d'une matrice d'Hadamard H, on peut obtenir une nouvelle matrice H01 à coefficients dans {0, 1}, en opérant la traduction suivante : 1 est remplacé par 0 et -1 est remplacé par 1. H01 permet de construire 3 codes binaires intéressants : C1 := l'ensemble des colonnes de la sous-matrice obtenue de H01 en effaçant la première ligne; C2 := l'ensemble des mots de C1 et de leurs complémentaires (le complémentaire d'un mot binaire est obtenu en remplaçant les 1 par des 0 et les 0 par des 1); C3 := l'ensemble des colonnes de H01 et de leurs complémentaires. Ces trois codes, nommés codes d'Hadamard, sont généralement non linéaires. C1 a pour longueur n-1, pour taille n et pour distance minimale n/2. C2 a pour longueur n-1, pour taille 2n et pour distance minimale au moins n/2-1. C3 a pour longueur n, pour taille 2n et pour distance minimale n/2. Procédures Calcul d'une matrice d'Hadamard d'ordre 2^m : > restart; > with(linalg): Warning, new definition for norm Warning, new definition for trace > had:=proc(m) local M,i; > M:=matrix([[1,1],[1,-1]]); > for i from 1 to m-1 do; > M:=blockmatrix(2,2,M,M,M,-M); > od; > evalm(M); > end: Conversion d'une matrice d'Hadamard en matrice avec des 0 et des 1 : > hadconv:=proc(H); > evalm(map(x->(-1/2)*x+(1/2),H)); > end: Construction du code C1 : > hadC1:=proc(H01,m) local M,C1,i; > M:=delrows(H01,1..1); > C1:=array(1..2^m); > for i from 1 to 2^m do; > C1[i]:=convert(evalm(col(M,i)),list); > od; > convert(C1,set); > end: Construction du code C2 : > hadC2:=proc(C1,m) local C1c,i; > C1c:=array(1..2^m); > for i from 1 to 2^m do; > C1c[i]:=map(x->1-x,op(i,C1)); > od; > C1c:=convert(C1c,list); > {op(C1),op(C1c)}; > end: Construction du code C3 : > hadC3:=proc(H01,m) local C3,i,u,uc; > C3:=array(1..2^m); > for i from 1 to 2^m do; > u:=convert(evalm(col(H01,i)),list); > uc:=map(x->1-x,u); > C3[i]:=u,uc; > od; > convert(C3,set); > end: Exemple > m:=4; m := 4 > H:=had(m); H := [1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1] [1 , -1 , 1 , -1 , 1 , -1 , 1 , -1 , 1 , -1 , 1 , -1 , 1 , -1 , 1 , -1] [1 , 1 , -1 , -1 , 1 , 1 , -1 , -1 , 1 , 1 , -1 , -1 , 1 , 1 , -1 , -1] [1 , -1 , -1 , 1 , 1 , -1 , -1 , 1 , 1 , -1 , -1 , 1 , 1 , -1 , -1 , 1] [1 , 1 , 1 , 1 , -1 , -1 , -1 , -1 , 1 , 1 , 1 , 1 , -1 , -1 , -1 , -1] [1 , -1 , 1 , -1 , -1 , 1 , -1 , 1 , 1 , -1 , 1 , -1 , -1 , 1 , -1 , 1] [1 , 1 , -1 , -1 , -1 , -1 , 1 , 1 , 1 , 1 , -1 , -1 , -1 , -1 , 1 , 1] [1 , -1 , -1 , 1 , -1 , 1 , 1 , -1 , 1 , -1 , -1 , 1 , -1 , 1 , 1 , -1] [1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , -1 , -1 , -1 , -1 , -1 , -1 , -1 , -1] [1 , -1 , 1 , -1 , 1 , -1 , 1 , -1 , -1 , 1 , -1 , 1 , -1 , 1 , -1 , 1] [1 , 1 , -1 , -1 , 1 , 1 , -1 , -1 , -1 , -1 , 1 , 1 , -1 , -1 , 1 , 1] [1 , -1 , -1 , 1 , 1 , -1 , -1 , 1 , -1 , 1 , 1 , -1 , -1 , 1 , 1 , -1] [1 , 1 , 1 , 1 , -1 , -1 , -1 , -1 , -1 , -1 , -1 , -1 , 1 , 1 , 1 , 1] [1 , -1 , 1 , -1 , -1 , 1 , -1 , 1 , -1 , 1 , -1 , 1 , 1 , -1 , 1 , -1] [1 , 1 , -1 , -1 , -1 , -1 , 1 , 1 , -1 , -1 , 1 , 1 , 1 , 1 , -1 , -1] [1 , -1 , -1 , 1 , -1 , 1 , 1 , -1 , -1 , 1 , 1 , -1 , 1 , -1 , -1 , 1] > H01:=hadconv(H); H01 := [0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0] [0 , 1 , 0 , 1 , 0 , 1 , 0 , 1 , 0 , 1 , 0 , 1 , 0 , 1 , 0 , 1] [0 , 0 , 1 , 1 , 0 , 0 , 1 , 1 , 0 , 0 , 1 , 1 , 0 , 0 , 1 , 1] [0 , 1 , 1 , 0 , 0 , 1 , 1 , 0 , 0 , 1 , 1 , 0 , 0 , 1 , 1 , 0] [0 , 0 , 0 , 0 , 1 , 1 , 1 , 1 , 0 , 0 , 0 , 0 , 1 , 1 , 1 , 1] [0 , 1 , 0 , 1 , 1 , 0 , 1 , 0 , 0 , 1 , 0 , 1 , 1 , 0 , 1 , 0] [0 , 0 , 1 , 1 , 1 , 1 , 0 , 0 , 0 , 0 , 1 , 1 , 1 , 1 , 0 , 0] [0 , 1 , 1 , 0 , 1 , 0 , 0 , 1 , 0 , 1 , 1 , 0 , 1 , 0 , 0 , 1] [0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1] [0 , 1 , 0 , 1 , 0 , 1 , 0 , 1 , 1 , 0 , 1 , 0 , 1 , 0 , 1 , 0] [0 , 0 , 1 , 1 , 0 , 0 , 1 , 1 , 1 , 1 , 0 , 0 , 1 , 1 , 0 , 0] [0 , 1 , 1 , 0 , 0 , 1 , 1 , 0 , 1 , 0 , 0 , 1 , 1 , 0 , 0 , 1] [0 , 0 , 0 , 0 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 0 , 0 , 0 , 0] [0 , 1 , 0 , 1 , 1 , 0 , 1 , 0 , 1 , 0 , 1 , 0 , 0 , 1 , 0 , 1] [0 , 0 , 1 , 1 , 1 , 1 , 0 , 0 , 1 , 1 , 0 , 0 , 0 , 0 , 1 , 1] [0 , 1 , 1 , 0 , 1 , 0 , 0 , 1 , 1 , 0 , 0 , 1 , 0 , 1 , 1 , 0] > C1:=hadC1(H01,m); C1 := {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0], [1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0], [0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1], [1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0], [1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1], [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], [1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0], [1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1], [0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0], [1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1], [0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0], [1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0], [0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1], [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1], [0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1]} > C2:=hadC2(C1,m); C2 := {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0], [1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0], [0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1], [1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0], [1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1], [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], [1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0], [1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1], [0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0], [1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1], [0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0], [1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0], [0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1], [0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0], [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1], [0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0], [1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1], [0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1], [0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1], [0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0], [1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1], [0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1], [1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0], [0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1], [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1], [0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1], [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0], [1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0]} > C3:=hadC3(H01,m); C3 := {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1], [0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1], [0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0], [0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1], [0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0], [0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0], [0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1], [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1], [0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0], [0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0], [0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1], [0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0], [0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1], [0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1], [0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0], [1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1], [1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0], [1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1], [1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1], [1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0], [1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1], [1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1], [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1], [1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0], [1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0], [1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1], [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0], [1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0]} Exercice Soit q une puissance d'un nombre premier impair, telle que q = 3 (mod 4). Soit chi la fonction de GF(q) dans {-1, 0, 1} définie ainsi : chi(x) := 0 si x = 0, 1 si x est un carré et -1 si x n'est pas un carré. Définissons une matrice Q d'ordre q par Q[i,j]:=chi(x[i]-x[j]), où x[i] et x[j] parcourent GF(q). Considérons maintenant la matrice P d'ordre q + 1 dont la première ligne est formée d'un 0 suivi de q fois le nombre 1, dont la première colonne est formée d'un 0 suivi de q fois le nombre -1 et dont le bloc restant est formé de Q. Finalement, posons : H := P + (la matrice identité d'ordre q + 1). Dans ces conditions, on peut montrer que H est une matrice d'Hadamard. Effectuer cette construction pour q = 11. Références Lekh R. Vermani : Elements of algebraic coding theory, Chapman & Hall 1996. J.H. van Lint & R.M. Wilson A course in Combinatorics, Cambridge University Press 1992. 7. Codes et designs Designs, matrice d'incidence, code associé Soient E un ensemble ordonné et B un sous-ensemble ordonné de l'ensemble des parties de E. Nous noterons e[j] (j variant de 1 à n := card(E)) les éléments de E et B[i] (i variant de 1 à card(B)) les éléments de B. Le couple (E, B) s'appelle un design (ou configuration combinatoire). On nomme généralement points les éléments de E, et blocs les éléments de B. La matrice d'incidence M d'un design est une matrice de card(B) lignes et card(E) colonnes ainsi définie : m[i,j] := (1 si e[j] appartient à B[i] , 0 autrement). A travers la matrice d'incidence, un code linéaire C peut être associé à un design en prenant le sous-espace vectoriel de GF(q)^n engendré par les lignes de M. Inversément, à partir d'un code C de longueur n, on peut définir un design (E, B), avec E = {1, 2, ..., n} et B = l'ensemble des ensembles des numéros de position des lettres différentes de zéro à l'intérieur d'un mot de C. Les designs les plus utilisés sont les t-(n, b, lambda) designs, où les paramètres sont des entiers tels que t<=b, b<=n, le nombre de points est n, chaque bloc a pour cardinal b, enfin tout ensemble de t points est contenu dans exactement lambda blocs. La plupart du temps, on utilise des codes pour fabriquer des designs, mais il arrive aussi qu'on utilise des designs pour fabriquer des codes. Procédure pour calculer une matrice d'incidence > restart; > with(linalg): Warning, new definition for norm Warning, new definition for trace > Minc:=proc(E,B) local n,cB,M,i,j; > n:=nops(E);cB:=nops(B); > M:=matrix(cB,n); > for i from 1 to cB do; > for j from 1 to n do; > if member(op(j,E),op(i,B)) then M[i,j]:=1 else M[i,j]:=0 fi; > od; > od; > evalm(M); > end: Exemple > E:=[seq(j,j=1..6)]; E := [1, 2, 3, 4, 5, 6] > B:=[{1,2},{2,4,5},{2},{1,2,5},{2,5},{5},{1,2,4,5},{1,4,5}]; B := [{1, 2}, {2, 4, 5}, {2}, {1, 2, 5}, {2, 5}, {5}, {1, 2, 4, 5}, {1, 4, 5}] > M:=Minc(E,B); [1 1 0 0 0 0] [ ] [0 1 0 1 1 0] [ ] [0 1 0 0 0 0] [ ] [1 1 0 0 1 0] M := [ ] [0 1 0 0 1 0] [ ] [0 0 0 0 1 0] [ ] [1 1 0 1 1 0] [ ] [1 0 0 1 1 0] Plans projectifs Un plan projectif d'ordre q est un 2-(q^2+q+1,q+1,1) design. Il s'agit d'un objet important en combinatoire, notamment par ses liens avec les carrés latins mutuellement orthogonaux. Un théorème affirme que : Si q = 2 (mod 4), alors le code binaire associé au plan projectif d'ordre q a pour longueur q^2+q+1, pour dimension (1/2)(q^2+q+2) et pour distance minimale q+1. Malheureusement, on ne sait presque rien sur l'existence ou non de plans projectifs d'ordre q avec q = 2 (mod 4). L'état actuel des connaissances se résume à ceci : il existe un plan projectif d'ordre 2 (nommé plan de Fano), il n'existe pas de plan projectif d'ordre 6, ni d'ordre 10 (démontré à l'aide de l'ordinateur en 1989). Par contre, lorsque q est une puissance d'un nombre premier p, la construction d'un plan projectif d'ordre q est facile. Soient E1 := GF(q)^2 et E2 := {f[1], f[2], ..., f[q+1]} un ensemble quelconque possédant q + 1 éléments. On définit : E := E1 union E2. La définition de B est plus délicate. B va contenir q^2+q+1 blocs de q+1 points. L'un des blocs sera constitué de E2. Pour les autres, considérons a, b et c des éléments quelconques de GF(q), avec toutefois a et b non simultanément nuls. Formons l'équation ax + by = c et cherchons les couples (x, y) de E1 qui en sont solutions. Définissons B[a,b,c] := l'ensemble de ces couples (x, y) union {f[w]}, où w := q + 1 si a = 0 et w := b/a+1 si a<>0. B est alors la réunion de {E2} et de l'ensemble des ensembles B[a,b,c]. Exemple Nous choisirons q premier. > q:=3; q := 3 E0 := GF(q) : > E0:=[seq(j,j=0..q-1)]; E0 := [0, 1, 2] E1 := GF(q)^2 : > makeE1:=proc(q) local L,j1,j2,j3; > L:=matrix(q,q); > for j1 from 0 to q-1 do; > for j2 from 0 to q-1 do; > L[j1+1,j2+1]:=[j1,j2]; > od; > od; > [seq(op(convert(row(L,j3),list)),j3=1..q)]; > end: > E1:=makeE1(q); E1 := [[0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2], [2, 0], [2, 1], [2, 2]] > E2:=[seq(f[j],j=1..q+1)]; E2 := [f[1], f[2], f[3], f[4]] Réunion de E1 et E2 : > E:=[op(E1),op(E2)]; E := [[0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2], [2, 0], [2, 1], [2, 2], f[1], f[2], f[3], f[4]] Nous allons maintenant écrire une procédure pour calculer B : > makeB:=proc(q) local S1,a,b,c,S2,x,y,w; > S1:={{op(E2)}}; > for a from 0 to q-1 do; > for b from 0 to q-1 do; > for c from 0 to q-1 do; > if (a<>0 or b<>0) then > S2:={}; > for x from 0 to q-1 do; > for y from 0 to q-1 do; > if modp(a*x+b*y,q)=c then S2:=S2 union {[x,y]} fi; > od; > od; > if a=0 then w:=q+1 else w:=modp(b/a,q)+1 fi; > S2:=S2 union {f[w]}; > S1:=S1 union {S2}; > fi; > od; > od; > od; > convert(S1,list); > end: > B:=makeB(q); B := [{[0, 1], [1, 2], [2, 0], f[3]}, {f[1], f[2], f[3], f[4]}, {[0, 0], [1, 0], [2, 0], f[4]}, {[0, 1], [1, 1], [2, 1], f[4]}, {[0, 2], [1, 2], [2, 2], f[4]}, {[0, 0], [0, 1], [0, 2], f[1]}, {[0, 2], [1, 0], [2, 1], f[3]}, {[1, 0], [1, 1], [1, 2], f[1]}, {[2, 0], [2, 1], [2, 2], f[1]}, {[0, 0], [1, 1], [2, 2], f[3]}, {[0, 2], [1, 1], [2, 0], f[2]}, {[0, 1], [1, 0], [2, 2], f[2]}, {[0, 0], [1, 2], [2, 1], f[2]}] Matrice d'incidence : > M:=Minc(E,B); [0 ,1 ,0 ,0 ,0 ,1 ,1 ,0 ,0 ,0 ,0 ,1 ,0] [ ] [0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,1 ,1 ,1 ,1] [ ] [1 ,0 ,0 ,1 ,0 ,0 ,1 ,0 ,0 ,0 ,0 ,0 ,1] [ ] [0 ,1 ,0 ,0 ,1 ,0 ,0 ,1 ,0 ,0 ,0 ,0 ,1] [ ] [0 ,0 ,1 ,0 ,0 ,1 ,0 ,0 ,1 ,0 ,0 ,0 ,1] [ ] [1 ,1 ,1 ,0 ,0 ,0 ,0 ,0 ,0 ,1 ,0 ,0 ,0] [ ] M := [0 ,0 ,1 ,1 ,0 ,0 ,0 ,1 ,0 ,0 ,0 ,1 ,0] [ ] [0 ,0 ,0 ,1 ,1 ,1 ,0 ,0 ,0 ,1 ,0 ,0 ,0] [ ] [0 ,0 ,0 ,0 ,0 ,0 ,1 ,1 ,1 ,1 ,0 ,0 ,0] [ ] [1 ,0 ,0 ,0 ,1 ,0 ,0 ,0 ,1 ,0 ,0 ,1 ,0] [ ] [0 ,0 ,1 ,0 ,1 ,0 ,1 ,0 ,0 ,0 ,1 ,0 ,0] [ ] [0 ,1 ,0 ,1 ,0 ,0 ,0 ,0 ,1 ,0 ,1 ,0 ,0] [ ] [1 ,0 ,0 ,0 ,0 ,1 ,0 ,1 ,0 ,0 ,1 ,0 ,0] Exercice Soient q := 6s + 1 une puissance d'un nombre premier et alpha une racine primitive de GF(q). Définissons E := GF(q) et B := {B[i,xi] : 0<=i et i restart; > with(combinat): Warning, new definition for Chi > perm:=proc(n,sigma,c) local img,i; > img:=array(1..n); > for i from 1 to n do; > img[op(i,sigma)]:=op(i,c); > od; > convert(img,list); > end: > aut:=proc(n,C) local S,ensP,i,sigma,sC,j,c; > S:=permute(n); > ensP:={}; > for i from 1 to n! do; > sigma:=op(i,S);sC:={}; > for j from 1 to nops(C) do; > c:=op(j,C); > sC:=sC union {perm(n,sigma,c)}; > od; > if sC=C then ensP:=ensP union {sigma} fi; > od; > ensP:=convert(ensP,list); > end: Exemple > n:=5; n := 5 > C := {[0, 2, 0, 2, 2], [1, 0, 0, 0, 0], [0, 2, 0, 1, 0], [1, 2, 0, 2, 2], > [0, 1, 0, 0, 2], [1, 1, 0, 0, 2], [2, 1, 0, 1, 1], [2, 1, 0, 0, 2], > [2, 0, 0, 0, 0], [2, 2, 0, 2, 2], [2, 0, 0, 2, 1], [0, 0, 0, 1, 2], > [0, 0, 1, 2, 1], [2, 2, 2, 0, 1], [0, 0, 0, 0, 0], [1, 2, 0, 1, 0], > [2, 2, 0, 1, 0], [0, 2, 0, 0, 1], [1, 0, 0, 1, 2], [0, 1, 0, 2, 0], > [1, 2, 0, 0, 1], [2, 0, 1, 2, 1], [1, 0, 1, 1, 2], [1, 0, 1, 2, 1], > [0, 0, 1, 1, 2], [1, 1, 1, 2, 0], [2, 2, 0, 0, 1], [0, 0, 1, 0, 0], > [0, 1, 1, 1, 1], [2, 0, 1, 1, 2], [0, 1, 1, 2, 0], [1, 0, 1, 0, 0], > [0, 2, 1, 2, 2], [2, 1, 1, 1, 1], [2, 0, 1, 0, 0], [1, 1, 1, 1, 1], > [2, 1, 1, 2, 0], [0, 1, 1, 0, 2], [1, 1, 1, 0, 2], [1, 2, 1, 1, 0], > [2, 2, 1, 2, 2], [2, 1, 1, 0, 2], [1, 2, 1, 2, 2], [0, 2, 1, 1, 0], > [0, 2, 1, 0, 1], [1, 0, 2, 2, 1], [1, 2, 1, 0, 1], [0, 0, 2, 1, 2], > [0, 0, 2, 2, 1], [1, 1, 0, 2, 0], [2, 2, 1, 0, 1], [2, 2, 1, 1, 0], > [0, 1, 2, 2, 0], [0, 0, 2, 0, 0], [2, 0, 2, 1, 2], [1, 0, 2, 0, 0], > [2, 0, 2, 2, 1], [1, 0, 2, 1, 2], [2, 0, 2, 0, 0], [2, 1, 2, 1, 1], > [0, 1, 2, 0, 2], [1, 1, 2, 2, 0], [0, 0, 0, 2, 1], [1, 1, 2, 1, 1], > [1, 1, 2, 0, 2], [0, 1, 2, 1, 1], [2, 1, 0, 2, 0], [2, 1, 2, 0, 2], > [0, 2, 2, 2, 2], [1, 0, 0, 2, 1], [0, 2, 2, 1, 0], [0, 2, 2, 0, 1], > [2, 1, 2, 2, 0], [1, 2, 2, 0, 1], [1, 2, 2, 1, 0], [2, 0, 0, 1, 2], > [0, 1, 0, 1, 1], [1, 1, 0, 1, 1], [1, 2, 2, 2, 2], [2, 2, 2, 1, 0], > [2, 2, 2, 2, 2]}: > Aut:=aut(n,C); Aut := [[3, 2, 1, 4, 5], [3, 2, 1, 5, 4], [3, 4, 1, 2, 5], [3, 4, 1, 5, 2], [3, 5, 1, 2, 4], [3, 5, 1, 4, 2], [1, 4, 3, 2, 5], [1, 4, 3, 5, 2], [1, 5, 3, 2, 4], [1, 5, 3, 4, 2], [1, 2, 3, 4, 5], [1, 2, 3, 5, 4]] Convertissons les permutations en notation de cycles disjoints : > with(group): > Aut:=map(convert,Aut,'disjcyc'); Aut := [[[1, 3]], [[1, 3], [4, 5]], [[1, 3], [2, 4]], [[1, 3], [2, 4, 5]], [[1, 3], [2, 5, 4]], [[1, 3], [2, 5]], [[2, 4]], [[2, 4, 5]], [[2, 5, 4]], [[2, 5]], [], [[4, 5]]] Formons le groupe correspondant : > AutC:=permgroup(n,{op(Aut)}): On peut dès lors obtenir des informations sur ce groupe, par exemple : est-il abélien ? > isabelian(AutC); false quelle est l'orbite de 2 ? > orbit(AutC,2); {2, 4, 5} quel est le centraliseur de [[4, 5]] ? > centralizer(AutC,[[4, 5]]); permgroup(5, {[[1, 3]], [[4, 5]]}) etc. REMARQUE : Sauf pour de petites valeurs de n, la procédure aut a un temps de calcul qui devient vite déraisonnable. Exercice Déterminer le groupe d'automorphismes du code cyclique de longueur 7 sur GF(2) de générateur g(x) := x^3+x^2+1. Référence Lekh R. Vermani : Elements of algebraic coding theory, Chapman & Hall 1996. *************************************************************************