Codes de parité à faible densité
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 bruité. 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 usages. 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
L'impossibilité matérielle 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 de capacité similaire, découverts en 1993, sont devenus 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 de taux d'erreur plancher et de performance en taux de codage ; les turbo-codes restant mieux adaptés pour les taux réduits de codage uniquement.
Applications
En 2003, un code LDPC a été préféré à six Turbo Codes pour devenir le code de correction d’erreur retenu dans le nouveau standard DVB-S2 pour la transmission par satellite de la télévision numérique. En 2008, LDPC a été choisi plutôt qu'un système de Turbo Codes 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 ils fonctionnent à des débits de données de près de 1 Gbit/s). LDPC est également utilisé pour le 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 le 802.11n et le 802.11ac. Certains systèmes OFDM ajoutent une correction d'erreur externe supplémentaire qui corrige les erreurs occasionnelles qui ont outrepassé les capacités de détection du code de correction LDPC, même à faible taux d'erreur binaire. 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
Exemple pédagogique
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 à de 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 les 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 corrigé parce que toutes les contraintes de codage ne permettent pas d'identifier plus d'un bit inconnu à la fois.
Première passe
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
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é et corrigé par itération.
Recherche par tableau de décodage (lookup table)
Il est possible de décoder les codes LDPC avec 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 grandes longueurs de bloc, il y a aussi des applications qui utilisent des processeurs de plus faible puissance et des longueurs de bloc courtes (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 2xn entrées (pour une longueur de bloc de 1 024 bits, il s'agit d'une table de 2x1024 mots) et contient toutes les entrées possibles pour les différents états d'entrée (erronés 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 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
Personnes
- Robert G. Gallager
- Richard Hamming
- Claude Shannon
- David J. C. MacKay
- Irving S. Reed
Théorie
- Propagation des convictions
- Théorie des graphes
- Code de Hamming
- Code linéaire
- Sparse graph code
- Expander code
Applications
- 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
- Turbo codes
- Online codes
- Fountain codes
- LT codes
- Raptor codes
- Repeat-accumulate codes (une famille de turbo codes simples)
- Tornado codes (LDPC codes conçus pour l'erasure decoding)
- Polar codes
Liens externes
- The on-line textbook: Information Theory, Inference, and Learning Algorithms, by David J. C. MacKay, discusses LDPC codes in Chapter 47.
- LDPC Codes: An Introduction
- LDPC codes and performance results
- Online density evolution for LDPC codes
- LDPC Codes – a brief Tutorial (by Bernhard Leiner, 2005)
- Iterative Error Correction: Turbo, Low-Density Parity-Check and Repeat-Accumulate Codes
- Source code for encoding, decoding, and simulating LDPC codes is available from a variety of locations: