Théorie d’information et codage de canal

Codes correcteurs d’erreurs

(1ère partie)
Codes linéaires en blocs
-Codes groupe-

Pr. A. AIT MADI

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 1
 Plan

Introduction
Classification des codes correcteurs d’erreurs
Deuxième théorème de Shannon
Codes linéaires en blocs
Capacité de détection et de correction

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 2
 Plan
Matrice génératrice et codage
Matrice génératrice, forme systématique
Matrice de contrôle de parité
Équations de contrôle de parité
Détection des erreurs par syndrome
Code de Hamming
Code de Hamming, matrice de contrôle
Code de Hamming, circuit de codage
Code de Hamming, circuit de décodage
RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 3
 Introduction

 La transmissions d'informations, via un canal qui n’est pas fiable, peut-être

sujet à des perturbations. Voici quelques applications touchées par ces
perturbations :

• Les téléphones cellulaires sont mobiles, relativement peu puissants, et

souvent utilisés soit loin des antennes relais, soit dans un environnement
urbain très bruyant du point de vue électromagnétique

• les images disque qui doivent être capable de restituer exactement le

contenu à l’original
• Le réseau Internet (paquets IP)

 Eliminer l’impact des perturbations sur la transmission  codage de

canal (usage des codes détecteurs ou/et correcteurs d ’erreurs)

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 4
 Introduction

 Il existe trois techniques de protection contre les erreurs de transmission

• ARQ (Automatic Repeat Request) : correction des erreurs par

retransmission. Comme application : protocole HDLC, X25…

• FEC (Forward Error Correction) : détection et correction des erreurs à la

réception. Comme application : DVB-S, DVB-S2, WIFI, GSM, UMTS…

• Hybride: Lorsque le code détecte une erreur, il essaie tout d’abord de

corriger les erreurs, si cela est possible, sinon l’émetteur recommencera
d’émettre

 Dans la suite de ce cours nous allons nous intéresser uniquement à

l’étude des FEC dans le cas des codes linéaires en bloc : cas des codes
groupe

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 5
 Introduction

 Exemple: code à répétition

• Codage :
 Pour un bit d’information, 3 bits sont envoyés tels que
0  000
1  111
• Décodage :

 Le décodage se fait par vote majoritaire. Par exemple, si le mot reçu est
001, alors on déduit que le bit émis était 0

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 6
 Classification des codes correcteurs d’erreurs

 On distingue deux classes de codes correcteurs d’erreurs :

• Les codes en blocs :
 Ils traitent chaque bloc d’information de k symbole
indépendamment les uns des autres. Chaque mot de code de n
symboles est indépendant des autres mots de code.
 Il existe deux types:
o Codes groupe : les mots sont considérés comme des éléments
d’un espace vectoriel, à savoir des vecteurs.

o Codes cycliques : les mots sont considérés comme des éléments

dans une algèbre, à savoir des polynômes. Ils sont aussi appelés
codes polynomiaux.

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 7
 Classification des codes correcteurs d’erreurs

• les codes convolutifs :

 Traitement effectué de manière continue, c.-à-d. un signe après un
autre
 La sortie d’un codeur convolutif dépend de :
o l’information courante à coder
o l’information précédente (effet de mémoire) et l’état du codeur.

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 8
 Deuxième théorème de Shannon

pour une source à débit d’information R [bits/s] et un canal de

capacité C [bits/s], si R<C il existe un code ayant des mots
d’une longueur n telle que la probabilité d’erreur après
décodage tend vers 0.

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 9
 Codes linéaires en blocs

 Principe de codage
• Le message issu de la source est découpé en bloc de même taille, k
symboles (codage en bloc), et un même algorithme de codage est
appliqué sur chaque bloc pour obtenir des mots code de n symboles :

 Soit on ajoute des (n-k) symboles de contrôle (symboles de

redondance) à la fin ou au début des différents k symboles

 Soit modifier complétement les blocs mais on évite que deux blocs
différents de k symbles soient transformés en un même bloc de n
symboles

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 10
 Codes linéaires en blocs
• Exemple:

 formation des mots code de n symboles par ajout des n-k symboles de
redondance à la fin des k symboles d’entrée

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 11
 Codes linéaires en blocs
Les symboles de la source et les mots code sont des symboles q-aires. Si
q=2, on parle des codes en blocs binaires. Sinon on parle des codes en blocs
non-binaires. Dans la suite, nous nous intéressons aux codes binaires.
Dans le cas des codes binaires, un mot code est considéré comme un vecteur
de n composantes appartenant à l’alphabet binaire {0,1}. Les mots de
longueur n sont des éléments de {0,1}n.
Chacun des 2k blocs de k symboles correspond de manière unique à un des
mots code de n bits
Un encodage est une application injective (tout élément de l’ensemble
d’arrivée a au plus un antécédent dans l’ensemble d’arrivée)

 :0,1k  0,1n
