Computer NetworksError Detection & Correction

Parity Check

LevelBeginner

Duration60 mins

TopicError Detection & Correction

1 / 5

Even and Odd Parity

The Simplest Guardian of Data Integrity

In the realm of digital communication, data travels as streams of binary digits—ones and zeros racing through copper wires, fiber optic cables, and wireless channels. But these journeys are fraught with peril. Electromagnetic interference, signal attenuation, thermal noise, and countless other phenomena can silently flip a 0 to a 1, or a 1 to a 0. Without some mechanism to detect such corruption, we would never know when our data has been compromised.

Parity checking stands as the oldest and most fundamental error detection technique in computing history. Its elegance lies in its simplicity: by adding just a single bit to a data unit, we can detect whether an error has occurred during transmission.

This deceptively simple concept—counting ones and adding a bit to make a pattern—has protected data integrity in systems ranging from early telegraph machines to modern memory systems. Understanding parity is not merely historical curiosity; it is the conceptual foundation upon which more sophisticated error detection and correction techniques are built.

What You Will Learn

By the end of this page, you will understand the mathematical foundations of even and odd parity, how parity bits are calculated and verified, why we need both even and odd schemes, and how this simple technique forms the conceptual basis for all error detection methods in computer networks.

The Fundamental Problem: Bit Errors in Transmission

Before we understand the solution, we must fully appreciate the problem. When digital data travels from one point to another, it passes through a physical medium—and that medium is inherently imperfect.

Sources of bit errors include:

Thermal Noise (Johnson-Nyquist Noise) Every conductor at a temperature above absolute zero generates random electrical fluctuations due to the thermal agitation of electrons. This noise is unavoidable and sets a fundamental limit on signal detection.

Electromagnetic Interference (EMI) External sources—motors, power lines, lightning, even other communication systems—can induce unwanted signals in transmission media. A strong enough interference can overwhelm the intended signal and cause bit inversions.

Crosstalk In cables carrying multiple signal pairs, electromagnetic coupling can cause signals to "leak" between adjacent pairs. The signal intended for one channel partially appears in another.

Signal Attenuation As signals travel through media, they lose energy. If a signal weakens too much before reaching the receiver, the difference between a '0' and a '1' becomes ambiguous, leading to detection errors.

Timing Jitter Digital systems rely on precise timing to sample signals. If the sampling clock is not perfectly synchronized or if the signal edges are distorted, the receiver may sample at the wrong moment and read incorrect values.

Bit Error Rate (BER) in Different Transmission Media
Medium	Typical BER	Interpretation
Fiber Optic	10⁻¹² to 10⁻¹⁵	1 error per trillion to quadrillion bits
Coaxial Cable	10⁻⁸ to 10⁻¹⁰	1 error per 100 million to 10 billion bits
Twisted Pair (Shielded)	10⁻⁷ to 10⁻⁹	1 error per 10 million to billion bits
Wireless (Good Conditions)	10⁻⁵ to 10⁻⁷	1 error per 100,000 to 10 million bits
Wireless (Poor Conditions)	10⁻² to 10⁻⁴	1 error per 100 to 10,000 bits

Why This Matters

Consider a 1 Gbps network link with a BER of 10⁻⁹. Even with this relatively low error rate, you would expect approximately one bit error per second. For critical applications—financial transactions, medical records, control systems—even rare errors are unacceptable without detection mechanisms.

The Concept of Parity

Parity is a mathematical property that refers to whether a count is even or odd. In the context of binary data, parity refers to whether the number of 1-bits in a binary sequence is even or odd.

Definition:

A binary sequence has even parity if it contains an even number of 1-bits (including zero)
A binary sequence has odd parity if it contains an odd number of 1-bits

Examples:

Binary Sequence	Count of 1s	Parity
0000	0	Even
0001	1	Odd
0101	2	Even
0111	3	Odd
1111	4	Even
10110	3	Odd
11111111	8	Even

