AATA Parity-Check and Generator Matrices

Section 8.3 Parity-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{.}\)

Example 8.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).

Table 8.24. A matrix-generated code

Message Word \(\mathbf x\)	Codeword \(G \mathbf x\)
\(000\)	\(000000\)
\(001\)	\(001101\)
\(010\)	\(010110\)
\(011\)	\(011011\)
\(100\)	\(100011\)
\(101\)	\(101110\)
\(110\)	\(110101\)
\(111\)	\(111000\)

Theorem 8.25.

If \(H \in {\mathbb M}_{m \times n}({\mathbb Z}_2)\) is a canonical parity-check matrix, then \(\Null(H)\) consists of all \({\mathbf x} \in {\mathbb Z}_2^n\) whose first \(n-m\) bits are arbitrary but whose last \(m\) bits are determined by \(H{\mathbf x} = {\mathbf 0}\text{.}\) Each of the last \(m\) bits serves as an even parity check bit for some of the first \(n-m\) bits. Hence, \(H\) gives rise to an \((n, n-m)\)-block 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.

Theorem 8.26.

Suppose that \(G\) is an \(n \times k\) standard generator matrix. Then \(C = \left\{{\mathbf y} : G{\mathbf x} ={\mathbf y}\text{ for }{\mathbf x}\in {\mathbb Z}_2^k\right\}\) is an \((n,k)\)-block code. More specifically, \(C\) is a group code.

Proof.

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.

Lemma 8.27.

Let \(H = (A \mid I_m )\) be an \(m \times n\) canonical parity-check matrix and \(G = \left( \frac{I_{n-m} }{A} \right)\) be the corresponding \(n \times (n-m)\) standard generator matrix. Then \(HG = {\mathbf 0}\text{.}\)

Proof.

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.

Theorem 8.28.

Let \(H = (A \mid I_m )\) be an \(m \times n\) canonical parity-check matrix and let \(G = \left( \frac{I_{n-m} }{A} \right) \) be the \(n \times (n-m)\) standard generator matrix associated with \(H\text{.}\) Let \(C\) be the code generated by \(G\text{.}\) Then \({\mathbf y}\) is in \(C\) if and only if \(H {\mathbf y} = {\mathbf 0}\text{.}\) In particular, \(C\) is a linear code with canonical parity-check matrix \(H\text{.}\)

Proof.

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{.}\)

Example 8.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.

Proposition 8.30.

Let \({\mathbf e}_i\) be the binary \(n\)-tuple with a \(1\) in the \(i\)th coordinate and \(0\)’s elsewhere and suppose that \(H \in {\mathbb M}_{m \times n}({\mathbb Z}_2)\text{.}\) Then \(H{\mathbf e}_i\) is the \(i\)th column of the matrix \(H\text{.}\)

Theorem 8.31.

Let \(H\) be an \(m \times n\) binary matrix. Then the null space of \(H\) is a single error-detecting code if and only if no column of \(H\) consists entirely of zeros.

Proof.

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{.}\)

Example 8.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.

Example 8.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.

Theorem 8.34.

Let \(H\) be a binary matrix. The null space of \(H\) is a single error-correcting code if and only if \(H\) does not contain any zero columns and no two columns of \(H\) are identical.

Proof.

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.

Prev Top Next