III.3. Les graphes de Tanner pour les codes LDPC
Les graphes de Tanner [29] sont très utiles pour la
représentation des codes en blocs linéaires, parce qu'ils
affichent la relation entre les bits des mots-codes et les noeuds de
contrôle de parité. Ils ont été proposés pour
la première fois par Tanner pour le décodage itératif des
codes LDPC. Les codes LDPC sont représentés sous forme de graphes
bipartites. Un graphe est bipartite si son ensemble de noeuds (í) peut
être divisé en deux sous-ensembles disjoints í, í1
et í2, de façon que chaque arête joint un noeud dans
í1 avec un noeud dans í2 et sans que deux noeuds dans í1
ou dans í2 soient connectés. Pour un code LDPC, les deux
ensembles de noeuds í1 et í2 représentent les n bits du
mot-code (noeuds des variables) et les J équations de contrôle de
parité qui doivent être satisfaites par les bits codés
(noeuds de contrôle). Toutes les connexions sont faites entre chaque
noeud de bit codé et ses noeuds de contrôle correspondants (qu'on
vérifie dans la somme de contrôle).
Un chemin dans un graphe est une séquence de noeuds et
d'arêtes, qui commence et finit par des noeuds, tel que chaque
arête est incidente avec les noeuds qui la précèdent et la
suivent et aucun noeud n'apparaît plus d'une fois. La longueur d'un
chemin est donnée par le nombre d'arêtes formant le chemin. Un
chemin qui commence et finit avec le même noeud s'appelle cycle. Si un
graphe bipartite contient des cycles, ces cycles ont des longueurs paires. La
longueur du plus court cycle dans le graphe s'appelle le
périmètre du graphe.
Pour un code LDPC régulier, les degrés de tous
les noeuds de bits codés sont égaux à ?? (le poids de
chaque colonne de la matrice H) et les degrés de tous les
noeuds de contrôle sont égaux à ?? (le poids de chaque
rangée de la matrice H). Ainsi, le graphe de Tanner est
régulier. Il ne peut pas y avoir deux bits codés qui peuvent
être vérifiés par deux équations différentes,
donc le graphe ne va contenir aucun cycle de longueur 4. Pour décoder un
graphe d'un code LDPC avec le décodage itératif, il est important
que le graphe de Tanner du code ne contienne aucun cycle de courte longueur (4
ou 6, mais en particulier 4), parce que les cycles courts limitent la
performance d'erreurs et empêchent le processus de décodage de
converger vers la performance obtenue avec le décodage à
vraisemblance maximale MLD (Maximum Likelihood Decoding) [32].
Avec un gap g petit si possible. Nous verrons dans la
suite comment ceci peut être accompli efficacement ;
| 
