Théorie de l’information 2011 - 2012

THEORIE DE L’INFORMATION

CORRIGES

EISTI Guy Almouzni

Théorie de l’information TD 1 Corrigé. Modélisation mathématique d’une source d’information

TD 1 Corrigé. Modélisation mathématique d’une source d’information

Partie I. Entropie d’une source. Définitions et propriétés.

Exercice 1. Entropie d’une source.

n
On utilise la définition : H ( X ) = −∑ pi ⋅ log 2 ( pi ) en bits/symbole (n est la taille de l’alphabet). Ici n = 5.
i =1

1. H ( X ) = −0.1 ⋅ log 2 (0.1) − 0.2 ⋅ log 2 (0.2 ) − 0.3 ⋅ log 2 (0.3) − 0.15 ⋅ log 2 (0.15 ) − 0.25 ⋅ log 2 (0.25 ) ≈ 2.23 bits/symbo le
2. H ( X ) = −4 ⋅ 0.05 ⋅ log 2 (0.05) − 0.8 ⋅ log 2 (0.8) ≈ 1.12 bits/symbole
1
3. Par la définition : H ( X ) = −5 ⋅ 0.2 ⋅ log 2 (0.2 ) = − log 2   bits/symbole , ou plus directement par la relation :
5
H ( X ) = log 2 (n ) = log 2 (5) ≈ 2.32 bits/symbole .

L’entropie représente l’incertitude sur l’issue de l’expérience; c’est l’information moyenne apportée par l’expérience.

On remarquera que l’entropie est la plus élevée dans le cas 3. : c’est une propriété générale de l’entropie :

L’entropie atteint son maximum lorsque tous les symboles d’un alphabet donné de taille n sont équiprobables
(l’incertitude sur la prédiction de détermination d’un symbole est maximale). Elle vaut alors log 2 (n ) .

Exercice 2. Information moyenne.

1. L’alphabet ici ne contient que le symbole « pile ». On remarque que « pile » est un évènement certain (probabilité 1).
Il n’y a aucune incertitude sur l’issue de l’expérience. On a donc H ( X ) = 0 (rappel : log 2 (1) = 0 )

1 si le chiffre sur le dé (1 à 6) est pair

Y =
2. Soit . L’alphabet est de taille 2.
0 si le chiffre sur le dé (1 à 6) est impair
P(Y = 1) = P(Y = 0) = 0.5 .
D’après la propriété de l’entropie dans le cas d’une distribution uniforme, on a immédiatement :

H (Y ) = log 2 (2 ) = 1 bit/symbole

3. Soit Y ∈ {♣,♦,♥,♠}. L’alphabet est de taille 4. On calcule la distribution de probabilités associée :

Y ♠ ♣ ♥ ♦
P(Y ) 3/10 4/10 2/10 1/10

On en déduit l’entropie :
3 4 4 2 2 1 1
H (Y ) = −
3
⋅ log 2   − ⋅ log 2   − ⋅ log 2   − ⋅ log 2   ≈ 1.85 bits/symbole
10  10  10  10  10  10  10  10 

TD 1 Corrigé. 1
Théorie de l’information TD 1 Corrigé. Modélisation mathématique d’une source d’information

Exercice 3. Propriété de groupe.

1. H ( X ) = −0.1 ⋅ log 2 (0.1) − 0.2 ⋅ log 2 (0.2) − 0.3 ⋅ log 2 (0.3) − 0.15 ⋅ log 2 (0.15) − 0.25 ⋅ log 2 (0.25) ≈ 2.23 bits/symbole

2.
p = P( A) = 0.1 + 0.3 + 0.25 = 0.65
q = P(B ) = 1 − p = 0.2 + 0.15 = 0.35
H ( p, q ) = − p log 2 ( p ) − q log 2 (q ) ≈ 0.93 bit/symbole

3. Les distributions de probabilité de A et B sont : (on normalise pour que la somme des probabilités soit égale à 1)

x 1 3 5 x 2 4
PA ( x ) 0.1/0.65 0.3/0.65 0.25/0.65 PB ( x ) 0.2/0.35 0.15/0.35
= 10/65 = 30/65 = 25/65 = 20/35 = 15/35

10  10  30  30  25  25  20  20  15  15 
HA = − log 2   − log 2   − log 2   ≈ 1.46 bits/symbo le HB = − log 2   − log 2   ≈ 0.98 bit/symbol e
65  
65 65  
65 65  65  35  
35 35  35 

Vérification de la propriété de groupe : H ( X ) = H ( p , q ) + pH A + qH B :

H ( X ) = H ( p , q ) + pH A + qH B = 0.93 + (0.65 ⋅ 1.46 ) + (0.35 ⋅ 0.98 ) = 0.93 + 0.95 + 0.34 ≈ 2.23 bits/symbo le

Exercice 4. Vers le codage de Shannon.

1. H ( X ) = −0.1 ⋅ log 2 (0.1) − 0.2 ⋅ log 2 (0.2) − 0.3 ⋅ log 2 (0.3) − 0.15 ⋅ log 2 (0.15) − 0.25 ⋅ log 2 (0.25) ≈ 2.23 bits/symbole

2. Propriété de groupe : H ( X ) = H ( p, q ) + pH A + qH B avec q = 1− p

Interprétation : H ( X ) est composée de :
1. l’incertitude sur le choix de l’une des 2 parties A et B : c’est H ( p, q )
2. la moyenne des incertitudes associées à chacune des 2 parties séparément : c’est pH A + qH B

Ici :
H ( p , q ) représente la quantité moyenne d’information apportée par l’observation d’une source binaire.
La source est la réponse à une question et p, la probabilité de la réponse « oui ».

→ H ( p, q ) = − p log 2 ( p ) − q log 2 (q )

3. D’après les propriétés de l’entropie : dans le cas d’un alphabet de taille n, l’entropie atteint son maximum (égal à
log 2 (n) ) uniquement dans le cas de distribution de probabilités uniforme. Dans le cas d’un canal binaire ( n = 2 ) et une
distribution de probabilités uniforme ( p = q = 0.5 ), on a donc : max H ( p, q ) = log 2 (2) = 1 bit/symbole .
p∈[0 , 1]

4. Propriété de groupe : La réponse à une question binaire partage l’ensemble des valeurs possibles de X en 2 parties
disjointes : celle du « oui » et celle du « non ». On peut alors appliquer la propriété de groupe :
 H A = H oui

Propriété de groupe : H ( X ) = H ( p, q ) + pH A + qH B = H ( p, q ) + pH oui + qH non  H B = H non
q = 1 − p

Interprétation : H ( X ) est composée de :
1. l’incertitude sur le choix de l’une des 2 parties A et B : c’est H ( p, q )
2. la moyenne des incertitudes associées à chacune des 2 parties séparément : c’est pH A + qH B

TD 1 Corrigé. 2
Théorie de l’information TD 1 Corrigé. Modélisation mathématique d’une source d’information

Si H ( X ) est l’incertitude moyenne que l’on a sur le résultat du tirage de X en début de jeu, la quantité H ( p, q )
représente l’information moyenne apportée par la réponse à la 1 ère
question, et la quantité pH oui + qH non est
l’incertitude moyenne restant sur la valeur de X une fois la réponse obtenue.
On a alors intérêt à choisir la 1ère question de sorte qu’elle apporte le maximum d’information.
→ La question à poser doit partager l’ensemble des valeurs de X en 2 parties équiprobables (à approcher autant que possible).
Ici, c’est possible en posant la question : X ∈ A = {2, 3} ? car p ( X ∈ A ) = p ( X = 2 ) + p ( X = 3) = 0.2 + 0.3 = 0.5