k est appelé la dimension du code
n est appelé la longueur de code

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 12
 Codes linéaires en blocs
L’ensemble des éléments de C={(X), X{0,1}k } sont appelés les mots code
du code C

Le code C est linéaire ( est application linéaire) si les 2k mots code
possibles forment un sous espace vectoriel de l’espace vectoriel GF(2)n=
{0,1}n , GF (Galois Field) : corps de Galois. Comme conséquence:

La somme modulo 2 de deux mots code est un mot code ( ou exclusif)

Le produit modulo 2 de deux mots code est un mot code (ET logique)

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 13
 Codes linéaires en blocs

Distance de Hamming

•La distance de Hamming, dans le cas binaire, entre deux vecteurs x et y de

dimension n correspond au nombre de composantes différentes entre ces
deux vecteurs
d H  X , Y   i : xi  yi ,0  i  n
|.| : Les deux barres verticales désigne le cardinal

•La distance minimale de Hamming d’un code C, dmin, est définie comme la
distance minimum entre toutes les paires de mots code du code C
d min C   min d H  X , Y 
 X ,Y C
X Y
•Exemple : pour le code de répétition de longueur 3 bits, la distance (aussi
minimale) de Hamming entre les mots code (000) et (111) est 3

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 14
 Codes linéaires en blocs

Les paramètres d’un code

•Un code linéaire en bloc sera noté

Cn, k , d min 
Pour designer un code en bloc de longueur n, qui code k bits et possède une
distance minimale de Hamming dmin
Le taux (rendement) d’un code est donné par
k
r
n
Si le nombre de bits de contrôle appliqué, à un bloc de message
d’information, croit, le rendement diminue
Plus, il est proche de zéro, meilleure est la protection contre les erreurs de
transmission

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 15
 Capacité de détection et de correction

 Pour détecter e erreurs pouvant intervenir dans une position quelconque

du mot, la distance minimale entre les mots code doit être
d min  e  1
 Pour corriger e erreurs pouvant intervenir dans une position quelconque,
la distance minimale doit être
d min  2e  1
 La capacité (pouvoir) de correction d’un code est le nombre d’erreurs
maximale corrigeable par ce code, elle sera définie par
 d min  1 
e  Ent  
 2 

 Exemple: pour le code de répétition de longueur 3 bits, la distance

minimale Hamming entre les mots code (000) et (111) est 3. Ce code peut
détecter (3-1=2) erreurs et corrige (3-1)/2=1 erreur

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 16
 Matrice génératrice et codage
 Pour un code en bloc linéaire C[n, k, dmin], il existe k mots, g0, g1,…gk-1,
linéairement indépendants considérés comme la base du sous espace
vectoriel GF(2)k
 Chaque mot U=(u0,u1,…un-1) appartenant au code C est une combinaison
linéaire de la base, ainsi U, pour une entrée du codeur X =(x0,x1,…xk-1),
s’écrit
U  x0  g0  x1  g1  ...  xk 1  g k 1
 : désigne la multiplication modulo 2
 : désigne l’addition modulo 2

 Les vecteurs de la base, g0, g1,…gk-1, du sous espace vectoriel GF(2)k sont disposés
comme des lignes d’une matrice, appelée la matrice génératrice du code définie par :

 g 0   g 0, 0 g 0,1  g 0,n1 
 
G           
 g k 1   g k 1,0 g k 1,1  g k 1,n 1 
RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 17
 Matrice génératrice et codage

 Chaque mot code peut être généré par la multiplication du bloc de k bits à
l’entrée par la matrice génératrice G  opération de codage

 Si X= (x0,x1,…xk-1) est l’entrée du codeur et le mot code U=(u0,u1,…un-1)

sa sortie alors
 g0 
U  X  G  u0 , u1 ,un 1       x0  g 0  x1  g1  ...  xk 1  g k 1
 g k 1 
 Exemple: on considère la matrice génératrice G de taille 4x7 suivante

 g 0  1 1 0 1 0 0 0
 g  0 1 1 0 1 0 0
G   1  
 g 2  1 1 1 0 0 1 0
   
 g 3  1 0 1 0 0 0 1

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 18
 Matrice génératrice et codage

• On cherche à déterminer les mots code qui correspondent à 24 vecteurs

possibles à l’entrée.

• Comme exemple on détermine le mot code qui correspond au vecteur

X= (1,0,0,1).
U  X  G  1  g 0  0  g1  0  g 2  1  g3
 1,1,0,1,0,0,0  1,0,1,0,0,0,1  0,1,1,1,0,0,1
