Chapitre 3

Codage linéaire
I. Introduction
Les codes linéaires correspondent à une très large majorité de type de codes
correcteurs. Ils sont utilisés pour la détection d'altérations, avec comme
méthode de correction associée une demande de retransmission, la technique
utilisée la plus usuelle est alors la somme de contrôle. Elles sont utilisés
dans une multitude de situations, depuis quelques erreurs isolées à de vastes
altérations ou des phénomènes d'effacements.
Si le cadre utilisé est largement employé, il ne répond néanmoins pas à
l'intégralité des besoins. On peut citer deux grands sujets, peu traités par la
théorie des codes linéaires. Un bon code répond à un critère d'optimalité, il est
dit parfait. Le cadre de la théorie des codes linéaires offre des critères pour
valider cette optimalité. En revanche, il ne propose pas de méthode pour
concevoir ce type de code.
Une méthode générale pour la correction des erreurs est disponible,
le décodage par syndrome. Cette méthode consiste à créer une table
associant à chaque erreur, sa solution. La table croît exponentiellement avec
le nombre de lettres susceptible d'être erronées. Dans le cas d'une large
capacité de correction, cette approche n'est plus opérationnelle.
La théorie des codes cycliques, utilisant largement les propriétés des corps
finis répond à ces deux besoins. Un code cyclique est un code linéaire
possédant une structure algébrique supplémentaire.

II. Définition et principes

Définition (code linéaire)
Un code linéaire sert à faire correspondre à chaque mot d’information un mot de
code, par une fonction linéaire, facilite la construction du code aussi bien que le
contrôle des messages reçus. Les codes linéaires sont des codes par blocs construits à
l’aide d’une telle fonction. On note F2 le corps à deux éléments 0 et 1. Les mots de
longueurs n sont les éléments de F n2 , que l'on écrira comme des vecteurs lignes. Un
code linéaire de longueur n est un sous espace vectoriel C inclus dans F n2. La lettre k
désignera toujours la dimension de C (comme espace vectoriel). Le nombre de mots
 du code C est 2k . Le poids d'un mot x = (x1 … xn) F2 n noté w(x), est le nombre
d'indices i tels que xi ≠ 0. Comme d(x, y) = w(x - y), la distance minimal d d'un code
linéaire C est le minimum des poids w(x) pour x C non nul. (On suppose que C n'est
pas le code nul.) On regroupe les trois paramètres n, k et d d'un code linéaire C en
disant que C est de type (n, k, d).

Exemple

C = {000, 111} est un [3, 1]-code linéaire sur le

corps Z2.
Le code binaire C = {000, 111, 011} n'est pas linéaire car
111 +011 = 100 qui n'est pas un mot du code.

Définition (codage linéaire)

Φ(u1 ⊕ u2 ⊕ · · · ⊕ up) = φ(u1) ⊕ φ(u2) ⊕ · · · ⊕ φ(up), ∀p ≥ 1

Soit les blocs ui . Un codage est linéaire quand l’application φ vérifie :

Simplification propre aux codes linéaires

Le codage non-linéaire besoin des 2k mots de code pour coder chaque bloc ,par
contre avec le codage linéaire k mots de code suffisent (base canonique) .

Définition (Base canonique de code)

b1 =1000 ... 00
b2 =0100 ... 00
= .... ...
bk−1=0000 ... 10
bk =0000 ... 01
(b1, b2, · · · , bk ) forme la base canonique de Bk

III. Représentations matricielles

1)Définition
On peut se donner un sous-espace vectoriel (et donc un code) par une base.
Soit C un code linéaire. Une matrice génératrice de C est une matrice dont les
lignes forment une base de C. Une matrice génératrice G est donc de taille
k*n et de rang k. Si m est un vecteur ligne de F2 k , le produit m.G est un mot
du code C (que l'on peut voir comme une opération de codage). Si la matrice
G est de la forme (I; P), on dit que le codage est systématique. Les k premiers
bits d'un mot de code portent l'information (on y recopie le vecteur de F2 k ),
 les n-k suivants sont de la redondance. On dit que deux codes linéaires de
même longueur sont équivalents si l'un s'obtient à partir de l'autre par une
permutation des coordonnées. On peut vérifier que deux codes équivalents
ont même type. De plus tout code est équivalent à un code donné par un
codage systématique

2)Exemples
Test de parité :