5.

6. A la lecture de l’arbre, on obtient la table de code :

X 1 2 3 4 5
m (mot-code) 001 11 10 000 01
i

li (longueur de mot-code) 3 2 2 3 2
n

∑d = 2(2 ) + 3(2 )
− li −3 −2
Remarque : on verra au chapitre 3 (Codage de source) avec l’inégalité de Kraft, qu’un code sans préfixe existe car = 1.
i =1

d = 2; n = 5
L’inégalité de Kraft indique qu’un code sans préfixe de longueurs de mots-données (l1 , l 2 , K , l n ) existe si et seulement si
n
où d est la taille
∑d
i =1
− li
≤1

de l’alphabet du canal (d = 2 pour un canal binaire comme ici) et n, la taille de l’alphabet de la source.

7. A la lecture de l’arbre : (la méthode utilisée ici est la même que celle du codage de Shannon, qui sera étudiée plus tard)

X 1 2 3 4 5
P (probabilité) 0.1 0.2 0.3 0.15 0.25
X
N (nombre de questions) 3 2 2 3 2

Nombre moyen de questions (moyenne de N ):

E [N ] = (3 ⋅ 0.1) + (2 ⋅ 0.2 ) + (2 ⋅ 0.3) + (3 ⋅ 0.15 ) + (2 ⋅ 0.25 ) = 2.25 questions.
à comparer à l’entropie de X :
H ( X ) ≈ 2.23 bits/symbole .
[ ] [ ]
On remarque que E N est proche de H ( X ) avec E N > H ( X ) (sauf à perdre de l’information, on ne peut descendre en deça
de H ( X ) qui représente l’information moyenne intrinsèque).
__________

TD 1 Corrigé. 3
Théorie de l’information TD 2 Corrigé. Cryptographie

TD 2 Corrigé. Cryptographie

Partie I. Entropie : un jeu d’espion !

Exercice 1. Rendons à César ce qui est à César : son chiffre !

1. L’ensemble des clairs possibles M , celui des chiffrés C ainsi que celui des clés K coïncident avec l’alphabet
latin et on a :

P (M = m ) =
1
∀m ∈ M,
26

De plus, la fonction de chiffrement établit un lien entre le clair (m), le chiffré (c) et la clé (k) :
c = (m + k ) mod 26

P( A ∩ B )
Rappel :  P ( A B ) = P (B )

Alors, pour tout c ∈ C et pour tout m ∈ M , on a :

 P ( A ∩ B ) = P( A)P (B ) si AB indépendants

P[M = m et C = c ] P[M = m et K = c − m ]
P[M = m C = c ] = =
P[C = c] P[C = c ]

et du fait de l’indépendance de m et k :
P[M = m ]P[K = c − m ] P[M = m]P[K = k ]
P[M = m C = c ] = =
P[C = c ] P[C = c ]

Le choix du message et de la clé étant indépendants :

P (C = c ) = P (K = k ) =
1
26
On a finalement :
P[M = m C = c ] = P[M = m]

2. Il est facile de constater qu’il n’existe aucun décalage de l’alphabet qui transforme le message m = AB en le
chiffré c = DM (les lettres A et B sont consécutives dans l’alphabet, elles devraient l’être dans l’alphabet décalé).
Donc P[M = m et C = c ] = 0 .
2

P[M = m C = c ] = 0
1 1  1 
Nous avons alors (≠ P[M = m]) car P[M = m ] = ⋅ =  .
26 26  26 

Le chiffrement de César avec l > 1 ne vérifie donc pas la condition de Shannon de système parfaitement sûr.

TD 2 Corrigé. 1
Théorie de l’information TD 2 Corrigé. Cryptographie

Exercice 2. Cryptanalyse du chiffre de César.

1. On peut trouver la clé par force brute (méthode exhaustive) (25 essais de décalage à faire). La méthode d’analyse des
fréquences permet de trouver la clé (le décalage) car les lettres les plus fréquentes du message clair sont celles de la
langue française.
Remarque : Avec la méthode d’analyse des fréquences, il faut que le texte soit suffisamment long (au moins la taille de l’alphabet latin, soit
26 lettres) sinon les fréquences ne sont pas significatives (théorème central limite des probabilités).

Clair : BELLE MARQUISE VOS YEUX ME FONT MOURIR D AMOUR

Chiffré : HKRRK SGXWAOYK BUY EKAD SK LUTZ SUAXOX J GSUAX

FréquencesClair FrequencesChiffré

20 14,00
18
12,00
16
14 10,00
12 8,00
10 Série1 Série1
8
6,00
6 4,00
4
2,00
2
0 0,00
1 4 7 10 13 16 19 22 25 1 4 7 10 13 16 19 22 25

Décalage (clé) par analyse des fréquences : k = 6 = Pic Chiffré (11) - Pic Clair (5)
Décalage (clé) réel : k=6
Lettre OccurChiffré FréquencesChiffré FréquencesClair
A 4 10,53 8,4
B 1 2,63 1,06
C 0 0,00 3,03
D 1 2,63 4,18
E 1 2,63 17,26
F 0 0,00 1,12
G 2 5,26 1,27
H 1 2,63 0,92
I 0 0,00 7,34
J 1 2,63 0,31
K 5 13,16 0,05
L 1 2,63 6,01
M 0 0,00 2,96
N 0 0,00 7,13
O 2 5,26 5,26
P 0 0,00 3,01
Q 0 0,00 0,99
R 2 5,26 6,55
S 4 10,53 8,08
T 1 2,63 7,07
U 4 10,53 5,74
V 0 0,00 1,32
W 1 2,63 0,04
X 4 10,53 0,45
Y 2 5,26 0,3
Z 1 2,63 0,12
Som 38 100,00 99,97

TD 2 Corrigé. 2
Théorie de l’information TD 2 Corrigé. Cryptographie

2. On peut trouver la clé par force brute (méthode exhaustive) (25 essais de décalage à faire). La méthode d’analyse des
fréquences est piégée ici car les lettres les plus fréquentes du message clair ne sont pas celles de la langue française.
Clair : BONJOUR NOUS VOUS PROPOSONS TROIS WAGONS POUR PARTIR AU ZANZIBAR VOTRE AVION VA PARTIR
LA OU VOUS VOULEZ UN VRAI VAUTOUR VEUT TOUJOURS VOLER HAUT POUR VOIR SA PROIE UN ZOMBI MARCHAIT EN
ZIGZAGANT SUR LA ROUTE

Chiffré : UHGCHNK GHNL OHNL IKHIHLHGL MKHBL PTZHGL IHNK ITKMBK TN STGSBUTK OHMKX TOBHG OT ITKMBK
ET HN OHNL OHNEXS NG OKTB OTNMHNK OXNM MHNCHNKL OHEXK ATNM IHNK OHBK LT IKHBX NG SHFUB FTKVATBM XG
SBZSTZTGM LNK ET KHNMX

FréquencesClair FrequencesChiffré

20
16,00
18
14,00
16
14 12,00
12 10,00
10 Série1 8,00 Série1
8 6,00
6 4,00
4
2,00
2
0 0,00
1 4 7 10 13 16 19 22 25 1 4 7 10 13 16 19 22 25

