Les codes correcteurs d’erreurs

Chaine de communication

Il est important de connaitre la capacité du canal avant la transmission. Dans l‟article de Shannon paru en 1948 [1], Shannon donne le modèle simplifié d‟une communication sans fil.
Ce modèle est composé de 6 parties : S (source), CS (codage de source), CC (codage de canal), DC (décodage canal), DS (décodage source), D (destination). La Figure 1.2 montre le modèle utilisé par Shannon pour la description de la communication. Evidemment, le FEC a un impact considérable sur la performance de la chaîne complète d‟émission-réception.

Codage de source

Des bits de redondance sont rajoutés avant que le message ne soit émis par la source S. Le codage de source a pour but d‟éliminer la redondance de la source (compression). Il faut pour cela répartir équitablement l‟information sur l‟ensemble des symboles 𝑥𝑖. On définit alors l‟entropie d‟une source comme étant l‟information moyenne émise par la source [2] :

Codage de canal

Le codage de canal a pour but de protéger le message émis par la source normalisée (sans redondance) contre les bruits et les perturbations introduits par le canal de propagation. Pour assurer un transfert sur un canal bruité, il est nécessaire d‟introduire de la redondance dans le message transmis. En réception, le décodeur reçoit le message émis par le codeur perturbé à cause de bruit du canal. L‟information mutuelle I(X; Y) en Figure 1.3 entre l‟entrée et la sortie du canal peut être exprimée sous la forme [2] :

Seconde Théorème de Shannon

Le second théorème de Shannon apporte donc une solution au problème soulevé au niveau de la capacité du canal. Les codes qui peuvent satisfaire le théorème de Shannon avec un rendement R aussi près voulu de la capacité C du canal considéré sont appelés les codes qui atteignent la capacité. Il faut noter que la recherche d‟un tel code est très difficile. En fait, à l‟époque de Shannon (1948), aucun code de la sorte n‟était connu. La preuve du théorème de Shannon n‟est pas constructive, c‟est-à-dire qu‟elle ne donne pas de recette explicite pour la construction d‟un code atteignant la capacité. Depuis 1948, les théoriciens des codes ont tenté sans succès de démontrer que certains codes pouvaient atteindre la capacité.
Ce n‟est qu‟en 2009 avec l‟introduction des codes polaires qu‟on a pu avoir une famille de codes avec une preuve d‟atteinte de la capacité et une complexité d‟encodage et de décodage réaliste pour des applications pratiques [3]. Ce théorème peut être décomposé en trois parties [4] :
1. Pour tous les canaux discrets sans mémoire, la capacité du canal 𝐶 a les propriétés suivantes. Pour tout 𝜀 > 0 et 𝑅 < C, pour 𝑁 assez grand, il existe un code de longueur 𝑁 et de rendement 𝑅 muni d‟un algorithme de décodage tel que la probabilité d‟erreur bloc maximale soit < 𝜀.

Canal AWGN

Le canal AWGN possède une entrée et une sortie continue en amplitude (le canal reste discret en temps). La perturbation (bruit) introduite par le canal est l‟addition d‟un bruit blanc de densité spectrale de puissance constante et de distribution gaussienne en amplitude. Le signal reçu peut s‟exprimer par : 𝑌 = 𝑋 + 𝐸 où 𝐸 suit une loi normale de moyenne nulle et de variance 𝜎2 (Figure 1.4). La perturbation ou le bruit est caractérisé par cette variance qu‟on obtient à partir de la somme des variances des différents bruits rencontrés sur la transmission supposée tous gaussiens et indépendants (bruit d‟émission spontanée, bruit thermique, bruit de battement entre le signal et le bruit, bruit de battement entre le bruit et lui-même…).

Théorie des codes

