## Section 16.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

and \(I_m\) is the \(m \times m\) identity matrix

With each canonical parity-check matrix we can associate an \(n \times (n-m)\) standard generator matrix

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

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

For

the associated standard generator and canonical parity-check matrices are

and

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

which yields a system of equations:

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

An even easier way to compute the null space is with the generator matrix \(G\) (Table 16.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\) |

###### Theorem 16.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 16.23, the first three bits are the information bits and the last three are the check bits.

###### Theorem 16.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

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

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

where

is the Kronecker delta.

###### Theorem 16.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 16.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:

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

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

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

Observe that

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

###### Proposition 16.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 16.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 16.30, \(H{\mathbf e}_i \neq {\mathbf 0}\text{.}\)

###### Example 16.32.

If we consider the matrices

and

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 16.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 16.33.

If we let

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

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

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.