Classification des codes
- Introduction
De nos jours, nous vivons dans un monde où les communications jouent un rôle primordial tant par la place qu’elles occupent dans le quotidien de chacun, que par les enjeux économiques et technologiques dont elles font l’objet. Nous avons sans cesse besoin d’augmenter les débits de transmission tout en gardant ou en améliorant la qualité de ceux-ci. Mais sans un souci de fiabilité, tous les efforts d’amélioration seraient ridicules car cela impliquerait forcément à ce que certaines données soient retransmises. C’est dans la course au débit et à la fiabilité que les codes entrent en jeux.
La théorie du codage est l’étude des méthodes permettant le transfert d’informations de
façons encaqué et précise. Cette théorie est utilisée dans de multiples champs d’applications. On la retrouve dans l’enregistrement des disques compacts, dans la transmission d’information
sur les réseaux ou encore dans les communications par satellites pour n’en nommer que
quelques-uns.
Le présent recherche consiste a présenter et a analyser les déférents class des codes.
- Théorie de l’information :
On définit un canal de transmission comme un système physique permettant la transmission d’une information entre deux points distants. Le taux d’erreurs binaire (TEB) d’un message est le rapport du nombre de bits erronés par le nombre de bits du message.
En 1948, Shannon énonce dans « A Mathematical Theory of Information » le théorème fondamental de la théorie de l’information : Tout canal de transmission admet un paramètre C, appelé capacité du canal, tel que pour tout > 0 et pour tout R < C, il existe un code de taux R permettant la transmission du message avec un taux d’erreurs binaire de.
En d’autres termes, nous pouvons obtenir des transmissions aussi fiables que l’on veut, en utilisant des codes de taux plus petits que la capacité du canal. Cependant, ce théorème n’indique pas le moyen de construire de tels codes, nous cherchons donc à construire des codes ayant un taux le plus élevé possible (pour des raisons de temps et de coût) et permettant une fiabilité arbitrairement grande. Les codes classiques ne permettent pas d’atteindre cette limite. Nous avons donc développé d’autres systèmes de codages.
- Classification des codes :
- Présentation :
Pour un traitement informatique, c’est-à-dire automatisé, de l’information, nous numérisons le signal à transmettre (une image, un son…). Nous ramenons ainsi celui-ci à une séquence de bits e1e2…. A cause des inévitables parasites qui détériorent le message, nous ne pouvons pas envoyer cette séquence telle quelle.
Pour améliorer la fiabilité de la transmission des données, une des méthodes de codage les plus simples est alors de répéter chaque bit. La séquence e1e2… sera ainsi transmise sous la forme e1e1e2e2…. Lors de la réception du message, le décodeur peut ainsi comparer chaque couple de bits reçus,s’ils sont différents alors il y a détection d’erreur. Nous voyions ainsi qu’en doublant la longueur du message (mais aussi le temps de transmission), nous parvenons à détecter d’éventuelles erreurs.
Toutefois, ce codage simple ne permet pas de les corriger. Pour cela, nous pouvons tripler les bits. Si nous considérons (ce qui est plus que raisonnable) qu’il y a au maximum une erreur pour chaque séquence de 3 bits, alors il est possible de les corriger : le décodeur n’a qu’à choisir le symbole qui apparaît deux fois dans chaque triplet reçu.
Si le canal de transmission n’est pas trop parasité, il paraît inutile d’ajouter autant de redondance au message transmis. Nous pouvons ainsi utiliser le système du bit de parité (qui ne permet que la détection d’erreurs) : le message est découpé en blocs de k bits, auxquels nous ajoutons un bit tel qu’il y ait un nombre pair de 1 dans le bloc transmis
Pour approcher au mieux la capacité C du canal si, conformément au théorème de Shannon, l’entropie de la source qui est inférieur à C nous pouvons ajouter de la redondance dans le codage de la source afin de diminuer les erreurs de transmission. C’est le problème du codage de canal. A côté des premiers codes empiriques (bit deparité, répétition,…) deux grandes catégories de codes ont été développées et sont actuellement utilisées en faisant l’objet permanent de perfectionnements :
- Les codes en blocs.
- Les codes en treillis.
La figure ci-dessous donne un simple résumé de la grande famille de codage. Dans la première classe (à droite sur la figure), citons les codes les plus célèbres comme les codes BCH, Reed Muller, Reed Solomon et Goppa, Golay et Hamming. La deuxième classe (à gauche sur la figure) est moins riche en variété mais présente beaucoup plus de souplesse surtout dans le choix des paramètres et des algorithmes de décodage disponibles. Citons par exemple, les codes convolutifs binaires systématiques récursifs très utilisés dans les modulations codées (TCM) et les codes concaténés parallèles (Turbo Codes).
- Codes linéaires :
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 F2n, que l’on écrira comme des vecteurs lignes. Un code linéaire de longueur n est un sous espace vectoriel C inclus dans F2n. 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)ϵ F2n 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), le codage des codes linéaires repose sur
Matrice génératrice
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 F2k, 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 F2k), 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.
- Code de Hamming :
Un code de Hamming est un code correcteur linéaire. Il permet la détection et la correction automatique d’une erreur si elle ne porte que sur une lettre du message.
Un code de Hamming est parfait, ce qui signifie que pour une longueur de code donnée, il n’existe pas d’autre code plus compact ayant la même capacité de correction. En ce sens, son rendement est maximal.
Le code de Hamming est de paramètres (2m −1, 2m – m – 1 ,3), il permet de détecter 3 erreurs et de corriger une seule.
Plusieurs méthodes permettent de construire un code de Hamming. Une approche consiste à rechercher les codes cycliques de distance minimale égale à trois, le code apparaît alors comme un cas particulier de code BCH.
❖ Distance de Hamming
Les messages transmis sont supposés découpés en blocs (ou mots) de longueur n écrits avec l’alphabet {0,1}.Un code (binaire) est un sous-ensemble C de l’ensemble {0,1}n de tous les mots possibles. On dit que n est la longueur de C.
La distance de Hamming entre deux mots x = (x1 … xn) t y = (y1 … yn), que l’on notera d(x,y) est le nombre d’indices i tels que Xi ≠ Yi. C’est bien une distance sur {0,1}n La distance minimale du code C est le minimum des d(x,y) pour x et y des mots différents de C (on suppose que C a au moins 2 mots !). On la notera toujours d.
- Codes polynomiaux :
Dans ces codes, on suppose que les bits d’une chaîne de caractères sont les coefficients d’un polynôme. Ces coefficients ne prennent que deux valeurs : 0 ou 1. Un bloc de k bits est vu comme la série des coefficients d’un polynôme comprenant les termes allant de xk − 1à x0.
Les codes polynomiaux forment aussi une catégorie des codes linéaires dont tous les mots peuvent se déduire d’un seul d’entre eux. En plus d’une grande facilité de codage et de contrôle, ils permettent une bonne détection des messages erronés. Ils sont liés à une représentation des n-uples binaire par des polynômes, ce qui leur a valu leur dénomination ou nous allons le détailler dans le chapitre suivant.
- Code Cyclique :
Les codes cycliques ont la propriété d’être stable par permutation circulaire des mots.
T :F2n → F2n
(x1,x2,…….,xn) → (x2,…….,xn,x1)
On identifie Fn à l’algèbre F2[X]/(Xn-1) par (x1,x2,…….,xn) → x1Xn-1+………+xn-1+xn. Ce sont des codes polynomiaux dont le polynôme générateur g(x) divise
(xn +1)
où n est la longueur du code. Cette particularité permet la construction immédiate d’une matrice de contrôle caractéristique de ce type de code et une simplification de la méthode de correction automatique. Pour la détermination des codes cycliques de longueur n, la connaissance diviseurs (xn +1) est essentielle..
- Codes BCH
Les codes BCH(Bose-Chaudhuri-Hocqenghem) sont une extension des codes cycliques, ils sont construits sur un alphabet composé d’un grand ensemble de symboles basés sur les propriétés des corps finis.
Ils sont considérés comme ceux qui ont la plus grande capacité de correction d’erreurs indépendantes, pour une redondance et une longueur donnée.
- Codes Reed –Solomon
Les codes de Reed-Solomon RS(n,k) sont formés de n symboles, avec n = q – 1 au maximum et q = 2s , chaque symbole appartenant à GF(q) qui est le corps de Galois (Galois Field) à q éléments, s représente donc le nombre de bits par symbole. Le nombre t est égal à (n-k)/2 représente le nombre de symboles d’erreurs que ce code sera capable de corriger.
- Codes CRC (Cyclic Redundancy Check)
Une séquence de k symboles binaires d’information est représentée par le polynôme i(x). Soit g(x) un polynôme de degré s. Le mot de code correspondant à i(x) est égal àc(x) =xs i(x)+r(x) où r(x) est le reste de la division de xs i(x) par g(x).
Ces codes permettent de détecter toute rafale (erreurs consécutives) d’erreurs de longueur inférieure ou égale à s.
Conclusion
L’objectif de cette recherche ont et de donné des principes algébriques associées
aux codes linéaires. Pour chacune des principales classes de codes, nous avons présentée les principaux codes utilisés. Pour certains codes, nous avons abordée leur création de différentes
façons a d’illustrer que la méthode de construction d’un code n’est, en général, pas unique.
L’important problème qui consiste à établir l’existence d’un code de paramètres données à et abordée, nous le croyons, d’une façon originale sous l’angle de l’identité de MacWilliams.
A cet effet, nous avons montré comment utiliser l’identité de MacWilliams afin d’exhiber les
seules distributions possibles pour un code de paramètres donnés.