Décalage (clé) par analyse des fréquences : k = 3 = Pic Chiffré (8) - Pic Clair (5)
Décalage (clé) réel : k = 19
Lettre OccurChiffré FréquencesChiffré FréquencesClair
A 2 1,16 8,4
B 11 6,40 1,06
C 2 1,16 3,03
D 0 0,00 4,18
E 4 2,33 17,26
F 2 1,16 1,12
G 10 5,81 1,27
H 24 13,95 0,92
I 7 4,07 7,34
J 0 0,00 0,31
K 20 11,63 0,05
L 10 5,81 6,01
M 11 6,40 2,96
N 19 11,05 7,13
O 11 6,40 5,26
P 1 0,58 3,01
Q 0 0,00 0,99
R 0 0,00 6,55
S 6 3,49 8,08
T 18 10,47 7,07
U 3 1,74 5,74
V 1 0,58 1,32
W 0 0,00 0,04
X 7 4,07 0,45
Y 0 0,00 0,3
Z 3 1,74 0,12
Som 172 100,00 99,97

TD 2 Corrigé. 3
Théorie de l’information TD 2 Corrigé. Cryptographie

Partie II. Entropie et arbres de décision

Exercice 3. Le jeu de la fausse pièce.

1. n = 8 pièces.

(a) Il y a 2x8 = 16 réponses possibles.

En effet, une réponse est un couple dont le 1er élément donne la fausse pièce et le 2nd le sens de la différence de poids.
Si on suppose que les pièces sont numérotées et si on note – pour la pièce la moins lourde et + pour la pièce la plus
lourde, les réponses possibles sont alors de la forme (i, -) ou (i, +) avec i = 1, 2, …, 8.

(b) Le résultat de chaque pesée peut prendre une des 31 = 3 valeurs possibles G, E, D.
→ Les résultats de 2 pesées sont des couples prenant des valeurs dans {G, E, D}x{G, E, D}.
Il y a donc 32 = 9 résultats possibles.
→ De façon analogue, les résultats de 3 pesées sont des triplets et il y a 33 = 27 valeurs possibles.
(c) Non, car le résultat de cette pesée est connu d’avance.

En effet, nous savons qu’il existe une seule pièce fausse. Elle sera obligatoirement dans l’un des 2 lots. La balance
penchera vers la Gauche ou vers la Droite sans que cela nous apporte un maximum d’information.

(d) Manipultation.

(e) Ne pas effectuer de pesées dont on connaît le résultat (tout ou partie) et donc n’apportant aucune ou peu
d’information (entropie nulle ou faible). Faire des pesées maximisant l’information apportée (donc l’entropie).

Voici une 1ère stratégie possible : n = 8 pièces, 3 pesées successives.

TD 2 Corrigé. 4
Théorie de l’information TD 2 Corrigé. Cryptographie

Voici une 2nde stratégie possible : n = 8 pièces, 3 pesées successives.

Enfin, voici une 3ème stratégie possible : n = 8 pièces, 3 pesées successives.

TD 2 Corrigé. 5
Théorie de l’information TD 2 Corrigé. Cryptographie

2. Voici une stratégie possible : n = 9 pièces, 3 pesées successives.

__________

TD 2 Corrigé. 6
Théorie de l’information TD 3 Corrigé. Codage de source

TD 3 Corrigé. Codage de source

Partie I. Codes sans préfixe.

Exercice 1. Décodage. Procédure de décodage pas à pas : 1011 000 010 1010 100 donne la séquence dhief

Exercice 2. Code sans préfixe.

Il suffit d’appliquer l’inégalité de Kraft, avec n = 10 (taille de l’alphabet de la source), d = 2 (code binaire) et
(l1 , l 2 ,K, l n ) = {4, 4, 4, 3, 2, 4, 3, 4, 3, 4} :
Théorème 3.1. Inégalité de Kraft. Un code instantané (≡ sans préfixe) de longueurs de mots-données
(l1 , l 2 ,K, l n ) existe si et seulement si
n

∑d
i =1
−li
≤1

où d est la taille de l’alphabet du canal, et n, la taille de l’alphabet de la source (d = 2 pour un canal binaire).

6 3 1 6+6+4
( ) ( ) ( )
n
Ici : ∑d
i =1
− li
= 6 ⋅ 2 − 4 + 3 ⋅ 2− 3 + 1 ⋅ 2− 2 = + + =
16 8 4 16
=1
→ l’inégalité de Kraft est vérifiée → un code binaire sans préfixe existe avec ces longueurs de mots.

Partie II. Codes sans préfixe et arbres binaires.

Exercice 3. Code sans préfixe. Arbre binaire.

1. Arbre associé au code suivant :
si a b c d e f g h i j
mi 1111 1110 110 1011 1010 100 011 000 010 001

Il s’agit d’un code sans préfixe.

1 a
1 0 b
1 c 1
0 0 …. élagage (code sans préfixe)
1 d
1
0 e
1 0 f 1
0 0
g 1
1
0
1 i 1
0 0 0
j 1
1
0 0
h 1
0 0

TD 3 Corrigé. 1
Théorie de l’information TD 3 Corrigé. Codage de source

2. Un code sans préfixe de longueurs de mots suivantes :

si a b c d e f g h i j
li 4 4 4 3 2 4 3 4 3 4

1 a
1 0 b
1 1 c
0 0 f
1 j
1
1 0 0 h
d 1
0 …. élagage (code sans préfixe)
0
g 1
1
0
1 i 1
0 0 0
1
e 1
0 0
1
0 0
→ Table de code :
si a b c d e f g h i j
mi 1111 1110 1101 100 00 1100 011 1010 010 1011
li 4 4 4 3 2 4 3 4 3 4

Partie III. Codage de Huffman

Exercice 4. Code sans préfixe optimal. Méthode de Huffman. Source d’alphabet Ω et de distribution
de probabilité :

si a b c d e f g h i j
pi 0.2 0.05 0.1 0.05 0.15 0.05 0.1 0.05 0.15 0.1

1. Longueur moyenne minimale pour un code binaire de cette source : on utilise le théorème de la borne inférieure :

Théorème 3.3. Borne inférieure. Soit une source S d’alphabet Ω S = {s1 , L , s n } de taille n et de distribution de
probabilités PS = {p1 , L , p n } . Soit un canal d’alphabet binaire Ω C = {0, 1} , donc de taille d = 2 , sans bruit,
stationnaire et sans mémoire. Soit un code déchiffrable {m1 , L , mn } de longueurs de mots {l1 , L , l n } .
Alors la longueur moyenne de mots de code vérifie :
 n
 H (S )  n

 L = ∑ pili  ≥ ⇒  L = ∑ pili  ≥ H (S )
 i =1  log 2 (d )  i =1 
− li − li
L’égalité n’est possible que si ∀i = 1, L , n pi = d = 2 .

→ La longueur moyenne minimale des mots d’un code binaire de cette source est l’entropie :
H (S ) n =10 n =10
L min = = H (S ) = ∑ pi log 2 ( pi ) avec H (S ) = pi log 2 ( pi ) = 3.14 bits/symbole → L min = 3.14 bits/symbole
∑
log 2 (d ) i =1 i =1

TD 3 Corrigé. 2
Théorie de l’information TD 3 Corrigé. Codage de source

2. Un code absolument optimal est tel que la longueur moyenne des mots-codes est égale à la borne inférieure
H (S )
. Le théorème de la borne inférieure indique que la borne inférieure est atteinte si les probabilités des
log 2 (d )
symboles de la source sont des puissances de 2 : ∀i = 1, L , n p i = d − li = 2 − li . Ce n’est pas le cas ici.
→ Un code absolument optimal n’existe pas pour cette source, car les probabilités des symboles de la source ne sont
pas toutes des puissances de 2.

3. Construction d’un code sans préfixe optimal selon la méthode de Huffman :

