Folded successive cancelation decoding of polar codes

Polar codes are the first explicit class of codes that are provably capacity-achieving under the successive cancelation (SC) decoding. As a suboptimal decoder, SC has quasi-linear complexity N(1 + log N) in the code length N. In this paper, we propose a new non-binary SC decoder with reduced complexity N/2(1 + log N/2) based on the folding operation, which was first proposed in [11] to implement folded tree maximum-likelihood decoding of polar codes. Simulation results for the additive white Gaussian noise channel show that folded SC decoders can achieve the same error performance of standard SC by suitable selecting the folding of the polar code.