Notice that zero is considered even—this follows from the mathematical definition that zero is divisible by 2 with no remainder.

The Key Insight:

If we know what the parity of a transmitted sequence should be, we can verify that the received sequence has the same parity. If the parity has changed, we know an error has occurred.

XOR: The Parity Calculator

The XOR (exclusive OR) operation is perfectly suited for parity calculation. XORing all bits in a sequence produces 0 if there's an even number of 1s, and 1 if there's an odd number. This is because XOR is commutative and associative, and 1 XOR 1 = 0. Example: 1 ⊕ 0 ⊕ 1 ⊕ 1 = 1 (odd parity, three 1s).

Even Parity Scheme

In an even parity scheme, the sender adds a single parity bit to the data such that the total number of 1-bits (including the parity bit) is always even.

How Even Parity Works:

Step 1: Count the 1-bits in the data The sender examines the data bits to be transmitted and counts how many are 1s.

Step 2: Determine the parity bit value

If the count of 1s is already even → parity bit = 0
If the count of 1s is odd → parity bit = 1

Step 3: Transmit data + parity bit The parity bit is appended (or prepended, depending on convention) to the data.

Step 4: Receiver verification The receiver counts all 1-bits in the received sequence (data + parity). If the total is even, no error is detected. If odd, an error is detected.

Even Parity Calculation ExampleLet's transmit the 7-bit ASCII character 'A' (1000001) using even parity.

Input

Output

Even Parity with Odd DataNow let's transmit the 7-bit ASCII character 'C' (1000011) using even parity.

Input

Output

even_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
def calculate_even_parity_bit(data: str) -> str:
    """
    Calculate the even parity bit for a binary data string.
    
    Args:
        data: Binary string (e.g., "1000001")
    
    Returns:
        "0" if data has even number of 1s, "1" if odd
    """
    count_ones = data.count('1')
    return '0' if count_ones % 2 == 0 else '1'
 
 
def add_even_parity(data: str) -> str:
    """
    Add even parity bit to data.
    
    Args:
        data: Binary string to protect
    
    Returns:
        Data with parity bit appended
    """
    parity_bit = calculate_even_parity_bit(data)
    return data + parity_bit
 
 
def verify_even_parity(received: str) -> bool:
    """
    Verify that received data (with parity) has even parity.
    
    Args:
        received: Binary string including parity bit
    
    Returns:
        True if parity is correct (even), False if error detected
    """
    return received.count('1') % 2 == 0
 
 
# Examples
print("Even Parity Examples:")
print("-" * 40)
 
data1 = "1000001"  # ASCII 'A'
with_parity1 = add_even_parity(data1)
print(f"Data: {data1} → With parity: {with_parity1}")
print(f"Verification: {verify_even_parity(with_parity1)}")
 
data2 = "1000011"  # ASCII 'C'  
with_parity2 = add_even_parity(data2)
print(f"Data: {data2} → With parity: {with_parity2}")
print(f"Verification: {verify_even_parity(with_parity2)}")
 
# Simulate an error
corrupted = "10000110"  # One bit flipped
print(f"\nCorrupted: {corrupted}")
print(f"Error detected: {not verify_even_parity(corrupted)}")

Odd Parity Scheme

In an odd parity scheme, the sender adds a parity bit such that the total number of 1-bits (including the parity bit) is always odd.

How Odd Parity Works:

Step 1: Count the 1-bits in the data Identical to even parity—count the 1s in the data.

Step 2: Determine the parity bit value

If the count of 1s is already odd → parity bit = 0
If the count of 1s is even → parity bit = 1

Step 3: Transmit data + parity bit The complete sequence is sent.

Step 4: Receiver verification The receiver counts all 1-bits. If the total is odd, no error is detected. If even, an error is detected.

Odd Parity Example 1Transmit 'A' (1000001) with odd parity.

Input

