HAMMING Les codes correcteurs d'erreur sont une application de l'arithmétique d'usage quotidien lecteur de CD DVD Le problème est d'essayer de reconstituer un message original partir d'un message abimé

Publié par

HAMMING Les codes correcteurs d'erreur sont une application de l'arithmétique d'usage quotidien (lecteur de CD, DVD...). Le problème est d'essayer de reconstituer un message original à partir d'un message abimé. Pour cela on utilise des applications linéaires de ? ??? ? ??? Z 2 Z k dans ? ??? ? ??? Z 2 Z n où with(LinearAlgebra): Définition de l'application linéaire On définit l'application linéaire C de ? ??? ? ??? Z 2 Z 4 dans ? ??? ? ??? Z 2 Z 7 suivante : l'image du vecteur [ ], , ,b1 b2 b3 b4 vaut + + +b1 [ ], , , , , ,1 1 0 1 0 0 0 b2 [ ], , , , , ,0 1 1 0 1 0 0 b3 [ ], , , , , ,0 0 1 1 0 1 0 b4 [ ], , , , , ,0 0 0 1 1 0 1 Montrer qu'elle est injective.

  • bibliothèque moderne

  • application de l'arithmétique d'usage quotidien

  • définition de l'application linéaire

  • applications linéaires de ? ???


