Codes correcteurs Ann. Univ.

2020-21

Université Hassan II-Mohammedia Filières Ingénieurs GMI 3

Faculté des Sciences et Techniques Module : Codes correcteurs
Département de Mathématiques Pr O. Khadir

Chap. 2. CODES LINEAIRES

Les codes linéaires sont des espaces vectoriels. Pourquoi s’en servir en pratique ?
Il y a au moins trois raisons à cela :
1. Mettre au service de la théorie des codes une bonne partie des outils de l’algèbre
linéaire.
2. Au lieu de transmettre des messages qui ne possèdent pas de caractéristiques parti-
culières, on transmet des mots appartenant à un espace vectoriel et codant les éléments
du message. En analysant leurs propriétés à la réception, on saura s’ils ont été altérés ou
non, et l’on pourra, éventuellement, effectuer des corrections et retrouver les véritables
mots expédiés.
3. Le calcul de la distance de Hamming devient plus simple. Comme on l’a vu au chapitre
précédent, le nombre d’erreurs que peut détecter et corriger un code en blocs, lors de la
transmission d’un mot via un canal parasité, dépend étroitement de cette distance.

Plus précisément, nous allons traiter dans ce chapitre des questions suivantes :
• La définition des codes linéaires pour fixer le vocabulaire et traduire la signification de
la distance de Hamming pour ces codes.
• La matrice génératrice G qui caractérise un code linéaire.
• La matrice de contrôle H qui vérifie rapidement l’appartenance d’un mot reçu au code
puisqu’on verra que le code devient le noyau de cette matrice. Dans certain cas, la matrice
H permet le calcul de la distance minimale et donc le nombre d’erreurs que ce code peut
détecter ou corriger.
• Le décodage des codes linéaires.
• La construction des codes de Reed-Muller (1954).

1
Codes correcteurs Ann. Univ. 2020-21

2.1. Définition d’un code linéaire, poids d’un vecteur

Donnons une structure algébrique à l’ensemble de tous les blocs constitué des n−uplets
dont chaque composante vaut le bit 0 ou 1. Ces deux bits de base seront représentés par
Z
les classes 0 et 1 de l’anneau .
2Z
Z n
L’ensemble (( ) , +, .) est un espace vectoriel (e.v) de dimension n ∈ N sur le corps à
2Z
Z
deux éléments K = dont la base canonique est :
2Z


 e1 = (1, 0, 0, 0, ..., 0, 0)
 e2 = (0, 1, 0, 0, ..., 0, 0)



e3 = (0, 0, 1, 0, ..., 0, 0) (1)
 ..



 .
 e = (0, 0, 0, 0, ..., 0, 1)
n

Définition 1. Un code linéaire C de longueur n ∈ N est un sous espace vectoriel (s.e.v)

Z n
de l’espace vectoriel ( ) .
2Z
Z
Du fait que le corps K = ne contient que deux éléments 0 et 1, savoir si un ensemble
2Z
est un s.e.v revient à vérifier s’il est stable par addition. Si la dimension du s.e.v C est
k ∈ N, alors 0 ≤ k ≤ n et Card(C) = 2k . Pour préciser ses paramètres, on notera C[n, k]
au lieu de C quand on voudra parler du code linéaire de longueur n et de dimension k.
Les éléments du code C sont tous constitués de n bits. On verra que parmi ces n bits, k
bits seront réservés pour l’information et n − k pour le contrôle d’erreurs.

Définition 2. Le poids d’un vecteur (x1 , x2 , ..., xn ) où xi ∈ {0, 1} est le nombre des
composantes non nulles :

p(x1 , x2 , ..., xn ) = card {i |1 ≤ i ≤ n, xi = 1} (2)

La proposition suivante justifie l’intérêt porté aux codes linéaires. En effet le calcul de la
distance minimale se simplifie.

Proposition 1. La distance minimale d’un code linéaire C est égale au poids minimal
des éléments non nuls du code C.

2
Codes correcteurs Ann. Univ. 2020-21

Démonstration. Soient d1 , d2 respectivement la distance minimale et le poids minimal du

code linéaire C.
Supposons que d1 est la distance de Hamming entre les deux éléments u et v du code C.
On a d1 = d(u, v) = d(u − v, 0) ≥ d2
Supposons que di est le poids d’un vecteur quelconque w du code C. On a d1 ≤ d(w, 0) = di
où 0 est le vecteur nul de longueur n.

On notera C[n, k, d] quand il s’agit du code linéaire de longueur n, de dimension k et de

