Spread Knowledge

CS601 - Data Communication - Lecture Handout 34

User Rating:  / 0
PoorBest 

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

Error Detection And Correction Methods

Longitudinal Red Check(LRC)

  • In LRC, a block of bits is organized in a table (rows and columns)
  • For example instead of sending 3 its, we organize them in a table made of 4 rows and 8 columns

Longitudinal Red Check()

  • We then calculate the Parity bit for each column and create a new row of 8 bits which are the parity bits for the whole block
  • Note that the first parity bit in the 5th row is calculated based on all the first bits
  • The second parity bit is calculated based on all the second bits and so on
  • We then attach the 8 parity bits to the original data and send them to the receiver

Example 9.4

Suppose the following block is sent:

Example 9.4

  • It is hit by a burst of length 8 and some bits are corrupted:

Example 9.4 1

  • Receiver checks LRC, some of bits do not follow even parity rule and whole block is discarded

Example 9.4 2

Performance of LRC

  • Burst errors can be detected more often
  • As shown in the last example, an LRC of ‘n; bits can easily detect a burst error of ‘n’ bits
  • A burst error of more than ‘n’ bits is also detected by LRC with a very high probability
  • One pattern of errors remain elusive
  • If two bits in one data unit are changed and two bits in exactly the same place in another data unit are also damaged

For Example:

  • Original data units
    11110000
    11000011
  • Changed data units

01110001

01000010

Cyclic Redundancy Check (CRC)

  • Most powerful of checking techniques
  • VRC and LRC are based on Addition
  • CRC is based on Binary Division
  • A sequence of redundant bits called CRC or CRC remainder is appended to the end of the data unit, so that the resulting data unit becomes exactly divisible by a second predetermined binary number
  • At its destination, the data unit is divided by the same number
  • If at this step, there is no remainder, the incoming data unit is assumed to be intact and is therefore accepted
  • A remainder indicates that a data unit has been damaged and therefore must be rejected

Qualities of CRC

  • To be valid the CRC must have two qualities:
    • It must have exactly one less bit than the divisor
    • Appending it to the end of the data must make the resulting bit sequence exactly dile by the divisor

Qualities of CRC

  • First a string of n 0’s is appended to the data unit
  • The number ‘n’ is one less than the number of bits in the predetermined divisor, which is n+1 bits
  • Seconly, newly elongated data unit is divided by the divisor using a process called binary divsion. The remainder resulting from this division is the CRC
  • Third,the CRC of ‘n’ bits replaces the appended 0’s at the end of the data unit
  • Note that CRC may consist of all zeros
  • The data unit arrives at the receiver followed by the CRC
  • The receiver treats the whole string as a unit and divides it by the same divisor that was used to find the CRC remainder
  • If string arrives without an error, the CRC checker yields a remainder of zero and data unit passes
  • If the sting has been changed in transit, the division yields a non-zero remainder and the data unit does not pass

The CRC Generator

  • Uses Modulo-2 Division

The CRC Generator

The CRC Checker

  • Functions exactly like CRC Generator

The CRC Checker

Polynomials

  • CRC generator ( the divisor) is most often represented not as a string of 1’s and 0’s but as an algebraic polynomial
  • The polynomial format is useful for two reasons:
    • It is short
    • Can be used to prove the concept mathematically

Selection of a Polynomial

  • A polynomial should have the following properties:
    • It should not be divisible by ‘x’
    • It should be divisible by ‘x+1’

 

  • The first condition guarantees that all burst errors of a length equal to the degree of the polynomial are detected
  • The 2nd guarantees that all burst errors affecting an odd number of bits are detected

Selection of a Polynomial

Popular Polynomials for CRC

Popular Polynomials for CRC

Performance of CRC

  • CRC can detect all burst errors that affect an odd number of errors
  • CRC can detect all burst errors of length less than or equal to the degree of the polynomial
  • CRC can detect with a very high probability burst errors of length greater than the degree of the polynomial

Example 9.6

Example 9.6

  • All burst errors affecting odd no. of bits
  • All burst errors with a length equal to or less than 12
  • 99.97 % of the time burst errors with a length of 12 or more

Summary

  • Types of Redundancy Checks
  • Longitudinal Redundancy Check (LRC)
  • Cyclic Redundancy Check (CRC)

Reading Section

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