Conception d’un logiciel de codage et correcteur d’erreurs

La théorie des communications s’intéresse aux moyens de transmettre une information depuis une source jusqu’à un destinataire. La nature de la source peut être très variée. Il peut s’agir par exemple d’une voix, d’un signal électromagnétique ou d’une séquence de symboles binaires. Le canal peut être une ligne téléphonique, une liaison radio ou encore un support magnétique ou optique : bande magnétique ou disque compact. Le canal sera généralement perturbé par un bruit qui dépendra de l’environnement et de la nature canal : perturbations électriques, rayures, … . Le codeur représente l’ensemble des opérations effectuées sur la sortie de la source avant la transmission. Ces opérations peuvent être, par exemple, la modulation, la compression ou encore l’ajout d’une redondance pour combattre les effets du bruit. Elles ont pour but de rendre la sortie de la source compatible avec le canal. Enfin, le décodeur devra être capable, à partir de la sortie du canal de restituer de façon acceptable l’information fournie par la source.

La technique de codage est utilisée depuis longtemps. De nos jours, le codage est une technique employée pour la communication, à coté d’autres techniques, matérielles ou logicielles, comme les protocoles de communications ou algorithme distribué. Il évoque toujours un procédé de transformation d’un objet, avec le procédé inverse, appelé le décodage qui permet de restituer l’objet initial.

Le codage s’applique à une suite de symbole émis par une source d’information. Cette suite peut être une suite discrète d’élément pris dans un ensemble fini ou bien il peut s’agit d’une fonction continue caractérisée par son amplitude en fonction du temps. Une source continue peut être transformée en source discrète par des techniques d’échantillonnage. Le codage consiste en la transformation de la suite émise de la source en une nouvelle suite qui est alors envoyée dans un canal de transmission.

Les codages que nous étudierons consistent toujours à la transformation d’une suite de symboles prise dans un ensemble fini. Cet ensemble est appelé alphabet. Souvent l’alphabet sera l’ensemble {0, 1}, c’est un alphabet binaire ou code binaire qui utilise deux symboles.

La transmission des informations à travers un système de communication risque d’introduire des erreurs sur les suites de symboles qu’on transmet du fait du bruit. Alors le message ‘Y’, à la sortie du canal de transmission, peut être différent au message émis de l’entrée. Dans notre cas, alphabet à deux symboles, l’erreur peut se traduire par des changements de ‘0’ en ‘1’, ou de ‘1’ en ‘0’.

Le problème de la transmission est la suivante : un expéditeur A envoie un message m à B; durant la transmission de ce message, des erreurs se produisent éventuellement, et B reçoit un message m’ qui comporte peut-être des erreurs. Il s’agit de trouver comment faire pour que B, d’une part détecte l’existence d’erreurs, d’autre part, si elles ne sont pas trop nombreuses, sache les corriger. Pour lutter contre le bruit du au canal, on utilise des blocs de n symboles pour transmettre k symboles d’information. Un tel bloc de longueur n est appelé un mot de code, avec k≤ n.

Codage [1] [2] 

Considérons un ensemble fini S de message de k symboles d’information à transmettre, les symboles prenant leur valeur dans un alphabet K. dans le cas de codage binaire, utilisons un alphabet à deux symboles que nous pouvons noter :{0,1}=K. supposons que le nombre d’éléments de S est une puissance de entière de 2 (2 k ) et S est identifié à ensemble Kk . Cette identification correspond à un codage sans redondance conduit à l’impossibilité de détecter la moindre erreur de transmission dans le cas de perturbation.

Pour pouvoir détecter les erreurs, il faut plonger S dans un ensemble plus grande de telle manière que les erreurs les plus courantes fassent passer d’une suite correspondant à un message à une autre suite qui n’est pas un message. Il faut utiliser des suite de n symboles de longueur supérieure à k, c’est-à-dire ajouter n-k symboles supplémentaires dits : redondance , Pour détecter et corriger les erreurs pendant la transmission, il faut donc ajouter des symboles (symbole de contrôle) aux symboles correspondant à l’information que l’on veut transmettre. Cet ajout se fait selon une règle de codage connu par l’émetteur et par le récepteur. Ainsi, le décodeur vérifiera si la suite qu’il vient de recevoir satisfait ou non, à la règle C choisie. Si elle ne la satisfait pas alors il est sûr qu’au moins une erreur est advenue.

Nous pouvons choisir un code en fonction des paramètres suivants :
– la distance minimale
– la capacité de correction d’erreur
– le temps d’attente pour avoir le premier mot décodé
Le codage d’un canal aussi appelé codage détecteur et/ou correcteur est une fonction spécifique des transmissions numériques, qui n’a pas son équivalent en transmission analogique. Cette opération permet d’améliorer la qualité la transmission.

Décodage d’un code linéaire 

Définition
On appelle décodage tout moyen qui permet de corriger toutes les erreurs qui effectuent les mots du code C, c’est-à-dire retrouver le mot x émis du code à partir du mot reçu y. Il existe 3 méthodes de décodage. La linéarité simplifie grandement le décodage. Le nombre t d’erreurs maximales assurément corrigibles est le plus grand entier strictement inférieur à 3/2 c’est-à-dire t = 1.

Décodage de voisin le plus proche 

Elle consiste à décoder le mot reçu y comme le mot de code x le plus proche dans la distance de Hamming, c’est-à-dire rechercher le vecteur d’erreur e qui est le plus faible poids. Ainsi nous pouvons comparer y avec tous les q k mots de code, il faut calculer toutes les distances d’un mot donné à chacun des mots de code. Lorsque la taille des paramètres augmente, cette méthode devient impraticable, alors ceci n’est pas valable que pour les petits codes (k petit).

Décodage par syndrome utilisant le tableau de décodage

Coder chaque vecteur reçu par le mot de code qui est dans le même colonne du tableau, en utilisant la matrice de contrôle.