A Tanner graph is a bipartite graph representing the local constraints that define a code (Tanner 1981).
For a binary parity check matrix 
with 
rows and 
columns, it has variable vertices 
and check vertices 
, with
 |
The check at 
requires the bits at its adjacent
variable vertices to sum to zero in the finite
field 
. Thus 
here uses rows for checks, the transpose
of the convention in which check vectors are columns.
Different parity check matrices for the same
linear code can give different Tanner graphs.
Each check can be represented by a function that is 1 when its constraint is satisfied and 0 otherwise. Their product is the characteristic function of the set of codewords, so the Tanner graph is a factor graph for these factors (Kschischang et al. 2001).
Two check vertices and two variable vertices form a graph cycle of length 4 iff
both checks involve both variables. Consequently, the
graph has no cycles of length
4 iff any two distinct rows of 
have ones in at most one common column. This restriction is
called the row-column constraint (Sadie et al. 2026). It is a condition on
the representation, not part of the definition of a low-density
parity-check code.
