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


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