Some Combinatorial Aspects of Constructing Bipartite-Graph Codes

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.

• Publication year

  2009

• Venue

  Graphs Comb.

• Publication date

  2009-09-30

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/s00373-011-1103-5arXiv 0909.5669
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On codewords in the dual code of classical generalised quadrangles and classical polar spaces

  2010cited by this paper
• Small weight codewords in the LDPC codes arising from linear representations of geometries

  2009influential reference
• Tactical (de-)compositions of symmetric configurations

  2009influential reference
• Low density parity check codes on bipartite graphs with Reed-Solomon constituent codes 1

  2009influential reference
• New inductive constructions of complete caps in PG(N, q), q even

  2009cited by this paper
• On geometric constructions of (k, g)-graphs

  2008cited by this paper
• On sharply transitive sets in PG(2,q)

  2008cited by this paper
• On the erasure-correcting capabilities of low-complexity decoded LDPC codes with constituent Hamming codes

  2008cited by this paper
• Generalized LDPC codes and generalized stopping sets

  2008cited by this paper
• Symmetric configurations for bipartite-graph codes

  2008cited by this paper
• Construction of Quasi-Cyclic LDPC Codes for AWGN and Binary Erasure Channels: A Finite Field Approach

  2007cited by this paper
• Small weight codewords in LDPC codes defined by (dual) classical generalized quadrangles

  2007influential reference
• Analysis of bipartite graph codes on the binary erasure channel

  2007cited by this paper
• Construction of Regular and Irregular LDPC Codes: Geometry Decomposition and Masking

  2007influential reference
• Small complete caps in PG(N, q), q even

  2007cited by this paper
• Randomly r-orthogonal (0, f)-factorizations of (0, mf-m+1)-graphs

  2007cited by this paper
• Generalized Construction of Quasi-Cyclic Regular LDPC Codes Based on Permutation Matrices

  2006influential reference
• Graph Codes with Reed-Solomon Component Codes

  2006cited by this paper
• A Family of Generalized Constant Modulus Algorithms for Blind Equalization

  2006cited by this paper
• LDPC codes generated by conics in the classical projective plane

  2006influential reference
• Multilevel expander codes

  2005cited by this paper
• Generalized LDPC codes with Reed-Solomon and BCH codes as component codes for binary channels

  2005cited by this paper
• Constructions of bipartite graphs from finite geometries

  2005cited by this paper
• Efficient encoding of quasi-cyclic low-density parity-check codes

  2005cited by this paper
• Codes on finite geometries

  2005influential reference
• Distance properties of expander codes

  2004cited by this paper
• Distance properties of expander codes

  2004cited by this paper
• Low-Density Parity-Check Codes

  2004cited by this paper
• LDPC Codes from Triangle-Free Line Sets

  2004cited by this paper
• LDPC block and convolutional codes based on circulant matrices

  2004cited by this paper
• Explicit construction of families of LDPC codes with no 4-cycles

  2004cited by this paper
• Quasicyclic low-density parity-check codes from circulant permutation matrices

  2004influential reference
• Regular low-density parity-check codes from oval designs

  2003cited by this paper
• Resolvable 2-designs for regular low-density parity-check codes

  2003influential reference
• High-rate LDPC codes from unital designs

  2003cited by this paper
• Sets of Type (a, b) From Subgroups of ΓL(1, pR)

  2001cited by this paper
• Error exponents of expander codes

  2001cited by this paper
• Low-density parity-check codes based on finite geometries: A rediscovery and new results

  2001influential reference
• Sets with few Intersection Numbers from Singer Subgroup Orbits

  2001cited by this paper
• Generalized low density (Tanner) codes

  1999cited by this paper
• On generalized low-density parity-check codes based on Hamming component codes

  1999cited by this paper
• The CRC handbook of combinatorial designs , edited by Charles J. Colbourn and Jeffrey H. Dinitz. Pp. 784. $89.95. 1996. ISBN 0-8493-8948-8 (CRC).

  1997cited by this paper
• Non-symmetric configurations with deficiencies 1 and 2

  1992cited by this paper
• Error Control Coding: Fundamentals and Applications

  1985cited by this paper
• Error control coding : fundamentals and applications

  1983cited by this paper
• A recursive approach to low complexity codes

  1981cited by this paper
• Projective Geometries Over Finite Fields

  1980cited by this paper
• Review of 'Low-Density Parity-Check Codes' (Gallager, R. G.; 1963)

  1964cited by this paper

• Incidence matrices for the class $${\mathcal {O}}_6$$ O 6 of lines external to the twisted cubic in

  2023cites this paper
• Twisted cubic and plane-line incidence matrix in PG(3,q)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm {PG}(3

  2022cites this paper
• Twisted cubic and plane-line incidence matrix in $$\mathrm {PG}(3,q)$$

  2022cites this paper
• Twisted cubic and point-line incidence matrix in PG(3,q)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm {PG}(3

  2021cites this paper
• Twisted cubic and point-line incidence matrix in $\mathrm {PG}(3, q)$

  2021cites this paper
• On planes through points off the twisted cubic in PG(3, q) and multiple covering codes

  2019cites this paper
• A latitudinal diversity gradient of shallow-water gorgonians (Cnidaria: Octocorallia: Alcyonacea) along the Tropical Eastern Pacific Ocean: testing for underlying mechanisms

  2019cites this paper
• On planes through points off the twisted cubic in $\mathrm{PG}(3,q)$ and multiple covering codes

  2019cites this paper
• Further results on multiple coverings of the farthest-off points

  2015cites this paper
• Multiple coverings of the farthest-off points with small density from projective geometry

  2015cites this paper
• Tables of parameters of symmetric configurations $v_{k}$

  2013cites this paper
• On constructions and parameters of symmetric configurations $$v_{k}$$vk

  2012influential citation