4.18.4 How Do Error Detection and Error Correction Work?
- Why Do Communication Systems Need Error Control?
- What Is Error Detection?
- What Is Error Correction?
- How Does Redundancy Enable Error Detection?
- What Is a Codeword?
- What Is a Parity Bit?
- What Errors Can Parity Detect?
- What Is a Checksum?
- What Is a Cyclic Redundancy Check?
- Why Are CRCs So Effective?
- What Is Forward Error Correction?
- How Does Error Correction Work?
- What Is Hamming Distance?
- How Many Errors Can a Code Detect?
- How Many Errors Can a Code Correct?
- What Is a Syndrome?
- What Happens When Too Many Errors Occur?
- What Is Automatic Repeat Request?
- What Is Hybrid ARQ?
- When Is Error Correction Preferred?
- Where Are Error Detection and Correction Used?
- Why Are Error Detection and Error Correction Important?
Digital communication systems are designed to transfer information accurately from one location to another. Whether the information consists of voice, video, telemetry, financial transactions, computer data, or Internet traffic, the receiver must obtain a faithful representation of the transmitted message.
Unfortunately, communication channels are never perfect. Noise, interference, fading, synchronization errors, equipment faults, and other impairments can corrupt transmitted information. A single altered bit may change the meaning of a message, while multiple errors can render entire blocks of data unusable.
To overcome these problems, communication systems employ error detection and error correction techniques. These techniques add carefully structured redundancy to the transmitted data, allowing the receiver to determine whether errors have occurred and, in many cases, recover the original information.
Today, error-control coding is fundamental to virtually every communications technology, including mobile-phone networks, Wi-Fi systems, satellite communications, optical-fiber networks, digital television, computer storage devices, and deep-space spacecraft.
Why Do Communication Systems Need Error Control?
Every practical communication channel introduces errors.
Common sources include:
- Thermal noise.
- Atmospheric noise.
- Interference from other systems.
- Multipath propagation.
- Fading.
- Hardware faults.
- Storage-media defects.
- Synchronization problems.
These impairments can alter transmitted bits. For example, a transmitted sequence 1101001 might be received as 11011010 if one bit is corrupted.
Without additional information, the receiver cannot determine whether the received sequence is correct. Error-control techniques provide the information necessary to identify and, in many cases, correct such problems.
What Is Error Detection?
Error detection is the process of determining whether transmitted data has been corrupted.
The receiver examines the received data and determines whether it satisfies certain mathematical relationships established by the transmitter. If the relationships are violated, an error is declared.
Error detection answers the question: Has an error occurred? It does not necessarily answer: What was the correct data?
Examples of error-detection techniques include:
- Parity checks.
- Checksums.
- Cyclic redundancy checks (CRCs).
What Is Error Correction?
Error correction goes one step further.
Rather than merely detecting the presence of an error, the receiver attempts to determine which bits are incorrect and reconstruct the original message.
Error correction answers both questions: Has an error occurred? and What was the original information? This capability is especially valuable when retransmission is difficult or impossible. Examples include:
- Satellite communications.
- Deep-space communications.
- Broadcast television.
- Streaming media.
How Does Redundancy Enable Error Detection?
Error detection relies on redundancy.
The transmitter deliberately adds extra information to the message. These additional bits are mathematically related to the original data.
Suppose a simple system transmits: 1011. The encoder may generate: 10111 where the final bit is a parity bit. The receiver performs the same calculation. If the parity relationship is not satisfied, an error is declared.
The redundancy provides a means of verifying data integrity.
What Is a Codeword?
The combination of information bits and redundant bits is called a codeword.
For example: Information: 1011. Encoded codeword: 1011100. The receiver knows that valid transmissions must correspond to valid codewords. If the received pattern does not match a valid codeword, an error has occurred.
Codewords form the foundation of most error-control systems.
What Is a Parity Bit?
The simplest form of error detection uses a parity bit.
A parity bit is chosen so that the total number of ones in the transmitted codeword is either:
- Even (even parity).
- Odd (odd parity).
For example: Data: 1011. Number of ones: 3. Using even parity: Parity bit = 1. Transmitted codeword: 10111 which contains four ones.
The receiver checks the parity relationship. If the parity is incorrect, an error is detected.
What Errors Can Parity Detect?
Parity can detect any odd number of bit errors.
For example: 10111 becomes: 10110. The parity changes and the error is detected.
However, parity cannot detect even numbers of bit errors. This limitation makes parity suitable only for simple applications.
More powerful techniques are often required.
What Is a Checksum?
A checksum is another widely used error-detection technique.
The transmitter performs arithmetic operations on the data and appends the result. The receiver repeats the calculation. If the results differ, an error is declared. Checksums are commonly used in:
- Computer networks.
- File transfers.
- Internet protocols.
Although more powerful than simple parity, checksums are not perfect.
Certain error patterns may remain undetected.
What Is a Cyclic Redundancy Check?
The cyclic redundancy check (CRC) is one of the most widely used error-detection methods.
Rather than performing ordinary arithmetic, CRCs treat data as polynomials and perform polynomial division. The resulting remainder is appended to the message. At the receiver:
- The same division is performed.
- A non-zero remainder indicates an error.
CRCs provide extremely powerful error-detection capability and are widely used in:
- Ethernet.
- Wi-Fi.
- Satellite systems.
- Storage devices.
- Digital broadcasting.
Why Are CRCs So Effective?
CRCs can detect:
- All single-bit errors.
- All double-bit errors (for suitable polynomials).
- Most burst errors.
- Very large classes of multiple-bit errors.
The probability of an undetected error is typically extremely small.
As a result, CRCs have become the preferred error-detection technique in many modern systems.
What Is Forward Error Correction?
Forward error correction (FEC) refers to coding systems that allow the receiver to correct errors without retransmission. The transmitter adds sufficient redundancy to enable the decoder to reconstruct the original message.
Examples include:
- Hamming codes.
- Reed–Solomon codes.
- Convolutional codes.
- Turbo codes.
- LDPC codes.
- Polar codes.
FEC is essential when retransmission is undesirable or impossible.
How Does Error Correction Work?
Error correction relies on the fact that valid codewords are separated from one another by a certain minimum distance.
Suppose a code permits only 000000 and 111111 as valid codewords. If the receiver obtains 111110 it is much closer to 111111 than to 000000. The decoder therefore concludes that 111111 was probably transmitted.
More sophisticated codes apply the same principle using much larger sets of codewords.
What Is Hamming Distance?
The Hamming distance between two codewords is the number of bit positions in which they differ.
For example 101100 and 111000 differ in two positions. Their Hamming distance is therefore 2.
Hamming distance plays a central role in coding theory because it determines:
- Error-detection capability.
- Error-correction capability.
How Many Errors Can a Code Detect?
If a code has minimum distance dmin it can detect up to dmin - 1 errors.
For example:
| Minimum Distance | Detectable Errors |
|---|---|
| 2 | 1 |
| 3 | 2 |
| 4 | 3 |
| 5 | 4 |
Larger minimum distances provide stronger protection.
How Many Errors Can a Code Correct?
A code can correct: t = (dmin – 1)/2 errors.
Examples include:
| Minimum Distance | Correctable Errors |
|---|---|
| 3 | 1 |
| 5 | 2 |
| 7 | 3 |
This relationship is one of the most important results in coding theory.
What Is a Syndrome?
Many error-correcting codes use a quantity called a syndrome. In medical terms, a syndrome is a symptom of a disease.
The syndrome is computed from the received codeword. If S = 0 no error is detected. If S ≠ 0 an error is present.
For many codes, specific syndrome values correspond to specific error patterns which allows the decoder to identify and correct errors efficiently.
What Happens When Too Many Errors Occur?
Every code has finite capability.
If the number of errors exceeds the correction capability:
- The decoder may fail.
- An incorrect correction may be made.
- Retransmission may be required.
Consequently, coding systems are designed so that uncorrectable errors occur very rarely.
What Is Automatic Repeat Request?
Automatic repeat request (ARQ) is an alternative approach to reliability.
Instead of correcting errors directly, the receiver:
- Detects the error.
- Requests retransmission.
ARQ is widely used in:
- Computer networks.
- Internet protocols.
- Wireless data systems.
ARQ works well when retransmission is practical.
What Is Hybrid ARQ?
Hybrid ARQ combines:
- Error correction.
- Retransmission.
The receiver first attempts correction. If correction fails, retransmission is requested.
Modern mobile-phone networks make extensive use of Hybrid ARQ because it combines high reliability with efficient spectrum utilization.
When Is Error Correction Preferred?
Error correction is preferred when:
- Retransmission is impossible.
- Latency must be minimized.
- Round-trip delay is large.
Examples include:
- Satellite systems.
- Deep-space communications.
- Broadcast television.
- Real-time streaming.
In these applications, waiting for retransmissions may be impractical.
Where Are Error Detection and Correction Used?
Virtually every digital system employs some form of error control.
Examples include:
- Mobile networks. 4G and 5G systems rely heavily on advanced coding.
- Wi-Fi systems. Error detection and correction improve reliability in noisy environments.
- Satellite communications. Powerful FEC codes compensate for long propagation distances.
- Optical-fiber networks. Coding helps achieve extremely low error rates.
- Hard drives and SSDs. Error correction protects stored information.
- Digital television. Coding enables reliable reception despite interference and fading.
- Deep-space missions. Spacecraft rely on powerful coding to communicate across enormous distances.
Few technologies are as universally applied in modern communications.
Why Are Error Detection and Error Correction Important?
Error-control techniques make reliable digital communication possible.
Without them:
- Mobile-phone calls would be less reliable.
- Internet connections would be slower.
- Satellite links would require much higher power.
- Storage systems would suffer frequent corruption.
- Deep-space exploration would be severely constrained.
By adding carefully structured redundancy, communication systems can detect and correct errors that would otherwise make reliable information transfer impossible.
Summary
Error detection and error correction are techniques that protect digital information against corruption caused by noise, interference, fading, and other channel impairments. Error detection determines whether an error has occurred, while error correction attempts to reconstruct the original information automatically.
Techniques such as parity checks, checksums, CRCs, Hamming codes, Reed–Solomon codes, convolutional codes, LDPC codes, and polar codes form the foundation of modern error-control systems. Together they enable the reliable operation of communication networks, storage systems, satellite links, wireless networks, and countless other digital technologies.
Back to reading