logo

SCIENCE CHINA Information Sciences, Volume 63 , Issue 10 : 202303(2020) https://doi.org/10.1007/s11432-019-2924-6

Efficient stochastic successive cancellation listdecoder for polar codes

Xiao LIANG 1,2,3,4, Huizheng WANG 1,2,3,4, Yifei SHEN 1,2,3,4, Zaichen ZHANG 1,2,3,4, Xiaohu YOU 1,2,3,4, Chuan ZHANG 1,2,3,4,*
More info
  • ReceivedDec 29, 2019
  • AcceptedMay 22, 2020
  • PublishedSep 21, 2020

Abstract

Polar codes are one of the most favorable capacity-achieving codes owing to their simple structures and low decoding complexity. Successive cancellation list (SCL) decoders with large list sizes achieve performances very close to those of maximum-likelihood (ML) decoders. However, hardware cost is a severe problem because an SCL decoder with list size $L$ consists of $L$ copies of a successive cancellation (SC) decoder. To address this issue, a stochastic SCL (SSCL) polar decoder is proposed. Although stochastic computing can achieve a good hardware reduction compared with the deterministic one, its straightforward application to an SCL decoder is not well-suited owing to the precision loss and severe latency. Therefore, a doubling probability approach and adaptive distributed sorting (DS) are introduced. A corresponding hardware architecture is also developed. Field programmable gate array (FPGA) results demonstrate that the proposed stochastic SCL polar decoder can achieve a good performance and complexity tradeoff.


Acknowledgment

This work was supported in part by National Key RD Program of China (Grant No. 2020YFB220-5503), National Natural Science Foundation of China (Grant Nos. 61871115, 61501116), Jiangsu Provincial NSF for Excellent Young Scholars (Grant No. BK20180059), Six Talent Peak Program of Jiangsu Province (Grant No. 2018-DZXX-001), Distinguished Perfection Professorship of Southeast University, Fundamental Research Funds for the Central Universities, and Student Research Training Program of Southeast University.


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. In: Proceedings of the IEEE International Symposium on Information Theory Proceedings, Petersburg, 2011. 1--5. Google Scholar

[3] Chen K, Niu K, Lin J R. List successive cancellation decoding of polar codes. Electron Lett, 2012, 48: 500-501 CrossRef ADS arXiv Google Scholar

[4] Yu Y, Pan Z, Liu N. Low-complexity polar code construction for higher order modulation. Sci China Inf Sci, 2019, 62: 209301 CrossRef Google Scholar

[5] Yu Y, Pan Z, Tan X. A latency-reduced successive cancellation list decoder for polar codes. Sci China Inf Sci, 2019, 62: 029302 CrossRef Google Scholar

[6] Gaines B R. Stochastic computing systems. In: Advances in Information Systems Science. Boston: Springer, 1969. 37--172. Google Scholar

[7] Moons B, Verhelst M. Energy-Efficiency and Accuracy of Stochastic Computing Circuits in Emerging Technologies. IEEE J Emerg Sel Top Circuits Syst, 2014, 4: 475-486 CrossRef ADS Google Scholar

[8] Brown B D, Card H C. Stochastic neural computation. I. Computational elements. IEEE Trans Comput, 2001, 50: 891-905 CrossRef Google Scholar

[9] Wang H Z, Zhang Z C, You X H, et al. Low-complexity Winograd convolution architecture based on stochastic computing. In: Proceedings of the IEEE International Conference on Digital Signal Processing, Shanghai, 2018. 1--5. Google Scholar

[10] Ceroici C, Gaudet V C. FPGA implementation of a clockless stochastic LDPC decoder. In: Proceedings of the IEEE Workshop on Signal Processing Systems, Belfast, 2014. 1--5. Google Scholar

[11] Chen J, Hu J, Sobelman G E. Stochastic MIMO Detector Based on the Markov Chain Monte Carlo Algorithm. IEEE Trans Signal Process, 2014, 62: 1454-1463 CrossRef ADS Google Scholar

[12] Chen J, Hu J, Sobelman G E. Stochastic Iterative MIMO Detection System: Algorithm and Hardware Design. IEEE Trans Circuits Syst I, 2015, 62: 1205-1214 CrossRef Google Scholar

[13] Liang X, Zhang C, Xu M H, et al. Efficient stochastic list successive cancellation decoder for polar codes. In: Proceedings of the IEEE International System-on-Chip Conference, Beijing, 2015. 421-426. Google Scholar

[14] Tal I, Vardy A. List decoding of polar codes. In: Proceedings of the IEEE International Symposium on Information Theory Proceedings, Petersburg, 2011. 1--5. Google Scholar

