Skip to content
Retour aux résultats

Codes à contrôle de parité de faible densité (LDPC)

Introduite par
Robert Gallager
Année
1962
Type
linear error-correcting code
Famille
Coding theory

Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais

Taille de police

À quoi sert-elle ?

Les codes LDPC, inventés par Robert Gallager en 1962 et redécouverts dans les années 1990 par MacKay, sont des codes linéaires correcteurs d'erreurs définis par des matrices de contrôle de parité creuses.

Ils atteignent des performances à moins de 0,4 dB de la limite de Shannon avec un décodage itératif par propagation de croyance et sont devenus la norme pour les communications sans fil modernes (WiFi-6, 5G NR, Digital Video Broadcasting). Contrairement aux codes turbo, les codes LDPC ont une structure théorique des graphes plus élégante et une analyse théorique plus mature.

L’intuition derrière la méthode

Les codes linéaires standards utilisent des matrices de contrôle de parité denses, rendant le décodage coûteux en calcul. Les codes LDPC inversent cette tendance : la matrice de contrôle de parité est creuse (la plupart des entrées sont nulles), de sorte que chaque vérification de parité n'implique qu'une poignée de bits. Au récepteur, un graphe biparti est construit où les nœuds variables représentent les bits transmis et les nœuds de vérification représentent les contraintes de parité. Le décodage devient un passage itératif de messages sur ce graphe : chaque nœud variable recueille des informations de ses voisins, met à jour sa croyance sur la valeur du bit et renvoie des estimations affinées. La sparsité assure une convergence rapide et des performances proches de celles de Shannon.

Histoire

Gallager a inventé les codes LDPC en 1962, mais la théorie a pris du retard sur la mise en œuvre pratique. En 1995, MacKay les a redécouverts et a démontré leurs performances proches de la limite de Shannon par simulation. Des recherches approfondies dans les années 2000 ont développé des algorithmes efficaces d'encodage, de décodage et de construction de graphes. Les codes LDPC ont été adoptés dans le WiFi-6 (802.11ax, 2021) et la norme 5G NR (2018). Ils sont devenus plus répandus que les codes turbo dans les nouveaux systèmes en raison de meilleures performances et d'une structure plus nette.

Quand l’utiliser

Les codes LDPC sont préférés aux codes turbo dans les systèmes modernes en raison de meilleures performances et d'une architecture plus simple. Utilisez les LDPC pour de larges plages de SNR (pas de falaise de seuil) ; ils fonctionnent bien de SNR faibles à élevés. Le LDPC est la norme pour WiFi-6, les communications par satellite et la 5G NR. Évitez les LDPC uniquement si la compatibilité héritée exige des codes turbo. Le LDPC convient également aux paquets très courts (>30 bits) car la structure du code est séparable.

Limites et points d’attention

  • La construction du graphe et le stockage de la matrice deviennent complexes pour les codes très longs (>10k bits)
  • Les performances sont sensibles aux structures de graphes à petite échelle (circonférences, ensembles absorbants) ; une conception minutieuse est nécessaire
  • La propagation de croyance suppose un graphe sans boucles, mais les graphes ont des cycles ; la convergence vers la solution optimale n'est pas garantie
  • La latence de décodage (itérations) augmente logarithmiquement avec le SNR ; pas de latence nulle comme certains codes classiques
  • La quantification des messages (dans le matériel à virgule fixe) affecte les performances ; une allocation de bits minutieuse est nécessaire

Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.

Points forts

  • Performances à moins de 0,4 dB de la limite de Shannon (légèrement meilleures que les codes turbo)
  • Structure théorique des graphes plus simple ; analyse théorique plus nette que les codes turbo
  • Le décodage itératif évite le comportement de falaise de seuil (contrairement aux codes turbo)
  • Conception de code flexible via la construction de graphes ; facile à adapter à des applications spécifiques
  • Matériel de décodage parallèle efficace ; le passage de messages convient à l'implémentation VLSI/GPU
  • Fonctionne bien pour les mots de code longs et modérément courts

Applications

  • WiFi-6 (802.11ax) : réseaux locaux sans fil à haut débit où les LDPC assurent une transmission de données fiable
  • 5G NR : codage de canal pour les canaux de données et de contrôle, remplaçant les codes turbo de la 4G
  • Communications par satellite : radiodiffusion vidéo numérique (DVB-S2) et missions dans l'espace lointain utilisant des LDPC à longs mots de code
  • Communications sur ligne électrique (PLC) : transmission de données robuste sur les réseaux électriques bruyants
  • Systèmes de mémoire Flash : correction d'erreurs pour le stockage Flash NAND sans usure due à des rafraîchissements fréquents

