THEORIE DE L’INFORMATION & CODAGE
Introduction aux codes correcteurs d’erreurs
ABDI.M –ENSTTIC-Oran
CODES DETECTEURS/CORRECTEURS D’ERREURS :
Définition : Un code correcteur est une technique de codage basée sur la redondance. Elle est
destinée à corriger les erreurs de transmission d’un message sur une voie de communication
peu fiable.
Remarque : La théorie des codes correcteurs ne se limite pas qu’aux communications
classiques (radio, câble coaxial, fibre optique, etc.) mais également aux supports de stockage
d’information comme les disques compacts, la mémoire RAM et d’autres applications où
l’intégrité des données est importante.
Selon sa construction et sa puissance, un code peut être utilisé en auto-correction
(FEC), ou en correction par retransmission (ARQ)
1. Classification des codes : Voici deux grandes familles de codes :
Les codes en blocs (linéaires, cycliques) : le codage/décodage d’un bloc dépend
uniquement de l’information de ce bloc.
Les codes en treillis (convolutifs, récursifs ou non) : le codage/décodage d’un bloc
dépend des informations d’autres blocs(généralement de blocs précédemment
transmis)
2. Principe du codage en blocs : Après avoir découpé l’information en blocs
de k bit, on applique un même algorithme à chaque bloc d’information en rajoutant
m bits de contrôle à la fin de chaque bloc, un obtient ainsi des séquences codées
(mots-code) de longueur n=k+m
1
THEORIE DE L’INFORMATION & CODAGE
Introduction aux codes correcteurs d’erreurs
ABDI.M –ENSTTIC-Oran
3. Principe du codage en treillis:
Principe : Chaque bloc de n bits de sortie (séquence codée) dépend des m blocs de k bits
d’information précédents
k bits
Séquence-information … i-4 i-3 i-2 i-1 i i+1 i+2 …
n > k
Séquences-codées … i-2 i-1 i i+1 i+2 …
n bits
Exemple : le bloc de sortie « i-1 », est construit sur la base des blocs informations
« i-4 », « i-3 », « i-2 » et « i-1 »,
4. Exemple du Codage en blocs :
Exemple : si k=2 et n= 3 avec n=k+m
n=3 : la longueur des mots-codes
k=2 : la dimension du code (nombres de bits d’information dans un mot-code)
m=1 : la redondance
Soit la séquence d’information à coder :
100011100010010111011110001010010111
Il y a 2k = 22= 4 symboles différents possibles, qui sont : 00, 01, 10, 11
Si le bit redondant rajouté, est un bit de parité paire, le codage se fera sur la base du tableau
suivant :
Bits Bit Mots-code
d’information redondant
00 0 000
01 1 011
10 1 101
11 0 110
Donc la séquence sera codée comme suit :
La séquence codée à transmettre est la suivante :
2
THEORIE DE L’INFORMATION & CODAGE
Introduction aux codes correcteurs d’erreurs
ABDI.M –ENSTTIC-Oran
DÉFINITIONS :
On note :
F2= {0,1} : l’alphabet binaire
: L’ensemble des mots de longueur k
: L’ensemble des mots de longueur n
Exemple :
Définition1 (codes en bloc (n,k))
Un code est une application injective
Le paramètre k est appelé la dimension du code C et le paramètre n est appelé la longueur du
mot code : on dit que C est un code de paramètres (k,n).
: est appelé taux de codage ( ou taux d’information), il peut être interprété comme la
quantité d’information par bit transmis .
Remarques :
Il y a 2k séquences d’information de longueur k
Il y a 2n séquences codées de longueur n
2k Codage
mots-info 2n
mots-code
(longueur = k) ( longueur = n)
2K
2k
mots-codes
possibles
5. Notion de distance minimale d’un code :
Le codage étant une opération qui nous permet à l’aide de la redondance ajoutée,
de choisir nos 2k mots-code dans un espace qui contient 2n mots-codes
possibles, qui est plus grand que l’espace de départ (qui n’en contient que 2k)
Cette opportunité de choix plus vaste doit être exploitée, pour nous permettre de
faire le meilleur choix possible du code. L’un des paramètres essentiel du choix
d’un bon code, c’est sa distance minimale do.
Définition2 (Poids et distance de Hamming )
La distance de Hamming ( notée d(c,c’) ) entre deux mots-code,
, et
avec :
Le poids (noté p (c ) ) d’un mot code , est sa distance à
l’origine , donc :
3
THEORIE DE L’INFORMATION & CODAGE
Introduction aux codes correcteurs d’erreurs
ABDI.M –ENSTTIC-Oran
Exemple :
la distance de Hamming entre 100110111 et 101100010 est 4
1 0 0 1 1 0 1 1 1
1 0 1 1 0 0 0 1 0
0 0 1 0 1 0 1 0 1
Le poids du mot 100110111 est 6
1 0 0 1 1 0 1 1 1
0 0 0 0 0 0 0 0 0
1 0 0 1 1 0 1 1 1
Définition3 (distance minimale d’un code C )
La distance minimale d’un code C, dont les mots code sont c1,c2,…,ci,…,cm ,est égale à
Exemple :
Si un code est composé des quatre mots code suivant :
c1= 0000 c2= 0110 c3=1010 c4=1111
Les distances de Hamming entre les différents mots sont
d(c1 , c2 ) =2 d(c1 , c3 ) =2 d(c1 , c4 ) =4
d(c2 , c1 ) =2 d(c2 , c3 ) =3 d(c2 , c4 ) =2
d(c3 , c1 ) =2 d(c3 , c2 ) =3 d(c3 , c4 ) =2
d(c4 , c1 ) =4 d(c4 , c2 ) =2 d(c4 , c3 ) =2
La distance minimale est donc égale à :
Exemple simple de codage : k=1 et n=3
CODAGE :
2n=23=8
2k=21=2 000 Mots-codes
Parmi les 8 mots-code
possibles , choisir 2 Possibles
0 mots-code de distance la
001
2 mots-info plus grande possible : 010
de longueur k= 1 011
qui sont 0 et 1 1 0 000 100
101 2k=21=2
1 111 110
2 mots-code
Longueur n= 3
111
Les paramètres de ce code sont :
Dimension k = 1
Longueur n = 3
Distance minimale do =3
Taux de codage = 0,33 (33%)
4
THEORIE DE L’INFORMATION & CODAGE
Introduction aux codes correcteurs d’erreurs
ABDI.M –ENSTTIC-Oran
Le code sera noté : , pour ce cas, ce sera le code
6. Capacité de correction d’un code :
La capacité de correction d’un est liée à sa distance minimale do .
Deux cas peuvent se présenter :
1. Distance minimale impaire :
il existe t entier non nul , tel que do=2t+1
le code dans ce cas, est au moins t-correcteur : il peut corriger tout mot-code
ayant subi une erreur de poids inférieur ou égal à t (nombre d’erreurs inférieur ou
égale à t)
Exemple : le code suivant : C={00000, 01101, 10110, 11011}, possède les
paramètres suivants :
Dimension k= 2
Longueur des mots-code n=5
Distance minimale do=3 (donc t=1) ,
Ce code peut donc corriger 1 erreur par mot-code transmis .
2. Distance minimale paire : do=2t
le code dans ce cas , peut détecter t erreurs, et corriger t-1 erreurs.
Exemple : le code suivant : C={0000, 0110, 1010, 1111}, possède les paramètres
suivants :
Dimension k= 2
Longueur des mots-code n=4
Distance minimale do=2 (donc t=1) ,
Ce code peut donc détecter 1 erreur par mot-code transmis .
Notion de boules :
Définition : Une boule de centre un mot c du code et de rayon r (notée B ( c , r )), est
l’ensemble qui contient tous les mots qui sont à une distance inférieure ou égale à r du mot c.
B (c , r ) = {{r0},{r1},…{ri},…{rt}},
où { ri } est le sous ensemble qui contient tous les mots qui sont à une distance i de c
Exemple de boule : Pour : , n=3 , c = 000 et r =3
5
THEORIE DE L’INFORMATION & CODAGE
Introduction aux codes correcteurs d’erreurs
ABDI.M –ENSTTIC-Oran
Exemple1 de Codage : Pour k=1, n=3
CODAGE :
000
Parmi les 8 mots-code 001
possibles , on choisit 010
0 deux mots-code de 100
distance la plus grande
possible :
0 000
1 011
1 111 101
110
111
Les paramètres de ce code sont :
Dimension k = 1
Longueur n = 3
taux de codage = 0,33 (33%)
Distance minimale do =3
Remarque : les deux boules de centres les mots codes 000 et 111 et de rayon r=1 sont comme ont le
voit disjointes, donc à chaque fois qu’un mot-code est transmis et qu’il y a une seule erreur, on peut
la corriger car le mot erroné reçu reste dans la même boule que le mot-code émis
Exemple1 de Codage : Pour k=2, n=5
CODAGE :
Parmi les 32 mots-code
possibles , choisir 4
00 mots-code de distance la
01 plus grande possible :
10
00 00000
11
01 01101
10 10110
11 11011
Les paramètres de ce code sont :
Dimension k = 2
Longueur n = 5
taux de codage = 0,4 (40%)
Distance minimale do =3
Remarque : les quatre boules de centres les mots codes 00000, 11011,10110 et 01101 et de
rayon r=1 sont comme ont le voit toutes disjointes, donc à chaque fois qu’un mot-code est
transmis et qu’il y a une seule erreur, on peut la corriger car le mot erroné reçu reste dans le
même boule que le mot-code émis
6
THEORIE DE L’INFORMATION & CODAGE
Introduction aux codes correcteurs d’erreurs
ABDI.M –ENSTTIC-Oran
7. Borne singleton et borne de Hamming :
On ne peut pas espérer construire des codes qui transmettent efficacement
l’information tout en permettant de corriger un nombre arbitraire d’erreurs.
Les deux bornes élémentaires suivantes donnent des limites précises à ce qu’on
peut espérer. (relation entre k, n et do)
Borne de singleton :
Soit C un code (n,k,do), alors do n-k+1
le taux de codage (ou taux d’information) :
le taux de correction :
L’inégalité du singleton s’écrit :
Borne de Hamming:
Si C est un code (n,k, do) , pour que C soit un code t-correcteur (do= 2t+1) sur F2 , il
faut que :
Démonstration : toutes les boules sont centrées autour des mots
codes choisis (au nombre de 2k) et de rayon t contiennent chacune
un nombre de mots égal à :B (c , t ) = {{r0},{r1},…{ri},…{rt}}
{r0} : contient les éléments qui sont à une distance 0 de c (il y a exactement : )
{r1} : contient les éléments qui sont à une distance 1 de c (il y a exactement : )
{rt} : contient les éléments qui sont à une distance t de c (il y a exactement : )
Au total dans chaque boule B (c , t ), il y a
Comme il y a 2k boules elles contiennent au total : mots différents
On sait aussi que le nombre total de mots possibles est égal à 2n
Les boules ne contiennent en général pas tous les mots possibles
(les mots en rouge sont en dehors des boules) , donc :
8. Codes MDS (Maximum Distance Separable) et codes parfaits :
Définition : soit C est code de paramètres (n,k,do),
si C atteint l’égalité de Singleton do=n-k+1 ,
on dit que le code C est MDS (Maximum Distance Separable).
si C atteint l’égalité de Hamming (où do=2t+1) ,
on dit que le code C, est t-correcteur parfait.
7
THEORIE DE L’INFORMATION & CODAGE
Introduction aux codes correcteurs d’erreurs
ABDI.M –ENSTTIC-Oran
Codes parfaits :
On dit qu’un code C est t-correcteur si les boules de C sont disjointes. En effet, on ne peut
corriger une erreur dans un mot reçu r que s’il existe un unique mot c de C le plus proche . De
plus si les boules forment une partition de l’ensemble d’arrivée ( il n’y a aucun mot en dehors
des boules), on parle de code correcteur d’erreur parfait, c'est-à-dire qu’il n’y a aucune
redondance inutile , il s’agit d’une situation idéale.
Code correcteur d’erreurs Code correcteur d’erreurs parfait
Les boules sont disjointes mais ne contiennent des boules centrées autour des mots-codes
pas tous les mots possibles (les mots en rouge choisis et de rayon t, sont disjointes, et
sont en dehors des boules centrées autour des contiennent tous les mots possibles
mots-codes choisis et de rayon t
