Wikipédia

Codes de parité à faible densité

(Redirigé depuis Ldpc)

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.

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.
Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.

Cet article ne cite pas suffisamment ses sources ().

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

Diagramme d'un exemple d'encodeur LDPC

Histoire

modifier

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

modifier

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

modifier

Exemple pédagogique

modifier

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

modifier

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

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.

Voir aussi

modifier

Articles connexes

modifier

Personnes

modifier

Théorie

modifier

Applications

modifier
  • 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

Liens externes

modifier
Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Codes_de_parité_à_faible_densité&oldid=216925798 ».