Codage par répétition :

Code Cyclique :

IV. Correction des codes linéaire

1)Construction du tableau standard
Le tableau standard peut être considéré comme un outil d'organisation, un
classeur qui contient tous les n-uplets binaires possibles de 2n (appelés
vecteurs) - rien ne manque et rien ne se réplique. L'espace entier des n-uplets
est appelé le vecteur espace Vn.
À première vue, les avantages de cet outil semblent limités aux petits codes
en blocs, car pour les longueurs de code au-delà de n = 20, il y a des millions
de n-uplets dans Vn. Cependant, même pour les grands codes, le tableau
standard permet la visualisation des problèmes de performances importants,
tels que les limites de la capacité de correction des erreurs, ainsi que les
compromis possibles entre la correction et la détection des erreurs
 Tableau standard
Pour un code de bloc linéaire (n, k), tous les vecteurs reçus 2n possibles sont
disposés dans un tableau, appelé tableau standard, de sorte que la première
ligne contient l'ensemble des 2k mots de code, {C}, en commençant par tous
mot de code -zéros (la séquence composée uniquement de zéros doit faire
partie de l'ensemble de mots de code).
Le terme mot de code est utilisé exclusivement pour indiquer une entrée de
mot de code valide dans la première ligne du tableau.
Le terme vecteur est utilisé pour indiquer tout séquence ordonnée (par
exemple, tout n-uplet dans Vn).
La première colonne du tableau standard contient tous les modèles d'erreurs
corrigibles, Le terme modèle d'erreur fait référence à un n-uplet binaire, e,
qui, lorsqu'il est ajouté à un mot de code transmis, C, entraîne la réception
d'un n-uplet ou d'un vecteur, r = C + e, qui peut être appelé un mot de code
corrompu. Dans le tableau standard, chaque ligne, appelée coset, consiste en
un modèle d'erreur corrigible dans la position la plus à gauche, appelé chef de
coset, suivi de mots de code corrompus (corrompus par ce modèle d'erreur).
La structure du tableau standard pour un code (n, k) est illustrée ci-dessous :

C1 C2 … Ci … C2 k
e2 e2+ C2 … e2+ Ci … e2+ C2k
e3 e3+ C2 … e3+ Ci … e3+ C2k
… … … … … …
ej ej+ C2 … ej+ Ci … ej+ C2k
… … … … … …
e2n-k e2n-k+ C2 … e2n-k+ Ci … e2n-k+ C2k

Le mot de code C₁, le mot de code tout à zéro, joue deux rôles. C'est l'un des
mots de code. De plus, C peut être considéré comme le modèle d'erreur e le
modèle qui ne représente aucune erreur, tel que r = C.
Le tableau contient tous les n-uplets de 2n dans l'espace (chaque n-uplet
n'apparaît qu'une seule fois). Chaque coset ou ligne contient 2n n-uplets.
Par conséquent, il y a 2n/2k=2n-k cosets (ou lignes)

Exemple de construction
Laisser C être le code binaire [4,2]. C’est-à-dire C = {0000, 1011, 0101, 1110}. Pour
construire le tableau standard, nous listons d'abord les mots de code dans une
rangée.

0000 1011 0101 1110

On sélectionne alors un vecteur de poids minimum (dans ce cas, poids 1) qui n'a pas
été utilisé. Ce vecteur devient le leader du coset pour la deuxième ligne.

0000 1011 0101 1110

1000

Après l'étape 3, nous complétons la ligne en ajoutant le leader du coset à chaque

mot de code.

0000 1011 0101 1110

1000 0011 1101 0110

Nous répétons ensuite les étapes 2 et 3 jusqu'à ce que nous ayons terminé toutes les
rangées. Nous nous arrêtons quand nous avons atteint 2n-k=24-2=22=4 lignes

0000 1011 0101 1110

1000 0011 1101 0110

0100 1111 0001 1010

0010 1001 0111 1100

Dans cet exemple, nous n'aurions pas pu choisir le vecteur 0001 comme leader du coset de la
ligne finale, même s'il répond aux critères d'avoir un poids minimal (1), car le vecteur était déjà
présent dans le tableau.
Nous aurions cependant pu le choisir comme premier leader de coset et construire un tableau
standard différent.
2)Correction en utilisant tableau standard
L'algorithme de décodage demande de remplacer un mot de code corrompu,
C+e, par le mot de code valide C, qui est situé en haut de la colonne où se
trouve C + e. Supposons qu'un mot de code U, soit transmis sur un canal
bruyant. Si le modèle d'erreur provoqué par le canal est un leader de coset, le
vecteur reçu sera décodé correctement dans le mot de code transmis C i. Si le
modèle d'erreur n'est pas un leader de coset, un décodage erroné en
résultera. Il existe plusieurs limites à la capacité de correction d'erreurs des
codes linéaires ; tout système de code fonctionnel doit respecter toutes ces
limites. Une de ces bornes, appelée borne de Hamming, est décrite ci-dessous
Nombre de bits se parité :

