III.6. Décodage des codes LDPC
Par rapport aux autres types de codes, le décodage des
codes LDPC ne pose pas autant de problèmes pour les chercheurs que leur
construction. Le travail le plus difficile est de trouver les meilleures
méthodes pour construire des codes LDPC efficaces. Un code LDPC peut
être décodé par plusieurs méthodes. On peut citer
:
1. Décodage avec des décisions fermes
? Décodage avec la logique majoritaire (MLG) ; ?
Décodage avec basculement de bit (BF) ;
2. décodage avec des décisions
pondérées
? Décodage basé sur la probabilité a
posteriori (APP) ;
? Décodage itératif basé sur la
propagation de la confiance (somme-produit SPA) ;
3. Décodage mixte (ferme et pondéré) ?
Décodage BF pondéré.
La méthode MLG est la plus simple du point de vue de la
complexité du circuit. La méthode BF demande un peu plus de
complexité du circuit, mais elle donne des meilleures performances
d'erreur que la méthode MLG. Les méthodes APP et SPA donnent des
meilleures performances d'erreurs, mais nécessitent aussi une plus
grande complexité du circuit. Le décodage BF
pondéré représente un bon compromis entre les deux
caractéristiques. Quand à la méthode SPA, donne les
meilleurs TEB entre les 5 types de décodage.
? Décodage MLG des codes LDPC
La méthode MLG à une seule étape [34]
peut être appliquée au décodage des 4 types de codes
LDPC.
On calcule les syndromes :
??-1 (??)
???? ?? = ?? * ???? ?? = ?????? ??,??
??=0 III.6
Où ????(??) (1= ?? = ?? ) sont les ?? lignes de H
qui sont orthogonales sur le bit de la l-ème position. L'ensemble
des sommes de contrôle ???? (??) sont orthogonales sur le bit d'erreurs
???? et on peut les utiliser
pour l'estimation de ????. Le bit d'erreurs est bien
corrigé si dans le vecteur d'erreurs il y a moins de ??/2 erreurs.
? Algorithme de décodage à basculement de
bit (BF) des codes LDPC
Cette méthode est basée sur l'échange du
nombre d'échecs de parité quand un bit de la séquence
reçue est basculé. Il s'agit d'une méthode
itérative de décodage [28]. Le décodeur calcule toutes les
sommes de parité et ensuite, il change chaque bit dans la
séquence reçue s'il fait partie de plus de ?? équations de
parité échouées. La valeur de S est un seuil
fixé et dépend des paramètres du code (??,??, dmin) et du
rapport signal à bruit ou (Signal Noise Ratio SNR).
À partir de la séquence modifiée, le
décodeur recalcule les sommes de parité et le processus est
répété jusqu'à ce que toutes les sommes de
parité soient nulles.
Le nombre d'itérations du décodage est une
variable aléatoire et dépend du rapport signal à bruit du
canal. Pour des meilleures performances, on peut utiliser des seuils adaptatifs
?? et utiliser aussi une méthode hybride entre BF et MLG. Le
décodage BF corrige beaucoup de séquences d'erreurs qui
possèdent plus de bits erronés que la capacité du code
pour corriger les erreurs.
? Algorithme de propagation de croyance
Dans cette partie, nous nous intéressons au
décodage itératif souple des codes LDPC. L'algorithme de
décodage itératif présenté initialement par
Gallager [40], revu ensuite par MacKay [41] dans le cadre de la théorie
des graphes, est connu sous le nom d'algorithme de propagation de croyance
(Belief
Pr ?? = 1 ?? =
1-??' ?????/?? (1-2 Pr ??' =1 ?? )
2
III.10
Propagation (BP)). Cet algorithme peut être vu comme un
algorithme d'échange d'information entre les noeuds du graphe à
travers les branches. Ces messages transitant de noeuds en noeuds portent une
information probabiliste sur l'état des noeuds.
Le principe de la propagation de croyance est l'application
directe de la règle de Bayes sur chaque bit d'une équation de
parité. La vérification de parité permet de calculer une
estimation de chaque bit. Ces estimations, formant des messages se propageant
sur les branches du graphe, sont alors échangées
itérativement afin de calculer une information a posteriori sur
chaque bit. Dans le cas d'une propagation de croyance sur un graphe sans cycle,
les messages échangés sont indépendants, ce qui conduit au
calcul simple et exact des probabilités a posteriori :
l'algorithme est dans ce cas optimal. Dans le cas des codes LDPC, le graphe
factoriel présente des cycles.
Dans ces conditions, l'hypothèse de messages
indépendants n'est plus valide. Cependant, plus le graphe est creux
(c'est à dire moins la matrice de contrôle de parité est
dense), plus l'approximation d'un graphe sans cycle devient valide. C'est donc
sous cette hypothèse que l'algorithme de décodage est
décrit.
Si on considère une équation de parité
c faisant intervenir un ensemble de bits Vc, la règle
de Bayes appliquée au bit v permet d'exprimer les
probabilités suivantes conditionnellement à la séquence
reçue { y } :
Pr ?? = 0 ?? = Pr(??' ??'
?????/?? = 0{??}) III.7
Pr ?? = 1 ?? = Pr(??' ??'
?????/?? = 1{??}) III.8
Où la somme est réalisée modulo 2. Gallager
a démontré dans [42] que ces deux probabilités sont
égales
à :
1+ ??' ?????/?? (1-2 Pr ??' =1 ?? )
Pr ?? = 0 ?? = III.9
2
En utilisant la relation :
???????? 2 1 ???? 1-Pr?(??' =1 ?? )
Pr ?(??' =1{??} = 1 - 2Pr?(??' = 1 ?? ) III.11
On peut calculer le rapport de vraisemblance suivant :
|
1 +
Pr ?? = 0 ??
|
?? '
|
?????
??
|
????????
|
1 ???? Pr ??' =
|
0 ??
|
0 ?? )
|
III. 12
III.13
|
|
2 Pr?(??' =
|
1{??}
|
|
Pr ?? = 1 ?? 1 -
Qui peut être simplifié par :
1 Pr?(?? = 0
|
?? '
??
|
??
)
|
?????
????????
=
??'?????
|
1 ???? Pr ??' =
|
0 ??
|
|
2 Pr?(??' =
1
???????? 2 ????
/??
|
1{??}
Pr?(??' =
|
|
???????? 2????
Pr?(?? = 1
|
??
|
)
|
Pr?(??' =
|
1{??}
|
La fonction tanh étant une fonction monotone
impaire, on peut décomposer la relation précédente de la
manière suivante :
Pr?(?? = 0{??}
Pr?(?? = 1{??}
= ???????? ????
??'???
Pr?(??' = 0 ?? ) Pr?(??' = 1{??}
???????? ????
??/??
III.14
???????? 2 1 ???? Pr?(?? = 0{??}
1 Pr?(??' = 0 ?? )
= ???????? 2 ???? Pr?(??' = 1{??}
Pr?(?? = 1{??}
??'?????/??
III.15
|
En utilisant le fait que :
?? ?? = - ln ????????
|
??
|
= ln
|
exp ?? + 1
|
= ?? -1(??) III. 16
|
|
|
|
2
|
exp ?? - 1
|
On peut exprimer la valeur absolue du rapport de vraisemblance
dans l'espace logarithmique par :
|
Pr?(?? = 0{??} ???? Pr?(?? = 1{??}
|
= ?? ?? ????
??'????? /??
|
Pr?(??' = 0 ?? ) Pr?(??' = 1{??}
|
III. 17
|
Cette relation va servir de base pour la description de
l'algorithme de propagation de croyance. Dans ce qui suit nous allons
présenter les résultats de simulation.
| 
