Institute of Information Science - University of Miskolc

Hamming codes are a family of error-correcting codes that can detect up to two-bit errors and correct single-bit errors in transmitted data. They use the Hamming distance concept to determine where errors may have occurred.

If we have \(m\) number of data bits then let's attach \(r\) number of redundant parity bits to it, so the whole bit length will be:

$$ n = m + r $$

If two code-words are given, for example : 0101110 and 001111110 and the only difference between them is 1 bit, then the 'Hamming distance' of these code-words will be 1. This is an interesting measure for distance because it does not matter which bit in the row is different or whether it belongs to a binary or decimal system. So for example : 45635263 and 45615263 have the Hamming distance of 1 too. It does not matter that 10 different digits could be in the place of the wrong digit.

The Hamming-style correction code supposed to increase the number of parity bits. To correct single bit errors we have to use k number of parity bits using this formula:

$$ n + 1 \le 2^k $$

According to this formula the necessary number of parity bits which are needed to correct single bit errors are stated in the following table (for different word lengths):