A parity check matrix of a linear code
of length
and dimension
over a field
is an
matrix whose columns
form a basis for the dual
code
. A row vector
is a codeword
of
iff
. Equivalently, the columns
of
form a basis for the null
space of a generator matrix
, and
is a generator matrix
for the dual code. A convention using the transpose
of
instead writes the check as
.
In the row-check convention, redundant rows may be retained without changing the code, provided their row space remains the dual code. A Tanner graph represents the incidence between coordinates and parity-check equations (Tanner 1981). A low-density parity-check code has a sparse check matrix (Gallager 1962).