1
$\begingroup$

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 ?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.