Upper bounds on the rate of LDPC codes as a function of minimum distance

New upper bounds on the rate of low-density parity-check (LDPC) codes as a function of the minimum distance of the code are derived. The bounds apply to regular LDPC codes, and sometimes also to right-regular LDPC codes. Their derivation is based on combinatorial arguments and linear programming. The new bounds improve upon the previous bounds due to Burshtein et al. It is proved that at least for high rates, regular LDPC codes with full-rank parity-check matrices have worse relative minimum distance than the one guaranteed by the Gilbert-Varshamov bound.

I. Introduction

Low-density parity-check (LDPC) codes were introduced by Gallager [1] in the early sixties. An LDPC code is a binary linear code which can be defined by a sparse parity-check matrix, i.e., containing a negligible number of nonzero entries. These codes became subject to intensive research in recent years, since it was discovered that the sparseness of the parity-check matrix induces many desirable properties for implementation of efficient iterative decoding.