distance minimale d. Plus la distance d est grande, plus on peut corriger d’erreurs. Plus
la dimension k est grande plus on peut coder d’informations.

Exemple 1. Soit C le code linéaire engendré par les vecteurs :

u1 = (0, 1, 1, 0, 1, 1), u2 = (1, 0, 0, 1, 1, 1), u3 = (0, 1, 1, 1, 0, 1)

Listons tous les éléments du code C et leurs poids. Ils sont de la forme λ1 u1 + λ2 u2 + λ3 u3
où les λi ∈ {0, 1}. D’où la table :
(λ1 , λ2 , λ3 ) (mot information) mots ui ∈ C poids p(ui ) = d(ui , 0)
000 000000 0
001 011101 4
010 100111 4
011 111010 4
100 011011 4
101 000110 2
110 111100 4
111 100001 2

La distance minimale ici est d = 2 et l’on vérifie la formule de Singleton vue dans un
exercice du chapitre 1 : d + k ≤ n + 1. Ce code peut servir à représenter au maximum 8
symboles. Il peut détecter une erreur.

3
Codes correcteurs Ann. Univ. 2020-21

2.2. Matrice génératrice

La matrice génératrice est pratique pour inclure un message de longueur k bits dans un
mot code de longueur n bits, n > k. Au lieu de transmettre le message via un canal de
communication parasité, on transmet le mot code car ce dernier possède des propriétés
permettant de détecter et corriger les erreurs survenues lors de la transmission.

Définition 3. Soit C ⊂ {0, 1}n un code linéaire de dimension k dont une base est :


 e1 = (a11 , . . . , a1n )
e2 = (a21 , . . . , a2n )

(4)

 .........
ek = (ak1 , . . . , akn )


Une matrice génératrice du code C est la matrice dont les lignes sont les composantes des
éléments de la base (ei )1≤i≤k :

 
a11 a12 ... a1n
 a21 a22 ... a2n 
G=
 ...
 (5)
... ... ... 
ak1 ak2 ... akn

Proposition 2. Soit C ⊂ {0, 1}n un code linéaire de dimension k dont une matrice
génératrice est G. Alors

a = (a1 , a2 , . . . , an ) ∈ C ⇐⇒ ∃ b = (b1 , b2 , . . . , bk ) ∈ {0, 1}k | a = bG

k
X
Démonstration. On peut vérifier que ∀ b ∈ {0, 1}k , bG = bi e i .
i=1

Nous avons ici un moyen de coder l’information. Il suffit de la mettre sous la forme de
k bits et de la multiplier par la matrice fixe G qui ne dépend que du code linéaire et de
l’une de ses bases. Après la multiplication, on tombe sur un élément du code.

Lorsqu’on ajoute à une ligne une combinaison linéaire (C.L) des autres lignes de la matrice
génératrice G, on ne fait qu’un changement de base et donc le code ne se modifie pas.

4
Codes correcteurs Ann. Univ. 2020-21

On peut souvent par ce biais s’arranger pour mettre G sous la forme réduite (standard,
normale, canonique) :
G = [Ik | A] (6)

où Ik est la matrice identité d’ordre k et A est une matrice (k, n − k).

Exemple 2. Considérons le code C ⊂ {0, 1}5 dont une base est :

e1 = (0 0 1 1 1) e2 = (1 0 1 0 1) e3 = (1 1 0 1 1)
 
0 0 1 1 1
G= 1 0 1 0 1 
1 1 0 1 1
Appliquons la méthode du pivot de Gauss :
échanger(L1 , L2 )  
1 0 1 0 1
G1 =  0 0 1 1 1 
1 1 0 1 1

L3 ←− L3 + L1  
1 0 1 0 1
G2 =  0 0 1 1 1 
0 1 1 1 0
échanger(L2 , L3 )  
1 0 1 0 1
G2 =  0 1 1 1 0 
0 0 1 1 1
L1 ←− L1 + L3  
1 0 0 1 0
G3 =  0 1 1 1 0 
0 0 1 1 1
L2 ←− L2 + L3  
1 0 0 1 0
G4 =  0 1 0 0 1  = [I3 | A(3 × 2)]
0 0 1 1 1

En utilisant la nouvelle base :

e01 = (1 0 0 1 0) e02 = (0 1 0 0 1) e03 = (0 0 1 1 1),

5
Codes correcteurs Ann. Univ. 2020-21

l’information se code par :

