LDPC

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Dans la théorie de l'information, un contrôle de parité de faible densité LDPC est un code linéaire correcteur d'erreur, permettant la transmission d'information sur un canal de transmission bruyant. LDPC est construit en utilisant un graphe biparti clairsemé. Les codes LDPC ont une capacité approchant la limite théorique. À l'aide de techniques itératives de propagation d'information sur la donnée transmise et à décoder, les codes LDPC peuvent être décodés en un temps proportionnel à leur longueur de bloc. Ces informations supplémentaires (qu'on appelle aussi contraintes) sont en fait un groupe de bits de parité, chaque bit protégeant un sous-ensemble du bloc, chaque sous-ensemble étant recouvert par d'autres sous-ensembles. Les codes LDPC ont trouvé une utilisation dans les applications exigeant le transfert d'informations fiables et hautement efficace avec peu d'information en retour. Bien que la mise en œuvre de codes LDPC ait pris du retard sur d'autres codes, notamment les turbo codes, l'absence de brevets logiciels a rendu LDPC attrayant pour certains. Les codes LDPC sont également appelés codes Gallager, en l'honneur de Robert G. Gallager, qui a développé le concept de LDPC dans sa thèse de doctorat du Massachusetts Institute of Technology en 1960.

Histoire[modifier | modifier le code]

L'impossibilité de mettre en œuvre les codes LDPC développés par Gallager en 1963, fait qu'ils furent oubliés jusqu'à ce que le travail de Gallager ait été redécouvert en 1996. Les Turbo-codes, une autre classe de codes capacité similaire, découvert en 1993, est devenu le schéma de codage de choix dans les années 1990. Ces dernières années, les avancées dans les codes de contrôle de parité faible densité les ont fait surpasser les turbo-codes en termes d'erreur plancher et de performance de taux de codage, laissant les turbo-codes mieux adapté pour les taux réduits de code uniquement.

Applications[modifier | modifier le code]

En 2003, un code de LDPC a été préféré à six Turbo Codes pour devenir code correction d’erreur dans le nouveau DVB-S2 standard pour la transmission par satellite de la télévision numérique. En 2008, LDPC plutôt que le système de Turbo Codes a été choisi comme système de correction aval des erreurs (FEC) pour la norme ITU-T G.hn. G.HN a choisi LDPC plutôt que les turbo-codes en raison de leur complexité de décodage plus faible (surtout quand fonctionnant à des débits de données près de 1,0 Gbit/s). LDPC est également utilisé pour 10GBase-T Ethernet, qui envoie des données à 10 gigabits par seconde sur un câble à paires torsadées. À partir de 2009, les codes LDPC font également partie de la spécification Wi-Fi de l'IEEE 802.11 comme une option pour 802.11n et 802.11ac. Certains systèmes OFDM ajoutent une correction d'erreur externe supplémentaire qui corrige les erreurs occasionnelles qui ont outrepassé le code de correction de LDPC même à faible taux d'erreur de bit. Par exemple : La norme DVB-T2 et la norme DVB-C2 utilisent un code externe BCH pour éliminer les erreurs résiduelles après décodage par LDPC.


Décodage[modifier | modifier le code]

Exemple pédagogique[modifier | modifier le code]

Comme avec d'autres codes, le décodage d'un code LDPC sur un canal binaire symétrique est un problème NP-complet, bien que dans la pratique on puisse arriver à bonnes approximations. En revanche, la propagation d'information sur la donnée codée sur un canal binaire à effacement, est particulièrement simple lorsqu'il est possible de satisfaire des contraintes de façon itérative.

Par exemple, si l’on suppose que le mot de code valide, 101011, est transmis à travers un canal binaire à effacement et reçu avec les premiers et quatrièmes bits effacés, ce qui donne ?01?11. Le premier bit de parité correspond aux quatre premiers bits de l'information à décoder. Le deuxième bit de parité correspond aux bits trois, quatre et six. Le troisième bit de parité correspond aux bits un, quatre et cinq. Dans cet exemple, le premier bit ne peut pas encore être rétabli parce que toutes les contraintes de codage ne permettent pas d'identifier plus d'un bit inconnu à la foi.

Première passe[modifier | modifier le code]

La première contrainte indique que les quatre premiers bits sont erronés, la deuxième indique que les bits trois, quatre et six sont également erronés, de même le troisième bit de parité indique que les bits un, quatre et cinq sont erronés. Afin de décoder le message, les contraintes sont examinées sur un seul des bits à la fois.

Si l'on examine la deuxième contrainte, le quatrième bit doit avoir été à "zéro", puisque seul un zéro à cet emplacement peut satisfaire la contrainte (il n'y a que deux possibilités 101011 et 101111).

Cette procédure est ensuite répétée sur la nouvelle configuration où seule la première contrainte et la troisième contrainte sont fausses.

Deuxième passe[modifier | modifier le code]

Les bits en commun à ces deux contraintes sont les bits un et quatre, mais on connait maintenant la valeur du bit quatre, donc cela signifie que le premier bit doit être à "un" pour satisfaire la contrainte.

Ainsi, le message peut être décodé par itération.

Recherche par tableau de décodage (lookup table)[modifier | modifier le code]

Il est possible de décoder les codes LDPC sur un microprocesseur de faible puissance par l'utilisation de tables de décodage. Alors que les codes tels que LDPC sont généralement implémentés sur des processeurs de haute puissance, avec des grande longueurs de bloc, il y a aussi des applications qui utilisent des processeurs de plus faible puissance et des longueurs de bloc court (1024). Par conséquent, il est possible de pré calculer le bit de sortie basé sur des bits d'entrée prédéterminés. Une table est générée qui contient 2^n entrées (pour une longueur de bloc de 1 024 bits, il s'agirait d'une table de 2^1024 mots) et contient toutes les entrées possibles pour les différents états d'entrée (erronées et sans erreurs). Quand un nouveau bit est à traiter, il est ajouté à un registre FIFO dont les sorties sont utilisées pour adresser la table, ainsi la valeur du registre FIFO est permet de rechercher dans la table, la sortie pertinente à partir des valeurs pré calculées. Par cette méthode, des itérations très rapides peuvent être effectuées, le seul coût étant celui de la mémoire pour le tableau de décodage.

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Personnes[modifier | modifier le code]

Théorie[modifier | modifier le code]

Applications[modifier | modifier le code]

  • G.hn/G.9960 (ITU-T Standard for networking over power lines, phone lines and coaxial cable)
  • 802.3an (10 Giga-bit/s Ethernet over Twisted pair)
  • CMMB(China Multimedia Mobile Broadcasting)
  • DVB-S2 / DVB-T2 / DVB-C2 (Digital video broadcasting, 2nd Generation)
  • WiMAX (IEEE 802.16e standard for microwave communications)
  • IEEE 802.11n-2009 (Wi-Fi standard)

Autres codes de capacité proche[modifier | modifier le code]

Liens externes[modifier | modifier le code]