ESEN 2014/2015 Mastère Web Intelligence
Corrigé Exercice 0 :
Source d'entrée X
Alphabet : { 0 , 1 }
Source de sortie Y
Alphabet : { 0 , 1 }
0
1
1-p
p
1-p
p
0
1
Sources :
entrée X d'alphabet { x1 = "0" , x2 = "1" } et p( x1 ) = p( x2 ) = 1/2 (caractères équiprobables).
sortie Y d'alphabet { y1 = "0" , y2 = "1" } et p( y1 ) = ? p( y2 ) = ?.
Probabilités conditionnelles p( y/x ): c'est une donnée du graphe.
p( y1/x1 ) = 1 – p
p( y2/x2 ) = 1 – p
p( y2/x1 ) = p
p( y1/x2 ) = p
Probabilités jointes entre les deux sources : calculées avec la loi de Bayes
p( x , y ) = p( y/x ).p( x )
p( x1 , y1 ) = (1-p) 1/2
p( x2 , y1 ) = p 1/2
p( x1 , y2 ) = p 1/2
p( x2 , y2 ) = (1-p) 1/2
Probabilités marginales de la source Y : calculées à partir des probabilités jointes
p( y1 ) = (1-p) 1/2 + p 1/2 = 1/2
p( y2 ) = p 1/2 + (1-p) 1/2 = 1/2
) y (p
2
j ∑
=
=
1 i
xp(
) y ,
j
i
Probabilités conditionnelles p( x/y) : calculées à partir de la loi de Bayes
précédent.
p( x/y ) = p( x , y ) / p( y ) en utilisant le résultat
p( x1/y1 ) = 1 – p
p( x1/y2 ) = p
p( x2/y1 ) = p
p( x2/y2 ) = 1 - p
Quantité d'information d'un caractère :
I( x1 ) = I( x2 ) = log2(2) = 1 bit
I( y1 ) = I( y2 ) = log2(2) = 1 bit
Entropie de chaque source:
H( X ) = 1 bit par symbole (= log2(K) avec K=2).
H( Y ) = 1 bit par symbole.
Entropie jointe: calcul direct à partir de probabilités jointes.
H( X , Y ) = (1/2) (1-p) log[ 2/(1-p) ] + (1/2) p log( 2/p ) + (1/2) p log( 2/p ) + (1/2) (1-p) log[ 2/(1-p) ]
= (1-p) log[ 2/(1-p) ] + p log( 2/p ) = (1-p) [ 1 - log( 1-p ) ] + p [ 1 - log( p ) ]
= 1 - (1-p) log( 1-p ) - p log( p )
Entropie conditionnelle moyenne:
) Y/X (H
= ∑
i
xp(
i
∑
)
j
log ) x/ y p(
j
i
1
) x/ y p(
j
i
1
=
2
) p-1 (
) p-1 ( -
=
log(
) p-1
p
log(
) p
log(
1
p1
+
)
p
log(
1
p
)
1
+
2
) p-1 (
log(
1
p1
+
)
p
log(
1
p
)
Codage : Corrigé TD - 1 - R. Rhouma
-
-
-
ESEN 2014/2015 Mastère Web Intelligence
Etant donné la symétrie des relations, H( X /Y ) aura, dans ce cas particulier, la même expression.
Quantité d'information mutuelle:
1er calcul à partir de l'entropie jointe.
I( X , Y ) = H (X ) + H( Y ) - H( X , Y )
2ème calcul à partir de l'entropie conditionnelle moyenne H( Y /X ):
= 1 + (1-p) log( 1-p ) + p log( p )
I( X , Y ) = H( Y ) – H (Y /X ) = 1 + (1-p) log( 1-p ) + p log( p )
Toujours par symétrie, la troisième méthode de calcul à partir de H ( X /Y ) est identique au précédent.
Quelques remarques :
1. si p = 0 ce qui veut dire pas d'erreur de transmission alors I( X , Y ) = 1. Similitude parfaite entre les deux sources, la
transmission se passe bien. H( X , Y ) = 1.
2. si p = ½, pagaille complète lors de la transmission. Dans ce cas I( X , Y ) = 0, plus du tout de similitude entre les deux
sources. H( X , Y ) = H( X ) + H( Y ) = 2. Tout se passe comme si les deux sources étaient indépendantes.
3. si p = 1, à nouveau I( X , Y ) = 1. Les deux sources sont à nouveau tout à fait semblables. Le fait qu'il y a dans ce cas
permutation du "0" et du "1" n'ayant pas d'importance.
Corrigé Exercice 1
1)
6
F
5
E
D 4
3
C
B
2
A 1
6
5
4
3
3
6
6
5
4
9
6
6
12
9
21
2)
3)
D
F
C
B
E
A
Symbole
Codage
Longueur
nk
F
E
D
C
B
A
00
10
11
010
0110
0111
2
2
2
3
4
4
probabilité
kp
216
215
214
213
212
211
4) Entropie de la source:
) X H(
= ∑
log p
k
2
(
k
1
p
k
=
)
2.3983
bits/
symbol
5) Longueur moyenne du code
= ∑R
p n
k
k
=
k
2,4286
bits/
symbol
Codage : Corrigé TD - 2 - R. Rhouma
ESEN 2014/2015 Mastère Web Intelligence
6) Efficacité :
h
huffman
=
)
XH
(
R
100
=
%75.98
7) Rapport de compression :
·R
8
100
=
%30
8)
F
E
D
C
B
A
6
5
4
3
2
1
0
0
1
1
1
1
MSB
0
1
0
1
1
1
0
1
1
0
1
LSB
9) Les deux codes ont même taux d’efficacité puisqu’ils partagent les meme longeurs nk et les mêmes
probabilités.
h
fano
shanon
=
)
(
XH
R
100
=
%75.98
=
h
huffman
Symbole
Codage
Longueur
nk
F
E
D
C
B
A
00
01
10
110
1110
1111
2
2
2
3
4
4
probabilité
kp
216
215
214
213
212
211
Corrigé Exercice 2
1)
G 7
6
F
E
5
D 4
3
C
B
2
A 1
7
6
5
4
3
3
7
6
6
5
4
9
7
6
6
12
9
7
16
12
28
2)
3)
G
F
E
D
C
B
A
Symbole
Codage
Longueur
nk
G
01
2
probabilité
kp
287
Codage : Corrigé TD - 3 - R. Rhouma
·
·
-
ESEN 2014/2015 Mastère Web Intelligence
F
E
D
C
B
A
10
000
001
110
1110
1111
2
3
3
3
4
4
286
285
284
283
282
281
4) Entropie de la source:
5) Longueur moyenne du code
) X H(
= ∑
log p
k
2
(
k
1
p
k
=
)
2.61
bits/
symbol
= ∑R
p n
k
k
=
2,64
bits/
symbol
6) Efficacité :
h
huffman
=
)
XH
(
R
k
100
=
%76.98
7) Rapport de compression :
·R
8
100
=
%33
8)
G
F
E
D
C
B
A
7
6
5
4
3
2
1
0
0
1
1
1
1
1
MSB
0
1
0
0
1
1
Publicité
1
0
1
0
1
1
0
1
LSB
Symbole
Codage
Longueur
nk
G
F
E
D
C
B
A
00
01
100
101
110
1110
1111
2
2
3
3
3
4
4
probabilité
kp
287
286
285
284
283
282
281
9) Les deux codes ont même taux d’efficacité puisqu’ils partagent les meme longeurs nk et les mêmes
probabilités.
h
fano
shanon
Corrigé Exercice 3
=
)
(
XH
R
100
=
%75.98
=
h
huffman
Codage : Corrigé TD - 4 - R. Rhouma
·
·
-
ESEN 2014/2015 Mastère Web Intelligence
=
H
01001
11010
10100
1) n =5 et k=2
2)
-
=THm
1
)
(
11101
001
010
100
011
110
)000(
⇒ donc
1m n’est pas un mot de code
-
=THm
2
(
11010
)000(
⇒ donc
2m est un mot de code
=
100
010
001
01011
)
110
10110
011
3)
(
2IPG
=
)
=
4) Tous les mots de codes
im
00
01
10
11
iC
00000
01101
11010
10111
iw
0
3
3
4
5) Distance minimale par trois méthodes :
- Méthode 1 :
d
- Méthode 2 :
d
=
=
min
min
{ } 3
=
w
i
{ } 3
=
d
ij
min
0
w
i
min
i
j
,
d’après le tableau de 4)
(voir tableau suivant)
Distance entre
jC
iC et
12d
13d
14d
23d
24d
34d
Valeur
3
3
4
4
3
3
- Méthode 3 : nombre minimale de colonnes de H linéairement liés est 3.
Codage : Corrigé TD - 5 - R. Rhouma
„
„
ESEN 2014/2015 Mastère Web Intelligence
Preuve : colonne4 + colonne1 + colonne2 = 0 ⇒
d
=
3
min
Corrigé Exercice 4
g(x) = 1 + x2 + x3
1) deg(g(x))= n-k = 3. et on a n=7 donc k=4 (cid:1)
2)
G
*
=
0001101
0011010
0110100
1101000
L
1
L
2
L
3
L
4
3) En effectuant les opérations suivantes sur les lignes de
*G :
L
1
L
2
L
1
L
1
L
3
L
+
+
L
2
L
+
L
3
L
2
On trouve la matrice systématique G :
L
1
L
2
L
3
+
+
4
4
=
G
0001101
0010111
0100011
1000110
4)
H
=
0111001
1110010
1011100
5)
m HC
T
=
(
0011101
)
001
010
100
101
111
011
110
)000
(
mC est donc n’est pas un mot de code.
Ou d’une autre manière :
xCm
x
Le reste de la division euclidienne de
1)(
+=
+
+
x
x
2
4
3
)(xCm
par g(x) est
x
2
„++ x
01
Donc
)(xCm
n’est pas un mot de code.
Codage : Corrigé TD - 6 - R. Rhouma
‹
‹
‹
‹
‹
‹
‹
‹
„
(cid:215)
(cid:215)
ESEN 2014/2015 Mastère Web Intelligence
3
7
x
+
=+
1
6) D’après la formule suivante :
+
++
2
)1
x
x
44 3
)
(
3
(1
x
44 2143421
xh
)(
On voit bien que g(x) divise
code (7,4)
17 +x
)(1
xg
)(
+
x
x
, donc g(x) qui est de degré 3 peut être un polynôme générateur d’un
7) Soit m=(1101)
++=
xm
x
3
1)(
3
x
)(
xm
xm (cid:215)
)(
=
3
x
4
x
+
6
x
3
x
/
)(
xg
donne :
x
+
3
x
+ x
+
12
3
x +
2
x
3
3
2
5
6
6
5
Publicité
4
x
x
+
+
+
x
x
+
x
x
x +
x
+
x
x
x
x =
)(
xr
+
4
5
2
4
D’où
=
)(
xmxCm
=
+
)(
6
x
x
3
x
+
4
+
x
)(
xr
+
x
3
2
Finalement
mC
(=
0011101
)
8)
)(
xYm
=
5
x
+
3
x
S
m
)(
x
=
)(
xY
m
mod
)(
xg
⇒
3
+ x
x
x +2
+
12
x
2
2
3
4
4
5
5
x +
x
+
+
x
x
+
+
x
x
+ 3
+
x
x
=+
x
x
3
2
4
x
x
x
S
)(
x
m
Table de décodage :
position Erreur
0
1
2
3
4
5
6
1
x
2x
3x
4x
5x
6x
syndrome
1
x
2x
12 +x
++ x
1+x
x +2
x
1
x
2
D’après la table de décodage, le syndrome
3
⇒
Codage : Corrigé TD - 7 - R. Rhouma
correspond à l’erreur
*
)(
xC
m
*
)(
xE
m
)(
xY
m
)(
x
+
=
+
+
=
S
x
x
x
x
x
m
6
5
2
=+
x
6
=
)(*
xE
m
(cid:215)
(cid:215)
ESEN 2014/2015 Mastère Web Intelligence
⇒
- =
mC
(
0001011
)
Finalement
(* =m
1011
)
Corrigé Exercice 5
++ x
+
x
3
1
++
x
1
4
4
5
3
6
2
5
5
x
x
+
x
+
14
+
4
x
1)
16 +x
+
x
x
+ x
x
+
x
x
13 +x
+ 2
+
x
x
++ x
x
0
On vérifie bien que
1
x
3
2
2
1
x
3
Mot de code C(x)
0
x ++
1 x+
+
+
x
x +
4x
…
…
x
x
2
3
2
x
++ x
1
divise
16 +x
Message m(x)
0
1
x
x+1
2x
1 x+
2
x +
2x
x ++
x
3x
1 x+
3
x +
3x
x ++
x
x +
3
x
+
x +
1
+
+
x
x
++
2
x
x
x
+
1
1
x
x
3
3
2
3
2
2
3
2
1
2)
3)
G
*
=
000111
001110
011100
111000
L
1
L
2
L
3
L
4
4)
En effectuant les opérations suivantes sur les lignes de G*, on trouve une matrice systématique G.
Codage : Corrigé TD - 8 - R. Rhouma
‹
‹
‹
‹
ESEN 2014/2015 Mastère Web Intelligence
L
2
L
2
L
3
⇒
G
=
+
L
1
000111
001001
010010
100011
=
H
101101
110110
L
1
L
2
L
3
L
4
L
1
L
1
L
3
L
4
+
+
+
5)
6)
d
min
=
2
Corrigé exercice 6
1) Question de cours.
2)
2.a) Pour un code (6,2), les messages possibles sont :
=
0
=
1)(
=
)(
xm
1
xm
2
)(
xm
3
xm
4
x
+=
1)(
x
2.b) on a la formule suivante :
X6+1 = (1+X2) (1+X+X2) (1+X+X2)
Deux polynômes générateurs sont des possibles candidats pour un code (6,2). Les polynômes générateurs
doivent être de degré 6 – 2=4.
)(
xg
1
)(
xg
2
Le polynôme générateur choisi est
2.c)
=
=
1(
1(
=
++
x
2
+
x
++
x
1()
2
1()
x
+=
1
x
2
x
++
x
Publicité
+
2
x
4
)(
xg
)(
xg
2
1)
2
++=
x
+=
1)
3
2
x
x
+
+
4
x
4
x
x
puisqu’il contient moins de terme que
)(1 xg
.
Message m(x)
0
1
x
1+x
Bits de contrôle r(x)
0
12 +x
x +3
x
+
++
x
x
1
x
2
3
Mot de code
)(xCm
4
x
5
x
4
+
5
x
+
x
0
+ x
+ 3
x
+
3
x
+
12
+
x
2
x
++
x
1
3)
3.a)
Le syndrome est la quantité avec laquelle le récepteur vérifie s’il y a eu des erreurs de transmissions.
Le récepteur calcule le syndrome
à partir du mot de code reçu selon deux méthodes :
)(x
- Méthode 1 :
S
)(
x
m
=
)(
xY
m
S m
mod
)(
xg
Si le récepteur travaille avec la méthode 1 alors la table de décodage doit être remplie selon la formule
suivante :
)(
xg
)(
x
=
S
m
- Méthode 2 :
)(
xE
m
'
S
m
)(
x
mod
=
)(
)(
xhxY
m
mod(
x
6
+
)1
Si le récepteur travaille avec la méthode 2 alors la table de décodage doit être remplie selon la formule
suivante :
)(
)(
xhxE
mod(
)(
x
)1
+
=
S
x
6
'
m
m
Codage : Corrigé TD - 9 - R. Rhouma
‹
‹
‹
‹
(cid:215)
(cid:215)
(cid:215)
(cid:215)
ESEN 2014/2015 Mastère Web Intelligence
Dans cet exercice, le code est (6,2) c'est-à-dire que le nombre des bits du syndrome est 6 – 2 = 4 bits.
Table de décodage (erreur simple) selon méthode 1 :
position
Pas d’erreur
0
1
2
3
4
5
)(xEm
0
1
x
2x
3x
4x
5x
)(xSm
0
1
x
2x
3x
12 +x
x +3
x
3.b)
Si on reçoit le mot de code
mY
⇒ Le syndrome se calcule par :
=
S
m
010111
=
)(
x
qui correspond au polynôme
)(
xYm
+=
x
3
x
+
4
x
+
5
x
)(
xY
m
mod
)(
xg
comme suit :
4
+
x
+ 3
x
3
+
x
+
+
x
x
+
12
4
+ x
x
1+x
5
5
x
x
4x
4
x
x
+ x
=+
12
+
12
S
m
)(
x
Le syndrome calculé est donc
=
*
table de décodage ⇒
)(
xEm
=)(*
le message correct est
xm
S m
4
x
x
= x
2 +
1
)(
x
⇒ Le mot de code correct est
ce qui correspond à l’erreur simple dans la position 4 de la
*
⇒
)(
xE
m
*
)(
xC
m
)(
xY
m
+=
x
=
+
+
x
x
5
3
111000
3.c)
=
010010
et
mY
1
Les syndromes associés sont :
S
1)(
mod
xg
)(
x
)(
x
mY
=
=
2
m
1
++=
x
S
m
2
)(
x
=
)(
x
mod
xg
1)(
++=
x
Y
m
1
Y
m
1
2
x
2
x
⇒ On constate qu’il ya un seul syndrome pour deux erreurs différentes. Ceci veut dire qu’il y a des erreurs
détectables et non-corrigeables.
Corrigé Exercice 7
1.a)
m(t)
mi
mi-1
q-1
mi-2
q-1
1.b)
n=3
C(t)
Codage : Corrigé TD - 10 - R. Rhouma
ESEN 2014/2015 Mastère Web Intelligence
K= 3
Si le message est de longueur L alors la longueur du mot de code est : n(L+K-1) =3 (L + 2)
+=
2
x
+
3
x
xm
1.c)
m= [1011] ⇒
1)(
et on a : g1(x)= 1+x2
g2(x)= 1+x
g3(x)= 1+x+x2
C(1)(x) = g(1)(x).m(x) =
1
C(2)(x) = g(2)(x).m(x) =
1
C(3)(x) = g(3)(x).m(x) =
1
3
+
+
x
++
x
x ++
x
x
x
2
5
4
+
+
x
x
4
5
-> C1= 100111
-> C2= 111010
-> C3= 110001
Donc C= 111 011 010 100 110 101
2) 2.a)
Combinaisons d'entrée
[ g0
(1) g1
(1) g2
(1) ] = [ 1 0 1 ]
[ g0
(2) g1
(2) g2
(2) ] = [ 1 1 0 ]
[ g0
(3) g1
(3) g2
(3) ] = [ 1 1 1]
[ mj mj-1 mj-2
]
Cj
(1)
Cj
(2)
Cj
(3)
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
0
1
0
1
1
0
1
0
0
0
1
1
1
1
0
0
0
1
1
0
1
0
0
1
2.b)
K = 3 ⇒ 2K-1 = 4 états internes. Les états sont repérés par des lettres : a fi
(00), b fi
(01), c fi
(10), d fi
(11). L'état présent
est constitué par les deux bits de droite de la combinaison d'entrée active et l'état suivant sera caractérisé par les deux bits de
gauche. La "sortie" correspondant au passage de l'un à l'autre est constituée de l'indication des colonnes Cj
Etat suivant
Combinaisons d'entrée
Etat présent
g(1) = [ 1 0 1 ]
g(2) =[ 1 1 0 ]
(3).
(1) Cj
(2) Cj
g(3) = [ 1 1 1]
[ mj mj-1 mj-2
]
Cj
(1)
Cj
(2)
Cj
(3)
a
a
b
b
c
c
d
d
0 0 0
0 0 1
Publicité
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
a
b
c
d
a
b
c
d
0
1
0
1
1
0
1
0
0
1
000
a
a
c
111
101
a
b
c
010
011
b
c
d
100
0
0
1
1
1
1
0
0
110
b
d
d
001
0
1
1
0
1
0
0
1
Codage : Corrigé TD - 11 - R. Rhouma
ESEN 2014/2015 Mastère Web Intelligence
2.c) Treillis
- Phase initiale
a
000
000
111
111
- cellule élémentaire
011
100
000
101
111
010
011
110
100
001
a
b
c
d
a
b
c
d
a
b
c
d
- phase finale
2.d)
a
b
c
d
000
101
011
110
000
101
a
000
a
011
010
111
c
100
101
110
b
Codage : Corrigé TD - 12 - R. Rhouma
d
001
ESEN 2014/2015 Mastère Web Intelligence
2.e) Vérification du résultat avec l’un des graphes
3°) Décodage
3.a) Algorithme de viterbi. Voir cours
3.b)
Mot de code reçu est : code [111 110 110 010 011 101]
5
2
4
1
Code reçu fi
111
3
110
a
b
c
d
5
2
4
1
0
Survivants
110
7
4
6
1
6
3
5
4
a
b
c
d
Phase centrale :
Code reçu fi
111
3
110
0
a
b
c
d
a
b
c
d
111
110
110
010
5
4
4
5
6
1
5
6
4
1
3
4
Survivants
a
b
c
d
0
2
1
Phase finale
Code reçu fi
111
110
110
0
2
1
4
1
3
4
111
110
110
010
0
2
1
1
3
4
4
1
5
6
111
110
110
010
011
a
b
c
d
0
2
1
1
3
6
5
1
7
4
4
1
5
Codage : Corrigé TD - 13 - R. Rhouma
ESEN 2014/2015 Mastère Web Intelligence
Survivants
111
110
110
010
011
0
2
1
4
4
1
1
3
a
b
c
d
111
110
110
010
011
101
a
b
c
d
a
b
c
d
0
2
1
5
1
4
4
1
1
3
111
110
110
010
011
111
0
1
010
011
1
110
100
1
1
Survivants
5
1
7
1
101
101
1
Le mot de correct est donc 111 100 110 010 011 101
Le message correspondant est 1 1 0 1
Corrigé Exercice 8
=
H
1101001
0111010
1110100
=
G
0001011
0010110
0100111
1000101
1)
2)
Codage : Corrigé TD - 14 - R. Rhouma
ESEN 2014/2015 Mastère Web Intelligence
Message m Mot de code
0000000
1010001
1110010
0100011
0110100
1100101
1000110
0010111
1101000
0111001
0011010
1001011
1011100
0001101
0101110
1111111
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
mC Poids w
0
3
4
3
3
4
3
4
3
4
3
4
4
3
4
7
D’après le tableau ci-dessus, {{ } 3
=
w
i
=
min
d
min
w
0
i
⇒
eC
=
E
d
min
2
1
=
1
Le nombre des erreurs corrigeables est 1.
3)
0=TCH
4) les erreurs doubles et triples et plus vont passer inaperçues parce que le pouvoir détecteur ne dépasse
pas les erreurs simples.
Preuve :
Le syndrome est codé sur 3 bits donc il ya
d’erreurs.
On a le cas de « pas d’erreur’
Et avec Les 7 cas d’erreurs simples, les codes des syndromes ont été totalement exploités et ne reste
aucune possibilité pour coder les erreurs doubles ou plus. Donc ils devront passer inaperçues pour le
récepteur.
32 possibilités qu’on peut dédier aux différents type
000
mS
=
5) différents codes d’erreurs = table de décodage
Position
Pas d’erreur
0
1
2
3
4
5
6
Erreur
0000000
1000000
0100000
0010000
0001000
0000100
0000010
0000001
Syndrome
000
100
010
001
110
011
111
101
Erreurs
simples
Codage : Corrigé TD - 15 - R. Rhouma
„
-