Limits of low-weight redundant checks in decoding random LDPC codes
Limits of Weight-Bounded Redundant Checks for Peeling Decoding of Random Regular LDPC Codes
Information Theory
Summary
When trying to fix data errors using a certain type of error-correcting code (LDPC codes), one can add extra checks to help find and fix problems. This paper shows that if these extra checks are limited to having only a small number of bits checked at once, then even adding many such checks will not improve error-fixing performance beyond a certain point. The authors prove that fixing all error patterns requires some checks that cover many bits at once, not just small ones.
What this means in practice
- •For error correction engineers: Design decoding algorithms knowing that restricting checks to small sizes limits solving all erasures in random LDPC codes efficiently.
- •For communication protocol developers: Avoid attempting to improve LDPC erasure decoding by only adding low-weight parity checks, since they do not improve critical decoding thresholds.
A theory result. No direct application yet.
Authors
Jianshen Zhu
Abstract
We study peeling decoding on the binary erasure channel when redundant parity checks may be added without restriction in number, but each check is subject to a row-weight constraint. For random simple binary regular low-density parity-check (LDPC) codes, we consider the parity-check matrix formed by all nonzero dual codewords up to a prescribed weight. We show that, throughout an explicit logarithmic row-weight range, this complete family of redundant checks has the same asymptotic normalized-residual threshold as peeling with the original LDPC matrix. In the same range, with probability tending to one over the random code, it still has a linear-size stopping set that is uniquely decodable. Consequently, every parity-check representation whose peeling decoder succeeds on every uniquely decodable erasure pattern must contain checks above this logarithmic scale, and the supports of those heavier checks must collectively contain a linear number of coordinates. Thus row weight remains an asymptotic limitation even when the number and selection of redundant checks are unrestricted.