Skip to main content
\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \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{\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\), 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).

Message Word \(\mathbf x\) Codeword \(G \mathbf x\)
000 000000
001 001101
010 010110
011 011011
100 100011
101 101110
110 110101
111 111000
Table8.24A matrix-generated code

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.

Proof
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.