Hamming Code: What is it? (Formula & Explanation)

What is Hamming Code?

In error detection and correction codes, adding more redundant bits to message bits improves the code’s ability to find and fix errors. With enough redundant bits, we can arrange them so that each error produces a unique result, allowing us to not only detect the error but also locate it.

Adding redundant bits changes the ‘distance’ code parameter, known as the Hamming distance. Hamming distance is the number of bit differences between two code words.

For example, adding a single parity bit results in a code with a Hamming distance of at least one. In a threefold repetition code, the smallest Hamming distance is three. Increasing the Hamming distance improves the code’s error detection and correction abilities.

Therefore Hamming’s code was an attempt to increase the Hamming distance and at the same time to have as high information at a throughput rate as possible.

The algorithm for writing the generalized Hamming code is as follows:

1. The generalized form of code is P1P2D1P3D2D3D4P4D5D6D7D8D9D10D11P5, where P and D respectively represent parity and data bits.
2. We can see from the generalized form of the code that all bit positions that are powers of 2 (positions 1, 2, 4, 8, 16) are used as parity bits.
3. All other bit positions (positions 3, 5, 6, 7, 9, 10, 11) are used to encode data.
4. A group of bits from the data bits in the code word is allotted to each parity bit, and the value of the parity bit which is 0 or 1 is used to give it certain parity to make the operation smooth.
5. Groups are formed by first checking N – 1 bits and then alternately skipping and checking N bits\ following the parity bit. Here, N is the position of the parity bit; 1 for P1, 2 for P2, 4 for P3, 8 for P4 and so on. For example, for the generalized form of code given above, various groups of bits formed with different parity bits would be P1D1D2D4D5, P2D1D3D4D6D7, P3D2D3D4D8D9, P4D5D6D7D8D9 D10D11 and so on. To illustrate the formation of groups further, let us examine the group corresponding to parity bit P3. Now, the position of P3 is at number 4. In order to form the group, we check the first three bits (N − 1 = 3) and then follow it up by alternately skipping and checking four bits (N = 4).

Hamming codes can correct single-bit errors in messages of any length. While they can detect two-bit errors, they cannot locate them.

The number of parity bits required to be transmitted along with the message, however, depends upon the message length, as shown above. The number of parity bits required to encode message bits is the smallest integer that satisfies the condition (2ⁿ – n) > m.