$\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{\nmid} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \newcommand{\transpose}{\text{t}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&}$

## 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}. \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}\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). \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 $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}, \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\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. \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}. \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, \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+1} & = 0\\ & \vdots \\ a_{m1} y_1 + a_{m2} y_2 + \cdots + a_{m, n-m} y_{n-m} + y_{n-m+1} & = 0. \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+1} & = a_{21} y_1 + a_{22} y_2 + \cdots + a_{2, n-m} y_{n-m}\\ & \vdots\\ y_{n-m+1} & = a_{m1} y_1 + a_{m2} y_2 + \cdots + a_{m, n-m} y_{n-m}. \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}. \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}, \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}. \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.