III.5.4. Les codes LDPC quasi-cycliques ou
réguliers
? Construction des codes LDPC quasi-cycliques
réguliers par décomposition circulaire
Cette méthode consiste en la décomposition d'une
matrice carrée, régulière et circulaire en plusieurs
matrices circulaires de mêmes dimensions, mais avec des poids
différents [34]. On obtient ces nouvelles matrices à partir de
chaque colonne de la matrice de parité initiale, qui est
décomposée en plusieurs colonnes de même longueur. Le poids
de la colonne initiale est partagé parmi les différentes
colonnes. À partir de chaque nouvelle colonne ainsi formée, on
forme une matrice circulaire par permutations circulaires successives de la
colonne en bas. La méthode présentée s'appelle la
décomposition des colonnes d'une matrice de parité.
De même, on peut décomposer la matrice initiale
en descendants, en décomposant sa première ligne en plusieurs
lignes et ensuite en faisant des permutations circulaires à la droite de
chaque nouvelle ligne. Cette méthode s'appelle la décomposition
de rangée. Si la matrice initiale est une matrice creuse, la matrice
obtenue est aussi une matrice creuse de densité plus faible, qui donne
un code LDPC quasi-cyclique dont le graphe de Tanner n'a pas de cycles de
longueur 4.
Des matrices creuses circulaires peuvent être
construites à partir des vecteurs d'incidence des lignes dans une
géométrie Euclidienne ou projective. De plus, il n'existe pas
deux lignes (ou deux colonnes) dans la même matrice ou dans
différentes matrices circulaires ayant plus d'une valeur de 1 en commun.
En conséquence, les codes LDPC quasi-cycliques peuvent être
construits en décomposant une ou un groupe de ces matrices circulaires
géométriques [36].
? Les codes LDPC quasi-cycliques (QC) réguliers
pour un codage rapide et pratique
Par rapport aux codes LDPC construits de manière
aléatoire, la matrice de parité d'un code QC-LDPC consiste en
plusieurs matrices de permutation ou matrices nulles. Ainsi, la mémoire
de stockage peut être réduite considérablement (il suffit
de mémoriser les premières rangées de chaque sous-matrice
: les autres rangées sont formées par permutations circulaires).
Cette structure est orientée sur la réalisation d'un
décodeur plus efficace. Ce qui est important est que cette nouvelle
structure de matrice de code LDPC ne diminue pas les performances du code.
Il a été démontré que le
périmètre d'un code QC-LDPC est limité en haut par un
certain nombre qui est déterminé par les positions des matrices
circulaires de permutations [37]. On peut donc obtenir de bons performances du
code en contrôlant la structure des cycles.
Une classe spéciale de codes LDPC quasi-cycliques sont
les codes LDPC de type bloc (B-LDPC) qui possèdent un algorithme de
codage efficace en raison de la structure simple de leurs matrices de
parité. Avec l'implémentation efficace du codeur et du
décodeur des codes B-LDPC et leurs bonnes performances
représentent un axe très prometteur pour l'implémentation
des systèmes de codage LDPC en temps réel. Les codes B-LDPC sont
construits comme des codes QC-LDPC irréguliers avec des matrices de
parité presque triangulaires inférieures, de sorte qu'ils aient
un algorithme de codage efficace, un bon palier de bruit et un plancher
d'erreurs bas. Leur complexité ne dépend pas de manière
linéaire de la taille des matrices de parité.
Pour la construction des codes B-LDPC, au lieu de faire la
multiplication entre la matrice de parité et le vecteur de message, on
construit un système d'équations composé par des
multiplications de matrices et de vecteurs de taille inférieure. Ainsi,
on obtient un codage plus rapide et une structure plus simple.
Quand il n'y a pas de sous-matrices nulles dans la structure
de H, le code est régulier et le rendement du code est
supérieur au rendement d'un code irrégulier parce que dans ce cas
la matrice H possède un rang maximal (si H est
triangulaire inférieure ou supérieure avec des
éléments non-nuls sur la diagonale principale, H a le
rang maximum).
Dans [38], les auteurs proposent une méthode efficace
de construction des codes B-LDPC, nommé le Principe A : on choisit
d'abord les blocs sur les colonnes avec un petit poids tels que la longueur
minimale des cycles entre les noeuds de degré inférieur soit
maximum. Ensuite, on choisit les blocs des colonnes correspondants aux noeuds
avec un degré supérieur tels que le périmètre du
graphe de Tanner soit maximum. Les codes qui sont ainsi construits ont un
plancher d'erreurs bas et des meilleures valeurs des rapports de Taux d'Erreurs
Binaires (TEB) et de Taux d'Erreurs par Trame (TET).
La performance d'erreurs de contrôle peut être
améliorée si on impose que le degré des petits cycles
inévitables soit le plus grand possible.
On doit mentionner que les noeuds de degré
élevé sont plus sensibles aux erreurs (parce qu'ils ont plusieurs
chemins pour la mise à jour des messages entre les noeuds variables et
les noeuds de parité). Richardson [39] a montré par la
méthode d'évolution de la densité (density evolution) que
les codes de
très grande longueur (qui convergent vers l'infini)
s'approchent de très près de la limite de Shannon. Mais ceci
n'est pas valide pour les codes courts. Les performances des codes LDPC
dépend aussi de cycles existants dans le graphe de Tanner et de la
distance minimale du code.
| 