∀ b = (b1 b2 b3 ) ∈ {0, 1}3 , bG = (b1 b2 b3 b1 + b3 b2 + b3 )
Quand l’information se retrouve au début du mot code, on parle de code systématique.
L’avantage de travailler avec une matrice génératrice réduite G, est que quand code un
mot information u par G, on trouve un mot code w qui contient à son début le mot
information u, et donc après transmission, il est aisé de localiser u.

6
Codes correcteurs Ann. Univ. 2020-21

2.3. Matrice de contrôle de parité

La matrice de contrôle de parité est pratique pour savoir rapidement si un mot reçu
x = (x1 , x2 , . . . , xn ) appartient ou non au code linéaire C[n, k, d]. Bien sûr, quand x 6∈ C,
c’est qu’il y a eu une erreur lors de la transmission des signaux. Si on désigne par H cette
matrice, le test revient à vérifier si H x = 0 en écrivant le mot x en colonne. C’est-à-dire
vérifier si H t x = 0 où t
A désigne la transposée de la matrice A.

En effet, d’après un résultat d’algèbre linéaire, pour tout sous-espace vectoriel C de dimen-
sion k d’un espace vectoriel de dimension n, il existe un système (S) de (n − k) équations
linéaires homogènes indépendantes dont la solution est l’ensemble C. Autrement dit :


 f1 (x) = 0
 f2 (x) = 0

x ∈ C ⇐⇒ (S) .. (7)


 .
 f (x) = 0
n−k

En prenant pour H la matrice de ce système qui est de type (n − k, n), on a :

Proposition 3. Soit H une matrice de contrôle de parité pour le code linéaire C[n, k, d].
On a :
1. La matrice H admet (n − k) lignes indépendantes et n colonnes.
2. x ∈ C ⇐⇒ H t x = 0. (égalité utile lors du décodage).
3. Le code C est le noyau de l’application linéaire associée à la matrice H.

Remarque 1. Ni la matrice génératrice G, ni la matrice de contrôle de parité H, ne

sont uniques car on peut permuter les lignes.

Théorème 1. Soit C[n, k, d] un code linéaire de matrice génératrice réduite G =

(Ik A(k,n−k) ). Alors une matrice de contrôle de parité du code C est H = ( t A(k,n−k) I(n−k) )

Exemple 3. Soit G la matrice définie par

 
1 0 1 1 1
G=
0 1 1 0 1
Cette matrice engendre un code C dont les éléments sont trouvés en multipliant (λ1 λ2 )
par la matrice G pour λ1 , λ2 ∈ {0, 1}. La table suivante contient le calcul de (λ1 λ2 )G :

7
Codes correcteurs Ann. Univ. 2020-21

(λ1 , λ2 ) (mot information) mots ui ∈ C

00 00000
01 01101
10 10111
11 11010
On observe que la distance minimale est d = 3. Donc le code C sert pour détecter 1 ou 2
erreurs et peut corriger une erreur.
Comme G est de la forme réduite G = [I2 A(2,3) ], la matrice de contrôle de parité est
 
1 1 1 0 0
H=  1 0 0 1 0 
1 1 0 0 1
   
0 0
t
Supposons que le mot w1 = 00011 a été reçu. On a H w1 =  1  6=  0 
1 0
On note que d(w1 , u1 ) = d(w1 , u2 ), donc on est embarrassé pour  corriger
 le mot reçu w1 .
1 0
Par contre si le mot w2 = 00101 a été reçu, on a aussi H t w2 =  0  6=  0 . Il y a
1 0
eu erreur lors de la transmission. Ici le seul mot du code proche de w2 est le mot u2 avec
d(w2 , u2 ) = 1, d’où on corrige w2 en le remplaçant par le mot u2 .

Un autre intérêt de la matrice de contrôle de parité est qu’elle peut nous fournir la distance
minimale du code.

Proposition 4. Soit C[n, k, d] un code linéaire dont une matrice de contrôle de parité
est H. Soient C1 , C2 , . . . , Cn les vecteurs colonnes de H. Alors :
Xn
1. x = (x1 , x2 , . . . , xn ) ∈ C ⇐⇒ xi Ci = 0.
i=1
r
X
2. Le code C possède un mot de poids r ≥ 1 ⇐⇒ ∃(i1 , i2 , . . . , ir ) | Cij = 0.
j=1
3. r colonnes de H sont liées ⇐⇒ d(C) ≤ r.
4. d(C) = r ⇐⇒ toute famille de r − 1 colonnes est libre et il existe r colonnes liées.

