On the Successive Cancellation Decoding of Polar Codes with Arbitrary Linear Binary Kernels

• DOI: 10.48550/arxiv.1701.03264
• Publication Date: 2017-01-01
• Authors: Huang, Zhiliang; Zhang, Shiyi; Zhang, Feiyan; Duanmu, Chunjiang; Chen, Ming
• Keywords: FOS: Computer and information sciences; Computer Science - Information Theory; Information Theory (cs.IT); 0202 electrical engineering, electronic engineering, information engineering; 02 engineering and technology

A method for efficiently successive cancellation (SC) decoding of polar codes with high-dimensional linear binary kernels (HDLBK) is presented and analyzed. We devise a $l$-expressions method which can obtain simplified recursive formulas of SC decoder in likelihood ratio form for arbitrary linear binary kernels to reduce the complexity of corresponding SC decoder. By considering the bit-channel transition probabilities $W_{G}^{(\cdot)}(\cdot|0)$ and $W_{G}^{(\cdot)}(\cdot|1)$ separately, a $W$-expressions method is proposed to further reduce the complexity of HDLBK based SC decoder. For a $m\times m$ binary kernel, the complexity of straightforward SC decoder is $O(2^{m}N\log N)$. With $W$-expressions, we reduce the complexity of straightforward SC decoder to $O(m^{2}N\log N)$ when $m\leq 16$. Simulation results show that $16\times16$ kernel polar codes offer significant advantages in terms of error performances compared with $2\times2$ kernel polar codes under SC and list SC decoders.<br/>8 pages, 2 figures, submitted to ISIT2017<br/>