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

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

With high probability, random LDPC codes have constant distance [2].

Rate

Achieve capacity on the binary symmetric channel under maximum-likelihood decoding [3][1][4]. Some 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 parity-check matrix into upper triangular form [7].

Decoding

Message-passing algorithm called belief propagation (BP) [2][8].Linear programming [9].Reinforcement learning [10].

Realizations

5G NR cellular communication for the traffic channel [11].WiMAX (IEEE 802.16e) [12].Satellite transmission of digital television [13].Quantum key distribution [14].

Notes

See Kaiserslautern database [15] for explicit representatives of several classes of LDPC codes, including \(q\)-ary, WiMAX, multi-edge, and spatially-coupled.See pretty-good-codes database [16] for explicit representatives and benchmarking.See Ref. [17] for a review of LDPC codes circa 2005.Codes have been benchmarked using AFF3CT toolbox [18].See book [19] for an introduction to LDPC codes, belief-propagation decoding, and connections to statistical mechanics.

Parent

Child

Cousins

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

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: ldpc

Cite as:
“Low-density parity-check (LDPC) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/ldpc
BibTeX:
@incollection{eczoo_ldpc, title={Low-density parity-check (LDPC) code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/ldpc} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/ldpc

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/tree/main/codes/classical/q-ary_digits/ldpc/ldpc.yml.