Hamming distance and parity

Question

For an Hamming code of $n$ bit there are $k$ bit reserved for the data and $p$ bit for the parity where $p$ is the minimum integer for which the following inequation is satisfied: $$2^p \geqslant p + k + 1$$ This because at least $p$ bit are required to code $n$ error on a single bit $+ 1$ for the "no error" word.

For an Hamming code with distance $d$ you can detect $d-1$ bit of errors and correct $\lfloor d-1/2 \rfloor$ bit of errors.

However you can have SEC (7,4) and SEC (12,8) with the same Hamming distance $d = 3$ but the the first has $p = 3$ bit for the parity while the second has $p = 4$ bit for the parity.

The first question is what does it mean for an Hamming code H having an Hamming distance = 3 ? Does it mean that all $k$ or $n$ bit of data are required to have $d=3$ with each other ?

What is the relationship between the parity and the distance in an Hamming code ?

Answer 1

A (binary) code $C$ is a collection of binary strings of some length $n$, known as codewords. The minimal distance of $C$ is the minimum Hamming distance between (different) codewords. Hamming codes have minimum distance 3, which means that (1) every two codewords differ in at least 3 places, (2) there exist two codewords which differ in exactly 3 places.

Hamming codes are examples of an important class of codes known as linear codes. You can think of linear codes in many ways:

1. A linear code of length $n$ is a linear subspace of $\{0,1\}^n$. The dimension of the code is known as the rate $k$.

2. A linear code is a code which is closed under XOR, that is, the XOR of any two codewords is again a codeword. It turns out that the number of codewords is always a power of 2, say $2^k$. The parameter $k$ is known as the rate.

3. A linear code is a way of encoding $k$-bit messages using $n$ bits. The original bits of the message are put in fixed places, and every other bit is an XOR of a certain fixed subset of the message bits. For example, the SEC(7,4) code encodes a 4-bit message $x,y,z,w$ using 7 bits: $$ x \oplus y \oplus w, x \oplus z \oplus w, x, y \oplus z \oplus w, y, z, w $$

The minimal distance of a linear code is also the minimal Hamming weight of a non-zero codeword. So the fact that Hamming codes have minimum distance 3 means that (1) every non-zero codeword has at least 3 ones, (2) there exists a codeword having exactly 3 ones.

We have mentioned three parameters: the length of the code $n$, the rate of the code $k$, and the minimal distance $d$. There is no exact relation between these three parameters, though there are various bounds relating the three quantities. One of these bounds is the Hamming bound: $$ \sum_{\ell=0}^{\lfloor \frac{d-1}{2}\rfloor} \binom{n}{\ell}\leq 2^{n-k}. $$ For example, for the SEC(7,4) code this gives $$ \binom{7}{0} + \binom{7}{1} \leq 2^{7-4}. $$ You can check that equality holds, and indeed this is the case for all Hamming codes. Codes for which equality holds are called perfect codes. Apart from a few trivial and exceptional cases, Hamming codes are (essentially) the only perfect codes.