[PDF] Codes cycliques - DI ENS PDF TD4-sol.pdf

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

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

Exercice 1 {Traite en TD.

Exercice 2 {Ccode cyclique dansK=F5[X]=(X101) engendre par le polyn^omeg.

1. En eectuant la division euclidienne deX101 pargdansF5[X] on obtient :

101 =g(X)(X6+ 3X4+ 2X2+ 4):

2. Le codeCa dimensionk=ndeg(g) = 104 = 6 etM=jF5jk= 56mots.

3. La premiere colonne deGcorrespond aux coecients du polyn^omeg:g0= 1;g1=

0;g2= 3;g3= 0;g4= 1 suivis des zeros. Les colonnes suivantes sont obtenues en

applicant un decalage sur la colonne precedente. G=0 B

BBBBBBBBBBBBB@1 0 0 0 0 0

0 1 0 0 0 0

3 0 1 0 0 0

0 3 0 1 0 0

1 0 3 0 1 0

0 1 0 3 0 1

0 0 1 0 3 0

0 0 0 1 0 3

0 0 0 0 1 0

0 0 0 0 0 11

CCCCCCCCCCCCCA

4. Le polyn^ome de cont^olehdeCest tel queh(X)g(X) =X101. On l'a calcule

lors de la premiere questionh(X) =X6+ 3X4+ 2X2+ 4. La matrice de cont^oleHa sur la premiere ligne les coecients du polyn^omeh: h

6= 1;h5= 0;h4= 3;h3= 0;h2= 2;h1= 0;h0= 4, suivis des zeros. Ensuite on

decale ces valeurs sur les lignes suivantes : H=0 B

B@1 0 3 0 2 0 4 0 0 0

0 1 0 3 0 2 0 4 0 0

0 0 1 0 3 0 2 0 4 0

0 0 0 1 0 3 0 2 0 41

C CA

5. Toute colonne deHest non-nulle, doncd >1. Deux colonnes deHqui comportent

une seule valeur non-nulle sont distinctes et celles qui ont deux valeurs non-nulles sur les m^emes positions ne sont pas proportionnelles, doncd >2. On trouve la dependence : 2C1C5C7= 0, doncd= 3 et la capacite de correction estt= 1. www.di.ens.fr/nitulesc/2M120 1 anca.nitulescu@ens.fr

6. a) On calcule le syndromeS(

) =H =0 B B@4 0 1 01 C

CA= 2C5.

On a queS(

) =S(2"5) ou"5= (0 0 0 0 1 0 0 0 0 0)>.

La capacite de correction etantt= 1,S(

) =S(2"5) etwt(2"5)1, alorsc=

2"5est

l'unique element deCa distance1 de c= (1 1 1 1 1 1 1 1 1 1)>: b) On sait quec(X) =m(X)g(X), doncm(X) est le quotient de la division dec(X) par g(X) ou : c(X) =X9+X8+X7+X6+X5+X4+X3+X2+X2+X+ 1: Exercice 3 {Ccode lineaire surF7de matrice generatriceG=0 B

BBBBB@1 0

5 1 5 5 2 5 1 2 0 11 C

CCCCCA.

1. Le codeCa longueurn= 6, dimensionk= 2 etM=jF7jk= 72mots.

2. La matriceGnous permet de deduire le polyn^ome unitaireg(X)2F7[X]=(X61)

de degrenk= 4 tel que toutc(x)2Cxpeut s'ecrirec(x) =g(x)m(x) dans

K[x] =F7[X]=(X61).

On pourra ecrire une formule pourc(x) =g(x)m(x) en utilisant les notations ma- tricielles. (Voir Lemme 4.1.3 du cours pour la multiplication des polyn^omes dans l'anneau quotientK[x] en tenant compte quexn= 1.) | Le polyn^ome generateurg(X) =X4+ 2X3+ 5X2+ 5X+ 1. | Le polyn^ome de cont^oleh(X) = (X61)=g(X) =X2+ 5X+ 6. 3. H=0 B

B@1 5 6 0 0 0

0 1 5 6 0 0

0 0 1 5 6 0

0 0 0 1 5 61

C CA

4. On cherche les elementsdeF7pour

lesquelsF7=f1;;2:::5g.

On trouve2 f3;5g.

On verie queg(X) a comme racines

1; = 3; 2= 2; 3=1.

Cela nous donne une decomposition en

facteurs pourg:www.di.ens.fr/nitulesc/2M120 2 anca.nitulescu@ens.fr g(X) = (X1)(X)(X2)(X3): Le codeCest donc un codeReed-SolomonRS(7;2) de longueurq1 = 71 = 6, de dimensionk= 2 et de polyn^ome generateurgde degre deg(g) =q1k= 4. Des resultats du cours nous donnent les parametres du codeRS(7;2) : | La distance minimumd=qk= 5. | La capacite de correctiont= 2.

5. a) On calcule le syndromeS(

) =H

Exercice 4 {

1. D'apres la table on remarque que1 = 1, donc on cherche les racines deX7+ 1

parmi les elements deKqui satisfontX7=1 = 1. Dans le groupe multiplicatif K d'ordre 81 = 7, d'apres le theoreme de Lagrange on a8a2Ka7= 1.

Donc les 7 racines deX7+ 1 sont les elements deK.

2.g=X2+ (1 + 2)X+ 12 =X2+ 3X+ 2.

h= (X+ 3)(X+ 4)(X+ 5)(X+ 6)(X+ 7) =X2+ (3 + 4)X+ 34X2+ (5 + 6)X+ 56(X+ 7) =X2+ 7X+ 7X2+ 3X+ 3(X+ 7) =X4+ (3 + 7)X3+ (3 + 7 + 37)X2+ (37 + 37)X+ 37(X+ 7) = (X4+ 4X3+ 6X2+ 2)(X+ 7) =X5+ (4 + 7)X4+ (6 + 47)X3+ 67X2+ 2X+ 27 =X5+ 3X4+ 7X3+ 4X2+ 2X+ 5

3. Le codeCest donc un codeReed-SolomonRS(8;4) de parametres :

| La longueurn=q1 =jKj 1 = 7, | La dimensionk=ndeg(g) = 5, | La distance minimumd=qk= 3, | La capacite de correctiont= 1. La matrice generatrice associee au polyn^ome generateurg: G=0 B

BBBBBBB@2 0 0 0 0

3 2 0 0 0

1 3 2 0 0

0 1 3 2 0

0 0 1 3 2

0 0 0 1 3

0 0 0 0 11

CCCCCCCA

La matrice de cont^ole associee au polyn^ome de cont^oleh:

H=1 3 7 4 2 5 0

0 1 3 7 4 2 5

4.c=Gm.

www.di.ens.fr/nitulesc/2M120 3 anca.nitulescu@ens.frquotesdbs_dbs4.pdfusesText_7

[PDF] [PDF] Codes cycliques - DI ENS