LDPC Codes Achieve List Decoding Capacity
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2019
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911949539770368 |
|---|---|
| author | Mosheiff, Jonathan Resch, Nicolas Ron-Zewi, Noga Silas, Shashwat Wootters, Mary |
| author_facet | Mosheiff, Jonathan Resch, Nicolas Ron-Zewi, Noga Silas, Shashwat Wootters, Mary |
| contents | 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 $\textit{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^*$ so that random linear codes of rate slightly less than $R^*$ satisfy $\mathcal{P}$ with high probability, while random linear codes of rate slightly more than $R^*$, with high probability, do not. We also give a characterization of the threshold rate $R^*$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1909_06430 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | LDPC Codes Achieve List Decoding Capacity Mosheiff, Jonathan Resch, Nicolas Ron-Zewi, Noga Silas, Shashwat Wootters, Mary Information Theory Computational Complexity Combinatorics 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 $\textit{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^*$ so that random linear codes of rate slightly less than $R^*$ satisfy $\mathcal{P}$ with high probability, while random linear codes of rate slightly more than $R^*$, with high probability, do not. We also give a characterization of the threshold rate $R^*$. |
| title | LDPC Codes Achieve List Decoding Capacity |
| topic | Information Theory Computational Complexity Combinatorics |
| url | https://arxiv.org/abs/1909.06430 |