Hamming Code

Posted: April 15, 2009 in Computer, Mathematics
Tags: ,

binarykey1

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:

  1. Number the bits starting from 1: bit 1, 2, 3, 4, 5, etc.
  2. Write the bit numbers in binary. 1, 10, 11, 100, 101, etc.
  3. All bit positions that are powers of two (have only one 1 bit in the binary form of their position) are parity bits.
  4. All other bit positions, with two or more 1 bits in the binary form of their position, are data bits.
  5. 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 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 _ 1 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

Comments
  1. nitin says:

    hey thanks buddy…i really got everything…..

  2. bruce says:

    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!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s