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.