Sparse check matrix definition

Let $H$ is an $r\times n$ matrix over $\mathbb{F}_2$ with the following properties:

• each row has exactly $\rho$ $1$'s,

• each column has exactly $\gamma$ $1$'s,

• the number of $1$'s in common between any two columns, denoted, $\delta$, satisfies $\delta\leq 1$,

• $\rho/n$ and $\gamma/r$ are ``small''.

The linear binary code $C$ is defined by

$$C=\{c\in \mathbb{F}_2^n\ \vert\ Hc=0\}.$$

In other words, $H$ is the parity check matrix for $C$. Since $H$ is sparse, $C$ is called a low density parity check code or a LDPC code.

More generally, such codes are called regular LDPC codes. We shall not discuss ``irregular LDPC codes'' here, which are defined by somewhat weaker conditions.