Graph-theoretic definition

Let $\Gamma$ be a bipartite graph whose vertices $V$ partition into two subsets $V_m$ and $V_c$. The vertices in $V_m$ are called message nodes, $V_m=\{v_1,...,v_n\}$. The vertices in $V_c$ are called check nodes, $V_c=\{v'_1,...,v'_r\}$.

$$\begin{array}{ccccccccc} & V_m& & & & & V_c\\ &&&&&& \\... ...\bullet &v'_r\\ \bullet & v_{n} & &\ & & & \\ \end{array}$$

Suppose that each of the message nodes have degree $\rho\geq 1$ and each of the check nodes have degree $\gamma\geq 1$. For $v\in V_m$, let $N(v)$ denote all the neighbors $v'\in V_c$ of $v$. Define $x=(x_1,...,x_n)\in \mathbb{F}_2^n$ to be a codeword if and only if, for all $v\in V_c$, we have

$$\sum_{v_i\in N(v)} x_i=0.$$

(Equivalently, if $H$ is the incidence matrix of $\Gamma$ whose rows are indexed by the check nodes and whose columns are indexed by the message nodes, then $x$ is a codeword if and only if $Hx=0$.)