Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection

et correction d

Généralités sur les

codes linéaires
Par :
SAMEN Yannick

Abomey-calavi, Juin 2016

logo
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Sommaire

1 Définition d’un code linéaire

2 Distance minimale d’un code linéaire

3 Matrice de contrôle d’un code linéaire

4 Détection et correction d’erreurs

5 Décodage par la méthode du syndrome

6 Codes parfaits

7 Caractéristiques des codes parfaits linéaires logo

Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Code linéaire

Définition
1 Un code linéaire C de longueur n est un sous-espace vectoriel

de Fn .
Cela signifie que le codage peut être réalisé par des
multiplications matricielles.
2 On dira donc qu’un code C [n, k, dm ] est linéaire s’il existe une
matrice G de dimension n × k dont les coefficients sont dans
F tels que l’ensemble des mots de code soient obtenus par
produit matriciel entre les mots source u et G. Pour Fn2 :
C = {y | y = G · u, u ∈ Fk2 }

La matrice G est appelée la matrice génératrice de C. logo

Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Code linéaire

Définition
1 Un code linéaire C de longueur n est un sous-espace vectoriel

de Fn .
Cela signifie que le codage peut être réalisé par des
multiplications matricielles.
2 On dira donc qu’un code C [n, k, dm ] est linéaire s’il existe une
matrice G de dimension n × k dont les coefficients sont dans
F tels que l’ensemble des mots de code soient obtenus par
produit matriciel entre les mots source u et G. Pour Fn2 :
C = {y | y = G · u, u ∈ Fk2 }

La matrice G est appelée la matrice génératrice de C. logo

Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Code linéaire

Définition
1 Un code linéaire C de longueur n est un sous-espace vectoriel

de Fn .
Cela signifie que le codage peut être réalisé par des
multiplications matricielles.
2 On dira donc qu’un code C [n, k, dm ] est linéaire s’il existe une
matrice G de dimension n × k dont les coefficients sont dans
F tels que l’ensemble des mots de code soient obtenus par
produit matriciel entre les mots source u et G. Pour Fn2 :
C = {y | y = G · u, u ∈ Fk2 }

La matrice G est appelée la matrice génératrice de C. logo

Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

1 Le code de Hamming [7, 4, 3] que nous avons vu dans

l’exercice précédent est un code linéaire. Une matrice
génératrice de C est :

 
1 0 0 0

 0 1 0 0 


 0 0 1 0 

G= 
 0 0 0 1 


 0 1 1 1 

 1 0 1 1 
1 1 0 1

logo
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Exemple de code linéaire

2 Pour le code de bit de parité (8, 9), la matrice génératrice est

 
I8
G=
1···1

3 Pour le code de répétition pure (1, 3), la matrice génératrice

est


1
G=  1 
1 logo
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Exemple de code linéaire

2 Pour le code de bit de parité (8, 9), la matrice génératrice est

 
I8
G=
1···1

3 Pour le code de répétition pure (1, 3), la matrice génératrice

est


1
G=  1 
1 logo
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Code systématique

Définition
Dire que le code C est systématique revient à dire que la matrice
génératrice de C est sous la forme
 
Ik
0
G

i.e lorsqu’on retrouve dans le mot codé les k symboles

d’information dans k positions determinées.

logo
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Sommaire

1 Définition d’un code linéaire

2 Distance minimale d’un code linéaire

3 Matrice de contrôle d’un code linéaire

4 Détection et correction d’erreurs

5 Décodage par la méthode du syndrome

6 Codes parfaits

7 Caractéristiques des codes parfaits linéaires logo

Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Distance minimale
Les codes linéaires sont intéressants car on dispose en général
d’informations sur leur distance minimale. De plus, dire qu’un code
C est linéaire revient à dire que la somme de deux mots de C est
encore un mot de C et le mot nul est toujours un élément de C (de
par la définition d’un sous-espace vectoriel).
Proposition
Soit C un code linéaire. Alors la distance minimale dm de C est
égale au plus petit poids de Hamming non nul d’un mot de C.

