Exercices Codes Correcteurs - Lirmm

1. : Code de répétition On utilise un code de répétition. Les bits sont envoyés 5 fois avec chaque
fois une probabilité p d'être mal transmis.
1/ Dans un tel paquet de 5 bits (c.a.d. 5 répétitions du bit de signal)
a. Quelle est la probabilité que 0, 1, 2,..., ou 4 des ces 5 bits sont
changés lors de la transmission?
b. Quelle est la probabilité que l'erreur de transmission soit détectée ?
c. Quelle est la probabilité que l'erreur soit transmise sans être
détectée ?
2/ Coder le message suivant : 01110
3/ Décoder le message suivant : 00100111110001011001
4/ Quel est le taux de transmission (rendement) d'un tel code ?
Pour améliorer la fiabilité, on décide d'utiliser un code avec 9
répétitions.
5/ Quel est le taux de transmission d'un tel code ?
6/ Quelle est la probabilité de faire 5 erreurs ?
7/ Montrer que pour p=0,001, la probabilité de faire 6 erreurs est
beaucoup plus petite que celle de faire 5 erreurs (c'est pourquoi les
cas de faire 6, 7, 8, ou 9 erreurs ne jouent pas de rôle et peuvent être
négligés par rapport au cas de 5 erreurs).
8/ Pour p=0,001, évaluer la probabilité qu'une erreur soit transmise
sans être détectée ?
9/ Comparer les résultats des codes avec 5 et 9 répétitions. 2. : Code par répétition On considère un code correcteur d'erreur (n, k) pour lequel k = 2 et n est
un entier pair tel que n ? 6, et dont les mots-codes y sont obtenus à
partir des mots d'informations u = (u1, u2) en les répétant (n/2- 1) fois.
En d'autres termes, le mot-code obtenu à partir de u = (u1, u2) où (u1, u2)
appartient à {0,1}2 s'écrit y = (u1, u2, u1, u2, ...., u1, u2)
(?)
Par exemple, si n = 8, le mot-code obtenu à partir de (1, 0) est (1, 0, 1,
0, 1, 0, 1, 0).
1. Donnez une matrice génératrice G de ce code Cn,2 (où, pour rappel, n
est un entier pair supérieur ou égal à 6).
2. Donnez une matrice de contrôle H de ce code Cn,2
3. Quel est le nombre maximal q de bits erronés que ce code garantit de
pouvoir toujours détecter ?
4. On compare à présent ce code Cn,2 dont les mots-codes sont construits
par répétition du mot d'information, comme décrit par (?), avec un autre
code Cn,2 qui associe au mot d'information u = (u1, u2) le mot-code y0 =
(u1, u2,u1 ( u2,u1 (u2, ... ,u1 ( u2,u1 ( u2) (?). Par exemple, si n =
8, le mot-code obtenu à partir de (1, 0) est (1, 0, 1, 1, 1, 1, 1, 1).
Lequel de ces deux a les meilleures propriétés détectrices et
correctrices d'erreur ? Justifiez rigoureusement votre réponse.
5. Parmi tous les codes linéaires Cn,2 avec n ? 6 et n pair, peut-on
trouver un code qui offre une garantie de détection d'un plus grand
nombre q d'erreurs que le code Cn,2 obtenu par répétition du mot
d'information, et défini par (?) ? Si oui, donnez un exemple d'un tel
code (spécifiez une matrice génératrice pour une valeur paire de n ? 6
particulière), sinon, expliquez pourquoi le code défini par (?) est le
code Cn,2 offrant la meilleure garantie de détection d'erreur. 3. : Contrôle de parité a. Montrer qu'un code C3,2 obtenu par parité paire est linéaire tandis
qu'un code C3,2 obtenu par parité impaire ne l'est pas
b. Que peut-on dire d'un code de longueur quelconque n obtenu par parité
paire, par parité impaire ? 4. : Contrôle de parité a. Combien d'erreurs peuvent-elles être détectées grâce à un contrôle
simple de parité? Est-il possible de corriger ces erreurs ?
b. Coder les messages suivants à l'aide d'un bit de parité :
o 1101011001
o 100
o 11111000111001111
c. Quels sont les taux de transmission (rendement) des trois messages ci-
dessus ? 5. : Contrôle de parité a. Soit un code de parités croisées pour des mots d'information de longueur
r = KxL, que l'on, range dans un tableau à L lignes et K colonnes. En
considérant come mot de code le bloc d'information suivi des bits de
parité :
c = i1, i2, iLxK, k1,.., kL, kL+1,....,kL+K+1, montrer qu'il s'agit
d'un code linéaire systématique.
b. Pour K=L=2, donner la matrice génératrice du code. 6. : Matrice de contrôle et matrice génératrice Un code linéaire a pour matrice de contrôle [pic]
a. Préciser la longueur n des mots de code et la longueur k des mots
d'information.
b. Les messages suivants sont-ils des mots du code ?
o m1 = (1 1 1 0 1 1)
o m2 = (1 0 0 1 1 0)
c. Donner la matrice génératrice du code et le codage de chaque mot
d'information. 7. : Code systématique Soit le code linéaire C7,4 qui au vecteur d'information i = (i1,i2,i3,i4)
associe le mot de code c= (i1,i2,i3,i4,c5,c6,c7) avec c5 = i1+i3+i4, c6 =
i1+i2+i3, et c7 = i2+i3+i4.
a. Donner la matrice génératrice et la matrice de contrôle de ce code
b. Soit i = (1 0 1 0), quel est le mot de code associé ?
c. Soit le message m = (1 1 1 1 0 0 1). Est-il un mot du code ? 8. : Code systématique On considère un code en bloc linéaire (6,3), de matrice génératrice G.
[pic]
1. Un code sous forme systématique est tel que les mots de code sont
composés par les k bits d'information suivis par (n -k) bits de
redondance.
Ecrire la matrice génératrice du code permettant d'obtenir la forme
systématique du code.
2. Donner tous les mots de code.
3. En déduire la distance minimale dmin de ce code. Combien d'erreurs peut-
il corriger ?
4. Déterminer la matrice de contrôle du code, à partir de la matrice
génératrice sous forme systématique.
9. : Code orthogonal Soit le code linéaire C5,3 de matrice génératrice [pic]
a. Donner la matrice de contrôle du code.
b. Décrire le code orthogonal de C 10. : Correction Soit le code linéaire C3,2 de matrice génératrice [pic]
a. Construire le tableau standard des syndromes des vecteurs de {0,1}3.
b. Donner les transformés de tous les messages reçus possibles dans la
correction automatique par syndromes.
c. Cette transformation est-elle unique ? 11. : Correction et code de Hamming Soit le code linéaire Cn,r de matrice de contrôle [pic]
a. Donner la longueur des mots d'information et celle des mots de code.
b. Soit m un message dont tous les bits sont égaux à 1. Est-ce un mot du
code?
c. Montrer que le code est un code de Hamming. Que peut-on dire de la
correction des messages ayant e erreurs, 1 ?e?7 ?
d. Si p est la probabilité d'erreur sur un bit et si les erreurs par bit
sont indépendantes, exprimer en fonction de p la probabilité qu'un
message erroné devienne, après correction automatique, un mot de code
différent du mot émis. Donner une valeur approchée pour p=0,1. 12. : Code de Hamming Lors d'un transfert de données, vous recevez les messages suivants codés
grâce au code Hamming(7,4). Des erreurs s'y sont insérées. Retrouvez-les et
corrigez-les.
. 0101000
. 1110010
. 1100011
. 1011011
. 1101011
. 1000011 13. : Code de Hamming On considère un code de Hamming(7,4).
a. Coder le message suivant : 010110010111
b. Décoder le message suivant : 010001110010101101001
c. Y a-t-il des erreurs dans les mots 1010110, 0110011 ?
d. Compléter le mot : A B 1 C 0 1 0 14. Code de Hamming étendu (8,4) On considère le code linéaire en blocs défini par une matrice de contrôle
[pic] obtenue en rajoutant à la matrice de contrôle du code de Hamming (7,4,3)
une colonne de zéros puis une ligne de uns.
a. Quelles sont la longueur n et la dimension k de ce code ?
b. A quoi correspond pratiquement la modification du code de Hamming ?
c. Mettre la matrice H sous forme systématique.
d. Trouver une matrice génératrice G de ce code.
e. Montrer que ce code détecte toutes les configurations de deux erreurs et
corrige toutes les configurations d'une erreur. 15. : Taille de paquets et taux de transfert (rendement) L'objet de cet exercice est de comparer les taux de transmission et la
fiabilité d'un code par répétition et un code de Hamming. Le but est de
démontrer que dans le cas d'un canal bruité, émettre des paquets longs est
plus efficace qu'émettre des paquets courts. On désire transmettre un
message de 10000 bits à travers un canal bruité. On considère une
probabilité d'erreur p = 0,01.
Codage par répétition : Chaque bit est émis trois fois. Le décodage se fait
par un vote à la majorité.
a. Quel est le taux de transmission ?
b. Quelle est la probabilité que le décodage soit incorrect ?
c. Combien des 10000 bits du message ne sont pas correctement transmis ?
Paquets de 9 bits : On considère un code Hamming(9,3). Le message est
envoyé sous forme de paquets de 9 bits, de la forme (s1, s2, s3, t1, t2,
t3, t4, t5, t6). Les trois premiers bits s1, s2, s3 constituent le message
original, les six suivants t1, ... , t6 sont les bits de contrôle.
d. Quel est le taux de transmission ?
e. Combien y a-t-il de configuration possible de 0 , 1 , ou 2 erreurs dans
un tel paquet de 9 bits ?
f. Supposons qu'il existe un codage tel que les 6 bits de contrôle puissent
localiser toutes les configurations jusqu'à deux erreurs. Quelle est
alors la probabilité qu'un tel paquet de 9 bits ne soit pas décodé
correctement ?
g. Combien des 10000 bits du message ne sont pas transmis correctement ?
Conclusion Expliquer pourquoi transmettre un message en longs paquets est
plus efficace que de le transmettre en paquets courts. Pourquoi la
répétition n'est-elle pas une bonne idée ? 16. : Code polynomial Soit le code linéaire C3,2 de matrice génératrice [pic]
a. Montrer qu'il s'agit d'un code polynomial
b. Donner les matrices génératrices caractéristique et normalisée (forme
systématique) du code.
c. Décrire tous les codes polynomiaux C3,2 17. : Code polynomial Soit C un code polynomial obtenu par codage systématique, de générateur :
g(x) = x3+x2+x+1
a. Donner la longueur de la clé de contrôle des mots du code
b.