首页    期刊浏览 2024年11月28日 星期四
登录注册

文章基本信息

  • 标题:LDPC Codes Achieve List-Decoding Capacity
  • 本地全文:下载
  • 作者:Jonathan Mosheiff ; Nicolas Resch ; Noga Ron-Zewi
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2019
  • 卷号:2019
  • 页码:1-32
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We show that Gallager's ensemble of Low-Density Parity Check (LDPC) codes achieve list-decoding capacity. These are the first graph-based codes shown to have this property. Previously, the only codes known to achieve list-decoding capacity were completely random codes, random linear codes, and codes constructed by algebraic (rather than combinatorial) techniques. This result opens up a potential avenue towards truly linear-time list-decodable codes which achieve list-decoding capacity.Our result on list decoding follows from a much more general result: any 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-decoding, list-recovery and average-radius list-decoding. Along the way, we give a characterization of sets of codewords that are likely to appear in a random linear code, which may be of independent interest.

  • 关键词:expander codes ; List Decoding Capacity ; Low-density Parity Check codes
国家哲学社会科学文献中心版权所有