Upper Bounds on the Minimum Distance of Structured LDPC Codes

Abstract

We investigate the minimum distance of structured binary Low-Density Parity-Check (LDPC) codes whose parity-check matrices are of the form $[\mathbf{C}|\mathbf{M}]$ where $\mathbf{C}$ is circulant and of column weight $2$, and $\mathbf{M}$ has fixed column weight $r\ge 3$ and row weight at least $1$. These codes are of interest because they are LDPC codes which come with a natural linear-time encoding algorithm. We show that the minimum distance of these codes is in $O(n^{\frac{r-2}{r-1}+\hat{I}\mu })$, where $n$ is the code length and $\hat{I}\mu >0$ is arbitrarily small. This improves the previously known upper bound in $O(n^{\frac{r-1}{r}})$ on the minimum distance of such codes.