×

zbMATH — the first resource for mathematics

Bounds on the minimum code distance for nonbinary codes based on bipartite graphs. (English. Russian original) Zbl 1302.94071
Probl. Inf. Transm. 47, No. 4, 327-341 (2011); translation from Probl. Peredachi Inf. 47, No. 4, 27-42 (2011).
Summary: The minimum distance of codes on bipartite graphs (BG codes) over \(\mathrm{GF}(q)\) is studied. A new upper bound on the minimum distance of BG codes is derived. The bound is shown to lie below the Gilbert-Varshamov bound when \(q\geq 32\). Since the codes based on bipartite expander graphs (BEG codes) are a special case of BG codes and the resulting bound is valid for any BG code, it is also valid for BEG codes. Thus, nonbinary \((q\geq 32)\) BG codes are worse than the best known linear codes. This is the key result of the work. We also obtain a lower bound on the minimum distance of BG codes with a Reed-Solomon constituent code and a lower bound on the minimum distance of low-density parity-check (LDPC) codes with a Reed-Solomon constituent code. The bound for LDPC codes is very close to the Gilbert-Varshamov bound and lies above the upper bound for BG codes.

MSC:
94B60 Other types of codes
94B65 Bounds on codes
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] 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
[2] Sipser, M. and Spielman, D.A., Expander Codes, IEEE Trans. Inform. Theory, 1996, vol. 42, no. 6, pp. 1710–1722. · Zbl 0943.94543 · doi:10.1109/18.556667
[3] Lubotzky, A., Phillips, R., and Sarnak, P., Ramanujan Graphs, Combinatorica, 1988, vol. 8, no. 3, pp. 261–277. · Zbl 0661.05035 · doi:10.1007/BF02126799
[4] Margulis, G.A., Explicit Constructions of Concentrators, Probl. Peredachi Inf., 1973, vol. 9, no. 4, pp. 71–80 [Probl. Inf. Trans. (Engl. Transl.), 1973, vol. 9, no. 4, pp. 325–332]. · Zbl 0312.22011
[5] Zémor, G., On Expander Codes, IEEE Trans. Inform. Theory, 2001, vol. 47, no. 2, pp. 835–837. · Zbl 1021.94025 · doi:10.1109/18.910593
[6] Skachek, V. and Roth, R., Generalized Minimum Distance Iterative Decoding of Expander Codes, in Proc. 2003 IEEE Information Theory Workshop, Paris, France, 2003, pp. 245–248.
[7] Barg, A. and Zémor, G., Distance Properties of Expander Codes, IEEE Trans. Inform. Theory, 2006, vol. 52, no. 1, pp. 78–90. · Zbl 1282.94107 · doi:10.1109/TIT.2005.860415
[8] Skachek, V., Minimum Distance Bounds for Expander Codes, in Information Theory and Applications Workshop (ITA’2008), San Diego, USA, 2008, pp. 366–370.
[9] Boutros, J., Pothier, O., and Zémor, G., Generalized Low Density (Tanner) Codes, in Proc. IEEE Int. Conf. on Communications (ICC), Vancouver, Canada, 1999, vol. 1, pp. 441–445.
[10] 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
[11] Ben-Haim, Y. and Litsyn, S., Upper Bounds on the Rate of LDPC Codes as a Function of Minimum Distance, IEEE Trans. Inform. Theory, 2006, vol. 52, no. 5, pp. 2092–2100. · Zbl 1285.94131 · doi:10.1109/TIT.2006.872972
[12] Roth, R. and Skachek, V., Improved Nearly-MDS Expander Codes, IEEE Trans. Inform. Theory, 2006, vol. 52, no. 8, pp. 3650–3661. · Zbl 1309.94082 · doi:10.1109/TIT.2006.878232
[13] Peterson, W.W. and Weldon, E.J., Jr., Error-Correcting Codes, Cambridge: MIT Press, 1972. Translated under the title Kody, ispravlyayushchie oshibki, Moscow: Mir, 1976. · Zbl 0251.94007
[14] Bassalygo, L.A., New Upper Bounds for Error Correcting Codes, Probl. Peredachi Inf., 1965, vol. 1, no. 4, pp. 41–44 [Probl. Inf. Trans. (Engl. Transl.), 1965, vol. 1, no. 4, pp. 32–35]. · Zbl 0259.94022
[15] McEliece, R.J., Rodemich, E.R., Rumsey, H., Jr., and Welch, L.R., New Upper Bounds on the Rate of a Code via the Delsarte-MacWilliams Inequalities, IEEE Trans. Inform. Theory, 1977, vol. 23, no. 2, pp. 157–166. · Zbl 0361.94016 · doi:10.1109/TIT.1977.1055688
[16] 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.
[17] Barg, A., Mazumdar, A., and Zémor, G., Weight Distribution and Decoding of Codes on Hypergraphs, Adv. Math. Commun., 2008, vol. 2, no. 4, pp. 433–450. · Zbl 1154.94012 · doi:10.3934/amc.2008.2.433
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.