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.4.33   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 generating 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 generating matrix can be put in standard form. In this case, the parity check matrix can be computed.

Proposition 3.4.34   If $G=(I_k\ \vert\ A)$ is the generating 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.4.35   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 \\ 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... ... 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.4.36   If $H=(I_k\ \vert\ B)$ is the parity check matrix for $C$ then $G=(-B^t\ \vert\ I_{n-k})$ is a generating matrix.

Example 3.4.37   The subcode of the ISBN code with generating matrix

$$G=\left( \begin{array}{cccccccccc} 1&0&0&0&0&0&0&0&0&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 or third rows to the last two rows to put this in the form

$$G'=\left( \begin{array}{cccccccccc} 1&0&0&0&0&0&0&0&0&1\\... ...&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.4.38   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), 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)\ \vert\ (s_1,...,s_k)\in \mathbb{F}_2^k\}$$

is a vector space, called the first order Reed-Muller code. It is also possible to define this code as the dual code of the Hamming code extended by one parity check bit: Let $C$ be the Hamming code over $\mathbb{F}_q$ of length $n=(q^r-1)/(q-1)$. Extend this code to a length $n+1$ code, $C'$, where the extra ``bit'' is defined by a parity check: $c_1+...+c_n+c_{n+1}=0$, where $(c_1,...,c_n)\in C$. Then $(C')^\perp$ is (equivalent to) the first order Reed-Muller code.

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

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

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

Exercise 3.4.42   Show that the code $C$ generated by

$$G= \left( \begin{array}{cccccccc} 1& 0& 0& 0& 1& 1& 0& 1... ...& 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$.