18 mars 2024
Sommaire
La détection et la correction d’erreurs sont essentielles dans les systèmes de communication modernes pour assurer l’intégrité et la fiabilité des données. Les codes polaires sont une classe de codes correcteurs d’erreurs. À une longueur qui tend vers l’infinie, ces codes sont théoriquement optimaux sous décodage par annulation successive (successive cancellation, SC) de faible complexité. Quant au décodage SC à inversion (successive cancellation flip, SCF), il permettrait d’atteindre de meilleures performances en correction d’erreurs, et ce, avec des longueurs de code réduites. Cependant, les temps d’exécution du décodage SCF sont très variables. Dans ce travail, nous proposons un mécanisme de redémarrage simplifié (simplified restart mechanism, SRM) pour écourter les temps d’exécution des décodeurs à inversion tout en offrant les mêmes performances de correction d’erreur.
Mots clés : décodage, codes correcteurs d’erreurs, codes polaires, annulation successive par inversion, gestion de la mémoire, temps d’exécution
Introduction
Un code correcteur d’erreurs permet à un récepteur de détecter et, s’il est utilisé correctement, de corriger la plupart, voire toutes, les erreurs d’un bloc d’informations corrompu pendant le transit entre l’émetteur et le récepteur. Un codeur applique un code correcteur d’erreurs (N,k) pour transformer des bits d’information k en une séquence de longueur N, ajoutant ainsi de la redondance à un message avant sa transmission. Le but ultime de la correction d’erreurs est de décoder les bits d’information k le plus simplement possible.
Les codes polaires ont suscité l’intérêt des chercheurs, étant le premier type de code correcteur d’erreurs asymptotiquement optimal lors d’un décodage de faible complexité, SC [1]. Cependant, lorsque les longueurs de code sont de courtes à modérées, la capacité de correction d’erreur par SC est inférieure à la moyenne. Le décodage SC avec liste (SCL) améliore les performances de décodage en générant L candidats en parallèle. Malgré la complexité accrue du décodage, la performance de correction d’erreur du SCL a motivé le choix des codes polaires pour protéger le canal de contrôle dans les communications mobiles nouvelle génération, c’est-à-dire la radio 5G.
Le décodage SC à inversion (SCF), où un chemin unique de SC sert à plusieurs tentatives de décodage, serait une solution de rechange au décodage SCL. Le décodage SCF n’inverse qu’un seul bit par tentative. Un nombre maximum de tentatives Tmax permet de limiter la latence et la complexité. Globalement, le SCF est moins complexe que le SCL, mais son temps d’exécution n’est pas déterministe. Ensuite, le DSCF-3, un algorithme de décodage SCF dynamique [2], permet d’inverser jusqu’à 3 bits par tentative.
Nous proposons ici un mécanisme de redémarrage simplifié (SRM) qui réduit le temps d’exécution moyen du décodage SCF pour codes polaires, sans affecter les performances de correction d’erreur.
Description du mécanisme de redémarrage simplifié
Figure 1 SRM proposé pour arbre de décodage de code polaire (8,4) inversant le bit û6.
Un code polaire (N,k) est composé de bits d’information k et de bits gelés (N-k), c’est-à-dire de bits connus à la fois de l’encodeur et du décodeur, et réglés à 0.
La Figure 1 présente l’arbre de décodage d’un code polaire (8,4). L’information provenant du canal est αch={α0,…,α7} et entre par la racine de l’arbre, tandis que les estimations de bits û={û0,…,û7} se trouvent aux feuilles de l’arbre. Les bits gelés sont représentés par les cercles blancs et ont une valeur de 0. Une décision sur l’estimation du bit est prise pour chaque bit d’information, représenté par les cercles noirs. Par conséquent, une estimation erronée (et une inversion de bit) ne peut se produire qu’à ces endroits.
Dans le cas du SCF, si la première tentative échoue, au moins un bit de décision est erroné. Le décodeur estime l’emplacement à inverser, effectue une autre tentative, inverse l’estimation une fois qu’il atteint l’emplacement identifié, puis reprend le décodage jusqu’à la fin.
La tentative supplémentaire reste inchangée jusqu’à ce qu’elle atteigne le premier bit à inverser. Si le bit d’information est situé du côté droit (CD) de l’arbre de décodage, l’arbre du côté gauche (CG) peut être sauté. À la Figure 1, l’inversion du bit est à la position f1=6>8/2, donc le (CG) est sauté et le décodage reprend à l’arbre de décodage du (CD).
Ainsi, le SRM proposé permet de sauter des calculs pour certaines tentatives supplémentaires du décodeur. Ce mécanisme ne modifie pas les performances de la correction d’erreur, mais cause une légère augmentation de la quantité de mémoire requise.
Efficacité du mécanisme proposé
L’analyse du SRM s’effectue en simulant une transmission par code polaire (1024, 128) sur le canal AWGN. Le code polaire passe par les décodeurs SCF ou DSCF-3 avec des contraintes Tmax=12 et Tmax=301, respectivement. Nous avons analysé les performances de correction d’erreur et le temps d’exécution moyen. Les caractéristiques du décodage SC sont également fournies à titre de référence.
Figure 2 Performances de correction d’erreur des décodeurs SCF et DSCF-3 avec et sans le SRM proposé.
Figure 3 Temps d’exécution moyens des décodeurs SCF et DSCF-3 avec et sans le SRM proposé. La latence du décodage SC est incluse à titre de référence.
La Figure 2 montre la performance de la correction d’erreur selon le taux d’erreurs sur les trames (frame-error rate, FER), c’est-à-dire le rapport entre le nombre de trames décodées avec succès et le nombre total de trames. L’axe x est Eb/N0, exprimé en dB, et indique le rapport signal / bruit (signal-to-noise ratio, SNR) par bit. Pour les Eb/N0 plus bas, l’énergie du bruit dans le canal est élevé par rapport à celui du signal d’intérêt, ce qui rend le décodage d’une trame plus difficile. Les deux décodeurs à inversion apportent des améliorations par rapport au décodeur SC. Comme prévu, le FER diminue dans les deux méthodes de décodage lorsque la qualité du signal s’améliore, et le SRM n’affecte pas la performance de la correction d’erreur.
La Figure 3 illustre le temps d’exécution moyen (TEM), où les lignes continues et pointillées correspondent aux décodeurs à inversion, avec et sans le SRM, respectivement. Le TEM est exprimé en nombre de cycles d’horloge (CH) requis pour les calculs avec une implantation matérielle réaliste [3]. L’axe x reprend le FER de la Figure 2. Le décodage SC situe la limite. Les décodeurs à SRM permettent une réduction notable du temps d’exécution moyen. La réduction est plus importante avec le décodeur DSCF-3 que le SCF. Pour 1 trame mal décodée sur 100, la réduction du TEM pour le décodeur DSCF-3 est de 31,70 %, par rapport à 11,17 % pour le décodeur SCF.
Conclusion
Le codage avec correction d’erreur est essentiel à la communication; il permet de détecter et de corriger les erreurs dans les informations transmises. Les décodeurs SC à inversion pour codes polaires sont d’un grand intérêt pour les systèmes ayant peu de ressources matérielles. Cependant, leur temps d’exécution non déterministe rend ces décodeurs plus difficiles à intégrer dans des systèmes à temps fixe. Dans ce travail, nous avons proposé un mécanisme permettant d’écourter le temps d’exécution moyen et la complexité des décodeurs SC à inversion pour codes polaires, tout en maintenant le même niveau de correction d’erreurs. Nos résultats démontrent que le temps d’exécution moyen d’un décodeur à inversion standard pour codes polaires peut être réduit de 31 %.
Références
[1] E. Arıkan, “Channel polarization: A method for constructing capacity-achieving binary-input memoryless channels”, IEEE Trans. Inf. Theory, vol. 55, no. 7, pp. 3051-3073, July 2009, doi: 10.1109/TIT.2009.2021379.
[2] L. Chandesris, V. Savin and D. Declercq, "Dynamic-SCFlip Decoding of Polar Codes," in IEEE Trans. Commun., vol. 66, no. 6, pp. 2333-2345, June 2018, doi: 10.1109/TCOMM.2018.2793887.
[3] C. Leroux, A. J. Raymond, G. Sarkis and W. J. Gross, "A Semi-Parallel Successive-Cancellation Decoder for Polar Codes," in IEEE Trans. Signal Process., vol. 61, no. 2, pp. 289-299, Jan.15, 2013, doi : 10.1109/TSP.2012.2223693.
Pour plus d'information, lire notre article :
[4] I. Sagitov et al, “Successive-cancellation flip decoding of polar codes with a simplified restart mechanism,” IEEE Wireless Commun. And Netw. Conf. (WCNC), Glasgow, United Kingdom, 2023, pp. 1-6, doi: 10.1109/WCNC55385.2023.10119097.