Preuve
La distance minimale est le plus petit élément non nul de
l’ensemble des distances entre deux mots de code. Il suffit donc de
montrer que cet ensemble coı̈ncide avec l’ensemble des poids des
mots de code. Tout d’abord, tout poids est une distance car logo
ωH (m) = dH (m, 0...0). Ensuite, toute distance est un poids car
0 0 0 0
dH (m, m ) = ωH (m + m ) et si m, m ∈ C on a aussi m + m ∈ C .
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Distance minimale
Les codes linéaires sont intéressants car on dispose en général
d’informations sur leur distance minimale. De plus, dire qu’un code
C est linéaire revient à dire que la somme de deux mots de C est
encore un mot de C et le mot nul est toujours un élément de C (de
par la définition d’un sous-espace vectoriel).
Proposition
Soit C un code linéaire. Alors la distance minimale dm de C est
égale au plus petit poids de Hamming non nul d’un mot de C.

Preuve
La distance minimale est le plus petit élément non nul de
l’ensemble des distances entre deux mots de code. Il suffit donc de
montrer que cet ensemble coı̈ncide avec l’ensemble des poids des
mots de code. Tout d’abord, tout poids est une distance car logo
ωH (m) = dH (m, 0...0). Ensuite, toute distance est un poids car
0 0 0 0
dH (m, m ) = ωH (m + m ) et si m, m ∈ C on a aussi m + m ∈ C .
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Distance minimale
Les codes linéaires sont intéressants car on dispose en général
d’informations sur leur distance minimale. De plus, dire qu’un code
C est linéaire revient à dire que la somme de deux mots de C est
encore un mot de C et le mot nul est toujours un élément de C (de
par la définition d’un sous-espace vectoriel).
Proposition
Soit C un code linéaire. Alors la distance minimale dm de C est
égale au plus petit poids de Hamming non nul d’un mot de C.

Preuve
La distance minimale est le plus petit élément non nul de
l’ensemble des distances entre deux mots de code. Il suffit donc de
montrer que cet ensemble coı̈ncide avec l’ensemble des poids des
mots de code. Tout d’abord, tout poids est une distance car logo
ωH (m) = dH (m, 0...0). Ensuite, toute distance est un poids car
0 0 0 0
dH (m, m ) = ωH (m + m ) et si m, m ∈ C on a aussi m + m ∈ C .
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Borne de Singleton

On dispose d’autres critères sur la distance minimale des codes

linéaires. Celui qui suit donne la limite de ce qu’on peut espérer :
Proposition
La distance minimale dm d’un code linéaire de longueur n et de
dimension k vérifie dm ≤ n − k + 1. Le membre de droite de cette
inégalité est appelé la borne de Singleton.
Un code pour lequel on a égalité est dit MDS (Maximum
Distance Separable).

logo
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Sommaire

1 Définition d’un code linéaire

2 Distance minimale d’un code linéaire

3 Matrice de contrôle d’un code linéaire

4 Détection et correction d’erreurs

5 Décodage par la méthode du syndrome

6 Codes parfaits

7 Caractéristiques des codes parfaits linéaires logo

Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Matrice de contrôle

L’intérêt principal de ne considérer que des codes linéaires est

qu’ils disposent de meilleurs algorithmes de décodage. On utilise
pour cela les matrices de contrôle.
Définition
Soit C un code linéaire de longueur n, de dimension k et matrice
génératrice G.
On appelle matrice de contrôle de C toute matrice H ayant n
colonnes et n − k lignes telle que H · m = 0 ⇔ m ∈ C .

logo
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Matrice de contrôle

L’intérêt principal de ne considérer que des codes linéaires est

qu’ils disposent de meilleurs algorithmes de décodage. On utilise
pour cela les matrices de contrôle.
Définition
Soit C un code linéaire de longueur n, de dimension k et matrice
génératrice G.
On appelle matrice de contrôle de C toute matrice H ayant n
colonnes et n − k lignes telle que H · m = 0 ⇔ m ∈ C .

logo
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Matrice de contrôle d’un code systématique

Théoreme
Soit C un code systématique de matrice génératrice
 
Ik
0
G
0
. Alors la matrice H = (G In−k ) est une matrice de contrôle de
G.

logo
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Exemple

1 Une matrice de contrôle du code de bit de parité (8, 9) est

