logo

SCIENCE CHINA Information Sciences, Volume 61, Issue 2: 022309(2018) https://doi.org/10.1007/s11432-017-9128-x

A complexity-reduced fast successive cancellation list decoder for polar codes

More info
  • ReceivedFeb 20, 2017
  • AcceptedApr 25, 2017
  • PublishedNov 20, 2017

Abstract

A multi-bit 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 error-correcting performance. However, list decoders are highly complex compared with decoders without a list algorithm. In this paper, a low-complexity list decoder is proposed, where path-splitting operations for a multi-bit 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 multi-bit decision processes, and a complexity-reduced 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 signal-to-noise ratio (SNR) region.


Acknowledgment

This work was partially supported by National Major Project (Grant No. 2016ZX030010- 11005), National Natural Science Foundation Project (Grant No. 61521061), and Intel Corporation.


References

[1] Arikan E. Channel polarization: a method for constructing capacity-achieving codes for symmetric binary-input memoryless channels. IEEE Trans Inf Theory, 2009, 55: 3051--3073. 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: 205--208. Google Scholar

[3] Alamdar-Yazdi A, Kschischang F R. A simplified successive-cancellation decoder for polar codes. IEEE Commun Lett, 2011, 15: 1378--1380. Google Scholar

[4] Sarkis G, Giard P, Vardy A, et al. Fast polar decoders: algorithm and implementation. IEEE J Sel Areas Commun, 2014, 32: 946--957. Google Scholar

[5] Tal I, Vardy A. List decoding of polar codes. IEEE Trans Inf Theory, 2015, 61: 2213--2226. Google Scholar

[6] Niu K, Chen K. CRC-aided decoding of polar codes. IEEE Commun Lett, 2012, 16: 1668--1671. 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. 1--5. 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. 1--6. Google Scholar

[9] Sarkis G, Giard P, Vardy A, et al. Fast list decoders for polar codes. IEEE J Sel Areas Commun, 2016, 34: 318--328. 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: 2044--2047. Google Scholar

[11] Chen K, Li B, Shen H, et al. Reduce the complexity of list decoding of polar codes by tree-pruning. IEEE Commun Lett, 2016, 20: 204--207. Google Scholar

[12] Zhang Z, Zhang L, Wang X, et al. A split-reduced successive cancellation list decoder for polar codes. IEEE J Sel Areas Commun, 2016, 34: 292--302. Google Scholar

[13] Yuan B, Parhi K K. LLR-based successive-cancellation list decoder for polar codes with multi-bit decision. IEEE Trans Circuits Syst II Express Briefs, 2016, 64: 21--25. Google Scholar

[14] Tal I, Vardy A. How to construct polar codes. IEEE Trans Inf Theory, 2013, 59: 6562--6582. Google Scholar

[15] Wu D, Li Y, Sun Y. Construction and block error rate analysis of polar codes over AWGN channel based on Gaussian ap-proximation. IEEE Commun Lett, 2014, 18: 1099--1102. 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 N=8.

  • Figure 3

    (Color online) BLER performance of different $\rho$ for N=1024, L=32.

  • Figure 4

    (Color online) Average complexity of different $\rho$ for N=1024, L=32.

  • Figure 5

    (Color online) BLER performance for L=8, N=256, 1024 and 4096.

  • Figure 6

    (Color online) Average complexity for L=8, N=256, 1024 and 4096.

  • Figure 7

    (Color online) Average complexity for N=1024, L=8, 16, 32.

  • Figure 8

    (Color online) BLER performance for N=1024, L=8, 16, 32.

  •   

    Algorithm 1 Complexity reduced fast SSC list decoder

    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$.

    if current node $v~\in~\left\{~{{\rm{Rate~-~0,~Rate~-~1,~REP}},{\rm{~SPC}}}~\right\}$ then

    for each source path l

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

    if $|{\alpha~_v}[\min~]|~>~{\rm~TL}_{N}^j$ then

    Do not split new paths;

    else

    Generate new path according to Subsection 3.3;

    end if

    end for

    Prune paths if path number exceeds the specific list size L;

    else

    Calculate ${{\boldsymbol{\alpha~}}_l}$ of each path: ${\alpha~_l}[i]~=~{{F}}\left(~{{\alpha~_v}[2i~-~1],{\alpha~_v}[2i]}~\right)$;

    go to the left child node;

    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)$;

    go to the right child node;

    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\}$;

    return to parent node;

    end if

    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