Chapitre II :
Les codes correcteurs d'erreurs
II.1. Introduction
La communication à distance (téléphone,
télévision, satellite, etc.) entre machines et usagers
nécessite des lignes de transmission acheminant l'information sans la
modifier. Les lignes utilisées sont en général loin
d'être parfaites. Alors le problème majeur de la transmission des
données est l'augmentation du débit de transmission, qui peut
être réglée par les méthodes de compression, et les
erreurs introduites par les supports de transmission. Et tout ceci entraine une
information reçue et erronée. Pour cela, l'information devra
être codée d'une manière spéciale permettant de
déceler les erreurs, ou ce qui est encore mieux de les corriger
automatiquement. On a été amené à concevoir la
théorie des codes correcteurs et détecteurs d'erreurs.
La théorie des codes correcteurs d'erreurs à
été introduite dans les années 40s par les travaux de
GOLAY, HAMMING et SHANNON. Cette théorie à été
développée pour répondre à un besoin et aux
problèmes cités auparavant (transmission des données sur
un canal de transmission bruité, compression des données...) et
trouve de nos jours de nombreuses applications.
Les codes correcteurs d'erreurs sont un outil visant à
améliorer la fiabilité des transmissions sur un canal
bruité. La méthode qu'ils utilisent consiste à envoyer sur
le canal plus de données que la quantité d'information à
transmettre. Une redondance est ainsi introduite. Si cette redondance est
structurée de manière exploitable, il est alors possible de
corriger d'éventuelles erreurs introduites pour le canal. On peut alors
malgré le bruit retrouver la quasi-intégralité des
informations transmises au départ.
Dans ce mémoire nous regroupons les codes selon deux
classes:
? La première est les codes convolutifs, qui forment
une classe souple et efficace de codes correcteurs d'erreurs;
? La deuxième famille est la famille des codes en
blocs. Dans ces derniers, l'information est d'abord coupée en blocs de
taille constante et chaque bloc est transmis indépendamment des autres
avec une redondance qui lui est propre. La plus grande sous famille de ces
codes rassemble ce que l'on appelle les codes linéaires qui constitue
les codes cycliques, les codes de HAMMING, les codes BCH [12], les codes de
Reed Solomon, les codes de GOLAY etc....
II.2. Les codes convolutifs
Les codes convolutifs ont été introduits en
1955 par P. Elias [13] comme une alternative aux codes en blocs. Sans
algorithme effectif de décodage, celle-ci est restée longtemps
sans application pratique. En 1959, les codes convolutifs sont remis au bout du
jour par D.W. Hagelbarger [14] sous le nom de codes récurrents.
L'intérêt naissant de la communauté pour ces codes a
permis, dès 1961, aux premiers algorithmes de décodage de voir le
jour. Les performances de ce nouveau type de code correcteur d'erreurs
dépassent de loin celles des codes classiques, notamment celles de codes
en blocs. Les algorithmes de décodage séquentiel, de
décodage à seuil, mais surtout l'algorithme de Viterbi [15] ont
rendu les codes convolutifs populaires et répandus.
Ceux-ci sont particulièrement adaptés aux
communications spatiales ; ils occupent alors une place
privilégiée dans la grande histoire de l'aventure spatiale. En
effet, la NASA adopte comme standard le code découvert par J.P.
Odenwalder [16] en 1970. Ce même code est utilisé par la navette
Voyager pour coder les photos de Jupiter, Saturne, Uranus et Neptune, au
début des années 80.
Les codes convolutifs traitent l'information non plus par
morceaux mais par flux. Ils sont souvent traités comme des blocs
linéaires en flux sur des corps finis. Nous nous limiterons ici aux cas
binaire (le corps à 2 éléments).
II.2.1. Présentation des codes convolutifs (ou
récurrents)
Un code convolutif transforme des mots de k
éléments binaires en mots de n éléments
binaires (n > k) selon le schéma de la figure II.1. Le
codeur est constitué de k registres à décalage en
parallèle et d'un circuit combinatoire. Pour chaque mot de k
éléments binaires en entrée, les registres sont
décalés vers la droite et le mot est inséré
à gauche, dans la première colonne. Les (m + 1)k
éléments binaires contenus dans les registres sont alors
combinés selon des opérations logiques pour former un mot de
n éléments binaires en sortie.
La différence avec les codeurs en bloc est que chaque
mot en sortie dépend non seulement de l'entrée courante, mais
aussi des entrées précédentes, les registres créant
un effet de mémoire de profondeur m [17]. La longueur m
+ 1 des registres est appelée longueur de contrainte du code. On
note un tel code C (n, k, m + 1).
Figure II.1 : Schéma de principe d'un codeur
convolutif.
Pour illustrer ce dernier, on prend comme exemple un codeur (2,
1, 3). Le circuit d'un code C (2, 1, 3) est représenté
sur la figure II.2. Ce codeur code des mots de 1 élément binaire
en mots de 2 éléments binaires (il a donc un rendement R = 1/2).
A chaque instant t se trouvent dans le registre le
dernier élément binaire m(t) ainsi que les deux
précédents m(t - Tb) et m(t - 2Tb), Tb désignant
le
temps bit. La sortie c(t) = [c1(t) c2(t)] correspondant à
l'entrée m(t) vaut :
c1(t) = m(t) + m(t - Tb) + m(t - 2Tb) II.1
c2(t) = m(t) + m(t - 2Tb) II.2
Les additions étant modulo 2 (ou exclusif
(1+1=0)).
Figure II.2 : Circuit d'un codeur convolutif C (2, 1, 3).
| 
