Towards Practical Software Stack Decoding of Polar Codes

Book excerpt: "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." --