[15] Bakulin M, Kreyndelin V, Rog A, et al. MMSE based K-best algorithm for efficient MIMO detection. In: Proceedings of the International Congress on Ultra Modern Telecommunications and Control Systems and Workshops, Munich, 2017. 258--263. Google Scholar

[16] Yuan B, Parhi K K. Successive cancellation decoding of polar codes using stochastic computing. In: Proceedings of the IEEE International Symposium on Circuits and Systems, Lisbon, 2015. 3040--3043. Google Scholar

[17] Sharifi Tehrani S, Mannor S, Gross W J. Fully Parallel Stochastic LDPC Decoders. IEEE Trans Signal Process, 2008, 56: 5692-5703 CrossRef ADS Google Scholar

[18] Xu Z L, Niu K. Successive cancellation decoders of polar codes based on stochastic computation. In: Proceedings of the IEEE 25th Annual International Symposium on Personal, Indoor, and Mobile Radio Communication, Washington, 2014. 908--912. Google Scholar

[19] Zhang Z, Zhang L, Wang X. A Split-Reduced Successive Cancellation List Decoder for Polar Codes. IEEE J Sel Areas Commun, 2016, 34: 292-302 CrossRef Google Scholar

[20] Liang X, Yang J M, Zhang C, et al. Hardware efficient and low-latency CA-SCL decoder based on distributed sorting. In: Proceedings of the IEEE Global Communications Conference, Washington, 2016. 1--6. Google Scholar

[21] Zhang C, Parhi K K. Low-Latency Sequential and Overlapped Architectures for Successive Cancellation Polar Decoder. IEEE Trans Signal Process, 2013, 61: 2429-2441 CrossRef ADS Google Scholar