(1 1 1 1 1 1 1 1 1).
2 Une matrice de contrôle du code de répétition pure (1, 3) est

 
1 0 1
0 1 1

logo
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Exemple

1 Une matrice de contrôle du code de bit de parité (8, 9) est

(1 1 1 1 1 1 1 1 1).
2 Une matrice de contrôle du code de répétition pure (1, 3) est

 
1 0 1
0 1 1

logo
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Exemple

3 Une matrice de contrôle du code de Hamming systématique

présenté à la première section est

 
1 1 1 0 1 0 0
 1 1 0 1 0 1 0 .
1 0 1 1 0 0 1

On pourra remarquer que cette matrice consiste simplement à

écrire en colonne tous les mots de 3 bits. Une autre
énumération aurait correspondu à un autre code de Hamming
(7, 4). logo
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Proposition
Soit C un code linéaire de matrice de contrôle H.
Alors dm est le nombre minimal de colonnes de H linéairement
dépendantes.
Par exemple :
Si H a une colonne nulle, on a dm = 1;
Si H a deux colonnes identiques, on a dm = 2
Sinon, et si une colonne de H est égale à la somme de deux
autres, on a dm = 3. etc...

On peut remarquer qu’avec cette proposition on peut retrouver

que le code de Hamming présenté plus haut a bien pour distance
minimale 3
logo
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Proposition
Soit C un code linéaire de matrice de contrôle H.
Alors dm est le nombre minimal de colonnes de H linéairement
dépendantes.
Par exemple :
Si H a une colonne nulle, on a dm = 1;
Si H a deux colonnes identiques, on a dm = 2
Sinon, et si une colonne de H est égale à la somme de deux
autres, on a dm = 3. etc...

On peut remarquer qu’avec cette proposition on peut retrouver

que le code de Hamming présenté plus haut a bien pour distance
minimale 3
logo
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Sommaire

1 Définition d’un code linéaire

2 Distance minimale d’un code linéaire

3 Matrice de contrôle d’un code linéaire

4 Détection et correction d’erreurs

Cas d’un canal sans symbole d’effacement
Cas d’un canal avec symbole d’effacement

5 Décodage par la méthode du syndrome

6 Codes parfaits
logo

7 Caractéristiques des codes parfaits linéaires

Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Cas d’un canal sans symbole d’effacement

Un symbole q-aire correspondra à un mot constitué de q éléments

binaires.
On considère un canal de transmission avec q entrées
(correspondant aux q éléments q-aires de l’alphabet de référence)
et q sorties.
Proposition
Un code linéaire C de distance minimale dm permet de :
détecter au plus dm − 1 erreurs
dm − 1
corriger au plus t = b c erreurs.
2
logo
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Cas d’un canal sans symbole d’effacement

Un symbole q-aire correspondra à un mot constitué de q éléments

binaires.
On considère un canal de transmission avec q entrées
(correspondant aux q éléments q-aires de l’alphabet de référence)
et q sorties.
Proposition
Un code linéaire C de distance minimale dm permet de :
détecter au plus dm − 1 erreurs
dm − 1
corriger au plus t = b c erreurs.
2
logo
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Remarque

Supposons que le mot code c1 ait été émis. Alors on doit se

trouver dans l’un des trois cas suivants:
1 Le mot reçu y1 est dans la boule
centrée sur c1 et de rayon t. Cela
signifie que le nombre d’erreurs
commises est inférieur à t. le mot
code choisi par le récepteur sera
c1 et les erreurs seront toutes
corrigées.

logo
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Remarque

Supposons que le mot code c1 ait été émis. Alors on doit se

trouver dans l’un des trois cas suivants:
2 Le mot reçu y2 est dans une
boule centrée sur un mot code c
( de rayon t) différent de c1 (cela
signifie que le nombre d’erreurs
est supérieur à t). Le mot code
choisi par le récepteur sera c et
il y’aura systématiquement une
erreur.

logo
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Remarque

Supposons que le mot code c1 ait été émis. Alors on doit se

