Description
Also known as Gallager codes. A \(q\)-ary linear code with a sparse parity-check matrix. More precisely, 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 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. The dual of an LDPC code has a sparse generator matrix and is called an LDGM code.
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) for binary codes, while yielding zero (no error) or a nonzero field element (error) for \(q\)-ary codes. Despite the fact that there is more than one nonzero outcome, \(q\)-ary linear codes with sparse parity-check matrices are also called LDPC codes.
Protection
Rate
Encoding
Decoding
Realizations
Notes
Parent
Child
Cousins
- Low-density generator-matrix (LDGM) code — LDPC and LDGM codes are dual to each other.
- Tensor-product code — Tensor products of random LDPC codes are robustly testable [20][21].
- Tornado code — Tornado codes are similar to LDPC codes, but they use a highly irregular weight distribution for the underlying graphs [22].
- Low-rank parity-check (LRPC) code — LRPC codes are rank-metric analogues of LDPC codes [23].
- Quantum low-density parity-check (QLDPC) code
References
- [1]
- R. Gallager, “Low-density parity-check codes”, IEEE Transactions on Information Theory 8, 21 (1962) DOI
- [2]
- R. Gallagher, 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 et al., “LDPC Codes Achieve List Decoding Capacity”, (2021) arXiv:1909.06430
- [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]
- S. Lin and D. J. Costello, Error Control Coding, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2004.
- [9]
- J. Feldman, “LP Decoding”, Encyclopedia of Algorithms 1177 (2016) DOI
- [10]
- S. Habib, A. Beemer, and J. Kliewer, “RELDEC: Reinforcement Learning-Based Decoding of Moderate Length LDPC Codes”, (2021) arXiv:2112.13934
- [11]
- M. V. Patil, S. Pawar, and Z. Saquib, “Coding Techniques for 5G Networks: A Review”, 2020 3rd International Conference on Communication System, Computing and IT Applications (CSCITA) (2020) DOI
- [12]
- LDPC coding for OFDMA PHY. 802.16REVe Sponsor Ballot Recirculation comment, July 2004. IEEE C802.16e04/141r2
- [13]
- R. Purnamasari, H. Wijanto, and I. Hidayat, “Design and implementation of LDPC(Low Density Parity Check) coding technique on FPGA (Field Programmable Gate Array) for DVB-S2 (Digital Video Broadcasting-Satellite)”, 2014 IEEE International Conference on Aerospace Electronics and Remote Sensing Technology (2014) DOI
- [14]
- 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
- [15]
- 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.
- [16]
- G. Liva, F. Steiner. “pretty-good-codes.org: Online library of good channel codes”, URL: http://pretty-good-codes.org/
- [17]
- A. Shokrollahi, “LDPC Codes: An Introduction”, Coding, Cryptography and Combinatorics 85 (2004) DOI
- [18]
- A. Cassagne et al., “AFF3CT: A Fast Forward Error Correction Toolbox!”, SoftwareX 10, 100345 (2019) DOI
- [19]
- M. Mézard and A. Montanari, Information, Physics, and Computation (Oxford University PressOxford, 2009) DOI
- [20]
- I. Dinur, M. Sudan, and A. Wigderson, “Robust Local Testability of Tensor Products of LDPC Codes”, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques 304 (2006) DOI
- [21]
- E. Ben-Sasson and M. Viderman, “Tensor Products of Weakly Smooth Codes Are Robust”, Lecture Notes in Computer Science 290 (2008) DOI
- [22]
- A. Shokrollahi, “Raptor codes”, IEEE Transactions on Information Theory 52, 2551 (2006) DOI
- [23]
- 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).
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