Abstract
This paper deals with the irregular binary low-density parity-check (LDPC) codes and two iterative low-complexity decoding algorithms. The first one is the majority error-correcting decoding algorithm, and the second one is iterative erasure-correcting decoding algorithm. The lower bounds on correcting capabilities (the guaranteed corrected error and erasure fraction respectively) of irregular LDPC code under decoding (error and erasure correcting respectively) algorithms with low-complexity were represented. These lower bounds were obtained as a result of analysis of Tanner graph representation of irregular LDPC code. The numerical results, obtained at the end of the paper for proposed lower-bounds achieved similar results for the previously known best lower-bounds for regular LDPC codes and were represented for the first time for the irregular LDPC codes.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
R. G. Gallager, Low-Density Parity-Check Codes (MIT Press, Cambridge, MA, 1963; Mir, Moskow, 1966).
V. V. Zyablov and M. S. Pisker, “Decoding Complexity of Low-Density Codes for Transmission over an Erasure Channel,” Probl. Peredachi Inform. 10 (1), 15–28 (1974).
V. V. Zyablov and M. S. Pinsker, “Estimation of complexity of error correction through low-density Gallagher codes,” Probl. Peredachi Inform. 11 (1), 23–26 (1975).
D. K. Zigangirov and K. Sh. Zigangirov, “Decoding of low-density codes with check matrices composed of permutation matrices, used for transmission over an erasure channel,” Probl. Peredachi Inform. 42 (2), 44–52 (2006).
K. Sh. Zigangirov, A. E. Pusane, D. K. Zigangirov, and D. Dzh. Kostello, “About error-correcting capability of codes with low density checks,” Probl. Peredachi Inform. 44 (3), 50–62 (2008).
V. Zyablov, M. Loncar, R. Johannesson, and P. Rybin, “On the erasure-correcting capabilities of low-complexity decoded LDPC codes with constituent hamming codes,” in Proc. IEEE 11th Int. Workshop on Algebraic and Combinatorial Coding Theory (ACCT08), Pamporovo, Bulgaria, June 16–22, 2008, (IEEE, New York, 2008), pp. 338–347.
M. Lentmaier and K. Zigangirov, “Iterative decoding of generalized low-density parity-check codes,” in Proc. IEEE Int. Symp. on Inform. Theory, Kobe, Japan, pp. 142–143, June 1988 (IEEE, New York, 1988), p. 149.
M. Lentmaier and K. Zigangirov, “On generalized lowdensity parity-check codes based on hamming component codes,” IEEE Commun. Lett. 3, 248–250 (1999).
J. Boutros, O. Pothier, and G. Zemor, “Generalized low density (Tanner) codes,” in Proc. IEEE Int. Conf. on Communications, Vancouver, British Columbia, Canada, June 6–10, 1999, (IEEE, New York, 1999), pp. 441–445.
S. Stiglmayr and V. Zyablov, “Asymptotically good lowdensity codes based on hamming codes,” in Proc. 11th Int. Symp. on Problems of Redundancy in Information and Control Systems, St-Petersburg, July 2–6, 2007 (St-Peterb. Gos. Univ., St-Petersburg, 2007), pp. 98–103.
V. V. Zyablov, R. Iokhannesson, and M. Lonchar, “Just decodable codes with low density checks on the basis of Hamming Codes,” Probl. Peredachi Inform. 45 (2), 25–40 (2009).
A. A. Frolov and V. V. Zyablov, “An asymptotic estimate errors share, corrected q-ary LDPC codes,” Probl. Peredachi Infom. 46 (2), 47–65 (2010).
V. V. Zyablov and P. S. Rybin, “Erasure correction through codes with low density checks,” Probl. Peredachi Inform. 45 (3), 15–32 (2009).
M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi, and D. A. Spielman, “Efficient erasure correcting codes,” IEEE Trans. Inf. Theory 47, 569–584 (2001).
V. V. Zyablov and P. S. Rybin, “Analysis of the connection between the properties of WFP codes and Tanner graph,” Probl. Peredachi Inform. 48 (4), 3–29 (2012).
D. Burshtein and G. Miller, “Asymptotic enumeration methods for analyzing LDPC codes,” IEEE Trans. Inf. Theory 50, 1115–1131 (2004).
R. Tanner, “A recursive approach to low complexity codes,” IEEE Trans. Inf. Theory 27, 533–547 (1981).
A. Frolov, “An upper bound on the minimum distance of LDPC codes over GF(q),” in Proc. IEEE Int. Symp. on Inform. Theory, (ISIT), Hong Kong, June 14–19, 2015 (IEEE, New York, 2015), pp. 2885–2888.
A. Frolov and V. Zyablov, “On the multiple threshold decoding of LDPC codes over GF(q),” in Proc. IEEE Int. Symp. on Inform. Theory, (ISIT), Hong Kong, June 14–19, 2015 (IEEE, New York, 2015), pp. 2673–2677 (2015).
A. S. Ivanov, A. I. Lyakhov, and E. M. Khorov, “Analytical model of a multi-step transmission Nonorderly wireless networks with channel redundancy,” Avtomat. Telemekh., No. 7, 52–68 (2015).
I. S. Kargin, E. M. Khorov, and A. I. Lyakhov, “The mathematical method of estimation of proportion of lost packets for the multi-step route in the presence of correlated noise,” Probl. Peredachi Inform. 51 (3), 105–111 (2015).
A. Kir’yanov, A. Kureev, A. Lyakhov, and E. Khorov, “Analysis of the mechanisms of constructing of logical topology in MANET networks,” Inf. Protsessy 15, 183–197 (2015).
Author information
Authors and Affiliations
Corresponding author
Additional information
Original Russian Text © P.S. Rybin, 2015, published in Informatsionnye Protsessy, 2015, Vol. 15, No. 4, pp. 447–459.
The article was translated by the authors.
Rights and permissions
About this article
Cite this article
Rybin, P.S. Correcting capabilities of binary irregular LDPC code under low-complexity iterative decoding algorithm. J. Commun. Technol. Electron. 61, 1432–1439 (2016). https://doi.org/10.1134/S1064226916120214
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S1064226916120214