III.5. Construction des codes LDPC
III.5.1. Une construction géométrique des
codes LDPC
Les codes LDPC peuvent être construits de manière
algébrique à partir de points et de lignes de la
géométrie finie, comme la géométrie Euclidienne et
la géométrie projective définies sur des champs finis
[34]. Une géométrie finie est formée de points et lignes,
qui ont les propriétés suivantes :
(1) chaque ligne à ?? points ;
(2) chaque point appartient à ?? lignes ;
(3) deux points sont connectés par juste une ligne ;
(4) deux lignes sont soit disjointes, soit leur intersection est
un seul point.
Pour chaque type de géométrie, on peut
construire des codes LDPC de type 1 (géométrie Euclidienne) et de
type 2 (géométrie projective), qui sont vraiment connexes et
leurs graphes sont conjugués entre eux : les noeuds des bits
codés d'un graphe sont les noeuds de contrôle pour l'autre graphe.
Pour le type 1, on peut former une matrice de parité H dont les
rangées sont les vecteurs d'incidence des lignes existantes dans la
géométrie finie et les colonnes sont les points. Le graphe
correspondant à cette matrice n'a aucun cycle de longueur 4. Pour un
code LDPC de type 2, la matrice de parité H est la
transposée de la matrice correspondante de type 1 : les rangées
sont les vecteurs d'incidence des points et les colonnes sont les lignes de la
géométrie finie. Les graphes correspondants à ces matrices
n'ont aucun cycle de longueur 4.
Les codes EG-LDPC (basés sur la géométrie
euclidienne) et les codes PG-LDPC (basés sur la géométrie
projective) ont des performances d'erreurs presque identiques [34]. Dans la
construction des codes EG-LDPC de type 1 et 2, on peut éliminer le point
d'origine de la géométrie et toutes les lignes qui passent par
l'origine. Ainsi, on met le code EG-LDPC de type 1 dans une forme cyclique et
le code EG-LDPC de type 2 dans une forme quasi-cyclique. Ceci simplifie le
circuit de codage ; on doit garder en mémoire juste la première
rangée de H et les autres rangées seront ajoutées
à l'aide d'un registre à décalage linéaire. La
différence entre les 4 types de codes (EG-LDPC et PG-LDPC de type 1 et
2) est comment on trouve les positions des valeurs de < 1 > dans la
première rangée de la matrice de parité et les
différents paramètres des codes obtenus. Les formules pour
calculer ces paramètres sont données en [34].
Pour les codes EG-LDPC de type 1, les colonnes
éliminées correspondent aux points d'un ensemble de paquets
parallèles qui ne passent pas par l'origine de la
géométrie finie. On obtient une nouvelle matrice
irrégulière dans laquelle les colonnes ont le même poids,
mais les lignes ont des poids inférieurs. Son noyau donne un code LDPC
irrégulier plus court avec la même distance minimale que le code
initial. Pour les codes EG-LDPC de type 2, il faut mettre la matrice de
parité dans une forme circulaire et on élimine les colonnes
correspondant à un ensemble de lignes. On obtient un code quasi-cyclique
plus court. On doit mentionner que plus on réduit la matrice de
parité, plus on obtient une meilleure performance d'erreurs du code.
| 
