Low-density parity-check code

In information theory, a low-density parity-check (LDPC) code is a linear error correcting code, a method of transmitting a message over a noisy transmission channel.[1][2] An LDPC code is constructed using a sparse Tanner graph (subclass of the bipartite graph).[3] LDPC codes are capacity-approaching codes, which means that practical constructions exist that allow the noise threshold to be set very close to the theoretical maximum (the Shannon limit) for a symmetric memoryless channel. The noise threshold defines an upper bound for the channel noise, up to which the probability of lost information can be made as small as desired. Using iterative belief propagation techniques, LDPC codes can be decoded in time linear in their block length.

LDPC codes are also known as Gallager codes, in honor of Robert G. Gallager, who developed the LDPC concept in his doctoral dissertation at the Massachusetts Institute of Technology in 1960.[4][5] However, LDPC codes require computationally expensive iterative decoding, so they went unused for decades. In 1993 the newly invented turbo codes demonstrated that codes with iterative decoding could far outperform other codes used at that time, but turbo codes were patented and required a fee for use. This raised renewed interest in LDPC codes, which were shown to have similar performance, but were much older and patent-free.[6] Now that the fundamental patent for turbo codes has expired (on August 29, 2013),[7][8] LDPC codes are still used for their technical merits.

LDPC codes have been shown to have ideal combinatorial properties. In his dissertation, Gallager showed that LDPC codes achieve the Gilbert–Varshamov bound for linear codes over binary fields with high probability. In 2020 it was shown that Gallager's LDPC codes achieve list decoding capacity and also achieve the Gilbert–Varshamov bound for linear codes over general fields.[9]

  1. ^ MacKay, David J. (2003). Information theory, Inference and Learning Algorithms. Cambridge University Press. ISBN 0-521-64298-1.
  2. ^ Moon, Todd K. (2005). Error Correction Coding, Mathematical Methods and Algorithms. Wiley. ISBN 0-471-64800-0. (Includes code)
  3. ^ Amin Shokrollahi, LDPC Codes: An Introduction (PDF), archived from the original (PDF) on May 17, 2017
  4. ^ Hardesty, L. (January 21, 2010). "Explained: Gallager codes". MIT News. Retrieved August 7, 2013.
  5. ^ 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.
  6. ^ 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."
  7. ^ US 5446747 
  8. ^ Mackenzie, D. (July 9, 2005). "Communication speed nears terminal velocity". New Scientist.
  9. ^ 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 (FOCS 2020): 38–73. arXiv:1909.06430. doi:10.1137/20M1365934. S2CID 244549036.