Towards Practical Software Stack Decoding of Polar Codes
Harsh Aurora, Warren J. Gross · arXiv (Cornell University) · 2018
Les codes correcteurs d'erreurs sont essentiels à la réalisation d'une communication fiable sur des canaux bruyants. Les codes polaires sont une classe récente de codes correcteurs d'erreurs en blocs linéaires, et sont les premiers à avoir une construction explicite et à atteindre asymptotiquement la capacité symétrique des canaux par rapport aux canaux d'entrée binaires sans mémoire discrète. Ils ont été récemment adoptés dans la norme 5G pour le canal de contrôle eMBB.L'algorithme de décodage à annulations successives par liste permet d'atteindre des performances de décodage presque optimales au prix d'une grande complexité d'implémentation. Il a été démontré que l'algorithme à annulations successives par pile fournit des performances de décodage similaires tout en ayant une complexité calculatoire beaucoup plus faible. Cependant, il requiert un important besoin de mémorisation qui évolue quadratiquement avec la longueur du code, ce qui le rend peu pratique. Cette thèse présente plusieurs approches pour augmenter l'aspect pratique de l'algorithme de décodage à annulations successives dans les implémentations logicielles. Tout d'abord, les copies multiples de la mémoire du décodeur sont remplacées par une seule mémoire, et l'étape de tri de la pile est remplacée par une recherche linéaire. Bien que cela se fasse au prix d'une complexité informatique accrue, les résultats montrent que les besoins importants en mémoire et en tri figurent parmi les principaux responsables des performances médiocres en termes de débit de l'algorithme de pile logicielle. Les simulations effectuées sur un CPU moderne cadencé à une fréquence de 3,2 GHz montrent une augmentation du débit de 14 Kbps à 6,3 Mbps pour un code polaire de longueur 1024. Cette idée est ensuite étendue pour permettre un nombre accordable de mémoires de décodeur instanciées, atténuant l'augmentation de la complexité de calcul tout en fournissant une augmentation modeste du débit. Troisièmement, un critère de fin prématurée est examiné et il est démontré qu'il réduit le nombre de bits estimés jusqu'à 58%. Enfin, les avantages du décodeur de listes d'annulation successives simplifiées et rapides sont étendus à l'algorithme de pile, ce qui se traduit par la première implémentation d'un décodeur de pile d'annulation successives simplifiées et rapides qui rapporte un débit de 20.44 Mbps.