Binary Hamming Codes

Simplest example of an error correcting code

A binary hamming code $\mathcal{H}_{2,r}$ has a parity check matrix $H_{2,r}$ consisting of all possible non-zero binary columns of length $r$. For example,

$$H_{2,r} = \begin{bmatrix}0 & 0 & 0 & 1 & 1 & 1 & 1 0 & 1 & 1 & 0 & 0 & 1 & 1 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{bmatrix}$$

The code for which $\mathcal{H}_{2,r}$ is the parity check matrix is called the binary Hamming code of length $2^{r-1}$. Its parameters are $[2^r -1, 2^r-1-r,3]$.

Theorem 1.7.1   Any $[2^r - 1, 2^r-r-1, 3]_2$ code is permutation equivalent to the binary Hamming code of length $2^r-1$.

Exercise: Any $[8,4,4]_2$ code is equivalent to $\hat \mathcal{H}_3$.

Other Fields: $\mathbb{F}_q$
Construct a parity check matrix $H_{q,r}$ whose columns consist of exactly 1 non-zero vector from each 1-dimensional subspace of $\mathbb{F}_q^r$. The code $\mathcal{H}_{q,r}$ is the one for which $H_{q,r}$ is a parity check matrix. Parameters: $[(q^r - 1)/(q-1), (q^r-1)/(q-1) - r, 3]_q$

Theorem 1.7.2   Any $[n_{q,r}, k_{q,r}, 3]_2$ code is monomially equivalent to the Hamming code $\mathcal{H}_{q,r}$.

Suppose $H_{q,r}$ is the generator matrix?

$$\mathcal{H}_{2,3}^\perp = \{ 0000000, 0001111, 0110011, \ldots, 1101001 \}$$

All nonzero vectors of $\mathcal{H}_{q,r}^\perp$ have weight $q^{r-1}$. The dual of a Hamming code is a simplex code ( $[(q^r-1)/(q-1),r,q^{r-1}]$).