Low-density parity-check (LDPC) code

Low-density parity-check (LDPC) code[1,2]

Also known as Sparse graph code.

Description

A binary linear code with a sparse parity-check matrix. Alternatively, a member of an infinite family of \([n,k,d]\) codes for which the number of nonzero entries in each row and column of the parity-check matrix are both bounded above by a constant as \(n\to\infty\).

An LDPC code is \((j,k)\)-regular if the parity-check matrix has a fixed number of \(j\) nonzero entries in each row and \(k\) entries in each column; otherwise, the LDPC code is irregular. Irregular LDPC codes are characterized by the fractions \(v_j\) of columns of weight \(j\) as well as likewise fractions \(h_j\) for rows of weight \(j\); these are collectively called the degree distribution.

A parity check is performed by taking the inner product of a row of the parity-check matrix with a codeword that has been affected by a noise channel. A parity check yields either zero (no error) or one (error).

In alternative conventions (not used here), LDPC codes are referred to as simple LDPC codes, as opposed to generalized LDPC codes, alternatively named as Tanner codes.

Rate

Some LDPC codes achieve the Shannon capacity of the binary symmetric channel under maximum-likelihood decoding [1,3,4]. Other LDPC codes achieve capacity for smaller block lengths under belief-propagation decoding [5]. Random LDPC codes achieve list-decoding capacity [6].

Encoding

Almost linear-time encoder based on transforming the parity-check matrix into upper triangular form [7].

Decoding

Message-passing algorithm called belief propagation (BP) [2,8,9] (see also [10–12]).Soft-decision Sum-Product Algorithm (SPA) [2,10,13] and its simplification the Min-Sum Algorithm (MSA) [14].Linear programming [15–17].Iterative LDPC decoders can get stuck at stopping sets of their Tanner graphs [18], with decoder performance improving with the size of the smallest stopping set; see [19; Sec. 21.3.1] for more details. The smallest stopping set size can reach the minimum distance of the code [20].Ensembles of random LDPC codes under iterative decoders are subject to the concentration theorem [10,21]; see [19; Thm. 21.7.1] for the case of the BEC.Reinforcement learning [22].Quantum-enhanced BP decoding [23].

Notes

The potential of LDPC codes was noted by Margulis [24], but realized by the broader community [3,25] much later after their discovery by Gallager [1,2].See books [26–28] and reviews [29,30] for introductions to LDPC codes, belief-propagation decoding, and connections to statistical mechanics. Other introductory references include Refs. [31–34] as well as a review of LDPC codes circa 2005 [35].See Kaiserslautern database [36] for explicit representatives of several classes of LDPC codes, including \(q\)-ary, WiMAX, multi-edge, and spatially-coupled.See pretty-good-codes database [37] for explicit representatives and benchmarking.See Encyclopedia of sparse graph codes for explicit representatives [38]LDPC codes have been considered for quantum key distribution [39].Codes have been benchmarked using AFF3CT toolbox [40].

Parents

Children

Cousins

Tensor-product code — Tensor products of random LDPC codes are robustly testable [41,42].
Low-density generator-matrix (LDGM) code — The dual of an LDPC code has a sparse generator matrix and is called an LDGM code.
Random code — LDPC codes are often constructed non-determinisitically.
Hamiltonian-based code — There are relations between LDPC codes and statistical mechanical models of spin glasses [26–28,43].
Tornado code — Tornado codes are similar to LDPC codes, but they use a highly irregular weight distribution for the underlying graphs [44].
Low-rank parity-check (LRPC) code — LRPC codes are rank-metric analogues of LDPC codes [45].
DNA storage code — LDPC codes are potentially relevant for DNA storage [46].
LDPC convolutional code (LDPC-CC) — LDPC-CCs are convolutional analogues of LDPC codes.
Lechner-Hauke-Zoller (LHZ) code — The LHZ code is an LDPC c-q code designed to convert the long-range interactions of a quantum annealer into local constraints.
Concatenated cat code — Cat codes have been concatenated with LDPC codes (treated as qubit stabilizer codes) [47].
Quantum LDPC (QLDPC) code
Spacetime circuit code — There is an equivalence between Clifford circuits and LDPC codes with bit-check symmetry [48].
EA QLDPC code — There exist necessary and sufficient conditions for an EA QLDPC code consuming \(e=1\) ebit that is obtainable from a pair of LDPC codes [49].

