Multiple Folding for Successive Cancelation Decoding of Polar Codes

Abstract

Polar coding is known as the first provably capacity-achieving coding scheme under low-complexity suboptimal successive cancelation decoding (SCD). The large error-correction capability of finite-length polar codes is mostly achieved with relatively long codes. SCD is the conventional decoder for polar codes and exhibits a quasi-linear complexity in terms of the code length. Practical decoder schemes with low latency are important for high-speed polar coding applications. In this letter, we propose a nonbinary multiple folded SCD scheme to reduce the decoding latency of standard binary polar codes. Multiple foldings were first proposed to improve the efficiency of folded tree maximum-likelihood decoder for Kronecker product-based codes. By successively applying the folding operation $\kappa$ times on the SCD, for a code length $N$ , the latency is reduced from $2N-1$ to $(N/2^{\kappa-1})-1$ time slots, assuming full parallelization. We show that multiple folded SCD can be effectively implemented for up to $\kappa=3$ foldings due to memory limitations. This decoder achieves exactly the same performance of the original SCD with significantly reduced latency.