Corollaire 1. La distance minimale d’un code linéaire C[n, k, d] est égale au nombre
minimal de colonnes liées dans la matrice de contrôle H.

Corollaire 2. 1. Si toutes les familles de r colonnes de H sont libres, alors d ≥ r + 1.

2. Si une matrice de contrôle d’un code linéaire C contient une colonne nulle, alors

8
Codes correcteurs Ann. Univ. 2020-21

d(C) = 1.
3. Si une matrice de contrôle d’un code linéaire C, sans colonne nulle, contient deux
colonnes égales, alors d(C) = 2.

Exemple 4. Soit C un code dont une matrice de contrôle est :

 
1 0 0 1 0 1
H= 0 1 0 1 1 1 
0 0 1 0 1 1
Il existe une famille de trois colonnes liées et deux quelconques sont libres. Donc
d(C) = 3.

9
Codes correcteurs Ann. Univ. 2020-21

2.4. Décodage des codes linéaires

A) Méthode de la matrice de contrôle

Soit C[n, k, d] un code linéaire de longueur n, de dimension k et de distance minimale d.
Supposons qu’on a expédié le mot x ∈ C et qu’on a reçu le mot y. La différence entre x
et y est le mot e = x − y. Chaque bit de e égal à 1 signifie qu’il y eu une erreur dans x à
la position associée à ce bit.
Par définition, le syndrome de y est :

H t y = H t (x − e) = H t (x + e) = H t e.

Soient C1 , C1 , . . . , Cn les vecteurs colonnes de H et posons e = (e1 , e1 , . . . , en ). On a

n
X
t
H y= ei Ci .
i=1

Théorème 2. On suppose que la matrice H n’admet pas de colonne nulle et pas de

colonnes égales. Si au cours de la transmission de x, il n’y a eu qu’une erreur au plus,
alors H t y sera nul ou égal à une colonne Ci0 et on doit corriger le bit d’indice i0 .
n
X
Démonstration. On a vu que H t e = ei Ci = Ci0 , (ou sera nul) car tous les bits de e
i=1
sont nuls sauf peut-être un. Si H t e = 0 c’est qu’il n’y a pas eu d’erreur.

Exemple 6. Soit la matrice de contrôle de parité obtenue à l’exemple 3. :

 
1 1 1 0 0
H= 1 0 0 1 0 
1 1 0 0 1
Supposons qu’on a reçu lemessage
 y = 10010. (au lieu du mot expédié x = 11010).
  1  
1 1 1 0 0   0  1
H =  1 0 0 1 0  0  =
    0 . C’est la deuxième colonne de H, donc on
1 1 0 0 1  1  1
0
corrige le second bit de y. D’où y = 11010.

Remarque 3. Soit C[n, k, d] un code de matrice génératrice G et de matrice de contrôle

de parité H. On a :
H t G = 0. (10)

10
Codes correcteurs Ann. Univ. 2020-21

En effet : ∀x ∈ {0, 1}k (x en ligne), on a x G ∈ C, donc t G t x ∈ C. En posant y = t x, on

a : ∀y ∈ {0, 1}k (y en colonne) : t G y ∈ C, et donc H t G y = 0. Par suite H t G = 0.
Autrement dit le produit scalaire de toute ligne de G avec toute ligne de H est nul.

B) Méthode du tableau standard

Z n
Soit C = C[n, k, d] un code linéaire. C’est un sous-groupe du groupe (( ) , +). La
2Z
congruence modulo C est bien connue. Les classes d’équivalence sont toutes de la forme
Z
x + C où x ∈ ( )n . Elles sont de même cardinal que celui de C et constitue une partition
2Z
Z n
de ( ) . Leur nombre est donc 2n−k . On les appelles classes latérales.
2Z
Le tableau standard est un tableau dont les lignes sont les classes latérales. Le premier
élément de chaque classe est choisi avec une distance minimale. Il s’appelle chef de classe
ou leader ou représentant de la classe. Une colonne termine le tableau et contient les
syndromes des chefs de classe.
Le tableau standard se construit ligne par ligne :
La première ligne est l’ensemble des éléments du code linéaire C, en rouge.
Le premier terme e1 , en bleu, de la seconde ligne est l’élément de {0, 1}5 de poids minimal
et n’appartenant pas à la première ligne. Quand on a plusieurs possibilités, on en prend
un arbitrairement. Les suivants sont la somme de e1 avec les éléments du code.
Le premier terme e2 , en bleu, de la troisième ligne est l’élément de {0, 1}5 de poids minimal
et n’appartenant pas aux lignes précédentes. Les suivants sont la somme de e2 avec les
éléments du code.
etc...
Nous allons illustrer la technique sur l’exemple du code C[5, 2] dont une matrice
génératrice et une matrice de contrôle de parité sont :
 
  1 1 0 0 0
