Exercices Codes Correcteurs - lirmm
Pour améliorer la fiabilité, on décide d'utiliser un code avec 9 répétitions. 5/ Quel
est le taux de ... Est-il possible de corriger ces erreurs ? Coder les messages ...
part of the document
: 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)
Quelle est la probabilité que 0, 1, 2,..., ou 4 des ces 5 bits sont changés lors de la transmission?
Quelle est la probabilité que l'erreur de transmission soit détectée ?
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.
: 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 e" 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 e" 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 e" 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.
: Contrôle de parité
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
Que peut-on dire d'un code de longueur quelconque n obtenu par parité paire, par parité impaire ?
: Contrôle de parité
Combien d'erreurs peuvent-elles être détectées grâce à un contrôle simple de parité? Est-il possible de corriger ces erreurs ?
Coder les messages suivants à l'aide d'un bit de parité :
1101011001
100
11111000111001111
Quels sont les taux de transmission (rendement) des trois messages ci-dessus ?
: Contrôle de parité
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.
Pour K=L=2, donner la matrice génératrice du code.
: Matrice de contrôle et matrice génératrice
Un code linéaire a pour matrice de contrôle EMBED Equation.3
Préciser la longueur n des mots de code et la longueur k des mots d'information.
Les messages suivants sont-ils des mots du code ?
m1 = (1 1 1 0 1 1)
m2 = (1 0 0 1 1 0)
Donner la matrice génératrice du code et le codage de chaque mot d'information.
: 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.
Donner la matrice génératrice et la matrice de contrôle de ce code
Soit i = (1 0 1 0), quel est le mot de code associé ?
Soit le message m = (1 1 1 1 0 0 1). Est-il un mot du code ?
: Code systématique
On considère un code en bloc linéaire (6,3), de matrice génératrice G.
1. Un code sous forme systématique est tel que les mots de code sont composés par les k bits dinformation 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.
: Code orthogonal
Soit le code linéaire C5,3 de matrice génératrice EMBED Equation.3
Donner la matrice de contrôle du code.
Décrire le code orthogonal de C
: Correction
Soit le code linéaire C3,2 de matrice génératrice EMBED Equation.3
Construire le tableau standard des syndromes des vecteurs de {0,1}3.
Donner les transformés de tous les messages reçus possibles dans la correction automatique par syndromes.
Cette transformation est-elle unique ?
: Correction et code de Hamming
Soit le code linéaire Cn,r de matrice de contrôle EMBED Equation.3
Donner la longueur des mots d'information et celle des mots de code.
Soit m un message dont tous les bits sont égaux à 1. Est-ce un mot du code?
Montrer que le code est un code de Hamming. Que peut-on dire de la correction des messages ayant e erreurs, 1 d"ed"7 ?
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.
: 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
: Code de Hamming
On considère un code de Hamming(7,4).
Coder le message suivant : 010110010111
Décoder le message suivant : 010001110010101101001
Y a-t-il des erreurs dans les mots 1010110, 0110011 ?
Compléter le mot : A B 1 C 0 1 0
Code de Hamming étendu (8,4)
On considère le code linéaire en blocs défini par une matrice de contrôle
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.
Quelles sont la longueur n et la dimension k de ce code ?
A quoi correspond pratiquement la modification du code de Hamming ?
Mettre la matrice H sous forme systématique.
Trouver une matrice génératrice G de ce code.
Montrer que ce code détecte toutes les configurations de deux erreurs et corrige toutes les configurations dune erreur.
: 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é.
Quel est le taux de transmission ?
Quelle est la probabilité que le décodage soit incorrect ?
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.
Quel est le taux de transmission ?
Combien y a-t-il de configuration possible de 0 , 1 , ou 2 erreurs dans un tel paquet de 9 bits ?
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 ?
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 ?
: Code polynomial
Soit le code linéaire C3,2 de matrice génératrice EMBED Equation.3
Montrer qu'il s'agit d'un code polynomial
Donner les matrices génératrices caractéristique et normalisée (forme systématique) du code.
Décrire tous les codes polynomiaux C3,2
: Code polynomial
Soit C un code polynomial obtenu par codage systématique, de générateur :
g(x) = x3+x2+x+1
[gøùûü Ò Õ ö ú ,
0
Q
]
½
À
ñ
õ
$ ( = } ½ ¾ À Á þ ÿ " & . / } º üõàÎà¼àªàªàªà¼à¼à¼àààà¼ààààªàà¼ààt"hãQûCJOJPJQJaJnH tH "h±x;CJOJPJQJaJnH tH "h¿p×CJOJPJQJaJnH tH "h#gCJOJPJQJaJnH tH "h'h CJOJPJQJaJnH tH "hk8CJOJPJQJaJnH tH (hãQûhãQûCJOJPJQJaJnH tH hãQûhãQûhÔ_g+Ø> Ò ÷ -
n
½
ò
% # ~ » Ò x.úíàØØØËËËí¾¾¾¾®ú¡gd$o ûÿ^`ûÿgd$o©¤d\$^©`gd±x; ©^©`gd±x; h^h`gd'h
& Fgd'h h^`hgd'h ^`gd_Bügdj*㺠» ½ Â Å Ð Ñ Ò Îhp:;>ÃÄÈ.08ëäàÙàäàʾʮʢÊwÊwÊwÊhÊYMÊwh¾)KCJOJQJaJ h¾)Kh¾)KCJOJQJaJ h$oh¾)KCJOJQJaJ+h$ohµMiCJH*OJPJQJaJnH tH (h$ohµMiCJOJPJQJaJnH tH h$oCJOJQJaJ h$ohµMiCJH*OJQJaJh'h CJOJQJaJ h$ohµMiCJOJQJaJ hßËhµMihµMi hãQûhµMi(h#ghãQûCJOJPJQJaJnH tH . ?£ÌDYÔ7LË ) y k òòòòâÝÎÎÝ¿¿°°°¿Ý¡
& F
¤d¤d[$\$gd_Bü
& F¤d¤d[$\$gd_Bü
& F¤d¤d[$\$gd_Bü
& F ¤d¤d[$\$gd'h gdj*㩤d\$^©`gd\% ª^ª`gd$o8ÆÌÎÖÜÞìòôü $
DXYÓÔ467LøñåñÓåñÓåñÓåñÓñ¾¨ñ¾¨ñ¾¨ñ¡vvoZ(hãQûhãQûCJOJPJQJaJnH tH hãQûhãQû(hãQûh'h CJOJPJQJaJnH tH "h'h CJOJPJQJaJnH tH h'h h=)Ìh'h +h$ohµMiCJH*OJPJQJaJnH tH (h$ohµMiCJOJPJQJaJnH tH " jÅðh$ohµMiCJOJQJaJh¾)KCJOJQJaJ h$ohµMiCJOJQJaJ ø - . M Y x y { k q r s t u v w x y | îÙÇٵ٣î|f|T|f|T|f?(h#gh#gCJOJPJQJaJnH tH "h#gCJOJPJQJaJnH tH +h#gh=)ÌCJH*OJPJQJaJnH tH (h#gh=)ÌCJOJPJQJaJnH tH h=)Ì h f h=)Ì h=)Ìh=)Ì"hãQûCJOJPJQJaJnH tH "h¿p×CJOJPJQJaJnH tH "h-x×CJOJPJQJaJnH tH (hãQûhãQûCJOJPJQJaJnH tH "h=)ÌCJOJPJQJaJnH tH
¥ Ð
1 L ] ^ éÔÂÔ¯ÔÂéÔéÔÂÂÔyqyqy_ÂD5jh#gh#gCJEHÎÿOJPJQJUaJnH tH "h* "CJOJPJQJaJnH tH *hÕ`´h: *hÕ`´h#g h#gh=)Ì"h=)ÌCJOJPJQJaJnH tH (h#gh=)ÌCJOJPJQJaJnH tH %h#gCJH*OJPJQJaJnH tH "h#gCJOJPJQJaJnH tH (h#gh#gCJOJPJQJaJnH tH +h#gh#gCJH*OJPJQJaJnH tH k Ð 1 t Å ÷
m 2 u « è ü ëÜ×˼¼¼××
& F
¤d¤d[$\$gd_Bü¤d¤d[$\$^`gd_Bü
& F ¤d¤d[$\$gd_Bü
& F ¤d¤d[$\$gd_Bü ¤d¤d[$\$gd_Bügdj*ã
& F
¤d¤d[$\$gd_Bü ¤d¤d[$\$^ `gd_Bü^ _ d p q s t « ¬ ù ý
m o éÕé·xfxTxTxTxLDLx *hÕ`´h* " *hÕ`´h:"h\%CJOJPJQJaJnH tH "henCJOJPJQJaJnH tH "h:CJOJPJQJaJnH tH "h#gCJOJPJQJaJnH tH 5jh#gh#gCJEHÎÿOJPJQJUaJnH tH ;j²uËN
h#gh#gCJEHÎÿOJPJQJUVaJnH tH &hÚ°CJEHÎÿOJPJQJaJnH tH ,h#gh#gCJEHÎÿOJPJQJaJnH tH ¿ À Â Ã Å Æ È É ç è ê ë í î ð ñ ò ó ô ö ÷ ù ú
# $ % ( ) + , . / 0 ëÕÃÕÃÕÃÕÃÕÃÕÃÕÃÕÃÕ®ÃÕÃÕÃÕÃÕîÃÕÃÕÃÕ®ÃÕîÃÕÃÕÃÕÃÕ®ÃÕÃÕÃÕÃ%h:CJH*OJPJQJaJnH tH (h:h:CJOJPJQJaJnH tH "h:CJOJPJQJaJnH tH +h:h:CJH*OJPJQJaJnH tH (h:h:CJOJPJQJaJnH tH 90 1 2 D i t u Å Æ ç è ü @!A!C!D![!h!!!¼!"""l#v#V$W$Y$i$$îÜîÊîÜî¸î£zozzzzz\UQîh* " h=)Ìh* "$hk8hk8CJOJQJaJnH tH jhª ¢hª ¢U"hk8hk86CJOJQJ]aJ hk8hk8CJOJQJaJ *hÕ`´hk8(h* "h* "CJOJPJQJaJnH tH "hIDCJOJPJQJaJnH tH "h§^àCJOJPJQJaJnH tH "h:CJOJPJQJaJnH tH "h* "CJOJPJQJaJnH tH ü C!E!0"ä"&#Ø#V$W$i$²$Ù$ù$%O%%þ%%&E&&Ó&úúúúúúúúõéÚÚõο¿¿õé°
& F¤d¤d[$\$gd_Bü
& F¤d¤d[$\$gd'h ¤d¤d[$\$gd'h
& F¤d¤d[$\$gd_Bü ¤d¤d[$\$gd_Bügdj*ãgdk8$$$$$$$$¢$®$¯$°$±$ëØÂØ{g{I.5j93h* "h4êCJEH¬ÿOJPJQJUaJnH tH ;jGLJ
h* "h4êCJEH¬ÿOJPJQJUVaJnH tH &hÚ°CJEH¬ÿOJPJQJaJnH tH ,h* "h* "CJEH¬ÿOJPJQJaJnH tH 5jh* "h* "CJEH¬ÿOJPJQJUaJnH tH (h* "h* "CJOJPJQJaJnH tH +h:h* "CJH*OJPJQJaJnH tH %h* "CJH*OJPJQJaJnH tH (h:h* "CJOJPJQJaJnH tH ±$²$Æ$Ù$÷$ø$ù$û$% % % %!%7%8%îÙîDz٫§mWBm(h* "h'h CJOJPJQJaJnH tH +h:h'h CJH*OJPJQJaJnH tH %h'h CJH*OJPJQJaJnH tH (h:h'h CJOJPJQJaJnH tH "h'h CJOJPJQJaJnH tH h'h h=)Ìh'h (h:h*12CJOJPJQJaJnH tH "h*12CJOJPJQJaJnH tH (h* "h* "CJOJPJQJaJnH tH "h* "CJOJPJQJaJnH tH 8%9%:%?%K%L%M%N%%%$&%&E&[&ä͹ÍänXnC
