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

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

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