Faulty data is not good

A lot of things can go wrong during the transmission of data, which can be lost or parts of it corrupted. One job of the second osi layer is to identify and handle these cases correctly.

Depending on the medium different bit error ratios are to be expected:

• Digital telephone networks: from 10^{-6} to 10^{-7}
• Coaxial cables: 10^{-9}
• Fiber-optic cables: 10^{-12}

Cyclic redundency checks

Error detection can happen by attaching a checksum to the data frame. The cyclic redundancy check (CRC) is used to calculated or validate the Frame Check Sequence (checksum). This method does not provide any information about which parts of the data are corrupted, so backwards error correction needs to be applied if data is corrupted.

This is done by interpreting the messages as a polynomial M(x) and a generator polynomial G(x). First multiply the the message polynomial with the highest term of the generator polynomial and divided by the generator polynomial M(x) \cdot x^n \div G(x), which results in a quotient and a remainder R(x). The transfer polynomial T(x) is M(x) \cdot x^n + R(x).

All arithmetic is performed in GF(2) (the Galois Field with two elements), meaning addition and subtraction are both equivalent to XOR, and there are no carries. This makes CRC computations efficient to implement in hardware.

The multiplication with the highest term of the generator polynomial x^n is done to append n-1 placeholder (zero) bits to the message, making room for the checksum remainder R(x) to be written into those positions, guaranteeing that the final transmitted codeword is divisible by G(x).

To check if the message was sucessfully transmitted the receiver has to devide T(x) with G(x). If the result is 0 the message was probably transmitted correctly.

Parity checks

Checks based on additional information being added to a data block. For every horizontal row we get one additional parity bit, which is 1 if the number of 1's is odd. The same applies for every vertical column.

This aforementioned rule is inverted if an odd parity system is used:

• Even parity: Number of bits is odd = 1
• Odd parity: Number of bits is odd = 0

These can be used to pin point the corrupted bit. By checking the horizontal parity we can determine that at least one bit in this row has to be corrupted, afterwards we can look up the exact column by checking each vertical parity bit.

After correcting all corrupted bits the receiver can send an acknowledgement, which is referred to as forward error correction.

Backwards error correction

If corrupted data can be detected but not corrected on the receiver machine the sender needs to resend the data frame. This process is referred backwards error correction.

The receiver system does not send a negative acknowledgement for the data to be re-transmitted by the sender.

Forward error correction

If corrupted data can be detected and corrected on the receiver machine, the receiver does simply send an ack. This process is referred to as forward error correction.