Introduction aux codes de vérification de la parité de faible densité

Introduits par Robert Gallager dans sa thèse de doctorat de 1960, ces codes ont été largement oubliés pendant des décennies avant d'être redécouverts au milieu des années 1990. Leur capacité à approcher la limite Shannon avec une complexité pratique de décodage en a fait la pierre angulaire d'innombrables systèmes, de la télévision par satellite à la nouvelle radio 5G et au stockage flash NAND. La clé de leur performance réside dans une matrice de contrôle de parité très peu développée : la plupart des entrées sont nulles, ce qui simplifie les algorithmes de décodage basés sur des graphiques qui peuvent être mis en œuvre dans le matériel.

Dans les environnements à haut débit, le décodage logiciel ne peut pas suivre le rythme. Alors que les taux de données grimpent vers 100 Gbps et au-delà dans les réseaux de transport optique, les exigences sur les décodeurs LDPC deviennent extrêmes. Cela a poussé l'industrie vers des accélérateurs matériels dédiés qui exploitent le parallélisme à tous les niveaux.

Technologie connexe: Pour un aperçu des fondamentaux du code LDPC, voir l'article Wikipedia sur les codes LDPC.

Contexte théorique : Décorer les algorithmes

Avant d'examiner les architectures matérielles, il est essentiel de comprendre les algorithmes qui sous-tendent le décodage LDPC. L'algorithme le plus utilisé est le décodeur de la propagation de croyance (BP), également connu sous le nom d'algorithme de sum-product. Il fonctionne sur un graphique bipartite – le graphique Tanner – composé de nœuds variables (représentant des bits de codeword) et de nœuds de vérification (représentant des contraintes de parité).

Le coût de calcul de BP est important en raison des fonctions de tangente hyperbolique nécessaires pour les calculs de probabilité. Une approximation pratique est l'algorithme de la somme min, qui remplace la fonction complexe par des opérations de min et de signe. Bien que cela entraîne une légère perte de performance, la simplification est essentielle pour la mise en œuvre du matériel à grande vitesse.

La nature itérative de ces algorithmes signifie que le décodage de la latence est directement proportionnel au nombre d'itérations et au temps de peritération. Les architectures parallèles visent à réduire le temps de peritération en effectuant simultanément plusieurs mises à jour, ou en chevauchant les itérations par la pipeline.

Architectures traditionnelles de déco et leurs limites

Les décodeurs LDPC du matériel initial ont utilisé une approche entièrement séquentielle : un seul appareil de traitement met à jour chaque nœud variable à son tour, puis chaque nœud de contrôle à son tour, répétant jusqu'à la convergence. Cette architecture série nécessite les ressources matérielles les moins importantes – une seule unité de calcul – mais souffre de latence élevée et de faible débit. Par exemple, un décodeur qui manipule une longueur de code de 10 000 bits peut nécessiter des dizaines de microsecondes de peritération, ce qui est inacceptable pour les systèmes multi-gigabits modernes.

Une autre limite est la bande passante de mémoire. Dans les architectures série, tous les messages intermédiaires doivent être stockés dans la mémoire sur puce et accessibles à plusieurs reprises. Cela crée un goulot d'étranglement, car les temps d'accès à la mémoire deviennent le facteur dominant dans la durée d'itération.

L'inefficacité des méthodes série a motivé le développement de décodeurs partiellement et totalement parallèles. Le défi est d'accroître le parallélisme sans causer de conflit de ressources ou de violation du calendrier de passage des messages requis pour la convergence.

Architectures de déco parallèle : Etat de l'art

Les décodeurs LDPC modernes utilisent une variété de techniques parallèles, souvent combinées. Les approches les plus importantes sont le décodage en couches, le traitement en pipelines et les architectures entièrement parallèles.

Décodage en couches

Le décodage en couches réorganise la matrice de contrôle de parité en couches, généralement des lignes ou des groupes de lignes, qui correspondent à des sous-ensembles d'équations de contrôle non-overlaping. Dans chaque couche, toutes les mises à jour de nœuds variables qui touchent cette couche peuvent être traitées simultanément, à condition qu'elles ne partagent pas le même nœud variable.

Bien qu'un calendrier d'inondation standard mette à jour tous les nœuds variables puis tous les nœuds de vérification par itération, le calendrier en couches met à jour les nœuds variables et les nœuds de vérification à l'intérieur de chaque calque en un seul passage. Cela réduit efficacement le nombre d'itérations requises par un facteur de deux ou plus. Par exemple, un décodeur en couches peut converger dans 5-10 itérations où un décodeur d'inondation a besoin de 20-30. Le résultat est une réduction proportionnelle de la latence.

Les décodeurs en couches offrent également des avantages intermédiaires. Comme seuls les messages pour une couche doivent être stockés à la fois, les exigences en mémoire sont plus petites que dans les conceptions entièrement parallèles, ce qui rend le décodage en couches attrayant pour l'implémentation de FPGA où la RAM de bloc est limitée.

