$q$-ary Hamming codes

Let $p$ be a prime and let $\mathbb{F}_p^r-\{0\}$ denote the set of all non-zero $r$-tuples, i.e., the non-zero vectors in the $r$-dimensional vector space $\mathbb{F}_p^r$ over $\mathbb{F}_p$. We may represent each vector by an $r$-tuple of integers belonging to $\{0,1,...,p-1\}$. If ${\bf a}=(a_1,...,a_r)\in \mathbb{F}_p^r-\{0\}$ and $0\leq a_i<p-1$ the define

$$n({\bf a})=a_1+a_2p+...+a_rp^{r-1}.$$

This is a map $x:\mathbb{F}_p^r-\{0\}\rightarrow \{0,1,...,p^r-1\}$. Let ${\bf a}=(a_1,...,a_r)$ and ${\bf b}=(b_1,...,b_r)$ be two such vectors. Define $a<_x b$ if $x({\bf a})<x({\bf b})$. Now take each vector ${\bf a}=(a_1,...,a_r)\in \mathbb{F}_p^r-\{0\}$ and divide every entry by it's first non-zero entry. Let $S$ be the set of them. There are $n=(p^r-1)/(p-1)$ elements in $S$. Write the elements of the set $S$ in increasing order, using the ordering $<_x$ above. Let $H$ be the $r\times N$ matrix whose $i^{th}$ column is the $i^{th}$ vector in $S$ (written as a column vector). We know that the first column of $H$ is

$$\begin{array}{c} 1 \\ 0\\ \vdots \\ 0 \end{array}$$

and the last column is

$$\begin{array}{c} 1 \\ p-1\\ \vdots \\ p-1 \end{array}$$

Example 3.9.5   For example, if $p=3$ and $r=2$ then

$$H= \begin{array}{cccc} 1 & 1 & 1 & 0\\ 0 & 1 & 2 & 1 \end{array}$$

is a parity check matrix and

$$H= \begin{array}{cccc} 1 & 1 & 1 & 0\\ 1 & 2 & 0 & 1 \end{array}$$

is a generator matrix for the $(4,2,3)$ Hamming code over $\mathbb{F}_3$.

Exercise 3.9.6   Write down $H$ if $p=3$ and $r=3$.

The code $C$ whose parity check matrix is this matrix $H$ constructed above is the $p$-ary Hamming code of length $n=(p^r-1)/(p-1)$ and dimension $k=n-r$. More generally, we have the following definition.

Definition 3.9.7   Let $r>1$ and let $q$ be a prime power. The Hamming $[n,k,3]$-code $C$ over $\mathbb{F}_q$ is the linear code with

$$n=(q^r-1)/(q-1),\ \ \ \ \ k=n-r,$$

and parity check matrix $H$ defined to be the matrix whose columns are all the (distinct) non-zero vectors in $\mathbb{F}_q^r$, normalized to have first non-zero coordinate equal to $1$.

Like its binary cousin, it has minimum distance $3$. It is left as an exercise to prove the analog of Lemma 3.9.3 in this case.

Remark 3.9.8   It is also possible to define the RM code of order $1$ in Example 3.7.6 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$. It is known that $(C')^\perp$ is equivalent to the first order Reed-Muller code (this is a special case of Theorem 11 in chapter 13 of [MS]).