A Tanner graph for a binary (n, k, d ) code
is a
bipartite graph whose adjacency matrix is
the paritycheck matrix of
. The left part of
the graph consists of site nodes which correspond
to symbol bits of the code, and the right part of the
graph consists of check nodes which correspond
to parity checks in the graph.
Thus the number of edges in any Tanner graph for a linear code
of length n is O(n^{2}), so that the graph's complexity grows quadratically with
length, regardless of the code.
Figure 1.5 gives a paritycheck matrix and corresponding
Tanner graph for a sample binary, linear code.
Figure 1.5:
H is the paritycheck matrix for a (5, 2, 3) binary,
linear code. The accompanying figure is its Tanner graph, in which
the left nodes correspond to symbol bits and the right nodes correspond to
paritychecks.

A generalized version of the Viterbi algorithm, known as the minsum
algorithm [66], might allow for decoding with Tanner graphs. This is an
iterative algorithm which tries to spread biterror information throughout
the Tanner graph. Thus, check nodes repeatedly minimize error among legal
site configurations neighboring them, and site nodes repeatedly sum errors from
their neighbors. This iterative algorithm
provenly converges [1,55,66] to a maximumlikelihood decision for
cyclefree Tanner graphs,
although it does not necessarily converge or decode correctly
if the graph has a cycle.
Thus, if we can represent
by a Tanner graph without cycles, then maximumlikelihood decoding
of
can be achieved in time O(n^{2}) using the minsum algorithm.
http://people.bu.edu/trachten