Even and Odd Parity — Parity Check | OneNoughtOne

0/240

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 \oplus 0 \oplus 1 \oplus 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 \to parity bit = 0 If the count of 1s is odd \to 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 Example

Let's transmit the 7-bit ASCII character 'A' (1000001) using even parity.

1
Step 1
$Data to send: 1000001 (ASCII 'A')$
2
Step 2
$Count the 1s: There are 2 ones (positions 0 and 6)$
3
Step 3
$Is the count even? Yes, 2 is even$
4
Step 4
$Parity bit: 0 (to keep total even)$
5
Step 5
$Transmitted sequence: 10000010 (data + parity bit)$
6
Step 6
$Verification: Total 1s = 2, which is even ✓$

Even Parity with Odd Data

Now let's transmit the 7-bit ASCII character 'C' (1000011) using even parity.

1
Step 1
$Data to send: 1000011 (ASCII 'C')$
2
Step 2
$Count the 1s: There are 3 ones$
3
Step 3
$Is the count even? No, 3 is odd$
4
Step 4
$Parity bit: 1 (to make total even: 3 + 1 = 4)$
5
Step 5
$Transmitted sequence: 10000111 (data + parity bit)$
6
Step 6
$Verification: Total 1s = 4, which is even ✓$

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
60
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"
Corrupted: {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 \to parity bit = 0 If the count of 1s is even \to 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 1

Transmit 'A' (1000001) with odd parity.

1
Step 1
$Data: 1000001$
2
Step 2
$Count of 1s: 2 (even)$
3
Step 3
$Parity bit: 1$
4
Step 4
$Transmitted: 10000011$
5
Step 5
$Total 1s: 3 (odd) ✓$

Odd Parity Example 2

Transmit 'C' (1000011) with odd parity.

1
Step 1
$Data: 1000011$
2
Step 2
$Count of 1s: 3 (odd)$
3
Step 3
$Parity bit: 0$
4
Step 4
$Transmitted: 10000110$
5
Step 5
$Total 1s: 3 (odd) ✓$

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 \oplus 0 = a Self-inverse: a \oplus a = 0 Commutativity: a \oplus b = b \oplus a Associativity: (a \oplus b) \oplus c = a \oplus (b \oplus 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 \oplus 0 \oplus 1 \oplus 1 \oplus 0 = ? Step by step: 1 \oplus 0 = 1 1 \oplus 1 = 0 0 \oplus 1 = 1 1 \oplus 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
77
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("
Efficient 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 \to 10000010 (parity at end) Used in: ASCII serial transmission, many protocols 2. Leading Parity The parity bit precedes the data bits. Example: Data 1000001 \to 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

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.

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 \oplus 0 \oplus 1 \oplus 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 \to parity bit = 0 If the count of 1s is odd \to 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 Example

Let's transmit the 7-bit ASCII character 'A' (1000001) using even parity.

1
Step 1
$Data to send: 1000001 (ASCII 'A')$
2
Step 2
$Count the 1s: There are 2 ones (positions 0 and 6)$
3
Step 3
$Is the count even? Yes, 2 is even$
4
Step 4
$Parity bit: 0 (to keep total even)$
5
Step 5
$Transmitted sequence: 10000010 (data + parity bit)$
6
Step 6
$Verification: Total 1s = 2, which is even ✓$

Even Parity with Odd Data

Now let's transmit the 7-bit ASCII character 'C' (1000011) using even parity.

1
Step 1
$Data to send: 1000011 (ASCII 'C')$
2
Step 2
$Count the 1s: There are 3 ones$
3
Step 3
$Is the count even? No, 3 is odd$
4
Step 4
$Parity bit: 1 (to make total even: 3 + 1 = 4)$
5
Step 5
$Transmitted sequence: 10000111 (data + parity bit)$
6
Step 6
$Verification: Total 1s = 4, which is even ✓$

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
60
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"
Corrupted: {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 \to parity bit = 0 If the count of 1s is even \to 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 1

Transmit 'A' (1000001) with odd parity.

1
Step 1
$Data: 1000001$
2
Step 2
$Count of 1s: 2 (even)$
3
Step 3
$Parity bit: 1$
4
Step 4
$Transmitted: 10000011$
5
Step 5
$Total 1s: 3 (odd) ✓$

Odd Parity Example 2

Transmit 'C' (1000011) with odd parity.

1
Step 1
$Data: 1000011$
2
Step 2
$Count of 1s: 3 (odd)$
3
Step 3
$Parity bit: 0$
4
Step 4
$Transmitted: 10000110$
5
Step 5
$Total 1s: 3 (odd) ✓$

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 \oplus 0 = a Self-inverse: a \oplus a = 0 Commutativity: a \oplus b = b \oplus a Associativity: (a \oplus b) \oplus c = a \oplus (b \oplus 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 \oplus 0 \oplus 1 \oplus 1 \oplus 0 = ? Step by step: 1 \oplus 0 = 1 1 \oplus 1 = 0 0 \oplus 1 = 1 1 \oplus 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
77
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("
Efficient 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 \to 10000010 (parity at end) Used in: ASCII serial transmission, many protocols 2. Leading Parity The parity bit precedes the data bits. Example: Data 1000001 \to 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

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.

Even and Odd Parity

The Simplest Guardian of Data Integrity

The Fundamental Problem: Bit Errors in Transmission

The Concept of Parity

Even Parity Scheme

Step 1

Step 2

Step 3

Step 4

Step 5

Step 6

Step 1

Step 2

Step 3

Step 4

Step 5

Step 6

Odd Parity Scheme

Step 1

Step 2

Step 3

Step 4

Step 5

Step 1

Step 2

Step 3

Step 4

Step 5

Mathematical Foundation: Modular Arithmetic and XOR

Parity Bit Positioning Conventions

Visual Representation of Parity

There’s more to understand.

Even and Odd Parity

The Simplest Guardian of Data Integrity

The Fundamental Problem: Bit Errors in Transmission

The Concept of Parity

Even Parity Scheme

Step 1

Step 2

Step 3

Step 4

Step 5

Step 6

Step 1

Step 2

Step 3

Step 4

Step 5

Step 6

Odd Parity Scheme

Step 1

Step 2

Step 3

Step 4

Step 5

Step 1

Step 2

Step 3

Step 4

Step 5

Mathematical Foundation: Modular Arithmetic and XOR

Parity Bit Positioning Conventions

Visual Representation of Parity

There’s more to understand.