0 0 1 1 1
G= et H =  1 0 1 1 0 
1 1 1 0 0
0 0 0 1 1
Deux colonnes quelconques de H sont libres et il existe trois colonnes liées : donc d(C) = 3.

11
Codes correcteurs Ann. Univ. 2020-21

Représentants 00000 11100 00111 11011 Syndromes

e1 =10000 10000 01100 10111 01011 110
e2 =01000 01000 10100 01111 10011 100
e3 =00100 00100 11000 00011 11111 010
e4 =00010 00010 11110 00101 11001 011
e5 =00001 00001 11101 00110 11010 001
e6 =10001 10001 01101 10110 01010 111
e7 =10010 10010 01110 10101 01001 101
Tableau standard

Voici comment on décode : Supposons que l’on reçu le mot y = 00101 après avoir expédié
le mot x ∈ C. On localise y grâce au calcul de son syndrome : H t y = 011. L’erreur
e4 =00010 montre qu’il y a eu un seul bit erroné. Et comme ce code est de distance
minimale d(C) = 3, il est capable de corriger une erreur, on prend l’élément du code C
de la colonne y, c’est-à-dire : x = 00111.
Complexité : La multiplication de la matrice de contrôle H par le mot reçu y de longueur
n, exige (n − k)kn multiplications. La recherche du syndrome dans la table des syndromes
qui est de cardinal 2n−k nécessite O(2n−k ). Donc le coût de l’algorithme est exponentiel.

12
Codes correcteurs Ann. Univ. 2020-21

2.5. Code de Hamming comme code linéaire

 peut-être considéré comme l’ensemble des éléments x1 x2 x3 x4 x5 x6 x7 ∈

Le code de Hamming
 x1 ≡ x3 + x5 + x7 [2]
7
{0, 1} tels que x2 ≡ x3 + x6 + x7 [2]
x4 ≡ x5 + x6 + x7 [2]


L’ensemble C est un s.e.v de dimension 4, noyau de la matrice de contrôle

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

La matrice de contrôle de parité de H est facile à retenir car chaque colonne est le renversé
de l’écriture binaire de 1,2,3,4,5,6,7. De plus on peut échanger la première et la troisième
lignes pour avoir directement l’écriture binaire de 1,2,3,4,5,6,7.
D’autre part, la matrice H contient trois colonnes de somme nulle et deux colonnes quel-
conques ne sont pas égales. D’où la distance minimale du code de Hamming est bien trois.
Il peut en conséquence corriger une seule erreur.
Comme (x1 , x2 , x3 , x4 , x5 , x6 , x7 ) = (x3 + x5 + x7 , x3 + x6 + x7 , x3 , x5 + x6 + x7 , x5 , x6 , x7 )
= x3 (1, 1, 1, 0, 0, 0, 0) + x5 (1, 0, 0, 1, 1, 0, 0) + x6 (0, 1, 0, 1, 0, 1, 0) + x7 (1, 1, 0, 1, 0, 0, 1) ; une
matrice génératrice de C est
 
1 1 1 0 0 0 0
 1 0 0 1 1 0 0 
G=
 0

1 0 1 0 1 0 
1 1 0 1 0 0 1

Les bits d’information sont x3 , x5 , x6 et x7 . Voici le schéma de la réalisation matérielle :

13
Codes correcteurs Ann. Univ. 2020-21

i1 i2 i3 i4

• •

• •
• •
• • •

⊕ ⊕ ⊕

x1 x2 x4 x3 x5 x6 x 7

Figure 1 – Circuit du codeur de Hamming

Lorsqu’on reçoit le message y = (y1 , .., y7 ), le syndrome s1 , s2 , s3 se calcule directement

du produit de la matrice de contrôle avec :

t
y = t (y1 , .., y7 )

On obtient : 
 s1 = y 1 + y 3 + y 5 + y 7
s2 = y 2 + y 3 + y 6 + y 7
s3 = y 4 + y 5 + y 6 + y 7


Voici le schéma de la réalisation matérielle :

