Figure 1.
Tanner graph
-
Previous Article
AFSRs synthesis with the extended Euclidean rational approximation algorithm
- AMC Home
- This Issue
-
Next Article
Generalized Hamming weights of codes over the $\mathcal{GH}$ curve
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 |
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:
Coding theory,
iterative decoding,
LDPC codes,
majority logic decoding,
threshold decoding,
decoding radius.
Mathematics Subject Classification:
Primary: 58F15, 58F17; Secondary: 53C35.
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-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.
|
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-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.
|
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 |
2021 Impact Factor: 1.015
Tools
Metrics
Other articles
by authors
[Back to Top]