{VERSION 2 3 "IBM INTEL NT" "2.3" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 }{CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 } {CSTYLE "2D Input" 2 19 "" 0 1 255 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "2 D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 256 " " 1 24 0 0 0 0 0 0 2 0 0 0 0 0 0 }{CSTYLE "" -1 257 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 259 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 260 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 261 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 262 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" 2 263 "" 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 }{CSTYLE "" -1 264 " " 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 265 "" 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 }{CSTYLE "" -1 266 "" 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 } {PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Text Output" -1 2 1 {CSTYLE "" -1 -1 "Courier" 1 10 0 0 255 1 0 0 0 0 0 1 3 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 1" 0 3 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 }1 0 0 0 8 4 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 2" 3 4 1 {CSTYLE "" -1 -1 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 } 0 0 0 -1 8 2 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 3" 4 5 1 {CSTYLE "" -1 -1 "" 1 12 0 0 0 0 1 0 0 0 0 0 0 0 0 }0 0 0 -1 0 0 0 0 0 0 0 0 -1 0 }{PSTYLE "Warning" 2 7 1 {CSTYLE "" -1 -1 "" 0 1 0 0 255 1 0 0 0 0 0 0 1 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Maple Output" 0 11 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 11 12 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Title" 0 18 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 1 0 0 0 0 0 0 }3 0 0 -1 12 12 0 0 0 0 0 0 19 0 }} {SECT 0 {PARA 18 "" 0 "" {TEXT 256 27 "Codes correcteurs d'erreurs" }} {PARA 0 "" 0 "" {TEXT -1 70 "N'oubliez pas de charger en m\351moire la bibloth\350que d'alg\350bre lin\351aire." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "with(linalg):" }}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 16 "Codes de Hamming" }}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 35 "En dimens ion 7: le code de Hamming " }{XPPEDIT 18 0 "H[7];" "&%\"HG6#\"\"(" }} {PARA 0 "" 0 "" {TEXT -1 35 "Par d\351finition, le code de Hamming " } {XPPEDIT 18 0 "H[7]" "&%\"HG6#\"\"(" }{TEXT -1 60 " est un sous-espace vectoriel de dimension 4 de l'espace Z/2" }{XPPEDIT 18 0 "Z^7" "*$%\" ZG\"\"(" }{TEXT -1 56 " Pour simplifier le d\351codage, il est commode de d\351finir " }{XPPEDIT 18 0 "H[7]" "&%\"HG6#\"\"(" }{TEXT -1 248 " par un syst\350me de 3 \351quations ind\351pendantes. Par constructio n, on choisit les 3 \351quations de sorte que si l'on met leurs coeffi cients en ligne dans une matrice 3x7 V7 les 7 vecteurs colonnes de V7 \+ sont les \351critures en base 2 des nombres de 1 \340 7." }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 75 "Il faut commencer \+ par cr\351er cette matrice avec Maple.\nOn donne la fonction " }{TEXT 19 2 "b2" }{TEXT -1 33 " suivante transforme un nombre x<" }{XPPEDIT 18 0 "2^n" ")\"\"#%\"nG" }{TEXT -1 91 " en un vecteur de longueur n do nt les composantes donnent la d\351composition en base 2 de x. " }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 92 "b2:=proc(x,n)\nlocal r;\nr:= x mod 2;\nif n=1 then [r];\nelse \n[op(b2(iquo(x,2),n-1)),r]\nfi;\nend :" }}}{PARA 0 "" 0 "" {TEXT -1 50 "Par exemple, pour avoir la d\351com position de 6=4+2:" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "b2(6,3) ;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7%\"\"\"F$\"\"!" }}}{PARA 0 "" 0 "" {TEXT -1 1 "\n" }{TEXT 257 2 "1)" }{TEXT -1 111 " Cr\351ez une matr ice 3x7 dont les colonnes sont (dans l'ordre) les \351critures en base 2 des nombres entre 1 et 7.\n" }}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 8 " Solution" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "V7:=augment(seq( b2(i,3),i=1..7));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#V7G-%'MATRIXG6 #7%7)\"\"!F*F*\"\"\"F+F+F+7)F*F+F+F*F*F+F+7)F+F*F+F*F+F*F+" }}}{PARA 5 "" 0 "" {TEXT -1 1 "\n" }}}{PARA 0 "" 0 "" {TEXT -1 2 "\n\030" } {TEXT 258 2 "2)" }{TEXT -1 66 "V\351rifiez que les trois \351quations \+ sont effectivement ind\351pendantes." }}{PARA 7 "" 0 "" {TEXT 2 137 "A ttention: Pour demander \340 Maple de travailler sur le corps (Z/2Z), vous pouvez utiliser les fonctions suivantes (Noter les majuscules): " }}{PARA 7 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "?Gausselim" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "?Nullspace" }}}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 8 "Solution" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "Gaus selim(V7) mod 2;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'MATRIXG6#7%7)\" \"\"\"\"!F(F)F(F)F(7)F)F(F(F)F)F(F(7)F)F)F)F(F(F(F(" }}}{PARA 0 "" 0 " " {TEXT -1 45 "Le rang de la matrice \351chelonn\351e est bien 3. " }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 98 "Pour r \351duire un vecteur ou un matrice modulo 2, vous pouvez utiliser la f onction reduit suivante. " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "reduit:=proc(M)\nmap(modp,evalm(M),2)\nend:" }}}{PARA 0 "" 0 "" {TEXT -1 25 "\nPar d\351finition, le code " }{XPPEDIT 18 0 "H[7]" "&% \"HG6#\"\"(" }{TEXT -1 34 " est le noyau de votre matrice V7." }} {PARA 0 "" 0 "" {TEXT 259 3 "3) " }{TEXT -1 21 "Calculez une base de \+ " }{XPPEDIT 18 0 "H[7] " "&%\"HG6#\"\"(" }{TEXT -1 35 " et explicitez \+ les 16 mots du code " }{XPPEDIT 18 0 "H[7]" "&%\"HG6#\"\"(" }{TEXT -1 1 "." }}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 8 "Solution" }}{PARA 0 "" 0 " " {TEXT -1 55 "Une base du noyau s'obtient avec la fonction Nullspace. " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "K:=Nullspace(V7) mod 2; " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"KG<&-%'VECTORG6#7)\"\"\"F*\"\" !F*F+F+F*-F'6#7)F+F*F+F*F+F*F+-F'6#7)F*F+F+F*F*F+F+-F'6#7)F*F*F*F+F+F+ F+" }}}{PARA 0 "" 0 "" {TEXT -1 79 "On trouve 4 vecteurs, ce qui redon ne que les 3 \351quations \351taient ind\351pendantes." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 7 "Les 16=" }{XPPEDIT 18 0 "2^4" "*$\"\"#\"\"%" }{TEXT -1 115 " mots du code s'obtiennent en prenant toutes les combinaisons lin\351aires (dans Z/2Z) possibles en tre ces 4 vecteurs." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "G:=au gment(op(K));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"GG-%'MATRIXG6#7)7 &\"\"\"\"\"!F*F*7&F*F*F+F*7&F+F+F+F*7&F*F*F*F+7&F+F+F*F+7&F+F*F+F+7&F* F+F+F+" }}}{PARA 0 "" 0 "" {TEXT -1 106 "G est donc une matrice g\351n \351ratrice pour le code. En multipliant cette matrice par tous les ve cteurs de Z/2" }{XPPEDIT 18 0 "Z^4" "*$%\"ZG\"\"%" }{TEXT -1 76 " on o btient toutes les combinaisons lin\351aires possibles entre ces vecteu rs. " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "seq(evalm(G &*b2(i,4 )),i=0..15);" }}{PARA 12 "" 1 "" {XPPMATH 20 "62-%'VECTORG6#7)\"\"!F'F 'F'F'F'F'-F$6#7)\"\"\"F+F+F'F'F'F'-F$6#7)F+F'F'F+F+F'F'-F$6#7)\"\"#F+F +F+F+F'F'-F$6#7)F'F+F'F+F'F+F'-F$6#7)F+F2F+F+F'F+F'-F$6#7)F+F+F'F2F+F+ F'-F$6#7)F2F2F+F2F+F+F'-F$6#7)F+F+F'F+F'F'F+-F$6#7)F2F2F+F+F'F'F+-F$6# 7)F2F+F'F2F+F'F+-F$6#7)\"\"$F2F+F2F+F'F+-F$6#7)F+F2F'F2F'F+F+-F$6#7)F2 FKF+F2F'F+F+-F$6#7)F2F2F'FKF+F+F+-F$6#7)FKFKF+FKF+F+F+" }}}{PARA 0 "" 0 "" {TEXT -1 159 "Attention, il y a des 2 et des 3 car Maple fait en \+ fait le calcul sur les entiers. Il faut r\351duire modulo 2 le r\351su ltat. D'o\371 l'int\351r^et de la fonction reduit." }}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 33 "seq(reduit(G &*b2(i,4)),i=0..15);" }}{PARA 12 "" 1 "" {XPPMATH 20 "62-%'VECTORG6#7)\"\"!F'F'F'F'F'F'-F$6#7)\"\"\" F+F+F'F'F'F'-F$6#7)F+F'F'F+F+F'F'-F$6#7)F'F+F+F+F+F'F'-F$6#7)F'F+F'F+F 'F+F'-F$6#7)F+F'F+F+F'F+F'-F$6#7)F+F+F'F'F+F+F'-F$6#7)F'F'F+F'F+F+F'-F $6#7)F+F+F'F+F'F'F+-F$6#7)F'F'F+F+F'F'F+-F$6#7)F'F+F'F'F+F'F+-F$6#7)F+ F'F+F'F+F'F+-F$6#7)F+F'F'F'F'F+F+-F$6#7)F'F+F+F'F'F+F+-F$6#7)F'F'F'F+F +F+F+-F$6#7)F+F+F+F+F+F+F+" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 19 "Par d\351finition, le " }{TEXT 266 5 "poids" } {TEXT -1 85 " d'un mot (= un vecteur) est le nombre de composantes non nulles. Par exemple, le mot" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "v:=vector([0,1,0,1,0,0,1]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>% \"vG-%'VECTORG6#7)\"\"!\"\"\"F)F*F)F)F*" }}}{PARA 11 "" 1 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 16 "est de poids 3.\n" }{TEXT 261 2 "4 )" }{TEXT -1 22 " Ecrivez une fonction " }{TEXT 19 5 "poids" }{TEXT -1 55 " qui prend en argument un vecteur et calcule son poids." }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "?vectdim" }}}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 8 "Solution" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 102 "poids:=proc(v)\nlocal s,i;\ns:=0;\nfor i from 1 to vectdim(v) do \n if v[i]<>0 then s:=s+1;\nfi; od;\ns;\nend:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "poids(v);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\" $" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 20 "\n Par d\351finition, la " }{TEXT 263 8 "distance" }{TEXT -1 61 " d'un co de est le minimum des poids de tous les mots du code." }}{PARA 0 "" 0 "" {TEXT 260 4 "5) C" }{TEXT -1 28 "alculez la distance du code " } {XPPEDIT 18 0 "H[7]" "&%\"HG6#\"\"(" }{TEXT -1 25 ". En d\351duire que le code " }{XPPEDIT 18 0 "H[7]" "&%\"HG6#\"\"(" }{TEXT -1 39 " permet de corriger au plus une erreur." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "?min" }}}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 8 "Solution" }}{PARA 0 "" 0 "" {TEXT -1 66 "On calcule le minimum de la suite des poids des vecteurs non nuls." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "l:=se q(poids(reduit(G &*b2(i,4))),i=1..15);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"lG61\"\"$F&\"\"%F&F'F'F&F'F&F&F'F&F'F'\"\"(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "min(l);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"$" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 262 2 "6)" }{TEXT -1 25 " S i c est un mot du code " }{XPPEDIT 18 0 "H[7]" "&%\"HG6#\"\"(" }{TEXT -1 32 ", que vaut le produit matriciel " }{TEXT 19 7 "V7 &* c" }{TEXT -1 160 "?\nSi v est un mot du code qui a subi une erreur au cours de l a transmission, on peut l'\351crire v=c+e, o\371 e est un mot de poids 1. Que vaut le produit matriciel " }{TEXT 19 7 "V7 &* v" }{TEXT -1 1 "?" }}{PARA 0 "" 0 "" {TEXT -1 92 "En d\351duire un algorithme pour \+ d\351coder un mot re\347u ayant au plus une erreur et programmez le." }}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 8 "Solution" }}{PARA 0 "" 0 "" {TEXT -1 94 "Par d\351finition le code est le noyau de V7. Donc un vec teur c appartient au code ssi V7 &* c=0." }}{PARA 0 "" 0 "" {TEXT -1 187 "Un vecteur ayant eu une erreur s'\351crit v=c+e avec c dans le co de et e un vecteur de poids 1, c'est-\340-dire avec une seule coordon \351e non nulle. Donc le produit V7 &* v= V7 &*(c+e)= V7 &* e." }} {PARA 0 "" 0 "" {TEXT -1 314 "On peut retrouver e \340 partir du r\351 sultat V7 &* v comme suit. Puisque e est de poids 1, toutes ses coordo nn\351es sont nulles sauf la i\350me et le produit V7 &* v=V7&* e est \+ \351gal \340 la i\350me colonne de V7. Mais par construction la i\350m e colonne de V7 est l'\351criture de i en base 2 et il n'y aplus qu' \340 changer le i\350me bit." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 138 "decodeH7:=proc(m)\nlocal m1,b,n;\nm1:=copy(m);\nn:=reduit(V7 &* m );\nb:=n[1]*4+n[2]*2+n[3];\nif b<> 0 then \nm1[b]:=1-m1[b];\nfi;\neval m(m1);\nend:" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 22 "Testez votre fonction " } {TEXT 19 8 "decodeH7" }{TEXT -1 61 " gr\342ce \340 la fonction test su ivante. Si vous obtenez toujours " }{TEXT 20 4 "true" }{TEXT -1 28 " c 'est bon; si vous obtenez " }{TEXT 20 5 "false" }{TEXT -1 45 " c'est q ue votre fonction ne marche pas bien." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 317 "test:= proc()\nlocal c,e,K,modif,i,dec;\nK:=augment(op(Nullspace(V7)mod 2)); \nc:=map(modp,evalm(augment(op(Nullspace(V7)mod 2))&* randvector(4,ent ries=rand(0..1))),2);\ne:=rand(1..7)();\nmodif:=copy(c);\nmodif[e]:=1- modif[e];\ndec:=decodeH7(modif);\nfor i from 1 to 7 do\nif (dec[i]<>c[ i]) then RETURN(false) fi;\nod;\ntrue;\nend:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "test();" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%true G" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 264 2 "7) " }{TEXT -1 81 " En faisant des op\351rations sur les lignes de V7, mo ntrer que les 16 mots du code " }{XPPEDIT 18 0 "H[7]" "&%\"HG6#\"\"(" }{TEXT -1 100 " sont obtenus \340 partir des 16 mots de longueur 4 en \+ leur rajoutant 3 bits de parit\351 \340 des sous-mots." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "?addrow" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 25 "En d\351duire une \+ proc\351dure " }{TEXT 19 6 "encode" }{TEXT -1 55 " qui associe \340 to ut mot m de longueur 4 un mot du code " }{XPPEDIT 18 0 "H[7]" "&%\"HG6 #\"\"(" }{TEXT -1 18 " commen\347ant par m." }}{SECT 0 {PARA 5 "" 0 " " {TEXT -1 8 "Solution" }}{PARA 0 "" 0 "" {TEXT -1 110 "On fait des op \351rations \351l\351mentaires sur les lignes de V7, mais en commen \347ant par la derni\350re colonne \340 droite." }}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 28 "N:=reduit(addrow(V7,3,1,1));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG-%'MATRIXG6#7%7)\"\"\"\"\"!F*F*F+F*F+7)F+F*F*F +F+F*F*7)F*F+F*F+F*F+F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 " N:=reduit(addrow(N,3,2,1));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG- %'MATRIXG6#7%7)\"\"\"\"\"!F*F*F+F*F+7)F*F*F+F+F*F*F+7)F*F+F*F+F*F+F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "N:=reduit(addrow(N,2,1,1) );" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG-%'MATRIXG6#7%7)\"\"!\"\" \"F+F+F+F*F*7)F+F+F*F*F+F+F*7)F+F*F+F*F+F*F+" }}}{PARA 0 "" 0 "" {TEXT -1 131 "La matrice a l'air \351chelonn\351e (en partant de la dr oite), mais on continue pour \351liminer tous les coefficients hors de la diagonale." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "N:=reduit( addrow(N,1,2,1));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG-%'MATRIXG6 #7%7)\"\"!\"\"\"F+F+F+F*F*7)F+F*F+F+F*F+F*7)F+F*F+F*F+F*F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "N:=reduit(addrow(N,1,3,1));" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NG-%'MATRIXG6#7%7)\"\"!\"\"\"F+F+F +F*F*7)F+F*F+F+F*F+F*7)F+F+F*F+F*F*F+" }}}{PARA 0 "" 0 "" {TEXT -1 59 "Les \351quations du code sont donc \351quivalentes aux suivantes:" }} {PARA 0 "" 0 "" {XPPEDIT 18 0 "x[5]=x[2]+x[3]+x[4]" "/&%\"xG6#\"\"&,(& F$6#\"\"#\"\"\"&F$6#\"\"$F+&F$6#\"\"%F+" }{TEXT -1 1 "\n" }{XPPEDIT 18 0 "x[6]=x[1]+x[3]+x[4]" "/&%\"xG6#\"\"',(&F$6#\"\"\"\"\"\"&F$6#\"\" $F+&F$6#\"\"%F+" }}{PARA 0 "" 0 "" {XPPEDIT 18 0 "x[7]=x[1]+x[2]+x[4] " "/&%\"xG6#\"\"(,(&F$6#\"\"\"\"\"\"&F$6#\"\"#F+&F$6#\"\"%F+" }}{PARA 0 "" 0 "" {TEXT -1 73 "Ce qui d\351finit bien les 3 derni\350res lettr es en fonctions des 4 premi\350res." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 187 "encode:=proc(m)\nlocal v,i;\nv:=vector(7);\nfor i fr om 1 to 4 do\n v[i]:=m[i];\nod;\nv[5]:= modp(v[2]+v[3]+v[4],2);\nv[6]: = modp(v[1]+v[3]+v[4],2);\nv[7]:= modp(v[1]+v[2]+v[4],2);\nevalm(v); \+ \nend:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "encode([1,0,1,0]) ;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'VECTORG6#7)\"\"\"\"\"!F'F(F'F( F'" }}}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 21 "Variante cyclique de " } {XPPEDIT 18 0 "H[7]" "&%\"HG6#\"\"(" }}{PARA 0 "" 0 "" {TEXT -1 154 "L a matrice V7bis suivante a 7 colonnes qui sont les \351critures en bas e 2 des nombres de 1 \340 7 mais dans un ordre diff\351rent. Son noyau d\351finit donc un code " }{XPPEDIT 18 0 "H[7]" "&%\"HG6#\"\"(" } {TEXT -1 18 "bis qui est comme " }{XPPEDIT 18 0 "H[7]" "&%\"HG6#\"\"( " }{TEXT -1 22 " 1-correcteur parfait." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 85 "V7bis:=matrix([[1, 0, 0, 1, 0, 1, 1], [0, 1, 0, 1, 1, 1, 0], [0, 0, 1, 0, 1, 1, 1]]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>% &V7bisG-%'MATRIXG6#7%7)\"\"\"\"\"!F+F*F+F*F*7)F+F*F+F*F*F*F+7)F+F+F*F+ F*F*F*" }}}{PARA 0 "" 0 "" {TEXT -1 21 "V\351rifier que ce code " } {XPPEDIT 18 0 "H[7]" "&%\"HG6#\"\"(" }{TEXT -1 8 "bis est " }{TEXT 265 8 "cyclique" }{TEXT -1 44 ", c'est \340 dire qu'il contient un vec teur v=(" }{XPPEDIT 18 0 "v[1],v[2],v[3],v[4],v[5],v[6],v[7]" "6)&%\"v G6#\"\"\"&F$6#\"\"#&F$6#\"\"$&F$6#\"\"%&F$6#\"\"&&F$6#\"\"'&F$6#\"\"( " }{TEXT -1 56 ") si et seulement s'il contient son permut\351 circula ire (" }{XPPEDIT 18 0 "v[2],v[3],v[4],v[5],v[6],v[7],v[1]" "6)&%\"vG6# \"\"#&F$6#\"\"$&F$6#\"\"%&F$6#\"\"&&F$6#\"\"'&F$6#\"\"(&F$6#\"\"\"" } {TEXT -1 2 ")." }}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 8 "Solution" }} {PARA 0 "" 0 "" {TEXT -1 279 "On peut remarquer que la deuxi\350me lig ne de V7bis s'obtient en permutant circulairement la troisi\350me et q ue de m\352me la troisi\350me s'obtient en permutant circulairement la premi\350re. Ceci sugg\350re l'\351nonc\351. \nPour v\351rifier compl \350tement l'\351nonc\351, il faut montrer que l'espace vectoriel " } {XPPEDIT 18 0 "H[7]" "&%\"HG6#\"\"(" }{TEXT -1 113 "bis est \351gal au sous-espace vectoriel E de Z/2Z^7 dont les \351quations sont les perm ut\351es circulaires de celles de " }{XPPEDIT 18 0 "H[7]" "&%\"HG6#\" \"(" }{TEXT -1 56 "bis, c'es-\340-dire du noyau de la matrice V7ter su ivante: " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "C:=col(V7bis,1); " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"CG-%'VECTORG6#7%\"\"\"\"\"!F* " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "M:=delcols(V7bis,1..1); " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"MG-%'MATRIXG6#7%7(\"\"!F*\"\" \"F*F+F+7(F+F*F+F+F+F*7(F*F+F*F+F+F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "V7ter:=augment(M,C);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&V7terG-%'MATRIXG6#7%7)\"\"!F*\"\"\"F*F+F+F+7)F+F*F+F+F+F*F*7)F*F +F*F+F+F+F*" }}}{PARA 0 "" 0 "" {TEXT -1 306 "Le noyau H7ter de cette \+ matrice est clairement toujours de dimension 4 (on a juste permut\351 \+ les colonnes et donc pas chang\351 le rang). Pour v\351rifier l'\351ga lit\351 de H7bis et H7ter, il suffit de v\351rifier une inclusion, ce \+ que l'on peut faire en calculant la r\351duction de Gauss de la juxtap os\351e de V7bis et V7ter." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "V:=stack(V7bis,V7ter);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"VG-% 'MATRIXG6#7(7)\"\"\"\"\"!F+F*F+F*F*7)F+F*F+F*F*F*F+7)F+F+F*F+F*F*F*F-7 )F*F+F*F*F*F+F+F," }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "Gausse lim(V) mod 2;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'MATRIXG6#7(7)\"\" \"\"\"!F)F(F)F(F(7)F)F(F)F(F(F(F)7)F)F)F(F)F(F(F(7)F)F)F)F)F)F)F)F,F, " }}}{PARA 0 "" 0 "" {TEXT -1 51 "Ouf, le rang est bien 3 d'o\371 l' \351galit\351 H7bis=H7ter." }}{PARA 0 "" 0 "" {TEXT -1 58 "Noter ici l a diff\351rence entre le calcul sur Z/2Z ou sur Q:" }}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 13 "gausselim(V);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'MATRIXG6#7(7)\"\"\"\"\"!F)F(F)F(F(7)F)F(F)F(F(F(F)7)F)F)F(F)F (F(F(7)F)F)F)F)F)!\"#F-7)F)F)F)F)F)F)F)F." }}}{PARA 0 "" 0 "" {TEXT -1 129 "Il y a une m\351thode plus conceptuelle de pr\351voir le r\351 sultat d\351montr\351. Les codes cycliques forment une classe importan te de codes." }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 42 "En dimension 8: le code de Hamming \351tendu " }{XPPEDIT 18 0 "H[8]" "&%\"HG6#\"\")" }}{PARA 0 "" 0 "" {TEXT -1 42 "Par d\351finition, le code de Hamming \+ \351tendu " }{XPPEDIT 18 0 "H[8] " "&%\"HG6#\"\")" }{TEXT -1 37 " est \+ le code obtenu \340 partir du code " }{XPPEDIT 18 0 "H[7]" "&%\"HG6#\" \"(" }{TEXT -1 36 " pr\351c\351dent en rajoutant aux mots de " } {XPPEDIT 18 0 "H[7]" "&%\"HG6#\"\"(" }{TEXT -1 18 " un bit de parit \351." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 69 " Ecrire une matrice V8 dont les lignes sont les \351quations d\351finis sant " }{XPPEDIT 18 0 "H[8]" "&%\"HG6#\"\")" }{TEXT -1 21 ". Donner un e base de " }{XPPEDIT 18 0 "H[8]" "&%\"HG6#\"\")" }{TEXT -1 75 " et ca lculez sa distance. \nCombien d'erreurs peut-on corriger avec ce code? " }}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 8 "Solution" }}{PARA 0 "" 0 "" {TEXT -1 54 "Le code H8 est d\351fini par une \351quation suppl\351men taire:" }}{PARA 0 "" 0 "" {XPPEDIT 18 0 "x[8]=x[1]+x[2]+x[3]+x[4]+x[5] +x[6]+x[7]" "/&%\"xG6#\"\"),0&F$6#\"\"\"\"\"\"&F$6#\"\"#F+&F$6#\"\"$F+ &F$6#\"\"%F+&F$6#\"\"&F+&F$6#\"\"'F+&F$6#\"\"(F+" }}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 15 "v:=vector(8,1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"vG-%'VECTORG6#7*\"\"\"F)F)F)F)F)F)F)" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 23 "M:=augment(V7,[0,0,0]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"MG-%'MATRIXG6#7%7*\"\"!F*F*\"\"\"F+F+F+F*7*F*F+F+F* F*F+F+F*7*F+F*F+F*F+F*F+F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "V8:=stack(M,v);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#V8G-%'MATRIX G6#7&7*\"\"!F*F*\"\"\"F+F+F+F*7*F*F+F+F*F*F+F+F*7*F+F*F+F*F+F*F+F*7*F+ F+F+F+F+F+F+F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "K8:=op(Nu llspace(V8) mod 2);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#K8G6&-%'VECT ORG6#7*\"\"\"F*F*\"\"!F+F+F+F*-F'6#7*F*F*F+F*F+F+F*F+-F'6#7*F*F+F*F*F+ F*F+F+-F'6#7*F+F*F*F*F*F+F+F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "G8:=augment(K8):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "s eq(poids(reduit(G8 &* b2(i,4))),i=1..15);" }}{PARA 11 "" 1 "" {XPPMATH 20 "61\"\"%F#F#F#F#F#F#F#F#F#F#F#F#F#\"\")" }}}{PARA 0 "" 0 " " {TEXT -1 104 "Le code \351tendu H[8] est donc de poids 4. Il permet \+ de corriger une erreur et peut d\351tecter deux erreurs." }}}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 36 "En dimens ion 15: le code de Hamming " }{XPPEDIT 18 0 "H[15]" "&%\"HG6#\"#:" }} {PARA 0 "" 0 "" {TEXT -1 29 "En mimant la construction de " }{XPPEDIT 18 0 "H[7]" "&%\"HG6#\"\"(" }{TEXT -1 21 ", construire un code " } {XPPEDIT 18 0 "H[15] " "&%\"HG6#\"#:" }{TEXT -1 67 " de dimension 11 e t de longueur 15 et qui est 1-correcteur parfait." }}{SECT 0 {PARA 5 " " 0 "" {TEXT -1 8 "Solution" }}{PARA 0 "" 0 "" {TEXT -1 8 "Le code " } {XPPEDIT 18 0 "H[15]" "&%\"HG6#\"#:" }{TEXT -1 158 " est de dimension \+ 11 et de longueur 15. Une matrice v\351rificatrice est donn\351e par u ne matrice 4x15 dont les colonnes sont tous les vecteurs non nuls de 2 /2Z^4:" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "V15:=augment(seq(b 2(i,4),i=1..15));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$V15G-%'MATRIXG 6#7&71\"\"!F*F*F*F*F*F*\"\"\"F+F+F+F+F+F+F+71F*F*F*F+F+F+F+F*F*F*F*F+F +F+F+71F*F+F+F*F*F+F+F*F*F+F+F*F*F+F+71F+F*F+F*F+F*F+F*F+F*F+F*F+F*F+ " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "K15:=Nullspace(V15) mod 2;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%$K15G<--%'VECTORG6#71\"\"!\" \"\"F*F*F*F*F*F+F*F+F*F*F*F*F*-F'6#71F*F+F*F+F*F+F*F*F*F*F*F*F*F*F*-F' 6#71F+F+F+F*F*F*F*F*F*F*F*F*F*F*F*-F'6#71F+F*F*F+F*F*F*F+F*F*F*F*F+F*F *-F'6#71F*F+F*F+F*F*F*F+F*F*F*F*F*F+F*-F'6#71F*F*F*F+F*F*F*F+F*F*F*F+F *F*F*-F'6#71F+F+F*F+F*F*F*F+F*F*F*F*F*F*F+-F'6#71F+F+F*F*F*F*F*F+F*F*F +F*F*F*F*-F'6#71F+F*F*F+F+F*F*F*F*F*F*F*F*F*F*-F'6#71F+F+F*F+F*F*F+F*F *F*F*F*F*F*F*-F'6#71F+F*F*F*F*F*F*F+F+F*F*F*F*F*F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "nops(K15);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#6" }}}{PARA 0 "" 0 "" {TEXT -1 139 "Les 4 \351quations sont bien ind\351pendantes. Reste \340 calculer la distance du code. On peut l e faire na\357vement en calculant le poids de tous (=" }{XPPEDIT 18 0 "2^11-1" ",&*$\"\"#\"#6\"\"\"\"\"\"!\"\"" }{TEXT -1 228 ") les vecteur s non nuls, mais on sent bien que si cette m\351thode va donner le r \351sultat ici, elle va rapidement atteindre ses limites en dimensions sup\351rieures. (On a donn\351 une m\351thode en cours pour montrer q ue la distance est >2." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "G1 5:=augment(op(K15)):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "min (seq(poids(reduit(G15 &* b2(i,11))),i=1..2^11-1));" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#\"\"$" }}}{PARA 0 "" 0 "" {TEXT -1 54 "On a le r\351s ultat, mais on commence \340 sentir le calcul!" }}}}{SECT 0 {PARA 4 " " 0 "" {TEXT -1 16 "Une variante de " }{XPPEDIT 18 0 "H[15];" "&%\"HG6 #\"#:" }{TEXT -1 24 " pour corriger 2 erreurs" }}{PARA 0 "" 0 "" {TEXT -1 52 "Voici comment on peut utiliser une variante du code " } {XPPEDIT 18 0 "H[15];" "&%\"HG6#\"#:" }{TEXT -1 232 " pour corriger 2 \+ erreurs.\nLes matrices V1 et V2 ci-dessous ont pour colonnes les \351c ritures en base 2 des nombres de 1 \340 15, mais dans un ordre diff \351rent. Soit C le code lin\351aire noyau de la matrice V obtenue en \+ superposant V1 et V2." }}{PARA 0 "" 0 "" {TEXT -1 44 "V\351rifier que \+ C permet de corriger 2 erreurs." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 201 "V1:=matrix([[1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1], [0 , 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0], [0, 0, 1, 0, 0, 1, 1, 0, \+ 1, 0, 1, 1, 1, 1, 0], [0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1]]); " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#V1G-%'MATRIXG6#7&71\"\"\"\"\"!F +F+F*F+F+F*F*F+F*F+F*F*F*71F+F*F+F+F*F*F+F*F+F*F*F*F*F+F+71F+F+F*F+F+F *F*F+F*F+F*F*F*F*F+71F+F+F+F*F+F+F*F*F+F*F+F*F*F*F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 201 "V2:=matrix([[1, 0, 0, 0, 1, 1, 0, 0, 0, \+ 1, 1, 0, 0, 0, 1], [0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1], [0, \+ 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1], [0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1]]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#V2G-%'MATR IXG6#7&71\"\"\"\"\"!F+F+F*F*F+F+F+F*F*F+F+F+F*71F+F+F+F*F*F+F+F+F*F*F+ F+F+F*F*71F+F+F*F+F*F+F+F*F+F*F+F+F*F+F*71F+F*F*F*F*F+F*F*F*F*F+F*F*F* F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "V:=(stack(V1,V2));" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"VG-%'MATRIXG6#7*71\"\"\"\"\"!F+F+ F*F+F+F*F*F+F*F+F*F*F*71F+F*F+F+F*F*F+F*F+F*F*F*F*F+F+71F+F+F*F+F+F*F* F+F*F+F*F*F*F*F+71F+F+F+F*F+F+F*F*F+F*F+F*F*F*F*71F*F+F+F+F*F*F+F+F+F* F*F+F+F+F*71F+F+F+F*F*F+F+F+F*F*F+F+F+F*F*71F+F+F*F+F*F+F+F*F+F*F+F+F* F+F*71F+F*F*F*F*F+F*F*F*F*F+F*F*F*F*" }}}{PARA 0 "" 0 "" {TEXT -1 104 "Programmez un algorithme na\357f de d\351codage (on peut faire plus r apide avec un peu plus de math\351matiques)." }}{SECT 0 {PARA 5 "" 0 " " {TEXT -1 8 "Solution" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "K: =Nullspace(V) mod 2;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"KG<)-%'VEC TORG6#71\"\"\"F*\"\"!F+F*F*F*F+F+F*F+F+F+F+F+-F'6#71F*F+F+F+F*F+F*F*F* F+F+F+F+F+F+-F'6#71F*F+F*F*F*F+F+F+F+F+F+F*F+F+F+-F'6#71F+F*F*F+F+F*F* F*F+F+F*F+F+F+F+-F'6#71F+F+F*F+F*F*F*F+F+F+F+F+F+F*F+-F'6#71F+F*F+F*F* F*F+F+F+F+F+F+F*F+F+-F'6#71F+F+F+F*F+F*F*F*F+F+F+F+F+F+F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "nops(K);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "G:= augment(op(K)):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 49 "min(seq( poids(reduit(G &* b2(i,7))),i=1..2^7-1));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"&" }}}{PARA 0 "" 0 "" {TEXT -1 640 "Le code est de \+ poids 5: il peut donc corriger deux erreurs.\nSi l'on re\347oit un mot v qui a au plus 2 erreurs, un algorithme de d\351codage na\357f consi ste \340 parcourir l'ensemble des 2^7 mots du code et pour chacun d'en tre eux de calculer sa distance \340 v. On s'arr\352te d\350s que l'on a trouv\351 un mot du code \340 distance moins que 2.\n\nUn d\351coda ge un peu meilleur, bien que toujours tr\350s na\357f, consiste \340 c alculer V &*m. On compare tout d'abord avec les colonnes de V : si c'e st l'une d'elles, c'est qu'il y a eu une erreur \340 l'indice de cette colonne. Sinon, on continue et l'on compare avec le produit de V avec tous les vecteurs possibles de poids 2." }}{PARA 0 "" 0 "" {TEXT -1 89 "Il est commode pour le code de d\351finir une fonction qui teste l '\351galit\351 de deux vecteurs." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 170 "egal:=proc(v1,v2)\nlocal i,d;\nd:=vectdim(v1);\nif d<>vectdim (v2) then RETURN(false);\n else\n for i from 1 to d do\nif v1[i]<>v2[i ] then \nRETURN(false);\nfi;\nod;\nfi;\ntrue;\nend:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "v:=vector(4,1);w:=vector(4,1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"vG-%'VECTORG6#7&\"\"\"F)F)F)" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"wG-%'VECTORG6#7&\"\"\"F)F)F)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "evalb(v=w); egal(v,w);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%&falseG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%t rueG" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 112 "On introduit \351galemen t pour nos tests une fonction p2(i,j) qui cr\351e un vecteur de poids \+ 2 (aux indices i et j). " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 72 "p2:=proc(i,j)\nlocal v;\nv:=vector(15,0);\nv[i]:=1;\nv[j]:=1;\nevalm( v);\nend:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 365 "decode:=proc( m)\nlocal m1,s,i,j;\nm1:=copy(evalm(m));\ns:=reduit(V&*m);\nif egal(s, vector(8,0)) then RETURN(evalm(m1)) fi;\nfor i from 1 to 15 do\n if e gal(s,col(V,i)) then \nm1[i]:=1-m1[i]; RETURN(evalm(m1));\nfi;\nod; \n for i from 1 to 14 do\n for j from i+1 to 15 do\nif egal(s,reduit(V&*p 2(i,j))) then \nm1[i]:=1-m1[i]; m1[j]:=1-m1[j];\nRETURN(evalm(m1));\nf i;\nod; \nod;\n end:" }}}{PARA 0 "" 0 "" {TEXT -1 49 "Quelques tests. \+ On tire un mot du code au hasard." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "c:=reduit(G &* b2(rand(1..2^7-1)(),7));" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#>%\"cG-%'VECTORG6#71\"\"\"F)\"\"!F)F*F)F)F)F)F*F *F*F)F*F*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 13 "Pas d'erreur:" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "decode(c);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'VECTORG6#71\"\"\"F'\"\"!F'F(F'F'F'F'F(F(F(F'F(F( " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 11 "Une erreur:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "e:=vector(15,0): e[rand(1..15)()]:=1:deco de(reduit(c+e));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'VECTORG6#71\"\" \"F'\"\"!F'F(F'F'F'F'F(F(F(F'F(F(" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 13 "Deux erreurs:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "e:=p2( rand(1..15)(),rand(1..15)()):decode(reduit(c+e));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'VECTORG6#71\"\"\"F'\"\"!F'F(F'F'F'F'F(F(F(F'F(F(" }} }{PARA 0 "" 0 "" {TEXT -1 0 "" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 21 "Codes tir\351s au hasard" }}{PARA 0 "" 0 "" {TEXT -1 134 "Tirer qu elques codes au hasard (pour n=15 et k=11 par exemple) et calculez leu r distance.\nPeut-on esp\351rer tirer un bon code au hasard?" }}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 8 "Solution" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "V:=randmatrix(4,15,entries=rand(0..1));" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#>%\"VG-%'MATRIXG6#7&71\"\"!F*F*F*\"\"\"F*F+F+F+F +F*F*F*F+F*71F*F*F+F+F+F*F*F*F+F*F+F+F+F*F+71F+F+F+F+F+F+F+F+F+F+F+F*F *F*F+71F*F*F+F*F*F+F*F+F+F+F*F*F*F+F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "G:=augment(op(Nullspace(V)mod 2));" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#>%\"GG-%'MATRIXG6#717-\"\"\"F*F*\"\"!F*F*F*F+F*F+F+7- F*F+F+F+F+F+F+F+F+F+F+7-F+F*F+F*F*F*F+F+F+F*F*7-F+F*F*F*F+F+F*F*F*F+F+ 7-F+F+F*F*F*F*F+F+F+F+F*7-F+F*F+F+F+F+F+F+F+F+F+7-F+F+F*F+F+F+F+F+F+F+ F+7-F+F+F+F+F+F*F+F+F+F+F+7-F+F+F+F*F+F+F+F+F+F+F+7-F+F+F+F+F*F+F+F+F+ F+F+7-F+F+F+F+F+F+F+F*F+F+F+7-F+F+F+F+F+F+F*F+F+F+F+7-F+F+F+F+F+F+F+F+ F*F+F+7-F+F+F+F+F+F+F+F+F+F+F*7-F+F+F+F+F+F+F+F+F+F*F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "coldim(G);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#6" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 60 "Les \351qu ations tir\351es au hasard sont ind\351pendantes; logique. " }}{PARA 0 "" 0 "" {TEXT -1 211 "Dans cet exemple, l'avant derni\350re colonne \+ est de poids 2, donc le poids du code est 1 ou 2 et il ne corrige pas \+ d'erreur. On s'aper\347oit ainsi qu'un code tir\351 au hasard a en g \351n\351ral une petite distance (1 ou 2)." }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 17 "Le code de Golay " } {XPPEDIT 18 0 "G[23]" "&%\"GG6#\"#B" }}{PARA 0 "" 0 "" {TEXT -1 335 "O n pr\351sente ici un autre code parfait, d\351couvert par le physicien suisse Marcel Golay en 1949. On peut montrer que c'est le seul code c orrecteur binaire parfait permettant de corriger au moins deux erreurs . Ce code a eu une grande importance dans un domaine plus abstrait des math\351matiques: la classification des groupes finis simples." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 17 "Le code d e Golay " }{XPPEDIT 18 0 "G[23]" "&%\"GG6#\"#B" }{TEXT -1 53 " et par \+ d\351finition donn\351 par les \351quations suivantes:" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 795 "V23:=matrix([[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 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, 1, 0, 0, 0, \+ 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0], [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1], [0, 0, 0, 0, 1, 0 , 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1], [0, 0, 0, 0, 0, \+ 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1], [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0], [0, 0, 0, 0, 0 , 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0], [0, 0, 0, 0, \+ 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1], [0, 0, 0, 0 , 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1]]);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%$V23G-%'MATRIXG6#7-79\"\"\"\"\"!F+F+ F+F+F+F+F+F+F+F*F*F*F*F*F+F+F*F+F+F*F+79F+F*F+F+F+F+F+F+F+F+F+F+F*F*F* F*F*F+F+F*F+F+F*79F+F+F*F+F+F+F+F+F+F+F+F*F*F+F+F+F*F*F*F+F*F*F+79F+F+ F+F*F+F+F+F+F+F+F+F+F*F*F+F+F+F*F*F*F+F*F*79F+F+F+F+F*F+F+F+F+F+F+F*F* F+F+F*F+F+F+F*F*F*F*79F+F+F+F+F+F*F+F+F+F+F+F*F+F+F*F*F*F+F*F+F*F+F*79 F+F+F+F+F+F+F*F+F+F+F+F*F+F*F*F+F*F*F*F*F+F+F+79F+F+F+F+F+F+F+F*F+F+F+ F+F*F+F*F*F+F*F*F*F*F+F+79F+F+F+F+F+F+F+F+F*F+F+F+F+F*F+F*F*F+F*F*F*F* F+79F+F+F+F+F+F+F+F+F+F*F+F+F+F+F*F+F*F*F+F*F*F*F*79F+F+F+F+F+F+F+F+F+ F+F*F*F*F*F*F+F+F*F+F+F*F+F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 30 "Calculer la dimension du code \+ " }{XPPEDIT 18 0 "G[23]" "&%\"GG6#\"#B" }{TEXT -1 93 " ainsi que sa di stance. Combien d'erreurs peut-il corriger?\nV\351rifier que ce code e st parfait." }}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 8 "Solution" }}{PARA 0 "" 0 "" {TEXT -1 137 "Vu la forme de la matrice, les \351quations so nt clairement ind\351pendantes (V23 commence par un bloc identit\351). Le code est donc de dimension" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "coldim(V23)-rowdim(V23);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#7 " }}}{PARA 0 "" 0 "" {TEXT -1 58 "Faute de mieux, on calcule encore sa distance \"\340 la main\"." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "G:=augment(op(Nullspace(V23) mod 2)):" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 49 "min(seq(poids(reduit(G&*b2(i,12))),i=1..2^12-1));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 262 "Le calcul est un pe u long, mais on s'en sort. Ce code est de distance 7: il peut donc cor riger 3 erreurs. Pour v\351rifier qu'il est parfait, il faut v\351rifi er que le nombre d'\351l\351ments dans les 2^11 boules de rayon 3 repr \351sentent exactement l'ensemble des 2^23 mots." }}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 44 "ifactor(1+23+binomial(23,2)+binomial(23,3));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*$-%!G6#\"\"#\"#6" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "2^23-2^12*(1+23+binomial(23,2)+binomial(2 3,3));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}}}}{MARK "2 0 0" 13 }{VIEWOPTS 1 1 0 3 2 1804 }