# CS601 - Data Communication - Lecture Handout 34

User Rating:  / 0
PoorBest

# 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

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