Exercice 1

TD 3
Protection contre les erreurs Exercice 1 :
1.a mot appartient au code => correct
mot n'appartient pas au code => erreur Pas de correction directe :
3 protocoles ARQ pour assurer la transmission correcte des informations :
(ARQ = Automatic Repeat Request) 1 Stop and wait (sans timout): [pic] 1 bis Stop and wait (avec timout): [pic]
2 Continue Go Back To N : [pic] 2 Selective Repeat [pic] 1.b Mixer Stop and wait et Selective Repeat Exercice 2 :
2.a
Code à parité (pair ou impair) :
Code à parité paire => nb bits à 1 pairs
[pic]
Code à parité impaire => nb bits à 1 impairs
[pic]
VRC : parité paire/impaire sur les lignes (1 bits par ligne)
LRC : parité paire/impaire sur les lignes (1 bits par colonne)
2.b
Parité paire :
|O |1 |0 |0 |
|0 |0 |1 |0 |
|0 |1 |1 |0/1 | Exercice 3 :
3a
Définition du poids de hamming : [pic] 3b
Définition de la distance de hamming entre deux mots: [pic] 3c
Définition de la distance de hamming d'un code : [pic] D nous renseigne sur la capacité de détection et de correction d'un code. 3d d(M0,M1)=5
d(M0,M2)=5
d(M0,M3)=10 d(M1,M2)=5
d(M1,M3)=5 d(M2,M3)=5 Distance de Hamming du code C
D(C) = 5 On peut donc corriger 2 bits erronés, et détecter 4 bits erronés 3e
d(M0,M)=3
d(M1,M)=2
d(M2,M)=8
d(M3,M)=7
le mot corrigé est M1, avec l'hypothèse du maximum de vraisemblance. 3f
d(M0,M)=6
d(M1,M)=3
d(M2,M)=7
d(M3,M)=4
Pas de correction possible 3g
3h
Code linéaire :
[pic] Exercice 4 a) M0 -> 00 00 00 00 00
M1 -> 01 01 01 01 01
M0 -> 10 10 10 10 10
M1 -> 11 11 11 11 11 Même code car distance de Hamming identique. Code C(k,n)
Rendement R = k/n
R = 2/10 = 20% b) G =
U*G = X
La matrice génératrice permet de transformer les bits d'informations en
mots codés.
H = La matrice de contrôle permet de controler que les mots codés reçus
appartiennent au code.
H * Xt = 0 Exercice 5
C(4,2)
Taille des mots constitués par les bits d'information : 2 (k)
Taille des mots codés : 4 (n)
G = 00 -> 0000
01 -> 0111
10 -> 1001
11 -> 1110
a)
Tableau standard :
| |0000 |0111 |1001 |1110 |
|0000 |0000 |0111 |1001 |1110 |
|0001 |0001 |0110 |1000 |1111 |
|0010 |0010 |0101 |1011 |1100 |
|0011 |0011 |0100 |1010 |1101 |
|0100 |0100 |0011 |1101 |1010 |
Le poids minimum doit être sur la première colonne. b)
y = 1101 => dernière classe
ycorrigé = E+Y=1101+0100=1001
Le bloc qui permet de déduire Y est le bloc 10 c)
D = 2 => Détection d-2 détecter 0 erreur,
corriger 0 erreur
d)
[pic] (i nombre de vecteurs d'erreurs avec i 1 (tableau standard)
P étant la probabilité de faire une erreur sur un bit P = 10-3
Pn est donc négligeable devant P
[pic] Pour ceux qui ne sont pas convaincus par un développement d'ordre 1 :
[pic]
e) Taux d'erreur résiduelle: probabilité qu'un symbole soit erronée après
décodage [pic] avec F(E) nombre de symboles erronées après décodage en utilisant le
vecteur E. 2 bits utiles :
F(E) ( {0,1,2}
F(E) = 0 si E est représentant (colonne 1)
F(E) = 1 si E est dans les colonnes 2 et 3
F(E) = 2 si E est dans les colonnes 4 | |1 |2 |3 |4 |
| |0000 |0111 |1001 |1110 |
|0000 |0000 |0111 |1001 |1110 |
|0001 |0001 |0110 |1000 |1111 |
|0010 |0010 |0101 |1011 |1100 |
|0100 |0100 |0011 |1101 |1010 | Dans la colonne 2 et 3:
1 vecteurs modifient 1 bits
3 vecteurs modifient 2 bits
4 vecteurs modifient 3 bits
0 vecteurs modifient 4 bits Dans la colonne 4:
0 vecteurs modifient 1 bits
2 vecteurs modifient 2 bits
1 vecteurs modifient 3 bits
1 vecteurs modifient 4 bits [pic]
[pic] Exercice 6
a)
[pic] b)
Code cyclique : toute permutation de j bits =>mot du code.
C'est un code polynomial dont le polynôme générateur est :
. Un diviseur de xn+1
. minimal
. irréductible dans l'ensemble des polynômes associés au code. 11011 -> x4+x3+x+1
c)d)
G =
Ce code n'est pas cyclique car ne divise pas x6+1
e)
110 -> 110001
f)
100011 n'appartient pas au code car syndrome est différent de 0
g)
D = 3
détection = d-1 = 1
correction = (d-1)/2 = 1
On peut corriger 1 erreur sur => bit sur xi
0 -> 0
x -> x
x2 -> x2
x3 -> x+1
x4 -> x2+x
x5 -> x2+x+1
Syndrome de 100011 est x2 donc l'erreur est sur le 3eme bit = 100111 2n-k classes
|000000 |001011 |010110 |011101 |100111 |101100 |110001 |111010 | |000000
|000000 |001011 |010110 |011101 |100111 |101100 |110001 |111010 | |000001
|000001 |001010 |010111 |011100 |100110 |101101 |110000 |111011 | |000010
|000010 |001001 |010100 |011111 |100101 |101110 |110011 |111000 | |000011
|000011 |001000 |010101 |011110 |100100 |101111 |110010 |111001 | |000100
|000100 |001111 |010010 |011001 |100011 |101000 |110101 |111110 | |000101
|000101 |001110 |010011 |011001 |100010 |101001 |110100 |111011 | |000110
|000110 |001101 |010000 |011011 |100001 |101010 |110111 |111100 | |000111
|000111 |001100 |010001 |011010 |100000 |101011 |110110 |111101 | |
vecteur d'erreur + mot reçus = mot corrigé
000110=>010110
000101=>000000
110010=>111010
101011=>001011
100010=>100111 Exercice 7 mot reçu R(x) = g(x)p(x)+S(x) ou S est le syndrome (reste de la division)
S(x)=0 => mot du code
S(x)?0 => n'est pas un mot du code M représente le polynôme constituant les bits d'information
M(x) = x14+x11+x10+x8+x6+x5+x3+x2+x+1 Par la définition des codes cycliques,
u(x)= R(x)+xn-kM(x)
xn-kM(x)= g(x)q(x)+R(x) Ayant g et M, il reste à trouver q et R, pour connaître la séquence
envoyée. Utilisant l'avis du CCITT, on suppose le code de type C(16,32).
Il faut donc d'abord multiplier M(x) par xn-k soit par x16 , puis diviser
ce nombre par g(x) pour trouver R(x) x16M(x)= x30+x27+x26+x24+x22+x21+x19+x18+x17+x16
Séquence complète u(x)=R(x)+x(n-k)M(x) :
0100110101101111 1110011011011001
x16*M(x) R(x)
Décodage :
u'(x)=q'(x)g(x)+ S(x)
Ici le syndrome S(x) est nul donc il n'a pas d'erreur, ou bien le code ne
permet pas de détecter l'erreur. -----------------------
bloc Syndrome x19+ x16+x15+x12+ x8+ x5+ x3+1
x20+x19+ x15+x12+x9+x8+ x5+x4+x3+1
x21+ x20+x19+ x17+x15+x12+ x10+x9+x8+x4+x3+1
x22+x21+ x20+x19+x18+x17+ x15+x12+x11+x10+x9+x8+ x6+x4+x3+1
x23+x22+x21+x20+x18+x17+x15+x11+x10+x9+x8+x7+x6+x4+x3+1
x24+ x23+x22+x21+x18+x17+x15+x13+x11+x10+x9+x7+x6+x4+x3+1
x14+x11+x8+x7+x6+x5+x4+x3 x27+x24+x22+x21+x18+x17+x16+x15+ x13+x10+x9+x7+x6+x4+x3+1
x15 +x14 + x13 + x10+ x9 +x7+x6 +x4+x3+1 = R
x16 +x15+x14 + x13 + x12 + x10+ x9 +x7+x6 + x5+x4+ x3
x19+ x16+ x14 + x13 + x12 + x10+ x9+ x8+x7+x6+x5 +x4
x20+x19+ x14 + x13 + x12 + x10+ x8+x7+x6+x5
x21+x20+x19+ x17+x14 + x13 + x12 + x8+x7+x6
x16+x12+x5+1 x23+x22+x21+x20+x18+x17+x14 + x13 +x11+x8
x24+ x23+x22+x21+ x18+x17+x14+x11
x30+x27+x26+x24+x22+x21+x19+x18+x17+x16+x15+x14+x13+x10+x9+x7+x6+x4+x3+1
x16+ x12+ x5+1 0 x22+x21+x20+x19+x18+x17+x14 + x13 + x12 +x11+x8+x7
x27+ x24+ x22+x21+ x18+x17+x16+x14
x14+
x11+
x8+
x7+
x6+
x5+
x4+
x3+
1 x16+x12+x5+1 x30+x27+x26+x24+x22+x21+x19+x18+x17+x16
Vecteur d'erreur E mots du code x3+x+1
x2+1 x5+x+1
x3+x2 x3+x+1
x3+x+1 x6+1
+x6+x4+x3
= x4+x3+1
+ x4+x2+x
= x3+x2+x+1
+ x3+x+1
= x2
0
1+x+x3= g (générateur)
x+x2+x4 = (x)g
1+x2+x3+x4 = (1+x)g
1+x+x2+x5 = (1+x2)g
x2+ x3+x5 = (x2)g
1+x4+x5 = (1+x+x2)g
x+x3+x4+x5 = (x2+x)g 0 0 0 0 0 0
0 0 1 0 1 1
0 1 0 1 1 0
0 1 1 1 0 1
1 0 0 1 1 1
1 0 1 1 0 0
1 1 0 0 0 1
1 1 1 0 1 0
1 0 1 1 1 1
0 1 0 1 1 0
0 0 1 0 1 1
000
001
010
011
100
101
110
111 1 0 1 1 1 1
0 1 0 1 1 0
0 0 1 0 1 1
1 0 0 1
0 1 1 1 I Car code systématique 1 0 1 0 0 0 0 0 0 0
0 1 0 1 0 0 0 0 0 0
1 0 0 0 1 0 0 0 0 0
0 1 0 0 0 1 0 0 0 0
1 0 0 0 0 0 1 0 0 0
0 1 0 0 0 0 0 1 0 0
1 0 0 0 0 0 0 0 1 0
0 1 0 0 0 0 0 0 0 1 1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 I Car code systématique "#$127:Y\????«¯æé ( + ,
üøñøêãÙÒËÄÀÄÀ¼µ¼­¨£­?¼?'fugYKhô'h"^¾5?\?mH sH hô'h"^¾6?]?mH sH
hô'h-i¥6?]?mH sH hô'h+[6?]?mH sH h+[h+[6?]?mH sH Min = n
+ 1 S = Vide
Pour i de 1 à 4
Si d(Mi, M) < Min alors
S = Mi
Min = d(Mi,M)
Sinon
Si d(Mi,M) == Min alors
S = Vide
FinSi
Fin Si
Fin Pour
k m