Chapitre III :
Les codes LDPC réguliers
Et résultats de simulation
Un code LDPC est un code dont la matrice de contrôle de
parité H est de faible densité (matrice creuse). La
faible densité signifie qu?il y a plus de « 0 » que de «
1 » dans la matrice H [31]. Un code
III.1. Introduction
Les codes LDPC ont été découverts par
Gallager [28], dans les années 60, mais il a proposé seulement
une méthode générale pour construire des codes LDPC
pseudo-aléatoires ; les bons codes LDPC sont
générés par ordinateur (en particulier les codes longs) et
leur décodage est très complexe dû au manque de structure.
Ces codes ont été ignorés jusqu'en 1981 quand Tanner leur
a donné une nouvelle interprétation d'un point de vue graphique
[29]. Sa théorie a été aussi ignorée pour les
prochaines 14 années jusqu'au jour où quelques chercheurs en
codage ont commencé à étudier les codes en graphes et le
décodage itératif.
La première construction algébrique et
systématique de codes LDPC basée sur les géométries
finies a été proposée par Kou, Lin et Fossorier dans les
années 2000 [30]. La classe de codes LDPC à
géométrie finie possède une bonne distance minimale et les
graphes de Tanner n'ont pas de cycles courts. Leur structure est cyclique ou
quasi-cyclique, ce qui fait que leur codage est simple et peut être
réalisé avec des registres à décalage
linéaire. Avec ce type de codes de grande longueur, on obtient de
très bonnes performances d'erreurs.
La construction et le décodage des codes LDPC peuvent
être fait de plusieurs manières. Un code LDPC est
caractérisé par sa matrice de parité.
III.2. Définition des codes LDPC
Un code LDPC régulier est défini comme l'espace
nul d'une matrice de contrôle de parité H [28], qui a les
propriétés suivantes :
(1) chaque ligne à p valeurs de 1 ;
(2) chaque colonne à y valeurs de 1 ;
(3) le nombre de 1 en commun entre deux colonnes quelconques,
désigné parA, n'est pas plus grand que 1 (donc A = 0 ou A = 1)
;
(4) p et y ont des valeurs petites en comparaison avec la
longueur du code et avec le nombre de lignes de la matrice H.
L'irrégularité de ces codes se spécifie
à travers deux polynômes A(x) et p (x):
LDPC peut être représenté sous forme
matricielle ou bien sous la forme d'un graphe bipartite (représentation
de Tanner). Par exemple, la matrice suivante :
|
H =
|
1 0 0 0 1 0 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 1
1
|
Figure III.1 : Graphe bipartite d'un code LDPC.
Si toutes les colonnes ou toutes les lignes de H
n'ont pas le même poids, le code LDPC s'appelle code LDPC
irrégulier.
La matrice peut être représentée par le
graphe de la figure III.1. Les lignes de la matrice sont
représentées par des carrés et sont appelées noeuds
de contrôle, les colonnes de la matrice sont représentées
par des cercles et sont appelées noeuds de données et les «
1 » représentent les arrêtes du graphe.
Il y a deux familles de codes LDPC : les codes
réguliers ou quasi-cycliques qui feront l'objet de notre étude et
les codes irréguliers. Les codes LDPC réguliers sont les codes
dont le nombre de « 1 » par ligne et le nombre de « 1 » par
colonne sont constants. Par extension, les codes LDPC irréguliers sont
les codes définis par des matrices de contrôle de parité
où le nombre de « 1 » par ligne ou par colonne n'est pas
constant.
?? ?? = ????????-1
??=2 III.1
?? ?? = ????????-1 III.2
??=2
| 
