Tanner graph of a code

Let $H$ be an $r\times n$ parity check matrix for a binary linear code $C$.

A biparite graph is a graph $\Gamma= (V,E)$, where $V$ denotes the vertices and $E$ the edges, having the property that $V$ is a disjoint union of two subsets $V=V_1\cup V_2$ and each edge in $E$ connects an element in $V_1$ to an element in $V_2$.

Definition 6.3.1   The Tanner graph of $C$ is the bipartite graph with $n+r$ vertices, the $n$ message vertices are labeled by the coordinates of $C$ ($x_1$, .., $x_n$, say), and the $r$ check vertices are unlabeled but are indexed by the rows ^6.1of $H$. The $i^{th}$ check vertex is connected by an edge to the $x_j$ message vertex if and only if the $(i,j)^{th}$ entry of $H$ is non-zero (i.e., if and only if $x_j$ occurs in the $i^{th}$ parity check equation defining $C$).

Example 6.3.2   Tanner graph for the binary Hamming $(7,4,3)$-code in §3.4.2.

The parity check equations correspond to the solid black vertices, the coordinates of the codes to the labeled vertices, and the edges correspond to the terms occurring in the parity check equation.

Exercise 6.3.3   Find the Tanner graph of the binary code with parity check matrix

$$H= \left( \begin{array}{cccccc} 1 & 1 & 0 & 1 & 0 & 0 \\ 1 ... ...& 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 \end{array}\right).$$