logo

SCIENCE CHINA Information Sciences, Volume 62, Issue 8: 082303(2019) https://doi.org/10.1007/s11432-018-9743-0

Sphere decoder for polar codes concatenated with cyclic redundancy check

More info
  • ReceivedJul 2, 2018
  • AcceptedDec 6, 2018
  • PublishedMay 30, 2019

Abstract

The existing cyclic redundancy check (CRC)-aided successive cancellation list (CA-SCL) decoder partitions the decoding process into two steps,where an SCL is followed by a CRC check. An SCL decoder can approach the maximum-likelihood (ML) decoding performance of the inner polar codes using a sufficiently large list; however, in this case, CRC is only used for performing error detection. Therefore, the decoding performance of the outer CRC is different from that of ML because the errors are not rectified, which degrades the performance of the entire concatenated codes. In this study, we propose a sphere decoder (SD)that can achieve the ML performance of polar codes concatenated with CRC to address the suboptimality of CA-SCL decoding. The proposed SD performs joint decoding of the CRC-polar codes in a single step, thereby avoiding the polar decoding and CRC detection decoding scheme. Because the proposed SD guarantees the ML decoding performance of the CRC-polar concatenated codes, the simulation results demonstrate that the block error rate (BLER) of the proposed SD acts as the lower bound of the CA-SCL decoding performance. Further, a new initial radius selection method is proposed for the SD to reduce the average decoding complexity. The simulations demonstrate that the proposed initial radius selection method reduces more amount of decoding complexity when compared with that reduced using sequential step size methods.


Acknowledgment

This work was partially supported by National Major Project (Grant No. 2017ZX03001002-004), National Natural Science Foundation Project (Grant No. 61521061), National Natural Science Foundation of China (Grant No. 61571123), and 333 Program of Jiangsu (Grant No. BRA2017366).


References

[1] Arikan E. Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels. IEEE Trans Inform Theor, 2009, 55: 3051-3073 CrossRef Google Scholar

[2] Tal I, Vardy A. List Decoding of Polar Codes. IEEE Trans Inform Theor, 2015, 61: 2213-2226 CrossRef Google Scholar

[3] Niu K, Chen K. CRC-Aided Decoding of Polar Codes. IEEE Commun Lett, 2012, 16: 1668-1671 CrossRef Google Scholar

[4] Tahir B, Schwarz S, Rupp M. BER comparison between convolutional, turbo, LDPC, and polar codes. In: Proceedings of the 24th International Conference on Telecommunications (ICT), Limassol, 2017. 1--7. Google Scholar

[5] Cao C, Kuang J, Fei Z. Low complexity list successive cancellation decoding of polar codes. IET Commun, 2014, 8: 3145-3149 CrossRef Google Scholar

[6] Xu Q Y, Pan Z W, Liu N. A complexity-reduced fast successive cancellation list decoder for polar codes. Sci China Inf Sci, 2018, 61: 022309 CrossRef Google Scholar

[7] Ryan W E, Lin S. Channel Codes Classical And Modern. New York: Cambridge University Press Ltd., 2009. 110--111. Google Scholar

[8] Kazakov P. Fast calculation of the number of minimum-weight words of CRC codes. IEEE Trans Inform Theor, 2001, 47: 1190-1195 CrossRef Google Scholar

[9] Castagnoli G, Brauer S, Herrmann M. Optimization of cyclic redundancy-check codes with 24 and 32 parity bits. IEEE Trans Commun, 1993, 41: 883-892 CrossRef Google Scholar

[10] Kahraman S, Celebi M E. Code based efficient maximum-likelihood decoding of short polar codes. In: Proceedings of 2012 IEEE International Symposium on Information Theory (ISIT), Cambridge, 2012. 1967--1971. Google Scholar

[11] Niu K, Chen K, Lin J. Low-Complexity Sphere Decoding of Polar Codes Based on Optimum Path Metric. IEEE Commun Lett, 2014, 18: 332-335 CrossRef Google Scholar

[12] Guo J, Fabregas A G. Efficient sphere decoding of polar codes. In: Proceedings of IEEE International Symposium on Information Theory (ISIT), Hong Kong, 2015. 236--240. Google Scholar

