4.18.6 What Are Parity Bits, Checksums, and CRCs?
- What Is Error Detection?
- Why Is Error Detection Necessary?
- What Is Redundancy?
- What Is a Parity Bit?
- How Does Even Parity Work?
- How Does Odd Parity Work?
- What Errors Can Parity Detect?
- What Errors Can Parity Miss?
- Where Is Parity Used?
- What Is a Checksum?
- How Does a Checksum Work?
- Why Are Checksums Better Than Parity?
- Where Are Checksums Used?
- What Is a Cyclic Redundancy Check?
- Why Is It Called a Cyclic Redundancy Check?
- How Does CRC Generation Work?
- What Is Modulo-2 Arithmetic?
- What Is a Generator Polynomial?
- Why Are CRCs So Effective?
- What Is a Burst Error?
- Why Are CRCs Preferred in Modern Systems?
- Where Are CRCs Used?
- Can Error Detection Correct Errors?
- What Happens When an Error Is Detected?
- How Do Parity, Checksums, and CRCs Compare?
- Why Are Parity Bits, Checksums, and CRCs Important?
Whenever information is transmitted across a communication channel or stored in a digital device, there is always the possibility that errors may occur. Noise, interference, fading, synchronization problems, hardware faults, and storage-media defects can all corrupt data. Even a single altered bit may change the meaning of a message, corrupt a computer file, or cause a communication session to fail.
To protect against such problems, communication systems employ error-detection techniques. These techniques allow the receiver to determine whether the received information is likely to be correct or whether corruption has occurred during transmission or storage.
Among the most widely used error-detection techniques are parity bits, checksums, and cyclic redundancy checks (CRCs). Although they differ greatly in complexity
y and capability, they all rely on the same fundamental principle: adding carefully structured redundancy to the transmitted information.
Today, these techniques are found in virtually every digital communication system, including computer networks, mobile communications, satellite systems, storage devices, digital broadcasting, and Internet protocols.
What Is Error Detection?
Error detection is the process of determining whether transmitted or stored data has been corrupted.
The receiver examines the received information and checks 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?
That additional capability requires error correction.
Why Is Error Detection Necessary?
Communication channels are imperfect. Common error sources include:
- Thermal noise.
- Interference.
- Multipath fading.
- Synchronization errors.
- Equipment faults.
- Storage-media defects.
These impairments can alter one or more transmitted bits.
For example: Transmitted: 11010101. Received: 11011101. Without additional information, the receiver has no way of knowing whether the received sequence is correct.
Error-detection techniques provide the information needed to identify such corruption.
What Is Redundancy?
Redundancy refers to information added solely for protection purposes.
The redundant information does not convey new user information. Instead, it allows the receiver to verify data integrity. Examples include:
- Parity bits.
- Checksums.
- CRC remainders.
The amount of redundancy is usually small compared with the protected information.
What Is a Parity Bit?
A parity bit is the simplest and oldest form of error detection.
The transmitter adds one extra bit to the data. The value of the parity bit is chosen so that the total number of ones in the transmitted codeword is either:
- Even (even parity).
- Odd (odd parity).
The receiver performs the same count and verifies that the parity relationship is satisfied.
If not, an error is detected.
How Does Even Parity Work?
Consider the data: 1011001. The number of ones is 4. Because this is already even, the parity bit is 0.
The transmitted codeword becomes 10110010. The total number of ones remains even. At the receiver:
- The ones are counted.
- If the count is odd, an error is declared.
This simple process provides basic error-detection capability.
How Does Odd Parity Work?
Odd parity works similarly.
The parity bit is selected so that the total number of ones is odd. Using the previous example 1011001 contains four ones. To make the total odd parity bit = 1. Transmitted codeword:10110011. The receiver verifies that the total number of ones remains odd.
Any violation indicates an error.
What Errors Can Parity Detect?
Parity can detect:
- All single-bit errors.
- Any odd number of bit errors.
For example, 10110010 becomes 10100010. One bit has changed. The parity relationship is violated and the error is detected.
This makes parity effective against isolated bit errors.
What Errors Can Parity Miss?
Parity cannot detect any even number of bit errors.
Suppose two bits change 10110010 becomes 11110000. The total number of ones may remain unchanged. The parity relationship still appears valid and the error therefore goes undetected.
This limitation significantly restricts the effectiveness of parity checking.
Where Is Parity Used?
Despite its limitations, parity remains useful because of its simplicity.
Applications include:
- Serial communications.
- Computer memory systems.
- Legacy communication protocols.
- Simple embedded systems.
Parity is often used when:
- Error rates are low.
- Minimal overhead is required.
- Simplicity is important.
What Is a Checksum?
A checksum is a more sophisticated error-detection technique.
Instead of counting ones, the transmitter performs arithmetic operations on the data and appends the resulting value. The receiver repeats the calculation. If the results differ, an error is declared.
Checksums provide significantly greater protection than simple parity bits.
How Does a Checksum Work?
Suppose a message consists of several data words.
The transmitter:
- Adds the words together.
- Computes a checksum.
- Appends the checksum to the message.
The receiver:
- Performs the same calculation.
- Compares the result with the received checksum.
Agreement suggests that the data is correct. Disagreement indicates an error.
Why Are Checksums Better Than Parity?
Checksums examine larger groups of bits simultaneously.
As a result, they can detect many error patterns that parity cannot.
They are particularly effective against:
- Multiple-bit errors.
- Burst errors.
- Data corruption affecting several bytes.
Although not perfect, checksums provide substantially stronger protection than parity.
Where Are Checksums Used?
Checksums appear in many communications systems.
Examples include:
- Internet protocols.
- File-transfer systems.
- Network packets.
- Embedded systems.
- Software distribution.
A familiar example is the Internet Protocol (IP) checksum used to verify packet headers.
What Is a Cyclic Redundancy Check?
The cyclic redundancy check (CRC) is one of the most powerful and widely used error-detection techniques.
Unlike parity and checksums, CRCs are based on polynomial arithmetic. Data is treated as a polynomial whose coefficients are binary digits. The transmitter performs a polynomial division and appends the resulting remainder to the message.
The receiver performs the same calculation. A non-zero remainder indicates an error.
Why Is It Called a Cyclic Redundancy Check?
The term reflects the underlying mathematics.
- Cyclic refers to the cyclic-code structure.
- Redundancy refers to the additional check bits.
- Check indicates that the technique is used for error detection.
CRCs are closely related to cyclic error-control codes, which are discussed elsewhere in coding theory.
How Does CRC Generation Work?
The process involves:
- Selecting a generator polynomial.
- Appending zeros to the data.
- Performing modulo-2 division.
- Obtaining a remainder.
- Appending the remainder to the transmitted message.
The remainder forms the CRC field.At the receiver, the same division is repeated.
A valid codeword produces a zero remainder.
What Is Modulo-2 Arithmetic?
Modulo-2 arithmetic is binary arithmetic without carries or borrows.
The operations are:
| A | B | A XOR B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
This operation is equivalent to the exclusive-OR (XOR) function.
CRCs rely heavily on modulo-2 arithmetic.
What Is a Generator Polynomial?
The generator polynomial defines the CRC algorithm.
Examples include:
- CRC-8: g(x) = x8+x2+x+1
- CRC-16: Various standardized forms.
- CRC-32: Widely used in Ethernet and storage systems.
The choice of polynomial determines the error-detection properties of the CRC.
Why Are CRCs So Effective?
Properly designed CRCs can detect:
- All single-bit errors.
- All double-bit errors.
- Most burst errors.
- Very large classes of multiple-bit errors.
The probability of an undetected error is typically extremely small.
For example, a CRC-32 may have an undetected-error probability on the order of 2–32 for random error patterns. This corresponds to approximately one undetected error in four billion possibilities.
What Is a Burst Error?
A burst error affects several adjacent bits.
For example, 111100001111 might become 111011100111.
Burst errors commonly arise from:
- Fading.
- Impulse noise.
- Storage-media defects.
- Synchronization failures.
CRCs are particularly effective at detecting burst errors.
Why Are CRCs Preferred in Modern Systems?
CRCs offer several advantages:
- Excellent error-detection capability.
- Efficient hardware implementation.
- Efficient software implementation.
- Small overhead.
- Strong burst-error detection.
As a result, CRCs have become the dominant error-detection technique in modern communications systems.
Where Are CRCs Used?
CRCs appear in countless applications:
- Ethernet networks. Ethernet frames use CRC-32.
- Wi-Fi systems. Wireless LANs employ CRC protection.
- Satellite communications. CRCs verify packet integrity.
- Digital television. Broadcast systems rely on CRC protection.
- Storage devices. Hard drives and SSDs use CRCs extensively.
- File compression and archiving. Many archive formats incorporate CRC checks.
Few error-detection techniques have achieved such widespread adoption.
Can Error Detection Correct Errors?
Not necessarily.
Parity, checksums, and CRCs are primarily error-detection techniques. They indicate that an error has occurred. They do not normally identify which bits are incorrect.
Correction generally requires:
- Error-correcting codes.
- Retransmission protocols.
- Additional redundancy.
However, strong error detection often forms the first stage of more advanced error-control systems.
What Happens When an Error Is Detected?
Several responses are possible.
- Retransmission. The receiver requests a new copy of the data.
- Packet discard. Corrupted packets are discarded.
- Error concealment. Approximate replacements may be generated.
- Error correction. Additional coding may reconstruct the original data.
The appropriate response depends on the application.
How Do Parity, Checksums, and CRCs Compare?
CRCs generally provide the best overall performance.
| Feature | Parity | Checksum | CRC |
|---|---|---|---|
| Complexity | Very low | Low | Moderate |
| Overhead | Very low | Low | Low |
| Single-bit detection | Excellent | Excellent | Excellent |
| Multiple-bit detection | Limited | Good | Excellent |
| Burst-error detection | Poor | Moderate | Excellent |
| Modern usage | Limited | Common | Extensive |
Why Are Parity Bits, Checksums, and CRCs Important?
These techniques provide the first line of defense against data corruption in digital systems. By adding carefully structured redundancy, they allow receivers to verify the integrity of transmitted and stored information.
Although modern communication systems often employ sophisticated error-correcting codes, error detection remains essential. Parity bits, checksums, and CRCs continue to play a critical role in ensuring the reliability of computer networks, storage devices, satellite systems, wireless communications, and countless other digital technologies.
Summary
Parity bits, checksums, and cyclic redundancy checks (CRCs) are error-detection techniques that protect digital information against corruption. Parity provides a simple means of detecting single-bit errors, checksums offer stronger protection through arithmetic operations, and CRCs use polynomial arithmetic to provide extremely powerful error-detection capability.
Among these techniques, CRCs are the most widely used because they efficiently detect a broad range of error patterns, including burst errors. Together, parity bits, checksums, and CRCs form an essential part of modern communication and storage systems, helping ensure that information is transferred and stored accurately.
Back to reading