trouver dans l’un des trois cas suivants:
3 Le mot reçu y3 n’appartient à
aucune boule centrée sur le mot
code et de rayon t (le nombre
d’erreurs est supérieur à t). si c1
est le mot code situé le plus près
de y3 , alors le recepteur choisira
c1 et les erreurs commises (en
nombre supérieur à t) seront cor-
rigées. Autrement, si le mot reçu
y4 n’appartient à aucune boule, il
y’aura erreur systématique.
logo
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Cas d’un canal avec symbole d’effacement

On considère un canal à q entrées et q + 1 sorties (dont un

symbole d’effacement). Les deux propositions qui suivent vont
nous montrer comment exploiter l’information apportée par la
détection d’un symbole d’effacement.
Proposition
Un code linéaire C de distance minimale dm peut ”remplir” ρ
effacements (c’est-à-dire remplacer dans un mot reçu les ρ
symboles d’effacement par les ρ éléments effectivement émis) si
ρ ≤ dm − 1.

logo
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Cas d’un canal avec symbole d’effacement

On considère un canal à q entrées et q + 1 sorties (dont un

symbole d’effacement). Les deux propositions qui suivent vont
nous montrer comment exploiter l’information apportée par la
détection d’un symbole d’effacement.
Proposition
Un code linéaire C de distance minimale dm peut ”remplir” ρ
effacements (c’est-à-dire remplacer dans un mot reçu les ρ
symboles d’effacement par les ρ éléments effectivement émis) si
ρ ≤ dm − 1.

logo
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Preuve
Supposons que le mot code c0 ait été émis et que ρ symboles aient
été transformés en symboles d’effacement (les autres symboles
constituant c0 ont été transmis correctement).
Alors un seul mot code peut être obtenu à partir du mot reçu en
remplaçant les symboles d’effacement par des symboles q-aires. En
effet, s’il en existait deux, alors la distance entre ces deux mots
code serait inférieure ou égale à ρ, donc strictement inférieure à
dm , ce qui est impossible. Donc le seul mot code qui peut être
obtenu en remplissant les symboles d’effacement est le mot code
c0 .

logo
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Proposition
Un code linéaire C de distance minimale dm peut ”remplir” ρ
effacements et corriger t erreurs si t et ρ vérifient à la fois :
ρ + 1 ≤ dm
2t + ρ + 1 ≤ dm

logo
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Preuve
Supprimer sur tous les mots code les éléments q-aires dont les
rangs coı̈ncident avec les rangs des symboles d’effacement
apparaissant dans le mot reçu,
0
On obtient un nouveau code de distance minimum dm avec
0
dm ≥ dm − ρ.
0
dm − 1
Un tel code peut corriger t erreurs si t ≤ b c.
2
Si la condition 2t + ρ + 1 ≤ dm est remplie, alors on a
0 0
2t ≤ dm − 1 − ρ. mais dm − ρ ≤ dm . Donc 2t ≤ dm − 1, soit
0 0
d −1 d −1
t≤ m . Comme t est entier, on a t ≤ b m c et par
2 2
conséquent le code peut corriger t erreurs.
Après correction des t erreurs, on obtient un mot code amputé
de ρ symboles (remplacés par le symbole d’effacement).
logo
Comme ρ + 1 ≤ dm , on sait d’après la proposition précédente
que le code peut remplir ces effacements.
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Exercice
On considère le code C donné par :
C = {000000, 010101, 101010, 111111}
1 Ce code est-il linéaire?

2 Quel est le rendement de C?

3 Quelle est sa distance minimale? la borne de Singleton est-elle

atteinte?
4 Bob reçoit le message 10?0?0. Peut-il avec certitude corriger

l’effacement (justifiez votre réponse, si oui donnez aussi le

mot corrigé).
5 Lisa reçoit le message 011111, peut-elle avec certitude

corriger l’erreur si elle suppose que c’est une erreur simple? si

elle suppose que c’est une erreur double? Justifiez votre
réponse, si oui donnez aussi à chaque fois le mot corrigé.
6 Quelle est la valeur maximale de k tel que tout effacement de
logo
k bits soit corrigeable?
7 Quelle est la valeur maximale de k tel que toute erreur de k
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Sommaire

1 Définition d’un code linéaire

2 Distance minimale d’un code linéaire

