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

该项目解决了差错控制编码理论中一些当前最重要的基础研究挑战。关于有效解码方法的大部分当前理论本质上是渐进的，并且因此对于延迟敏感应用所需的较短和中间块长度（例如，高速通信、流和对等网络）。一个密切相关的目标是更深入地了解某些类别的低密度奇偶校验（LDPC）码所表现出的所谓的“错误平层”行为。这些错误平层严重限制了它们对于非常低的误码率（BER）应用（例如，高速通信、数据存储）。目前的一个主要瓶颈是缺乏系统和可靠的方法来探索这种深度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