Energy-proportional polar decoders

Sagitov, Ilshat (2024). Energy-proportional polar decoders. Thèse de doctorat électronique, Montréal, École de technologie supérieure.

Prévisualisation

PDF Télécharger (819kB) | Prévisualisation

Résumé

Polar codes are a class of linear error-correction codes that have received a lot of attention due to their ability to achieve channel capacity in an arbitrary binary discrete memoryless channel (B-DMC) with low-complexity successive-cancellation (SC) decoding. However, practical implementations often require better error-correction performance than what SC decoding provides, particularly at shorter code lengths. As a result, the successivecancellation list (SCL) decoder has become the reference algorithm for many practical applications, such as 3GPP’s next-generation mobile-communication standard (5G). The SCL decoder improves error-correction performance by generating a list of candidate codewords from the noisy received message. However, the hardware implementation of SCL decoder tends to be less energy- and area-efficient than that of a SC decoder.

Successive-cancellation flip (SCF) decoder involves multiple decoding trials, where at each additional trial, the decision bit estimated as the least reliable is flipped before resuming the standard SC decoding. The successivecancellation list flip (SCLF) decoder combines the SCL and SCF decoding strategies. Variations of these decoders, such as dynamic successive-cancellation flip (DSCF) and dynamic successive-cancellation list flip (DSCLF), further improve the error-correction performance. Despite their advantages in error correction, the flip decoders (SCF and SCLF) have variable execution times, which can lead to high average execution time and latency. Nevertheless, existing architectural designs demonstrate that flip decoders are more efficient in area and energy requirements compared to the SCL decoder.

The contributions of this doctoral study are focused on the design of energy-efficient decoders for polar codes. The flip decoding algorithms based on SCF and their variations can achieve the error-correction performance of the state-of-the-art SCL decoders while resulting in more efficient hardware implementations. However, variable execution time poses a challenge for realization in receivers. This doctoral study proposes mechanisms to improve the execution-time characteristics of flip decoders while minimizing the impact on error-correction performance and hardware resources. Among hardware resources, the primary focus is on the decoder memory, which occupies the largest part of the decoder area.

The first contribution of this thesis is the generalized restart mechanism (GRM) for the flip decoder based on SCF. By applying the GRM, a portion of the decoding tree can be skipped. This portion corresponds to parts of the tree to estimate the bit-flipping candidate and all the previous bits in each additional decoding trial. The GRM reduces the average execution time of the DSCF-3 decoder by 26% to 60% without any negative effect on the error-correction performance. The GRM results in approximately 4% of additional memory for this decoder.

The second contribution is the modified GRM for flip decoders with fast decoding techniques. Existing fast decoding techniques improve the execution-time characteristics of the flip decoders. Our proposed GRM is designed to be adaptable to these fast decoders. As a result of this combination, the average execution time of the flip decoders is further reduced while maintaining the original error-correction performance.

The third contribution is the limited-locations restart mechanism (LLRM) for the list-flip decoder (SCLF and its variations). Applying our proposed GRM to list-flip decoders results in enormous memory overhead. To overcome this issue, the LLRM, a modification of the GRM, is proposed. The probability-based method for selecting restart locations is proposed, which aims to maximize the execution-time reduction while minimizing the memory overhead. The LLRM reduces the average execution time by 10% to 40% when applied to DSCLF-3 decoder. For this decoder, the LLRM requires approximately 2% of additional memory. The LLRM does not modify original error-correction performance.

The fourth contribution is the early-termination mechanism for flip decoders. This contribution consists of two mechanisms. First, the early-stopping mechanism is introduced to differentiate undecodable codewords from decodable ones by using our proposed early-stopping metric. If the metric suggests that a codeword is likely undecodable, the decoder attempts a reduced maximum number of trials, much smaller than the initial maximum number of trials. The early-stopping mechanism reduces the average execution time of the DSCF-1 decoder by 22% at the cost of minor error-correction loss of 0.05 dB. Second, the multi-threshold mechanism is proposed. This mechanism restrains the delay of a flip decoder depending on the state of the buffer to prevent overflow. This mechanism is implemented in the system where the channel produces data with a fixed rate. When applied to the DSCF-1 decoder, the multi-threshold mechanism allows to operate in a system with a fixed channel-production rate 1.13 times lower than the rate associated with a single decoding trial. This results in a minor in a minor error-correction loss of 0.06 dB.

Titre traduit

Décodeurs polaires proportionnels à l’énergie

Résumé traduit

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.

Type de document:	Mémoire ou thèse (Thèse de doctorat électronique)
Renseignements supplémentaires:	"Thesis presented to École de technologie supérieure in partial fulfillment for the degree of doctor of philosophy". Comprend des références bibliographiques (pages 135-137).
Mots-clés libres:	codes polaires, codes correcteur d’erreurs, décodage, gestion de la mémoire, temps d’exécution, complexité, efficacité énergétique
Directeur de mémoire/thèse:	Directeur de mémoire/thèse Giard, Pascal
Programme:	Doctorat en génie > Génie
Date de dépôt:	30 avr. 2025 14:57
Dernière modification:	30 avr. 2025 14:57
URI:	https://espace.etsmtl.ca/id/eprint/3598

Gestion Actions (Identification requise)

Dernière vérification avant le dépôt