Comment ça marche

Comment ça marche

1

Les bits d'information sont encodés à l'aide d'une matrice de contrôle de parité creuse H ; les bits encodés sont la solution de H*c = 0 (mod 2), où c est le mot de code.

2

La matrice de contrôle de parité H est structurée pour être creuse (par exemple, chaque ligne/colonne a un poids faible constant de 3 à 5). Cette structure est exploitée pour un encodage efficace.

3

Les bits encodés sont transmis sur un canal bruité ; les bits reçus sont des valeurs douces (rapports de vraisemblance ou rapports de vraisemblance logarithmiques).

4

Un graphe biparti est construit : nœuds gauches = nœuds variables (bits), nœuds droits = nœuds de vérification (équations de parité). Les arêtes relient les variables aux vérifications dans lesquelles elles apparaissent.

5

Propagation de croyance itérative : les nœuds variables agrègent les messages des nœuds de vérification, mettent à jour les estimations de bits et renvoient des messages affinés. Après itérations, des décisions dures sont prises ; si les vérifications de parité sont satisfaites, le décodage est réussi.

Pièges courants

  • Utilisation d'un graphe creux mal conçu avec des cycles courts ; les cycles courts provoquent l'oscillation de la propagation de croyance
  • Sur-itération au-delà de la convergence ; les itérations inutiles gaspillent de l'énergie sans amélioration
  • Supposer que le décodage par somme minimale est aussi bon que le produit-somme ; les approximations entraînent une perte de performance, surtout à faible SNR
  • Négliger les effets de longueur finie ; les graphes conçus pour l'analyse asymptotique peuvent sous-performer sur des paquets courts
  • Ne pas tenir compte de la quantification dans l'implémentation matérielle ; la simulation en virgule flottante diffère de la réalité en virgule fixe

Questions fréquentes

Qu'est-ce qui rend le décodage LDPC si efficace par rapport aux codes linéaires généraux ?

La sparsité de la matrice de contrôle de parité signifie que chaque bit ne participe qu'à quelques vérifications de parité. Lors du décodage, le passage de messages sur le graphe biparti est linéaire par rapport au nombre d'arêtes, et non à la longueur du code. Pour les codes denses, le décodage nécessiterait une inversion de matrice, qui est cubique par rapport à la longueur du code. La sparsité rend le décodage quasi-linéaire et pratique pour les longs codes.

Qu'est-ce qu'un ensemble absorbant et pourquoi est-il important ?

Un ensemble absorbant est un petit sous-ensemble du graphe qui peut piéger le décodage par propagation de croyance, empêchant la convergence vers la solution correcte. Ils sont une source principale de plancher d'erreur (la diminution non exponentielle du taux d'erreur binaire à faible SNR). Les concepteurs de codes évitent les petits ensembles absorbants par une construction de graphe minutieuse ; les outils d'analyse (par exemple, l'analyse des ensembles d'arrêt) identifient les structures problématiques.

Comment les LDPC se comparent-ils aux codes polaires ?

Les deux atteignent des performances proches de la limite de Shannon. Les codes polaires ont une structure récursive et une optimalité prouvable sous décodage par annulation successive à longueur de code infinie. Les codes LDPC sont plus flexibles et ont empiriquement de meilleures performances à longueur finie. La 5G NR utilise des codes polaires pour les canaux de contrôle (paquets courts) et des codes LDPC pour les canaux de données (paquets longs), exploitant les forces de chaque code.

Pourquoi la circonférence du graphe est-elle importante dans les codes LDPC ?

La circonférence est la longueur du plus court cycle dans le graphe biparti. Les cycles courts (circonférence < 6) amènent la propagation de croyance à utiliser des informations corrélées (les messages bouclent), dégradant les performances. Les codes à haute circonférence (circonférence ≥ 6) brisent mieux les corrélations. Les codes sont souvent conçus pour maximiser la circonférence sous contrainte de sparsité.

Méthodes associées

Sources

  1. Gallager, R. G. (1962). Low-density parity-check codes. IRE Transactions on Information Theory, 8(1), 21-28.

    Ouvrir la référence DOI
    Copié.
  2. Richardson, T. J., & Urbanke, R. L. (2001). The capacity of low-density parity-check codes under message-passing decoding. IEEE Transactions on Information Theory, 47(2), 599-618.

    Ouvrir la référence DOI
    Copié.