Dans l‟article de Shannon 1948 [1], Shannon a prouvé qu‟il était possible de transmettre un débit 𝑅 de manière fiable sur un canal non-fiable de capacité 𝐶 tant que 𝑅 < 𝐶, par contre pour le cas inverse, on ne peut pas garantir la fiabilité du message reçu à travers le canal [6]. Dans ce papier, Shannon aussi introduit la notion de “codes” comme un ensemble fini de vecteurs dans l‟alphabet d‟entrée. Si on suppose que tous les vecteurs possèdent une longueur identique 𝑁 et que 𝑁 est égal à (qui peut être codé sur𝐾 bits), il faut alors 𝑁 utilisations du canal pour transmettre 𝐾 bits. Le débit (rendement du code) est donc égal : bits par utilisation du canal.
Avec K qui représente la taille en bits du message à coder et M qui représente la redondance apportée par le codage de canal. En réception, c‟est le décodeur qui, à partir du vecteur 𝑦 reçu et de l‟alphabet de sortie, va en déduire le mot de code 𝐶 envoyé par l‟encodeur. Si le canal introduit des erreurs, alors on ne peut pas identifier le mot de code transmis de manière certaine. On peut cependant trouver le mot de code le plus probable en maximisant la probabilité (𝑦|𝑐). Le décodage alors effectué est dit décodage à Maximum de Vraisemblance, qui fonction en minimisant la distance entre le mot décodé et tous les mots de code dans l‟alphabet. Shannon a prouvé qu‟il existe des codes de rendement arbitrairement proche de la capacité pour lesquels la probabilité d‟erreur du décodeur ML tend vers 0 quand la longueur du code tend vers l‟infini. Ce théorème ne donne cependant pas la méthode permettant de construire ces codes. De plus, même si un code (aléatoire) atteignant la capacité pour un certain rendement était connu, la réalisation de l‟encodage ainsi que du décodage par des algorithmes efficaces (polynomiaux) reste un problème ouvert. Depuis longtemps, les scientifiques ont cherché à trouver des codes qui atteignent ou s‟approchent de la capacité de canal. Pour une efficacité de codage et de décodage, Elias et Golay introduisent le concept de code linéaire en définissant des codes comme un sous-espace vectoriel d‟un espace vectoriel de dimension finie, c‟est à dire, au lieu de stocker une liste de mots de code dans l‟encodeur, on fait une simple multiplication matricielle [7]. Ils ont ainsi montré que la détection à Maximum de Vraisemblance (ML) pour un canal binaire symétrique (BSC) était un problème NP complet. Dans les années 1960, les codes RS [8] ont été inventés et ils peuvent être décodés par un algorithme qui est appelé algorithme de Berlekamp Massey. La complexité de ces algorithmes limite la longueur des codes (toujours fixée à (255, 𝐾)) à quelques centaines de symboles entrainant un écart entre les performances des codes et la limite donnée par Shannon largement supérieur à 3 dB. En 1993, les turbo codes [9] sont présentés par C. Berrou et provoquent un émoi dans la communauté scientifique concernée puisqu‟ils permettent de s‟approcher très près (moins de 0.5 dB) de la borne de Shannon sur un canal AWGN tout en présentant une complexité de décodage raisonnable. Le décodage s‟opère de façon itérative en échangeant à travers des entre laceurs les informations extrinsèques issues des décodeurs de canal à sorties pondérées. Enfin en 1996, MacKay et Neal redécouvrent les codes LDPC qui avaient été inventés pour la première fois avant eux par Gallager en 1962, et généralisent l‟emploi des graphes de Tanner pour modéliser les échanges d‟informations extrinsèques entre nœuds de variable et nœuds de parité.

Distance minimale de Hamming

La distance minimale de Hamming notée 𝑑 𝑖𝑛 est définie comme la plus petite des distances entre deux mots de code distincts, constitue un paramètre très important dans la conception d‟un code efficace. Par exemple un mot de code qui contient 𝑁 bits codés à partir de 𝐾 bits avec une redondance de 𝑀 bits est noté (𝑁, 𝐾, 𝑀) alors le pouvoir de détection du code, correspondant au nombre maximal d’erreurs détectables dans un mot dépend directement de la distance de Hamming minimale. Il est déterminé par 𝑡 = 𝑑 – 1 qui capitale pour un bon code correcteur d‟erreur. Le pouvoir de correction, défini comme le nombre maximal d’erreurs corrigibles dans un mot est donné par [10.69].

Les codes blocs et les codes convolutifs

Deux grandes familles de FEC (codes correcteurs d‟erreurs) sont à distinguer : les codes convolutifs et les codes en blocs. Par définition, les codes convolutifs calculent la redondance de manière continue à mesure que le flot de données arrive alors que les codes en blocs génèrent la redondance par blocs de données. Quelle que soit la nature du code, il est dit systématique si l‟on retrouve les 𝐾 bits d‟information utiles 𝑀 dans le mot codé 𝐶. Cela se traduit dans la représentation matricielle par le fait qu’une partie de la matrice génératrice est composée de la matrice identité. Cette représentation est appelée la forme systématique de la matrice génératrice.

Les codes convolutifs

Les codes convolutifs, aussi appelés codes convolutionnels ont été initialement inventés en 1954 par Elias [14]. Le principe des codes convolutifs est de considérer le message à émettre comme une séquence semi-infinie de symboles. Il consiste à passer le message utile à coder dans une succession de registre à décalage. Il y a 3 paramètres des codes convolutifs : 𝐾 (bits informations utiles), 𝐵 (le nombre de registres à décalage du code), 𝑁 (bits codés après le codeur). On définit aussi la longueur de contrainte du code qui est égale à : 𝐵 + 1. Pour un codeur convolutif on utilise le plus souvent un schéma de codage de rendement R. Parmi les codes convolutifs, il existe deux catégories : les codes non systématiques (NSC : Non Systematic convolutional), et les codes systématiques récursifs (ou RSC : Recursive Systematic Convolutional codes). Prenons l‟exemple d‟un code convolutif (2, 1,3) ou 2 est le nombre de sorties, 1 nombre d‟entrées et 3 nombre des registres. 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 =. 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) = [𝑐 (t) 𝑐 (t)] correspondant à l’entrée B(t) vaut :

Les différentes représentations d’un code en bloc linéaire

Il est possible de représenter un code en bloc linéaire sous trois formes principales : forme matricielle, forme d‟une matrice de parité ou bien forme d‟un factor graph. L‟application est linéaire car pour tout couple de messages (u,v) () 2 et tout couple de scalaires (ℷ;µ) ( ) 2 , nous avons l(ℷu + µv) = ℷl(u)+ µl(v) . Il est alors possible de définir la matrice correspondante à cette application linéaire, G de K lignes et N colonnes, et telle que le mot de code C du message u est calculé par :