zbMATH — the first resource for mathematics

On the minimum distance of low-density parity-check codes with parity-check matrices constructed from permutation matrices. (English. Russian original) Zbl 1078.94038
Probl. Inf. Transm. 41, No. 1, 33-44 (2005); translation from Probl. Peredachi Inf. 41, No. 1, 39-52 (2005).
Summary: An ensemble of codes defined by parity-check matrices composed of \(M \times M\) permutation matrices is considered. This ensemble is a subensemble of the ensemble of low-density parity-check (LDPC) codes considered by R. G. Gallager [Low-density parity-check codes, Cambridge: MIT Press (1963)]. We prove that, as \(M\to \infty \), the minimum distance of almost all codes in the ensemble grows linearly with \(M\). We also show that in several cases the asymptotic minimum-distance-to-block-length ratio for almost all codes in the ensemble satisfies Gallager’s bound.

94B60 Other types of codes
94A45 Prefix, length-variable, comma-free codes
Full Text: DOI
[1] Gallager, R.G., Low-Density Parity-Check Codes, Cambridge: MIT Press, 1963. · Zbl 0156.40701
[2] MacKay, D.J.C. and Davey, M.C., Evaluation of Gallager Codes for Short Block Length and High Rate Applications, Codes, Systems and Graphical Models, Marcus, B. and Rosenthal, J., Eds., IMA Vols. Math. Appl., vol. 123, New York: Springer, 2001, pp. 113-130. · Zbl 0995.94035
[3] Tanner, R.M., Sridhara, D., Sridharan, A., Fuja, T.E., and Costello, D.J., Jr., LDPC Block and Convolutional Codes Based on Circulant Matrices, IEEE Trans. Inform. Theory, 2004, vol. 50, no.12, pp. 2966-2984. · Zbl 1287.94122 · doi:10.1109/TIT.2004.838370
[4] Fossorier, M.P.C., Quasi-Cyclic Low Density Parity Check Codes, in Proc. 2003 IEEE Int. Symp. on Information Theory, Yokahama, Japan, 2003, p. 150.
[5] Johannesson, R. and Zigangirov, K.Sh., Fundamentals of Convolutional Coding, Piscataway: IEEE Press, 1999. · Zbl 0964.94024
[6] Sridharan, A., Truhachev, D.V., Lentmaier, M., Costello, D.J., Jr., and Zigangirov, K.Sh., On the Free Distance of LDPC Convolutional Codes, in Proc. 2004 IEEE Int. Symp. on Information Theory, Chicago, USA, 2004. · Zbl 1320.94096
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.