Binary hamming codes

The easiest way to define the Hamming code, which is a vector space over $\mathbb{F}_2$, is by defining a generator matrix. Incidently, calling it ``the'' Hamming code is a slight abuse of terminology. First, for each integer $r\geq 2$ there is a different Hamming code. Second, we often implicitly identify two equivalent codes, so two equivalent forms of a Hamming code are regarded as the same.

Definition 3.9.1   Let $r>1$. The Hamming $[n,k,3]$-code $C$ is the linear code with

$$n=2^r-1,\ \ \ \ \ k=2^r-r-1,$$

and parity check matrix $H$ defined to be the matrix whose columns are all the (distinct) non-zero vectors in $\mathbb{F}_2^r$. (Later we will show that it has minimum distance $d=3$.)

Example 3.9.2   $r=2$: The Hamming $(3,1)$-code has parity check matrix

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

By Corollary 3.7.4, the matrix $G=(1,1,1)$ is a generating matrix.

$r=3$: The Hamming $(7,4)$-code has parity check matrix

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

By Corollary 3.7.4, the matrix

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

is a generating matrix. Though this may not look like the code presented in an earlier section, they are equivalent.

Lemma 3.9.3   Every binary Hamming code $C$ has minimum distance $3$.

proof: Indeed, if $C$ has a code wode of weight 1 then the parity check matrix $H$ of $C$ would have to have a column which consists of the zero vector, contradicting the definition of $H$. Likewise, if $C$ has a code wode of weight 2 then the parity check matrix $H$ of $C$ would have to have two identical columns, contradicting the definition of $H$. Thus $d\geq 3$.

Since

$$\left( \begin{array}{c} 1 \\ 0 \\ 0\\ \vdots \\ 0 \end{a... ...n{array}{c} 1 \\ 1 \\ 0 \\ \vdots \\ 0 \end{array}\right),$$

form three columns of the parity check matrix $H$ of $C$ - say the $1^{st}$, $2^{nd}$, and $3^{rd}$ columns - the vector $(1,1,1,0,...,0)$ must be a code word. Thus $d\leq 3$. $\char93$

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