Abstract
We propose geometrical methods for constructing square 01-matrices with the same number n of units in every row and column, and such that any two rows of the matrix contain at most one unit in common. These matrices are equivalent to n-regular bipartite graphs without 4-cycles, and therefore can be used for the construction of efficient bipartite-graph codes such that both the classes of its vertices are associated with local constraints. We significantly extend the region of parameters m, n for which there exist an n-regular bipartite graph with 2m vertices and without 4-cycles. In that way we essentially increase the region of lengths and rates of the corresponding bipartite-graph codes. Many new matrices are either circulant or consist of circulant submatrices: this provides code parity-check matrices consisting of circulant submatrices, and hence quasi-cyclic bipartite-graph codes with simple implementation.
Similar content being viewed by others
References
Gallager R.G.: Low-Density Parity-Check Codes. MIT Press, Cambridge (1963)
Tanner R.M.: A recursive approach to low complexity codes. IEEE Trans. Inf. Theory 27, 533–547 (1981)
Sipser M., Spielman D.: Expander codes. IEEE Trans. Inf. Theory 42, 1710–1722 (1996)
Lentmaier M., Zigangirov K.S.: On generalized low-density parity-check codes based on Hamming component codes. IEEE Commun. Lett. 3, 248–260 (1999)
Boutros, J., Pothier, O., Zémor, G.: Generalized low density (Tanner) codes. In: Proc. IEEE Int. Conf. Commun. (ICC), vol. 1. Vancouver, BC, Canada, pp. 441–445 (1999)
Kou Y., Lin S., Fossorier M.P.C.: Low-density parity-check codes based on finite geometries: a rediscovery and new results. IEEE Trans. Inf. Theory 47, 2711–2736 (2001)
Barg A., Zémor G.: Error exponents of expander codes. IEEE Trans. Inf. Theory 48, 1725–1729 (2002)
Johnson S.J., Weller S.R.: Resolvable 2-designs for regular low-density parity-check codes. IEEE Trans. Commun. 51, 1413–1419 (2003)
Weller S.R., Johnson S.J.: Regular low-density parity-check codes from oval designs. Eur. Trans. Telecommun. 14, 399–409 (2003)
Johnson, S.J., Weller, S.R.: High-rate LDPC codes from unital designs. In: Proc. IEEE Globecom Conf. San Francisco, CA, USA, pp. 150–152 (2003)
Lin S., Costello D.J. Jr: Error Control Coding: Fundamental and Applications. 2nd edn. Prentice Hall, Upper Saddle River, NJ (2004)
Fossorier M.P.C.: Quasi-cyclic low-density parity-check codes from circulant permutation matrices. IEEE Trans. Inf. Theory 50, 1788–1793 (2004)
Kim J.-L., Peled U.N., Perepelitsa I., Pless V., Friedland S.: Explicit construction of families of LDPC codes with no 4-cycles. IEEE Trans. Inf. Theory 50, 2378–2388 (2004)
Tanner R.M., Sridhara D., Sridharan A., Fuja T.E., Costello D.J. Jr: LDPC block and convolutional codes based on circulant matrices. IEEE Trans. Inf. Theory 50, 2966–2984 (2004)
Mellinger K.E.: LDPC codes from triangle-free line sets. Des. Codes Cryptogr. 32, 341–350 (2004)
Tang H., Xu J., Lin S., Abdel-Ghaffar K.A.S.: Codes on finite geometries. IEEE Trans. Inf. Theory 51, 572–596 (2005)
Mellinger K.E., Mubayi D.: Constructions of bipartite graphs from finite geometries. J. Graph Theory 49, 1–10 (2005)
Miladinović, N., Fossorier, M.: Generalized LDPC codes with Reed–Solomon and BCH codes as component codes for binary channels. In: Proc. IEEE Global Comm. Conf. (Globecom), vol. 3. St. Luis, MO, USA, pp. 6–10 (2005)
Barg A., Zémor G.: Distances properties of expander codes. IEEE Trans. Inf. Theory 52, 78–90 (2006)
Li Z.-W., Chen L., Zeng L., Lin S., Fong W.H.: Efficient encoding of quasi-cyclic low-density parity-check codes. IEEE Trans. Commun. 54, 71–81 (2006)
Gabidulin, E., Moinian, A., Honary, B.: Generalized construction of quasi-cyclic regular LDPC codes based on permutation matrices. In: Proc. Int. Symp. Inf. Theory 2006, ISIT 2006. Seattle, USA, pp. 679–683 (2006)
Høholdt, T., Justesen, J.: Graph codes with Reed–Solomon component codes. In: Proc. Int. Symp. Inf. Theory 2006, ISIT 2006. Seattle, USA, pp. 2022–2026 (2006)
Gabidulin, E.M.: On LDPC matrices equivalent to Vandermonde matrices. In: Proc. X Int. Workshop Algebraic Comb. Coding Theory, ACCT 2006. Zvenigorod, Russia, pp. 97–101 (2006). http://dcn.infos.ru/acct/ACCT2006/papers/gabi.pdf
Liva G., Song S., Lan L., Zhang Y., Lin S., Ryan W.E.: Design of LDPC codes: a survey and new results. J. Commun. Softw. Syst. 2, 191–211 (2006)
Droms S.V., Mellinger K.E., Meyer C.: LDPC codes generated by conics in the classical projective plane. Des. Codes Crypt. 40, 343–356 (2006)
Xu J., Chen L., Djurdjevic I., Abdel-Ghaffar K.: Construction of regular and irregular LDPC codes: geometry decomposition and masking. IEEE Trans. Inf. Theory 53, 121–134 (2007)
Lan L., Zeng L., Tai Y.Y., Chen L., Lin S., Abdel-Ghaffar K.: Construction of quasi-cyclic LDPC codes for AWGN and binary erasure channels: a finite field approach. IEEE Trans. Inf. Theory 53, 2429–2458 (2007)
Afanassiev, V.B., Davydov, A.A., Zyablov, V.V.: Low density concatenated codes with Reed–Solomon component codes. In: Proc. XI Int. Symp. on Problems of Redundancy in Inf. and Control Syst. St.-Petersburg, Russia, pp. 47–51 (2007). http://k36.org/redundancy2007
Mazumdar, A.: Analysis of bipartite graph codes on the binary erasure channel. In: Proc. 4–5 Annual Allerton Conf., UIUC. Illinois, USA, pp. 897–904 (2007)
Kim J.-L., Mellinger K.E., Storme L.: Small weight codewords in LDPC codes defined by (dual) classical generalized quadrangles. Des. Codes Crypt. 42, 73–92 (2007)
Miladinović N., Fossorier M.P.C.: Generalized LDPC codes and generalized stopping sets. IEEE Trans. Commun. 56, 201–212 (2008)
Zyablov, V., Johannesson, R., Lončar, M., Rybin, P.: On the error-correcting capabilities of low-complexity decoded LDPC codes with constituent Hamming codes. In: Proc. XI Int. Workshop Algebraic Comb. Coding Theory, ACCT2008. Pamporovo, Bulgaria, pp. 325–337 (2008). http://www.moi.math.bas.bg/acct2008/b54.pdf
Davydov, A.A., Giulietti, M., Marcugini, S., Pambianco, F.: Symmetric configurations for bipartite-graph codes. In: Proc. XI Int. Workshop Algebraic Comb. Coding Theory, ACCT2008. Pamporovo, Bulgaria, pp. 63–69 (2008). http://www.moi.math.bas.bg/acct2008/b11.pdf
Pepe V., Storme L., Van de Voorde G.: Small weight codewords in the LDPC codes arising from linear representations of geometries. J. Combin. Des. 17, 1–24 (2009)
Afanassiev V.B., Davydov A.A., Zyablov V.V.: Low density parity check codes on bipartite graphs with Reed–Solomon constituent codes. Electron. J. Inf. Process. 9(4), 301–331 (2009)
Castleberry C., Hunsberger K., Mellinger K.E.: LDPC codes arising from hyperovals. Bull. Inst. Combin. Appl. 58, 59–72 (2010)
Pepe V., Storme L., Van de Voorde G.: On codewords in the dual code of classical generalised quadrangles and classical polar spaces. Discrete Math. 310, 3132–3148 (2010)
Hirschfeld J.W.P.: Projective Geometries over Finite Fields. 2nd edn. Oxford Science, Oxford (1998)
Colbourn, C.J., Dinitz, J. (eds.): The CRC Handbook of Combinatorial Designs. 2nd edn. CRC Press, Boca Raton (2006)
Gropp H.: On the existence and non-existence of configurations n k . J. Combin. Inform. System Sci. 15, 34–48 (1990)
Gropp, H.: Non-symmetric configurations with deficiencies 1 and 2. In: Combinatorics 90, Ann. Discrete Math., vol 52, pp. 227–239 (1992)
Funk M., Labbate D., Napolitano V.: Tactical (de-)compositions of symmetric configurations. Discret. Math. 309, 741–747 (2009)
Abreu M., Funk M., Labbate D., Napolitano V.: On (minimal) regular graphs of girth 6. Australas. J. Combin. 35, 119–132 (2006)
Gács A., Héger T.: On geometric constructions of (k, g)-graphs. Contrib. Discr. Math. 3, 63–80 (2008)
Dembowski P.: Finite Geometries. Springer, Berlin (1968)
Hamilton N., Penttila T.: Sets of type (a, b) from subgroups of Γ L(1, p R). J. Algebraic Combin. 13, 67–76 (2001)
Coykendall J., Dover J.: Sets with few intersection numbers from Singer subgroup orbits. Eur. J. Combin. 22, 455–464 (2001)
Davydov A.A., Giulietti M., Marcugini S., Pambianco F.: New inductive constructions of complete caps in PG(N, q), q even. J. Comb. Des. 18, 176–201 (2010)
Giulietti M.: Small complete caps in PG(N, q), q even. J. Comb. Des. 15, 420–436 (2007)
Davydov A.A., Giulietti M., Marcugini S., Pambianco F.: On sharply transitive sets in PG(2, q). Innov. Incid. Geom. 6(7), 139–151 (2009)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Davydov, A.A., Giulietti, M., Marcugini, S. et al. Some Combinatorial Aspects of Constructing Bipartite-Graph Codes. Graphs and Combinatorics 29, 187–212 (2013). https://doi.org/10.1007/s00373-011-1103-5
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-011-1103-5
Keywords
- Low-density parity-check (LDPC) codes
- Bipartite-graph codes
- Graphs without 4-cycles
- Configurations in combinatorics
- Projective and affine spaces