UNIVERSITE LARBI BEN M’HIDI OUM EL BOUAGHI

INSTITUT DES SCIENCES ET DES TECHNIQUES APPLIQUEES

DEPARTEMENT RESEAUX ET TELECOMMUNICATIONS

Module : codage et compression RT M1

TD N 3&4

Exercice 1

Soit un code linéaire sur F2 dont la matrice génératrice est donnée ci-dessous
1 0 1 0 1
G 
0 1 1 1 1
1. Trouvez la longueur des blocs du message (source), la longueur des mots de code et le nombre de bits de
parité

2. En déduire la matrice de contrôle H

3. trouvez les mots de code

4. En déduire la distance minimale, le nombre d’erreurs que ce code peut détecter et peut corriger.

Solution Exercice 1

1. On voit bien que la matrice génératrice G est déjà sous forme systématique (sous sa forme normale), c'est-à-
dire composée de deux partie :
 une première partie est une matrice identité de taille 22 donc k=2 (la taille du bloc de donnée du message initial)
 et la deuxième partie représente les bits de parité de taille 23 correspondant à k(n-k) ce qui nous donne n=5 la
taille d’un mot de code.

Il s’agit donc d’un code en bloc linéaire (5,2). n=5 et k=2

2. La matrice de contrôle de parité H peut être déduite à partir de la matrice génératrice

 
G  Ik P  
H  P t I nk 
1 1 1 0 0
1 0 1 0 1 H  0 1 0 1 0
G   1 1 0 0 1
0 1 1 1 1
3. Comme les blocs du message original ont une taille k=2, nous aurons alors 4 possibilités soit D={(0,0),
(0,1), (1,0) et (1,1)} (où D désigne la donnée) pour chacun de ces blocs messages le codeur nous donnera un
mot de code CD. Il suffit de faire le produit : CD=DG

D : Donnée CD : Mot de code

00 00000

01 01111

10 10101

11 11010
 UNIVERSITE LARBI BEN M’HIDI OUM EL BOUAGHI
INSTITUT DES SCIENCES ET DES TECHNIQUES APPLIQUEES
DEPARTEMENT RESEAUX ET TELECOMMUNICATIONS

Module : codage et compression RT M1

4) dmin=3  ce code peut détecter deux erreurs (e=dmin-1) et il peut corriger une seule erreur ( ).

Exercice 2

101100
 
Un code linéaire a pour matrice de contrôle H   1 1 0 0 1 0 
 010001
 

a. Préciser la longueur n des mots de code et la longueur k des mots d'information.

b. En déduire la matrice génératrice normale de ce code

c. Les données suivantes sont-elles des mots du code ?

o C1 = (1 1 1 0 1 1)

o C2 = (1 0 0 1 1 0)

d. Donner la matrice génératrice du code et le codage de chaque mot d'information.

Solution exercice 5

Rappel : H est matrice de contrôle de parité du code linéaire permettant de définir les n-k bits de contrôle en fonction
des bits d’information et du transposé du vecteur CD formé des bits codés.

 
G  Ik P  
H  P t I nk 
n c’est la taille du code, k la taille de la donnée du message (source) et n-k c’est la taille des bits de contrôle qu’on a
rajouté dans le code

a)- Dans notre cas et selon la matrice de contrôle proposée, on déduit que n-k=3, correspondant à la matrice identité,
n=6 et donc k=3

1 0 1 1 1 0
 
b)- G  0 1 0 0 1 1 
 0 0 1 1 0 0
 

c)- Rappel : un mot codé CD a été généré par la matrice génératrice G si et seulement si HCDt = 0.

101100
 
H  1 1 0 01 0
 010001
 

 Pour premier mot de code C1 = (1 1 1 0 1 1), , nous aurons

HC1T=010, le résultat n’est pas nul donc C1 n’est pas un mot de code l’erreur est dans la position 2 (1 1 1 0 1
1)
 Pour le deuxième mot de code C2 = (1 0 0 1 1 0), nous aurons
 UNIVERSITE LARBI BEN M’HIDI OUM EL BOUAGHI
INSTITUT DES SCIENCES ET DES TECHNIQUES APPLIQUEES
DEPARTEMENT RESEAUX ET TELECOMMUNICATIONS

Module : codage et compression RT M1

HC1T=000, donc C2 est un mot de code

Exercice 3

On Suppose que la matrice des coefficients DCT pour un bloc d’image 4x4 est donné ce dessous (dctblock).

a. Essayez de quantifier ses coefficients DCT en utilisant la matrice quantification Q.

 1.3676 - 0.0500 - 0.0466 0.0912 

 0.0134 - 0.0033 0.0877 0.0071 
dctblock  1.0e  003 *  ,
 - 0.0086 - 0.0207 0.0036 0.0019 
 
 - 0.0046 0.0086 0.0044 0.0085 

 16 10 24 51 
 14 16 40 69 
Q ,
 18 37 68 103 
 
 49 78 103 120 

85 − 5 − 2 2
⎡10 0 2 0⎤
⎢ ⎥
𝑚𝑞𝑢𝑎𝑛𝑡𝑖𝑓𝑖é𝑒 = ⎢ 0 1 0 0⎥
⎢0 0 0 0⎥
⎣ ⎦

b. Déterminez la suite des symbols obtenus après le balayage en zig-zag

85 − 5 10 0 0 − 2 2 2 1 0 0 0 0 0 0 0

c. Appliquer le codage RLE.

85 − 5 10 2(0) − 2 2 2 1 7

d. Essayez de donner le bitstream complet après le codage de Huffman

p(85)=1/10 ; p(-5)=1/10 ; p(-2)=1/10 ; p(2)=2/10 ; p(10)=1/10 ; p(0)=2/10 ; p(1)=1/10; p(7)=1/10

0(01) ; 2(011) ; 85(110) ; -5(111) ; 10(100) ; -2(101) ; 1(0000) ; 7(0001)

110 111 100 01 01 101 011 011 0000 0001