CIF: Small: Polar Codes --- From Theory to Practice

CIF：小码：Polar 码 --- 从理论到实践

• 批准号: 1116820
• 负责人: Alexander Vardy
• 金额: $ 49.46万
• 依托单位: University of California-San Diego
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-09-01 至 2014-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1116820&HistoricalAwards=false
• 关键词: CIF; Small; Polar; Codes; Theory

Digital communication pervades our daily lives while digital storage devices have become the principal means of preserving our information. During the "information age," in which we now live, the need for reliable transmission and storage of digital data is of paramount importance. What makes such reliable transmission and storage possible are error- correcting codes, first conceived by Claude Shannon over 50 years ago. The recent invention of polar codes is, without doubt, the most original and profound development in the theory of error-correcting codes in the past decade. Polar codes provably achieve the capacity of any memoryless symmetric channel, with low encoding and decoding complexity, thereby providing the first deterministic and constructive solution to the problem posed by Shannon in 1948. Nevertheless, the impact of polar codes in practice has been, so far, negligible. The objective of this project is to advance the theory of polar codes on one hand, and to bring polar codes much closer to practice on the other hand. If successful, the outcome of this research is likely to become an enabling technology for numerous communications applications, both commercial and for national security.In order to make polar codes practical, major obstacles must be resolved. The first key problem in the field is how to efficiently construct polar codes. This project aims to develop a linear-time construction algorithm, with explicit guarantees on the quality of its output. The investigators also study algebraic and combinatorial structure of polar codes, with the goal of developing a good analytical handle on the rate of channel polarization. Currently available empirical results indicate that the rate of channel polarization is too slow for many applications. Thus the investigators intend to drastically improve the performance of polar codes, at short to moderate code lengths, by introducing certain key modifications in the successive-cancellation decoding algorithm. One especially promising idea in this regard is list decoding. A concerted effort is devoted to the analysis of list decoding algorithms for polar codes. Furthermore, a full implementation of such decoding algorithms in high-speed and low-power VLSI is pursued. This part of the research involves algorithmic transformations for the key steps of the decoder, effective high-throughput design techniques, careful VLSI complexity/area analysis, and new computation scheduling ideas. Finally, applications of polar codes and channel polarization beyond point-to-point communications are considered. Such applications include multiple-access channels, relay channels, Slepian-Wolf coding, and information-theoretic security.

数字通信遍布我们的日常生活，而数字存储设备已成为保留我们信息的主要手段。在我们现在居住的“信息时代”中，对数字数据的可靠传输和存储的需求至关重要。使这种可靠的传输和存储成为可能的是错误纠正代码，这是克劳德·香农（Claude Shannon）在50年前首先构想的。毫无疑问，最近十年中，极地代码的最新发明是误差校正码理论中最原始，最深刻的发展。极性代码可证明实现了任何无内存的对称通道的能力，具有低编码和解码的复杂性，从而为Shannon在1948年提出的问题提供了第一个确定性和建设性的解决方案。但是，到目前为止，极地代码在实践中的影响至今已忽略不可忽略。该项目的目的是一方面推进极地代码的理论，另一方面使极地代码更接近实践。如果成功的话，这项研究的结果可能会成为用于商业安全和国家安全的众多通信应用程序的促成技术。为了使极地代码实用，必须解决主要障碍。该领域的第一个关键问题是如何有效构建极地代码。该项目旨在开发线性时间构建算法，并明确保证其产出质量。研究人员还研究了极地代码的代数和组合结构，目的是对通道极化速率进行良好的分析处理。当前可用的经验结果表明，对于许多应用，通道极化的速率太慢。因此，研究人员打算通过在连续的策略解码算法中引入某些关键修改，从而大幅度提高极地代码的性能，简短到中等代码长度。在这方面，一个特别有希望的想法是列表解码。一致的努力致力于分析极地代码的列表解码算法。此外，追求了高速和低功率VLSI中这种解码算法的全面实施。研究的这一部分涉及解码器，有效的高通量设计技术的关键步骤，仔细的VLSI复杂性/区域分析以及新的计算计划思想的算法转换。最后，考虑了超出点对点通信的极地代码和通道极化的应用。此类应用程序包括多访问频道，继电器频道，SLEPIAN-WOLD编码和信息理论安全性。