Error Correction Capability of Column-Weight-Three LDPC Codes

Abstract

In this paper, we investigate the error correction capability of column-weight-three LDPC codes when decoded using the Gallager A algorithm. We prove that the necessary condition for a code to correct $k\ge 5$ errors is to avoid cycles of length up to $2k$ in its Tanner graph. As a consequence of this result, we show that given any $\alpha >0,\exists N$ such that $\forall n>N$, no code in the ensemble of column-weight-three codes can correct all $\alpha n$ or fewer errors. We extend these results to the bit flipping algorithm.

16 pages, 3 figures. Submitted to IEEE Transactions on Information Theory

Cited by in corpus (1)

• On the Hardness of Approximating Stopping and Trapping Sets in LDPC Codes