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

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

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.