[13] Hashemi S A, Condo C, Gross W J. List sphere decoding of polar codes. In: Proceedings of the 49th Asilomar Conference on Signals, Systems and Computers, Pacific Grove, 2015. 1346--1350. Google Scholar

[14] Hashemi S A, Condo C, Gross W J. Matrix reordering for efficient list sphere decoding of polar codes. In: Proceedings of 2016 IEEE International Symposium on Circuits and Systems (ISCAS), Montreal, 2016. 1730--1733. Google Scholar

[15] Husmann C, Nikolaou P C, Nikitopoulos K. Reduced Latency ML Polar Decoding via Multiple Sphere-Decoding Tree Searches. IEEE Trans Veh Technol, 2018, 67: 1835-1839 CrossRef Google Scholar

[16] Trifonov P. Efficient Design and Decoding of Polar Codes. IEEE Trans Commun, 2012, 60: 3221-3227 CrossRef Google Scholar

[17] Tal I, Vardy A. How to Construct Polar Codes. IEEE Trans Inform Theor, 2013, 59: 6562-6582 CrossRef Google Scholar

[18] He G, Belfiore J C, Land I, et al. Beta-expansion: a theoretical framework for fast and recursive construction of polar codes. In: Proceedings of IEEE Global Communications Conference, Singapore, 2017. 1--6. Google Scholar

[19] Koopman P, Chakravarty T. Cyclic redundancy code (CRC) polynomial selection for embedded networks. In: Proceedings of International Conference on Dependable Systems and Networks, Florence, 2004. 145--154. Google Scholar

[20] Agrell E, Eriksson T, Vardy A. Closest point search in lattices. IEEE Trans Inform Theor, 2002, 48: 2201-2214 CrossRef Google Scholar

[21] Zhang Q, Liu A, Pan X. CRC Code Design for List Decoding of Polar Codes. IEEE Commun Lett, 2017, 21: 1229-1232 CrossRef Google Scholar

[22] Hassibi B, Vikalo H. On the sphere-decoding algorithm I. Expected complexity. IEEE Trans Signal Process, 2005, 53: 2806-2818 CrossRef ADS Google Scholar

[23] Zhao W, Giannakis G B. Sphere Decoding Algorithms With Improved Radius Search. IEEE Trans Commun, 2005, 53: 1104-1109 CrossRef Google Scholar

