Decoding Hamming codes

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

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

This is a map $n:\mathbb{F}_p^n-\{0\}\rightarrow \{0,1,...,p^n-1\}$. Let ${\bf a}=(a_1,...,a_n)$ and ${\bf b}=(b_1,...,b_n)$ be two such vectors. Define $a<_n b$ if $n({\bf a})<n({\bf b})$. Now take each vector ${\bf a}=(a_1,...,a_n)\in \mathbb{F}_p^n-\{0\}$ and divide every entry by it's first non-zero entry. Let $S$ be the set of them. There are $N=(p^n-1)/(p-1)$ elements in $S$. Write the elements of the set $S$ in increasing order, using the ordering $<_n$ above. Let $H$ be the $n\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.8.4   Write down $H$ if $p=2$ and $n=4$.

Here's the decoding algorithm: Let $y$ be the received vector. Auume that $y$ has $\leq 1$ error. Compute $y\cdot H^t$. This is an $n$-tuple, so it must be of the form $c\cdot {\bf s}$, for some ${\bf s}\in S$ and some $c\in \mathbb{F}_p^\times$. If ${\bf s}$ is the $i^{th}$ element of $S$ then the decoded vector is ${\bf y}-c\cdot {\bf e}_i$, where

$${\bf e}_1=(1,0,...,0), \ \ {\bf e}_2=(0,1,0,...,0), ..., {\bf e}_n=(0,...,0,1),$$

are the standard basis vectors in $\mathbb{F}_p^n$.

Remark 3.8.5   Dual to the binary Hamming code is the simplex code. The line segments connecting the codewords in a simplex code form a regular simplex.