Principles of The Data Link Layer: Error Detection

This lesson will go into depth with how the data link layer does error detection

We'll cover the following

Error Detection Codes

Besides framing, the data link layer also includes mechanisms to detect and sometimes even recover from transmission errors.

To allow a receiver to detect transmission errors:

  1. A sender must add some redundant information (some rr bits) as an error detection code to the frame sent. This error detection code is computed by the sender on the frame that it transmits.

  2. When the receiver receives a frame with an error detection code, it recomputes it and verifies whether the received error detection code matches the computed error detection code.

  3. If they match, the frame is considered to be valid.

Many error detection schemes exist and entire books have been written on the subject. A detailed discussion of these techniques is outside the scope of this course, and we will only discuss some examples to illustrate the key principles.

To understand error detection codes, let us consider two devices that exchange bit strings containing N bits. To allow the receiver to detect a transmission error:

  1. The sender converts each string of NN bits into a string of N+rN+r bits.
  2. Usually, the rr redundant bits are added at the beginning or the end of the transmitted bit string, but some techniques interleave redundant bits with the original bits.
  3. An error detection code can be defined as a function that computes the rr redundant bits corresponding to each string of NN bits.

Parity Bit

The simplest error detection code is the parity bit. In this case, the number of redundant bits is 1. There are two types of parity schemes:

  1. Even parity: With the even parity scheme, the redundant bit is chosen so that an even number of bits are set to 1 in the transmitted bit string of N+1N+1 bits.

  2. Odd parity: With the odd parity scheme, the redundant bit is chosen so that an odd number of bits are set to 1 in the transmitted bit string of N+1N+1 bits.

The receiver can easily recompute the parity of each received bit string and discard the strings with an invalid parity. The parity scheme is often used when 7-bit characters are exchanged. In this case, the eighth bit is often a parity bit.

Example

The table below shows the parity bits that are computed for bit strings containing three bits.

3 bits string Odd parity Even parity
000 1 0
001 0 1
010 0 1
100 0 1
111 0 1
110 1 0
101 1 0
011 1 0

The parity bit allows a receiver to detect transmission errors that have affected a single bit among the transmitted N+1N+1 bits. If there are an even number of bits in error, the errors wouldn’t be detected. An odd number of errors will still be detected.

Error Correction Mechanisms

It is also possible to design a code that allows the receiver to correct transmission errors.

Triple Modular Redundancy (TMR)

The simplest error correction code is the triple modular redundancy (TMR).

  • To transmit a bit set to 11, the sender transmits 111111 and to transmit a bit set to 00, the sender transmits 000000.
  • When there are no transmission errors, the receiver can decode 111111 as 11.
  • If transmission errors have affected a single bit, the receiver performs majority voting as shown in the table below. This scheme allows the receiver to correct all transmission errors that affect a single bit.
Received bits Decoded bit
000 0
001 0
010 0
100 0
111 1
110 1
101 1
011 1

Other Techniques

Other more powerful error correction codes have been proposed and are used in some applications. The Hamming Code is a clever combination of parity bits that provides error detection and correction capabilities.

In practice, data link layer protocols combine bit stuffing or character stuffing with a length indication in the frame header and a checksum. The checksum is computed by the sender and placed in the frame before applying bit/character stuffing.

Please attempt the question in the widget below. Our AI will evaluate your answer.

What would be the drawbacks of error detection and correction?

Quick Quiz!

1

What would be the parity bit for the following string in an odd parity scheme?

100101001100101001

A)

0

B)

1

Question 1 of 30 attempted

Get hands-on with 1400+ tech skills courses.