• Par la même méthode, on donne tous les mots code possibles sur le tableau
suivant :

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 19
Matrice génératrice et codage

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 20
 Matrice génératrice, forme systématique

 D’après le tableau précédent , on remarque que les 4 dernières bits sont ceux
du vecteur X d’information et les 3 premiers sont les bits de contrôle.
Cette forme particulière du code linéaire en bloc est appelé forme
systématique

 L’opération de correction des erreurs est simple

 L’opération de séparation des bits d’information lors du décodage est

facile

 La structure du mot code sous sa forme systématique est donné par la figure
suivante. Les n-k bits de contrôle et les k bits du vecteur d’entrée sont
placés respectivement au début et à la fin du mot code

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 21
 Matrice génératrice, forme systématique

 La matrice génératrice G du code linéaire en bloc sous une forme

systématique est donnée par :
 p0,0 p0,1  p0,n  k 1 1 0 0  0
 p 0 1 0  0
G  Pk n  k  , I k   
1, 0 p1,1  p1,n  k 1
         
 
 pk 1,0 pk 1,1  pk 1,n  k 1 0 0 0  1

Pkx(n-k) : matrice de parité de dimension kx(n-k)

Ik : sous matrice identité de dimension kxk

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 22
 Matrice génératrice, forme systématique

 Les relations qui lient les n bits du mot code U, les k bits du vecteur X d’entrée et
ceux des n-k bits de contrôle sont données par :
• Les k bits du vecteur d’entrée
unk i  xi i  0,1,, k  1
• Les n-k bits de contrôle
u j  x0  p0, j  x1  p1, j   xk 1  pk 1, j j  0,1,, n  k  1
• Ainsi chaque mot code peut s’écrire sous sa forme systématique comme suit

U  u0 , u1 ,, un1  u0 , u1 ,unk 1 , x0 , x1 , xk 1 

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 23
 Matrice de contrôle de parité
 La matrice de contrôle de parité H générée à partir de la matrice génératrice G est
donnée par :
 h0 
 h 
 
H  I n  k , P T n  k k   1 
  
 
hn  k 1 
1 0  0 p0 , 0 p1, 0 p2 , 0  pk 1, 0 
0 1  0 p0,1 p1,1 p2,1  pk 1,1 
 
         
 
0 0  1 p0,n  k 1 p1,n  k 1 p2,n  k 1  pk 1,n  k 1 
PT (n-k) xk : sous matrice, transposée de Pkx(n-k), de dimension (n-k)xk
In-k : sous matrice identité de dimension (n-k)x(n-k)
 Si on multiplie la matrice G par la matrice transposée de H, on obtient :
G HT  0
RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 24
 Equations de contrôle de parité

 Ces équations vérifient la validité d’un mot code

 Il peuvent servir comme moyen pour détecter la présence des erreurs de
transmission

 Les équations de contrôle de parité sont définies par :


U  HT  X  G HT  0 
 Pour chaque ligne de la matrice H on a une équation de contrôle de parité, on peut
écrire :

ui  x0  p0,i  x1  p1,i    xk 1  pk 1,i  0 0  i  n  k 1

ui  x0  p0,i  x1  p1,i    xk 1  pk 1,i 0  i  n  k 1

 Exemple :
• On considère la matrice de contrôle de parité et son transposé suivantes :

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 25
 Equations de contrôle de parité
• La matrice génératrice G du code C(7,4) est donné par :

1 1 0 1 0 0 0
0 1 1 0 1 0 0
G
1 1 1 0 0 1 0
 
1 0 1 0 0 0 1

• La matrice de contrôle de parité H et son transposé sont données par

1 0 0
0 1 0

1 0 0 1 0 1 1 0 0 1
   
H  0 1 0 1 1 1 0  H  1
T
1 0
0 0 1 0 1 1 1 0 1 1
 
1 1 1
1 0 1

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 26
 Equations de contrôle de parité

• Le vecteur d’entrée se présente sous la forme X= (x0,x1, x2, x3), le mot code sera
U= (u0, u1, u2, u3, u4, u5, u6)=(u0, u1, u2,x0,x1, x2, x3) les trois équations de contrôle de
parité devraient vérifier :
1 0 0
0 1 0

0 0 1
 
U  H T  u0 , u1 , u2 , x0 , x1 , x2 , x3   1 1 0  0
0 1 1
 
1 1 1
1 0 1
u0  x0  x2  x3 
u1  x0  x1  x2
u2  x1  x2  x3

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 27
 Détection des erreurs par syndrome

 Les mots code sont censés être transmis via un canal de transmission vulnérable aux
bruits, par conséquent les messages reçus peuvent être entachés d’erreurs de
transmission
 Dans le cas d’un modèle de canal AWGN (Additif White Gaussian Noise)

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 28
 Détection des erreurs par syndrome

 Une erreur est détectée sur la position ou une composante du vecteur E est non nulle.

 Le mécanisme de détection des erreurs par la technique du syndrome peut être

