{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/139723"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/139723","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Graceful codes : fundamental limits and constructions","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Roozbeham, Hajir (Hosseini Roozbeham)"],"institution":"Massachusetts Institute of Technology","degree_name":"Doctoral","degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Department of Aeronautics and Astronautics","school":null,"contributors":[],"advisors":["Yury Polyanskiy."],"committee_chairs":[],"committee_members":[],"year":2019,"date_issued":"2019","date_published":"2019","updated_at":"2026-07-22T22:21:50Z","subjects":["Aeronautics and Astronautics."],"languages":["eng"],"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."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1721.1/139723","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Yury Polyanskiy."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Department of Aeronautics and Astronautics","Aero"]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Department of Aeronautics and Astronautics."]},{"key":"dc:creator","label":"Author","values":["Roozbeham, Hajir (Hosseini Roozbeham)"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2022-01-25T16:14:42Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2022-01-25T16:14:42Z"]},{"key":"dc:date.issued","label":"Date","values":["2019"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctoral"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Aeronautics and Astronautics."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["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."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1721.1/139723"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis: Ph. D., Massachusetts Institute of Technology, Department of Aeronautics and Astronautics, September, 2019","Cataloged from the official PDF of thesis.","Includes bibliographical references (pages 147-155)."]},{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Ph. D."]},{"key":"dc:title","label":"Title","values":["Graceful codes : fundamental limits and constructions"]}]}],"canonical_facts":{"dc:contributor.advisor":["Yury Polyanskiy."],"dc:contributor.department":["Massachusetts Institute of Technology. Department of Aeronautics and Astronautics","Aero"],"dc:contributor.other":["Massachusetts Institute of Technology. Department of Aeronautics and Astronautics."],"dc:creator":["Roozbeham, Hajir (Hosseini Roozbeham)"],"dc:date.accessioned":["2022-01-25T16:14:42Z"],"dc:date.available":["2022-01-25T16:14:42Z"],"dc:date.issued":["2019"],"dc:description":["Thesis: Ph. D., Massachusetts Institute of Technology, Department of Aeronautics and Astronautics, September, 2019","Cataloged from the official PDF of thesis.","Includes bibliographical references (pages 147-155)."],"dc:description.abstract":["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."],"dc:description.degree":["Ph. D."],"dc:identifier.uri":["https://hdl.handle.net/1721.1/139723"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"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."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Aeronautics and Astronautics."],"dc:title":["Graceful codes : fundamental limits and constructions"],"dc:type":["Thesis"],"thesis:degree_name":["Doctoral"]},"updated_at":"2026-07-22T22:21:50Z"}