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

University Of Arizona, Tucson AZ

Investigators

Abstract

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.