Exemple: Un décodeur en couches pour un code (64800, 64800–17280) utilisé dans DVB-S2 peut atteindre des débits dépassant 1 Gbps sur les FPGA modernes de Xilinx, comme le document ce papier IEEE sur les décodeurs LDPC à haut débit.

Traitement par pipeline

La pipeline est une technique numérique classique qui divise un calcul en plusieurs étapes, chacune se terminant en un cycle d'horloge, avec des registres entre les étapes tenant des résultats intermédiaires. Dans les décodeurs LDPC, la pipeline peut être appliquée à plusieurs niveaux : à l'intérieur d'une seule itération (tuyline d'inter-itération) ou à travers plusieurs itérations (tuyline d'inter-itération).

La pipeline intra-itération divise le calcul du message pour une variable ou vérifie le nœud en étapes arithmétiques plus petites, comme la recherche de min, le produit des signaux et la normalisation, permettant au matériel de fonctionner à une fréquence d'horloge plus élevée. Cependant, cela augmente la latence par itération, ce qui peut compenser le gain de débit si elle n'est pas gérée avec soin.

La pipeline interitération est plus agressive : elle chevauche le traitement de l'itération i avec l'itération i+1. Cela nécessite le découplage des mémoires du message afin qu'on puisse écrire l'un pendant qu'on lit l'autre. La profondeur du pipeline peut être plusieurs itérations, et il faut faire attention à éviter les risques de données lorsqu'une itération ultérieure dépend des résultats non encore produits.

Les architectures pipelines sont couramment utilisées dans les implémentations ASIC où le décodeur fait partie d'un système sur puce plus grand (SoC). Par exemple, le décodeur LDPC d'un processeur 5G à bande de base utilise souvent un pipeline en 4 étapes pour maintenir un débit de 20 Gbps tout en s'adaptant à une enveloppe de puissance stricte.

Architectures entièrement parallèles

Le parallélisme ultime est un décodeur entièrement parallèle qui assigne une unité de traitement dédiée à chaque noeud variable et à chaque nœud de contrôle du graphique Tanner. Tous les nœuds peuvent mettre à jour leurs messages dans un cycle d'horloge unique, en utilisant un calendrier d'inondation. Cela élimine les frais généraux séquentiels des approches en couches ou en pipelines, permettant d'atteindre le débit le plus élevé possible.

Un décodeur entièrement parallèle pour un code avec 10 000 nœuds variables et 5 000 nœuds de contrôle nécessiterait 15 000 éléments de traitement, plus un réseau de routage pour les connecter selon la matrice de contrôle de parité. Le câblage domine la zone de puce. Historiquement, seuls les très courts codes LDPC (avec quelques centaines de bits) pourraient être mis en œuvre complètement en parallèle sur une seule puce.

Cependant, les progrès de la technologie ASIC – la réduction des nœuds de processus, l'intégration 3D dense et les réseaux à large bande sur puce – ont rendu les décodeurs entièrement parallèles plus faciles à traiter. Les prototypes de recherche récents démontrent des décodeurs entièrement parallèles pour les codes de longueur 2000-4000 bits pouvant fonctionner à 1-10 Gbps. Ils ne conviennent toujours pas pour les codes très longs (p. ex., 64 bits pour DVB-S2), mais ils sont idéaux pour les applications sensibles aux latences comme les interconnections optiques et les liaisons satellite à faible orbite terrestre.

Étude de cas : Un décodeur LDPC entièrement parallèle pour la norme IEEE 802.11ad (60 GHz WiGig) a été démontré dans une puce CMOS de 28 nm, avec 10 Gbps avec 350 mW, comme décrit dans ce journal IEEE de circuits à État solide .

Autres approches notables

Plusieurs techniques de parallélisation supplémentaires méritent d'être mentionnées:

  • Décodage stochastique: Représente les messages comme des séquences de bits aléatoires, permettant un matériel extrêmement simple (un seul flop par message) au prix d'une convergence plus lente. Le parallélisme est naturellement élevé parce que chaque noeud fonctionne indépendamment. Les décodeurs stochastiques ont été explorés pour des applications de très faible puissance telles que les dispositifs médicaux implantés.
  • Décodeurs LDPC quasi cycliques (QC) : La plupart des normes modernes utilisent des codes LDPC quasi cycliques, où la matrice de contrôle de parité est composée de sous-matrices d'identité décalées circulairement. Cette structure permet au décodeur d'utiliser des décalages de barils ou des réseaux de permutation pour acheminer les messages entre les éléments de traitement, simplifiant grandement l'interconnexion. Presque tous les décodeurs en couches et partiellement parallèles pour les codes QC-LDPC exploitent cette régularité.
  • Architectures parallèles partielles:[ Un compromis entre des conceptions en couches et des conceptions entièrement parallèles, des décodeurs parallèles partiels assignent un nombre fixe d'unités de traitement pour traiter plusieurs nœuds sur plusieurs cycles d'horloge.

Plateformes matérielles pour la mise en œuvre du décodeur LDPC

Le choix de la plateforme – FPGA, ASIC ou GPU – influence fortement le parallélisme et les compromis de conception réalisables.

Décoders basés sur le FPGA

Les FPGA modernes contiennent des milliers de tranches DSP et une RAM en bloc abondante, ce qui permet aux décodeurs en couches d'un parallélisme modéré. Les décodeurs en pleine parallèle sont rarement implémentés sur les FPGA en raison de la congestion du routage, mais des conceptions partielles parallèles et en couches peuvent atteindre un débit multi-gigabits. La flexibilité des FPGA permet également l'adaptation des paramètres de code en temps d'exécution, ce qui est précieux pour les radios définies par logiciel.

Décoders basés sur l'ASIC

Les circuits intégrés spécifiques à l'application (ASIC) sont les chevaux de travail des puces de communication de masse. Ils peuvent intégrer des centaines d'éléments de traitement avec des hiérarchies de mémoire personnalisées et un routage dédié. Les décodeurs ASIC pour 5G NR et Wi-Fi 6 dépassent systématiquement 10 Gbps en utilisant des architectures en couches ou en pipelines.

Décoders à base de GPU

Les unités de traitement graphiques (GPU) ne sont pas utilisées dans les récepteurs de communication de production, mais elles sont inestimables pour la recherche et le décodage hors ligne. Un GPU moderne peut simuler des milliers de mises à jour de nœuds en parallèle en utilisant son architecture SIMT (une seule instruction, plusieurs fils). Les chercheurs utilisent des décodeurs basés sur GPU pour tester de nouveaux algorithmes et des conceptions de code sans s'engager sur le matériel.

Défis dans le design de décoder parallèle

Malgré des progrès impressionnants, plusieurs obstacles subsistent avant que les décodeurs parallèles de CLD ne puissent satisfaire à toutes les exigences d'application.

  • Consommation de puissance:[ Les unités de traitement parallèles consomment une puissance dynamique importante. Pour les appareils alimentés par batterie, le budget de puissance peut limiter le degré de parallélisme.
  • Complexité du logiciel :[ Le routage et la mémoire nécessaires pour un parallélisme élevé augmentent la surface des puces et l'effort de conception.Pour les décodeurs entièrement parallèles, l'interconnexion peut occuper plus de 70% de la surface de jeu.
  • Rail de sol :[ Certaines architectures parallèles introduisent des effets de quantification ou des algorithmes simplifiés qui causent une erreur de plancher – une région où le taux d'erreur de bits cesse d'améliorer à mesure que le rapport signal-bruit augmente.
  • Scalabilité: À mesure que les longueurs de code LDPC grandissent (à 64k ou 128k bits), maintenir la concordance sans conflits de mémoire devient plus difficile. Les décodeurs en couches exigent que chaque couche soit traitée sans conflits; la conception de matrices et les algorithmes de superposition sont un domaine de recherche actif.

Orientations futures

La prochaine génération de décodeurs LDPC combinera probablement le parallélisme avec de nouveaux paradigmes informatiques.

  • Décodage assisté par la machine: Les réseaux neuraux peuvent être formés pour approximer l'algorithme de propagation des croyances, ce qui peut réduire le nombre d'itérations tout en maintenant les performances. Par exemple, les décodeurs de propagation des croyances neurales utilisent des poids et des compensations appris, et ils peuvent être mis en œuvre dans le matériel avec un minimum de frais généraux.
  • Architectures reconfigurables et adaptatives:[ Les futurs décodeurs peuvent ajuster dynamiquement leur degré de parallélisme en fonction des exigences de qualité et de débit des canaux. Par exemple, un décodeur pourrait basculer entre les modes stratifiés et entièrement parallèles en temps réel.
  • Intégration avec correction d'erreur quantique:[ Comme le calcul quantique arrive à maturité, la correction d'erreur pour qubits exigera des décodeurs extrêmement rapides – selon l'ordre des nanosecondes. Des décodeurs parallèles LDPC inspirés par des conceptions classiques sont évalués pour les codes de surface et d'autres codes de correction d'erreur quantique, bien que les contraintes soient très différentes (p. ex., la mesure du syndrome n'est pas destructive).
  • L'intégration 3D et les interconnexions optiques:[ L'entaillement de la mémoire meurt directement en haut des matrices logiques peut atténuer les goulets d'étranglement de la bande passante de la mémoire.

Des enquêtes plus complètes sont disponibles dans cet article sur les enquêtes et les tutoriels de l'IEEE sur les architectures de décodeurs LDPC et dans cet article sur les décodeurs LDPC à efficacité énergétique .

Conclusion

Les architectures de décodage parallèles ont transformé les codes LDPC d'une curiosité théorique en un outil pratique de communication haute vitesse moderne. Des conceptions en couches, en pipelines et en totalement parallèles abordent chacun des différents points de l'espace de conception du débit, de la zone et de la puissance. Les progrès continus de la technologie des semi-conducteurs et de l'optimisation des algorithmes promettent des décodeurs encore plus rapides et plus efficaces dans les années à venir.