zbMATH — the first resource for mathematics

Erasure correction by low-density codes. (English. Russian original) Zbl 1178.94254
Probl. Inf. Transm. 45, No. 3, 204-220 (2009); translation from Probl. Peredachi Inf. 45, No. 3, 15-32 (2009).
Summary: We generalize the method for computing the number of errors correctable by a low-density parity-check (LDPC) code in a binary symmetric channel, which was proposed by V. V. Zyablov and M. S. Pinsker [Probl. Peredaci Inform. 11, No. 1, 23–26 (1975; Zbl 0358.94017)]. This method is for the first time applied for computing the fraction of guaranteed correctable erasures for an LDPC code with a given constituent code used in an erasure channel. Unlike previously known combinatorial methods for computing the fraction of correctable erasures, this method is based on the theory of generating functions, which allows us to obtain more precise results and unify the computation method for various constituent codes of a regular LDPC code. We also show that there exist an LDPC code with a given constituent code which, when decoded with a low-complexity iterative algorithm, is capable of correcting any erasure pattern with a number of erasures that grows linearly with the code length. The number of decoding iterations, required to correct the erasures, is a logarithmic function of the code length. We make comparative analysis of various numerical results obtained by various computation methods for certain parameters of an LDPC code with a constituent single-parity-check or Hamming code.

94B60 Other types of codes
94B20 Burst-correcting codes
Full Text: DOI
[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. and Pinsker, M.S., Decoding Complexity of Low-Density Codes for Transmission in a Channel with Erasures, Probl. Peredachi Inf., 1974, vol. 10, no. 1, pp. 15–28 [Probl. Inf. Trans. (Engl. Transl.), 1974, vol. 10, no. 1, pp. 10–21]. · Zbl 0326.94011
[4] Zigangirov, D.K. and Zigangirov, K.Sh., Decoding of Low-Density Codes with Parity-Check Matrices Composed of Permutation Matrices in an Erasure Channel Probl. Peredachi Inf., 2006, vol. 42, no. 2, pp. 44–52 [Probl. Inf. Trans. (Engl. Transl.), 2006, vol. 42, no. 2, pp. 106–113]. · Zbl 1237.94142
[5] Luby, M.G., Mitzenmacher, M., Shokrollahi, M.A., and Spielman, D.A., Efficient Erasure Correcting Codes, IEEE Trans. Inform. Theory, 2001, vol. 47, no. 2, pp. 569–584. · Zbl 1019.94032 · doi:10.1109/18.910575
[6] 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.
[7] Zyablov, V.V and Rybin, P.S., Erasure Correction by Low-Density Gallager Codes, in Proc. 31st Conference of Young Scientists and Engineers on Information Technologies and Systems (ITaS’08), Gelendzhik, Russia, 2008, Moscow: Inst. Probl. Peredachi Inf. Ross. Akad. Nauk, 2008, pp. 167–172.
[8] 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
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.