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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[8] R. G. Gallager, Low-Density Parity-Check Codes, MIT Press, Cambridge, 1963.  doi: 10.1109/TIT.1962.1057683.  Google Scholar
[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.   Google Scholar

[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.  Google Scholar

[11]

S. Kovalev, Decoding of low-density codes, Probl. Inf. Transm., 27 (1991), 51-56.   Google Scholar

[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.  Google Scholar

[13]

A. LubotzkyR. Phillips and P. Sarnak, Ramanujan graphs, Combinarorica., 8 (1988), 261-277.  doi: 10.1007/BF02126799.  Google Scholar

[14]

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, NorthHolland, Amsterdam, 1991. Google Scholar

[15]

G. A. Margulis, Explicit constructions of concentrators, Probl. Inform. Transm., 9 (1975), 325-332.   Google Scholar

[16] J. Massey, Threshold Decoding, MIT Press, Cambridge, 1963.   Google Scholar
[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.  Google Scholar

[18]

M. Sipser and D. A. Spielman, Expander codes, IEEE Trans. Inf. Theory, 42 (1996), 1710-1722.  doi: 10.1109/18.556667.  Google Scholar

[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.   Google Scholar

[20]

R. Tanner, A recursive approach to low complexity codes, IEEE Trans. Inf. Theory, 27 (1981), 533-547.  doi: 10.1109/TIT.1981.1056404.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[25]

V. Zyablov and M. Pinsker, Estimation of the error-correction complexity for Gallager lowdensity codes, Probl. Inf. Transm., 11 (1975), 18-28.   Google Scholar

show all references

References:
[1]

N. Alon, Eigenvalues and expanders, Combinarorica, 6 (1986), 83-96.  doi: 10.1007/BF02579166.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[8] R. G. Gallager, Low-Density Parity-Check Codes, MIT Press, Cambridge, 1963.  doi: 10.1109/TIT.1962.1057683.  Google Scholar
[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.   Google Scholar

[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.  Google Scholar

[11]

S. Kovalev, Decoding of low-density codes, Probl. Inf. Transm., 27 (1991), 51-56.   Google Scholar

[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.  Google Scholar

[13]

A. LubotzkyR. Phillips and P. Sarnak, Ramanujan graphs, Combinarorica., 8 (1988), 261-277.  doi: 10.1007/BF02126799.  Google Scholar

[14]

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, NorthHolland, Amsterdam, 1991. Google Scholar

[15]

G. A. Margulis, Explicit constructions of concentrators, Probl. Inform. Transm., 9 (1975), 325-332.   Google Scholar

[16] J. Massey, Threshold Decoding, MIT Press, Cambridge, 1963.   Google Scholar
[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.  Google Scholar

[18]

M. Sipser and D. A. Spielman, Expander codes, IEEE Trans. Inf. Theory, 42 (1996), 1710-1722.  doi: 10.1109/18.556667.  Google Scholar

[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.   Google Scholar

[20]

R. Tanner, A recursive approach to low complexity codes, IEEE Trans. Inf. Theory, 27 (1981), 533-547.  doi: 10.1109/TIT.1981.1056404.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[25]

V. Zyablov and M. Pinsker, Estimation of the error-correction complexity for Gallager lowdensity codes, Probl. Inf. Transm., 11 (1975), 18-28.   Google Scholar

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]

Agnaldo José Ferrari, Tatiana Miguel Rodrigues de Souza. Rotated $ A_n $-lattice codes of full diversity. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020118

[2]

Patrick W. Dondl, Martin Jesenko. Threshold phenomenon for homogenized fronts in random elastic media. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 353-372. doi: 10.3934/dcdss.2020329

[3]

Felix Finster, Jürg Fröhlich, Marco Oppio, Claudio F. Paganini. Causal fermion systems and the ETH approach to quantum theory. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020451

[4]

Weiwei Liu, Jinliang Wang, Yuming Chen. Threshold dynamics of a delayed nonlocal reaction-diffusion cholera model. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020316

[5]

Cuicui Li, Lin Zhou, Zhidong Teng, Buyu Wen. The threshold dynamics of a discrete-time echinococcosis transmission model. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020339

[6]

Pierre-Etienne Druet. A theory of generalised solutions for ideal gas mixtures with Maxwell-Stefan diffusion. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020458

[7]

Juan Pablo Pinasco, Mauro Rodriguez Cartabia, Nicolas Saintier. Evolutionary game theory in mixed strategies: From microscopic interactions to kinetic equations. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020051

[8]

Sergey Rashkovskiy. Hamilton-Jacobi theory for Hamiltonian and non-Hamiltonian systems. Journal of Geometric Mechanics, 2020, 12 (4) : 563-583. doi: 10.3934/jgm.2020024

[9]

Claudianor O. Alves, Rodrigo C. M. Nemer, Sergio H. Monari Soares. The use of the Morse theory to estimate the number of nontrivial solutions of a nonlinear Schrödinger equation with a magnetic field. Communications on Pure & Applied Analysis, 2021, 20 (1) : 449-465. doi: 10.3934/cpaa.2020276

2019 Impact Factor: 0.734

Metrics

  • PDF downloads (156)
  • HTML views (65)
  • Cited by (0)

Other articles
by authors

[Back to Top]