Low-Complexity Software Stack Decoding of Polar Codes

Abstract

Polar codes are a recent class of linear error-correcting codes that asymptotically achieve the channel capacity at infinite code length. The Successive Cancellation List (SCL) algorithm yields very good error-correction performance, at the cost of high implementation complexity. The Stack (SCS) decoding algorithm provides similar error-correction performance at a lower complexity. In this work, we propose an efficient software implementation of the SCS decoding algorithm, along with techniques to further reduce its computational complexity. In particular, we reduce the SCS memory requirements through efficient path switching, replace the stack sorting with a linear search, and explore the use of a partial CRC along with an early termination criterion. Using the proposed methods, we are able to reduce the computational complexity of the SCS decoder, reducing the number of estimated bits up to 97% with respect to SCL, while maintaining similar error-correction performance as SCL.