Parity Check

Parity Check: The Simplest Error Detection Method

The parity check is the most fundamental error detection technique in digital communication — elegant in its simplicity, requiring just one extra bit to protect an entire data word. While more sophisticated methods have largely replaced simple parity in modern communication links, understanding parity is essential because it forms the building block for virtually all more complex error detection and correction schemes, including Hamming codes, CRC, and LDPC codes.

The Basic Idea

Think of it this way: imagine a group of friends entering a cinema — you count them to make sure everyone is there. If you always travel in even numbers, anyone can tell immediately if one person is missing (the count becomes odd). Parity works exactly this way with ones and zeros.

Even parity: The parity bit is chosen so that the total number of 1-bits (including the parity bit) is even. Odd parity: The parity bit is chosen so the total number of 1-bits is odd.

Example (even parity):

• Data: 1 0 1 1 0 0 1 → Count of 1s = 4 (even) → Parity bit = 0
• Data: 1 0 1 1 0 1 1 → Count of 1s = 5 (odd) → Parity bit = 1

The parity bit is appended to form the transmitted word. The receiver counts all 1s (including parity) — if the count is not even (for even parity), an error has occurred.

Mathematical Formulation

Parity is simply the XOR (exclusive-OR) of all data bits:

P = b₁ ⊕ b₂ ⊕ b₃ ⊕ ... ⊕ bₙ

At the receiver, XOR all received bits including parity:

• Result = 0 → Even number of errors (including zero errors) → Assume correct
• Result = 1 → Odd number of errors → Error detected!

This reveals the fundamental limitation: parity detects all odd-number errors but misses all even-number errors. Two bits flipping cancel each other out.

Hardware Implementation

Parity generation and checking requires only XOR gates — the simplest digital logic:

Generator: Chain of XOR gates computing the cumulative XOR of all data bits Checker: XOR gate combining received data XOR result with received parity bit

For an 8-bit byte, a parity tree uses just 7 XOR gates with a propagation delay of only 3 gate levels (log₂8). This makes parity checking extremely fast — fast enough to keep up with multi-GHz clock speeds in modern processors.

Parity in Serial Communication

Historically, parity was the standard error detection method for serial communication:

UART (RS-232) framing:

• Start bit | Data bits (5-8) | Parity bit (optional) | Stop bit(s)

Parity options in serial ports:

• None: No parity bit transmitted
• Even: Total 1s in data + parity is even
• Odd: Total 1s in data + parity is odd
• Mark: Parity bit always 1 (used as extra stop bit)
• Space: Parity bit always 0 (used for 9-bit data)

At typical UART error rates (10⁻⁴ to 10⁻⁶ BER), single-bit errors dominate, and parity catches them all. The risk of undetected double errors (≈BER²) is acceptably small.

Two-Dimensional Parity (Block Parity)

Two-dimensional parity dramatically improves error detection by computing parity for both rows and columns:

Detection capabilities:

• All single-bit errors (caught by both row and column parity)
• All double-bit errors (caught by at least one dimension)
• All triple-bit errors
• Most four-bit errors (except rectangular patterns)

Correction capability: Can correct any single-bit error! The failing row parity identifies the row, and the failing column parity identifies the column — their intersection pinpoints the exact error position.

Limitation: A rectangular pattern of 4 errors (at corners of a rectangle) goes undetected because it satisfies both row and column parity. Probability: very low in practice.

Parity in Modern Memory Systems

DRAM memory systems use parity as the simplest form of memory protection:

Parity memory:

• 9 bits stored per byte (8 data + 1 parity)
• Detects single-bit errors (cosmic ray hits, cell degradation)
• Cannot correct — triggers a system error (NMI interrupt)
• Used in consumer PCs (lower cost than full ECC)

ECC memory (extends parity concept):

• 72 bits stored per 64-bit word (8 ECC bits using Hamming code)
• Corrects single-bit errors silently
• Detects double-bit errors
• Required for servers, workstations, mission-critical systems

Parity in RAID Storage

RAID (Redundant Array of Independent Disks) uses parity for data protection:

RAID 3/4: Dedicated parity disk stores XOR of corresponding blocks from all data disks

• If any one disk fails: lost data = XOR of all surviving disks = reconstruction
• Overhead: one disk worth of capacity

RAID 5: Parity distributed across all disks (avoids parity disk bottleneck)

• Same protection as RAID 3/4 but better write performance
• Single-disk failure recoverable

RAID 6: Two independent parity calculations (using different polynomials)

• Survives any two simultaneous disk failures
• Uses both XOR parity and Reed-Solomon-based second parity

Limitations of Simple Parity

For modern communication links with burst errors, parity alone is insufficient. CRC is the standard replacement for link-level error detection.

Interleaved Parity

Interleaving multiple parity bits across different bit positions improves burst error detection:

Example: Instead of one parity bit for 8 data bits, use 8 separate parity bits — each protecting every 8th bit across a block of 64 data bits. A burst error of up to 8 bits corrupts at most one bit in each parity group → all errors detected.

This technique bridges the gap between simple parity and full CRC for applications needing moderate burst protection with minimal complexity.

Key Takeaways

1. Parity adds one bit to make the total 1-count even (or odd), detecting all single-bit errors with minimal overhead.
2. Parity detection fails for even numbers of errors — the bits "cancel out" in the XOR computation.
3. Two-dimensional parity extends detection to multiple errors and enables single-error correction by intersecting failing row and column.
4. Parity remains essential in RAID storage, computer memory (basic protection), and as the building block of more powerful codes.
5. Hardware implementation requires only XOR gates — the simplest and fastest logic operation available.
6. For modern serial links, CRC has largely replaced parity due to superior burst error detection, but parity persists where simplicity and speed are paramount.