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.
Google Scholar
|
| [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. 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. |
| [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. |
| [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. 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. |
| [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. 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. |
| [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. |
| [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. Google Scholar |
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.
Google Scholar
|
| [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. 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. |
| [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. |
| [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. 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. |
| [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. 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. |
| [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. |
| [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. Google Scholar |
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] |
W. Cary Huffman. On the theory of $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2013, 7 (3) : 349-378. doi: 10.3934/amc.2013.7.349 |
| [2] |
Arseny Egorov. Morse coding for a Fuchsian group of finite covolume. Journal of Modern Dynamics, 2009, 3 (4) : 637-646. doi: 10.3934/jmd.2009.3.637 |
| [3] |
Charles Amorim, Miguel Loayza, Marko A. Rojas-Medar. The nonstationary flows of micropolar fluids with thermal convection: An iterative approach. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2509-2535. doi: 10.3934/dcdsb.2020193 |
| [4] |
Guillaume Bal, Wenjia Jing. Homogenization and corrector theory for linear transport in random media. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1311-1343. doi: 10.3934/dcds.2010.28.1311 |
| [5] |
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, 2021, 14 (5) : 1717-1746. doi: 10.3934/dcdss.2020451 |
| [6] |
Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 119-147. doi: 10.3934/amc.2011.5.119 |
| [7] |
Jérôme Ducoat, Frédérique Oggier. On skew polynomial codes and lattices from quotients of cyclic division algebras. Advances in Mathematics of Communications, 2016, 10 (1) : 79-94. doi: 10.3934/amc.2016.10.79 |
| [8] |
John Leventides, Costas Poulios, Georgios Alkis Tsiatsios, Maria Livada, Stavros Tsipras, Konstantinos Lefcaditis, Panagiota Sargenti, Aleka Sargenti. Systems theory and analysis of the implementation of non pharmaceutical policies for the mitigation of the COVID-19 pandemic. Journal of Dynamics & Games, 2021 doi: 10.3934/jdg.2021004 |
| [9] |
Hakan Özadam, Ferruh Özbudak. A note on negacyclic and cyclic codes of length $p^s$ over a finite field of characteristic $p$. Advances in Mathematics of Communications, 2009, 3 (3) : 265-271. doi: 10.3934/amc.2009.3.265 |
| [10] |
Raj Kumar, Maheshanand Bhaintwal. Duadic codes over $ \mathbb{Z}_4+u\mathbb{Z}_4 $. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2020135 |
| [11] |
Jong Yoon Hyun, Yoonjin Lee, Yansheng Wu. Connection of $ p $-ary $ t $-weight linear codes to Ramanujan Cayley graphs with $ t+1 $ eigenvalues. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2020133 |
2019 Impact Factor: 0.734
Tools
Metrics
Other articles
by authors
[Back to Top]