Hamming Code

What is Hamming code?

Hamming code is a category of error correcting codes that developed by Richard Hamming. Parity checking was already being used to detect errors in the calculations of the relay-based computers of the day, and Hamming realized that a more sophisticated pattern of parity checking allowed the correction of single errors along with the detection of double errors.

These codes were originally designed with d _min=3, which mean that they can detect up to two errors or correct one single error. In simple parity check cannot correct the errors and can detect an odd number errors.

First of all we need to know the relationship between n and k in a hamming code. We need to choose an integer m >3. The values of n and k are then calculated from m as n = 2^m-1 and r = n-m. The number of check bits r = m.
To calculate the number of redundancy bits  use : 2^m ≥ n + m + 1

Example: If m=3, then n=7 and k=4. This is a hamming code C(7,4) with d _min=3. Figure below is the number of redundancy bits r.

Step to calculating Hamming code:

1. Check the total of bits of data (Number of data bits +Number of redundancy bits)
• For example if the number of bits provided is 11 , and ask you to check using hamming code
• The redundancy bit would be 4 bit and the data bits would be 6 bit
2. Mark the redundancy bit (Note: the bit can be start from left or right so solve it with your own standard but mine would be calculate from right )
• redundancy bit is position where power of 2.
• 2⁰->1,2¹->2,2²->4 and so on
• Example of position of redundancy bit if the total bits is 11 (the redundancy bit are Bold)
• 11010010110
• The others bit are data bit. (position start from right :3,5,6,7,9,10)
3. The redundancy bit on each position determines the sequence of bits that it alternately. (Note the redundancy check from the right is different from left )
• -----------------------------redundancy bit start from right------------------------------------
• General rule for position n: skip n−1 bits, check n bits, skip n bits, check n bits...
• position 1(n=1): Skip 0 bit,check 1 bit(n),skip 1 bit(n),check 1 bit(n),skip 1 bit(n),etc(1,3,5,7,9)
• Position 2 (n=2): skip 1 bit (1=n−1), check 2 bits (n), skip 2 bits (n), check 2 bits (n), skip 2 bits (n), etc. (2,3,6,7,10,11...)
• Position 4 (n=4): skip 3 bits (3=n−1), check 4 bits (n), skip 4 bits (n), check 4 bits (n), skip 4 bits (n), etc. (4,5,6,7,12...)
• Position 8 (n=8): skip 7 bits (7=n−1), check 8 bits (n), skip 8 bits (n), check 8 bits (n), skip 8 bits (n), etc. (8-15,24-31,40-47,...)
• --------------------------redundancy bit start from left----------------------------------
• Position 1: check 1 bit, skip 1 bit, check 1 bit, skip 1 bit, etc. (1,3,5,7,9,11,13,15,...)
• Position 2: check 2 bits, skip 2 bits, check 2 bits, skip 2 bits, etc. (2,3,6,7,10,11,14,15,...)
• Position 4: check 4 bits, skip 4 bits, check 4 bits, skip 4 bits, etc. (4,5,6,7,12,13,14,15,20,21,22,23,...)
• Position 8: check 8 bits, skip 8 bits, check 8 bits, skip 8 bits, etc. (8-15,24-31,40-47,...)
4. Set a parity bit to 1 if the total number of ones in the position it check is odd. Set a parity bit to 0 if the total number of ones in the positions it check is even.