Error detection and correction deal with one or multiple bits flipped during transmission from a sender to a receiver. Saying that ‘an error occurred’ does include the case of multiple bit flips. Such errors are very common on the physical layer if a bit is flipped when being transmitted, especially if the transmission is wireless.
Error detection or correction are then applied by the data link layer to provide reliable transmission to the network layer. Furthermore, routers on the network layer may introduce bit flips while relaying data. The transport layer is responsible for detecting and correcting these errors if a reliable data stream is desired.
Error detection means that the receiver can identify that there has been an error but they are typically not able to tell which error occurred. As a consequence, the sender has to be given a signal that they have to retransmit the message. Signals can be explicit requests for retransmission.
Alternatively, receivers may acknowledge correctly received data. If such an acknowledgement is not received within a certain time, the sender retransmits. In contrast, error correction allows the receiver to identify the exact bit or bits that have been flipped. The receiver can hence correct the error without retransmission.
Note that no algorithm can detect or correct all errors; error detection and correction only considerably reduce the probability of errors to be forwarded to the next higher layer. For this purpose, these algorithms add additional bits, creating redundancy that allows the receiver to detect or correct errors.
The number of additional bits added is referred to as the amount of redundancy. Usually this amount of redundancy is given as additional bits per data amount or as a percentage of extra data. For example, consider an algorithm that adds 9 bits to every message of 100 bits. The amount of redundancy is 9 bits per 100 bits or 9%. Instead of amount of redundancy, the term overhead can be used. Note that overhead is not a synonym of amount of redundancy but a more general term that can refer to any additional bits added to the actual message, e.g., information about the protocol version used or flag bytes that indicate the beginning of a frame on the data link layer.
The choice of a suitable error detection or error correction algorithm depends on multiple factors. The higher the amount of redundancy is, the more errors can be detected. However, a higher amount of redundancy means that more data needs to be transmitted, which can cause longer delays or overload the network. If one can tell based on measurements that errors are rare, an algorithm with a low redundancy is hence preferable. Error correction has a lower latency as it does not require retransmission. Yet, for the same amount of redundancy, error correction has a higher chance to accidentally forward an incorrect message than error detection, as we will illustrate on the example of Hamming codes later on. So the choice depends on trading off the requirements for error probability, bandwidth, and latency.
In this section, we first discuss parity bits, a simple error detection algorithm that appends one bit to the message. Afterwards, we discuss parity words and checksums, which extend parity bits to append multiple bits. Last, we move to a more advanced error detection algorithm, the cyclic redundancy check (CRC), which is based on polynomial division with binary coefficients.