LDPC Codes Achieve List Decoding Capacity

Abstract

We show that Gallager's ensemble of Low-Density Parity Check (LDPC) codes achieves list-decoding capacity with high probability. These are the first graph-based codes shown to have this property. This result opens up a potential avenue towards truly linear-time list-decodable codes that achieve list-decoding capacity. Our result on list decoding follows from a much more general result: any $\text{local}$ property satisfied with high probability by a random linear code is also satisfied with high probability by a random LDPC code from Gallager's distribution. Local properties are properties characterized by the exclusion of small sets of codewords, and include list-decodability, list-recoverability and average-radius list-decodability. In order to prove our results on LDPC codes, we establish sharp thresholds for when local properties are satisfied by a random linear code. More precisely, we show that for any local property $\mathcal{P}$, there is some $R^{\ast }$ so that random linear codes of rate slightly less than $R^{\ast }$ satisfy $\mathcal{P}$ with high probability, while random linear codes of rate slightly more than $R^{\ast }$, with high probability, do not. We also give a characterization of the threshold rate $R^{\ast }$.

39 pages, 3 figures

References in corpus (1)

• On the weight distribution of random binary linear codes

Cited by in corpus (2)

• Single-shot preparation of hypergraph product codes via dimension jump
• Optimal Particle-Conserved Linear Encoding for Practical Fermionic Simulation