Section8.3Parity-Check and Generator Matrices

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\text{,}$$ 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\text{.}$$ If the last $$m$$ columns of the matrix form the $$m \times m$$ identity matrix, $$I_m\text{,}$$ then the matrix is a canonical parity-check matrix. More specifically, $$H= (A \mid I_m)\text{,}$$ 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}\text{.} \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)\text{.} \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}\text{.}$$ 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}\text{.}$$

Example8.23.

Suppose that we have the following eight words to be encoded:

\begin{equation*} (000), (001), (010), \ldots, (111)\text{.} \end{equation*}

For

\begin{equation*} A = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix}\text{,} \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}\text{,} \end{equation*}

respectively.

Observe that the rows in $$H$$ represent the parity checks on certain bit positions in a $$6$$-tuple. The $$1$$s in the identity matrix serve as parity checks for the $$1$$s in the same row. If $${\mathbf x} = (x_1, x_2, x_3, x_4, x_5, x_6)\text{,}$$ 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}\text{,} \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\text{.} \end{align*}

Here $$x_4$$ serves as a check bit for $$x_2$$ and $$x_3\text{;}$$ $$x_5$$ is a check bit for $$x_1$$ and $$x_2\text{;}$$ and $$x_6$$ is a check bit for $$x_1$$ and $$x_3\text{.}$$ The identity matrix keeps $$x_4\text{,}$$ $$x_5\text{,}$$ and $$x_6$$ from having to check on each other. Hence, $$x_1\text{,}$$ $$x_2\text{,}$$ and $$x_3$$ can be arbitrary but $$x_4\text{,}$$ $$x_5\text{,}$$ 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.

Let $$G {\mathbf x}_1 = {\mathbf y}_1$$ and $$G {\mathbf x}_2 ={\mathbf y}_2$$ be two codewords. Then $${\mathbf y}_1 + {\mathbf y}_2$$ is in $$C$$ since

\begin{equation*} G( {\mathbf x}_1 + {\mathbf x}_2) = G {\mathbf x}_1 + G {\mathbf x}_2 = {\mathbf y}_1 + {\mathbf y}_2\text{.} \end{equation*}

We must also show that two message blocks cannot be encoded into the same codeword. That is, we must show that if $$G {\mathbf x} = G {\mathbf y}\text{,}$$ then $${\mathbf x} = {\mathbf y}\text{.}$$ Suppose that $$G {\mathbf x} = G {\mathbf y}\text{.}$$ Then

\begin{equation*} G {\mathbf x} - G {\mathbf y} = G( {\mathbf x} - {\mathbf y}) = {\mathbf 0}\text{.} \end{equation*}

However, the first $$k$$ coordinates in $$G( {\mathbf x} - {\mathbf y})$$ are exactly $$x_1 -y_1, \ldots, x_k - y_k\text{,}$$ since they are determined by the identity matrix, $$I_k\text{,}$$ part of $$G\text{.}$$ Hence, $$G( {\mathbf x} - {\mathbf y}) = {\mathbf 0}$$ exactly when $${\mathbf x} = {\mathbf y}\text{.}$$

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

Let $$C = HG\text{.}$$ The $$ij$$th entry in $$C$$ is

\begin{align*} c_{ij} & = \sum_{k=1}^n h_{ik} g_{kj}\\ & = \sum_{k=1}^{n-m} h_{ik} g_{kj} + \sum_{k=n-m+1}^n h_{ik} g_{kj}\\ & = \sum_{k=1}^{n-m} a_{ik} \delta_{kj} + \sum_{k=n-m+1}^n \delta_{i-(m-n),k} a_{kj}\\ & = a_{ij} + a_{ij}\\ & = 0\text{,} \end{align*}

where

\begin{equation*} \delta_{ij} = \begin{cases} 1 & i = j \\ 0 & i \neq j \end{cases} \end{equation*}

is the Kronecker delta.

First suppose that $${\mathbf y} \in C\text{.}$$ Then $$G {\mathbf x} = {\mathbf y}$$ for some $${\mathbf x} \in {\mathbb Z}_2^m\text{.}$$ By Lemma 8.27, $$H {\mathbf y} = HG {\mathbf x} = {\mathbf 0}\text{.}$$

