SCIENTIA SINICA Informationis, Volume 51 , Issue 8 : 1331(2021) https://doi.org/10.1360/SSI-2020-0124

Enhanced stochastic soft decoding algorithm for Reed-Solomon codes

More info
  • ReceivedMay 7, 2020
  • AcceptedDec 7, 2020
  • PublishedAug 3, 2021


Funded by



[1] Massey J. Shift-register synthesis and BCH decoding. IEEE Trans Inform Theor, 1969, 15: 122-127 CrossRef Google Scholar

[2] Sugiyama Y, Kasahara M, Hirasawa S, et al. A method for solving key equation for decoding goppa codes. Information and Control.27, 1975. 87-99. Google Scholar

[3] Xing J, Chen L, Bossert M. Low-Complexity Koetter-Vardy Decoding of Reed-Solomon Codes using Module Minimization. ICC 2019 - 2019 IEEE International Conference on Communications (ICC), Shanghai, China, 2019. 1-6. Google Scholar

[4] Lee H, Wu J, Wang C,et al. An iterative soft-decision decoding algorithm for Reed-Solomon codes. 2017 IEEE International Symposium on Information Theory (ISIT), Aachen, 2017. 2775-2779. Google Scholar

[5] Zhang W, Wang S, Luo H. High-Performance Soft Decision Algorithm for Bursty Channel Decoding of Reed-Solomon Codes. IEEE Commun Lett, 2019, 23: 1141-1144 CrossRef Google Scholar

[6] Chase D. Class of algorithms for decoding block codes with channel measurement information. IEEE Transactions on Information Theory, 2003, 18(1):170-182. Google Scholar

[7] Leroux C, Hemati S, Mannor S, et al. Stochastic Chase Decoding of Reed-Solomon Codes. IEEE Communications Letters, September 2010, 14(9): 863-865. Google Scholar

[8] Mani H, Hemati S. Symbol-Level Stochastic Chase Decoding of Reed-Solomon and BCH Codes. IEEE Transactions on Communications, Aug. 2019, 67(8): 5241-5252. Google Scholar

[9] Chu S, Chen Y, Chiu Y. Fast chase algorithms for decoding Reed-Solomon codes. 2014 International Symposium on Next-Generation Electronics (ISNE), Kwei-Shan, 2014. 1-3. Google Scholar

  • Table 1   FER gain of different stochastic algorithms for different RS codes compared with BM-HD ($\tau~=~128~/~{\rm~FER}$protect łinebreak $=10^{-4}$) (dB)
    RS codes RS16(11,5) RS16(15,9) RS32(31,25)
    BSCA(128)/BPSK 2.77 2.375 1.825
    EO-BSCA(128)/BPSK 3.16 2.375 1.795
    SSCA(128)/BPSK 2.87 2.42 1.44
    EO-SSCA(128)/BPSK 3.086 2.44 1.4
    SSCA(128)/M-QAM 1.01(16-QAM) 0.37(16-QAM) 0.948(32-QAM)
    EO-SSCA(128)/M-QAM 1.08(16-QAM) 0.52(16-QAM) 0.943(32-QAM)

    Algorithm 1 Bit-wise stochastic Chase algorithm


    Compute $p_i$ according to Eq. (1), where $i=0,1,\ldots,nm-1$;

    for $0\leq~i~\leq~nm-1$

    if $p_i\leq~0.5-\theta$ then

    $p_i=0$, where $0\leq~\theta~\leq~0.5$;ELSIF$p_i\ge~0.5+\theta$



    $p_i=\cfrac{1}{1+{\rm~e}^{\beta~y_i}}$, where $\beta~>~0$;

    end if

    end for


    for $1\leq~t~\leq~\tau$

    for $0\leq~i~\leq~nm-1$

    Generate a uniformly distributed random value: $\alpha_i\in~[0,1]$;


    end for

    Convert the binary vector $(y_0^t,y_1^t,\ldots,y_{nm-1}^t)$ to symbol vector $\boldsymbol{Y}^t=(Y_0^t,Y_1^t,\ldots,Y_{n-1}^t)$and perform BM-HDD to obtain $\boldsymbol{X}^t=(X_0^t,X_1^t,\ldots,X_{n-1}^t)$,then convert $\boldsymbol{X}^t$ to binary vector $(x_0^t,x_1^t,\ldots,x_{nm-1}^t)$;

    Compute the soft weight of $\boldsymbol{Y^}H~\oplus~\boldsymbol{X^}t$: $W(\boldsymbol{Y}^H~\oplus~\boldsymbol{X}^t)=\sum_{i=0}^{nm-1}~{|p_i-0.5|(y_i^H~\oplus~x_i^t)}$;

    end for

  • Table 2   Comparison of normalized time complexity of different algorithms in high Eb/No with BPSK modulation (${\rm~FER}=10^{-4}$)
    RS codes BSCA(128) EO-BSCA(128) SSCA(128) EO- SSCA(128)
    RS16(11,5) 1 0.07 1 0.25
    RS16(15,9) 1 0.1 1.188 0.426
    RS32(31,25) 1 0.1 1.625 0.875
  • Table 3   Statistics table of the maximum number of codewords within the search range of a single symbol for RS codes in GF(M) with M-QAM modulation
    RS codes@EbN0 (dB)/FER SSCA(128) $3\sigma$-EO-SSCA(128)
    RS256(255,239)@17.28 dB/FER=0.7540 256 2
    RS256(255,239)@20.28 dB/FER=2.0e$-$6 256 1
    RS512(30,18)@17.22 dB/FER=0.6852 512 9
    RS512(30,18)@21.22 dB/FER=1.0e$-$5 512 4
    RS1024(30,18)@20.22 dB/FER=0.5786 1024 9
    RS1024(30,18)@24.72 dB/FER=1.1e$-$5 1024 4

Contact and support