On trie les caractères de la source par probabilité décroissante pour que les symboles les plus probables (revenant donc
souvent dans le message émis) soient codés avec un nombre de bit minimal (→ réduction de la quantité d’information, du débit, pour
compression par exemple).

Parcours feuilles → racine :

Ici, on regroupe les 2 caractères les moins probables (f et h), on l’appelle fh, on additionne les probabilités
correspondantes et on recommence.
si a e i c g j b d f h
pi 0.2 0.15 0.15 0.1 0.1 0.1 0.05 0.05 0.05 0.05
si a e i c g j fh b d
pi 0.2 0.15 0.15 0.1 0.1 0.1 0.1 0.05 0.05
si a e i c g j fh bd
pi 0.2 0.15 0.15 0.1 0.1 0.1 0.1 0.1
si a fhbd e i c g j
pi 0.2 0.2 0.15 0.15 0.1 0.1 0.1
si a fhbd gj e i c
pi 0.2 0.2 0.2 0.15 0.15 0.1
si ic a fhbd gj e
pi 0.25 0.2 0.2 0.2 0.15
si gje ic a fhbd
pi 0.35 0.25 0.2 0.2
si afhbd gje ic
pi 0.4 0.35 0.25
si gjeic afhbd
pi 0.6 0.4

TD 3 Corrigé. 3
Théorie de l’information TD 3 Corrigé. Codage de source

4. Représentation du code sous forme d’arbre :

Parcours racine → feuilles : Convention arbitraire : 1 ≡ symboles les plus probables, 0 ≡ symboles les moins probables

gj 1 0.1 g
0.2
gje 1
0 0.1
1 0.15 j
0.35
0 e
gjeic
0.15
0.6 ic 1
i
1 0 0.1
0.25
0 c

0.2
1 a
0 0.4
fh 1 0.05 f
0.1
fhbd 1 0.05 h
afhbd 0
0 0.1 bd 1 0.05 b
0.2
0 d
0 0.05
Un code optimal sans préfixe

→ Table de code :
si a b c d e f g h i j
pi 0.2 0.05 0.1 0.05 0.15 0.05 0.1 0.05 0.15 0.1
mi 01 0001 100 0000 110 0011 1111 0010 101 1110
li 2 4 3 4 3 4 4 4 3 4

Longueur moyenne du code :

n =10
L= ∑pl i i = 2(0.2 ) + 4(0.05) + 3(0.1) + 4(0.05) + 3(0.15) + 4(0.05 ) + 4(0.1) + 4(0.05) + 3(0.15) + 4(0.1) = 3.2 bits/symbo le
i =1

L > (H (S ) = 3.14 bits/symbole )

__________

TD 3 Corrigé. 4
Théorie de l’information TD 4 Corrigé. Compression de données

TD 4 Corrigé. Compression de données

Codage et compression d’images sans pertes

Exercice 1. Codages RLE (Run Length Encoding) et Huffman.

Méthode 1. Codage de Huffman.

1. Statistique du nombre de pixels (B, N, G) de l’image :

Ligne B N G
1 8 1 0
2 6 3 0
3 4 0 5
4 2 1 6
5 0 3 6
6 2 1 6
7 4 0 5
8 6 3 0
9 8 1 0
Cumul 40 13 28 81
Chaque pixel étant codé sur 8 bits, l’image occupe une taille de : 9×9×8 = 648 bits = 81 Octets.
→ Table des fréquences des couleurs présentes dans l’image :
Couleur B N G
Nombre d’occurences 40 13 28
Fréquence pi 40/81 13/81 28/81

40  40  13  13  28  28 
2. Entropie : H =− log 2   − log 2   − log 2   ≈ 1.46 bits/symbole
81  81  81  81  81  81 
Efficacité du codage qui associe 8 bits à chaque pixel : L’entropie H (~ 1.46 bits/symbole) est inférieure au
codage utilisé (8 bits/pixel) → Une compression sans pertes de l’image est possible.

3. Arbre de Huffman :
si B G N
pi 40/81 28/81 13/81
si GN B
pi 41/81 40/81
Convention arbitraire : 1 ≡ symboles les plus probables, 0 ≡ symboles les moins probables

G
1 28/81
GN
41/81 N
1 0
1 3/81

0
B
40/81
Un code optimal sans préfixe

TD 4 Corrigé. 1
Théorie de l’information TD 4 Corrigé. Compression de données

Code associé :
si B G N
pi 40/81 28/81 13/81
mi 0 11 10
li 1 2 2

4. Longueur du code :
40 pixels B → 40 x 1 bit = 40 bits
28 pixels G → 28 x 2 bits = 56 bits
13 pixels N → 13 x 2 bits = 26 bits
→ Taille du code de Huffman (en bits) pour cette image : 40 + 56 +26 = 122 bits

 NC − C
Taux de Compression (% ) = NC = 1 − NC
C
648 − 122 Rappel : 
Taux de compression : t1 = ≈ 81 %
648  NC : taille des données non compressées
C : taille des données compressées



Méthode 2. Codage RLE.

1. Code RLE :
(4, B) (1, N) (7, B) (3, N) (5, B) (5, G) (3, B) (3, G) (1, N) (3, G) (1, B) (3, G) (3, N) (3, G) (1, B)
(3, G) (1, N) (3, G) (3, B) (5, G) (5, B) (3, N) (7, B) (1, N) (4, B)
2. Longueur du code : 25 couples x 16 bits = 400 bits → Taille du code RLE (en bits) pour cette image : 400 bits

3. Taux de compression : t 2 = 648 − 400 ≈ 38 %

648

Méthode 3. Codage RLE + Huffman.

1. Table des fréquences des couples (nb, c) présents dans le code RLE de l’image :
Couple (4, B) (1, N) (7, B) (3, N) (5, B) (5, G) (3, B) (3, G) (1, B)
Nombre d’occurences 2 4 2 3 2 2 2 6 2
Fréquence pi 2/25 4/25 2/25 2/25 2/25 2/25 2/25 6/25 2/25

2  2  3  3  4  4  6  6 
2. Entropie : H = −6 ⋅ log 2   − log 2   − log 2   − log 2   ≈ 3.03 bits/symbole
25  25  25  25  25  25  25  25 
Efficacité du codage qui associe 16 bits à chaque couple : L’entropie H (~ 3.03 bits/symbole) est inférieure au
codage utilisé (16 bits/couple) → Une compression sans pertes de l’image est possible.

TD 4 Corrigé. 2
 Théorie de l’information TD 4 Corrigé. Compression de données

3. Arbre de Huffman : Pour alléger la notation, on associe une lettre à chaque couple

si (3, G) ≡ a (1, N) ≡ b (3, N) ≡ c (4, B) ≡ d (7, B) ≡ e (5, B) ≡ f (5, G) ≡ g (3, B) ≡ h (1, B) ≡ i

pi 6/25 4/25 3/25 2/25 2/25 2/25 2/25 2/25 2/25
si a b Hi c d e f g
pi 6/25 4/25 4/25 3/25 2/25 2/25 2/25 2/25
si a b Hi fg c d e
pi 6/25 4/25 4/25 4/25 3/25 2/25 2/25
si a b Hi fg de c
pi 6/25 4/25 4/25 4/25 4/25 3/25
si dec a B hi fg
pi 7/25 6/25 4/25 4/25 4/25
si hifg dec A b
pi 8/25 7/25 6/25 4/25
si ab hifg Dec
pi 10/25 8/25 7/25
si hifgdec ab
pi 15/25 10/25
Convention arbitraire : 1 ≡ symboles les plus probables, 0 ≡ symboles les moins probables

