à‰tude des codes ldpc réguliers.

III.4. Encodage des codes LDPC

Les travaux de T.J. Richardson et R.L Urbanke [33] ont montré que la matrice de contrôle doit subir un prétraitement avant l'opération d'encodage. L'objectif de ce prétraitement est de mettre la matrice H de taille m × n sous une forme presque triangulaire inférieure, comme illustré sur la Figure III.2, en utilisant uniquement des permutations de lignes ou de colonnes.

Cette matrice est composée de 6 sous-matrices creuses, notées A, B, C, D, E et d'une sous-matrice triangulaire inférieure T de taille m-g × m-g. Une fois que le prétraitement de H est achevé, le principe d'encodage est basé sur la résolution du système représenté par l'équation matricielle suivante :

cH^T = 0 III.3

Figure III.2: Représentation sous forme pseudo-triangulaire inférieure de la matrice H.

L'algorithme de prétraitement est décrit ci-dessous de manière succincte :

1- La triangulation est une permutation des lignes ou des colonnes pour avoir une approximation de la matrice H sous forme triangulaire inférieure :

H = A B T

C D E

2- Le contrôle de rang est l'élimination gaussienne pour effectuer la pré multiplication

par	?? 0 -????^-1 ?? .

Cette pré multiplication permet d'obtenir :

?? 0 ?? ?? ?? ?? ?? ??

-???? -1 ?? ?? ?? ?? = -????^-1?? + ?? - ????^-1?? + ?? 0

Il est nécessaire de vérifier que -ET^-1B+D est inversible pour que le processus de prétraitement soit utilisable pour la résolution de l'équation III.3.

Lors de la résolution de l'équation III.3, le mot de code recherché est décomposé en trois parties : c = (d, r1, r2) où d est la partie systématique (c'est-à-dire un élément de la base canonique du sous espace vectoriel de dimension n-m comme indiqué sur la figure III.2, où les bits de redondances recherchés sont séparés en deux vecteurs r1 et r2 de tailles respectives g et m-g. Après multiplication à droite par la

matrice ?? 0

-????^-1 ?? , l'équation III.3 devient:

?????? + ????1^?? + ????2^??= 0 III.4

-????^-1?? + ?? ???? + -????^-1?? + ?? ??1^?? = 0 III.5

L'équation III.5 permet de trouver ??1^?? en inversant Ö = -????^-1?? + ??. L'équation III.4 permet ensuite de trouver ?????? . Remarquons que la phase de prétraitement est une phase qui nécessite de nombreuses opérations coûteuses en temps de calcul. Par contre, toutes les opérations répétées au cours de l'encodage ont une complexité en o(n) excepté la multiplication de -????^-1?? + ?? ???? par la matrice carrée (-Ö^-1) de taille g x g qui après insertion n'est plus creuse d'où une complexité en o(g²) . T.J. Richardson et R.L Urbanke [33] ont aussi montré que l'on peut obtenir une valeur de g égale à une faible fraction de n : g = ???? où ?? est un coefficient suffisamment faible pour que o(g²) << o(n) pour des valeurs de n allant jusqu'à 10⁵. Ainsi, la complexité de l'approche d'encodage est de complexité O(n).

Ces codes peuvent être raccourcis par élimination des colonnes de la matrice de parité.