Output

Odd Parity Example 2Transmit 'C' (1000011) with odd parity.

Input

Output

Even vs. Odd: Which to Choose?

Both schemes have identical error detection capability—they can detect any odd number of bit errors. The choice between them is often arbitrary or based on convention. However, odd parity has one subtle advantage: it guarantees that every valid codeword contains at least one '1' bit. This can help detect certain systematic failures where an entire byte is read as all zeros (which would pass even parity but fail odd parity).

Mathematical Foundation: Modular Arithmetic and XOR

Understanding parity at a mathematical level reveals its elegance and explains why XOR is the perfect operation for parity calculation.

Modular Arithmetic View:

Parity checking is fundamentally about counting modulo 2:

Even parity: (count of 1s) mod 2 = 0
Odd parity: (count of 1s) mod 2 = 1

When we add a parity bit, we're ensuring the sum remains constant modulo 2. If any bit flips, it changes the sum by 1 (mod 2), which is always detectable.

XOR as Parity Calculator:

The XOR operation has remarkable properties for parity:

A	B	A ⊕ B
0	0	0
0	1	1
1	0	1
1	1	0

Key properties:

Identity: a ⊕ 0 = a
Self-inverse: a ⊕ a = 0
Commutativity: a ⊕ b = b ⊕ a
Associativity: (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c)

Parity via XOR: XORing all bits together yields:

0 if even number of 1s (even parity)
1 if odd number of 1s (odd parity)

Example: 1 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 0 = ?

Step by step:

1 ⊕ 0 = 1
1 ⊕ 1 = 0
0 ⊕ 1 = 1
1 ⊕ 0 = 1

Result: 1 (odd parity, since we have three 1s)

xor_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
69
70
71
72
73
74
75
76
def xor_parity(data: str) -> int:
    """
    Calculate parity using XOR operation.
    
    This is more efficient than counting because XOR
    can be implemented with a single CPU instruction
    operating on multiple bits simultaneously.
    
    Args:
        data: Binary string
    
    Returns:
        0 for even parity, 1 for odd parity
    """
    result = 0
    for bit in data:
        result ^= int(bit)
    return result
 
 
def xor_parity_efficient(data: int, num_bits: int = 8) -> int:
    """
    Efficient parity calculation for integers using bit manipulation.
    
    This technique progressively XORs halves of the word,
    reducing to a single parity bit in O(log n) operations.
    
    Args:
        data: Integer value
        num_bits: Number of bits to consider
    
    Returns:
        0 for even parity, 1 for odd parity
    """
    # For 8 bits:
    #   XOR upper 4 with lower 4
    #   XOR upper 2 with lower 2
    #   XOR upper 1 with lower 1
    
    # Example with 8 bits: 0b10110010 (4 ones, even parity)
    #   Step 1: 1011 XOR 0010 = 1001
    #   Step 2: 10 XOR 01 = 11
    #   Step 3: 1 XOR 1 = 0  ← Even parity
    
    result = data
    shift = num_bits // 2
    
    while shift > 0:
        result ^= (result >> shift)
        shift //= 2
    
    return result & 1
 
 
# Demonstration
print("XOR Parity Calculation")
print("=" * 50)
 
test_cases = [
    "00000000",  # 0 ones - even
    "10000000",  # 1 one - odd
    "10100000",  # 2 ones - even
    "10110000",  # 3 ones - odd
    "10110010",  # 4 ones - even
    "11111111",  # 8 ones - even
]
 
for data in test_cases:
    parity = xor_parity(data)
    count = data.count('1')
    print(f"{data}: {count} ones → parity = {parity} ({'even' if parity == 0 else 'odd'})")
 
print("\nEfficient integer parity:")
for val in [0, 128, 160, 176, 178, 255]:
    parity = xor_parity_efficient(val, 8)
    print(f"{val:3d} (0b{val:08b}): parity = {parity}")