2/2 5 h = (3,B)
4 /25 hi 1
hifg 1 2/25 i = (1 ,B)
0 2/25 f = (5,B)
1 4 /25 fg 1
8/25 0 2/2 5
hifgdec 0 g = (5 ,G)
4 /25
de 1
dec 1 2/25 d = (4 ,B)
15/25 0
1 0 2/25 e = (7,B)
7/2 5
0 3 /25
c = (3, N)
6/25
1 a = (3 ,G)
0 10/25

ab 4 /25
0 b = (1,N)

Un code optimal sans préfixe

Code associé :
si (3, G) ≡ a (1, N) ≡ b (3, N) ≡ c (4, B) ≡ d (7, B) ≡ e (5, B) ≡ f (5, G) ≡ g (3, B) ≡ h (1, B) ≡ i
pi 6/25 4/25 3/25 2/25 2/25 2/25 2/25 2/25 2/25
mi 01 00 100 1011 1010 1101 1100 1111 1110
li 2 2 3 4 4 4 4 4 4

4. Longueur du code : (6 couples x 2 bits) + (4 couples x 2 bits) + (3 couples x 3 bits) + 6 x (2 couples x 4 bits) = 77 bits
→ Taille du code de Huffman (en bits) pour la séquence du code RLE de cette image = 77 bits

648 − 77
Taux de compression : t3 = ≈ 88.1 %
648

5. La dernière méthode (Codage RLE + Huffman) présente le taux de compression le plus élevé.
__________

TD 4 Corrigé. 3
Théorie de l’information TD 5 Corrigé. Modélisation mathématique d’un canal

TD 5 Corrigé. Modélisation mathématique d’un canal

Partie I. Représentation mathématique d’un canal de transmission

Exercice 2. Un modèle probabiliste de transmission.

1. Les probabilités de réception données définissent la distribution de probabilités conditionnelle P(Y X ) .

2. Représentation sous forme de graphe des probabilités de réception :

3. Matrice de distribution conditionnelle P(Y X ) :

X \Y 0 1 -1
P(Y X ) = 0 0.7 0.2 0.1

1 0.3 0.6 0.1

4. Distributions manquantes :

Distribution conjointe de X et Y : P( X , Y ) On utilise la définition avec n = 2 et m = 3 :

p(xi , y j ) = p( y j xi ) p(xi ) i = 1,K, n j = 1,K, m
→
X \Y 0 1 -1
P( X , Y ) = 0 (0.7 x 0.5) (0.2 x 0.5) (0.1 x 0.5)
0.35 0.1 0.05
1 (0.3 x 0.5) (0.6 x 0.5) (0.1 x 0.5)
0.15 0.3 0.05

Distributions marginales de X : PX = P( X ) , et de Y : PY = P(Y ) Définition avec n = 2 et m = 3 :

PX = P( X ) : p(xi ) = ∑ p(xi , y j ) PY = P(Y ) : p( y j ) = ∑ p(xi , y j )

m n
i = 1, K, n j = 1, K, m
j =1 i =1

→ PX = P( X ) (donnée) s’obtient comme la somme des éléments de chaque ligne de P( X , Y ) :  PX (0) = 0.35 + 0.1 + 0.05 = 0.5
 PX (1) = 0.15 + 0.3 + 0.05 = 0.5
 PY (0 ) = 0.35 + 0.15 = 0.5
→ PY = P(Y ) s’obtient comme la somme des éléments de chaque colonne de P( X , Y ) : 
 PY (1) = 0.1 + 0.3 = 0.4
 P (− 1) = 0.05 + 0.05 = 0.1
 Y
→
X \Y 0 1 -1 PX
P( X , Y ) = 0 0.35 0.1 0.05 0.5
1 0.15 0.3 0.05 0.5
PY 0.5 0.4 0.1

TD 5 Corrigé. 1
Théorie de l’information TD 5 Corrigé. Modélisation mathématique d’un canal

Distributions conditionnelles P( X Y ) et P(Y X ) On utilise la définition avec n = 2 et m = 3 :

(
P( X Y ) : p xi y j = ) p(px(y, y) )i j
i = 1,K, n j = 1,K, m
j

→
X \Y 0 1 -1
P(X Y ) = 0
0.7
(0.35 / 0.5)
0.25
(0.1 / 0.4)
0.5
(0.05 / 0.1)

1 (0.15 / 0.5) (0.3 / 0.4) (0.05 / 0.1)

0.3 0.75 0.5

p(xi , y j )
P(Y X ) : p(y j xi ) = i = 1,K, n j = 1,K, m
p( xi )
(donnée)

→
X \Y 0 1 -1
P(Y X ) = 0
0.7
(0.35 / 0.5)
0.2
(0.1 / 0.5)
0.1
(0.05 / 0.5)

1 (0.15 / 0.5) (0.3 / 0.5) (0.05 / 0.5)

0.3 0.6 0.1

5. Entropies associées au canal : H ( X ) , H (Y ) , H ( X , Y ) , H ( X Y ) et H (Y X )

H ( X ) . L’entropie de la source. La source binaire X ayant une distribution uniforme :

n=2
H ( X ) = −∑ p( xi ) log 2 [ p( xi )] = log 2 (2) = 1 bit/symbole.
i =1

H (Y ) . L’entropie du récepteur. On utilise la distribution marginale PY = P(Y ) :

m =3
H (Y ) = − ∑ p( y i ) log 2 [ p( y i )] = −0.5 log 2 (0.5) − 0.4 log 2 (0.4) − 0.1 log 2 (0.1) ≈ 1.36 bits/symbole.
i =1

H ( X , Y ) . L’entropie conjointe ”source-récepteur”. On utilise la distribution conjointe P( X , Y ) :

[ ]
n = 2 m =3
H ( X , Y ) = −∑ ∑ p (x i , y j ) log 2 p (x i , y j ) ≈ 2.22 bits/symbole.
i =1 j =1

H ( X Y ) . L’entropie conditionnelle de la source, sachant le symbole reçu.

On utilise la distribution conjointe P( X , Y ) et la distribution conditionnelle P( X Y ) :
 p (x , y )
[ ( )]
n=2 m=3 n=2 m=3
H ( X Y ) = −∑∑ p (xi , y j )log 2  i j  = −∑∑ p (xi , y j )log 2 p xi y j ≈ 0.86 bit/symbole.
i =1 j =1  p ( y j )  i =1 j =1

H (Y X ) . L’entropie conditionnelle du récepteur, sachant le symbole émis.

On utilise la distribution conjointe P( X , Y ) et la distribution conditionnelle P(Y X ) :
 p (x , y )
[ ]
n=2 m=3 n=2 m=3
H (Y X ) = −∑∑ p (xi , y j )log 2  i j  = −∑∑ p (xi , y j )log 2 p ( y j xi ) ≈ 1.22 bit/symbole.
i =1 j =1  p( xi )  i =1 j =1

6. Déduction de l’information mutuelle I ( X ; Y ) du canal :

I ( X ; Y ) = I (Y ; X ) = H (Y ) − H (Y X ) = H ( X ) − H (X Y ) ≈ 0.14 bit/symbole.

TD 5 Corrigé. 2
Théorie de l’information TD 5 Corrigé. Modélisation mathématique d’un canal

Exercice 3. Capacité de canal.

1. Canal symétrique ? Non, ce canal ne correspond pas à la définition d’un canal symétrique :

Rappel : Définition d’un canal symétrique : « Un canal symétrique est caractérisé par une propriété particulière de sa
( )
matrice de transition P X Y . Toutes les lignes de cette matrice sont équivalentes entre elles par permutation et toutes
les colonnes également. Cela veut dire que toutes les lignes sont obtenues par permutation d’une seule d’entre elles, et
toutes les colonnes sont obtenues par permutation d’une seule d’entre elles. »