Publié le : mardi 19 juin 2012
Lecture(s) : 28
Source : math.unice.fr
Nombre de pages : 13
Voir plus Voir moins
HAMMING Les codes correcteurs d'erreur sont une application de l'arithmétique d'usage quotidien (lecteur de CD, DVD...). Le problème est d'essayer de reconstituer un message original à partir d'un message abimé. s de 2 ZZ k 2 ZZ n  où k 0 n  dont les points de Pour cela on utilise des applications linéaire dans l'image sont aussi éloignés que possible les uns des autres : si on reçoit un point qui n'est pas dans l'image il sera facile de reconstituer le point de l'image le plus proche qui est le point probablement correct. Avec la bibliothèque moderne LinearAlgebra > with(LinearAlgebra): Définition de l'application linéaire 4 éfinit l'application linéaire C de Z dans 2 ZZ 7  suivante : On d 2 Z  l'image du vecteur [ b 1 , b 2 , b 3 , b 4 ] vaut b 1 [1, 1, 0, 1, 0, 0, 0 ] # b 2 [0, 1, 1, 0, 1, 0, 0 ] # b 3 [0, 0, 1, 1, 0, 1, 0 ] # b 4 [0, 0, 0, 1, 1, 0, 1 ] Montrer qu'elle est injective. Solution On peut facilement résoudre le système linéaire à la main : on voit que les quatre première équations forment le système b 1 1 0, b 1 # b 2 1 0, b 2 # b 3 1 0, b 1 # b 3 # b 4 1 0 On peut aussi en profiter pour définir la matrice en utilisant la bibliothèque LinearAlgebra précédemment chargée : > V1:=Vector([1,1,0,1,0,0,0]);V2:=Vector([0,1,1,0,1,0,0]); 1 1 0 1 V1 := 0 0 0
0 1 1 V2 := 0 1 0 0 > V3:=Vector([0,0,1,1,0,1,0]);V4:=Vector([0,0,0,1,1,0,1]); 0 0 1 V3 := 1 0 1 0 0 0 0 V4 := 1 1 0 1 1 0 0 1 1 0 0 1 1 A := 1 0 1 0 1 0 0 0 1 0 0 0
> A:=<V1|V2|V3|V4>;
0 0 0 1 1 0 1
> Nullspace(A) mod 2; { } La base du noyau est vide, le noyau est réduit à {0}. L'application est bien injective. On appelle poids d'un élément son nombre de bits valant 1. Montrer que le poids d'un élément non nul de l'image de C  est au moins 3. (si quelqu'un a une idée autre que l'investigation systématique je suis preneur) On définit la distance de deux vecteurs comme le poids de leur différence. Vérifier que c'est bien une distance. Quelle est la distance minimale de deux points de l'image de C  ? Combien d'erreur(s) peut-on corriger ? Solution On peut taper à la main tous les éléments non nuls de 2 ZZ 4 , il n'y en a que 15. Essayons une solution plus amusante : on peut remarquer que ces vecteurs correspondent aux nombres binaires 0001 à 1111, soit 1 à 15 en décimal. D'où la petite procédure : > conv:=proc(n0) local j,l,n; l:=NULL;n:=n0; for j from 3 by -1 to 1 do  l:=l,iquo(n,2^j,'n') end do; <l,n> end proc: > conv(13);
1 1 0 1
Ca marche. Il faut régler un problème : le résultat de la multiplication par A n'est pas réduit modulo 2, un exemple > A.<1,1,1,1>;
1 2 2 3 2 1 1 > A.<1,1,1,1> mod 2; Error, invalid argument for modp or mods Car le résultat de multiply est un vecteur, il faut appliquer mod aux éléments du vecteur > map(modp,A.<1,1,1,1>,2); 1 0 0 1 0 1 1
D'où la boucle : > for i from 1 to 15 do  map(modp,A.conv(i),2) end do;
0 0 0 1 1 0 1
0
0
1
1
0
1
0 0
0
1
0
1
1
1 0
1
1
0
1
0
0 0
1
1
1
0
0
1
1
0
1
0
1
1
1
0 0
1
0
0
0
1
1 1
1
0
1
0
0
0 1
1
0
0
1
0
1
1
1
1
1
0
0
1
0 1
1
1
1
1
1
1 1
0
1
1
1
0
0 1
0
1
0
0
0
1
1
1 0 0 0 1 1 0 1 0 0 1 0 1 1 Si ça fatigue vos yeux de compter et puis ça peut toujours être utile de définir la procédure poids d'un vecteur > poids:=proc(v) local i; add(v[i],i=1..7) end proc: > for i from 1 to 15 do  poids(map(modp,A.conv(i),2)) end do; 3 3 4 3 4 4 3 3 4 4 7 4 3 3 4
Ce coup-ci on est convaincu.
d(V1,V2)=poids(V1-V2) est une distance : poids(V1-V2) équivaut V1-V2 est le vecteur nul à poids(V1-V2)=poids(V2-V1) car on est sur Z/2Z et V1-V2=V2-V1 poids(V1-V3) <= poids(V1-V2)+poids(V2-V3) : utiliser V1-V3=(V1-V2)+(V2-V3) et regarder d'où viennent les bits non nuls.
Si on a deux points distincts de l'image de C  leur distance est le poids de leur différence qui est un élément non nul de l'image donc au moins 3. On va donc pouvoir corriger une erreur : on saura sans hésitation quel est le point le plus proche de l'image.
Codage
Ecrire une procédure codage qui réalise l'application linéaire C  ci-dessus. Solution C'est évident : on l'a fait pour calculer tous les points de l'image. > Code:=proc(V) global A; map(modp,A.V,2) end proc: > Code(<1,1,1,1>);
1 0 0 1 0 1 1
Lecture ou Transmission Ecrire une procédure qui perturbe aléatoirement un bit du message codé. Solution Une procédure pour tirer un nombre aléatoire entre 1 et 7 : > tire7:=rand(1..7): > tire7();tire7();tire7(); 7 4
5 > Perturbe:=proc(V) local i; i:=tire7(); V[i]:=V[i]+1 mod 2; V end proc: > Perturbe(<1, 0, 0, 1, 0, 1, 1>); 1 0 0 0 0 1 1
Nous voilà prêts à attaquer le décodage.
Décodage
Vérifier que des équations de l'image de notre application linéaire C  sont : c 1 # c 4 # c 6 # c 7 1 0 c 2 # c 4 # c 5 # c 6 1 0 c 3 # c 5 # c 6 # c 7 1 0 Solution On va tester si les 4 vecteurs V1, V2, V3 et V4 satisfont les trois équations : > TestEqn:=proc(V) [V[1]+V[4]+V[6]+V[7] mod 2,V[2]+V[4]+V[5]+V[6] mod 2,V[3]+V[5]+V[6]+V[7] mod 2] end proc: > TestEqn(V1);TestEqn(V2);TestEqn(V3);TestEqn(V4); [0, 0, 0 ] [0, 0, 0 ] [0, 0, 0 ] [0, 0, 0 ] Ils satisfont les 3 équations. On a vu au début que les 4 vecteurs V1, V2, V3 et V4 étaient linéairement indépendants. Ils engendrent donc un sous-espace vectoriel de dimension 4 de 2 ZZ 7  donc défini par trois équations indépendantes.
Nos trois système d'équations de l'image.
Montrer que si un point différe d'un bit d'un point de l'image de C  on peut, en calculant les valeurs des trois formes linéaires précédentes, déterminer de quel bit il s'agit et donc le corriger. Solution Si un point différe d'un bit d'un point de l'image de C  il s'écrit V+e où V est dans l'image et e est de poids 1. donc chaque forme linéaire f correspondant au premier membre d'une équation vaudra f(V+e)=f(V)+f(e)=f(e). Il faut donc voir que l'évaluation des trois formes sur les vecteurs e de poids 1 identifie le vecteur e. On va donc passer TestEqn sur les 7 vecteurs de poids 1. On adapte la procédure conv précédente qui ne fabrique que des vecteurs à 4 composantes. > conv7:=proc(n0) local j,l,n; l:=NULL;n:=n0; for j from 6 by -1 to 1 do  l:=l,iquo(n,2^j,'n') end do; <l,n> end proc: > conv7(2^5);
0 1 0 0 0 0 0 > for i from 0 to 6 do TestEqn(conv7(2^i)) end do; [1, 0, 1 ] [1, 1, 1 ] [0, 1, 1 ] [1, 1, 0 ] [0, 0, 1 ] [0, 1, 0 ] [1, 0, 0 ] Ils sont tous différents donc caractéristiques de e mais pas très rangés. On définit une fonction par cas énumérés du genre f(5):=3, en fait on utilise la table de remember de la fonction. Comme conv7 respecte l'aspect visuel de l'écriture en base 2, 2^6 correspond à un 1 en première place, ..., 2^0 à un 1 en septième place. On aurait pu faire le choix inverse. Donc l
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.