L’écriture binaire s3 s2 s1 donne la position de l’erreur du mot transmis y1 y2 . . . y7 .

•−−−−−•−−−−−•−−−−−•−−−−−•

14
Codes correcteurs Ann. Univ. 2020-21

y1 y2 y3 y4 y5 y6 y7

•
•
• •

⊕ ⊕ ⊕

Z Y X

Figure 2 – Circuit du décodeur de Hamming

15
Codes correcteurs Ann. Univ. 2020-21

2.6. Code dual

Les codes duaux jouent un rôle important dans le décodage des erreurs. La définition
suivante utilise le produit scalaire classique entre deux n−uplets. Il est noté à l’aide d’un
point en gras.

Définition 4. Soit C ≡ C[n, k, d] un code linéaire. Le dual (ou l’orthogonal) C 0 du code

Z n
C, noté C ⊥ , est l’ensemble des éléments de ( ) dont le produit scalaire binaire avec
2Z
n’importe quel élément du code linéaire C est nul. C’est-à-dire :
Z n
C ⊥ = {(y1 , y2 , . . . , yn ) ∈ ( ) | x1 y1 + x2 y2 + · · · + xn yn ≡ 0 [2], ∀ (x1 , x2 , . . . , xn ) ∈ C}
2Z
(8)
n
X
Remarque : Ne pas confondre produit scalaire normal u.v = ui vi , et produit scalaire
i=1
Xn
binaire u.v = ( ui vi ) mod 2 qui sert dans la définition du code dual.
i=1

Proposition 5. L’ensemble C ⊥ est un code linéaire de longueur n.

Z n
Démonstration. On a C ⊥ ⊂ ( ) , donc C ⊥ est un code de longueur n. Pour prouver qu’il
2Z
est linéaire, il suffit de montrer qu’il est stable par addition. Soient y = (y1 , y2 , . . . , yn ), y’ =
(y10 , y20 , . . . , yn0 ) ∈ C ⊥ . On a pour tout x = (x1 , x2 , . . . , xn ) ∈ C, (y + y’).x = (y1 + y10 )x1 +
(y2 + y20 )x2 + . . . + (yn + yn0 )xn = (x1 y1 + x2 y2 + · · · + xn yn ) + (x1 y10 + x2 y20 + · · · + xn yn0 ) = 0.
Donc y + y’ ∈ C ⊥ .

Proposition 6. Si C ≡ C[n, k, d] est un code linéaire dont une matrice génératrice est
G, alors G est une matrice de contrôle de parité du code dual C ⊥ .

Démonstration. Soit (ei )1≤i≤k la base du code C associée à la matrice génératrice G =

(aij ) 1≤i≤k . Si x = (x1 , x2 , . . . , xn ), on a :
1≤j≤n 

 a11 x1 + . . . + a1n xn = 0
 a21 x1 + . . . + a2n xn = 0

x ∈ C ⊥ ⇐⇒ ∀i ∈ {1, 2, . . . , k}, x.ei = 0 ⇐⇒ ..


 .
 a x + ... + a x = 0
k1 1 kn n

⇐⇒ x ∈ Ker(G). D’où C ⊥ = Ker(G) et par conséquent G est une matrice de contrôle

de parité du code dual C ⊥ .

16
Codes correcteurs Ann. Univ. 2020-21

Corollaire 3. Soit C ≡ C[n, k, d] un code linéaire dont une matrice génération est G et
dont le dual est C ⊥ . On a :
1. dim(C ⊥ ) = n − k.
2. (C ⊥ )⊥ = C.

Démonstration. 1. Comme C ⊥ = Ker(G), on a dim(C ⊥ ) = n − dim(Im(G)) = n −

rang(G)) = n − k.
2. Puisque dim((C ⊥ )⊥ ) = dim(C), il suffit de prouver que C ⊂ (C ⊥ )⊥ . Soit x ∈ C. Pour
tout y ∈ C ⊥ , par définition de C ⊥ , y.z = 0 pour tout z ∈ C. En particulier y.x = 0, et
donc x ∈ (C ⊥ )⊥ .

Proposition 7. Si C ≡ C[n, k, d] est un code linéaire dont une matrice de contrôle de

parité est HC = (bij ) 1≤i≤n−k , alors HC est une matrice génératrice du code dual C ⊥ .
1≤j≤n


 e01 = (b11 , b12 , . . . , b1n )
 e0 = (b21 , b22 , . . . , b2n )

