# Section8.3Parity-Check and Generator Matrices¶ permalink

We need to find a systematic way of generating linear codes as well as fast methods of decoding. By examining the properties of a matrix $H$ and by carefully choosing $H$, it is possible to develop very efficient methods of encoding and decoding messages. To this end, we will introduce standard generator and canonical parity-check matrices.

Suppose that $H$ is an $m \times n$ matrix with entries in ${\mathbb Z}_2$ and $n \gt m$. If the last $m$ columns of the matrix form the $m \times m$ identity matrix, $I_m$, then the matrix is a canonical parity-check matrix. More specifically, $H= (A \mid I_m)$, where $A$ is the $m \times (n-m)$ matrix \begin{equation*}\begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1,n-m} \\ a_{21} & a_{22} & \cdots & a_{2,n-m} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{m,n-m} \end{pmatrix}\end{equation*} and $I_m$ is the $m \times m$ identity matrix \begin{equation*}\begin{pmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{pmatrix}.\end{equation*} With each canonical parity-check matrix we can associate an $n \times (n-m)$ standard generator matrix \begin{equation*}G = \left( \frac{I_{n-m}}{A} \right).\end{equation*} Our goal will be to show that an $\mathbf x$ satisfying $G {\mathbf x} = {\mathbf y}$ exists if and only if $H{\mathbf y} = {\mathbf 0}$. Given a message block ${\mathbf x}$ to be encoded, the matrix $G$ will allow us to quickly encode it into a linear codeword ${\mathbf y}$.

##### Example8.23

Suppose that we have the following eight words to be encoded: \begin{equation*}(000), (001), (010), \ldots, (111).\end{equation*} For \begin{equation*}A = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix},\end{equation*} the associated standard generator and canonical parity-check matrices are \begin{equation*}G= \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix}\end{equation*} and \begin{equation*}H = \begin{pmatrix} 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 \end{pmatrix},\end{equation*} respectively.

Observe that the rows in $H$ represent the parity checks on certain bit positions in a 6-tuple. The 1s in the identity matrix serve as parity checks for the 1s in the same row. If ${\mathbf x} = (x_1, x_2, x_3, x_4, x_5, x_6)$, then \begin{equation*}{\mathbf 0} = H{\mathbf x} = \begin{pmatrix} x_2 + x_3 + x_4 \\ x_1 + x_2 + x_5\\ x_1 + x_3 + x_6 \end{pmatrix},\end{equation*} which yields a system of equations: \begin{align*} x_2 + x_3 + x_4 & = 0\\ x_1 + x_2 + x_5 & = 0\\ x_1 + x_3 + x_6 & = 0. \end{align*} Here $x_4$ serves as a check bit for $x_2$ and $x_3$; $x_5$ is a check bit for $x_1$ and $x_2$; and $x_6$ is a check bit for $x_1$ and $x_3$. The identity matrix keeps $x_4$, $x_5$, and $x_6$ from having to check on each other. Hence, $x_1$, $x_2$, and $x_3$ can be arbitrary but $x_4$, $x_5$, and $x_6$ must be chosen to ensure parity. The null space of $H$ is easily computed to be \begin{equation*}\begin{array}{cccc} (000000) & (001101) & (010110) & (011011) \\ (100011) & (101110) & (110101) & (111000). \end{array}\end{equation*} An even easier way to compute the null space is with the generator matrix $G$ (Table 8.24).

We leave the proof of this theorem as an exercise. In light of the theorem, the first $n - m$ bits in ${\mathbf x}$ are called information bits and the last $m$ bits are called check bits. In Example 8.23, the first three bits are the information bits and the last three are the check bits.

##### Proof

Before we can prove the relationship between canonical parity-check matrices and standard generating matrices, we need to prove a lemma.

##### Proof

It would be helpful if we could compute the minimum distance of a linear code directly from its matrix $H$ in order to determine the error-detecting and error-correcting capabilities of the code. Suppose that \begin{align*} {\mathbf e}_1 & = (100 \cdots 00)^{\rm t}\\ {\mathbf e}_2 & = (010 \cdots 00)^{\rm t}\\ & \vdots\\ {\mathbf e}_n & = (000 \cdots 01)^{\rm t} \end{align*} are the $n$-tuples in ${\mathbb Z}_2^n$ of weight 1. For an $m \times n$ binary matrix $H$, $H{\mathbf e}_i$ is exactly the $i$th column of the matrix $H$.

##### Example8.29

Observe that \begin{equation*}\begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix}.\end{equation*}

We state this result in the following proposition and leave the proof as an exercise.

##### Example8.32

If we consider the matrices \begin{equation*}H_1 = \begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \end{pmatrix}\end{equation*} and \begin{equation*}H_2 = \begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 \end{pmatrix},\end{equation*} then the null space of $H_1$ is a single error-detecting code and the null space of $H_2$ is not.

We can even do better than Theorem 8.31. This theorem gives us conditions on a matrix $H$ that tell us when the minimum weight of the code formed by the null space of $H$ is 2. We can also determine when the minimum distance of a linear code is 3 by examining the corresponding matrix.

##### Example8.33

If we let \begin{equation*}H = \begin{pmatrix} 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 \end{pmatrix}\end{equation*} and want to determine whether or not $H$ is the canonical parity-check matrix for an error-correcting code, it is necessary to make certain that ${\rm Null}(H)$ does not contain any 4-tuples of weight 2. That is, $(1100)$, $(1010)$, $(1001)$, $(0110)$, $(0101)$, and $(0011)$ must not be in ${\rm Null}(H)$. The next theorem states that we can indeed determine that the code generated by $H$ is error-correcting by examining the columns of $H$. Notice in this example that not only does $H$ have no zero columns, but also that no two columns are the same.

##### Proof

Suppose now that we have a canonical parity-check matrix $H$ with three rows. Then we might ask how many more columns we can add to the matrix and still have a null space that is a single error-detecting and single error-correcting code. Since each column has three entries, there are $2^3 = 8$ possible distinct columns. We cannot add the columns \begin{equation*}\begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}, \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix}.\end{equation*} So we can add as many as four columns and still maintain a minimum distance of 3.

In general, if $H$ is an $m \times n$ canonical parity-check matrix, then there are $n-m$ information positions in each codeword. Each column has $m$ bits, so there are $2^m$ possible distinct columns. It is necessary that the columns ${\mathbf 0}, {\mathbf e}_1, \ldots, {\mathbf e}_m$ be excluded, leaving $2^m - (1 + m)$ remaining columns for information if we are still to maintain the ability not only to detect but also to correct single errors.