Energy-proportional polar decoders

Résumé

Les codes polaires sont une classe de codes correcteur d’erreurs ayant reçus beaucoup d’attention depuis leur découverte. Cela s’explique en partie par le fait qu’il a été prouvé que les codes polaires atteignent asymptotiquement la capacité d’un canal binaire symmétrique sans mémoire (binary discrete memoryless channel (B-DMC)) via un algorithme de décodage à faible complexité nommé annulation successive (successive-cancellation (SC)). Cependant, les performances de correction d’erreurs restent limitées pour SC pour des longueurs de codes finis. Ainsi, un algorithme plus performant, le décodeur à annulation successive par liste (successive-cancellation list (SCL)) est considéré comme l’algorithme de référence dans de nombreuses applications pratiques, comme lors de la standardisation de la 5G. Le décodeur SCL génère une liste de candidats pour décoder la représentation bruitée d’un message transmis. En conséquence, les performances de correction d’erreurs de SCL sont considérablement améliorées par rapport à SC. Par contre, l’implémentation matérielle d’un décodeur SCL consomme plus d’énergie et requiert une plus grande surface en comparaison à SC. Le décodage SC à inversion (successive-cancellation flip (SCF)) a été proposé pour améliorer les performances de correction d’erreurs de SC en générant les candidats à travers plusieurs essais de décodage, c’est-à-dire de manière séquentielle. À chaque essai supplémentaire, le bit de décision estimé comme le moins fiable est inversé. Le décodeur à annulation successive par liste à inversion (successive-cancellation list flip (SCLF)) a été proposé avec l’idée de combiner les stratégies de décodage SCL et SCF. Les variantes dynamiques de ces décodeurs, SCF dynamique (dynamic successive-cancellation flip (DSCF)) et SCLF dynamique (dynamic successive-cancellation list flip (DSCLF)), améliorent les performances de correction d’erreurs. Cette stratégie de décodage à inversion fait que SCF et SCLF présentent des temps d’exécution variables, rendant le temps d’exécution moyen et la latence potentiellement très élevés. Néanmoins, les architectures existantes montrent que les décodeurs à inversion sont plus efficaces en termes de surface et de consommation énergétique en comparaison au décodeur SCL. Les contributions de ce doctorat s’articulent autour de la conception de décodeurs de codes polaires à faible consommation d’énergie. Les algorithmes de décodage par inversion basés sur SCF et leurs variations peuvent atteindre les performances de correction d’erreurs des décodeurs SCL tout en ayant des implémentations matérielles plus efficaces. Cependant, le temps d’exécution variable pose un problème pour la réalisation des récepteurs. Les mécanismes proposés dans cette étude doctorale améliorent le temps d’exécution des décodeurs à inversion avec un impact minimal ou nul sur les performances de correction d’erreurs et les ressources matérielles. Concernant l’implémentation matérielle, l’accent est mis sur la mémoire requise, majoritaire à la surface du décodeur. La première contribution de ce mémoire est le mécanisme de redémarrage généralisé (generalized restart mechanism (GRM)) pour le décodeur par inversion basé sur SCF. Lors de l’application du GRM à chaque essai supplémentaire, la partie de l’arbre de décodage précédant l’inversion du bit non fiable est évitée. Le chemin de redémarrage parcourt l’arbre de décodage depuis la racine jusqu’au bit de redémarrage afin de pouvoir l’estimer tout en évitant l’estimation des bits précédents. Le GRM réduit le temps d’exécution moyen du décodeur DSCF-3 de 26% à 60% sans aucun effet négatif sur les performances de correction d’erreurs. Le GRM requiert environ 4% de mémoire supplémentaire pour ce décodeur. La deuxième contribution est l’ajout d’un GRM modifié pour des décodeurs à inversion possédant des techniques de décodage rapide. Ces techniques de décodage rapide améliorent le temps d’exécution des décodeurs à inversion. Notre proposition GRM est conçue pour être adaptable à ces techniques de décodage rapide. Grâce à cela, le temps d’exécution moyen des décodeurs à inversion est encore plus réduit. La troisième contribution est le mécanisme de redémarrage à localisation limitée (limited-locations restart mechanism (LLRM)) pour le décodeur SCLF. L’ajout du GRM aux décodeurs à inversion par liste requiert une quantité trop importante de mémoire. Pour résoudre ce problème, nous proposons le LLRM, une modification du GRM. Une méthode basée sur les probabilités pour sélectionner les emplacements de redémarrage est proposée. Elle vise à maximiser la réduction du temps d’exécution tout en minimisant la mémoire requise. Le LLRM réduit le temps d’exécution moyen de 10% à 40% lorsqu’il est appliqué au décodeur DSCLF-3. Le LLRM nécessite environ 2% de mémoire supplémentaire. La quatrième contribution est le mécanisme de terminaison anticipée pour les décodeurs à inversion. Cette contribution consiste en deux mécanismes distincts. Tout d’abord, un mécanisme d’arrêt précoce est introduit pour différencier les mots de code indécodables des mots de code décodables en utilisant notre métrique. Si la métrique suggère qu’un mot codé est probablement indécodable, le décodeur tente un nombre maximal réduit d’essais. Le mécanisme d’arrêt précoce réduit le temps d’exécution moyen du décodeur DSCF-1 de 22% au prix d’une perte de correction d’erreur mineure de 0,05 dB. Deuxièmement, le mécanisme à seuils multiples proposé limite la latence d’un décodeur à inversion en fonction de l’état du buffer afin d’éviter toute perte de données. Ce mécanisme est mis en oeuvre dans un système où le canal produit des données à un taux fixe. Appliqué au décodeur DSCF-1, le mécanisme à seuils multiples permet d’opérer dans un système avec un taux de production de canaux fixe 1,13 fois inférieur au taux associé à un seul essai de décodage. Il en résulte une perte de correction d’erreurs mineure de 0,06 dB.

Date	29 nov. 2024
langue originale	Anglais américain
Établissement diplômant	École de technologie supérieure
Superviseur	Pascal Giard (Directeur(-trice))