2
Démonstration. Soit (e0i )1≤i≤n−k la famille définie par : ..

 .
 e0 = (b

n−k n−k,1 , bn−k,2 , . . . , bn−k,n )

Puisque le rang deHC est n − k, la famille (e0i )1≤i≤n−k est libre. De plus pour tout x ∈ C,

 e01 .x = 0
 e0 .x = 0

2
HC (x) = 0, donc .. et par suite le sous-espace vectoriel < e0i > engendré par

 .
 e0 .x = 0

n−k
les éléments e0i est contenu dans le code dual C ⊥ et les deux ont même dimension. D’où
< e0i >= C ⊥ et par conséquent HC est bien une matrice génératrice du code dual C ⊥ .

Corollaire 4. Si GC ⊥ et HC ⊥ sont respectivement une matrice génératrice et une matrice

de contrôle de parité du code dual C ⊥ , alors elles sont respectivement une matrice de
contrôle de parité et une matrice génératrice du code C. Autrement di :

HC = GC ⊥
(9)
GC = HC ⊥

Démonstration. Cela vient du fait que (C ⊥ )⊥ = C.

Remarque pratique 2. Que ce soit pour le code linéaire C ou pour son code dual
C ⊥ , la détermination de l’une des matrices G ou H à partir de l’autre se ramène à la

17
Codes correcteurs Ann. Univ. 2020-21

détermination d’une matrice de contrôle de parité et donc à la détermination d’une base

du noyau Ker d’une matrice.

Exemple 5. Déterminons une matrice de contrôle de parité HC pour le code linéaire C

dont une matrice génératrice est
 
1 1 0 1 0
GC =  0 0 1 0 1 
1 1 1 0 1
Comme HC = GC ⊥ , il suffit de déterminer GC ⊥ . Mais C ⊥ = Ker(GC ), donc il suffit de
trouver Ker(GC ).  
 x1 + x2 + x4 = 0  x1 + x 2 = 0
Soit x = (x1 , x2 , x3 , x4 , x5 ). On a x ∈ C ⊥ ⇐⇒ x 3 + x5 = 0 ⇐⇒ x3 + x 5 = 0
x1 + x2 + x3 + x5 = 0 x4 = 0
 
 0
e1 = (1, 1, 0, 0, 0)
⇐⇒ x = (x1 , x1 , x3 , 0, x3 ). D’où une base du code dual C ⊥ est : et
  e02 = (0, 0, 1, 0, 1)
1 1 0 0 0
par suite HC = GC ⊥ = .
0 0 1 0 1

18
Codes correcteurs Ann. Univ. 2020-21

2.7. Codes de Reed-Muller comme code linéaires (1954)

Découverts indépendamment par deux chercheurs américains en 1954, ce sont des codes
très efficaces pour la correction des erreurs lors de transmissions de messages et possèdent
un bon taux de rendement dimension/longueur. L’algorithme qui permet leur construction
est assez simple. On les fabrique par une technique de récurrence. L’un de ces codes a été
utilisé par la NASA pour les missions spatiales de 1969 à 1976. En particulier, en 1972, la
sonde Mariner, pour transmettre des images de la planète Mars aux stations terrestres,
était programmée pour se servir d’un code de Reed-Muller capable de corriger jusqu’à 7
erreurs.
Voici comment ces codes se construisent récursivement. Soient C1 un code [n, k1 , d1 ] et
C2 un code [n, k2 , d2 ] deux codes linéaires de même longueur n, de dimensions respectives
k1 , k2 et de distances minimales respectives d1 < d2 . On fabrique un nouveau code C3 =
C1 ∗ C2 de longueur 2n et de dimension k1 + k2 de la façon suivante : les mots de C3 sont
les mots w = (u, u + v) où u et v sont tous les mots de C1 et de C2 respectivement. La
longueur de C3 vaut bien 2n et sa dimension k1 + k2 .
Pourquoi la dimension de C3 est k1 + k2 ? :
Soient (e1 , e2 , . . . , ek1 ) une base de C1 et (e01 , e02 , . . . , e0k2 ) une base de C2 . On forme la famille
B = (e1 , e1 ), (e2 , e2 ), . . . , (ek1 , ek1 ), (0, e01 ), (0, e02 ), . . . , (0, e0k2 ). C’est une famille génératrice
Xk1 X k1 Xk2 k1
X
car (u, u + v) = (u, u) + (0, v) = ( λi ei , λi ei ) + (0, µj ej ) = λi (ei , ei ) +
i=1 i=1 j=1 i=1
k2
X
µj (0, e0j ).
j=1
On vérifie facilement que la famille B est libre. Donc c’est une base et par conséquent
dim(C3 ) = dim(C1 ∗ C2 ) = k1 + k2 .
Pourquoi la distance minimale de C3 est min(2d1 , d2 ) ? :
On partage le code C3 en deux sous ensemble disjoints : A = {(u, u) | u ∈ C1 } et
B = {(u, u + v) | u ∈ C1 , v ∈ C2 , v 6= 0}.
Pour avoir le poids minimal de C3 , il suffit de calculer celui de A et celui de B et de
prendre leur minimum.
Il est évident que le poids minimal de A est 2d1 .
Le poids d’un couple (u, u + v) est supérieur ou égal au poids de (0, v) car un bit ”1”
neutralisé dans la seconde composante u + v, est récupéré dans la première composante u