Hardware Efficiency

Modern processors often include dedicated parity instructions or can compute parity for an entire 64-bit word in just 4-5 operations using the divide-and-conquer XOR approach. This makes parity checking essentially free in terms of computational cost.

Parity Bit Positioning Conventions

Where should the parity bit be placed relative to the data? Different systems use different conventions:

Common Positioning Schemes:

1. Trailing Parity (Most Common) The parity bit follows the data bits.

Example: Data 1000001 → 10000010 (parity at end)
Used in: ASCII serial transmission, many protocols

2. Leading Parity The parity bit precedes the data bits.

Example: Data 1000001 → 01000001 (parity at start)
Used in: Some memory systems

3. High-Bit Parity In systems with fixed word sizes, the highest bit position may be designated for parity.

Example: 8-bit word where bit 7 is parity
Used in: 7-bit ASCII with 8-bit transmission

Parity Conventions in Different Systems
System	Data Bits	Parity Position	Total Bits
7-bit ASCII + Parity	7	Bit 7 (MSB)	8
RS-232 Serial	5-8	After stop bit	Variable
DRAM Memory	64	Separate chip	72 (with ECC)
PCI Bus (legacy)	32	4 parity lines	36

Convention Matters

Both sender and receiver must agree on the parity convention: even vs. odd, and bit position. A mismatch doesn't just fail to detect errors—it causes every valid transmission to appear erroneous!

Visual Representation of Parity

Understanding parity visually can help solidify the concept. Let's examine how data flows through a parity-protected channel.

Transmission Flow:

┌─────────────────────────────────────────────────────────────────────────┐
│                           SENDER SIDE                                   │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                         │
│   Original Data:  1 0 0 0 0 1 1     (7 bits, 3 ones - odd count)       │
│                   ↓                                                     │
│   Parity Calc:    Count 1s → 3 (odd) → Need parity bit = 1 for even    │
│                   ↓                                                     │
│   Transmitted:    1 0 0 0 0 1 1 [1]   (8 bits, 4 ones - even count)    │
│                                 └── Parity bit                          │
└─────────────────────────────────────────────────────────────────────────┘
                                    ↓
                          Transmission Channel
                         (may introduce errors)
                                    ↓
┌─────────────────────────────────────────────────────────────────────────┐
│                          RECEIVER SIDE                                  │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                         │
│   Case 1: No Error                                                      │
│   Received:      1 0 0 0 0 1 1 1    (4 ones - even) ✓ Valid            │
│                                                                         │
│   Case 2: Single Bit Error (bit 3 flipped)                              │
│   Received:      1 0 0 1 0 1 1 1    (5 ones - odd) ✗ Error Detected    │
│                          ↑                                              │
│                       corrupted                                         │
│                                                                         │
│   Case 3: Two Bit Errors (bits 3 and 5 flipped)                         │
│   Received:      1 0 0 1 0 0 1 1    (4 ones - even) ⚠ Undetected!      │
│                          ↑   ↑                                          │
│                       corrupted                                         │
└─────────────────────────────────────────────────────────────────────────┘

This visualization illustrates a critical limitation: parity can only detect an odd number of bit errors. When an even number of bits flip, the parity remains unchanged, and the error goes undetected.

The Even-Error Blind Spot

If 2, 4, 6, or any even number of bits are corrupted, simple parity checking will NOT detect the error. Each pair of flipped bits cancels out in the parity calculation. This is a fundamental limitation that more sophisticated error detection methods (CRC, checksums) address.

Historical Context: From Telegraphs to Modern Systems

Parity checking has a rich history that parallels the development of digital communication itself.

Timeline of Parity in Computing:

1940s-1950s: Early Computers The earliest electronic computers used parity to protect data stored in volatile vacuum tube memory. Memory failures were common, and parity provided a crucial check on data integrity.

