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

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

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

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

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

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

• Functions exactly like CRC Generator

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

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

• 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

• < Prev
• Next >