Theory and Methodology for the Design and Evaluation of High-Performance LDPC Codes

该项目解决了当前差错控制编码理论中一些最重要的基础研究挑战。当前关于有效解码方法的大部分理论在本质上是渐近的，因此不能对延迟敏感应用(例如，高速通信、流和对等网络)所需的较短和中间块长度产生有用的预测。一个密切相关的目标是更深入地了解某些类低密度奇偶校验(LDPC)码所表现出的所谓的“差错平台”行为。这些错误平层严重限制了它们对于非常低的误码率(BER)应用(例如，高速通信、数据存储)的有用性。目前的一个主要瓶颈是缺乏系统和可靠的方法来探索这种深度误码率机制，我们建议通过组合和几何分析、基于硬件的仿真和快速随机模拟来解决这一挑战。智力优势：缺乏有限长度分析和错误平层的存在是阻碍高性能码在一系列非常重要的应用中部署的关键瓶颈。解决这一挑战需要一系列深层次和基础性的科学问题，借鉴多面体组合学、图论、动力系统和概率论的思想。高性能应用的消息传递算法的硬件实现本身就具有挑战性。该研究以高性能迭代译码器的开发为设计驱动，开发了一种新的基于仿真的设计方法。这一范式是新颖的，并提出了许多基本挑战，包括开发收集错误统计数据的快速模拟技术，利用错误统计数据设计更好代码的随机自适应算法，以及研究将代码设计高效映射到现场可编程门阵列(FPGA)平台的系统技术。广泛影响：图形上的消息传递算法在广泛的科学和工程学科中发挥着基础性作用。应用范围涵盖通信系统、图像处理、生物信息学、统计物理和自然语言处理等多个领域。因此，我们的研究，其明确的目标是更深入地了解消息传递算法，具有在各种领域产生广泛影响和传播的潜力。此外，我们的项目还包含重要的教育和外展内容。伯克利的研究生将在参与这项研究的同时接受算法和VLSI设计技术方面的培训。来我们这个项目的学生将拥有一套独特的技能，跨越理论和实施，因此构成了国家技术劳动力的宝贵补充。我们还非常积极地促进本科生的研究，并促进来自历史上代表性不足的社区的学生的研究经验。该项目的总体主旨有许多明确界定的子项目，这使其非常适合本科生一级的这种外联活动。

The project addresses some of the currently most important basic research challenges in errorcontrol coding theory. The bulk of current theory on efficient decoding methods is asymptotic in nature, and thus does not yield useful predictions for the shorter and intermediate blocklengths needed for delaysensitive applications (e.g., high-speed communications, streaming and peer-to-peer networks). A closely related goal is to gain a deeper understanding the so-called "error floor" behavior exhibited by certain classes of low-density parity check (LDPC) codes. These error floors seriously limit their usefulness for very low bit error rate (BER) applications (e.g., high-speed communications, data storage). A current major bottleneck is the lack of systematic and reliable methods to explore this deep BER regime, and we propose to address this challenge through a combination of combinatorial and geometric analysis, hardware-based emulation,and fast stochastic simulation.Intellectual merit: Lack of finite-length analysis and the existence of error floors is a key bottleneck slowing down the deployment of high performance codes in a range of very important applications. Addressing this challenge requires a range of deep and fundamental scientific questions, drawing on ideas from polyhedral combinatorics, graph theory, dynamical systems and probability theory. Hardware implementation of message passing algorithms for high performance applications is in itself challenging. The research uses the development of high performance iterative decoders as a design driver for developing a novel emulation-simulation based design approach. This paradigm is novel and poses many fundamental challenges,including the development of fast simulation techniques for gathering error statistics, stochasticadaptive algorithms that exploit error statistics in order to design better codes, and investigation of systematic techniques for efficiently mapping code designs onto a field-programmable gate array (FPGA) platform.Broader impact: Message-passing algorithms on graphs play a fundamental role across of a broad spectrum of scientific and engineering disciplines. The range of applications covers areas as diverse as communication systems, image processing, bioinformatics, statistical physics, and natural language processing, among many others. Consequently, our research, with its explicit goal of gaining a deeper understanding of message passing algorithms, has the potential for broad impact and dissemination across a variety of areas. In addition, our project has a significant educational and outreach component. Graduate students at Berkeley will be trained in both algorithmic and VLSI design techniques while participating in this research. Students coming our of this program will have a unique skill set that spans both theory and implementation,thereby constituting an invaluable addition to the nation's technical workforce. We are also very active in promoting undergraduate research and in facilitating research experiences for students from historically underrepresented communities. The overall thrust of this project has many well defined subprojects, which makes it very well-suited to such outreach activity at the undergraduate level.1