February  2017, 11(1): 123-137. doi: 10.3934/amc.2017007

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

1. 

Skolkovo Institute of Science and Technology (Skoltech), and Institute for Information Transmission Problems, Russian Academy of Sciences, Moscow, Russia

2. 

Institute for Information Transmission Problems, Russian Academy of Sciences, Moscow, Russia

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

Received  July 2015 Revised  March 2016 Published  February 2017

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

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.

Citation: Alexey Frolov, Victor Zyablov. On the multiple threshold decoding of LDPC codes over GF(q). Advances in Mathematics of Communications, 2017, 11 (1) : 123-137. doi: 10.3934/amc.2017007
References:
[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. Gallager, Low-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. Massey, Threshold 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. 

show all references

References:
[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. Gallager, Low-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. Massey, Threshold 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. 

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
($\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
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
($\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
[1]

Kwankyu Lee. Decoding of differential AG codes. Advances in Mathematics of Communications, 2016, 10 (2) : 307-319. doi: 10.3934/amc.2016007

[2]

Hannes Bartz, Antonia Wachter-Zeh. Efficient decoding of interleaved subspace and Gabidulin codes beyond their unique decoding radius using Gröbner bases. Advances in Mathematics of Communications, 2018, 12 (4) : 773-804. doi: 10.3934/amc.2018046

[3]

Johan Rosenkilde. Power decoding Reed-Solomon codes up to the Johnson radius. Advances in Mathematics of Communications, 2018, 12 (1) : 81-106. doi: 10.3934/amc.2018005

[4]

Elisa Gorla, Felice Manganiello, Joachim Rosenthal. An algebraic approach for decoding spread codes. Advances in Mathematics of Communications, 2012, 6 (4) : 443-466. doi: 10.3934/amc.2012.6.443

[5]

Washiela Fish, Jennifer D. Key, Eric Mwambene. Partial permutation decoding for simplex codes. Advances in Mathematics of Communications, 2012, 6 (4) : 505-516. doi: 10.3934/amc.2012.6.505

[6]

Alexander Barg, Arya Mazumdar, Gilles Zémor. Weight distribution and decoding of codes on hypergraphs. Advances in Mathematics of Communications, 2008, 2 (4) : 433-450. doi: 10.3934/amc.2008.2.433

[7]

Terasan Niyomsataya, Ali Miri, Monica Nevins. Decoding affine reflection group codes with trellises. Advances in Mathematics of Communications, 2012, 6 (4) : 385-400. doi: 10.3934/amc.2012.6.385

[8]

Heide Gluesing-Luerssen, Uwe Helmke, José Ignacio Iglesias Curto. Algebraic decoding for doubly cyclic convolutional codes. Advances in Mathematics of Communications, 2010, 4 (1) : 83-99. doi: 10.3934/amc.2010.4.83

[9]

Violetta Weger, Karan Khathuria, Anna-Lena Horlemann, Massimo Battaglioni, Paolo Santini, Edoardo Persichetti. On the hardness of the Lee syndrome decoding problem. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022029

[10]

Joan-Josep Climent, Diego Napp, Raquel Pinto, Rita Simões. Decoding of $2$D convolutional codes over an erasure channel. Advances in Mathematics of Communications, 2016, 10 (1) : 179-193. doi: 10.3934/amc.2016.10.179

[11]

Irene I. Bouw, Sabine Kampf. Syndrome decoding for Hermite codes with a Sugiyama-type algorithm. Advances in Mathematics of Communications, 2012, 6 (4) : 419-442. doi: 10.3934/amc.2012.6.419

[12]

Anas Chaaban, Vladimir Sidorenko, Christian Senger. On multi-trial Forney-Kovalev decoding of concatenated codes. Advances in Mathematics of Communications, 2014, 8 (1) : 1-20. doi: 10.3934/amc.2014.8.1

[13]

Vladimir Sidorenko, Christian Senger, Martin Bossert, Victor Zyablov. Single-trial decoding of concatenated codes using fixed or adaptive erasing. Advances in Mathematics of Communications, 2010, 4 (1) : 49-60. doi: 10.3934/amc.2010.4.49

[14]

Peter Beelen, Kristian Brander. Efficient list decoding of a class of algebraic-geometry codes. Advances in Mathematics of Communications, 2010, 4 (4) : 485-518. doi: 10.3934/amc.2010.4.485

[15]

Julia Lieb, Raquel Pinto. A decoding algorithm for 2D convolutional codes over the erasure channel. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021031

[16]

Robert F. Bailey, John N. Bray. Decoding the Mathieu group M12. Advances in Mathematics of Communications, 2007, 1 (4) : 477-487. doi: 10.3934/amc.2007.1.477

[17]

Anna-Lena Horlemann-Trautmann, Violetta Weger. Information set decoding in the Lee metric with applications to cryptography. Advances in Mathematics of Communications, 2021, 15 (4) : 677-699. doi: 10.3934/amc.2020089

[18]

Fernando Hernando, Tom Høholdt, Diego Ruano. List decoding of matrix-product codes from nested codes: An application to quasi-cyclic codes. Advances in Mathematics of Communications, 2012, 6 (3) : 259-272. doi: 10.3934/amc.2012.6.259

[19]

Ahmed S. Mansour, Holger Boche, Rafael F. Schaefer. The secrecy capacity of the arbitrarily varying wiretap channel under list decoding. Advances in Mathematics of Communications, 2019, 13 (1) : 11-39. doi: 10.3934/amc.2019002

[20]

Henry Cohn, Nadia Heninger. Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding. Advances in Mathematics of Communications, 2015, 9 (3) : 311-339. doi: 10.3934/amc.2015.9.311

2020 Impact Factor: 0.935

Metrics

  • PDF downloads (259)
  • HTML views (72)
  • Cited by (0)

Other articles
by authors

[Back to Top]