User Rating:  / 0

PoorBest 

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

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

checksum

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 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

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

Reading Sections

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