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
- Original data units
11110000
11000011 - Changed data units
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