à‰tude des codes ldpc réguliers.

II.3.4. Génération du mot de code

? Matrice de génération de code

C'est une matrice notée G [21], elle sert à générer le mot de code C_m à partir du message X_m soit :

C_m=X_m.G II.4

Nous nous intéressons à des codes systématiques, la matrice G est donc de la forme :

G=[P Ik] II.5

G est une matrice (k, n), P une matrice (k, n-k) et Ik la matrice identité (k, k).

? Principe de réalisation du codeur

Chaque bit de parité s'exprime donc par [21] :

bi = .m1 p1

?? II.6
1=1

En binaire les _Pji E {0, 1} et les bi sont obtenus par une simple addition binaire.

Le principe de la réalisation technique en est donc simple, il suffit de disposer de deux registres à décalage et un inverseur (switch électronique) ce qui donne la figure II.6 :

Figure II.6 : Principe de réalisation du codeur

II.3.5. Détection des erreurs de transmission

Pour détecter les erreurs de transmission, on doit tenir compte de deux facteurs qui sont les suivants [21] :

? Matrice de contrôle de parité

Nous définissons un espace dual engendré par la matrice H tel que :

H = [In-k PT] II.7

En décomposant les matrices nous obtenons :

G.HT = [P Ik] IIIn_k

?? ] = P + P = 0 II.8

En effet, P est constitué d'éléments binaires tels que : a + a = 0.

D'où la relation fondamentale :

G.HT = 0 II.9

? Syndrome :

On appelle syndrome le vecteur s de dimension M défini par :

ST = Hx^T II.10

Si S est un vecteur nul alors x est un mot de code, sinon le vecteur x contient des bits erronés. Il est possible de détecter la présence d'erreurs dans un mot de code par le calcul du syndrome.

Nous pouvons établir la relation servant de base à la détection d'erreurs pour tout mot de code:

G_m.H^T = X_m.G.H^T = 0 II.11

Le détecteur va utiliser cette relation. En effet, si le mot du code reçu Y_m est entaché d'erreurs, nous pouvons l'exprimer sous la forme :

Code reçu = code émis + erreur Y_m = C_m + E_m II.12

En effectuant le contrôle :

Y_m.H^T = C_m.H^T + Em. H^T = Em. H^T II.13

(v0, v1, ..., vn-1) ? C (vn-1, ^v0,..., vn-2) ? C

S'il n'y a pas eu des erreurs de transmission, alors on a :

Em. H^T = 0 II.14

Em. H^T est par définition le syndrome de l'erreur S_m , avec :

S_m = Y_m. Em. H^T = Em. H^T II.15

Le syndrome ne dépend que de l'erreur de transmission commise et non du mot du code.

II.3.6. Famille des codes en blocs

Nous donnons ci-dessous une liste non exhaustive de familles de code en bloc linéaires. Les codes que nous considérons sont binaires ou sont définis sur une extension du corps à deux éléments. Nous noterons (n, k, d) un code linéaire défini sur un alphabet à q éléments de longueur n, de dimension k et de distance minimale d.

Nous avons choisi de ne lister ici que des familles de codes ayant un intérêt pratique (s'ils sont utilisés, typiquement Reed-Solomon ou BCH, ou susceptibles de l'être comme les codes géométriques) ou théorique [12].

? Les codes cycliques

Les codes cycliques forment une sous-classe des codes linéaires, et sont les plus utilisés en pratique [23]. Ils conjuguent en effet de nombreux avantages : leur mises-en oeuvre (codage/décodage) est facile, ils offrent une gamme étendue de codes, avec de nombreux choix de paramètres (n, k, d), et enfin permettent de corriger différents types d'erreurs, isolées ou par paquets.

Les codes cycliques sont des codes linéaires stables par permutation circulaire des coordonnées. Ils ont une forte structure mathématique : si on les voit comme des espaces vectoriels de polynômes (les coordonnées des mots deviennent les coefficients des polynômes). Un code linéaire C est dit cyclique s'il est stable par permutation circulaire des coordonnées. Donc, on peut écrire :

Si l'on représente le vecteur ci-dessus par le polynôme v(x) = v0 + v1x +.... + _vn-1xn-1, alors la permutation circulaire d'une unité à droite correspond à la multiplication par x modulo xⁿ-1.

? Codes de Hamming :

Ce code est lui aussi très simple mais a un bien meilleur taux de transmission. Pour le définir il est nécessaire d'introduire la notion de matrice de parité :

C'est une matrice H de taille (n - k) X n qui a pour noyau le code C tout entier. Ainsi si c ? C, on aura toujours Hc^T = 0, et uniquement dans ce cas là. Remarquons qu'un même code C peut avoir plusieurs matrices de parité différentes, de même qu'il peut avoir plusieurs matrices génératrices différentes.

On appellera syndrome d'un mot c l'élément S obtenu en calculant S = Hc.

Le code de Hamming est donc un code binaire défini par sa matrice de parité plutôt que par sa matrice génératrice [24]. C'est la matrice de dimension r X (2^r -1) qui contient toutes les colonnes non nulles distinctes que l'on peut écrire sur r bits. Ainsi pour r = 3 on a :

? Les codes BCH (Bose-Chaudhuri-Hocquenghem)

Les codes BCH (Bose-Chaudhuri-Hocquenghem) binaires sont des codes cycliques particuliers. La famille des codes BCH contient les codes de Reed-Solomon qui servent pour la lecture des CD [25]. Lorsque le cardinal de l'alphabet sur lequel un code de Reed-Solomon est défini est une puissance de 2, alors il est possible de définir son sous-code binaire (les mots de code ayant des coefficients 0 ou 1).

Ce sous-code est stable par addition (la somme de deux mots binaires est un mot binaire) et donc linéaire. Un code de Reed-Solomon (n, k, d) avec q = 2m fournira un code BCH binaire (n, kÇ d'), avec k' est la nouvelle dimension et d' est la nouvelle distance du code BCH obtenu à partir du code de Reed-Solomon. La longueur est conservée, en revanche la distance minimale peut augmenter, et la dimension diminue fortement. Les valeurs exactes de d' et k' sont dépendantes de la structure du corps fini et ne peuvent être décrites par des formules closes simples.

Si g(x) est le polynôme générateur du code Reed-Solomon, alors, le code BCH aura pour générateur le polynôme binaire de plus bas degré multiple de g(x). Le décodage d'un code BCH sera très similaire au décodage du code de Reed-Solomon dont il est issu.

? Les codes de Reed-Solomon

Les codes de Reed-Solomon ont été développés par Reed et Solomon dans les années 50 [26] mais avaient déjà été construits par Bush [27] un peu avant, dans un autre contexte. Ces codes sont certainement les codes par blocs les plus utilisés pour la correction d?erreurs en étant présents dans les CD, les DVD et la plupart des supports de données numériques. Ils sont trés utilisés car ils sont extrêmaux du point de vue de la capacité de correction.

Les codes de Reed-Solomon sont des codes cycliques q-aires de longueur n = q -1. Le polynôme générateur d'un code de Reed-Solomon est de la forme :

g (x )= fl(x - a^??)

??-1 II.16
??=1

Où a est un élément primitif du corps fini à q éléments. Il a pour degré d-1. Le code correspondant au polynôme générateur ci-dessus a pour longueur n = q-1, pour distance minimale d et

pour dimension k = n - d + 1. Nous avons donc affaire à des codes (n, k, n - k + 1).

Ces codes sont efficaces dans la correction d'erreurs par paquet du fait de leur structure. Ils ont été employés dans les communications spatiales et restent encore utilisées dans les codes concaténés.