Single-bit Detection

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.

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.

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.

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.

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.

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.

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.

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:

1. Discard the data — Safe but wastes bandwidth
2. Request retransmission — Effective if channel allows bidirectional communication
3. 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).

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