[PDF] 1 Codes correcteurs derreurs - webusersimj-prgfr PDF 2M120-TD-2016-ch1-codes-correcteurs.pdf

Exercice 1 1 Soit C le code binaire : C = {00001100,00001111,01010101, 11011101} 1 et c7 = m2 + m3 + m4, et soit C le code linéaire binaire image de E 1

Previous PDF

Next PDF

[PDF] Codes linéaires

Semestre 2 Exercices et corrections pour le TD 3 2014–2015 Codes linéaires 1 Le code peut détecter un erreur, mais il ne peut pas corriger des erreurs 2

[PDF] Corrigés exercices codes correcteurs - LIRMM

Le code par parité impaire n'est pas linéaire, sa capacité de détection est de 1 bit , pour tout n Exercice 4: a: toute erreur sur un nombre impair de bit Pas de

[PDF] Feuille dexercices 3

Codes linéaires — On prend pour F le corps Fq ; le code C est dit linéaire si C est un sous-espace vectoriel de Fn q de dimension k Le poids ω(x) d'un élément

[PDF] 1 Codes correcteurs derreurs - webusersimj-prgfr

Exercice 1 1 Soit C le code binaire : C = {00001100,00001111,01010101, 11011101} 1 et c7 = m2 + m3 + m4, et soit C le code linéaire binaire image de E 1

[PDF] Feuille dexercices n Codes correcteurs - Benjamin Collas

ii) Quelle est la plus grande dimension d'un code linéaire binaire de longueur 8 qui corrige 2 erreurs? Construire un tel code Exercice 7 Soit C le code linéaire

[PDF] Exercices Codes Correcteurs - ENSIIE

On consid`ere le code binaire o`u on envoie 16 bits pour 9 bits significatifs de la mani`ere suivante : Montrer que ce code est linéaire, donnez sa matrice génératrice c'est `a dire la matrice dont On rappelle qu'il corrige une erreur

[PDF] Corrigé du TD 6

Ainsi le nouveau ensemble de mots de code ne forme plus un sous-espace vectoriel de GF8(2), et donc le code n'est plus un code linéaire EXERCICE 2 1 Les

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

Exercices 26 Chapitre 3 Les codes linéaires parfaits 35 3 1 Les codes de Hamming 36 3 4 façon que les erreurs puissent être détectées et corrigées 1 2

[PDF] Exercice 1 Exercice 2

200–2010 Algèbre et Arithmétique 3 Feuille n°7 : codes correcteurs d'erreurs Les premiers exercices de cette feuille sont tirés de la base WIMS Exercice 1 1

[PDF] Réseaux et Protocoles - Université de Strasbourg

Un code linéaire ajoute n − k bits de contrôle au aux bits codés Exercice 1 Pour qu'un code corrige k erreurs, la distance d du code doit vérifier d ≥ 2k + 1

1. Quelle est la longueur deC?

2. La distance minimaledeCest la plus petite des distances entre 2 elements deC. Quelle est

sa valeur? Exercice 1.2SoitEl'application d'encodage qui a un messagem= (m1;m2;m3;m4)2F42associe le mot de codec=E(m) = (m1;m2;m3;m4;c5;c6;c7)2F72ouc5=m1+m3+m4,c6=m1+m2+m3, etc7=m2+m3+m4, et soitCle code lineaire binaire image deE.

1. Donner la matrice generatriceGdeCassociee a l'application d'encodageE.

2. Soitm= (1010). Quel est le mot de code associe?

3. Soit

= (1111001). Est-ce un mot du code?

4. Determiner tous les elementsc2Ctels qued(c;

)1. Exercice 1.3SoitCle code binaire :C=f0000;1100;1010;0110;1001;0101;0011;1111g.

1. Quelle est la longueurndeC?

2. CombienCa-t-il d'elements? SiCetait un code lineaire surF2, quelle serait sa dimensionk?

Choisirkelementsm1;:::;mkdeC, lineairement independant, et considerer le code lineaire C

0engendre par (m1;:::;mk). Montrer queC0=C. Conclusion?

3. Quelle est la distance minimale deC? (Il est inutile de determiner toutes les distances entre

deux elements deC: sic12Cetc22Calorsd(c1;c2) est le nombre de coordonnees non nulles dec1c2qui est lui-m^eme un element deC.)

4. Montrer queG=0

B@1 0 0

0 1 0 0 0 1

1 1 11

CAest une matrice generatrice deC.

5. Montrer quec= (c1;c2;c3;c4) appartient aCsi et seulement sic1+c2+c3+c4= 0.

Exercice 1.4SoitG1la matrice a coecients dansF2:

G 1=0 B

BBBBB@1 0 1 1

0 0 1 1

1 1 0 0

1 1 0 1

1 1 1 1

0 1 1 11

CCCCCA

1. Quel est le rang deG1?

2. En deduire queG1est la matrice generatrice d'un code lineaire binaireCde longueurn= 6

et de dimensionk= 4.

3. Le codeCest-il systematique? Si oui, donner une matrice generatriceG2deCsous forme

standard.

4. Donner une matrice de contr^oleHdeC.

5. Y a-t-il dansCdes mots de poids 1? Des mots de poids 2? Quelle est la distance minimale

deC?

Laurent Koelblen1maj 11 sept., 2016

2M120

ELEMENTS D'ARITHMETIQUE LICENCE D'INFORMATIQUE UPMC 2015-2016Exercice 1.5SoitCle code lineaire binaire ayant pour matrice de contr^ole :

H=0 @1 0 1 1 0 0

