On the Minimum Distance of Generalized LDPC Codes

Ayoub Otmani (1) , Jean-Pierre Tillich (2) , Iryna Andriyanova (3)

1 GREYC - Groupe de Recherche en Informatique, Image et Instrumentation de Caen
2 CODES - Coding and cryptography
3 EPFL - Ecole Polytechnique Fédérale de Lausanne

We study necessary conditions which have to be satisfied in order to have LDPC codes with linear minimum distance. We give two conditions of this kind in this paper. These conditions are not met for several interesting code families: this shows that they are not asymptotically good. The second one concerns LDPC codes that have a Tanner graph in which there are cycles linking variable nodes of degree 2 together and provides some insight about the combinatorial structure of some low-weight codewords in such a case. When the LDPC code family is obtained from the lifts of a given protograph and if there are such cycles in the protograph, the second condition seems to capture really well the linear minimum distance character of the code. This is illustrated by a code family which is asymptotically good for which there is a cycle linking all the variable nodes of degree 2 together. Surprisingly, this family is only a slight modification of a family which does not satisfy the second condition

Domaines: Algorithme et structure de données [cs.DS]

Ayoub Otmani, Jean-Pierre Tillich, Iryna Andriyanova. On the Minimum Distance of Generalized LDPC Codes. 2007 IEEE International Symposium on Information Theory, Jun 2007, Nice, France. pp.751-755. ⟨hal-00259015⟩