CS601 - Data Communication - Lecture Handout 35

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

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

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

checksum

Example 9.8

  • Examples of no error and a burst error

Example 9.8

  • 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

Redundancy Bits (r)

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

Hamming Code

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