Où Nombre de cosets

n
Où le facteur binomial ( ), représente le nombre de façons dont j bits sur
j
peuvent être erronés, notons que la somme des termes entre crochets donne
le nombre minimum de lignes nécessaires dans le tableau standard pour
corriger toutes les combinaisons d'erreurs via des erreurs de t-bit. L'inégalité
donne une borne inférieure sur n-k, le nombre de bits de parité (ou le nombre
de cosets 2n-k) en fonction de la capacité de correction d'erreur t-bit du code.
De même, l'inégalité peut être décrite comme donnant une valeur supérieure
lié à la capacité de correction d'erreur de t-bits en fonction du nombre de n-k
bits de parité (ou 2n-k cosets). Pour que tout code en bloc linéaire (n, k)
fournisse une capacité de correction d'erreur à t-bit, il est nécessaire que la
borne de Hamming soit satisfaite
Exemple
Tableau standard du code de parité [4,3,2]

0000 0011 0101 0110 1001 1010 1100 1111

0001 0010 0100 0111 1000 1011 1101 1110

On remplace R = 1000 par M = 1001

Et on remplace R = 0001 par M = 0000
V. Matrice de contrôle et syndrome

1)Définition
On peut aussi se donner un sous-espace vectoriel par un système d’équations
indépendantes.
Soit C un code linéaire. Une matrice de contrôle de C est la matrice d’un
système d’équations linéaires homogènes indépendantes dont l’espace des
solutions est C.
Autrement dit, une matrice de contrôle H est de taille (n−k)×n et de rang n−k,
et C = {x ∈ F 2, Htx = 0}.
n

Si C est donné sous forme systématique par la matrice génératrice G = (Ik, P),
alors on peut prendre comme matrice de contrôle H = (−tP , In−k) (le signe − est
superflu en caractéristique 2).
Supposons que c ∈ C est le mot du code envoyé et r ∈ F 2 le mot reçu.
n

La différence e = r −c est le vecteur d’erreur. Son poids w(e) est le nombre de

bits erronés dans le mot reçu.
Soit H une matrice de contrôle de C. Le syndrome du mot reçu r est le vecteur
s ∈ F 2 défini par ts = Ht r = Ht e.
n−k

Le syndrome est nul si et seulement si r ∈ C. Le syndrome définit un

isomorphisme du quotient F n2 /C sur F n−k
2 .

Si le syndrome est non nul, on corrige le mot reçu r en appliquant le principe

du maximum de vraisemblance : on soustrait à r un mot de poids minimum
dans sa classe modulo C, c-à-d un mot de poids minimum parmi ceux ayant
même syndrome que r. Dans le cas où w(e) est strictement inférieur à d/2,
alors e est l’unique mot de poids minimum dans la classe de r modulo C et on
récupère bien le mot de code émis.

2)Matrice de contrôle

Matrice H permettant de déterminer si un mot c appartient bien à un code C

c ∈ C ⇐⇒ c · tH = 0
avec une matrice génératrice donnée.
 Exemple :
