[PDF] [PDF] Feuille dexercices 3 Montrez que ce code permet

View - Download [PDF] Feuille dexercices 3

Previous PDF

Next PDF

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

C

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=0quotesdbs_dbs32.pdfusesText_38

[PDF] erreurs de syntaxe courantes

[PDF] cours de syntaxe pdf

[PDF] on modelise un oeil normal par un oeil reduit

[PDF] exercice corrigé doublet de lentilles

[PDF] pole emploi cv exemple

[PDF] modele cv pole emploi 2016

[PDF] dialogue simple en russe

[PDF] lecture russe

[PDF] conversation simple en russe

[PDF] russe débutant pdf

[PDF] comment reparer sa priere en islam

[PDF] comment faire prosternation distraction

[PDF] les 12 piliers de la priere

[PDF] soujoud sahw en arabe

[PDF] doute pendant la priere