[22] Xiong C, Zhong Y, Zhang C, et al. An FPGA emulation platform for polar codes. In: Proceedings of the IEEE Workshop on Signal Processing Systems, 2016. 148--153. Google Scholar

  • Figure 5

    (Color online) Candidate paths' selection in polar SCL decoder ($L=4$).

  • Figure 8

    (Color online) Binary-tree of stochastic SCL decoder in double-level ($L=2$).

  • Figure 9

    (Color online) Candidate paths' selection in polar SCL decoder with double-level ($L=4$).

  • Figure 16

    (Color online) Mixed node II for the last stage, also mixed node III for the first stage in SCL decoding.

  • Figure 17

    (Color online) The $8$-bit stochastic SC decoder with double-level decoding.

  • Figure 18

    (Color online) The $N$-bit stochastic SCL decoder with double-level decoding.

  • Figure 19

    (Color online) The architecture of list core module with ADS method and enlarging probability approach.

  • Figure 20

    (Color online) Decoding schedule for $N$-bit stochastic SCL decoder with double-level decoding.

  •   

    Algorithm 1 Proposed ADS algorithm

    setstretch0.7

    Require:$~$ $s1:jk=\{00,01\}$; $s2:jk=\{00,10\}$; $s3:jk=\{00,01,10,11\}$; $\mathbf{I}$: $L$ previous path numbers; $[\mathbf{PPM}_{\rm~FC},~\mathbf{JK}]=\max\nolimits_{s1,~s2,~s3~}(\mathbf{PPM}(\hat{u}_{1}^{2i-2}|\hat{u}_{1}^{2i-1}=j,\hat{u}_{1}^{2i}=k))$; $\mathbf{PPM}_{\rm~NC}$, expanded paths list $\mathbb{P}$.

    Output:$~$ Updated paths list $\mathbb{P}_{\mathrm{new}}=[\mathbb{P}(\mathbf{I}),~\mathbf{J},~\mathbf{K}]$ and PPM list $\mathbf{PPM}_{s}$.

    $[\mathbf{PPM}_{s},~\mathbf{Ix},~\mathbf{JKx}]=\mathrm{sort}(\mathbf{PPM}_{\rm~FC},~{\rm~ascend})$;

    $[\mathbf{PPM}_{1},~\mathbf{Iy},~\mathbf{JKy}]=\mathrm{sort}(\mathbf{PPM}_{\rm~NC},~{\rm~descend})$;

    for $i=1:L-1$

    $f=0$;

    if $(\mathrm{PPM}_{1,i}\leqslant\mathrm{PPM}_{s,i})$ then

    $f=1$;

    else

    $f=0$;

    end if

    if ($f==0$) then

    Update $\mathbf{I}$: replace $\mathbf{I}\big(Ix(i)\big)$ with $\mathbf{I}\big(Iy(i)\big)$;

    Update ${\boldsymbol~u}_{2i-1}{\boldsymbol~u}_{2i}$: $\mathbf{JK}\big(JKx(i)\big)=\mathbf{JK}\big(JKy(i)\big)$;

    else

    break;

    end if

    end for

    Updated paths list $\mathbb{P}_{\mathrm{new}}=[\mathbb{P}(\mathbf{I}),~\mathbf{J},~\mathbf{K}]$ and PPM list $\mathbf{PPM}_{s}$.

  • Table 1  

    Table 1The complexity of different modules of stochastic SCL decoder$^{\rm~a)}$

    ModulesMixed node I Mixed node IIMixed node III SC decoder$^{\rm~a)}$SCL decoder$^{\rm~b)}$
    XOR $1$ $1$ $1$ $N-1$ $NL/2-L+N/2$
    NOT 3 6 5 $3N$ ${3NL}/{2}+{5N}/{2}$
    AND $2$ $8$ $4$ $2N+4$ $NL+4L+2N$
    1-bit register $1$ $1$ $1$ $N-1$ ${NL}/{2}-L+{N}/{2}$
    JK-FF $1$ $2$ $2$ $N$ ${NL}/{2}+N$
    MUX $2$ $2(N-2)$ $NL+N-4L$
    Counter $4$ $4L$

    a) $N$ and $L$ denote the code length and list size, respectively; b) Double-level decoding.

  • Table 2  

    Table 2Comparison of the implementation results of several FPGA-based SCL architectures

    Decoder [20] [22] SSCL$^{\rm~a)}$ SSCL$^{\rm~a)}$
    with $1$-level decoding with $2$-level decoding
    FPGA device$^{\rm~b)}$ Altera stratix V Xilinx Kintex 7Altera stratix V Altera stratix V
    $(N,~L,~R)$ $(1024,~4,~0.5)$ $(1024,~4,~0.5)$ $(1024,~4,~0.5)$ $(1024,~4,~0.5)$
    ALMs(A)/LUTs(X)$^{\rm~c)}$$101160$$142961$ $8080$ $8146$
    Registers $13544$ $19795$$2824$ $2862$
    $f_{op}$ (MHz) $42.66$$462.9$ $445.2$
    Latency (cycles) $4064$ $371$ $2^{20}$ $2^{19}$
    TP (Mbps)$115$ $0.452$ $0.871$

    a) Stream length $l=1024$. b) All the FPGAs are manufactured on 28 nm process technology. c) An ALM on Altera FPGA can be used as a 6-input LUT.

  •   

    Algorithm 2 ADS algorithm for $2^p$ level decoder

    setstretch0.7

    Require:$~$ $2^p$-level scheme, list size is $L$;

    Output:$~$ Final $L$ candidates.

    for $i=1:L$

    Choose the best PPM as FC$_i$, the rest as $\mathbf{NC}_i=[{\rm~NC}_{i,1},~{\rm~NC}_{i,2},\ldots,~{\rm~NC}_{i,(2^{2^P}-1)L}]$;

    Set $\mathbf{FC}=[{\rm~FC}_1,~{\rm~FC}_2,\ldots,~{\rm~FC}_L]$;

    end for

    Set candidates$=[{\rm~FC}_1,{\rm~FC}_2,\ldots,{\rm~FC}_L]$;

    for $i=1:L$

    Choose the best PPM of each $\mathbf{NC}_i$;

    $\mathbf{NC^k}=[{\rm~NC}_{1k},~{\rm~NC}_{2k},\ldots,~{\rm~NC}_{Lk}]$;

    end for

    Select the worst PPM ${\rm~FC}_k$ of $\mathbf{FC}$;

    Select the best PPM ${\rm~NC}_{pk}$ of $\mathbf{NC}^k$, $p$ denotes ${\rm~NC}_{pk}$ is from $\mathbf{NC}_{p}$;

    if ${\rm~NC}_{pk}<{\rm~FC}_k$ then

    Jump to line $21$;

    else

    Keep on;

    end if

    Replace ${\rm~FC}_k$ with ${\rm~NC}_{pk}$ in $\mathbf{candidates}$;

    Cancel ${\rm~FC}_k$ from $\mathbf{FC}$, cancel ${\rm~NC}_{pk}$ from $\mathbf{NC}_p$;

    Select the best PPM of $\mathbf{NC}_p$ as ${\rm~NC}_{pk}$;

    Jump to line $10$;

    Output final $L$ $\mathbf{candidates}$.

Copyright 2020  CHINA SCIENCE PUBLISHING & MEDIA LTD.  中国科技出版传媒股份有限公司  版权所有

京ICP备14028887号-23       京公网安备11010102003388号