TOPICS
Search

Low-Density Parity-Check Code


A low-density parity-check code (LDPC code) is a linear code specified by a sparse parity check matrix. In the binary case, using an m×n check matrix H, possibly with redundant rows, its codewords are

 C={x in F_2^n:Hx^T=0}.

Here F_2 is the two-element finite field, and x is a row vector. This uses the transpose of the convention in which the columns of a parity check matrix span the dual code.

Gallager (1962) introduced regular binary LDPC codes with a fixed small number j of ones in each column and k in each row. The number of nonzero entries is nj=mk, so the density is j/m=k/n. Codes with nonconstant row or column weights are called irregular. The dimension of the binary code is n-rank(H), giving the rate

 R=1-(rank(H))/n>=1-m/n.

Here rank(H) is the matrix rank over F_2. For a regular code the lower bound is 1-j/k. Equality requires the check rows to be linearly independent.

The associated Tanner graph has one variable graph vertex per column and one check graph vertex per row. Iterative decoding by the sum-product algorithm exchanges single-variable messages between these two kinds of vertices (Kschischang et al. 2001). The code and its decoding representation are distinct. The same checks can instead be arranged in a cluster graph that exchanges joint messages about several variables (Sadie et al. 2026).


See also

Error-Correcting Code, Linear Code, Parity Check Matrix, Tanner Graph

Explore with Wolfram|Alpha

References

Gallager, R. G. "Low-Density Parity-Check Codes." IRE Trans. Inform. Th. 8, 21-28, 1962. https://doi.org/10.1109/TIT.1962.1057683.Kschischang, F. R.; Frey, B. J.; and Loeliger, H.-A. "Factor Graphs and the Sum-Product Algorithm." IEEE Trans. Inform. Th. 47, 498-519, 2001. https://doi.org/10.1109/18.910572.Sadie, K. M.; du Toit, J.; and du Preez, J. A. "On the Role of Graph Structure on LDPC Decoding Fidelity." IEEE Access 14, 172385-172408, 2026. https://doi.org/10.1109/ACCESS.2026.3747195.

Cite this as:

Weisstein, Eric W. "Low-Density Parity-Check Code." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Low-DensityParity-CheckCode.html

Subject classifications