Graceful codes : fundamental limits and constructions

A central question in information theory is to understand when and how data can be reconstructed from noisy observations Error correcting codes are means of adding redundancy to the data to enable better recovery Most commonly, codes are designed to recover data in a regime where the statistics of the noise are kept constant In a number of applications, however, it is required that the quality of the reconstruction degrade gracefully as noise statistics worsen It was known since the early work of Jacob Ziv (among others) that trade-offs between gracefullness and error correcting capability exist We focus on characterizing these trade-offs and proposing codes that are closer to optimal than those employed today The information-theoretic contributions consist of three parts combinatorial where we study the so called alpha-beta profile of codes over large alphabets, geometric - where we show that a linear code that spreads out nearby data vectors must contract some far away data vectors as well, and probabilistic - where we show that good linear codes must necessarily experience threshold effect, i e degrade their performance sharply when the noise level exceeds a certain limit Our main coding-theoretic contribution is the introduction of a new class of nonlinear sparse-graph codes that we call Low-Density Majority Codes (LDMCs) They admit efficient decoding via belief propagation and have provably superior performance compared to the best-possible linear systematic codes, in particular LDGMs Hence, we hope that LDMCs will be able to replace LDGMs in practical applications, such as pre-coding for optical channels, tornado-raptor codes, and protograph constructions.

Name thesis:degree_name

Doctoral

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Aeronautics and Astronautics

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2019

Author dc:creator

• Roozbeham, Hajir (Hosseini Roozbeham)

Advisor dc:contributor.advisor

• Yury Polyanskiy.

• Aeronautics and Astronautics.

Statement dc:rights

• MIT theses may be protected by copyright. Please reuse MIT thesis content according to the MIT Libraries Permissions Policy, which is available through the URL provided.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/139723

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/139723