1960s: Magnetic Core Memory As magnetic core memory became standard, parity bits were added to each memory word. This tradition continued into semiconductor memory.

1970s: ASCII Standard 7-bit ASCII was designed with an eighth bit explicitly reserved for parity. This allowed error detection in serial communication, which was crucial for the early internet's predecessors.

1980s-1990s: PC Era Parity memory (8 data bits + 1 parity bit per byte) was standard in PCs. Systems would halt with a "parity error" message when memory corruption was detected—better to stop than to corrupt data silently.

2000s-Present: ECC Dominance For critical systems, simple parity has largely been replaced by Error Correcting Code (ECC) memory, which can not only detect but also correct single-bit errors. However, parity concepts remain foundational to understanding ECC.

Why Parity Still Matters Today

•Conceptual Foundation — Understanding parity is prerequisite to understanding Hamming codes, CRC, RAID, and other error detection/correction schemes
•Low Overhead — For applications where space is critical and error rates are low, a single parity bit may be sufficient
•Fast Computation — XOR-based parity calculation is essentially free in hardware
•Serial Communication — Many embedded systems and legacy protocols still use parity as their primary error check
•Educational Value — Parity perfectly illustrates the tradeoff between redundancy and error detection capability

Summary: Even and Odd Parity

We have explored the foundational concepts of parity checking, the simplest form of error detection in digital communication. Let's consolidate the key concepts:

Key Takeaways

•Parity is about counting ones — Even parity ensures an even total of 1-bits; odd parity ensures an odd total
•Single bit overhead — Only one additional bit is needed per data unit
•XOR enables efficient calculation — Parity can be computed by XORing all bits together
•Detects odd numbers of errors — Any 1, 3, 5, etc. bit errors will be detected
•Cannot detect even numbers of errors — Pairs of errors cancel out and go undetected
•Cannot correct errors — Parity only tells you that an error occurred, not where
•Both schemes are equivalent — Even and odd parity have identical detection capability

What's Next:

In the next page, we'll examine how parity is used specifically for single-bit error detection, exploring the probability of detection, the relationship between data size and error rates, and practical considerations for implementing parity in real systems.

Page Complete

You now understand the fundamental principles of even and odd parity. These concepts form the basis for understanding all error detection and correction techniques in computer networks, from simple single-bit detection to sophisticated polynomial-based methods like CRC.

1 / 5

Loading learning content...

Computer NetworksError Detection & Correction

Parity Check

LevelBeginner

Duration60 mins

TopicError Detection & Correction

1 / 5

Even and Odd Parity

The Simplest Guardian of Data Integrity

What You Will Learn

The Fundamental Problem: Bit Errors in Transmission

Sources of bit errors include:

Crosstalk In cables carrying multiple signal pairs, electromagnetic coupling can cause signals to "leak" between adjacent pairs. The signal intended for one channel partially appears in another.

Bit Error Rate (BER) in Different Transmission Media
Medium	Typical BER	Interpretation
Fiber Optic	10⁻¹² to 10⁻¹⁵	1 error per trillion to quadrillion bits
Coaxial Cable	10⁻⁸ to 10⁻¹⁰	1 error per 100 million to 10 billion bits
Twisted Pair (Shielded)	10⁻⁷ to 10⁻⁹	1 error per 10 million to billion bits
Wireless (Good Conditions)	10⁻⁵ to 10⁻⁷	1 error per 100,000 to 10 million bits
Wireless (Poor Conditions)	10⁻² to 10⁻⁴	1 error per 100 to 10,000 bits

Why This Matters

The Concept of Parity

Parity is a mathematical property that refers to whether a count is even or odd. In the context of binary data, parity refers to whether the number of 1-bits in a binary sequence is even or odd.

Definition:

A binary sequence has even parity if it contains an even number of 1-bits (including zero)
A binary sequence has odd parity if it contains an odd number of 1-bits

Examples:

