section-parity-check.ipynb

Kernel:

%%html
<link href="http://mathbook.pugetsound.edu/beta/mathbook-content.css" rel="stylesheet" type="text/css" />
<link href="https://aimath.org/mathbook/mathbook-add-on.css" rel="stylesheet" type="text/css" />
<style>.subtitle {font-size:medium; display:block}</style>
<link href="https://fonts.googleapis.com/css?family=Open+Sans:400,400italic,600,600italic" rel="stylesheet" type="text/css" />
<link href="https://fonts.googleapis.com/css?family=Inconsolata:400,700&subset=latin,latin-ext" rel="stylesheet" type="text/css" /><!-- Hide this cell. -->
<script>
var cell = $(".container .cell").eq(0), ia = cell.find(".input_area")
if (cell.find(".toggle-button").length == 0) {
ia.after(
    $('<button class="toggle-button">Toggle hidden code</button>').click(
        function (){ ia.toggle() }
        )
    )
ia.hide()
}
</script>

Important: to view this notebook properly you will need to execute the cell above, which assumes you have an Internet connection. It should already be selected, or place your cursor anywhere above to select. Then press the "Run" button in the menu bar above (the right-pointing arrowhead), or press Shift-Enter on your keyboard.

ParseError: KaTeX parse error: \newcommand{\lt} attempting to redefine \lt; use \renewcommand

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 . 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)$

$$\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 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)\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).

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

Theorem8.25

If $H \in {\mathbb M}_{m \times n}({\mathbb Z}_2)$ is a canonical parity-check matrix, then ${\rm 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 and the last $m$ bits are called . In Example 8.23, the first three bits are the information bits and the last three are the check bits.

Theorem8.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. \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.

Lemma8.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, \end{align*}$$

where

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

is the Kronecker delta.

Theorem8.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)^{\rm t}$ 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}^{\rm t} = {\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)^{\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\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.

Proposition8.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{.}$

Theorem8.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 ${\rm Null}(H)$ is a single error-detecting code. Then the minimum distance of the code must be at least 2. 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. 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)\text{,}$ $(1010)\text{,}$ $(1001)\text{,}$ $(0110)\text{,}$ $(0101)\text{,}$ and $(0011)$ must not be in ${\rm 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.

Theorem8.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 1s 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.

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.