Computing the check matrix and the encoding matrix

The following property of $H$ is perhaps the key reason for introducing the dual code.

Lemma 3.7.1   For all ${\bf v}\in F^n$, we have ${\bf v}\in C$ if and only if ${\bf v}\cdot H^t={\bf0}$.

The proof is left as an exercise.

In particular, a vector ${\bf v}\in F^n$ is a code word if and only if it satisfies the conditions ${\bf v}\cdot {\bf h_i}=0$ ( $1\leq i\leq n-k$), where ${\bf h_i}\in F^n$ is the $i-th$ row of $H$. This is a very convenient condition for checking if an error has been made in transmission.

Sometimes a generator matrix $G$ can, after elementary row operations, be put in the form

$$G=(I_k\vert A),$$

where $I_k$ is the $k\times k$ identity matrix and $A$ is an $k\times (n-k)$ matrix. If this can be done, then we say that the generator matrix can be put in standard form. In this case, the parity check matrix can be computed.

Proposition 3.7.2   If $G=(I_k\ \vert\ A)$ is the generator matrix for $C$ then $H=(-A^t\ \vert\ I_{n-k})$ is a parity check matrix.

The proof of this will be left as an exercise.

One other interesting fact about codes in standard form is that the information bits of the codewords are easy to distinguish. If we denote the row vectors of $G=(I_k\ \vert\ A)$ by $g_1,g_2,...,g_k$ then these form a basis for $C$. The information bits of a codeword are the first $k$ coordinates. Moreover, to to encode a message $m=(m_1,...,m_k)$ into a codeword, simply compute the $n$-tuple $G^tm$ (or $mG$, depending on if you're writing $m$ as a row vector or a column vector).

Example 3.7.3   If $C$ is the code over $\mathbb{F}_2$ with generator matrix

$$G=\left( \begin{array}{ccccccc} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\... ...& 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 \end{array}\right).$$

The codewords are all of the form $(c_1,c_2,c_3,c_4,c_1+c_3+c_4,c_1+c_2+c_3,c_2+c_3+c_4)$, where $c_i\in \mathbb{F}_2$. In other words, all codewords are of the form $G^tm$, where $m=(c_1,c_2,c_3,c_4)\in \mathbb{F}_2^4$. A check matrix for $C$ is given by

$$H=\left( \begin{array}{ccccccc} 1 & 0 & 1 & 1 & 1 & 0 & 0 \\... ...& 0 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 \end{array}\right).$$

Since $(C^\perp)^\perp = C$, we have, as a consequence of this, the following result.

Corollary 3.7.4   If $H=(I_k\ \vert\ B)$ is the parity check matrix for $C$ then $G=(-B^t\ \vert\ I_{n-k})$ is a generator matrix.

Example 3.7.5   Consider the subcode of the ISBN code with generator matrix

$$G=\left( \begin{array}{cccccccccc} 1&0&0&0&0&0&0&0&0&1\\ 0&... ...1&1&0&0&0&0&0&1&0&0\\ 1&0&1&0&0&0&1&0&0&0 \end{array}\right).$$

We can add the first, second and third rows to the last two rows to put this in the upper-triangular form

$$G'=\left( \begin{array}{cccccccccc} 1&0&0&0&0&0&0&0&0&1\\ 0... ...0&0&0&0&0&0&0&1&1&1\\ 0&0&0&0&0&0&1&1&0&1 \end{array}\right).$$

This is not in standard form. In fact, the code $C$ does not have a generator matrix in standard form. However, let $C'$ be the code obtained from $C$ by swapping the $6^{th}$ and $8^{th}$ coordinates. These codes $C$ and $C'$ are equivalent. We leave it as an exercise to show that $C'$ has a generator matrix in standard form.

Example 3.7.6   One way to define the Reed-Muller code is as follows. Let $\{s_i\}$ be a sequence defined by an equation such as (1.3) in the above section on linear recussion §1.7.6, where $a_i\in \mathbb{F}_q$ and $s_i\in \mathbb{F}_q$. Assume that the characteristic polynomial of $A$ in §1.7.6 is irreducible and primitive. Let $N$ be the period. The set

$$RM(k,1)=\{ (s_1,...,s_N)\ {\rm satisfying\ (\ref{eq:recur})}\, \vert\ (s_1,...,s_k)\in \mathbb{F}_q^k\ \}$$

is a vector space, called the first order Reed-Muller code.

These were used by Marinar 9 on its 1972 flight to Mars.

Exercise 3.7.7   Let $C'$ be as in Example 3.7.5. Show that $C'$ has a generator matrix in standard form.

Exercise 3.7.8   Prove Lemma 3.7.1. (Hint: The proof uses from the definition of $H$.)

Exercise 3.7.9   Prove Proposition 3.7.2 (Hint: The proof uses from the definition of $H$.)

Exercise 3.7.10   Show that the code $C$ generated by

$$G= \left( \begin{array}{cccccccc} 1& 0& 0& 0& 1& 1& 0& 1\\ ... ... 1& 0& 1& 1& 1& 0\\ 0& 0& 0& 1& 1& 0& 1& 1 \end{array}\right)$$

satisfies $C=C^\perp$. Show that $n=8$, $k=4$, and $d=4$.