19
 Codes correcteurs Ann. Univ. 2020-21

de (u, u + v). Donc le poids minimal dans B est (0, v0 ) où v0 est l’élément de C2 de poids
minimal. Ainsi le poids minimal dans l’ensemble B est d2 .
En conclusion la distance minimale, qui se confond avec le poids minimal pour les codes
linéaires, de C3 = C1 ∗ C2 est min(2d1 , d2 ).
En d’autres termes, C3 = C1 ∗ C2 est un code [2n, k1 + k2 , min(2d1 , d2 )]. Et si l’on a
2d1 = d2 et k1 > k2 , alors C3 = C1 ∗ C2 est un code meilleur que C1 sur la distance
minimale et meilleur que C2 sur le taux d’information.

Exemple 7. Partons des codes C1 = {00, 01, 10, 11} = C[2, 2, 1] et C2 = {00, 11} =
C[2, 1, 2].

On fabrique un code C[2n, k1 + k2 , min(2d1 , d2 )] = C[4, 3, 2] constitué de :

{0000, 0011, 0101, 0110,1010, 1001, 1111, 1100}

La règle consiste à oublier définitivement le code C2 et à reproduire chaque mot du code

C1 deux fois : un première fois concaténé avec lui-même et une seconde fois concaténé
avec son complémentaire. On peut utiliser les arbres binaires pour une représentation plus
simple.

0 1

00 01 11 10

0000 0011 0101 0110 1111 1100 1010 1001

00000000 00001111 ... ... ... ... ... ... ... ... ... ... ... ... ...

Combinant celui-ci avec le code [4, 1, 4] = {0000, 1111}, on fabrique un code C[8, 4, 4].
Combinant ce dernier avec un code C[8, 1, 8] = {00000000, 11111111}, on fabrique un
code C[16, 5, 8].

20
Codes correcteurs Ann. Univ. 2020-21

La table suivante contient le code de Reed-Muller C[16, 5, 8] de longueur 16. Ce code peut
coder jusqu’à 25 = 32 symboles. On peut donc séparer les bits du flux à coder en paquets
de 5 bits. Le code détecte toutes les erreurs entre 1 et 7 et il en corrige jusqu’à 3.

00000000 00000000 00000000 11111111 00001111 00001111 00001111 11110000

00110011 00110011 00110011 11001100 00111100 00111100 00111100 11000011
01010101 01010101 01010101 10101010 01011010 01011010 01011010 10100101
01100110 01100110 01100110 10011001 01101001 01101001 01101001 10010110
10101010 10101010 10101010 01010101 10100101 10100101 10100101 01011010
10011001 10011001 10011001 01100110 10010110 10010110 10010110 01101001
11111111 11111111 11111111 00000000 11110000 11110000 11110000 00001111
11001100 11001100 11001100 00110011 11000011 11000011 11000011 00111100

Code Reed-Muller C[16, 5, 8]

Le code C[16, 5, 8], à son tour, combiné avec un code à répétition C[16, 1, 16] fournit
un code C[32, 6, 16]. Ce dernier a été utilisé par la NASA pour la transmission d’images
de la planète Mars à l’aide du satellite Mariner-9. Les 6 bits d’information représentaient
la couleur en gris d’un pixel parmi 64 possibilités. Le code peut corriger 7 erreurs et peut
détecter jusqu’à 15 erreurs.

A retenir : Si la longueur des mots d’un code de Reed-Muller est 2m alors sa distance
minimale est 2m−1 (moitié de la longueur) et son cardinal est 2m+1 (le double de la
longueur).

•−−−−−•−−−−−•−−−−−•−−−−−•

21