Université Pierre & Marie Curie 2005/06 L2 Mathématiques Module LM 220 Feuille

Université Pierre & Marie Curie 2005/06 L2 Mathématiques Module LM 220 Feuille d'exercices n◦3. Codes correcteurs d'erreurs Exercice 1.  On considère les codes binaires suivants C1 = {0000, 1100, 1010, 1001, 0110, 0101, 0011, 1111} ⊂(F2)4 (1) C2 = {10000, 01010, 00001} ⊂(F2)5 (2) C3 = {000000, 101010, 010101} ⊂(F2)6. (3) 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.  1. Construire un code binaire de 4 mots de longueur 3 et de distance minimum 2. 2. Montrer qu'un code binaire C de longueur 3 et de distance minimum 2 possède au plus 4 mots. Exercice 3.  Soit n un entier positif. Montrer qu'une condition nécessaire pour qu'il existe un code linéaire binaire parfait 1-correcteur de longueur n est que l'entier n soit de la forme n = 2r −1, où r est un entier positif. Exercice 4.  Soit C un code linéaire binaire. 1. Montrer que si C est de longueur 17 et de dimension 7, il ne corrige pas plus d'une erreur. 2. Montrer que si C est de longueur 10 et de distance minimum 3, alors #C ≤93. Exercice 5.  Soit C le code linéaire sur F3 de matrice génératrice G =  2 1 0 1 2 0 2 1 1 1  . 1. Montrer que C est systématique et en donner une matrice génératrice normalisée G′. 2. Encoder le message (12) avec G, puis avec G′. 3. Construire une matrice de contrôle de C et calculer sa distance minimale. Le code est-il MDS (Maximum Distance Separable) ? 4. On reçoit le message 11102 codé par G. Quel est le message d'origine ? Le mot 12121 est-il un mot de code ? Le décoder sachant qu'il a été encodé par G. Exercice 6.  Soit C le code linéaire sur F5 de matrice génératrice G =  3 4 1 0 0 3 4 1  . 1. Donner le nombre de mots de C. 2. Le code est-il systématique ? 3. Déterminer une matrice de contrôle de C. 4. Calculer la capacité de correction t de C. Le code est-il MDS ? 5. Donner la table de contrôle contenant tous les vecteurs erreurs possibles de poids ≤t. 6. Décoder quand c'est possible les mots 3001, 1101 et 2311. Exercice 7.  Soit C le code de Hamming binaire de longueur 7. 1. Déterminer une matrice génératrice normalisée de C à l'aide de la méthode du pivot de Gauss. 2. En déduire une matrice de contrôle de C. 3. Décoder quand c'est possible les mots 1111111, 1101011, 0110110 et 1111010. 2 LM 220 Exercice 8.  Soit C le code linéaire ternaire de matrice génératrice G =     1 0 0 2 2 1 2 0 1 1 0 0 0 0 1 1 2 0 0 1 1 2 0 1    . Montrer que C est systématique, en donner une matrice de contrôle. Quelle est sa distance minimale ? Exercice 9.  Soit C le code sur F5 de matrice génératrice G avec G =  1 2 3 4 0 4 1 1 1 1 4 0  ; G′ =  1 0 4 3 3 1 0 1 2 3 1 4  . 1. Montrer que G′ est une matrice normalisée génératrice du même code C. 2. En déduire une matrice de contrôle. 3. Quelle est la capacité de correction de C ? 4. Décoder les mots 432100 et 411141. Exercice 10.  Soit C le code binaire linéaire de matrice génératrice G =   1 1 0 1 1 0 1 1 0 0 0 1 0 1 1 1 0 0  . 1. Le code est-il systématique ? 2. Déterminer une matrice de contrôle et la capacité de correction de C. 3. Le code est-il MDS ? 4. Décoder si possible les mots 111110 et 111111. Exercice 11.  Soit C le code binaire linéaire de matrice génératrice G =   1 1 0 1 0 1 1 1 1 0 1 0 1 0 1 1 0 0  . 1. Montrer que ce code est systématique. Pourquoi ? 2. Déterminer une matrice de contrôle et la capacité de correction de C. 3. Décoder si possible le mot 110110. Exercice 12.  Soit p un nombre premier, on considère le code Cp sur Fp, de matrice génératrice G =     1 0 0 1 2 2 0 1 0 0 2 2 0 0 1 0 1 3 0 0 0 2 3 2    . 1. Quelles sont les longueur et dimension de Cp ? Montrer que d ≤3. 2. Pour p = 2, 3, 5, trouver des matrices de contrôle pour Cp et déterminer les distances minimales. 3. Pour p = 5, décoder le mot 111234. Feuille d'exercices n◦3. Codes correcteurs d'erreurs 3 Codes cycliques Exercice 13.  Montrer que le polynôme X5 + X4 + X + 1 engendre un code cyclique binaire de longueur n = 8. En donner une matrice génératrice et une matrice de contrôle. Exercice 14.  Combien existe-t-il de codes cycliques binaires de longueur 4 ? Donner pour chacun une matrice génératrice et une matrice de contrôle. Exercice 15.  Montrer que si un code est cyclique, son mot minimal e m = a0 a1 . . . ar−1 1 0 . . . 0 véri e a0 ̸= 0. Exercice 16.  Le code binaire de matrice génératrice G =   1 1 1 0 0 0 1 1 1 0 0 0 1 1 1   est-il cyclique ? Exercice 17.  Soit m un mot non nul de Fn q et soit Cm le sous-espace vectoriel de Fn q engendré par la famille {σi(m) | i = 0, 1, . . . , n −1}. 1. Montrer que (a) Cm est un code cyclique de longueur n. (b) Cm est le plus petit code cyclique de longueur n sur Fq contenant le mot m. (c) Le polynôme générateur du code Cm est le pgcd des polynômes Xn −1 et m(X). 2. Déterminer le polynôme générateur de Cm lorsque q = 3, n = 9 et m = 022011000. Exercice 18.  Soit C un code cyclique de longueur n sur Fq, et soit h son polynôme de contrôle. Montrer que pour tout mot m ∈Fn q , on a (m ∈C) si et seulement si le polynôme m(X)h(X) est divisible par le polynôme Xn −1. Exercice 19.  Code binaire de Hamming de longueur 2r −1. Montrer que le code binaire de Hamming de longueur 2r −1 dé ni en cours est un code cyclique parfait de dimension k = 2s −1 −s, de distance minimum d = 3 et de polynôme générateur g = s−1 Y i=0 (X −α2i) ∈F2[X]. Exercice 20.  Exemple d'un code de Reed-Solomon. Soit F8 = F2[X]/⟨X3 + X + 1⟩et soit α = X. 1. Montrer que α est un élément primitif de F8. 2. Écrire la table des logarithmes de base α. 3. Soient g ∈F8[X] le diviseur unitaire de (X7 −1) dé ni par g = (X −α)(X −α2). Montrer que g = X2 + α4X + α3. 4. Écrire une matrice génératrice du code (de Reed-Solomon) C de longueur 7 engendré par g. 5. Déterminer le polynôme de contrôle et une matrice de contrôle de C. 6. En déduire que C est MDS. 7. Corriger le mot reçu α3α2αα4αα41. 4 LM 220 Exercice 21.  Examen juin 2004 1. Montrer, sans eectuer de division euclidienne, que dans F3[X], le polynôme g = (X −1)5 divise le polynôme X9 −1. 2. Soit C le code cyclique de longueur 9 sur F3, engendré par le polynôme g. (a) Quelle est la dimension de C ? (b) Quel est le nombre de mots de C ? 3. Développer le polynôme g dans F3[X], en détaillant et justi ant les calculs. 4. Pourquoi la matrice G =     2 2 2 1 1 1 0 0 0 0 2 2 2 1 1 1 0 0 0 0 2 2 2 1 1 1 0 0 0 0 2 2 2 1 1 1     est-elle une matrice génératrice du code C ? 5. Montrer que C contient un mot de poids 3. 6. Montrer que le polynôme de contrôle de C est le polynôme h = X4 + 2X3 + 2X + 1. 7. Déterminer une matrice de contrôle de C. 8. Déterminer la distance minimum du code C et le nombre d'erreurs que C peut corriger. 9. Le mot m = 121102210 est reçu. (a) Sous l'hypothèse d'au plus une erreur, quel est le mot de code émis ? (b) Quel est le message envoyé, sachant qu'il est encodé par la matrice G ? Feuille d'exercices n◦3. Codes correcteurs uploads/S4/ exercices-communication-corriges 1 .pdf

Documents similaires

Lycée BILLES Classe : 6e Bilingual Lycee of Excellent in Sciences Année scolair 0 0

http://mathematice.fr Informatique en CPGE (2018-2019) Exercices : courbes para 0 0

Ex 1) Je mets le signe qui convient < , > ou = : (2 pts) Contrôle de maths N°: 0 0

Université Toulouse 1 Préparation au Diplôme Supérieur de Comptabilité et de Ge 0 0

TP #1 Langage Java / Corrigé Applications Réparties 2009-2010 Université Paris 0 0

Manuel technique, N° de publication 6193.074 1033 Diagnostics 6-1 6 Diagnostics 0 0

NOM et Prénom ………………………………………… Classe de Quatrième …… Contrat 3 Année 2006 2007 0 0

Exercice II p.39 : corrigé Socrate : « (A) D’abord, il est nécessaire que tu fa 0 0

Amérique du Nord mai 2019 EXERCICE 4 Candidats ayant suivi l’enseignement de sp 0 0

Cours Galilée Spécialité mathématiques première 2020 CONTRÔLE 10 Exercice 1 : D 0 0

• Détails
• Publié le Mar 30, 2021
• Catégorie Law / Droit
• Langue French
• Taille du fichier 0.1357MB