[PDF] Feuille dexercices 3 PDF td3.pdf

Codes linéaires cycliques — L'exemple précédent sugg`ere de rajouter une structure d'alg`ebre `a un code linéaire C ; on obtient ce que l'on appelle un code

Previous PDF

Next PDF

[PDF] Codes cycliques - DI ENS

Exercice 1 – Traité en TD Exercice 2 – C code cyclique dans K = F5[X]/(X10 − 1) engendré par le polynôme g 1 En effectuant la division euclidienne de X10

[PDF] 4 Codes cycliques - webusersimj-prgfr

4 Codes cycliques Exercice 4 1 Soit C le code linéaire sur F5 de matrice génératrice G = Soit C le code cyclique de longueur 10 sur F5, engendré par le polynôme g 2 Quelle est la de code c émis ? Combien de bits ont été corrigés ?

[PDF] Codes Correcteurs dErreurs Les codes cycliques - LIRMM

12 nov 2008 · Exercice Plan 1 Codes Cycliques Rappel sur les polynômes Définition - Code Cycliques - Polynôme générateur Codage et décodage avec

[PDF] Exercices Codes Correcteurs - ENSIIE

Exercice 2 On consid`ere le code binaire o`u on envoie 16 bits pour 9 bits significatifs de la mani`ere suivante : On rappelle qu'il corrige une erreur On consid`ere le code cyclique C engendré par P quelle est sa longueur ? Quelle est sa

[PDF] Feuille dexercices 3

Codes linéaires cycliques — L'exemple précédent sugg`ere de rajouter une structure d'alg`ebre `a un code linéaire C ; on obtient ce que l'on appelle un code

[PDF] Université Pierre & Marie Curie

Exercice 1 On considère Dire dans chaque cas si le code est linéaire ainsi que le nombre d'erreurs qu'il peut détecter et corriger Exercice 2 Montrer que si C est de longueur 17 et de dimension 7, il ne corrige pas plus d'une erreur 2 Montrer que le polynôme X5 + X4 + X + 1 engendre un code cyclique binaire de

