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:
This allows us to use matrix multiplication to append check bits to a string:
Example 19.3.2.
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:
Namely (performing all arithmetic modulo \(2\)), we have
In fact, multiplying any \(3\)-bit string by \(G\) yields the same string with its parity check-bit appended.
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.
Example 19.3.5.
Find all the codewords of the binary linear code \(\code\) corresponding to the generator matrix
We have
We use this matrix to encode each of the \(2^3 = 8\) binary strings of length \(3\text{:}\)
So \(\code = \{ 00000, 00111, 01001, 01110, 10010, 10101, 11011, 11100\}\text{.}\)
Exercises 19.3.6.
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{.}\)
\(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{.}\)
\(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.