Certes, ici les lignes de la matrice de transition sont toutes équivalentes par permutation, mais pas les colonnes.

2. Distribution de probabilité conjointe de X et Y : P( X , Y ) On utilise la définition de la distribution

conditionnelle P(Y X ) impliquant la distribution marginale de X, PX , avec n = 2 et m = 3 :
p(xi , y j )
P(Y X ) : p(y j xi ) = i = 1,K, n j = 1,K, m → p(xi , y j ) = p( y j x i ) p( xi )
p( xi )

On en déduit :
Distribution marginale de Y : PY = P(Y ) On utilise la définition avec n = 2 et m = 3 :

PY = P(Y ) : p(y j ) = ∑ p(xi , y j ) P( X , Y )

n
j = 1, K, m Somme des éléments de chaque colonne de
i =1
→
X \Y 0 -1 1 PX
P( X , Y ) = 0 0.8p 0.2p 0 p
1 0 0.2(1-p) 0.8(1-p) 1-p
PY 0.8p 0.2 0.8(1-p)

On en déduit :
Distribution conditionnelle P(X Y ) On utilise la définition avec n = 2 et m = 3 :

P( X Y ) : p xi y j = ( ) p(px(y, y) )
i j
i = 1, K, n j = 1, K, m
j

→
X \Y 0 -1 1
P(X Y ) = 0
1
(0.8p / 0.8p)
p
(0.2p / 0.2)
0
(0 / 0.8(1-p))

1 (0 / 0.8p) (0.2(1-p) / 0.2) (0.8(1-p) / 0.8(1-p))

0 1-p 1

3. H X ( p ) . L’entropie de la source.
n=2
H X ( p ) = −∑ p( xi ) log 2 [ p( xi )] = − p log 2 ( p ) − (1 − p ) log 2 (1 − p )
i =1

TD 5 Corrigé. 3
Théorie de l’information TD 5 Corrigé. Modélisation mathématique d’un canal

4. H ( X Y ) . L’entropie conditionnelle de la source, sachant le symbole reçu.

On utilise la distribution conjointe P( X , Y ) et la distribution conditionnelle P( X Y ) :
 p(xi , y j )
H (X Y ) = −∑∑ p (xi , y j )log 2  [( )]
n = 2 m =3
 = −∑∑ p (xi , y j )log 2 p xi y j
n = 2 m =3

i =1 j =1  p ( y j )  i =1 j =1

→ H ( X Y ) = −0.8 p log 2 (1) − 0.2 p log 2 ( p ) − 0.2(1 − p ) log 2 (1 − p ) − 0.8(1 − p ) log 2 (1)
→ H (X Y ) = −0.2 p log 2 ( p ) − 0.2(1 − p ) log 2 (1 − p )
→ H ( X Y ) = 0.2 H X ( p )

( )
5. I ( X ; Y ) = H X ( p ) − H X Y = H X ( p ) − 0.2 H X ( p ) = 0.8 H X ( p )

6. C = max I ( X ; Y ) → C = max 0 .8 H X ( p )
PX p ∈ [0 , 1]

car la distribution d’une source binaire est complètement définie par la donnée de p.
Or, l’entropie d’une source binaire, H X ( p ) , atteint son maximum ( log 2 (2 ) ) pour p = 0.5 (équiprobabilité, distribution
uniforme):

→ C = max 0.8 H X ( p ) = 0 .8 H X ( p = 0.5 ) = 0.8 log 2 (2 ) = 0.8 bit/symbole.

p ∈ [0 , 1]

Partie II. Pour approfondir

Exercice 4. Nombre d’itérations d’un algorithme.

1. 4 cas possibles ( X 0 ∈ {1, 2, 3, 4}) :

X0 =1 : L’algorithme s’arrête tout de suite, sans entrer dans la boucle Tant que
→ N = 0 avec la probabilité 1 .
X0
X0 = 2 : X 0 est pair → ∀A0 , on a X 1 = = 1 et N = 1 puis l’algorithme s’arrête
2
→ N = 1 avec la probabilité 1 .
X0 = 3 : L’exemple est traité à la figure 2.
 N = 1 avec probabilité 1
 3
→ 
 N = 3 avec probabilité 2
 3
X0 = 4 : L’algorithme effectue 2 divisions par 2 indépendamment des valeurs aléatoires An
→ N = 2 avec la probabilité 1 .

→ On obtient la matrice de probabilités conditionnelles P (N X ) :

X \ N 0 1 2 3
P (N X ) = 1 1 0 0 0

2 0 1 0 0
3 0 1/3 0 2/3
4 0 0 1 0

TD 5 Corrigé. 4
Théorie de l’information TD 5 Corrigé. Modélisation mathématique d’un canal

2. Distribution marginale de X : PX = P( X ) :
X uniformément distribuée → PX (1) = PX (2 ) = PX (3) = PX (4) = 1
4

Distribution conjointe de X et N : P( X , N ) On utilise la définition avec n = 4 et m = 4 :

p(xi , N j ) = p(N j x i ) p( xi ) ( p( xi ) =
1
i = 1, K, n j = 1, K, m i = 1, K, n )
4
→
X \ N 0 1 2 3
P( X , N ) = 1 1/4 0 0 0
2 0 1/4 0 0
3 0 1/12 0 1/6
4 0 0 1/4 0

3. Distribution marginale de N : PN = P(N ) On utilise la définition avec n = 4 et m = 4 :

PN = P ( N ) : p(N j ) = ∑ p(xi , N j ) P( X , N )
n
j = 1, K, m Somme des éléments de chaque colonne de
i =1
→
X \ N 0 1 2 3 PX
P( X , N ) = 1 1/4 0 0 0 1/4
2 0 1/4 0 0 1/4
3 0 1/12 0 1/6 1/4
4 0 0 1/4 0 1/4
PN 1/4 1/3 1/4 1/6

4. A partir de la distribution marginale de N : PN = P ( N ) , on détermine E [N ] :

N 0 1 2 3
PN 1/4 1/3 1/4 1/6

E [N ] = 0 ⋅
1 1 1 1 4
→ + 1 ⋅ + 2 ⋅ + 3 ⋅ = itérations.
4 3 4 6 3
__________

TD 5 Corrigé. 5
Théorie de l’information TD 6 Corrigé. Codage de canal

TD 6 Corrigé. Codage de canal.

Codes linéaires correcteurs d’erreurs

Exercice 1. Code à répétition.

I. Expérience.

Manipulation (facultative)

1. Fichier [Link] : tauxErr = 0.1 : le décodage n’est pas parfait : des erreurs sont produites au décodage.
2. tauxErr = 0.05 : moins d’erreurs issues du décodage; tauxErr = 0.3 : davantage d’erreurs issues du décodage.

Interpétation

3. Lien entre la matrice de cumul d’erreurs et la possibilité de correction des erreurs ?

- Les mots-sources sont : 0 et1

- Les mots du code sont : ω1 = 000 et ω 2 = 111

On décode « 0 » par vote majoritaire si après transmission il y a 2 ou 3 « 0 » dans le mot reçu. Idem pour « 1 ».

Supposons que l’on envoie le mot-code « 000 » correspondant donc au mot source « 0 » à émettre. On a 4 cas
possibles d’erreurs de transmission :

0 erreur : on reçoit le mot m = 000 : on décode « 0 » par vote majoritaire (OK).

m = 100


