ECCS/CCSS: Neural Network Nonlinear Iterative LDPC Decoders with Guaranteed Error Performance and Fast Convergence

低密度奇偶校验码（LDPC）是现代通信和数据存储系统的重要组成部分。在许多应用中，在严格的吞吐量、延迟、面积、能量或功率限制下实现所需的数据可靠性是具有挑战性的，因此对解码算法的根本突破的需求尚未得到满足。为了满足这一需求，研究小组将为LDPC码开发新颖复杂的解码算法。新的解码器将直接应用于对错误性能要求最严格的闪存和光通信，以及需要非常低延迟的大规模机器类型通信。这项提议的研究将为新一代芯片开辟一条道路，大大减少能源需求，降低环境足迹。参赛学生将接受工程和数学方面的高级培训。他们的教育经验将通过PI与来自学术界和工业界的国内和国际合作者的密切合作而丰富。传统的LDPC解码算法通过沿着图的边缘传播消息来操作代码的图形模型。在这种迭代消息传递解码器中，存储消息所需的内存与消息宽度和图中节点数量的乘积成正比，对于实际感兴趣的代码，节点数量约为数千个。因此，降低消息宽度可以大大降低复杂度，但会导致译码性能的下降，即错误层，并减慢译码收敛速度。提出的研究通过以下新方法以统一的方式解决硬件复杂性，错误层和收敛问题：(1)非线性消息更新函数<e:1> -错误层直接与Tanner图中引起解码器故障的某些子图结构（称为捕获集）的存在相关联。我们的消息更新规则将是非线性的，并明智地选择以消除捕获集的影响，从而降低错误下限。(2)保证的纠错能力<e:2> -此外，对解码器无法纠正的捕获集的精确了解解决了与LDPC码相关的基本问题-缺乏数据可靠性保证。这开启了大量的设计可能性，但由于潜在的良好消息更新规则的数量很大，因此需要一种系统的方法来搜索最佳规则，为此我们将依赖神经网络。(3)神经网络解码器<e:1> -主要思想来自于这样的观察，即在时间（迭代）中展开的图本质上形成了一个神经网络，可以通过训练来产生最优更新规则。生成的更新规则还需要更少的迭代次数才能成功解码。(4)内置学习<e:1> -解码器将配备学习工具。这样，梯度下降算法在训练过程中不是离线使用，而是在解码过程中使用。损失函数基于统计力学中能量函数的概念，通过不满足奇偶校验的次数来捕获解码器输出到码字的距离。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Low-density parity-check (LDPC) codes are an integral part of modern communications and data storage systems. In many applications, achieving desired data reliability with strict throughput, latency, area, energy or power constraints is challenging, and thus there is an unmet need for fundamental breakthroughs in decoding algorithms. To meet this need, the research team will develop novel sophisticated decoding algorithms for LDPC codes. The new decoders will have a direct application in flash memories and optical communications which have the most stringent requirements on error performance, and in massive machine-type communications requiring very low-latencies. The proposed research will create a path to a new generation of chips with greatly reduced energy requirements and lower environmental footprint. The participating students will receive advanced training in engineering and mathematics. Their educational experiences will be enriched by close collaboration between the PI and his national and international collaborators from academia and industry.The conventional LDPC decoding algorithms operate on a graphical model of a code by propagating messages along edges of the graph. In such an iterative message-passing decoder, the memory needed to store messages is proportional to the product of the message width and the number of nodes in the graph, which is of the order of thousands for codes of practical interest. Therefore lowering message width reduces the complexity greatly, but causes a degradation of decoding performance known as error floor, and slows down decoding convergence. The proposed research addresses the hardware complexity, error floor and convergence problems in a unified way by the following novel approaches: (1) Nonlinear message update functions – Error floor is directly linked to the presence of certain subgraph structures, called trapping sets, in the Tanner graph that induce decoder failures. Our message update rules will be nonlinear and judiciously chosen to eliminate the effect of trapping sets, and will thus lower the error floor. (2) Guaranteed error correction capability – Moreover, the precise knowledge of what trapping sets are not correctable by a decoder solves the fundamental issue associated with LDPC codes - the lack of data reliability guarantees. This opens a plethora of design possibilities, but since the number of potentially good message update rules is large, a systematic method is needed to search for the optimal ones, and for this we will rely on neural networks. (3) Neural network decoders – The main idea follows from the observation that a graph unwrapped in time (iterations) essentially forms a neural network which can be trained to produce an optimal update rule. The resulting update rule also requires much smaller number of iterations for a successful decoding. (4) Built-in learning – The decoders will be equipped with instruments of learning. In this way, the gradient descent algorithm is not used offline during training but during decoding. The loss function based on the concept of energy function from statistical mechanics, and captures the distance of the decoder output from a codeword through the number of unsatisfied parity checks.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.