Binary Sequence	Count of 1s	Parity
0000	0	Even
0001	1	Odd
0101	2	Even
0111	3	Odd
1111	4	Even
10110	3	Odd
11111111	8	Even

Notice that zero is considered even—this follows from the mathematical definition that zero is divisible by 2 with no remainder.

The Key Insight:

If we know what the parity of a transmitted sequence should be, we can verify that the received sequence has the same parity. If the parity has changed, we know an error has occurred.

XOR: The Parity Calculator

Even Parity Scheme

In an even parity scheme, the sender adds a single parity bit to the data such that the total number of 1-bits (including the parity bit) is always even.

How Even Parity Works:

Step 1: Count the 1-bits in the data The sender examines the data bits to be transmitted and counts how many are 1s.

Step 2: Determine the parity bit value

If the count of 1s is already even → parity bit = 0
If the count of 1s is odd → parity bit = 1

Step 3: Transmit data + parity bit The parity bit is appended (or prepended, depending on convention) to the data.

Step 4: Receiver verification The receiver counts all 1-bits in the received sequence (data + parity). If the total is even, no error is detected. If odd, an error is detected.

Even Parity Calculation ExampleLet's transmit the 7-bit ASCII character 'A' (1000001) using even parity.

Input

Output

Even Parity with Odd DataNow let's transmit the 7-bit ASCII character 'C' (1000011) using even parity.

Input

Output

even_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
def calculate_even_parity_bit(data: str) -> str:
    """
    Calculate the even parity bit for a binary data string.
    
    Args:
        data: Binary string (e.g., "1000001")
    
    Returns:
        "0" if data has even number of 1s, "1" if odd
    """
    count_ones = data.count('1')
    return '0' if count_ones % 2 == 0 else '1'
 
 
def add_even_parity(data: str) -> str:
    """
    Add even parity bit to data.
    
    Args:
        data: Binary string to protect
    
    Returns:
        Data with parity bit appended
    """
    parity_bit = calculate_even_parity_bit(data)
    return data + parity_bit
 
 
def verify_even_parity(received: str) -> bool:
    """
    Verify that received data (with parity) has even parity.
    
    Args:
        received: Binary string including parity bit
    
    Returns:
        True if parity is correct (even), False if error detected
    """
    return received.count('1') % 2 == 0
 
 
# Examples
print("Even Parity Examples:")
print("-" * 40)
 
data1 = "1000001"  # ASCII 'A'
with_parity1 = add_even_parity(data1)
print(f"Data: {data1} → With parity: {with_parity1}")
print(f"Verification: {verify_even_parity(with_parity1)}")
 
data2 = "1000011"  # ASCII 'C'  
with_parity2 = add_even_parity(data2)
print(f"Data: {data2} → With parity: {with_parity2}")
print(f"Verification: {verify_even_parity(with_parity2)}")
 
# Simulate an error
corrupted = "10000110"  # One bit flipped
print(f"\nCorrupted: {corrupted}")
print(f"Error detected: {not verify_even_parity(corrupted)}")

Odd Parity Scheme

In an odd parity scheme, the sender adds a parity bit such that the total number of 1-bits (including the parity bit) is always odd.

How Odd Parity Works:

Step 1: Count the 1-bits in the data Identical to even parity—count the 1s in the data.

Step 2: Determine the parity bit value

If the count of 1s is already odd → parity bit = 0
If the count of 1s is even → parity bit = 1

Step 3: Transmit data + parity bit The complete sequence is sent.

Step 4: Receiver verification The receiver counts all 1-bits. If the total is odd, no error is detected. If even, an error is detected.

Odd Parity Example 1Transmit 'A' (1000001) with odd parity.

Input

Output

Odd Parity Example 2Transmit 'C' (1000011) with odd parity.

Input

Output

Even vs. Odd: Which to Choose?

Mathematical Foundation: Modular Arithmetic and XOR