1 erreur : on reçoit le mot ou m = 010 : on décode « 0 » par vote majoritaire (OK)
ou m = 001

→ 1 erreur est corrigée.
m = 101


2 erreurs : on reçoit le mot ou m = 110 : on décode « 1 » par vote majoritaire (au lieu de « 0 » !)
ou m = 011

→ 2 erreurs ne peuvent pas être corrigées.

3 erreurs : on reçoit le mot m = 111 : on décode « 1 » par vote majoritaire (au lieu de « 0 » !)
→ 3 erreurs ne peuvent pas être corrigées.
ici on ne se rend même pas compte qu’il y a eu des erreurs ! (unanimité du vote majoritaire)

Conclusion : le décodage est correct seulement s’il y a 0 ou 1 erreur sur les 3 transmissions.

II. Analyse.
ω1 = 000
1. Distance minimale du code : comme il n’y a que 2 mots-codes :  la distance minimale du code est :
ω 2 = 111
d = d h (000,111) = 3

Capacité de détection : on utilise la définition : ed = d − 1 = 2 → ed = 2 :

au maximum, il est toujours possible de détecter 2 erreurs.

 d − 1
Capacité de correction : on utilise la définition : ec = E  → ec = 1 :
 2 
au maximum, il est toujours possible de corriger 1 erreur.
On confirme l’observation (interprétation de l’expérience) où on a vu qu’1 erreur au maximum pouvait être corrigée.

TD 6 Corrigé. 1
Théorie de l’information TD 6 Corrigé. Codage de canal

2. Code linéaire ? Oui. On applique la définition :

Définition 6.15. Code correcteur linéaire (k, n). Un code linéaire (k, n) est un code de classe (k, n) tel que
l’application φ : Gk → Gn qui le génère est une application linéaire, c’est-à-dire, tel qu’il existe une matrice
G ∈ Μ n ,k (0,1) telle que :
 m1 
 
φ (m ) = Gm ∀m = M 
m 
 p

On appelle G la matrice génératrice du code. Elle est de dimension nxk .

Ici, on a :
k = 1 colonne : (dimension du code) taille des mots-sources ( m1 = 0, m2 = 1 ) (avant codage)
taille des mots-codes ( ω1 = [000] , ω 2 = [111] ) (après codage)
T T
n = 3 lignes : (longueur du code)
1
G = 1 = [1 1 1] : matrice génératrice (3x1).
T

1

ω1 = [000]T = φ (m1 ) = Gm1 = [1 1 1]T ⋅ 0

On a bien : 
ω 2 = [111]T = φ (m2 ) = Gm 2 = [1 1 1]T ⋅ 1

Exercice 2. Code linéaire.

1. G, matrice génératrice du code, est de dimension n x k = 8 x 4.

k = 4 colonnes : (dimension du code) taille des mots-sources (ou blocs d’origine) ( mi i = 1L l ) (avant codage)
n = 8 lignes : (longueur du code) taille des mots-codes ( ω i i = 1L p ) (après codage)

~  Ik   I k : matrice identité (k x k )
2. G sous forme systématique : G=  avec : 
 G′  G ′ : matrice (( n − k ) x k )
 
~
→ L’obtention de G implique un échelonnage de G suivant ses colonnes. Notons les c1 , c 2 , c3 , c 4 .

c1 c2 c3 c4
1 0 0 0
1 0 1
0  
  0 1 0 0
0 1 1
0 0
0 c1 ← c1 0 1 0
0 1
1 c ← c  
   2 ~ 0 0 0 1
→G=
2
0 0 1
0 Il suffit de réaliser les combinaisons linéaires  
G=
1 c3 ← c3 1 0 1 1
1 0 1
c 4 ← c1 + c 2 + c3 + c 4 0 1 1 1
0 1 1
1  
  1 1 0 1
1 1 0 1 1 1 1 0 
1 
 1 1 1

TD 6 Corrigé. 2
Théorie de l’information TD 6 Corrigé. Codage de canal

1 0 0 0
 
0 1 0 0
0 1 0 1 1
0 1 0  
  ~  I k 
 avec k = 4 et 0 1 1 1
~ 0 0 0 1 → G =   G′ = 
G =
 G′ 1 1 0 1
1 0 1 1    
1 1 1 0
0 1 1 1  
 
1 1 0 1
1 1 1 0 


3. Ensemble de mots de code (image C du code) ?

L’image du code donne les mots-codes ωi en balayant tous les mots-sources mi avec la relation : ω i = φ (mi ) = Gmi .
On peut obtenir également la même image du code sous forme systématique : ω i = φ (mi ) = Gmi .
~

Cette dernière relation présente l’avantage d’engendrer les mots-codes ωi avec les mots-sources mi pour préfixes :

[ ]
T

(~ )
T
 I    m 
ω iT = (Gmi )T = Gmi  = miT (G ′mi )T
T
=  k mi  =  i
 G ′    G ′mi 
~
G et G produisent la même image, mais les mots-codes générés ne correspondent pas aux mêmes mots-sources.

Avec le code construit sous forme systématique, on a donc :

~
[
ω i = φ (mi ) = Gmi , on a : ω iT = miT (G ′mi )T ] :

la partie préfixe d’un mot-code ωi est le mot-source mi

la partie suffixe d’un mot-code ωi est G ′mi :

 mi 1  + mi 4  mi 1 + mi 3
1 0 1 1   

 
Ici 0 1  . En notant  mi 2  les 4 bits d’un mot-source mi , le suffixe d’un mot-code ω i est donc :+ mi 4  mi + mi 3
G′ = 
1 1
m  G′mi =  2
1 + mi 4  m + mi 2

1 1 0
  i3   i1

1 0   mi   mi + mi
+ mi 3 
 1 1  4   1 2

Rappel : les sommes se font modulo 2. Table de code systématique (image C du code systématique ) :
# mot source mot-code distance, poids
d h (ω i ,0 ) = w(ω i )
[ ]
T

(~ )
T T
m  I    m 
ω iT = (Gmi )T = Gmi  = miT (G ′mi )T
i T
=  k mi  =  i
 G ′    G ′mi  (= nombre de bits 1 de ωi )
1 0000 0000 0000 0
2 1000 1000 1011 4
3 0100 0100 0111 4
4 0010 0010 1101 4
5 0001 0001 1110 4
6 1100 1100 1100 4
7 1010 1010 0110 4
8 1001 1001 0101 4
9 0101 0101 1001 4
10 0011 0011 0011 4
11 0110 0110 1010 4
12 1110 1110 0001 4
13 1101 1101 0010 4
14 1011 1011 1000 4
15 0111 0111 0100 4
16 1111 1111 1111 8
→d =4

TD 6 Corrigé. 3
Théorie de l’information TD 6 Corrigé. Codage de canal

4. Distance minimale du code :

La distance minimale d’un code linéaire est égale au plus petit poids non nul des mots de code → d = 4 .

Capacité de détection : ed = d − 1 → ed = 3 : au maximum, il est toujours possible de détecter 3 erreurs.

 d − 1
Capacité de correction : ec = E  → ec = 1 : au maximum, il est toujours possible de corriger 1 erreur.
 2 

5. Matrice de contrôle du code : d’après la définition de la matrice de contrôle H : H = (G ′ I n − k )

1 0 1 1
ici n x k = 8 x 4 → H = (G ′ I 4 ) avec 
0 1 1 1

G′ = 
1 1 0 1
 
1 1 1 0 

1 0 1 1 1 0 0 0
 
0 1 1 1 0 1 0 0
→ H =
1 1 0 1 0 0 1 0
 
1 1 1 0 0 0 0 1 

