Introduction to Error Control

Transmission Errors

A communication channel, whether it uses copper cable, an optical-fiber link, or a wireless link, is exposed to noise, interference, and other disturbances during transmission. These impairments can corrupt the signal and cause the receiver to interpret one or more data bits incorrectly.

A bit erroroccurs when a transmitted '1' is received as a '0', or the reverse. Its effect depends on the field or sample that contains the bit, so a receiver needs an error-control method to detect or correct corrupted data. The number and distribution of errors also affect which coding method is appropriate. Data integrity is a central requirement in telecommunications.

Redundancy in Error Control

A basic strategy for handling transmission errors is to introduce redundancy. This means adding extra information to the original data stream according to specific coding rules. The receiver uses this information to determine whether the data arrived correctly and, with an error-correcting code, to reconstruct a permitted number of corrupted bits.

The receiver recomputes the check relation from the received block and compares it with the redundancy sent with that block. A mismatch indicates that the block requires rejection or correction, depending on the code.

ARQ: Detection and Retransmission

This approach, known as ARQ (Automatic Repeat reQuest), uses a feedback channel. The receiver reports whether the block passed the check, and the sender transmits the next block or repeats the corrupted block.

1. The sender sends a block of data along with some redundancy (e.g., a checksum).
2. The receiver checks if the data is correct using the redundant information.
3. If the data is correct, the receiver sends a positive acknowledgement (ACK). The sender then sends the next block.
4. If the data is corrupted, the receiver sends a negative acknowledgement (NACK). The sender then retransmits the block.

ARQ can recover corrupted blocks when a return path and retransmission procedure remain available. TCP uses acknowledgements and retransmissions for reliable byte-stream delivery. Each retransmission adds delay, which limits efficiency on links with frequent errors or long propagation times, including some satellite links.

FEC: Forward Error Correction

This method, called FEC (Forward Error Correction), places error correction at the receiver. The sender adds enough redundant information for the receiver to detect and correct a specified number of errors independently.

This is useful when a feedback channel is unavailable or impractical:

• One-way broadcasts: Such as digital television or radio.
• High-latency links: Such as communication with deep-space probes, where a retransmission would add a long propagation delay.
• Real-time systems: Where there is no time to wait for a retransmission, such as in streaming audio/video.

Hamming Distance in Error Control

The ability of a code to detect and correct errors is determined by its minimum Hamming distance ($d_{min}$). A larger distance between valid code words increases the number of errors a decoder can tolerate before ambiguity occurs.

Detection and Correction Conditions

1. For Error Detection: To be able to detect up to $e$ bit errors in a code word, the minimum Hamming distance of the code must be:

   $d_{min} \ge e + 1$

   For example, a simple parity bit creates a code with $d_{min} = 2$, so it can reliably detect $e=1$ single bit error.
2. For Error Correction: To be able to correct up to $t$ bit errors in a code word, the minimum Hamming distance of the code must be:

   $d_{min} \ge 2t + 1$

   For example, a simple repetition code (like sending '000' for '0' and '111' for '1') has a $d_{min} = 3$. This code can correct $t=1$ single bit error.