3 Matrice de contrôle d’un code linéaire

4 Détection et correction d’erreurs

5 Décodage par la méthode du syndrome

Notion de syndrome
Construction de la table de décodage

6 Codes parfaits
logo

7 Caractéristiques des codes parfaits linéaires

Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Notion de syndrome

On a vu que si c est un mot code, alors H · c = 0. Plus

généralement si y est un mot reçu, c’est-à-dire un élément de
Fn2 , on définit le syndrome de y par la quantité s(y ) = H · y .
Si donc un mot code c est transformé en le mot reçu y tel que
y = c + e, cela signifie que e comporte des ”1” là où une
erreur a été commise.
Le syndrome de y s’écrit alors:
s(y ) = s(c + e) = H · (c + e) = H · c + H · e = H · e.
Il en découle de ceci que le syndrome ne dépend que de
l’erreur (maladie) mais pas du mot reçu (le patient). Cette
propriété va permettre de diminuer la complexité du décodage
à distance minimum.
logo
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Notion de syndrome

On a vu que si c est un mot code, alors H · c = 0. Plus

généralement si y est un mot reçu, c’est-à-dire un élément de
Fn2 , on définit le syndrome de y par la quantité s(y ) = H · y .
Si donc un mot code c est transformé en le mot reçu y tel que
y = c + e, cela signifie que e comporte des ”1” là où une
erreur a été commise.
Le syndrome de y s’écrit alors:
s(y ) = s(c + e) = H · (c + e) = H · c + H · e = H · e.
Il en découle de ceci que le syndrome ne dépend que de
l’erreur (maladie) mais pas du mot reçu (le patient). Cette
propriété va permettre de diminuer la complexité du décodage
à distance minimum.
logo
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Notion de syndrome

On a vu que si c est un mot code, alors H · c = 0. Plus

généralement si y est un mot reçu, c’est-à-dire un élément de
Fn2 , on définit le syndrome de y par la quantité s(y ) = H · y .
Si donc un mot code c est transformé en le mot reçu y tel que
y = c + e, cela signifie que e comporte des ”1” là où une
erreur a été commise.
Le syndrome de y s’écrit alors:
s(y ) = s(c + e) = H · (c + e) = H · c + H · e = H · e.
Il en découle de ceci que le syndrome ne dépend que de
l’erreur (maladie) mais pas du mot reçu (le patient). Cette
propriété va permettre de diminuer la complexité du décodage
à distance minimum.
logo
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Notion de syndrome

La procédure de décodage du mot reçu y se résume de la manière

suivante:
On calcule le syndrome de y, s(y ) = H · y .
1 Si s(y ) = 0, y est un mot code et on interprète y en le mot
code y.
2 Sinon on recherche la séquence z de longueur n de poids
minimum telle que H · z = s(y ) et on décode y en c = y + z.

logo
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Construction de la table de décodage

Le problème consiste à trouver le mot z de poids minimum
vérifiant H · z = s(y ). Pour ce faire on utilise une table de
décodage construite comme suit :

On liste les q (n−m) valeurs possibles s du syndrome et on recherche

pour chacune la séquence z de longueur n de poids minimum
vérifiant H · z = s .
Le plus simple est de commencer par z = 0 puis de faire
correspondre une valeur s aux z de poids 1, puis aux z de
poids 2, · · · On s’arrête lorsque toutes les valeurs s ont un z
correspondant.
Comme on choisit le mot code c tel que c = y + z, les erreurs
corrigées sont celles apparaı̈ssant dans la table. En
conséquence la probabilité d’erreur liée à cette stratégie de logo
décodage est la probabilité des séquences d’erreurs qui ne
figurent pas dans la table.
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Construction de la table de décodage

Le problème consiste à trouver le mot z de poids minimum
vérifiant H · z = s(y ). Pour ce faire on utilise une table de
décodage construite comme suit :

On liste les q (n−m) valeurs possibles s du syndrome et on recherche

