In telecommunication, a Hamming code is a linear error-correcting code named after its inventor, Richard Hamming. Hamming codes can detect up to two simultaneous bit errors, and correct single-bit errors; thus, reliable communication is possible when the Hamming distance between the transmitted and received bit patterns is less than or equal to one. By contrast, the simple parity code cannot correct errors, and can only detect an odd number of errors.

The key to the Hamming Code is the use of extra parity bits to allow the identification of a single error. Create the code word as follows:

- Number the bits starting from 1: bit 1, 2, 3, 4, 5, etc.
- Write the bit numbers in binary. 1, 10, 11, 100, 101, etc.
- All bit positions that are powers of two (have only one 1 bit in the binary form of their position) are parity bits.
- All other bit positions, with two or more 1 bits in the binary form of their position, are data bits.
- Each data bit is included in a unique set of 2 or more parity bits, as determined by the binary form of its bit position.

*Parity bit 1 *covers all bit positions which have the least significant bit set: bit 1 (the parity bit itself), 3, 5, 7, 9, etc.

*Parity bit 2* covers all bit positions which have the second least significant bit set: bit 2 (the parity bit itself), 3, 6, 7, 10, 11, etc.

*Parity bit 4* covers all bit positions which have the third least significant bit set: bits 4-7, 12-15, 20-23, etc.

*Parity bit 8* covers all bit positions which have the fourth least significant bit set: bits 8-15, 24-31, 40-47, etc.

In general each parity bit covers all bits where the binary AND of the parity position and the bit position is non-zero.

**Example**

A byte of data: **10011010**

Create the data word, leaving spaces for the parity bits: _ _ 1 _ 0 0 1 _ 1 0 1 0

Calculate the parity for each parity bit (a ? represents the bit position being set):

- Position 1 checks bits 1,3,5,7,9,11:

**?**_**1**_**0**0**1**_**1**0**1**. Even parity so set position 1 to a 0:**0**_**1**_**0**0**1**_**1**0**1**0 - Position 2 checks bits 2,3,6,7,10,11:

0**? 1****0 1**_ 1**0 1**0. Odd parity so set position 2 to a 1: 0**1 1**_ 0**0 1**_ 1**0 1**0 - Position 4 checks bits 4,5,6,7,12:

0 1 1**? 0 0 1**_ 1 0 1**0**. Odd parity so set position 4 to a 1: 0 1 1**1 0 0 1****0** - Position 8 checks bits 8,9,10,11,12:

0 1 1 1 0 0 1**? 1 0 1 0**. Even parity so set position 8 to a 0: 0 1 1 1 0 0 1**0 1 0 1 0**

- Code word:
**011100101010**.

**Finding and fixing a bad bit**

The above example created a code word of 011100101010. Suppose the word that was received was 011100101110 instead. Then the receiver could calculate which bit was wrong and correct it. The method is to verify each check bit. Write down all the incorrect parity bits. Doing so, you will discover that parity bits 2 and 8 are incorrect. It is not an accident that 2 + 8 = 10, and that bit position 10 is the location of the bad bit. In general, check each parity bit, and add the positions that are wrong, this will give you the location of the bad bit.

*Source :*

http://en.wikipedia.org/wiki/Hamming_code#Encoding

http://users.cs.fiu.edu/~downeyt/cop3402/hamming.html

hey thanks buddy…i really got everything…..

hey you summarized this very concisely, why didn’t you try to impress us with some cool matrix transposes, again nice job I now understand this simple crap!