Re: mat309 2019
Publié : mar. déc. 10, 2019 4:05 pm
10/12:
Preuve des 2 propositions.
Def code t-correcteur parfait.
Nombre d'elements dans une boule de rayon t.
2^n=2^k*(1+n+...+comb(n,t))
Cas t=1, codes de Hamming binaires
n=2^m-1, k=n-m
m=1 donne k=0 ne sert a rien
m=2 n=3, k=1 code de repetition
m=3, n=7, k=4 construction d'un code de Hamming systematique de distance 3, la matrice de controle contient l'ecriture en base 2 de tous les entiers de 1 a 7 en colonne. Le syndrome correspond a un entier, dont la colonne correspondante dans la matrice de controle donne le bit a corriger.
Le meme principe fonctionne pour m quelconque, exemple pour m=4, n=15, k=11.
Codes polynomiaux: poly de degre<k -> poly de degre<n, phi(P)=P*g pour g de degre m=n-k. Ce code n'est pas systematique, exemple g=x^3+x+1, k=4, n=7.
Code systematique phi(P)=P*x^m - reste(P*x^m,g), exemple ci-dessus, on retrouve un code de Hamming binaire.
J'ai evoque pour finir 2 prolongements hors programme
* corps fini faciles a manipuler sur ordinateur en base 2: reste de polynomes a coeff dans Z/2Z modulo un polynome irreductible (equivalent des restes d'entiers modulo un nombre premier)
* algorithme de Strassen pour mulitplier 2 matrices viewtopic.php?f=35&t=2432
Preuve des 2 propositions.
Def code t-correcteur parfait.
Nombre d'elements dans une boule de rayon t.
2^n=2^k*(1+n+...+comb(n,t))
Cas t=1, codes de Hamming binaires
n=2^m-1, k=n-m
m=1 donne k=0 ne sert a rien
m=2 n=3, k=1 code de repetition
m=3, n=7, k=4 construction d'un code de Hamming systematique de distance 3, la matrice de controle contient l'ecriture en base 2 de tous les entiers de 1 a 7 en colonne. Le syndrome correspond a un entier, dont la colonne correspondante dans la matrice de controle donne le bit a corriger.
Le meme principe fonctionne pour m quelconque, exemple pour m=4, n=15, k=11.
Codes polynomiaux: poly de degre<k -> poly de degre<n, phi(P)=P*g pour g de degre m=n-k. Ce code n'est pas systematique, exemple g=x^3+x+1, k=4, n=7.
Code systematique phi(P)=P*x^m - reste(P*x^m,g), exemple ci-dessus, on retrouve un code de Hamming binaire.
J'ai evoque pour finir 2 prolongements hors programme
* corps fini faciles a manipuler sur ordinateur en base 2: reste de polynomes a coeff dans Z/2Z modulo un polynome irreductible (equivalent des restes d'entiers modulo un nombre premier)
* algorithme de Strassen pour mulitplier 2 matrices viewtopic.php?f=35&t=2432