pour chacune la séquence z de longueur n de poids minimum
vérifiant H · z = s .
Le plus simple est de commencer par z = 0 puis de faire
correspondre une valeur s aux z de poids 1, puis aux z de
poids 2, · · · On s’arrête lorsque toutes les valeurs s ont un z
correspondant.
Comme on choisit le mot code c tel que c = y + z, les erreurs
corrigées sont celles apparaı̈ssant dans la table. En
conséquence la probabilité d’erreur liée à cette stratégie de logo
décodage est la probabilité des séquences d’erreurs qui ne
figurent pas dans la table.
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Exemple
On considère le code :
mots d’information mots code
000 000000
001 001110
010 010101
011 011011
100 100011
101 101101
110 110110
111 111000
On note u1 u2 u3 les mots d’information et a1 a2 · · · a6 les mots code.
On a a1 = u1 , a2 = u2 , a3 = u3 , donc le code est systématique.
D’autre part les éléments binaires de contrôle s’expriment comme
combinaisons linéaires des éléments binaires d’information: logo

a4 = u2 + u3 , a5 = u1 + u3 , a6 = u1 + u2 . Ceci nous permet

d’écrire la matrice génératrice G du code:
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

logo
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

 
1 0 0

 0 1 0 
  
 0 0 1  = I3

G=

 0 1 1 
 P
 1 0 1 
1 1 0

On déduit alors la matrice H :

 

0 1 1 1 0 0
logo
H= P I6−3 =  1 0 1 0 1 0 .
1 1 0 0 0 1
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Exemple

pour construire la table de décodage, on doit recenser les valeurs

possibles des syndromes. La matrice H étant de dimension 3 × 6 et
les séquences z de dimension 6 × 1, les produits H · z sont de
dimension 3 × 1. Donc il y’a 23 valeurs possibles des syndromes.
La séquence z = (000000)T a pour syndrome (000)T ,
La séquence z = (000001)T a pour syndrome (001)T ,
La séquence z = (000010)T a pour syndrome (010)T
etc · · ·

logo
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Finalement on obtient:
syndrome (transposés) séquences z (transposées)
000 000000
001 000001
010 000010
011 100000
100 000100
101 010000
110 001000
111 100100

D’après cette table de décodage, on constate que le code permet

de corriger toutes les configurations d’une erreur et une
configuration de deux erreurs.
Supposons que l’on reçoive le mot y = 110111. Le calcul du
syndrome de y défini par H · z = s(y ) conduit à la valeur (001)T . logo
La table de décodage permet de déterminer z = (000001)T . Le
décodage de y est c = y + z = 110110.
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Exercice

1 Soit C le code engendré par la matrice

 
1 1 1 0 1 1
 0 1 0 0 1 1 
G= 
 1
.
0 1 1 0 1 
0 1 1 1 0 1

a Déterminer le nombre de mots de code de C.

b Calculer une matrice de contrôle de C.
c Calculer la distance minimale de C
d Déterminer le nombre d’erreurs que C peut détecter/corriger. logo
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Suite exercice

2 Soit C le code de matrice de contrôle

 
1 1 1 0 0
H=  0 1 0 1 0 .
1 0 0 0 0

i Donner une matrice génératrice pour C.

ii Décoder par syndrome r = (11100) et s = (11011).
logo
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Sommaire

1 Définition d’un code linéaire

2 Distance minimale d’un code linéaire

3 Matrice de contrôle d’un code linéaire

4 Détection et correction d’erreurs

5 Décodage par la méthode du syndrome

6 Codes parfaits

7 Caractéristiques des codes parfaits linéaires logo

Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Inégalité de Hamming

Proposition
Soit C un code de paramètres (k, n) et de capacité de correction t.
Alors on a :
Pt i n−k
i=0 Cn ≤ 2

Et on appelle cette propriété l’inégalité de Hamming.

logo
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Définition d’un code parfait

Définition
Soit C un code de paramètres (k, n), de capacité de correction t.
On dit que C est un code parfait s’il vérifie une des trois
caractérisations équivalentes suivantes :
Les boules de rayon t et de centre les mots du code forment
une partition de {0, 1}n
C
Pvérifie le cas d’égalité de l’inégalité de Hamming
t i = 2n−k (on dit que C vérifie l’égalité de
C
i=0 n
Hamming).
Pour tout mot r ∈ {0, 1}n , il existe un unique mot de code m
qui réalise le minimum de d(r , m).
logo
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Sommaire

