Error Detection and Correction

Now imagine the received data has 7th bit changed from 1 to 0.

Single-bit error

The receiver takes the transmission and recalculates four new data using the same set of bits used by the sender plus the relevant parity (r) bit for each set.

Error detection

Ø  Then it assembles the new parity values into a binary number in order of r position (r8,r4,r2,r1).

Ø  This step gives us the binary number 0111(7 in decimal) which is the precise location of the bit in error.

Ø  Once the bit is identified, the receiver can reverse its value and correct the error.

Hamming Distance

     One of the central concepts in coding for error control is the idea of the Hamming distance.

Ø  The Hamming distance between two words (of the same size) is the number of differences between the corresponding bits. The Hamming distance between two words x and y is d(x, y).

Ø  The Hamming distance can be found by applying the XOR operation on the two words and count the number of 1’s in the result.

Ø  In a set of words, the minimum Hamming distance is the smallest Hamming distance between all possible pairs. We use dmin to define the minimum Hamming distance in a coding scheme. 

Error Correction

Error Correction can be handled in two ways

1.     When an error is discovered, the receiver can have the sender to retransmit the entire data unit.

2.     A receiver can use an error correcting code, which automatically correct certain errors.

Error correcting codes are more sophisticated than error-detection codes and require more redundancy bits.

In single bit error detection only two states are sufficient.

1) error

2) no error

Two states are not enough to detect an error but not to correct it.

Redundancy Bits

Ø  To calculate the number of redundancy bit(r) required to correct a given number of data bits (m), we must find a relationship between m and r.

Ø  Add m bits of data with r bits. The length of the resulting code is m+r.

Data and Redundancy bits

Ø  If the total number of bits are m+r, then r must be able to indicate at least m+r+1 different states. r bits can indicate 2^r different states. Therefore, 2^r must be equal to or greater than m+r+1

2^r >=m+r+1

Ø  For example if the value of m is 7 the smallest r value that can satisfy this equation is 4.

 Relationship between data and redundancy bits

Number of Data Bits (m)	Number of redundancy Bits(r)	Total bits (m+r)
1	2	3
2	3	5
3	3	6
4	3	7
5	4	9
6	4	10
7	4	11

Hamming Code

R.W. Hamming provides a practical solution for the error correction.

Positioning the Redundancy Bits

For example, a seven-bit ASCII code requires four redundancy bits that can be added to the end of the data or intersperse with the original data bits. These redundancy bits are placed in positions 1, 2, 4 and 8. We refer these bits as r1, r2, r3 and r4

Position of redundancy bits in Hamming code

The combination used to calculate each of the four r values for a seven-bit data sequence are as follows

Ø  The r1 bit is calculated using all bits positions whose binary representation include a 1 in the rightmost position

Ø  r2 is calculated using all bit position with a 1 in the second position and so on

                    r1: bits 1,3,5,7,9,11

                    r2: bits 2, 3, 6, 7, 10, 11

                    r3: bits 4, 5, 6, 7

                    r4: bits 8, 9, 10, 11

Redundancy bits calculation

Calculating the r values

Ø  Place each bit of the original character in its appropriate position in the 11-bit unit.

Ø  Calculate the even parities for the various bit combination.

Ø  The parity value for each combination is the value of the corresponding r bit.

For example,

Ø  The value of r1 is calculated to provide even parity for a combination of bits 3,5,7,9 and 11.

Ø  The value of r2 is calculated to provide even parity with bits 3, 6, 7, 10 and 11.

Ø  The value of r3 is calculated to provide even parity with bits 4,5,6 and 7.

Ø  The value of r4 is calculated to provide even parity with bits 8,9,10 and 11.

Error Detection and Correction

Data can be corrupted during transmission. For reliable communication, errors must be detected and corrected.

Types of Errors

Single-bit error

The term Single-bit error means that only one bit of a given data unit (such as byte, character, data unit or packet) is changed from 1 to 0 or from 0 to 1.

Burst Error

The term Burst Error means that two or more bits in the data unit have changed from 1 to 0 or from 0 to 1.

Redundancy

             One method is to send every data twice, so that receiver checks every bit of two copies and detect error.

Drawbacks

Ø  Sends n-redundant bits for n-bit message.

Ø  Many errors are undetected if both the copies are corrupted.

Instead of adding entire data, some bits are appended to each unit.

             This is called redundant bit because the bits added will not give any new information. These bits are called error detecting codes.

The three error detecting techniques are:

Ø  Parity check

Ø  Check sum algorithm

Ø  Cyclic Redundancy Check

Parity Check

Simple parity check

             Only one redundant bit, called parity bit is added to every data unit so that the total number of 1’s in unit become even (or odd)

Two Dimensional Parity

Ø  It is based on simple parity.

Ø  It performs calculation for each bit position across each byte in the frame.

Ø 

This adds extra parity byte for entire frame, in addition to a parity bit for each byte.

            For example frame containing 6 bytes of data. In this third bit of the parity byte is 1 since there are an odd number of 1’s is in the third bit across the 6 bytes in the frame.

            In this case, 14 bits of redundant information are added with original information.

Check sum algorithm

Ø  In the sender side all the words are added and then transmit the result of sum called checksum with the data.

Ø  The receiver performs the same calculation on the received data and compares the result with the received checksum.

Ø  If any transmitted data, including the checksum itself, is corrupted, then the results will not match, so the receiver knows that an error occurred.

 Ø  Instead of sending the checksum as such, one’s complement of that sum will be send to the receiver. If the receiver gets the result as zero then it will be the correct one.

Ø  In this, we can represent unsigned number from 0 to 2ⁿ using n bits.

Ø  If the number has more than n bits, the extra leftmost bits need to be added to the n rightmost bits.

Ø  Data can be divided in to 16 bit word and the Checksum is initialized to zero.