19.3: Using the Generator Matrix For Encoding

Last updated
Save as PDF

Page ID: 60175

Joy Morris
University of Lethbridge

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Notation

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

\[ \left[ \begin{array}{ll} x_1\\ x_2\\ ...\\ x_n\\ \end{array} \right]. \]

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

Example \(\PageIndex{1}\)

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

\(G = \left[ \begin{array}{ll} 1\;\;0\;\;0 \\ 0\;\;1\;\;0 \\ 0\;\;0\;\;1 \\ 1\;\;1\;\;1 \\ \end{array} \right] = \left[ \dfrac{I_3}{A} \right] \)

where \(I_k\) is the \(k \times k\) identity matrix, and \(A = [1\;\;\;1 \;\;\;1]\).

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

\( \left[ \begin{array}{ll} 0\\ 1\\ 0 \end{array} \right] = \left[ \begin{array}{ll} 0\\ 1\\ 0 \\ 1 \end{array} \right]. \)

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

\( \left[ \begin{array}{ll} x_1\\ x_2\\ x_3 \end{array} \right] = \left[ \begin{array}{ll} x_1\\ x_2 \\ x_3 \\ x_1 + x_2 + x_3 \end{array} \right], \text{ and } x_1 + x_2 + x_3 (\text{mod } 2) = \left\{ \begin{array}{ll} 0 \text{ if even # of } 1\text{s}\\ 1 \text{ if odd # of } 1\text{s}\\ \end{array} \right. \)

General Method

For some \(k\), \(r ∈ \mathbb{N}^+\),

choose an \(r \times k\) matrix \(A\) of \(0\)s and \(1\)s, and
let \(G = \left[ \dfrac{I_k}{A} \right]\)

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

Note

In the next section, we will see how to choose \(G\) so that the resulting code \(C\) 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: Binary Linear Code

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

Example \(\PageIndex{2}\)

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

\(G = \left[ \dfrac{I_3}{A} \right], \text{with } A = \left[ \begin{array}{ll} 1\;\;0\;\;1\\ 0\;\;1\;\;1 \end{array} \right]. \)

Solution

We have

\(G = \left[ \dfrac{I_3}{A} \right], \text{with } A = \left[ \begin{array}{ll} 1\;\;0\;\;0\\ 0\;\;1\;\;0\\ 0\;\;0\;\;1\\ 1\;\;0\;\;1\\ 0\;\;1\;\;1 \end{array} \right]. \)

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

\[\begin{equation} \begin{split} &G\left[ \begin{array}{ll} 0\\ 0\\ 0 \end{array} \right] = \left[ \begin{array}{ll} 0\\ 0 \\ 0 \\ 0 \\0 \end{array} \right],\;\;\;\; &G\left[ \begin{array}{ll} 0\\ 0\\ 1 \end{array} \right] = \left[ \begin{array}{ll} 0\\ 0 \\ 1 \\ 1 \\1 \end{array} \right], \;\;\;\; &G\left[ \begin{array}{ll} 0\\ 1\\ 0 \end{array} \right] = \left[ \begin{array}{ll} 0\\ 1 \\ 0 \\ 0 \\1 \end{array} \right], \;\;\;\; &G\left[ \begin{array}{ll} 0\\ 1\\ 1 \end{array} \right] = \left[ \begin{array}{ll} 0\\ 1 \\ 1 \\ 1 \\0 \end{array} \right],\\[0.25in] &G\left[ \begin{array}{ll} 1\\ 0\\ 0 \end{array} \right] = \left[ \begin{array}{ll} 1\\ 0 \\ 0 \\ 1 \\0 \end{array} \right], &G\left[ \begin{array}{ll} 1\\ 0\\ 1 \end{array} \right] = \left[ \begin{array}{ll} 1\\ 0 \\ 1 \\ 0 \\1 \end{array} \right], &G\left[ \begin{array}{ll} 1\\ 1\\ 0 \end{array} \right] = \left[ \begin{array}{ll} 1\\ 1 \\ 0 \\ 1 \\1 \end{array} \right], &G\left[ \begin{array}{ll} 1\\ 1\\ 1 \end{array} \right] = \left[ \begin{array}{ll} 1\\ 1 \\ 1 \\0 \\0 \end{array} \right]. \end{split} \end{equation}\]

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

Exercise \(\PageIndex{1}\)

Encode each of the given words by using the generating matrix \(G = \left[ \begin{array}{ll} I_k\\ A \end{array} \right]\). associated to the given matrix \(A\).

1) \(A = \left[ \begin{array}{ll} 1\;\;1\;\;0\;\;0\\ 1\;\;0\;\;0\;\;1 \end{array} \right]\). Words to encode: \(0101\), \(0010\), \(1110\).

2) \(A = \left[ \begin{array}{ll} 1\;\;1\;\;0\\ 1\;\;0\;\;1 \\0\;\;1\;\;1 \\ 1\;\;1\;\;1 \end{array} \right]\). Words to encode: \(110\), \(011\), \(111\), \(000\).

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.