A multibit decision for polar codes based on a simplified successive cancellation (SSC) decoding algorithm can improve the throughput of polar decoding. A list algorithm is used to improve the errorcorrecting performance. However, list decoders are highly complex compared with decoders without a list algorithm. In this paper, a lowcomplexity list decoder is proposed, where pathsplitting operations for a multibit decision can be avoided, if the decoding reliability exceeds a threshold. The threshold is determined based on the reliability of subchannels and positions of decoding nodes. Path splitting rules are designed for multibit decision processes, and a complexityreduced list decoder is proposed based on this. Results show that the number of survival paths can be greatly reduced at the cost of negligible deterioration in block error performance. Thus, the computational complexity can be significantly reduced, especially for a high signaltonoise ratio (SNR) region.
This work was partially supported by National Major Project (Grant No. 2016ZX030010 11005), National Natural Science Foundation Project (Grant No. 61521061), and Intel Corporation.
[1] Arikan E. Channel polarization: a method for constructing capacityachieving codes for symmetric binaryinput memoryless channels. IEEE Trans Inf Theory, 2009, 55: 30513073. Google Scholar
[2] Arikan E, Costello D J, Kliewer J, et al. Guest editorial recent advances in capacity approaching codes. IEEE J Sel Areas Commun, 2016, 34: 205208. Google Scholar
[3] AlamdarYazdi A, Kschischang F R. A simplified successivecancellation decoder for polar codes. IEEE Commun Lett, 2011, 15: 13781380. Google Scholar
[4] Sarkis G, Giard P, Vardy A, et al. Fast polar decoders: algorithm and implementation. IEEE J Sel Areas Commun, 2014, 32: 946957. Google Scholar
[5] Tal I, Vardy A. List decoding of polar codes. IEEE Trans Inf Theory, 2015, 61: 22132226. Google Scholar
[6] Niu K, Chen K. CRCaided decoding of polar codes. IEEE Commun Lett, 2012, 16: 16681671. Google Scholar
[7] Trifonov P, Miloslavskaya V. Polar codes with dynamic frozen symbols and their decoding by directed search. In: Proceedings of IEEE Information Theory Work, Sevilla, 2013. 15. Google Scholar
[8] Sarkis G, Giard P, Vardy A, et al. Increasing the speed of polar list decoders. In: Proceedings of IEEE Work Signal Process Syst, Belfast, 2014. 16. Google Scholar
[9] Sarkis G, Giard P, Vardy A, et al. Fast list decoders for polar codes. IEEE J Sel Areas Commun, 2016, 34: 318328. Google Scholar
[10] Li B, Shen H, Tse D. An adaptive successive cancellation list decoder for polar codes with cyclic redundancy check. IEEE Commun Lett, 2012, 16: 20442047. Google Scholar
[11] Chen K, Li B, Shen H, et al. Reduce the complexity of list decoding of polar codes by treepruning. IEEE Commun Lett, 2016, 20: 204207. Google Scholar
[12] Zhang Z, Zhang L, Wang X, et al. A splitreduced successive cancellation list decoder for polar codes. IEEE J Sel Areas Commun, 2016, 34: 292302. Google Scholar
[13] Yuan B, Parhi K K. LLRbased successivecancellation list decoder for polar codes with multibit decision. IEEE Trans Circuits Syst II Express Briefs, 2016, 64: 2125. Google Scholar
[14] Tal I, Vardy A. How to construct polar codes. IEEE Trans Inf Theory, 2013, 59: 65626582. Google Scholar
[15] Wu D, Li Y, Sun Y. Construction and block error rate analysis of polar codes over AWGN channel based on Gaussian approximation. IEEE Commun Lett, 2014, 18: 10991102. Google Scholar
Figure 1
(Color online) Decoding tree of an (8, 4) polar code.
Figure 2
(Color online) Delivery of LLR messages in decoding tree for
Figure 3
(Color online) BLER performance of different $\rho$ for
Figure 4
(Color online) Average complexity of different $\rho$ for
Figure 5
(Color online) BLER performance for
Figure 6
(Color online) Average complexity for
Figure 7
(Color online) Average complexity for
Figure 8
(Color online) BLER performance for
Decoding starts from the root node by setting ${\alpha~_v}[i]~=~\log~\left(~{\frac{{\Pr~({y_i}{x_i}~=~0)}}{{\Pr~({y_i}{x_i}~=~1)}}}~\right),{\rm{~for~}}~1~\le~i~\le~N$. 

Calculate ${{\boldsymbol{\beta~}}_v}$ according to Subsection 

Do not split new paths; 

Generate new path according to Subsection 


Prune paths if path number exceeds the specific list size 
Calculate ${{\boldsymbol{\alpha~}}_l}$ of each path: ${\alpha~_l}[i]~=~{{F}}\left(~{{\alpha~_v}[2i~~1],{\alpha~_v}[2i]}~\right)$; 

Calculate ${{\boldsymbol{\alpha~}}_r}$ of each path: ${\alpha~_r}[i]~=~{\mathop{~G}\nolimits}~\left(~{{\alpha~_v}[2i~~1],{\alpha~_v}[2i],{\beta~_l}[i]}~\right)$; 

Calculate ${{\boldsymbol{\beta~}}_v}$ of each path: $\left\{~{{\beta~_v}[2i~~1],{\beta~_v}[2i]}~\right\}~=~\left\{~{{\beta~_l}[i]~\oplus~{\beta~_r}[i],{\beta~_r}[i]}~\right\}$; 

When the decoding returns from the root node, select the final output that satisfies the CRC constraint. 
Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有
京ICP备18024590号1