1 Définition d’un code linéaire

2 Distance minimale d’un code linéaire

3 Matrice de contrôle d’un code linéaire

4 Détection et correction d’erreurs

5 Décodage par la méthode du syndrome

6 Codes parfaits

7 Caractéristiques des codes parfaits linéaires logo

Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Code de Hamming
Définition
Soit 2 ≤ m un entier.
Un code de Hamming est un code de paramètres
(2m − m − 1, 2m − 1) dont une matrice de contrôle est obtenu par
n’importe quelle énumération en colonne de tous les mots de m
bits non nuls.

Proposition
Un code de Hamming a toujours pour distance minimale 3.

Preuve
Par définition, la matrice de contrôle d’un tel code n’a pas de
colonne nulle donc dm ≥ 2 et n’a pas deux colonnes identiques
donc dm ≥ 3; enfin en faisant la somme de deux colonnes
logo
contenant exactement un seul 1 on obtient un vecteur contenant
exactement deux 1, donc une autre colonne, d’où dm = 3.
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Code de Hamming
Définition
Soit 2 ≤ m un entier.
Un code de Hamming est un code de paramètres
(2m − m − 1, 2m − 1) dont une matrice de contrôle est obtenu par
n’importe quelle énumération en colonne de tous les mots de m
bits non nuls.

Proposition
Un code de Hamming a toujours pour distance minimale 3.

Preuve
Par définition, la matrice de contrôle d’un tel code n’a pas de
colonne nulle donc dm ≥ 2 et n’a pas deux colonnes identiques
donc dm ≥ 3; enfin en faisant la somme de deux colonnes
logo
contenant exactement un seul 1 on obtient un vecteur contenant
exactement deux 1, donc une autre colonne, d’où dm = 3.
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Code de Hamming
Définition
Soit 2 ≤ m un entier.
Un code de Hamming est un code de paramètres
(2m − m − 1, 2m − 1) dont une matrice de contrôle est obtenu par
n’importe quelle énumération en colonne de tous les mots de m
bits non nuls.

Proposition
Un code de Hamming a toujours pour distance minimale 3.

Preuve
Par définition, la matrice de contrôle d’un tel code n’a pas de
colonne nulle donc dm ≥ 2 et n’a pas deux colonnes identiques
donc dm ≥ 3; enfin en faisant la somme de deux colonnes
logo
contenant exactement un seul 1 on obtient un vecteur contenant
exactement deux 1, donc une autre colonne, d’où dm = 3.
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Remarque

Un code linéaire de paramètres (2m − 1, 2m − m − 1, 3) est

nécessairement un code de Hamming.
En effet, une matrice de contrôle H d’un tel code doit avoir 2m
lignes et m − 1 colonnes, donc contient en colonne des vecteurs de
Fn2 . Comme dm > 1, aucun vecteur colonne de H n’est nul, comme
dm > 2, aucun vecteur colonne n’apparaı̂t deux fois. Finalement, il
nous faut placer en colonne m − 1 vecteurs non nuls et distincts de
Fn2 . Comme il y’en a précisement m − 1, il faut tous les mettre et
le code considéré est un code de Hamming.

logo
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Théorème fondamental

Selon la remarque, il découle qu’un code parfait de capacité de

correction 1 a nécessairement les paramètres d’un code de
Hamming; et un code parfait linéaire de capacité de correction 1
est toujours un code de Hamming.
Théorème
Les seuls codes parfaits linéaires (binaires) sont :
Les codes de répétition pure (1, 2t + 1)
Les codes de Hamming
Le code de Golay G23

logo
Définition d’un code linéaire Distance minimale d’un code linéaire Matrice de contrôle d’un code linéaire Détection et correction d

Théorème fondamental

Selon la remarque, il découle qu’un code parfait de capacité de

correction 1 a nécessairement les paramètres d’un code de
Hamming; et un code parfait linéaire de capacité de correction 1
est toujours un code de Hamming.
Théorème
Les seuls codes parfaits linéaires (binaires) sont :
Les codes de répétition pure (1, 2t + 1)
Les codes de Hamming
Le code de Golay G23

logo