résumé par l’expression suivante :

Sr  Y  H T   X  E   H T  E  H T  S0 , S1 ,, Snk 1 

 Le vecteur Sr s’appelle le vecteur du syndrome. Il ne dépend que du vecteur de la
pattern d’erreurs E.

 Si le vecteur du syndrome est nul, le mot reçu est un mot code, sinon le message
reçu est entaché d’une ou plusieurs erreurs de transmission

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 29
 Code de Hamming

 Permet de corriger seulement une seule erreur

 Si le syndrome code directement la position de l'erreur, il pourrait alors représenter:

2n-k -1 positions.

 Aucune place n'est donc perdue si le nombre total de positions à représenter (c.-à-d. la
longueur n du mot de code) est n=2n-k -1

 Voici quelques tailles possibles pour ces codes :

n k n-k
7 4 3
15 11 4
31 26 5
63 57 6
 

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 30
 Code de Hamming, matrice de contrôle

 Le code de Hamming est caractérisé par une matrice de contrôle H où la colonne hi

est la représentation binaire du nombre i
0 0 0  1
0 0 0  1

    
H  h1 , h2 , , hn    
0 0 0  1
0 1 1  1
 
1 0 1  1
 Matrice de contrôle pour un code de Hamming (7,4) (n-k=3) et n=15 (n-k=4)

0 0 0 1 1 1 1
H 3  0 1 1 0 0 1 1
1 0 1 0 1 0 1

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 31
 Code de Hamming, matrice de contrôle

 Matrice de contrôle pour un code de Hamming (15,11) (n-k=4)

0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
H4  
0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
 
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 32
 Code de Hamming, circuit de codage
 Considérons toujours le code C(7,4) de matrice de contrôle H3
 Le vecteur d’information d’entrée est :
X  x0 , x1 , x2 , x3 
 Les symboles de contrôle seront placés dans les positions 20, 21, 22
 Ce qui donne le mot code suivant
U  c0 , c1 , x0 , c2 , x1 , x2 , x3 
 Les 3 équations de contrôle de parité donne les 3 symboles de contrôle c0, c1 et c2
0 0 1
0 1 0

0 1 1
 
U  H T  c0 , c1 , x0 , c2 , x1 , x2 , x3   1 0 0  0
1 0 1
 
1 1 0
1 1 1

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 33
 Code de Hamming, circuit de codage

c0  x0  x1  x3  Pour un vecteur X d’entrée tel que (x0 , x1, x2, x3 ) = (0,0,1,1),

les bits de contrôle seront : (c0 , c1, c2) =(1,0,0).
c1  x0  x2  x3  Le mot code U sera (c0 , c1, x0 , c2 , x1, x2, x3 )=(1,0,0,0,0,1,1)
c2  x1  x2  x3

 Le circuit de codage sera donné comme suit

c0 c1 c2
U

RD
x0 x1 x2 x3

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 34
 Code de Hamming, circuit de codage

 Les symboles de contrôle sont calculés par des additionneurs modulo 2

 Après la formation du mot code, les entrées du registre à décalage RD seront
bloquées
 Le contenu apparait à la sortie sous la forme de succession d’impulsions (au rythme
d’une horloge) représentant le mot code

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 35
 Code de Hamming, circuit de décodage
 Après émission du mot code U, on reçoit le mot Û tel que
Uˆ  c0r , c1r , x0 r , c2 r , x1r , x2r , x3r 
 Le calcul du vecteur du syndrome est effectué comme suit
S 0  c2 r  x1r  x2 r  x3r
S1  c1r  x0 r  x2 r  x3r
S 2  c0 r  x0 r  x1r  x3r
 La valeur en décimale du syndrome permet de localiser facilement la position de
l’erreur (la valeur du syndrome =position de l’erreur)
 Pour le vecteur X précédent tel que (x0 , x1, x2, x3 ) = (0,0,1,1), Le mot code U était
(c0 , c1, x0 , c2 , x1, x2, x3 )=(1,0,0,0,0,1,1)
 On introduit une erreur (changer 0 par 1) sur la position 4, le mot reçu sera
(c0r , c1r , x0r , , x1r , x2r , x3r )=(1,0,0, ,0,1,1)
 Le calcul du syndrome donne (S0 ,S1 ,S2)=(1,0,0)= 4
 Pour corriger l’erreur on additionne (modulo 2) (0,0,0,1,0,0,0) au mot reçu
(1,0,0, ,0,1,1), ce qui donne (1,0,0,0,0,1,1)

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 36
 Code de Hamming, circuit de décodage
 Le circuit de décodage est donné comme suit :

S2

S1

S0

Û x3r U
c0r c1r x0r c2r x1r x2r

LUT

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 37
RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 38