\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

On the multiple threshold decoding of LDPC codes over GF(q)

A part of the results of this paper were presented at the 2015 IEEE International Symposium on Information Theory, June 2015, Hong Kong [7].

The research was carried out at the IITP RAS and supported by the Russian Science Foundation (project no. 14-50-00150)

Abstract Full Text(HTML) Figure(5) / Table(2) Related Papers Cited by
  • We consider decoding of LDPC codes over GF(q) with a harddecision low-complexity majority algorithm, which is a generalization of the bit-flipping algorithm for binary LDPC codes. A modification of this algorithm with multiple thresholds is suggested. A lower estimate on the decoding radius realized by the new algorithm is derived. The estimate is shown to be better than the estimate for a single threshold majority decoder. At the same time, introducing multiple thresholds does not affect the order of decoding complexity.

    Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  Tanner graph

    Figure 2.  Single threshold decoding. The lower estimate $L(W)$ is valid only up to $W^*$, that is why the line is dashed after the point. Points A, C and B have coordinates ($W^*/2$; $W^* \ell/2$), ($W^{(S)}$; $W^{(S)} \ell$) and ($W^*$; $W^* \ell / 2$) accordingly

    Figure 3.  A subgraph of Tanner graph

    Figure 4.  Multiple thresholds. The lower estimate $L(W)$ is valid only up to $W^*$, that is why the line is dashed after the point

    Figure 5.  The dependency of $\alpha^{(S)}$ and $\alpha^{(M)}$ on $\ell$

    Table 1.  Results for $q=16$

    ($\ell$, $n_0$); $R$ $\delta$ $\omega^*$ $\rho^{(S)}$ $\rho^{(M)}$ $\rho^{(M)}/\rho^{(S)}$
    (45, 52); 0.135 0.6130 0.0103 0.0053 0.0065 1.226
    (43, 58); 0.26 0.4855 0.0095 0.0049 0.0060 1.224
    (40, 64); 0.375 0.3797 0.0085 0.0044 0.0054 1.227
    (31, 62); 0.5 0.2808 0.0072 0.0037 0.0046 1.243
    (24, 64); 0.625 0.1935 0.0053 0.0028 0.0034 1.214
    (24, 96); 0.75 0.1168 0.0033 0.0017 0.0021 1.235
    (26,208);0.875 0.0507 0.0015 0.0008 0.0010 1.250
     | Show Table
    DownLoad: CSV

    Table 2.  Results for $q=64$

    ($\ell$, $n_0$); $R$ $\delta$ $\omega^*$ $\rho^{(S)}$ $\rho^{(M)}$ $\rho^{(M)}/\rho^{(S)}$
    (21, 24); 0.125 0.7355 0.0156 0.0082 0.0099 1.207
    (24, 32); 0.25 0.5863 0.0131 0.0068 0.0083 1.221
    (20, 32); 0.375 0.4585 0.0104 0.0054 0.0066 1.222
    (22, 44); 0.5 0.3445 0.0081 0.0042 0.0052 1.238
    (27, 72); 0.625 0.2415 0.0059 0.0031 0.0038 1.226
    (24, 96); 0.75 0.1485 0.0037 0.0019 0.0024 1.263
    (26,208); 0.875 0.0661 0.0017 0.0009 0.0011 1.222
     | Show Table
    DownLoad: CSV
  • [1] N. Alon, Eigenvalues and expanders, Combinarorica, 6 (1986), 83-96.  doi: 10.1007/BF02579166.
    [2] A. Barg and A. Mazumdar, On the number of errors correctable with codes on graphs, IEEE Trans. Inf. Theory, 57 (2011), 910-919.  doi: 10.1109/TIT.2010.2094812.
    [3] J. Boutros, O. Pothier and G. Zémor, Generalized low density (Tanner) codes, in Proc. IEEE Int. Conf. Comm. , Vancouver, 1999,441-445. doi: 10.1109/ICC.1999.767979.
    [4] D. Burshtein, On the error correction of regular LDPC codes using the flipping algorithm, IEEE Trans. Inf. Theory, 54 (2008), 517-530.  doi: 10.1109/TIT.2007.913261.
    [5] M. C. Davey and D. MacKay, Low-density parity check codes over GF(q), IEEE Commun. Lett., 2 (1998), 165-167.  doi: 10.1109/ITW.1998.706440.
    [6] A. Frolov and V. Zyablov, Asymptotic estimation of the fraction of errors correctable by q-ary LDPC codes, Probl. Inf. Transm., 46 (2010), 142-159.  doi: 10.1134/S0032946010020043.
    [7] A. Frolov and V. Zyablov, On the multiple threshold decoding of LDPC codes over GF(q), in Proc. 2015 IEEE Int. Symp. Inf. Theory, Hong Kong, 2015,2673-2677. doi: 10.1109/ISIT.2015.7282941.
    [8] R. G. GallagerLow-Density Parity-Check Codes, MIT Press, Cambridge, 1963.  doi: 10.1109/TIT.1962.1057683.
    [9] F. Garcia-FerreroD. Declercq and J. Valls, Non-binary LDPC decoder based on symbol flipping with multiple votes, IEEE Commun. Lett., 18 (2014), 749-752. 
    [10] N. Kahale, On the second eigenvalue and linear expansion of regular graphs, in Proc. IEEE Symp. Found. Comp. Sci. , 1992,296-303. doi: 10.1109/SFCS.1992.267762.
    [11] S. Kovalev, Decoding of low-density codes, Probl. Inf. Transm., 27 (1991), 51-56. 
    [12] M. Lentmaier and K. Zigangirov, On generalized low-density parity-check codes based on Hamming component codes, IEEE Commun. Lett., 3 (1999), 248-250.  doi: 10.1109/4234.781010.
    [13] A. LubotzkyR. Phillips and P. Sarnak, Ramanujan graphs, Combinarorica., 8 (1988), 261-277.  doi: 10.1007/BF02126799.
    [14] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, NorthHolland, Amsterdam, 1991.
    [15] G. A. Margulis, Explicit constructions of concentrators, Probl. Inform. Transm., 9 (1975), 325-332. 
    [16] J. MasseyThreshold Decoding, MIT Press, Cambridge, 1963. 
    [17] P. Rybin, On the error-correcting capabilities of low-complexity decoded irregular LDPC codes, in Proc. 2014 IEEE Int. Symp. Inf. Theory, Honolulu, 2014,3165-3169. doi: 10.1109/ISIT.2014.6875418.
    [18] M. Sipser and D. A. Spielman, Expander codes, IEEE Trans. Inf. Theory, 42 (1996), 1710-1722.  doi: 10.1109/18.556667.
    [19] H. Song and J. R. Cruz, Reduced-complexity decoding of Q-ary LDPC codes for magnetic recording, IEEE Transact. Magnetics, 39 (2003), 1081-1087. 
    [20] R. Tanner, A recursive approach to low complexity codes, IEEE Trans. Inf. Theory, 27 (1981), 533-547.  doi: 10.1109/TIT.1981.1056404.
    [21] J. Webber, T. Nishimura, T. Ohgane and Y. Ogawa, A study on adaptive thresholds for reduced complexity bit-flip decoding, in Proc. Int. Conf. Adv. Commun. Techn. , 2012,497-501.
    [22] J. Webber, T. Nishimura, T. Ohgane and Y. Ogawa, Performance investigation of reduced complexity bit-flipping using variable thresholds and noise perturbation, in Proc. Int. Conf. Adv. Commun. Techn. , 2014,206-2013. doi: 10.1109/ICACT.2014.6779175.
    [23] K. ZigangirovA. PusaneD. Zigangirov and D. Costello, On the error-correcting capability of LDPC codes, Probl. Inf. Transm., 44 (2008), 214-225.  doi: 10.1134/S0032946008030046.
    [24] V. ZyablovR. Johannesson and M. Lonċar, Low-complexity error correction of Hammingcode-based LDPC codes, Probl. Inf. Trans., 45 (2009), 95-109.  doi: 10.1134/S0032946009020021.
    [25] V. Zyablov and M. Pinsker, Estimation of the error-correction complexity for Gallager lowdensity codes, Probl. Inf. Transm., 11 (1975), 18-28. 
  • 加载中

Figures(5)

Tables(2)

SHARE

Article Metrics

HTML views(156) PDF downloads(300) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return