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 check matrix
, possibly with redundant rows, its codewords
are
Here
is the two-element finite field, and
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
of ones in each column and
in each row. The number of nonzero
entries is
, so the density is
. Codes with nonconstant row or column weights
are called irregular. The dimension of the binary
code is
, giving the rate
Here
is the matrix rank over
. For a regular code the lower
bound is
. 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).