Concéderons le codage linéaire c : F 42→ F 72défini par sa matrice génératrice

[ ]
1 0 0 0 1 1 0
0 1 0 0 0 1 1
G=
0 0 1 0 1 0 1
0 0 0 1 1 1 1

C’est un codage dont une matrice de contrôle est :

[ ]
1 0 1 1 1 0 0
H= 1 1 0 1 0 1 0
0 1 1 1 0 0 1

3)Notion de syndrome
Soit C un (k ,n)-code. Il existe une application linéaire σ : Fn Fn-k

On appelle σ(w) le syndrome de w ∈ Fn .

telle que C =ker σ.

w∈ C
Ceci permet de calculer efficacement si w est un mot du code :
σ(w)=0
Soit C donné par sa matrice génératrice (Ik |P), alors une telle application est donnée
par :

σ: w (
w.
−P
I n−k
.)
Le syndrome de message m, est σ(m) = m.tH
Exemple : message syndrome

[ ]
1 1
σ(101) = (1 0 1). 1 0 = (1 0) 110 11
0 1
011 10

101 01
Remarques :
Lignes de tH = tous les syndromes des messages de poids 1.
Sommes 2 à 2 des lignes de tH = syndromes des messages de poids 2, etc

4)Correction avec les syndromes

La linéarité du code assure un décodage aisé. Si un message m est reçu, alors
la détection d'erreurs est réalisée par la matrice de contrôle H. En effet, des
altérations détectables ont eu lieu si et seulement si Ht.m est différent du
vecteur nul. Si le nombre d'erreurs présentes dans le message est inférieur
à t, le nombre d'altérations assurément détectables, alors Ht.m possède un
unique antécédent e dans la boule fermée de centre le vecteur nul et de
rayon t. Le message corrigé est m - e. Le vecteur Ht.m est appelé syndrome.
Dans le cas où le nombre d'erreurs est supérieur à t il existe plusieurs
antécédents de poids minimal et les altérations ne sont plus assurément
corrigibles. La solution idéale consiste à demander une nouvelle transmission.
Si le nombre de syndromes est petit, une table de correspondance entre les
syndromes et leurs antécédents de plus petits poids est envisageable. Une
telle table est nommés tableaux standard et le décodage associé décodage
par tableau standard. Si l'espace des syndromes est trop vaste, il est
nécessaire de calculer son antécédent à la réception du message altéré .

Avec R reçu : on le corrige en lui ajoutant l’élément de Γ(R) de plus petit poids, donc
l’élément de Fn qui a le même syndrome que R avec le plus petit poids possible.

M Syndrome
0000000 000
0000001 001
0000010 010
0000100 100
0001000 011
0010000 110
0100000 111
1000000 101

Méthode pratique pour corriger R :

1. Calculer σ(R)

3. Corriger R en le remplaçant par R ⊕ S

2. Repérer S : le message associe à σ(R) dans la liste.

Exemple :
Soit R = 1010101, et tH est le transposé de matrice de contrôle
 ( )
1 1 0
0 1 1
1 0 1
σ(R) = R. H = (1 0 1 0 1 0 1). 1
t
1 1 = ( 1 1 0)
1 0 0
0 1 0
0 0 1

D’après la liste des syndromes : M =0010000

C = 1010101 ⊕ 0001000 = 1000101

C=R⊕M

Le message reçu est 1000101

Conclusion
Les structures utilisées dans les codes correcteurs ont tout d'abord été
très simples (par exemple celle d'espace vectoriel), puis se sont
complexifiées avec une meilleure compréhension des problèmes
théoriques. La théorie des codes correcteurs en arrive même à utiliser
la géométrie arithmétique pour construire des codes

Conclusion
Le chapitre trois était consacré sur une brève explication d’une seule branche des
codes correcteurs d’erreurs appelé « les codes en blocs », et qui regroupent des
différents types d’autre codes comme les codes linéaires.
Dans ce chapitre, nous avons éclairé aussi les relations qui existent entre les
différents codes avec leurs principes et leurs méthodes de correction d’erreurs
(codage et décodage)