Threshold rates for error correcting codes
Abstract/Contents
- Abstract
- Completely random codes, random linear codes and Gallager's Low Density Parity Check (LDPC) codes are amongst the most fundamental and well-studied error correcting codes. A complete understanding of the combinatorial properties of completely random and random linear codes is important for informing our basic beliefs about what properties any error correcting code can achieve. As such, these questions have received great attention since the very conception of the field. LDPC codes are uniquely important in error-correction due to their vast practical use and fast decoding algorithms. However, precious little had been understood about their combinatorial properties beyond a proof that they achieve the Gilbert-Varshamov bound over binary alphabets, which was provided by Gallager in the 1960s. We develop a new method to precisely characterize vast groups of combinatorial properties for completely random and random linear codes. These groups of properties are general enough to include many of coding theory's most popular obsessions like distance, list-decoding, list-recovery, and their meaningful variants. Our main conceptual contributions are the characterization theorems for symmetric properties of random codes and local properties of random linear codes. In these results, we show that for any property under consideration, there is a 'threshold rate' associated to the property: below that rate it is highly unlikely for the code to achieve the property, and even slightly above that rate it is almost certain. Further, we also give a simple characterization for this threshold rate. In our view, the discovery and characterization of such 'phase transitions' for large classes of natural properties of these error correcting codes is fundamental. Further, it ties in neatly with a line of highly influential work in graph theory and boolean functions (which describes similar phenomena in those domains) beginning with Erdos in the 1950s. Finally, we show that if a random linear code achieves a local property, then so does an LDPC code the same rate. We use our characterizations to show a variety of new results about properties of completely random and random linear codes which are of particular interest to coding theorists. For random linear codes, perhaps our most compelling result shows that the list size of a binary random linear code takes just one of three values with all but negligible probability. Since completely random codes are considered quite 'easy' to analyze, an informed reader may be surprised that there are meaningful questions yet to be answered in this domain. Even here, our techniques give several new results. Notably, we can precisely compute the threshold rate for completely random codes to achieve properties such as perfect hashing and list-of-two decodability. Most surprisingly perhaps, we show that for a large class of combinatorial properties, Gallager's LDPC codes are as good as random linear codes. We hope that this particular result opens new paths towards solving the central open problems in coding theory: (i) finding explicit constructions of binary codes which achieve the GV bound and list-decoding capacity, (ii) finding linear time algorithms for list-decoding codes up to capacity.
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource. |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | 2021; ©2021 |
| Publication date | 2021; 2021 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Silas, Shashwat |
|---|---|
| Degree supervisor | Wootters, Mary |
| Thesis advisor | Wootters, Mary |
| Thesis advisor | Tan, Li-Yang |
| Thesis advisor | Valiant, Gregory |
| Degree committee member | Tan, Li-Yang |
| Degree committee member | Valiant, Gregory |
| Associated with | Stanford University, Computer Science Department |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Shashwat Silas. |
|---|---|
| Note | Submitted to the Computer Science Department. |
| Thesis | Thesis Ph.D. Stanford University 2021. |
| Location | https://purl.stanford.edu/mb262qp1973 |
Access conditions
- Copyright
- © 2021 by Shashwat Silas
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...