[24] Balatsoukas-Stimming A, Parizi M B, Burg A. LLR-Based Successive Cancellation List Decoding of Polar Codes. IEEE Trans Signal Process, 2015, 63: 5165-5179 CrossRef Google Scholar

  • Figure 1

    (Color online) Sphere decoding process.

  • Table 1   CRC codeword weight distributions$^{\rm~a)b)c)}$
    $g(x)$ $d_{\text{min}}$ $d_{\text{min2}}$ $d_{\text{min3}}$ $A_{d_{\text{min}}}$ $A_{d_{\text{min2}}}$ $A_{d_{\text{min2}}}$
    $x^6~+~x~+~1$ 3 4 5 53 329 1541
    $x^8~+~x^7~+~x^6~+~x^5~+~x^4~+~x^3~+~1$ 3 4 5 26 347 2673

    a

  •   

    Algorithm 1 Proposed sphere decoder, main function

    Input: $g(x)$, ${{\boldsymbol~G}}_{\mathcal{A},~p}$, $\tilde{{\boldsymbol~y}}_1^N$.

    Output: $\hat{{\boldsymbol~u}}_{1,\text{output}}^K$.

    Calculate ${\boldsymbol~G}_{\text{CRC}}$ through $g(x)$;

    ${\boldsymbol~G}~=~{\boldsymbol~G}_{\text{CRC}}{\boldsymbol~G}_{\mathcal{A},~p}$;

    Obtain ${\boldsymbol~P}$ in Definition 2;

    $\hat{{\boldsymbol~u}}_1^K~\Leftarrow~$ null array; //Temporary bit estimate

    ${\boldsymbol~d}_1^K~\Leftarrow~$ null array; //Distance metric

    $\overline{{\boldsymbol~d}}_1^K~\Leftarrow~$ null array; //Auxiliary distance metric to avoid redundant calculations

    $r~\Leftarrow~+\infty~$; //Initial radius

    $\hat{{\boldsymbol~u}}_{1,\text{output}}^K~\Leftarrow$ SphereDecoder($K,~{\boldsymbol~P},~{\boldsymbol~G},~\tilde{{\boldsymbol~y}}_1^N,~\hat{{\boldsymbol~u}}_1^K,~{\boldsymbol~d}_1^K,~\overline{{\boldsymbol~d}}_1^K,~r$).

  •   

    Algorithm 2 SphereDecoder

    Input: $k,~{\boldsymbol~P},~{\boldsymbol~G},~\tilde{{\boldsymbol~y}}_1^N,~\hat{{\boldsymbol~u}}_1^K,~{\boldsymbol~d}_1^K,~\overline{{\boldsymbol~d}}_1^K,~r$. Output: $\hat{{\boldsymbol~u}}_{1,\mbox{current~optimal}}^K$.

    for $a~\Leftarrow~1:~2$

    if $a~=~1$ then

    $\hat{u}_k,~d_k,~\overline{d}_k]~\Leftarrow$ SelectFirstBit($k,~{\boldsymbol~P},~{\boldsymbol~G},~\tilde{{\boldsymbol~y}}_1^N,~\hat{{\boldsymbol~u}}_1^K$);

    else

    $\hat{u}_k~\Leftarrow~\hat{u}_k~\oplus~1$, $d_k~\Leftarrow~\overline{d}_k$;

    end if

    if $\sum_{i=k}^Kd_i~>~r^2$ then

    continue //Pruning operation

    else

    if $k~=~1$ then

    $r^2~\Leftarrow~\sum_{i=1}^{K}~d_i$; //Update radius

    $\hat{{\boldsymbol~u}}_{1,\mbox{current~optimal}}^K~\Leftarrow~\hat{{\boldsymbol~u}}_1^K$; //Update bit estimate

    else

    $\hat{{\boldsymbol~u}}_{1,\text{current~optimal}}^K~~\Leftarrow$ SphereDecoder($k-1,~{\boldsymbol~P},~{\boldsymbol~G},~\tilde{{\boldsymbol~y}}_1^N,~\hat{{\boldsymbol~u}}_1^K,~{\boldsymbol~d}_1^K,~\overline{{\boldsymbol~d}}_1^K,~r$).

    end if

    end if

    end for

  •   

    Algorithm 3 SelectFirstBit

    Input: $k,{\boldsymbol~P},~{\boldsymbol~G},~\tilde{{\boldsymbol~y}}_1^N,~\hat{{\boldsymbol~u}}_1^K$. Output: $\hat{u}_k,~d_k,~\overline{d}_k$.

    $\hat{u}_k~\Leftarrow~0$;

    $d_{\text{tmp1}}~\Leftarrow~\sum_{i~=~{\boldsymbol~P}_{k,1}}^{{\boldsymbol~P}_{k,2}}(\tilde{y_i}~-~\sum_{j~=~k}^{K}~\hat{u}_j~G_{j,i})^2$;

    $\hat{u}_k~\Leftarrow~1$;

    $d_{\text{tmp2}}~\Leftarrow~\sum_{i~={\boldsymbol~P}_{k,1}}^{{\boldsymbol~P}_{k,2}}(\tilde{y_i}~-\sum_{j~=~k}^{K}~\hat{u}_j~G_{j,i})^2$;

    if $d_{\text{tmp1}}~>~d_{\text{tmp2}}$ then

    $\hat{u}_k~\Leftarrow~1$;

    $d_k~\Leftarrow~d_{\text{tmp2}}$;

    $\overline{d}_k~\Leftarrow~d_{\text{tmp1}}$;

    else

    $\hat{u}_k~\Leftarrow~0$;

    $d_k~\Leftarrow~d_{\text{tmp1}}$;

    $\overline{d}_k~\Leftarrow~d_{\text{tmp2}}$.

    end if

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1