Decoding LDPC Codes with Maximum-Likelihood Single-Bit Messages

A framework for analyzing any memoryless extrinsic BMP algorithm operating on quantized channel samples.

Problem

Low density parity check (LDPC) codes have become an important component of modern communication standards. High-performance LDPC decoders use sophisticated message-passing algorithms, typically based on the belief propagation (BP) or min-sum (MS) algorithms. To reduce the decoding complexity, various binary message passing (BMP) algorithms have been developed. BMP decoders are known to provide good performance, but usually require edge-memories, creating complex dynamic behavior that is not easily analyzed. Due to the presence of memory in their decoding steps, traditional analysis methods, such as the density evolution method, cannot be directly applied to BMP algorithms. Density evolution can only be applied to memoryless algorithms that satisfy the extrinsic message passing requirement. Approximate thresholds are computable for some BMP algorithms, but the approximation method has limitations and may not be computationally tractable for all cases. Finally, in addition to BMP methods, a related class of bit-flipping methods has been studied but these algorithms violate the requirement for extrinsic message passing.

Solution

The locally maximum likelihood binary message passing (LMLBM) algorithm is memoryless, satisfies the extrinsic message passing requirement, and incorporates soft channel information. Density evolution thresholds are therefore obtainable for LMLBM. Some memoryless extrinsic algorithms were previously known, but they did not account for soft channel information and tend to have poor performance on the additive white Gaussian noise channel.

The LMLBM method can be interpreted as a framework for analyzing any memoryless extrinsic BMP algorithm operating on quantized channel samples. The algorithm assumes a standard bipartite Tanner graph comprised of symbol nodes and parity-check nodes. Like other BMP algorithms, the parity-check nodes are comprised of XOR operations. In each symbol node, the messages are determined by drawing decisions from a global look-up table with time varying elements. The look-up table elements are obtained by computing the locally maximum likelihood decision, given the channel information together with local extrinsic parity-checks.

Benefits

The LMLBM algorithm approaches min-sum performance in the high-degree and high-rate cases and is found to be very close to the differential decoding with binary message passing (DD-BMP) algorithm. Since LMLBM is a true memoryless extrinsic message passing algorithm, it can be studied using techniques that are not suited for studying bit-flipping decoders, DD-BMP, or other BMP decoders which use memory. The density evolution procedure generalizes directly for irregular degree distributions so that they can be evaluated and optimized for LMLBM decoding.

Applications

Potential applications include telecommunication, data storage, FPGAs, and IP cores and chips.

Contact

---

Questions about this technology including licensing availability can be directed to:

Alan Edwards, MA, JD
Manager, Technology Transfer Services
(435) 797-2328 alan.edwards@usu.edu

---

USU ID C14061