Conversely, suppose that $${\mathbf y} = (y_1, \ldots, y_n)^\transpose$$ is in the null space of $$H\text{.}$$ We need to find an $${\mathbf x}$$ in $${\mathbb Z}_2^{n-m}$$ such that $$G {\mathbf x}^\transpose = {\mathbf y}\text{.}$$ Since $$H {\mathbf y} = {\mathbf 0}\text{,}$$ the following set of equations must be satisfied:

\begin{align*} a_{11} y_1 + a_{12} y_2 + \cdots + a_{1, n-m} y_{n-m} + y_{n-m+1} & = 0\\ a_{21} y_1 + a_{22} y_2 + \cdots + a_{2, n-m} y_{n-m} + y_{n-m+2} & = 0\\ & \vdots\\ a_{m1} y_1 + a_{m2} y_2 + \cdots + a_{m, n-m} y_{n-m} + y_{n-m+m} & = 0\text{.} \end{align*}

Equivalently, $$y_{n-m+1}, \ldots, y_n$$ are determined by $$y_1, \ldots, y_{n-m}\text{:}$$

\begin{align*} y_{n-m+1} & = a_{11} y_1 + a_{12} y_2 + \cdots + a_{1, n-m} y_{n-m}\\ y_{n-m+2} & = a_{21} y_1 + a_{22} y_2 + \cdots + a_{2, n-m} y_{n-m}\\ & \vdots\\ y_{n} & = a_{m1} y_1 + a_{m2} y_2 + \cdots + a_{m, n-m} y_{n-m}\text{.} \end{align*}

Consequently, we can let $$x_i = y_i$$ for $$i= 1, \ldots, n - m\text{.}$$

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)^\transpose\\ {\mathbf e}_2 & = (010 \cdots 00)^\transpose\\ & \vdots\\ {\mathbf e}_n & = (000 \cdots 01)^\transpose \end{align*}

are the $$n$$-tuples in $${\mathbb Z}_2^n$$ of weight $$1\text{.}$$ For an $$m \times n$$ binary matrix $$H\text{,}$$ $$H{\mathbf e}_i$$ is exactly the $$i$$th column of the matrix $$H\text{.}$$

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}\text{.} \end{equation*}

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

Suppose that $$\Null(H)$$ is a single error-detecting code. Then the minimum distance of the code must be at least $$2\text{.}$$ Since the null space is a group code, it is sufficient to require that the code contain no codewords of less than weight $$2$$ other than the zero codeword. That is, $${\mathbf e}_i$$ must not be a codeword for $$i = 1, \ldots, n\text{.}$$ Since $$H{\mathbf e}_i$$ is the $$i$$th column of $$H\text{,}$$ the only way in which $${\mathbf e}_i$$ could be in the null space of $$H$$ would be if the $$i$$th column were all zeros, which is impossible; hence, the code must have the capability to detect at least single errors.

Conversely, suppose that no column of $$H$$ is the zero column. By Proposition 8.30, $$H{\mathbf e}_i \neq {\mathbf 0}\text{.}$$

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}\text{,} \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\text{.}$$ 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 $$\Null(H)$$ does not contain any $$4$$-tuples of weight $$2\text{.}$$ That is, $$(1100)\text{,}$$ $$(1010)\text{,}$$ $$(1001)\text{,}$$ $$(0110)\text{,}$$ $$(0101)\text{,}$$ and $$(0011)$$ must not be in $$\Null(H)\text{.}$$ The next theorem states that we can indeed determine that the code generated by $$H$$ is error-correcting by examining the columns of $$H\text{.}$$ Notice in this example that not only does $$H$$ have no zero columns, but also that no two columns are the same.

The $$n$$-tuple $${\mathbf e}_{i} +{\mathbf e}_{j}$$ has $$1$$s in the $$i$$th and $$j$$th entries and 0s elsewhere, and $$w( {\mathbf e}_{i} +{\mathbf e}_{j}) = 2$$ for $$i \neq j\text{.}$$ Since

\begin{equation*} {\mathbf 0} = H({\mathbf e}_{i} +{\mathbf e}_{j}) = H{\mathbf e}_{i} + H{\mathbf e}_{j} \end{equation*}

can only occur if the $$i$$th and $$j$$th columns are identical, the null space of $$H$$ is a single error-correcting code.

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}\text{.} \end{equation*}

So we can add as many as four columns and still maintain a minimum distance of $$3\text{.}$$

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.