**Related Content:** CS601 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Data Communication

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

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

- 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

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

- 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

- Mechanisms that we have studied all detect errors but do not correct them
- Error correction can be done in two ways:
- Receiver can ask Sender for Re- TX
- 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

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?

- 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

- 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

- Checksum
- Single-Bit Error Correction
- Haming Code

- Section 9.6, 9.7, “Data Communications and Networking” 4th Edition by Behrouz A. Forouzan