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

Description

Also known as Gallager codes. Binary or \(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.

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].

Realizations

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

Notes

See Kaiserslautern database [13] for explicit representatives of several classes of LDPC codes, including \(q\)-ary, WiMAX, multi-edge, and spatially-coupled.See pretty-good-codes database [14] for explicit representatives and benchmarking.See Ref. [15] for a review of LDPC codes circa 2005.Codes have been benchmarked using AFF3CT toolbox [16].

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]
Venkatesan Guruswami, “Iterative Decoding of Low-Density Parity Check Codes (A Survey)”. cs/0610022
[5]
Shrinivas Kudekar, Tom Richardson, and Ruediger Urbanke, “Spatially Coupled Ensembles Universally Achieve Capacity under Belief Propagation”. 1201.2999
[6]
Jonathan Mosheiff et al., “LDPC Codes Achieve List Decoding Capacity”. 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]
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
[11]
LDPC coding for OFDMA PHY. 802.16REVe Sponsor Ballot Recirculation comment, July 2004. IEEE C802.16e04/141r2
[12]
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
[13]
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.
[14]
G. Liva, F. Steiner. “pretty-good-codes.org: Online library of good channel codes”, URL: http://pretty-good-codes.org/
[15]
A. Shokrollahi, “LDPC Codes: An Introduction”, Coding, Cryptography and Combinatorics 85 (2004). DOI
[16]
A. Cassagne et al., “AFF3CT: A Fast Forward Error Correction Toolbox!”, SoftwareX 10, 100345 (2019). DOI
[17]
A. Shokrollahi, “Raptor codes”, IEEE Transactions on Information Theory 52, 2551 (2006). DOI

Zoo code information

Internal code ID: ldpc

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 |  | 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/properties/ldpc.yml.