II.3. Les codes en blocs linéaires
II.3.1. Définition générale d'un code
en bloc
Le message à transmettre est découpé en
blocs de k bits, qui sont alors traités séparément par
le
codeur.
On appelle code un ensemble C de 2k
n-uplets de bits, avec n > k, dont les
éléments sont appelés mots [20]. Les blocs à
transmettre sont traduits en des éléments du code, chacun des
2k messages différents possibles correspondant de
manière unique à un des mots du code.
On appelle distance de Hamming entre deux mots du code le
nombre de composantes par lesquelles ils diffèrent. La distance minimale
d'un code C, notée d, est alors la distance de Hamming minimale
entre deux mots quelconques.
Un code est alors défini par les trois
paramètres (n, k, d), où n est la taille du code, k sa
dimension et d sa distance minimale.
II.3.2. Définition d'un code linéaire
La plupart des codes connus appartiennent à une classe
de codes appelés codes linéaires [21]. Cette
classe est définie par une forte contrainte sur la structure du code. La
structure imposée nous aide dans la recherche des bons codes et permet
de faciliter la réalisation du codeur et du décodeur. Les codes
les plus puissants ne sont pas nécessairement linéaires, mais peu
de méthodes existent pour rechercher les bons codes non
linéaires.
Le nombre des mots du code C est 2k. 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).
? Propriétés des codes
linéaires
Définition 1
La distance de Hamming entre 2 mots est égale aux
nombres de symboles qui diffèrent.
Des solutions existent pour les codes Reed-Solomon
Généralisés (RSG) pour les codes cycliques dans certains
cas favorables, mais pas, par exemple, pour les codes de Goppa ou les codes
géométriques.
Définition 2
Le poids de Hamming d'un mot est égal aux nombres de
symboles égaux à 1.
Définition 3
La distance minimale d'un code C est le minimum entre 2 mots de
code x et y. On notera cette distance d(x, y) et on suppose que x et y sont des
mots différents de C (on suppose que C a au moins deux mots).
dmin = min{d (x, y)} II.3
II.3.3. Généralités du
décodage
Plusieurs méthodes de décodage existent. Le
décodage du maximum de vraisemblance est la méthode la plus
souhaitable mais n'est pas toujours réalisable en pratique, sauf pour
les codes convolutifs. Elle consiste, à partir d'un modèle
probabiliste du canal, à calculer le mot le plus probable compatible
avec le mot reçu. Il est facile de montrer que le décodage
utilisant le maximum de vraisemblance consiste à retrouver le mot de
code le plus proche (au sens de Hamming) du mot reçu.
Le décodage en revanche va utiliser la structure
algébrique du code ou de son dual. La connaissance de la seule matrice
génératrice ne suffit en général pas à
décoder de manière efficace, et la structure algébrique
n'est pas nécessairement facile à obtenir à partir de la
matrice génératrice (c'est même l'un des fondements de la
sécurité de certains crypto systèmes tels que celui de
McEliece) [22].
Le décodage d'un code en bloc est un problème
difficile. On ne connait pas d'autre algorithme pour décoder les codes
linéaires, que des techniques au coût exponentiel dans le nombre
d'erreurs corrigées par bloc.
Pour de petits codes en blocs binaires, ce coût n'est
pas un problème et les solutions donnent des résultats
satisfaisants. Dans les autres cas, la connaissance du code (par exemple par la
donnée d'une matrice génératrice) sera insuffisante et il
faudra retrouver la structure algébrique.
| 