Understanding parity at a mathematical level reveals its elegance and explains why XOR is the perfect operation for parity calculation.

Modular Arithmetic View:

Parity checking is fundamentally about counting modulo 2:

Even parity: (count of 1s) mod 2 = 0
Odd parity: (count of 1s) mod 2 = 1

When we add a parity bit, we're ensuring the sum remains constant modulo 2. If any bit flips, it changes the sum by 1 (mod 2), which is always detectable.

XOR as Parity Calculator:

The XOR operation has remarkable properties for parity:

A	B	A ⊕ B
0	0	0
0	1	1
1	0	1
1	1	0

Key properties:

Identity: a ⊕ 0 = a
Self-inverse: a ⊕ a = 0
Commutativity: a ⊕ b = b ⊕ a
Associativity: (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c)

Parity via XOR: XORing all bits together yields:

0 if even number of 1s (even parity)
1 if odd number of 1s (odd parity)

Example: 1 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 0 = ?

Step by step:

1 ⊕ 0 = 1
1 ⊕ 1 = 0
0 ⊕ 1 = 1
1 ⊕ 0 = 1

Result: 1 (odd parity, since we have three 1s)

xor_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
69
70
71
72
73
74
75
76
def xor_parity(data: str) -> int:
    """
    Calculate parity using XOR operation.
    
    This is more efficient than counting because XOR
    can be implemented with a single CPU instruction
    operating on multiple bits simultaneously.
    
    Args:
        data: Binary string
    
    Returns:
        0 for even parity, 1 for odd parity
    """
    result = 0
    for bit in data:
        result ^= int(bit)
    return result
 
 
def xor_parity_efficient(data: int, num_bits: int = 8) -> int:
    """
    Efficient parity calculation for integers using bit manipulation.
    
    This technique progressively XORs halves of the word,
    reducing to a single parity bit in O(log n) operations.
    
    Args:
        data: Integer value
        num_bits: Number of bits to consider
    
    Returns:
        0 for even parity, 1 for odd parity
    """
    # For 8 bits:
    #   XOR upper 4 with lower 4
    #   XOR upper 2 with lower 2
    #   XOR upper 1 with lower 1
    
    # Example with 8 bits: 0b10110010 (4 ones, even parity)
    #   Step 1: 1011 XOR 0010 = 1001
    #   Step 2: 10 XOR 01 = 11
    #   Step 3: 1 XOR 1 = 0  ← Even parity
    
    result = data
    shift = num_bits // 2
    
    while shift > 0:
        result ^= (result >> shift)
        shift //= 2
    
    return result & 1
 
 
# Demonstration
print("XOR Parity Calculation")
print("=" * 50)
 
test_cases = [
    "00000000",  # 0 ones - even
    "10000000",  # 1 one - odd
    "10100000",  # 2 ones - even
    "10110000",  # 3 ones - odd
    "10110010",  # 4 ones - even
    "11111111",  # 8 ones - even
]
 
for data in test_cases:
    parity = xor_parity(data)
    count = data.count('1')
    print(f"{data}: {count} ones → parity = {parity} ({'even' if parity == 0 else 'odd'})")
 
print("\nEfficient integer parity:")
for val in [0, 128, 160, 176, 178, 255]:
    parity = xor_parity_efficient(val, 8)
    print(f"{val:3d} (0b{val:08b}): parity = {parity}")

Hardware Efficiency

Parity Bit Positioning Conventions

Where should the parity bit be placed relative to the data? Different systems use different conventions:

Common Positioning Schemes:

1. Trailing Parity (Most Common) The parity bit follows the data bits.

Example: Data 1000001 → 10000010 (parity at end)
Used in: ASCII serial transmission, many protocols

2. Leading Parity The parity bit precedes the data bits.

Example: Data 1000001 → 01000001 (parity at start)
Used in: Some memory systems

3. High-Bit Parity In systems with fixed word sizes, the highest bit position may be designated for parity.

