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

Alexey Frolov; Victor Zyablov

doi:10.3934/amc.2017007

Article Contents

2017, Volume 11, Issue 1: 123-137. Doi: 10.3934/amc.2017007

This issue Previous Article Generalized Hamming weights of codes over the $\mathcal{GH}$ curve Next Article AFSRs synthesis with the extended Euclidean rational approximation algorithm

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

Alexey Frolov^1,2, and
Victor Zyablov^2,

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: May 2017

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

Abstract

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.

Keywords:

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

Citation:

Full Text(HTML)

Figure 1. Tanner graph

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

Figure 3. A subgraph of Tanner graph

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Related Papers

Cited by

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-Ferrero, D. 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. Lubotzky, R. 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. Zigangirov, A. Pusane, D. 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. Zyablov, R. 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.