Error Detection and Correction

1. Implemented either at the data link layer or the transport layer of the OSI model.

2. Types of errors
   • Single-bit errors is when only one bit of a given data unit is changed. They are the least likely type of error in serial data transmission.

   • Burst errors occur when there is a change in two or more bits, which do not have to be consecutive. It is most likely to happen in serial transmission.

3. Detection
   • Redundancy is a technique when extra bits are appended to a data unit.

   • Vertical redundancy check (VRC) or parity check is when a redundant bit, or parity bit is appended to every data unit so that the total number of 1s is odd (odd parity) or even (even parity). It can detect all single-bit errors, but cannot detect errors when the total number of bits changed is even.

   • In longitudinal redundancy check (LRC) a block of bits is organized in a table. The parity bit is calculated for each column and a new row of eight bits is created, which are the parity bits for the whole block. Increased likelihood of detecting burst errors.

   • Cyclic Redundancy Check (CRC)
     • Based on binary division, a sequence of redundant bits, called the CRC or the 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.

     • The CRC generator (the divisor) is often represnted as an algebraic polynomial. It should not be divisible by x (binary 10) and 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 second condition guarantees that all burst errors affecting an odd number of bits are detected.

     • Can detect all burst errors that affect an odd number of bits.

     • Can detect all burst errors of length less than or equal to the degree of the polynomial.

     • Can detect with very high probability burst errors of length greater than the degree of the polynomial.

   • Checksum
     • In the sender, the checksum generator subdivides the data unit into equal segments of n bits. These segments are added together using one's complement arithmetic so that the total is n bits long. The total is then complemented and appended to the end of the original data unit as redundancy bits, called the checksum field. The extended data unit is transmitted across the network.

     • The receiver subdivides the data unit and adds all segments together and complements the result. If the extended data unit is intact, the total value found by adding the data segments and the checksum field should be zero.

     • Detects all errors involving an odd number of bits, as well as most errors involving an even number of bits.

4. Error correction can be handled in two ways. In one, when an error is discovered, the receiver can have the sender retransmit the entire data unit. In the other, a receiver can use an error-correcting code, which automatically corrects certain errors. The Hamming code can be applied to data units of any length and uses the relationship between data and redundancy bits.