[PDF] T D Codes correcteurs derreurs POLYTECH 4i`eme année Année

Feuille de T D 3 corrigée : Codes cycliques Exercice 1 : code cyclique I) Soit C un code cyclique de longueur 15 sur IF2 de polynôme générateur g(x) = x4 + x

[PDF] Codes de Hamming 2 Codes cycliques et Reed-Solomon - Moais

(a) Ici, on construit un code de Hamming qui corrige une erreur unique dans Les codes cycliques ont un double intérêt : d'une part [exercice 1], le codage et le

[PDF] Th´eorie des codes correcteurs derreurs I - Page Personnelle du Pr

Fonctions booléennes 51 4 9 Exercices 52 Chapitre 5 Codes cycliques 53 5 1 Définition façon que les erreurs puissent être détectées et corrigées 1 2

[PDF] TD Réseau Les codes correcteurs et les codes détecteurs Claude

Le code de Hamming (3) Exercice (Correction) 1 0 1 0 1 1 0 C ' 2 vaut 1+0+ 1+0=0 (bits d'indice 7, 6, 5 et 4) C ' 1 vaut 1+0+1+1=1 (bits d'indice 7, 6, 3 et

Feuille d'exercices 3

du forum (http ://cours-jussieu-nombres.monforum.com/cours-et-td-2009-vf7.html) les exercices que nous aurons

1. Corps ¯nis

Exercice 1.1

en question : (i) F

4'F2[X]=(X2+X+ 1);

(ii) F

8'F2[X]=(X3+X+ 1);

(iii) F F

2[X;Y]=(Y2+Y+ 1;X2+X+Y).

(iv) F

9'F3[X]=(X2+X¡1).

Exercice 1.2

Pour toutndivisantn0on ¯xe une injectionFpn½Fpn0. Montrez alors que¹Fp:=S n>1Fpn!est une cloture

Exercice 1.3

Exercice 1.4

(a) Montrer que sidjnalors siP2A(d;q)on aPqui diviseXqn¡X. (b) Montrer que siP2A(d;n)diviseXqn¡Xalorsddivisen. (c) X djndI(d;q) =qn; puis en appliquant la formule d'inversion de Moebius

I(n;q) =1

n X djn¹(n d )qd: (d)

Exercice 1.5

(1) X (2) F 5[X] (P(X)) est isomorphe au corps F

25et que

Pa deux racines dansF25.

(3) a®+bavecaetb dansF5. (4) F

Exercice 1.6

On considµere le polyn^omeQ(X) =X9¡X+ 1surF3. (a) Montrer que le polyn^omeQn'a pas de racines dansF3;F9. 1 2 (b)Montrer queF27'F3[X](X3¡X¡1). (c) Montrer que toute racine®2F27du polyn^omeX3¡X¡1est une racine du polyn^omeQ. (d) (e)

Factoriser le polyn^omeQsur le corpsF3.

Exercice 1.7

F pm? P

5µa coe±cients dansFp

F pm.

Exercice 1.8

premier et nun entier premier avecp. On poseq=pr. (1) l'application qui µa un sous-groupe

Hdegal(Fqn=Fq)associe le sous-corps de

F F q½K½Fqn. (2) l'image de F pen un produit de pour tout entier

Exercice 1.9

(Indication : montrer que pour tout nombre premier impair p, le polyn^omeX4+1a une racine dans le corps F p2. n-iµeme de Galois des corps ¯nis, que

Exercice 1.10

SoitP(X) =X4¡10X3+ 21X2¡10X+ 11

(a) (b)

Exercice 1.11

mod 3. On note (i)

Montrer quePn'a pas de racine rationnelle.

(ii)

Montrer que

que

Q=¹©let¹R=X(X¡1).

(iii)

Exercice 1.12

(a) p´3 mod 4; (b)p´1 mod 4; (c) p´1 mod 2m; (d)p´5 mod 6; (e) p´5 mod 8; (f)p´1 mod 6; (g) p´ ¡1 mod 12; (h)p´ ¡1 mod 10. Indication : on cherchera µa faire des lemmes du genre : sipdivisea2+qb2etppremier avec b, alors¡qest un q.

Exercice 1.13

guration

Cquelconque de billes sur le plateau on introduit

C:=X (x;y)2Cj x+y2F4¯C:=X (x;y)2Cj x¡y2F4 3 e e e e e ee e e e e e ee e e e e e ee e e e e e ee e ee e e s s R ss ss s s e e ee e ee e e e e e ee e e e e e ee e e e e e ee e ee e e s s s s oµu e e e e e ee e e e e e ee e e e e e ee e e e e e ee e ee e e x 6 y s s R e e e e e ee e e e e e ee e e e e e ee e e e e e ee e ee e e x 6 y s (1)

Montrer que(®;¯)est un invariant du jeu.

(2) sauf un seul disons (x0;y0). (3)

Partant de la con¯guration suivante, montrer qu'il est impossible d'arriver µa une con¯guration oµu il n'y

aurait qu'une seule bille sur le plateau.

Exercice 1.14

2. Codes correcteurs

des erreurs que l'on supposera pas trop nombreuses (sinon il faut changer de mode de transmission). Il s'agit alors

son message; citons l'exemple un peu b^ete suivant. Exempleson prend pour alphabetF2. Supposons que A veuille transmettre l'un des 4 messages suivant :

0001 il sait qu'il y

a eu une erreur de transmission. Cependant m^eme en supposant qu'il n'y a qu'une seule erreur il ne sait pas si

00 ou 01; il peut alors demander µa A de lui renvoyer le message. Une solution moins co^uteuse

4 g g gt t t g g gt t tg g g g g g gt t t t tg g g g g g gt t t t tg g g g g g gt t t t tg g gt t tg g gt t t x6 y mais on sent bien qu'on peut faire plus brilliant.

2.1. Mise en place. |

On ¯xe un alphabet ¯niFde cardinalq(rapidementFsera un corps ¯ni) de sorte que tous les messages µa transmettre constituent un sous-ensemble de F k. La phase d'encodage consiste ensuite µa choisir n > kpuis µa associer injectivement µa chaque informationI2Fkun message

M2Fn; le sous-ensemble obtenu

deFns'appellele codeCde longueurn. Le rapportk=nqui mesure la redondance s'appellele taux d'information

du code. On dit que le message xet sorte que si le message re»cu Rappartient au code alors le nombre d'erreurs est nul et sinon le message initialM comme une application

C. Pour que tout cela

fonctionne correctement, il y a un certain nombre de contraintes que nous allons essayer d'exposer. SoitCun code surF, on appelle distance minimum deCl'entier d= minfdH(x;y) :x6=y2Cg: m^eme s'il s'agit du mot de r· bd=2c: en e®et si on avait d ddeC. Pourdpair etr=d=2, il n'est pas non plus exclu qu'il y ait deux mots distincts deCµa distancerde t=bd¡1 2 c:

On dit alors que

Cest un codet-correcteur.

5 C. i=0(i n)(q¡1)i, le code

Cest parfait si et seulement si on a

jCj:tX i=0( i n(q¡1)i=qn:

Un code est bon si

deFnqde dimensionk.Le poids d

H(x;0). Ainsi on a

d= min06=x2C!(x).

Proposition 2.5

d·n¡k+ 1:

Preuve :Notons

de sorte qu'en notant de 1 vu que leur somme est plus petite que

1+1=n. On dit queCestun code MDS, en anglais Maximum Distance

Separable, si on ad=n¡k+ 1.

Hd'un codeCest une matrice telle quex2C,Hx= 0.

Proposition 2.7

C=f(u1;¢¢¢;uk)G: (u1;¢¢¢;uk)2Fkqg C ?s'annulant sur C. B

BBBBB@

.....0... f

1f2¢¢¢ ¢¢¢ ¢¢¢fkfk+1¢¢¢fn1

CCCCCA

et f telles que se lit directement sur les kpremiµeres colonnes et lignes, est inversible. En s'autorisant un algorithme pour construire

Hµa partir deG.

6 de contr^ole. Hx pour lesxtels que!(x)·tde sorte que lorsque l'on re»coit un message m

0, la correction µa apporter est²tel que

!(²)·tetH(²) =H(m0).

Proposition 2.10

colonnes de cun mot (x1;¢¢¢;xn) de poids ralors de la relation est identique.

2.11|Code de Hamming de longueur7:prenons l'ensemble des mots de sept chi®res binaires,q= 2,n= 7

etCle code ayant pour base e 0=0 B

BBBBBBB@

1 1 0 1 0 0 01 C

CCCCCCCA; e

1=0 B

BBBBBBB@

0 1 1 0 1 0 01 C

CCCCCCCA; e

2=0 B

BBBBBBB@

0 0 1 1 0 1 01 C

CCCCCCCA; e

3=0 B

BBBBBBB@

0 0 0 1 1 0 11 C

CCCCCCCA;

Pour transmettre un message

m= (m0;m1;m2;m3), on transmetx=m0e0+m1e1+m2e2+m3e3. Les paramµetres H=0

1 0 1 1 1 0 0

1 1 1 0 0 1 0

0 1 1 1 0 0 11

3 et queGtH= 0. En outre toutes les colonnes deHsont distinctes de sorte qu'on

obtient toutes les vecteurs non nuls de F x B B@x 1 x 2 xquotesdbs_dbs10.pdfusesText_16

[PDF] [PDF] Feuille dexercices 3

Feuille d'exercices 3

1. Corps ¯nis

Exercice 1.1

4'F2[X]=(X2+X+ 1);

8'F2[X]=(X3+X+ 1);

2[X;Y]=(Y2+Y+ 1;X2+X+Y).

9'F3[X]=(X2+X¡1).

Exercice 1.2

Exercice 1.3

Exercice 1.4

I(n;q) =1

Exercice 1.5

25et que

Pa deux racines dansF25.

Exercice 1.6

Factoriser le polyn^omeQsur le corpsF3.

Exercice 1.7

5µa coe±cients dansFp

Exercice 1.8

Hdegal(Fqn=Fq)associe le sous-corps de

Exercice 1.9

Exercice 1.10

SoitP(X) =X4¡10X3+ 21X2¡10X+ 11

Exercice 1.11

Montrer quePn'a pas de racine rationnelle.

Montrer que

Q=¹©let¹R=X(X¡1).

Exercice 1.12

Exercice 1.13

Cquelconque de billes sur le plateau on introduit

Montrer que(®;¯)est un invariant du jeu.

Exercice 1.14

2. Codes correcteurs

0001 il sait qu'il y

00 ou 01; il peut alors demander µa A de lui renvoyer le message. Une solution moins co^uteuse

2.1. Mise en place. |

M2Fn; le sous-ensemble obtenu

C. Pour que tout cela

On dit alors que

Cest un codet-correcteur.

Cest parfait si et seulement si on a

Un code est bon si

H(x;0). Ainsi on a

Proposition 2.5

Preuve :Notons

1+1=n. On dit queCestun code MDS, en anglais Maximum Distance

Separable, si on ad=n¡k+ 1.

Hd'un codeCest une matrice telle quex2C,Hx= 0.

Proposition 2.7

BBBBB@

1f2¢¢¢ ¢¢¢ ¢¢¢fkfk+1¢¢¢fn1

CCCCCA

Hµa partir deG.

0, la correction µa apporter est²tel que

Proposition 2.10

2.11|Code de Hamming de longueur7:prenons l'ensemble des mots de sept chi®res binaires,q= 2,n= 7

BBBBBBB@

CCCCCCCA; e

BBBBBBB@

CCCCCCCA; e

BBBBBBB@

CCCCCCCA; e

BBBBBBB@

CCCCCCCA;

Pour transmettre un message

1 0 1 1 1 0 0

1 1 1 0 0 1 0

0 1 1 1 0 0 11

3 et queGtH= 0. En outre toutes les colonnes deHsont distinctes de sorte qu'on