×

zbMATH — the first resource for mathematics

Analysis of the relation between properties of LDPC codes and the Tanner graph. (English. Russian original) Zbl 1312.94117
Probl. Inf. Transm. 48, No. 4, 297-323 (2012); translation from Probl. Peredachi Inf. 48, No. 4, 3–29 (2012).
Summary: A new method for estimating the number of errors guaranteed to be corrected by a low-density parity-check code is proposed. The method is obtained by analyzing edges with special properties of an appropriate Tanner graph. In this paper we consider binary LDPC codes with constituent single-parity-check and Hamming codes and an iterative decoding algorithm. Numerical results obtained for the proposed lower bound exceed similar results for the best previously known lower bounds.

MSC:
94B05 Linear codes, general
94B35 Decoding
05C90 Applications of graph theory
Full Text: DOI
References:
[1] Gallager, R.G., Low-Density Parity-Check Codes, Cambridge: MIT Press, 1963. Translated under the title Kody s maloi plotnost’yu proverok na chetnost’, Moscow: Mir, 1966.
[2] Zyablov, V.V. and Pinsker, M.S., Estimation of the Error-Correction Complexity for Gallager Low-Density Codes, Probl. Peredachi Inf., 1975, vol. 11, no. 1, pp. 23–36 [Probl. Inf. Trans. (Engl. Transl.), 1975, vol. 11, no. 1, pp. 18–28]. · Zbl 0358.94017
[3] Zigangirov, K.Sh., Pusane, A.E., Zigangirov, D.K., and Costello, D.J., Jr., On the Error-Correcting Capability of LDPC Codes, Probl. Peredachi Inf., 2008, vol. 44, no. 3, pp. 50–62 [Probl. Inf. Trans. (Engl. Transl.), 2008, vol. 44, no. 3, pp. 214–225]. · Zbl 1173.94010
[4] Lentmaier, M. and Zigangirov, K., Iterative Decoding of Generalized Low-Density Parity-Check Codes, in Proc. 1998 IEEE Int. Sympos. on Information Theory (ISIT’2008), Cambridge, USA, Piscataway, NJ, 1998. · Zbl 1010.94017
[5] Lentmaier, M. and Zigangirov, K., On Generalized Low-Density Parity-Check Codes Based on Hamming Component Codes, IEEE Commun. Lett., 1999, vol. 3, no. 8, pp. 248–250. · doi:10.1109/4234.781010
[6] Boutros, J., Pothier, O., and Zémor, G., Generalized Low Density (Tanner) Codes, in Proc. IEEE Int. Conf. on Communications (ICC’99), Vancouver, Canada, 1999, vol. 1, pp. 441–445.
[7] Stiglmayr, S. and Zyablov, V.V., Asymptotically Good Low-Density Codes Based on Hamming Codes, in Proc. 11th Int. Sympos. on Problems of Redundancy in Information and Control Systems, St. Petersburg, Russia, 2007, pp. 98–103. Available at http://www.k36.org/redundancy2007/proceedings.php .
[8] Zyablov, V.V., Johannesson, R., and Lončar, M., Low-Complexity Error Correction of Hamming-Code-Based LDPC Codes, Probl. Peredachi Inf., 2009, vol. 45, no. 2, pp. 25–40 [Probl. Inf. Trans. (Engl. Transl.), 2009, vol. 45, no. 2, pp. 95–109].
[9] Frolov, A.A. and Zyablov, V.V., Asymptotic Estimation of the Fraction of Errors Correctable by q-ary LDPC Codes, Probl. Peredachi Inf., 2010, vol. 46, no. 2, pp. 47–65 [Probl. Inf. Trans. (Engl. Transl.), 2010, vol. 46, no. 2, pp. 142–159]. · Zbl 1237.94145
[10] Zyablov, V.V. and Rybin, P.S., Erasure Correction by Low-Density Codes, Probl. Peredachi Inf., 2009, vol. 45, no. 3, pp. 15–32 [Probl. Inf. Trans. (Engl. Transl.), 2009, vol. 45, no. 3, pp. 204–220]. · Zbl 1178.94254
[11] Barg, A. and Mazumdar, A., On the Number of Errors Correctable with Codes on Graphs, IEEE Trans. Inform. Theory, 2011, vol. 57, no. 2, pp. 910–919. · Zbl 1366.94737 · doi:10.1109/TIT.2010.2094812
[12] Tanner, R.M., A Recursive Approach to Low Complexity Codes, IEEE Trans. Inform. Theory, 1981, vol. 27, no. 5, pp. 533–547. · Zbl 0474.94029 · doi:10.1109/TIT.1981.1056404
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.