Asymptotic estimation of the fraction of errors correctable by \(q\)-ary LDPC codes. (English. Russian original) Zbl 1237.94145

Frolov, A. A.; Zyablov, V. V.

Probl. Inf. Transm. 46, No. 2, 142-159 (2010); translation from Probl. Peredachi Inf. 46, No. 2, 47-65 (2010).

Summary: We consider an ensemble of random \(q\)-ary LDPC codes. As constituent codes, we use \(q\)-ary single-parity-check codes with \(d = 2\) and Reed-Solomon codes with \(d = 3\). We propose a hard-decision iterative decoding algorithm with the number of iterations of the order of the logarithm of the code length. We show that under this decoding algorithm there are codes in the ensemble with the number of correctable errors linearly growing with the code length. We weaken a condition on the vertex expansion of the Tanner graph corresponding to the code.

MSC:

94B60	Other types of codes
94B35	Decoding
94B70	Error probability in coding theory

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]	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
[3]	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].
[4]	Zyablov, V., Johannesson, R., Lončar, M., and Rybin, P., On the Erasure-Correcting Capabilities of Low-Complexity Decoded LDPC Codes with Constituent Hamming Codes, in Proc. 11th Int. Workshop on Algebraic and Combinatorial Coding Theory (ACCT’2008), Pamporovo, Bulgaria, 2008, pp. 338–347.
[5]	Miladinović, N. and Fossorier, M., Generalized LDPC Codes with Reed-Solomon and BCH Codes as Component Codes for Binary Channels, in Proc. IEEE Conf. on Global Telecommunications (GLOBECOM 2005), St. Louis, USA, 2005, pp. 591–596.
[6]	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
[7]	Bassalygo, L.A., Formalization of the Problem of Complexity of Code Specification, Probl. Peredachi Inf., 1976, vol. 12, no. 4, pp. 105–106 [Probl. Inf. Trans. (Engl. Transl.), 1976, vol. 12, no. 4, pp. 322–324]. · Zbl 0355.94013
[8]	Zyablov, V., Potapov, V., and Groshev, F., Low-Complexity Error Correction in LDPC Codes with Constituent RS Codes, in Proc. 11th Int. Workshop on Algebraic and Combinatorial Coding Theory (ACCT’2008), Pamporovo, Bulgaria, 2008, pp. 348–353.