Towards practical software stack decoding of polar codes

Error correcting codes are essential in realizing reliable communication over noisy channels. Polar codes are a recent class of linear block error correcting codes, and are the first of their kind to have an explicit construction and asymptotically achieve the symmetric channel capacity over binary-input discrete memoryless channels. They have recently been adopted into the 5G standard in the eMBB control channel. The successive cancellation list decoding algorithm yields near-optimal decoding performance at the cost of high implementation complexity. The successive cancellation stack algorithm has been shown to provide similar decoding performance at a much lower computational complexity, but suffers from a large memory requirement that scales quadratically with the code length, rendering it impractical in most applications. This thesis presents several approaches to increase the practicality of the successive cancellation stack decoding algorithm in software implementations. First, multiple copies of decoder memory are replaced with a single memory, and the stack sorting step is replaced by a linear search. While this comes at the cost of an increase in computational complexity, results show that the large memory requirement and sorting are amongst primary culprits in the mediocre throughput performance of the software stack algorithm. Simulations run on a modern CPU clocked at 3.2 GHz show the throughput increase from 14 Kbps to 6.3 Mbps for a polar code of length 1024. This idea is then extended to allow for a tunable number of decoder memories instantiated, mitigating the increase in computational complexity while providing modest increase in throughput. Third, an early termination criterion is investigated that is shown to reduce the number of bit estimates by up to 58%. Finally, the benefits of the fast simplified successive cancellation list decoder are extended to the stack algorithm, resulting in the first reported implementation of a fast simplified successive cancellation stack decoder that reports a throughput of up to 20.44 Mbps.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