1 1 0 0 1 0

0 1 0 0 0 11

1. Donner la longueurnet la dimensionkdeC.

2. Les mots

1= (111011) et

2= (100110) sont-ils des mots du codeC?

3. Donner une matrice generatriceGdeCainsi que l'application d'encodageE:Fk2!Fn2associee.

4. Pour chacun des mots

ide la question 2, donner, quand cela est possible, le messagemitel que i=E(mi). Exercice 1.6SoitCle code lineaire binaire de matrice de contr^ole : H=0 @1 1 0 0 1 0 1

0 0 1 1 1 0 1

1 0 1 0 0 1 11

1. Quelle est la longueurndeC? Quelle est la dimensionkdeC?

2. Soit

= 1111111. Est-ce un mot du code?

3. Y a-t-il dansCdes mots de poids 1? Des mots de poids 2? Des mots de poids 3? Quelle est

la distance minimaleddeC? Quelle est la capacite de correctiontdeC?

4. Le codeCest-il parfait?

5. Soitc2Cet

2F72tel qued(c;

)> t. Montrer qu'il existec02Ctel qued(c0; )t.

6. Sipest la probabilite d'erreur sur un bit (une coordonnee) lors d'une transmission, et si les

erreurs par bit sont independantes, exprimer en fonction depla probabilitePqu'un mot

2F72recu lors d'une transmission devienne, apres correction, un mot de codec0dierent du

mot de codecemis. Donner une valeur approchee dePpourp2110 ;1100 ;11000 Exercice 1.7Comme dans l'exercice 1.6, soitCle code lineaire binaire de matrice de contr^ole : H=0 @1 1 0 0 1 0 1

0 0 1 1 1 0 1

1 0 1 0 0 1 11

1. Reordonner les colonnes deHpour obtenir une matriceH0de la formeH0= (BjI3) ouB

une matrice 34 etI3la matrice identite 33. SoitC0le code equivalent aCde matrice de contr^oleH0. Donner une matriceG0generatrice deC0et en deduire une matriceGgeneratrice deC. On noteraEl'application d'encodage associee aG.

2. Les mots suivants sont recus :

1= 0101000,

2= 1110010,

3= 1100011,

4= 1011011,

5= 1101011,

6= 1000011. Montrer qu'il existe pour chacun des

iun motcidu codeCtel qued(ci; i)t. Determiner les mots de codeciainsi que les messagesmitels queci=E(mi).

Laurent Koelblen2maj 11 sept., 2016

quotesdbs_dbs3.pdfusesText_6

[PDF] [PDF] 1 Codes correcteurs derreurs - webusersimj-prgfr

1. Quelle est la longueur deC?

2. La distance minimaledeCest la plus petite des distances entre 2 elements deC. Quelle est

1. Donner la matrice generatriceGdeCassociee a l'application d'encodageE.

2. Soitm= (1010). Quel est le mot de code associe?

3. Soit

4. Determiner tous les elementsc2Ctels qued(c;

1. Quelle est la longueurndeC?

2. CombienCa-t-il d'elements? SiCetait un code lineaire surF2, quelle serait sa dimensionk?

0engendre par (m1;:::;mk). Montrer queC0=C. Conclusion?

3. Quelle est la distance minimale deC? (Il est inutile de determiner toutes les distances entre

4. Montrer queG=0

B@1 0 0

1 1 11

CAest une matrice generatrice deC.

5. Montrer quec= (c1;c2;c3;c4) appartient aCsi et seulement sic1+c2+c3+c4= 0.

Exercice 1.4SoitG1la matrice a coecients dansF2:

BBBBB@1 0 1 1

0 0 1 1

1 1 0 0

1 1 0 1

1 1 1 1

0 1 1 11

CCCCCA

1. Quel est le rang deG1?

2. En deduire queG1est la matrice generatrice d'un code lineaire binaireCde longueurn= 6

3. Le codeCest-il systematique? Si oui, donner une matrice generatriceG2deCsous forme

4. Donner une matrice de contr^oleHdeC.

5. Y a-t-il dansCdes mots de poids 1? Des mots de poids 2? Quelle est la distance minimale

Laurent Koelblen1maj 11 sept., 2016

1 1 0 0 1 0

0 1 0 0 0 11

1. Donner la longueurnet la dimensionkdeC.

2. Les mots

1= (111011) et

2= (100110) sont-ils des mots du codeC?

3. Donner une matrice generatriceGdeCainsi que l'application d'encodageE:Fk2!Fn2associee.

4. Pour chacun des mots

0 0 1 1 1 0 1

1 0 1 0 0 1 11

1. Quelle est la longueurndeC? Quelle est la dimensionkdeC?

2. Soit

3. Y a-t-il dansCdes mots de poids 1? Des mots de poids 2? Des mots de poids 3? Quelle est

4. Le codeCest-il parfait?

5. Soitc2Cet

2F72tel qued(c;

6. Sipest la probabilite d'erreur sur un bit (une coordonnee) lors d'une transmission, et si les

2F72recu lors d'une transmission devienne, apres correction, un mot de codec0dierent du

0 0 1 1 1 0 1

1 0 1 0 0 1 11

1. Reordonner les colonnes deHpour obtenir une matriceH0de la formeH0= (BjI3) ouB

2. Les mots suivants sont recus :

1= 0101000,

2= 1110010,

3= 1100011,

4= 1011011,

5= 1101011,

6= 1000011. Montrer qu'il existe pour chacun des

Laurent Koelblen2maj 11 sept., 2016