Wednesday, 8 October 2014

Hamming Code

Data Error

Data error is term which occurs when we send data and it’s not received as we send.

Error Type

There are two type of error single bit and multiple bits (Burst)

Error detection and Correction

Error detection technique are user detect an error on the other hand error correction technique enable us to resolve an error. We can remove one, two and three bit error only because burst error may occur extremely.

Hamming code

Hamming code is a set of error-correction code s that can be used to detect and correct bit errors that can occur when computer data is moved or stored. Hamming code is named for R. W. Hamming of Bell Labs.

Single bit error correction

A single bit error can be detected by the addition of a redundant (parity) bit to the data unit (VRC). A Single additional bit can detect single bit error in any sequence of bits because it must distinguish between only two condition : Error or no Error A bit has two state (0 and 1).These two state are sufficient for this level of detection.

Bit Selection Logic

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,...)
Position 16: check 16 bits, skip 16 bits, check 16 bits, skip 16 bits, etc. (16-31,48-63,80-95,...)
Position 32: check 32 bits, skip 32 bits, check 32 bits, skip 32 bits, etc. (32-63,96-127,160-191,...)

Redundancy Bits

To calculate the number of redundancy bits (r) required to correct a given number of data bits (m), we must find a relationship between m and r.
Positioning the redundancy bits
The Hamming code can be applied to data unit of any length and uses the relationship between data and redundancy bits.For Example a seven bit ASCII

Calculating the r Values

Figure shows a Hamming code implementation for an ASCII character. In the first
step, we place each bit of the original character in its appropriate position in the 1l-bit
unit. In the subsequent steps, we calculate the even parities for the various bit combina-
tions. The parity value for each combination is the value of the corresponding r bit- For
example, the value of r, is calculated to provide even parity for a combination of bits 3,
5,7,9, and ll.Thevalueof r2 is calculated to provide even parity with bits 3,6,7,10,
and 11 , and so on. The final 1 I -bit code is sent through the transmission line.

Error Detection and Correction

Now imagine that by the time the above transmission is received, the number 7 bit has
been changed from 1 to 0 .The receiver takes the transmission and recalculates four new VRC using the same sets of bits used by the sender plus the relevant parity (r) bit for each set.Then it is assembles the new parity values into a binary number in order of r position(r8,r4,r2,r1). In our example gives us the binary number 0111 (7 in decimal). which is the best precise location of the bit in error.
once the bit is identified , the receiver can reverse its value and correct the error