Low-density parity-check code

Low-density parity-check (LDPC) codes, also known as Gallager codes, are a class of error-correction codes first proposed in 1960. Together with the closely related turbo codes, they have gained prominence in coding theory and information theory since the late 1990s. The codes today are widely used in applications ranging from wireless communications to flash-memory storage. Together with turbo codes, they sparked a revolution in coding theory, achieving order-of-magnitude improvements in performance compared to traditional error correction codes.

LDPC codes were originally conceived by Robert G. Gallager in 1960. Gallager devised the codes in his doctoral dissertation at the Massachusetts Institute of Technology. The codes were largely ignored at the time, as their iterative decoding algorithm (despite having linear complexity) was prohibitively computationally expensive for the hardware available. They came back into favor in the mid 1990s, both because improved hardware made them practical, and because they provided a high performance and patent-free alternative to turbo codes.

Central to the performance of LDPC codes is their adaptability to the iterative belief-propagation decoding algorithm. Under this algorithm, they can be designed to approach theoretical limits (capacities) of many channels at low computation costs.

[−PT|In−k] through basic row operations in GF(2):

P=−P), or specifically:

⊙ is symbol of mod 2 multiplication.

As a check, the row space of G is orthogonal to H such that 𝐳=𝐇⊙𝐫=(111100001101100110)⊙(101011)=(000).

Because the outcome z (the syndrome) of this operation is the three × one zero vector, the resulting codeword r is successfully validated.

After the decoding is completed, the original message bits '101' can be extracted by looking at the first 3 bits of the codeword.

While illustrative, this erasure example does not show the use of soft-decision decoding or soft-decision message passing, which is used in virtually all commercial LDPC decoders.

Updating node information

edit

Starting in 2010, there has also been a great deal of work spent studying the effects of alternative schedules for variable-node and constraint-node update. The original technique that was used for decoding LDPC codes was known as flooding. This type of update required that, before updating a variable node, all constraint nodes needed to be updated and vice versa. In later work by Vila Casado et al., alternative update techniques were studied, in which variable nodes are updated with the newest available check-node information.

The intuition behind these algorithms is that variable nodes whose values vary the most are the ones that need to be updated first. Highly reliable nodes, whose log-likelihood ratio (LLR) magnitude is large and does not change significantly from one update to the next, do not require updates with the same frequency as other nodes, whose sign and magnitude fluctuate more widely. These scheduling algorithms show greater speed of convergence and lower error floors than those that use flooding. These lower error floors are achieved by the ability of the Informed Dynamic Scheduling (IDS) algorithm to overcome trapping sets of near codewords.

When nonflooding scheduling algorithms are used, an alternative definition of iteration is used. For an (n, k) LDPC code of rate k/n, a full iteration occurs when n variable and n − k constraint nodes have been updated, no matter the order in which they were updated.

↑ "Turbo Codes Explained: History, Examples, and Applications - IEEE Spectrum". spectrum.ieee.org. Retrieved December 18, 2024.

↑ Gallager, R.G. (January 1962). "Low density parity check codes". IRE Trans. Inf. Theory. 8 (1): 21–28. doi:10.1109/TIT.1962.1057683. hdl:1721.1/11804/32786367-MIT. S2CID 260490814.

↑ Erico Guizzo (March 1, 2004). "CLOSING IN ON THE PERFECT CODE". IEEE Spectrum. Archived from the original on September 2, 2021. "Another advantage, perhaps the biggest of all, is that the LDPC patents have expired, so companies can use them without having to pay for intellectual-property rights."

↑ Telemetry Data Decoding, Design Handbook

↑ US 5446747 

↑ Mosheiff, J.; Resch, N.; Ron-Zewi, N.; Silas, S.; Wootters, M. (2020). "Low-Density Parity-Check Codes Achieve List-Decoding Capacity". SIAM Journal on Computing. 53 (FOCS 2020): 38–73. arXiv:1909.06430. doi:10.1137/20M1365934. S2CID 244549036.

↑ Nakamura, Kazutaka; Kabashima, Yoshiyuki; Saad, David (November 2001). "Statistical mechanics of low-density parity check error-correcting codes over Galois fields". Europhysics Letters. 56 (4): 610–616. arXiv:cond-mat/0010073. Bibcode:2001EL.....56..610N. doi:10.1209/epl/i2001-00564-y.

↑ Ruiz, Diego; Guillaud, Jérémie; Leverrier, Anthony; Mirrahimi, Mazyar; Vuillot, Christophe (January 26, 2025). "LDPC-cat codes for low-overhead quantum computing in 2D". Nature Communications. 16 (1) 1040. arXiv:2401.09541. Bibcode:2025NatCo..16.1040R. doi:10.1038/s41467-025-56298-8. ISSN 2041-1723. PMID 39863608.

↑ Eroz, Mustafa; Sun, Feng-Wen; Lee, Lin-Nan (2004). "DVB-S2 Low Density Parity Check Codes with Near Shannon Limit Performance". International Journal of Satellite Communications and Networking. 22 (3). Wiley: 269–279. doi:10.1002/sat.787.

↑ "5G Channel Coding" (PDF). Archived from the original (PDF) on December 6, 2018. Retrieved January 6, 2019.

↑ Yadav, M. K.; Parhi, K. K. (2005). "Design and implementation of LDPC codes for DVB-S2". Conference Record of the Thirty-Ninth Asilomar Conference on Signals, Systems and Computers. Pacific Grove, CA, USA: IEEE. pp. 723–728.

1 2 Andrews, Kenneth S., et al. "The development of turbo and LDPC codes for deep-space applications." Proceedings of the IEEE 95.11 (2007): 2142-2156.

1 2 Hassan, A.E.S., Dessouky, M., Abou Elazm, A. and Shokair, M., 2012. Evaluation of complexity versus performance for turbo code and LDPC under different code rates. Proc. SPACOMM, pp.93-98.

↑ Marchand, C.; Conde-Canencia, L.; Boutillon, E. (2011). "Architecture and Finite Precision Optimization for Layered LDPC Decoders". Journal of Signal Processing Systems. 65 (2): 185–197. doi:10.1007/s11265-011-0604-z.

1 2 Richardson, T. (October 2003). "Error floors of LDPC codes" (PDF). Proceedings of the Annual Allerton Conference on Communication Control and Computing. 41 (3): 1426–35. ISSN 0732-6181.

↑ Richardson, T.J.; Urbanke, R.L. (February 2001). "Efficient encoding of low-density parity-check codes". IEEE Transactions on Information Theory. 47 (2): 638–656. Bibcode:2001ITIT...47..638R. doi:10.1109/18.910579.

↑ Ahmad Darabiha, Anthony Chan Carusone, Frank R. Kschischang. "Power Reduction Techniques for LDPC Decoders"

↑ Tahir, B.; Schwarz, S.; Rupp, M. (2017). BER comparison between Convolutional, Turbo, LDPC, and Polar codes. 2017 24th International Conference on Telecommunications (ICT), Limassol, Cyprus. pp. 1–7. doi:10.1109/ICT.2017.7998249.

↑ MacKay, David J.C. (September 25, 2003). "47. Low-Density Parity-Check Codes". Information Theory, Inference, and Learning Algorithms. Cambridge University Press. pp. 557–573. ISBN 978-0-521-64298-9.