×

zbMATH — the first resource for mathematics

Asymptotic estimation of the fraction of errors correctable by \(q\)-ary LDPC codes. (English. Russian original) Zbl 1237.94145
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
PDF BibTeX XML Cite
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] 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.
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.