# CS601 - Data Communication - Lecture Handout 35

User Rating:     / 0
PoorBest

# Error Correction And Detection Method

## CHECKSUM

• Error detection method used by the Higher Layers
• Like VRC, LRC, CRC, Checksum is also based on the concept of redundancy

## One’s Complement

Finding one’s complement

• Invert every 1 to 0 and 0 to 1
• A and –A are one’s complement of each other
• +A = 1010 → -A = 0101
• +0 = 0000 → -0 = 1111

• Error detection method used by the Higher Layers
• Like VRC, LRC, CRC, Checksum is also based on the concept of redundancy

## CHECKSUM Generator • The sender subdivides data units into equal segments of ‘n’ bits(16 bits)
• These segments are added together using one’s complement
• The total (sum) is then complemented and appended to the end of the original data unit as redundancy bits called CHECKSUM
• The extended data unit is transmitted across the network
• The receiver subdivides data unit as above and adds all segments together and complement the result
• If the intended data unit is intact, total value found by adding the data segments and the checksum field should be zero
• If the result is not zero, the packet contains an error & the receiver rejects it

## Checksum Figure ### Performanceof Checksum

• Detects all errors involving an odd number of bits
• Detects most errors involving an even number of bits
• One pattern remains elusive

## Examples

### Example 9.7 ### Example 9.8

• Examples of no error and a burst error • Error is invisible if a bit inversion is balanced by an opposite bit inversion in the corresponding digit of another segment

Segment1 10111101

Segment2 00101001

Checksum 00011001

Sum 11111111

• The error is undetected

## ERROR CORRECTION

• Mechanisms that we have studied all detect errors but do not correct them
• Error correction can be done in two ways:
• Receiver can use an error-detecting code, which automatically correct certain errors
• Error correcting code are more sophisticated than error detecting codes
• They require more redundancy bits
• The number of bits required to correct multiple –bit or burst error is so high that in most cases it is inefficient
• Error correction is limited to 1, 2 or 3 bit

### Single-bit Error Correction

Simplest case of error correction

• Error correction requires more redundancy bits than error detection
• One additional bit can detect single-bit errors
• Parity bit in VRC
• One bit for two states: error or no error
• To correct the error, more bits are required
• Error correction locates the invalid bit or bits
• 8 states for 7-bit data : no error, error in bit 1, and so on
• Looks like three bits of redundancy is adequate
• What if an error occurs in the redundancy bits?

## Hamming Code

### Redundancy Bits (r)

• r must be able to indicate at least m+r+1 states
• m+r+1 states mus boverable by r bits
• Therefore, 2r ≥ m+r+1
• If m=7, r=4 as 24 ≥ 7+4+1 ### Hamming Code

• Each r bit is the VRC bit for one combination of data bits
• rit is calculated using all bit positions whose binary representation includesa 1 in the first(second) position, and so on ## Summary

• Checksum
• Single-Bit Error Correction
• Haming Code