Hamming code

The binary Hamming code of redundancy $r$ has parameters $[2^r-1,2^r-r-1,3]$. Its parity-check matrix has every nonzero vector of ${\mathbb{F}}_2^r$ as a column.

For $s\ge 2$, use one nonzero representative from each one-dimensional subspace of ${\mathbb{F}}_3^s$ as a parity-check matrix column. The rank is $s$; no zero or proportional columns imply minimum Hamming distance at least three. Two independent columns and the representative of their sum give a weight-three relation, proving equality. Every nonzero syndrome uniquely identifies one column and one nonzero error value.

For odd $s\ge 3$, put $n=(3^s-1)/2$ and choose $\alpha$ of order $n$ in ${\mathbb{F}}_{3^s}$. Because $n$ is odd, the powers ${\alpha }^i$, $0\le i<n$, represent every projective point once. The cyclic code defined by $c(\alpha )=0$ is therefore monomially equivalent to a ternary Hamming code, with the displayed generator polynomial of a cyclic code. This statement requires a qualification: at $s=2$, every ternary cyclic length-four, dimension-two code has a weight-two generator, so none has Hamming distance three.

Set $n=(3^s-1)/2$ and let $\beta$ be a primitive element of a finite field ${\mathbb{F}}_{3^s}$. The powers $1,\beta ,\dots ,{\beta }^{n-1}$ represent every projective point once. Their kernel code is a ternary Hamming code. Since ${\beta }^n=-1$, its polynomial description is a negacyclic code, generated by the minimal polynomial of an algebraic element $\beta$ over ${\mathbb{F}}_3$.

Let $\omega$ generate ${\mathbb{F}}_{2^s}^{\times }$, $s\ge 2$, and set $n=2^s-1$. The binary cyclic code defined by $c(\omega )=0$ has a parity-check matrix consisting of every nonzero vector of ${\mathbb{F}}_2^s$ once, after choosing a basis and ordering its columns. It is therefore a Hamming code. Its generator polynomial is the minimal polynomial of an algebraic element $m_{\omega }(x)={\prod }_{j=0}^{s-1}(x-{\omega }^{2^j})$, of degree $s$.

Here $N=2^l-1$, $m=2^{l-1}$ and the weight enumerator convention is $W_C(s,t)={\sum }_{c\in C}{s}^{\mathrm{wt}(c)}{t}^{N-\mathrm{wt}(c)}$. The dual code is the binary simplex code, with enumerator $t^N+(2^l-1)s^m{t}^{m-1}$. The MacWilliams identity gives the formula. For $l=3$, the ordinary enumerator $W_C(z,1)$ is $1+7z^3+7z^4+z^7$; for $l=1$, the degenerate one-word code has enumerator $t$.

For $n=2^{\ell }-1$, a codeword in a Hamming code is a subset of the nonzero vectors of ${\mathbb{F}}_2^{\ell }$ whose sum is zero. Ordered weight-three supports of a vector are determined by two distinct nonzero vectors, giving $n(n-1)$ choices. For weight four, the third vector must avoid the three nonzero vectors in the linear span of the first two, giving $n(n-1)(n-3)$ choices. For weight five, the first three must be linearly independent, and the fourth must avoid all seven nonzero vectors in their linear span, giving $n(n-1)(n-3)(n-7)$ choices. The final vector is their sum. Dividing by $3!$, $4!$, and $5!$ counts unordered supports of a vector and proves the displayed weight enumerator coefficients.

Adding an overall parity bit to the Hamming code of length seven gives an eight-bit linear code with minimum Hamming distance four: every resulting weight is even, every original nonzero weight is at least three, and a weight-three word extends to weight four. Thus it detects up to three errors when testing codeword membership and corrects one error. Joint single-error correction and double-error detection uses the overall parity together with the seven-bit syndrome.

The binary linear code known as the Hamming code of length seven is the kernel of a $3\times 7$ parity-check matrix whose columns are all the nonzero vectors of ${\mathbb{F}}_2^3$. Its dimension is four. No one-column or two-column sum vanishes, but some three-column sum does, so its minimum Hamming distance is three. The syndrome of a one-bit error is its column, uniquely identifying the erroneous position.

The binary simplex code is the dual of the binary Hamming code. For redundancy $r$ it has parameters $[2^r-1,r,2^{r-1}]$.

Its relation to the Hamming code is duality, not equality of the code families.

When the columns of $H$ are every nonzero vector in ${\mathbb{F}}_2^l$, a nonzero row vector $a$ defines a nonzero linear functional $v\mapsto a\cdot v$. Exactly half the $2^l$ input vectors take value $1$: translation by any vector on which the functional is $1$ pairs its zero and one fibres. Removing the zero input removes only a zero value. Thus every nonzero word in the binary simplex code has Hamming weight $2^{l-1}$.

A Hamming code has $2^{2^r-r-1}$ words, and each radius-one Hamming ball contains $1+(2^r-1)=2^r$ vectors. Its minimum distance is three, so these balls are disjoint, and their total size is $2^{2^r-1}$. They therefore partition the ambient space, making the code perfect.