References

[1]: R. Gallager, “Low-density parity-check codes”, IEEE Transactions on Information Theory 8, 21 (1962) DOI
[2]: R. Gallager, Low-density parity check codes. 1963. PhD thesis, MIT Cambridge, MA.
[3]: D. J. C. MacKay, “Good error-correcting codes based on very sparse matrices”, IEEE Transactions on Information Theory 45, 399 (1999) DOI
[4]: V. Guruswami, “Iterative Decoding of Low-Density Parity Check Codes (A Survey)”, (2006) arXiv:cs/0610022
[5]: S. Kudekar, T. Richardson, and R. Urbanke, “Spatially Coupled Ensembles Universally Achieve Capacity under Belief Propagation”, (2012) arXiv:1201.2999
[6]: J. Mosheiff, N. Resch, N. Ron-Zewi, S. Silas, and M. Wootters, “Low-Density Parity-Check Codes Achieve List-Decoding Capacity”, SIAM Journal on Computing FOCS20 (2021) arXiv:1909.06430 DOI
[7]: T. J. Richardson and R. L. Urbanke, “Efficient encoding of low-density parity-check codes”, IEEE Transactions on Information Theory 47, 638 (2001) DOI
[8]: Pearl, J. (2022). Reverend Bayes on inference engines: A distributed hierarchical approach. In Probabilistic and Causal Inference: The Works of Judea Pearl (pp. 129-138).
[9]: “Probabilistic Reasoning in Intelligent Systems”, (1988) DOI
[10]: T. J. Richardson and R. L. Urbanke, “The capacity of low-density parity-check codes under message-passing decoding”, IEEE Transactions on Information Theory 47, 599 (2001) DOI
[11]: S. Lin and D. J. Costello, Error Control Coding, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2004.
[12]: K. Shimizu, T. Ishikawa, N. Togawa, T. Ikenaga, and S. Goto, “A parallel LSI architecture for LDPC decoder improving message-passing schedule”, 2006 IEEE International Symposium on Circuits and Systems DOI
[13]: F. R. Kschischang, B. J. Frey, and H.-A. Loeliger, “Factor graphs and the sum-product algorithm”, IEEE Transactions on Information Theory 47, 498 (2001) DOI
[14]: J. Chen, A. Dholakia, E. Eleftheriou, M. P. C. Fossorier, and X.-Y. Hu, “Reduced-Complexity Decoding of LDPC Codes”, IEEE Transactions on Communications 53, 1288 (2005) DOI
[15]: J. Feldman. Decoding Error-Correcting Codes via Linear Programming. PhD thesis, Massachusetts Institute of Technology, 2003.
[16]: J. Feldman, M. J. Wainwright, and D. R. Karger, “Using Linear Programming to Decode Binary Linear Codes”, IEEE Transactions on Information Theory 51, 954 (2005) DOI
[17]: J. Feldman, “LP Decoding”, Encyclopedia of Algorithms 1177 (2016) DOI
[18]: Changyan Di, D. Proietti, I. E. Telatar, T. J. Richardson, and R. L. Urbanke, “Finite-length analysis of low-density parity-check codes on the binary erasure channel”, IEEE Transactions on Information Theory 48, 1570 (2002) DOI
[19]: C. A. Kelley, "Codes over Graphs." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[20]: M. Schwartz and A. Vardy, “On the stopping distance and the stopping redundancy of codes”, IEEE Transactions on Information Theory 52, 922 (2006) DOI
[21]: T. J. Richardson, M. A. Shokrollahi, and R. L. Urbanke, “Design of capacity-approaching irregular low-density parity-check codes”, IEEE Transactions on Information Theory 47, 619 (2001) DOI
[22]: S. Habib, A. Beemer, and J. Kliewer, “RELDEC: Reinforcement Learning-Based Decoding of Moderate Length LDPC Codes”, (2023) arXiv:2112.13934
[23]: S. M. Perez-Garcia and A. Montanaro, “Quantum-enhanced belief propagation for LDPC decoding”, (2024) arXiv:2412.08596
[24]: G. A. Margulis, “Explicit constructions of graphs without short cycles and low density codes”, Combinatorica 2, 71 (1982) DOI
[25]: D. J. C. MacKay and R. M. Neal, “Near Shannon limit performance of low density parity check codes”, Electronics Letters 33, 457 (1997) DOI
[26]: M. Mézard and A. Montanari, “Information, Physics, and Computation”, (2009) DOI
[27]: H. Nishimori, “Statistical Physics of Spin Glasses and Information Processing”, (2001) DOI
[28]: I. F. Blake, Essays on Coding Theory (Cambridge University Press, 2024) DOI
[29]: Y. Kabashima and D. Saad, “Statistical mechanics of low-density parity-check codes”, Journal of Physics A: Mathematical and General 37, R1 (2004) DOI
[30]: A. Montanari and R. Urbanke, “Course 2 Modern coding theory: The statistical mechanics and computer science point of view”, Complex Systems 67 (2007) DOI
[31]: T. Richardson and R. Urbanke, “The renaissance of gallager’s low-density parity-check codes”, IEEE Communications Magazine 41, 126 (2003) DOI
[32]: Johnson, Sarah J. "Introducing low-density parity-check codes." University of Newcastle, Australia 1 (2006): 2006.
[33]: David J. C. MacKay. Information Theory, Inference and Learning Algorithms. Cambridge university press, 2003.
[34]: B. Vasic and E. M. Kurtas, editors , Coding and Signal Processing for Magnetic Recording Systems (CRC Press, 2004) DOI
[35]: A. Shokrollahi, “LDPC Codes: An Introduction”, Coding, Cryptography and Combinatorics 85 (2004) DOI
[36]: Michael Helmling, Stefan Scholl, Florian Gensheimer, Tobias Dietz, Kira Kraft, Stefan Ruzika, and Norbert Wehn. Database of Channel Codes and ML Simulation Results. URL, 2022.
[37]: G. Liva, F. Steiner. “pretty-good-codes.org: Online library of good channel codes”, URL: http://pretty-good-codes.org/
[38]: MacKay, David JC. "Encyclopedia of sparse graph codes." (2005).
[39]: N. Borisov, I. Petrov, and A. Tayduganov, “Asymmetric Adaptive LDPC-Based Information Reconciliation for Industrial Quantum Key Distribution”, Entropy 25, 31 (2022) arXiv:2212.01121 DOI
[40]: A. Cassagne et al., “AFF3CT: A Fast Forward Error Correction Toolbox!”, SoftwareX 10, 100345 (2019) DOI
[41]: I. Dinur, M. Sudan, and A. Wigderson, “Robust Local Testability of Tensor Products of LDPC Codes”, Lecture Notes in Computer Science 304 (2006) DOI
[42]: E. Ben-Sasson and M. Viderman, “Tensor Products of Weakly Smooth Codes Are Robust”, Lecture Notes in Computer Science 290 (2008) DOI
[43]: Franz, M. Leone, A. Montanari, and F. Ricci-Tersenghi, “Dynamic phase transition for decoding algorithms”, Physical Review E 66, (2002) arXiv:cond-mat/0205051 DOI
[44]: A. Shokrollahi, “Raptor codes”, IEEE Transactions on Information Theory 52, 2551 (2006) DOI
[45]: Gaborit, P., Murat, G., Ruatta, O., & Zemor, G. (2013, April). Low rank parity check codes and their application to cryptography. In Proceedings of the Workshop on Coding and Cryptography WCC (Vol. 2013).
[46]: X. Lu, J. Jeong, J.-W. Kim, J.-S. No, H. Park, A. No, and S. Kim, “Error Rate-Based Log-Likelihood Ratio Processing for Low-Density Parity-Check Codes in DNA Storage”, IEEE Access 8, 162892 (2020) DOI
[47]: D. Ruiz, J. Guillaud, A. Leverrier, M. Mirrahimi, and C. Vuillot, “LDPC-cat codes for low-overhead quantum computing in 2D”, (2024) arXiv:2401.09541
[48]: Y. Li, “Low-density parity-check representation of fault-tolerant quantum circuits”, (2024) arXiv:2403.10268
[49]: Y. Fujiwara and V. D. Tonchev, “A Characterization of Entanglement-Assisted Quantum Low-Density Parity-Check Codes”, IEEE Transactions on Information Theory 59, 3347 (2013) arXiv:1108.0679 DOI

Page edit log

Victor V. Albert (2022-08-17) — most recent
Victor V. Albert (2022-04-25)
Armin Gerami (2022-04-23)

Cite as:

“Low-density parity-check (LDPC) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/ldpc

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/bits/tanner/ldpc.yml.