Parity Check - Learning Module

Loading content...

0/240

Single-bit Detection

The One-Bit Guardian

Of all the errors that can corrupt digital data during transmission, the single-bit error is the most common. When electromagnetic interference strikes, when thermal noise causes momentary confusion, when signal degradation pushes a voltage level below threshold—these events typically affect just one bit at a time.

This is fortunate, because simple parity checking is perfectly suited to detect single-bit errors. Not probabilistically. Not approximately. With 100% certainty, a single parity bit will detect any single-bit error in the protected data.

In this page, we will mathematically prove why single-bit detection is guaranteed, explore the probability landscape of different error scenarios, and understand exactly where parity's protective boundary lies.

What You Will Learn

By the end of this page, you will understand the mathematical proof behind parity's single-bit detection guarantee, analyze the probability of detecting various error patterns, explore the relationship between bit error rate and parity effectiveness, and recognize the exact conditions under which parity succeeds or fails.

The Detection Guarantee: Mathematical Proof

Let us establish with mathematical rigor why parity checking always detects single-bit errors.

Theorem: A single parity bit will detect any single-bit error in the protected codeword.

Proof:

Let the transmitted codeword (data + parity) be:

C = c₁c₂c₃...cₙ₋₁cₙ (where cₙ is the parity bit)

For even parity, by construction:

c₁ ⊕ c₂ ⊕ c₃ ⊕ ... ⊕ cₙ₋₁ ⊕ cₙ = 0

Now suppose a single bit cᵢ is flipped during transmission. The received word is:

C' = c₁c₂...c'ᵢ...cₙ₋₁cₙ (where c'ᵢ = cᵢ ⊕ 1, i.e., the complement of cᵢ)

The receiver computes:

c₁ ⊕ c₂ ⊕ ... ⊕ c'ᵢ ⊕ ... ⊕ cₙ₋₁ ⊕ cₙ

Since c'ᵢ = cᵢ ⊕ 1, and XOR is associative and commutative:

= (c₁ ⊕ c₂ ⊕ ... ⊕ cₙ) ⊕ 1
= 0 ⊕ 1
= 1

The result is 1, not 0, indicating odd parity. Error detected. ∎

The key insight:

Flipping any single bit changes the parity from even to odd (or vice versa). Since the original codeword had even parity, the corrupted word will have odd parity. This difference is always detectable.

Including the Parity Bit Itself

The proof holds even if the parity bit itself is the corrupted bit! If cₙ flips, the XOR of all bits will yield 1, detecting the error. This is the beauty of parity—the parity bit protects itself along with the data.

Visualizing Single-bit Detection

Let's trace through the detection process for every possible single-bit error position.

Example: 7-bit data with even parity

Original data: 1010011 (4 ones → even parity → parity bit = 0) Transmitted codeword: 10100110

Bit Position:    1  2  3  4  5  6  7  P
Original:        1  0  1  0  0  1  1  0    (4 ones, even ✓)

Error at bit 1:  0  0  1  0  0  1  1  0    (3 ones, odd ✗)
Error at bit 2:  1  1  1  0  0  1  1  0    (5 ones, odd ✗)
Error at bit 3:  1  0  0  0  0  1  1  0    (3 ones, odd ✗)
Error at bit 4:  1  0  1  1  0  1  1  0    (5 ones, odd ✗)
Error at bit 5:  1  0  1  0  1  1  1  0    (5 ones, odd ✗)
Error at bit 6:  1  0  1  0  0  0  1  0    (3 ones, odd ✗)
Error at bit 7:  1  0  1  0  0  1  0  0    (3 ones, odd ✗)
Error at P:      1  0  1  0  0  1  1  1    (5 ones, odd ✗)

Every single-bit error produces odd parity, which is detected.

Notice that the error count changes by exactly ±1 for each single-bit flip, which always changes odd to even or even to odd.

Single-bit Error Detection Summary
Error Position	Original Bit	After Error	New 1-Count	Parity Check
Bit 1	1	0	3 (was 4)	FAIL (Error detected)
Bit 2	0	1	5 (was 4)	FAIL (Error detected)
Bit 3	1	0	3 (was 4)	FAIL (Error detected)
Bit 4	0	1	5 (was 4)	FAIL (Error detected)
Bit 5	0	1	5 (was 4)	FAIL (Error detected)
Bit 6	1	0	3 (was 4)	FAIL (Error detected)
Bit 7	1	0	3 (was 4)	FAIL (Error detected)
Parity	0	1	5 (was 4)	FAIL (Error detected)

Multi-bit Error Analysis

While parity guarantees detection of single-bit errors, its behavior with multiple errors follows a precise mathematical pattern.

The General Rule:

Parity detects an error if and only if an odd number of bits are corrupted.

Bits Corrupted	Parity Change	Detected?
1	Yes	✓ Always
2	No	✗ Never
3	Yes	✓ Always
4	No	✗ Never
n (odd)	Yes	✓ Always
n (even)	No	✗ Never

Mathematical Explanation:

Each bit flip changes the parity. Starting from the correct parity:

1 flip: parity changes once → wrong parity → detected
2 flips: parity changes twice → back to original → undetected
3 flips: parity changes thrice → wrong parity → detected
And so on...

Algebraically, the received parity check is:

Original XOR sum: S = 0 (for even parity)
After k flips: S' = S ⊕ 1 ⊕ 1 ⊕ ... (k times) = 0 ⊕ (k mod 2) = k mod 2

When k is odd, S' = 1, error detected. When k is even, S' = 0, undetected.

Two-bit Error: UndetectedLet's see how a 2-bit error escapes detection.

Input

Output

The Dangerous Pairs

When two bits flip—especially when one is a 0→1 and the other is 1→0—the changes exactly cancel. This is not a rare corner case; in burst errors common in real transmission media, multiple adjacent bits are often corrupted together.

Probability of Detection

Understanding the probability that parity detects errors requires analysis of the error distribution.

Assumption: Independent Bit Errors

In the independent bit error model, each bit has probability p of being corrupted, independent of other bits. While not always realistic (burst errors violate this), it provides useful baseline analysis.

For a codeword of n bits:

Probability of exactly k errors follows the binomial distribution:

P(k errors) = C(n,k) × pᵏ × (1-p)ⁿ⁻ᵏ

Probability of detection:

P(detect) = P(1 error) + P(3 errors) + P(5 errors) + ...
P(detect) = Σ P(k errors) for odd k

Probability of undetected error:

P(undetected) = P(2 errors) + P(4 errors) + P(6 errors) + ...
P(undetected) = Σ P(k errors) for even k ≥ 2

Important: P(no error) is also even (0 errors), but this is a correct acceptance, not an undetected error.

detection_probability.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
from math import comb
from typing import Tuple
 
 
def error_probabilities(n: int, p: float) -> Tuple[float, float, float]:
    """
    Calculate detection probabilities for parity checking.
    
    Args:
        n: Number of bits in codeword (including parity)
        p: Bit error probability
    
    Returns:
        Tuple of (P_no_error, P_detected, P_undetected)
    """
    q = 1 - p  # Probability bit is correct
    
    p_no_error = q ** n  # All bits correct
    p_detected = 0.0     # Odd number of errors
    p_undetected = 0.0   # Even number of errors (≥ 2)
    
    for k in range(n + 1):
        prob_k = comb(n, k) * (p ** k) * (q ** (n - k))
        
        if k == 0:
            continue  # No error - correct acceptance
        elif k % 2 == 1:
            p_detected += prob_k  # Odd errors - detected
        else:
            p_undetected += prob_k  # Even errors - undetected
    
    return p_no_error, p_detected, p_undetected
 
 
def detection_efficiency(n: int, p: float) -> float:
    """
    Calculate detection efficiency: detected / (detected + undetected)
    
    This tells us: given that an error occurred, what's the
    probability that parity catches it?
    """
    _, p_detected, p_undetected = error_probabilities(n, p)
    total_error = p_detected + p_undetected
    
    if total_error == 0:
        return 1.0  # No errors means no failures
    
    return p_detected / total_error
 
 
# Analysis for 8-bit codeword (7 data + 1 parity)
n = 8
 
print("Parity Detection Probability Analysis")
print(f"Codeword size: {n} bits")
print("=" * 60)
print(f"{'BER':>12} | {'P(no err)':>12} | {'P(detect)':>12} | {'P(undetect)':>12} | {'Efficiency':>10}")
print("-" * 60)
 
for p in [1e-6, 1e-5, 1e-4, 1e-3, 1e-2, 0.1]:
    p_no, p_det, p_undet = error_probabilities(n, p)
    eff = detection_efficiency(n, p)
    print(f"{p:12.2e} | {p_no:12.6f} | {p_det:12.2e} | {p_undet:12.2e} | {eff:9.4%}")
 
print("
" + "=" * 60)
print("Note: At low BER, almost all errors are single-bit errors,")
print("so parity detection efficiency approaches 100%.")
print("As BER increases, multi-bit errors become probable,")
print("and more errors escape detection.")

Key Insight: Low BER Favors Parity

When bit error rate is low (e.g., 10⁻⁶), the probability of multiple simultaneous errors is extremely small. In such conditions, parity detects virtually 100% of errors because nearly all errors are single-bit. This is why parity was historically sufficient for many applications.

Quantitative Analysis: Error Detection Rate

Let's derive closed-form expressions for parity's detection probability.

Mathematical Result:

For independent bit errors with probability p in an n-bit codeword:

P(odd number of errors) = ½ × [1 - (1 - 2p)ⁿ] P(even number of errors ≥ 2) = ½ × [1 + (1 - 2p)ⁿ] - (1 - p)ⁿ

Derivation sketch: Using the binomial theorem:

(1-p+p)ⁿ = 1 = Σ C(n,k) × pᵏ × (1-p)ⁿ⁻ᵏ ... (sum of all probabilities)
(1-p-p)ⁿ = (1-2p)ⁿ = Σ C(n,k) × (-p)ᵏ × (1-p)ⁿ⁻ᵏ = Σ (-1)ᵏ × C(n,k) × pᵏ × (1-p)ⁿ⁻ᵏ

Adding and subtracting these sums:

Sum for even k = ½ × [1 + (1-2p)ⁿ]
Sum for odd k = ½ × [1 - (1-2p)ⁿ]

Practical Implications:

For very small p (p << 1):

(1 - 2p)ⁿ ≈ 1 - 2np (first-order Taylor expansion)
P(odd errors) ≈ ½ × [1 - (1 - 2np)] = np
P(1 error) ≈ np × (1-p)ⁿ⁻¹ ≈ np

So when p is small, almost all errors are single-bit errors.

Detection Performance Metrics (8-bit codeword)
Error Rate (BER)	P(error occurs)	P(detected \| error)	P(undetected)	Residual Error Rate
10⁻⁹	8×10⁻⁹	≈100%	~10⁻¹⁷	~10⁻¹⁷
10⁻⁶	8×10⁻⁶	≈100%	~10⁻¹¹	~10⁻¹¹
10⁻⁴	8×10⁻⁴	99.97%	~10⁻⁷	~10⁻⁷
10⁻³	8×10⁻³	99.7%	~10⁻⁵	~10⁻⁵
10⁻²	7.7×10⁻²	97%	~10⁻³	~10⁻³

Residual Error Rate

The 'residual error rate' is the probability that an error occurs AND escapes detection. Even with simple parity, this rate is dramatically lower than the raw BER—typically by many orders of magnitude for low BER channels.

Error Localization: What Parity Cannot Do

A critical limitation of simple parity is its inability to locate errors. When the parity check fails, we know that an error occurred, but not where or how many.

The Information Theory Perspective:

A single parity bit provides exactly 1 bit of information about errors:

Bit = 0: No error detected (even number of errors, including zero)
Bit = 1: Error detected (odd number of errors)

To locate a single error among n positions, we need log₂(n) bits of information.

For an 8-bit codeword:

Positions to distinguish: 8
Information needed: log₂(8) = 3 bits
Parity provides: 1 bit
Deficit: 2 bits of information

This is why single parity cannot correct errors—insufficient information.

Consequences:

When parity detects an error, the receiver has limited options:

Discard the data — Safe but wastes bandwidth
Request retransmission — Effective if channel allows bidirectional communication
Mark data as unreliable — Let higher layers handle the uncertainty

None of these options fix the error in place. For error correction, we need more sophisticated codes like Hamming codes (covered in Module 6).

What Parity CAN Do

•Detect any single-bit error
•Detect any odd number of bit errors
•Signal that retransmission is needed
•Work with minimal overhead (1 bit)
•Compute quickly in hardware

What Parity CANNOT Do

•Identify which bit is corrupted
•Correct any errors automatically
•Detect even numbers of errors
•Distinguish 1 error from 3, 5, 7...
•Protect against burst errors reliably

Practical Implementation Considerations

Implementing parity checking in real systems involves several practical considerations.

Hardware Implementation:

Parity generation and checking are trivially implemented in hardware using XOR gates:

                    ┌───┐
         d₀ ───────┤   │
                   │XOR├───┬─────────────┐
         d₁ ───────┤   │   │             │
                    └───┘   │             │
                            │             │
                    ┌───┐   │             │
                    │XOR│◄──┘             │
         d₂ ───────┤   ├───┬─────────────┤
                    └───┘   │             │
                            │             │
                    ┌───┐   │             │
                    │XOR│◄──┘             │
         d₃ ───────┤   ├─────────────────┴──► Parity Bit
                    └───┘
                    
For 8-bit parallel data: 7 XOR gates, ~7 gate delays
Using tree structure: 3 levels, ~3 gate delays

Tree-structured XOR (faster):

    d₀ d₁   d₂ d₃   d₄ d₅   d₆ d₇     Level 0: Input
     ╲╱       ╲╱       ╲╱       ╲╱        ↓
     XOR     XOR     XOR     XOR      Level 1
       ╲     ╱         ╲     ╱           ↓
        ╲   ╱           ╲   ╱
         XOR             XOR           Level 2
           ╲             ╱               ↓
            ╲           ╱
             ╲         ╱
              ╲       ╱
               ╲     ╱
                 XOR                   Level 3
                  │
                  ▼
             Parity Bit

hardware_parity.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
"""
Simulating hardware parity generation with timing analysis.
"""
 
class XORGate:
    """Simulates an XOR gate with propagation delay."""
    PROP_DELAY_NS = 0.5  # Typical propagation delay in nanoseconds
    
    @classmethod
    def compute(cls, a: int, b: int) -> tuple[int, float]:
        """Returns (result, delay_ns)."""
        return a ^ b, cls.PROP_DELAY_NS
 
 
def parity_linear(data: list[int]) -> tuple[int, float]:
    """
    Compute parity using linear chain of XOR gates.
    Returns (parity_bit, total_delay_ns).
    """
    result = 0
    total_delay = 0
    
    for bit in data:
        result, delay = XORGate.compute(result, bit)
        total_delay += delay
    
    return result, total_delay
 
 
def parity_tree(data: list[int]) -> tuple[int, float]:
    """
    Compute parity using balanced tree of XOR gates.
    Returns (parity_bit, total_delay_ns).
    Assumes len(data) is a power of 2.
    """
    if len(data) == 1:
        return data[0], 0
    
    # XOR pairs in parallel
    next_level = []
    for i in range(0, len(data), 2):
        xor_result, _ = XORGate.compute(data[i], data[i + 1])
        next_level.append(xor_result)
    
    # Recurse and add one level of gate delay
    result, sub_delay = parity_tree(next_level)
    return result, sub_delay + XORGate.PROP_DELAY_NS
 
 
# Compare implementations
test_data = [1, 0, 1, 0, 0, 1, 1, 0]  # 8 bits
 
linear_result, linear_delay = parity_linear(test_data)
tree_result, tree_delay = parity_tree(test_data)
 
print("Hardware Parity Implementation Comparison")
print("=" * 50)
print(f"Data: {test_data}")
print(f"Expected parity: {sum(test_data) % 2}")
print()
print(f"Linear chain: parity = {linear_result}, delay = {linear_delay:.1f} ns")
print(f"Balanced tree: parity = {tree_result}, delay = {tree_delay:.1f} ns")
print()
print(f"Tree speedup: {linear_delay / tree_delay:.1f}x faster")
print()
print("For 64-bit word:")
print(f"  Linear: {64 * XORGate.PROP_DELAY_NS:.1f} ns (64 gate delays)")
print(f"  Tree: {6 * XORGate.PROP_DELAY_NS:.1f} ns (log₂64 = 6 gate delays)")

Modern CPU Parity Instructions

Modern CPUs include dedicated instructions for parity calculation. x86 processors have the POPCNT (population count) instruction that counts 1-bits in a single cycle. Parity is simply POPCNT mod 2. Some processors even have a parity flag (PF) in the status register that's automatically updated after arithmetic operations.

Applications of Single-bit Detection

Despite its limitations, parity-based single-bit detection remains relevant in several contexts.

1. Serial Communication (RS-232, UART)

Parity is still a standard option in serial communication:

Mark parity (always 1)
Space parity (always 0)
Even parity
Odd parity
None

The low bandwidth and character-by-character transmission make burst errors rare, and parity is sufficient for many applications.

2. Memory Systems (Legacy)

Parity memory was standard in PCs through the 1990s:

Each byte stored with one parity bit
Memory controller checked parity on every read
Errors triggered non-maskable interrupt (NMI)
System would halt rather than use corrupted data

3. Bus and Interface Checking

PCI bus used parity on address and data lines
Some internal processor buses use parity
Cost-effective protection for parallel interfaces

4. Embedded Systems

Resource-constrained systems may use parity where CRC would be too expensive:

Simple microcontrollers
Sensor networks
Low-bandwidth protocols

Parity in Real-World Systems
System	Configuration	Parity Type	Purpose
RS-232 Serial	7-bit data + parity	Even or Odd	Character-level error detection
PC Memory (1990s)	8 bits + 1 parity	Even	Memory corruption detection
PCI Bus (legacy)	32 bits + 4 parity	Even	Bus transaction integrity
I²C (optional)	8 bits + 1 parity	Optional	Low-speed bus checking
ASCII Character Set	7 bits + 1 free	Even	Teleprinter error detection

Summary: Single-bit Detection

We have thoroughly explored the capabilities and limitations of parity for single-bit error detection. Let's consolidate the essential insights:

Key Takeaways

•100% single-bit detection guarantee — Parity always detects any single-bit error, mathematically proven via XOR properties
•Odd-error detection — More generally, parity detects any odd number of bit errors (1, 3, 5, ...)
•Even-error blind spot — Two, four, six, etc. simultaneous errors escape detection
•Low BER favors parity — When bit error rate is low, nearly all errors are single-bit and thus detected
•Detection without correction — Parity cannot locate errors; retransmission is the only remedy
•Minimal overhead — Just 1 bit per data unit, with O(n) XOR computation
•Hardware-friendly — XOR gates provide fast, parallel parity computation

What's Next:

In the next page, we'll explore two-dimensional parity, a technique that arranges data in a grid and applies parity to both rows and columns. This enhancement can not only detect but actually correct single-bit errors—achieving error correction with simple parity concepts.

Page Complete

You now understand the theoretical and practical aspects of single-bit error detection using parity. This foundation prepares you for understanding more sophisticated error detection schemes that build upon these same mathematical principles.