Example: 8-bit word where bit 7 is parity
Used in: 7-bit ASCII with 8-bit transmission

Parity Conventions in Different Systems
System	Data Bits	Parity Position	Total Bits
7-bit ASCII + Parity	7	Bit 7 (MSB)	8
RS-232 Serial	5-8	After stop bit	Variable
DRAM Memory	64	Separate chip	72 (with ECC)
PCI Bus (legacy)	32	4 parity lines	36

Convention Matters

Both sender and receiver must agree on the parity convention: even vs. odd, and bit position. A mismatch doesn't just fail to detect errors—it causes every valid transmission to appear erroneous!

Visual Representation of Parity

Understanding parity visually can help solidify the concept. Let's examine how data flows through a parity-protected channel.

Transmission Flow:

┌─────────────────────────────────────────────────────────────────────────┐
│                           SENDER SIDE                                   │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                         │
│   Original Data:  1 0 0 0 0 1 1     (7 bits, 3 ones - odd count)       │
│                   ↓                                                     │
│   Parity Calc:    Count 1s → 3 (odd) → Need parity bit = 1 for even    │
│                   ↓                                                     │
│   Transmitted:    1 0 0 0 0 1 1 [1]   (8 bits, 4 ones - even count)    │
│                                 └── Parity bit                          │
└─────────────────────────────────────────────────────────────────────────┘
                                    ↓
                          Transmission Channel
                         (may introduce errors)
                                    ↓
┌─────────────────────────────────────────────────────────────────────────┐
│                          RECEIVER SIDE                                  │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                         │
│   Case 1: No Error                                                      │
│   Received:      1 0 0 0 0 1 1 1    (4 ones - even) ✓ Valid            │
│                                                                         │
│   Case 2: Single Bit Error (bit 3 flipped)                              │
│   Received:      1 0 0 1 0 1 1 1    (5 ones - odd) ✗ Error Detected    │
│                          ↑                                              │
│                       corrupted                                         │
│                                                                         │
│   Case 3: Two Bit Errors (bits 3 and 5 flipped)                         │
│   Received:      1 0 0 1 0 0 1 1    (4 ones - even) ⚠ Undetected!      │
│                          ↑   ↑                                          │
│                       corrupted                                         │
└─────────────────────────────────────────────────────────────────────────┘

The Even-Error Blind Spot

Historical Context: From Telegraphs to Modern Systems

Parity checking has a rich history that parallels the development of digital communication itself.

Timeline of Parity in Computing:

1960s: Magnetic Core Memory As magnetic core memory became standard, parity bits were added to each memory word. This tradition continued into semiconductor memory.

Why Parity Still Matters Today

•Conceptual Foundation — Understanding parity is prerequisite to understanding Hamming codes, CRC, RAID, and other error detection/correction schemes
•Low Overhead — For applications where space is critical and error rates are low, a single parity bit may be sufficient
•Fast Computation — XOR-based parity calculation is essentially free in hardware
•Serial Communication — Many embedded systems and legacy protocols still use parity as their primary error check
•Educational Value — Parity perfectly illustrates the tradeoff between redundancy and error detection capability

Summary: Even and Odd Parity

We have explored the foundational concepts of parity checking, the simplest form of error detection in digital communication. Let's consolidate the key concepts:

Key Takeaways

•Parity is about counting ones — Even parity ensures an even total of 1-bits; odd parity ensures an odd total
•Single bit overhead — Only one additional bit is needed per data unit
•XOR enables efficient calculation — Parity can be computed by XORing all bits together
•Detects odd numbers of errors — Any 1, 3, 5, etc. bit errors will be detected
•Cannot detect even numbers of errors — Pairs of errors cancel out and go undetected
•Cannot correct errors — Parity only tells you that an error occurred, not where
•Both schemes are equivalent — Even and odd parity have identical detection capability

What's Next:

Page Complete

1 / 5