Skip to main content

Section 19.3 Using the generator matrix for encoding

This section and Section 19.4 do assume some familiarity with elementary linear algebra: specifically, knowing what vectors and matrices are, and being able to perform matrix multiplication. These two sections can be omitted by anyone who does not have this background, without affecting your understanding of the rest of the book.

Notation 19.3.1.

It is convenient to represent the binary string \(x_1x_2\ldots x_n\) as a column vector:

\begin{equation*} \begin{bmatrix}x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix}\text{.} \end{equation*}

This allows us to use matrix multiplication to append check bits to a string:

Appending a parity check-bit to the string \(010\) yields \(0101\text{.}\) The same result can be obtained by multiplying the column vector corresponding to \(010\) by the following generator matrix:

\begin{equation*} \text{\(G = \begin{bmatrix}1 \amp 0 \amp 0 \\ 0 \amp 1 \amp 0 \\ 0 \amp 0 \amp 1\\ 1 \amp 1 \amp 1 \end{bmatrix} = \begin{bmatrix}I_3 \\ \hline A \end{bmatrix} \) where \(I_k\) is the \(k \times k\) identity matrix, and \(A = \begin{bmatrix}1 \amp 1 \amp 1 \end{bmatrix} \).} \end{equation*}

Namely (performing all arithmetic modulo \(2\)), we have

\begin{equation*} G \begin{bmatrix}0 \\ 1 \\ 0 \end{bmatrix} = \begin{bmatrix}0 \\ 1 \\ 0 \\ 1 \end{bmatrix}\text{.} \end{equation*}

In fact, multiplying any \(3\)-bit string by \(G\) yields the same string with its parity check-bit appended.

Proof

We see that \(G \begin{bmatrix}x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix}x_1 \\ x_2 \\ x_3 \\ x_1 + x_2 + x_3 \end{bmatrix}\text{,}\) and \(x_1 + x_2 + x_3 \pmod{2} \) is \(0\) if there are an even number of \(1\)s among \(x_1\text{,}\) \(x_2\text{,}\) and \(x_3\text{,}\) and it is \(1\) if there are an odd number of \(1\)s among \(x_1\text{,}\) \(x_2\text{,}\) and \(x_3\text{.}\)

General Method.

For some \(k,r \in \natural^+\text{,}\)

  • choose an \(r \times k\) matrix \(A\) of \(0\)s and \(1\)s, and

  • let \(G = \begin{bmatrix}I_k \\ \hline A \end{bmatrix}\text{.}\)

Multiplying a \(k\)-bit string by \(G\) yields the same string, with \(r\) check bits appended at the end. We let \(\code\) be the set of all possible strings \(Gx\text{,}\) and we call \(G\) the generator matrix of this code.

Remark 19.3.3.

In the next section, we will see how to choose \(G\) so that the resulting code \(\code\) can correct errors.

Although many important error-correcting codes are constructed by other methods, we will only discuss the ones that come from generator matrices (except in Section 19.5).

Definition 19.3.4.

Any code that comes from a generator matrix \(G\) (by the General Method described above) is said to be a binary linear code.

Find all the codewords of the binary linear code \(\code\) corresponding to the generator matrix

\begin{equation*} \text{\(G = \begin{bmatrix}I_3 \\ \hline A \end{bmatrix} \), with \(A = \begin{bmatrix}1 \amp 0 \amp 1 \\ 0 \amp 1 \amp 1 \end{bmatrix} \)}\text{.} \end{equation*}
Solution

We have

\begin{equation*} G = \begin{bmatrix}I_3 \\ \hline A \end{bmatrix} = \begin{bmatrix}1 \amp 0 \amp 0 \\ 0 \amp 1 \amp 0 \\ 0 \amp 0 \amp 1 \\ 1 \amp 0 \amp 1 \\ 0 \amp 1 \amp 1 \end{bmatrix}\text{.} \end{equation*}

We use this matrix to encode each of the \(2^3 = 8\) binary strings of length \(3\text{:}\)

\begin{align*} G \begin{bmatrix} 0\\ 0\\ 0 \end{bmatrix} \amp = \begin{bmatrix} 0\\ 0\\ 0\\ 0\\ 0\end{bmatrix} , \amp G \begin{bmatrix} 0\\ 0\\ 1 \end{bmatrix} \amp = \begin{bmatrix} 0\\ 0\\ 1\\ 1\\ 1\end{bmatrix} , \amp G \begin{bmatrix} 0\\ 1\\ 0 \end{bmatrix} \amp = \begin{bmatrix} 0\\ 1\\ 0\\ 0\\ 1\end{bmatrix} , \amp G \begin{bmatrix} 0\\ 1\\ 1 \end{bmatrix} \amp = \begin{bmatrix} 0\\ 1\\ 1\\ 1\\ 0\end{bmatrix} ,\\ G \begin{bmatrix} 1\\ 0\\ 0 \end{bmatrix} \amp = \begin{bmatrix} 1\\ 0\\ 0\\ 1\\ 0\end{bmatrix} , \amp G \begin{bmatrix} 1\\ 0\\ 1 \end{bmatrix} \amp = \begin{bmatrix} 1\\ 0\\ 1\\ 0\\ 1\end{bmatrix} , \amp G \begin{bmatrix} 1\\ 1\\ 0 \end{bmatrix} \amp = \begin{bmatrix} 1\\ 1\\ 0\\ 1\\ 1\end{bmatrix} , \amp G \begin{bmatrix} 1\\ 1\\ 1 \end{bmatrix} \amp = \begin{bmatrix} 1\\ 1\\ 1\\ 0\\ 0\end{bmatrix} \text{.} \end{align*}

So \(\code = \{ 00000, 00111, 01001, 01110, 10010, 10101, 11011, 11100\}\text{.}\)

Encode each of the given words by using the generating matrix \(G = \begin{bmatrix}I_k \\ A \end{bmatrix}\) associated to the given matrix \(A\text{.}\)

  1. \(A = \begin{bmatrix}1 \amp 1 \amp 0 \amp 0 \\ 1 \amp 0 \amp 0 \amp 1 \end{bmatrix}\text{.}\) Words to encode: \(0101\text{,}\) \(0010\text{,}\) \(1110\text{.}\)

  2. \(A = \begin{bmatrix}1 \amp 1 \amp 0 \\ 1 \amp 0 \amp 1 \\ 0 \amp 1 \amp 1 \\ 1 \amp 1 \amp 1 \end{bmatrix}\text{.}\) Words to encode: \(110\text{,}\) \(011\text{,}\) \(111\text{,}\) \(000\text{.}\)

The generator matrix provides an easy way to encode messages for sending, but it is hard to use it to decode a message that has been received. For that, the next section will introduce a slightly different matrix. From this new matrix, it will be easy to determine whether the corresponding code can correct every single-bit error.