Principles of The Data Link Layer: Error Detection

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 $r$ 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 $N$ bits into a string of $N+r$ bits.
2. Usually, the $r$ 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 $r$ redundant bits corresponding to each string of $N$ bits.