6. On reçoit les mots suivants. Sans utiliser la table de mots de code, comment savoir s’ils sont des mots-codes ?
m1 = (0001 0101)
T


m 2 = (0100 0111)
T


m3 = (0011 1010)
T

Pour savoir si un mot reçu m est un mot de code, on utilise la propriété de la matrice de contrôle : on calcule le
syndrome : S = Hm et on a : m ∈ C (C : image de code) ⇔ S = Hm = 0 :

H m1 m2 m3 S1 S 2 S 3
0 0 0
 
0 1 0
1 0 1 1 1 0 0 0 0 0 1 1 0 1
    
→ 0 1 1 1 0 1 0 01 0 1 0 0 0 calcul simultané des 3 syndromes
=
1 1 0 1 0 0 1 0   0 0 1   1 0 0
   
1 1   1 0   1 1 
 1 1 0 0 0 0 1 0
 
0 1 1
1 1 0 


→
S1 = Hm1 ≠ 0 ⇒ m1 ∉ C

S 2 = Hm 2 = 0 ⇒ m 2 ∈ C (une vérication consiste en l’examen de la table de code (image C du code) (ligne 3)

S 3 = Hm3 ≠ 0 ⇒ m3 ∉ C

7. En supposant qu’il y a eu au plus 1 erreur de transmission par mot, est-il possible de retrouver les mots de code
transmis ?

La capacité de correction étant ec = 1 → oui : au maximum, il est toujours possible de corriger 1 erreur par mot.

TD 6 Corrigé. 4
Théorie de l’information TD 6 Corrigé. Codage de canal

A titre d’exemple, considérons les 3 cas :

m 2 = (0100 0111)
T


m1 = (0001 0101)
T


m3 = (0011 1010)
T

m 2 = (0100 0111)
T

m2 est un mot-code ( S2 = Hm2 = 0 ⇒ m2 ∈ C ), il sera décodé directement et par son préfixe: (0100 ) (table C ligne 3).
T
Comme
En outre, comme il est supposé qu’il y a au plus 1 erreur, alors m 2 est sans erreur, car la distance minimale du code
est 4; cela veut dire qu’il faut au minimum 4 erreurs pour transformer un mot du code en un autre mot du code.

m1 = (0001 0101)
T

Comme m1 n’est pas un mot-code ( S1 = Hm1 ≠ 0 = (1011)T ⇒ m1 ∉ C ), on sait qu’il y a erreur de transmission.

Décodage & Correction : méthode du syndrome

e1 le vecteur erreur défini par m1 = ω1 + e1 avec ω1 ∈ C ( ω1 issu de la correction de m1 et tel que Hω1 = 0 ).
Soit
⇒ S1 = Hm1 = Hω1 + He1 = He1 : l’erreur e1 a le même syndrome que m1 !
e1 est de la forme : e1 = (0 L 010 L 0 ) , où le
T
En outre, comme il est supposé qu’il y a au plus 1 erreur, le vecteur
bit 1 se trouve à la i-ème position sur 8 bits.
→ He1 = ci où ci représente la i-ème colonne de la matrice H .
→ s’il y a 1 seule erreur, au i-ème bit, on doit avoir : ci = He1 = Hm1 = S1
H doit être égale au syndrome S1 == (1011) .
T
→ 1 des colonnes de la matrice

On constate en effet que la colonne c1 de H est égale au syndrome S1 : c1 = S1

e1 = (10 L 0 ) et le mot-code est :
T
→ le vecteur erreur est
ω1 = m1 + e1 = (0001 0101)T + (1000 0000)T = (1001 0101)T
→ on décode ω1 (comme préfixe de ω1 ou par la table de code C, ligne 8) et on trouve le mot-source (1001)T .
Autre méthode de Décodage & Correction : méthode de décodage au sens de minimum de distance de Hamming

Le mot reçu m1 est corrigé en un mot-code ωi de sorte que la distance de Hamming d H (m1 , ωi ) soit minimale :
Table de code systématique (image C du code systématique ) :
ωiT d H (m1 , ωi ) m1 = (0001 0101)
#
mot source miT mot-code distance de Hamming avec
T

1 0000 0000 0000 3

2 1000 1000 1011 5
3 0100 0100 0111 3
4 0010 0010 1101 3
5 0001 0001 1110 3
6 1100 1100 1100 5
7 1010 1010 0110 5
8 1001 1001 0101 1
9 0101 0101 1001 3
10 0011 0011 0011 3
11 0110 0110 1010 7
12 1110 1110 0001 5
13 1101 1101 0010 5
14 1011 1011 1000 5
15 0111 0111 0100 3
16 1111 1111 1111 5

Le mot-code #8 est à la distance minimale (1) de m1 → m1 corrigé = ω1 = (1001 0101)T → mot-source (décodage) : (1001)T .

TD 6 Corrigé. 5
Théorie de l’information TD 6 Corrigé. Codage de canal

m3 = (0011 1010)
T

Comme m3 n’est pas un mot-code ( S3 = Hm3 ≠ 0 = (1001)T ⇒ m3 ∉ C ), on sait qu’il y a erreur de transmission.

Décodage & Correction : méthode du syndrome

Soite3 le vecteur erreur défini par m3 = ω 3 + e3 avec ω3 ∈ C ( ω 3 issu de la correction de m3 et tel que Hω3 = 0 ).
⇒ S 3 = Hm3 = Hω 3 + He3 = He3 : l’erreur e3 a le même syndrome que m3 !
En outre, comme il est supposé qu’il y a au plus 1 erreur, le vecteur e3 est de la forme : e3 = (0 L 010L 0 ) , où le bit 1 se trouve à la i-ème
T

position sur 8 bits.

→ He3 = ci où ci représente la i-ème colonne de la matrice H .
→ s’il y a 1 seule erreur, au i-ème bit, on doit avoir : ci = He3 = Hm3 = S 3

→ 1 des colonnes de la matrice H doit être égale au syndrome S3 = (1001)T .

On constate qu’aucune colonne de H n’est égale au syndrome S 3 → il y a donc 2 erreurs ou plus !

La capacité de correction étant ec = 1 → au maximum, il est toujours possible de corriger 1 erreur par mot.
→ la correction à coup sûr de plus d’1 erreur n’est pas possible.

Pour néanmoins essayer de trouver les erreurs, on ne peut que tester des hypothèses de 2, 3, 4 … erreurs.

• Par exemple, à partir de l’hypothèse de 2 erreurs, il doit donc exister i ≠ j tel que ci + c j = He3 = Hm3 = S 3
→ plusieurs vecteurs erreurs e3 candidats ( e3 non unique) → après correction, plusieurs mots-codes ω 3 ∈ C candidats :
♦ c5 + c8 = (1000) + (0001) = (1001)T → e3 = (0000 1001)T → ω3 = m3 + e3 = (0011 1010)T + (0000 1001)T = (0011 0011)T (C ligne 10)
T T

♦ c1 + c7 = (1011)T + (0010)T = (1001)T → e3 = (1000 0010)T → ω3 = m3 + e3 = (00111010)T + (1000 0010)T = (1011 1000)T (C ligne 14)
♦ c3 + c6 = (1101)T + (0100)T = (1001)T → e3 = (0010 0100)T → ω3 = m3 + e3 = (00111010)T + (0010 0100)T = (00011110)T (C ligne 5)

Rappel : La capacité de correction étant ec = 1 → au maximum, il est toujours possible de corriger 1 erreur par mot.
→ la correction à coup sûr de plus d’1 erreur n’est pas possible → on peut ne pas pouvoir corriger.

__________

TD 6 Corrigé. 6