Algèbre T1
5. On reprend l’exemple n = 3 4 − 1 de la question précédente et l’on se donne une
racine β d’un facteur irréductible de Φ n . Définir β par une commande RootOf,
puis calculer Expand(product(x-beta^(3^j),j=0..3)) mod 3. Vérifier que
l’on obtient bien le polynôme minimal de β.
Écrire une procédure s := proc(i) calculant le cardinal de la classe cyclotomique de i. Calculer s(1) et s(2). En déduire g 2 =
j∈Σ 2
(x − β j ), calculé
comme un produit. Vérifier que β 2 est racine de Φ m , pour m l’ordre de 2 dans
Z/nZ. En déduire son polynôme minimal, en testant quel facteur irréductible
il annule, et comparer.
6. On se restreint pour simplifier aux codes BCH binaires primitifs : on prend
q = 2 et n = 2 m −1. La théorie des classes cyclotomiques est alors extrêmement
simple : elles sont représentées par les nombres impairs (justifier).
Écrire une procédure Generateur:=proc(m,delta) renvoyant g, calculé selon
l’algorithme explicité plus haut, et le polynôme minimal de la racine β choisie
au cours de la procédure. On prendra soin de ne calculer que les factorisations
des Φ k requises et de ne les calculer qu’une seule fois, afin d’optimiser le temps
de calcul. Tester sur des exemples de votre choix.
Codes correcteurs d’erreurs, codage et décodage des codes BCH
Le propos de la théorie des codes correcteurs d’erreurs est la détection et la
correction d’erreurs lors de la transmission d’un message dans un canal, qui est en
général bruité, donc source d’erreurs. En rajoutant une information supplémentaire au message M (opération de codage) avant de le transmettre (on transmet
donc le message codé m), on espère pouvoir reconstituer le message d’origine
(opération de décodage) à partir du message reçu m . Si les erreurs ne sont pas
trop nombreuses, le message décodé M est égal à M .
Par exemple, on peut répéter plusieurs fois le message M et décoder en prenant
les symboles qui apparaissent majoritairement. Une erreur de transmission se
produit avec une probabilité moindre qu’en transmettant simplement le message,
cependant le coût de la transmission se trouve accru, puisque la longueur du
message augmente. Le but est de construire des codes qui réduisent la probabilité
d’erreur, avec un coût raisonnable, et tels que l’on dispose d’algorithmes de codage
et surtout de décodage efficaces. Les bases de la théorie des codes ont été établies
par Shannon vers 1950. Les applications technologiques sont nombreuses dans
les télécommunications (minitel, TV par satellite, etc.). C’est également grâce à
ces technologies qu’il est possible de lire un CD avec une bonne qualité d’écoute,
même s’il est rayé.
392
5. On reprend l’exemple n = 3 4 − 1 de la question précédente et l’on se donne une
racine β d’un facteur irréductible de Φ n . Définir β par une commande RootOf,
puis calculer Expand(product(x-beta^(3^j),j=0..3)) mod 3. Vérifier que
l’on obtient bien le polynôme minimal de β.
Écrire une procédure s := proc(i) calculant le cardinal de la classe cyclotomique de i. Calculer s(1) et s(2). En déduire g 2 =
j∈Σ 2
(x − β j ), calculé
comme un produit. Vérifier que β 2 est racine de Φ m , pour m l’ordre de 2 dans
Z/nZ. En déduire son polynôme minimal, en testant quel facteur irréductible
il annule, et comparer.
6. On se restreint pour simplifier aux codes BCH binaires primitifs : on prend
q = 2 et n = 2 m −1. La théorie des classes cyclotomiques est alors extrêmement
simple : elles sont représentées par les nombres impairs (justifier).
Écrire une procédure Generateur:=proc(m,delta) renvoyant g, calculé selon
l’algorithme explicité plus haut, et le polynôme minimal de la racine β choisie
au cours de la procédure. On prendra soin de ne calculer que les factorisations
des Φ k requises et de ne les calculer qu’une seule fois, afin d’optimiser le temps
de calcul. Tester sur des exemples de votre choix.
Codes correcteurs d’erreurs, codage et décodage des codes BCH
Le propos de la théorie des codes correcteurs d’erreurs est la détection et la
correction d’erreurs lors de la transmission d’un message dans un canal, qui est en
général bruité, donc source d’erreurs. En rajoutant une information supplémentaire au message M (opération de codage) avant de le transmettre (on transmet
donc le message codé m), on espère pouvoir reconstituer le message d’origine
(opération de décodage) à partir du message reçu m . Si les erreurs ne sont pas
trop nombreuses, le message décodé M est égal à M .
Par exemple, on peut répéter plusieurs fois le message M et décoder en prenant
les symboles qui apparaissent majoritairement. Une erreur de transmission se
produit avec une probabilité moindre qu’en transmettant simplement le message,
cependant le coût de la transmission se trouve accru, puisque la longueur du
message augmente. Le but est de construire des codes qui réduisent la probabilité
d’erreur, avec un coût raisonnable, et tels que l’on dispose d’algorithmes de codage
et surtout de décodage efficaces. Les bases de la théorie des codes ont été établies
par Shannon vers 1950. Les applications technologiques sont nombreuses dans
les télécommunications (minitel, TV par satellite, etc.). C’est également grâce à
ces technologies qu’il est possible de lire un CD avec une bonne qualité d’écoute,
même s’il est rayé.
392