東華大學圖書館 |

Threshold Rates for Error Correcting Codes.

Record Type:	Electronic resources : Monograph/item
Title/Author:	Threshold Rates for Error Correcting Codes./
Author:	Silas, Shashwat.
Published:	Ann Arbor : ProQuest Dissertations & Theses, : 2021,
Description:	222 p.
Notes:	Source: Dissertations Abstracts International, Volume: 83-06, Section: B.
Contained By:	Dissertations Abstracts International83-06B.
Subject:	Codes. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=28483283
ISBN:	9798505571859

Threshold Rates for Error Correcting Codes.
Silas, Shashwat.

Threshold Rates for Error Correcting Codes. - Ann Arbor : ProQuest Dissertations & Theses, 2021 - 222 p.

Source: Dissertations Abstracts International, Volume: 83-06, Section: B.

Thesis (Ph.D.)--Stanford University, 2021.

This item must not be sold to any third party vendors.

Error correcting codes are used for the reliable communication of information over a noisy channel. Before transmission over the channel, information is encoded with an error correcting code so that even if certain parts of it are corrupted or lost during transmission, the receiver may decode the original message. Error-correction is a ubiquitous technology in our lives since all channels of information transmission are prone to noise. In this dissertation, we look at some of the basic mathematical questions about error correcting codes and develop new tools towards understanding them.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.

ISBN: 9798505571859Subjects--Topical Terms:

3560019
Codes.
Subjects--Index Terms:

Threshold rates

Threshold Rates for Error Correcting Codes.
LDR:05026nmm a2200385 4500 001 2346869
005 20220706051311.5
008 241004s2021 ||||||||||||||||| ||eng d
020 $a 9798505571859
035 $a (MiAaPQ)AAI28483283
035 $a (MiAaPQ)STANFORDmb262qp1973
035 $a AAI28483283
040 $a MiAaPQ $c MiAaPQ
100 1 $a Silas, Shashwat. $3 3686066
245 1 0 $a Threshold Rates for Error Correcting Codes.
260 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2021
300 $a 222 p.
500 $a Source: Dissertations Abstracts International, Volume: 83-06, Section: B.
500 $a Advisor: Wootters, Mary; Tan, Li-Yang.
502 $a Thesis (Ph.D.)--Stanford University, 2021.
506 $a This item must not be sold to any third party vendors.
520 $a Error correcting codes are used for the reliable communication of information over a noisy channel. Before transmission over the channel, information is encoded with an error correcting code so that even if certain parts of it are corrupted or lost during transmission, the receiver may decode the original message. Error-correction is a ubiquitous technology in our lives since all channels of information transmission are prone to noise. In this dissertation, we look at some of the basic mathematical questions about error correcting codes and develop new tools towards understanding them.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.
590 $a School code: 0212.
650 4 $a Codes. $3 3560019
650 4 $a Low density parity check codes. $3 3682517
650 4 $a Computer engineering. $3 621879
650 4 $a Computer science. $3 523869
650 4 $a Information science. $3 554358
650 4 $a Multimedia communications. $3 590562
653 $a Threshold rates
653 $a Error correction
653 $a Error correcting codes
653 $a Coding theory
690 $a 0984
690 $a 0464
690 $a 0723
690 $a 0558
710 2 $a Stanford University. $3 754827
773 0 $t Dissertations Abstracts International $g 83-06B.
790 $a 0212
791 $a Ph.D.
792 $a 2021
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=28483283