Parity Checks & Simple Codes

The simplest error-detecting and error-correcting schemes

Roadmap

Historical Context

The Parity Bit

Single Parity Check Code

Python: Parity Encoding

def encode_even_parity(data: str) -> str:
    """Append an even parity bit to a binary string."""
    parity = sum(int(b) for b in data) % 2
    return data + str(parity)

def check_even_parity(codeword: str) -> bool:
    """Check if a codeword has valid even parity."""
    return sum(int(b) for b in codeword) % 2 == 0

# Encoding examples
print(encode_even_parity("1011001"))  # "10110010" (4 ones, parity=0)
print(encode_even_parity("1010001"))  # "10100011" (4 ones, parity=1)

# Detection examples
print(check_even_parity("10110010"))  # True  - no error
print(check_even_parity("10110011"))  # False - 1 bit flipped!
print(check_even_parity("10110001"))  # True  - 2 bits flipped, UNDETECTED!

When Parity Fails

Repetition Codes

Majority Voting Decoder

def repetition_encode(bit: str, n: int = 3) -> str:
    """Encode a single bit using n-fold repetition."""
    return bit * n

def majority_vote_decode(received: str) -> str:
    """Decode using majority voting."""
    ones = received.count('1')
    return '1' if ones > len(received) // 2 else '0'

# Encode and simulate error
encoded = repetition_encode('1', 3)  # "111"
received = "110"  # one bit flipped
decoded = majority_vote_decode(received)  # "1" - correct!

Repetition Code Performance

from math import comb

def repetition_error_prob(p, n):
    """Probability of decoding error for [n,1,n] repetition code.
    Error occurs when more than n//2 bits are flipped."""
    t = n // 2  # correction capability
    p_error = sum(comb(n, i) * p**i * (1-p)**(n-i)
                  for i in range(t + 1, n + 1))
    return p_error

# Compare for p = 0.01
for n in [1, 3, 5, 7, 9]:
    pe = repetition_error_prob(0.01, n)
    rate = 1/n
    print(f"[{n},1,{n}]: P_error = {pe:.2e}, Rate = {rate:.3f}")

Two-Dimensional Parity

  Data bits   | Row
  -----------+-----
  1 0 1 1    |  1
  0 1 1 0    |  0
  1 1 0 1    |  1
  -----------+-----
  0 0 0 0    | Col parity
                

2D Parity: Worked Example

  1 0 1 1 | 1
  0 1 1 0 | 0
  1 1 0 1 | 1
  ---------+--
  0 0 0 0 | 0
                

  1 0 1 1 | 1 ✓
  0 0 1 0 | 0 ✗
  1 1 0 1 | 1 ✓
  ---------+--
  0 0 0 0 | 0
     ✗
                

Python: 2D Parity

def encode_2d_parity(data, rows, cols):
    """Encode data with 2D parity (row + column + corner)."""
    grid = [data[i*cols:(i+1)*cols] for i in range(rows)]
    # Add row parity
    for row in grid:
        row.append(sum(row) % 2)
    # Add column parity row
    col_parity = [sum(grid[r][c] for r in range(rows)) % 2
                  for c in range(cols + 1)]
    grid.append(col_parity)
    return grid

def check_2d_parity(grid):
    """Check 2D parity; return error position or None."""
    rows, cols = len(grid), len(grid[0])
    bad_rows = [r for r in range(rows) if sum(grid[r]) % 2 != 0]
    bad_cols = [c for c in range(cols)
                if sum(grid[r][c] for r in range(rows)) % 2 != 0]
    if not bad_rows and not bad_cols:
        return None  # No error detected
    if len(bad_rows) == 1 and len(bad_cols) == 1:
        return (bad_rows[0], bad_cols[0])  # Single error located!
    return "Multiple errors detected"

# Example
data = [1,0,1,1, 0,1,1,0, 1,1,0,1]
grid = encode_2d_parity(data, 3, 4)
grid[1][1] ^= 1  # Flip bit at (1,1)
print(check_2d_parity(grid))  # (1, 1)

ISBN Check Digits

Python: ISBN Validation

def validate_isbn10(isbn: str) -> bool:
    """Validate an ISBN-10 check digit."""
    isbn = isbn.replace('-', '')
    if len(isbn) != 10:
        return False
    total = 0
    for i, ch in enumerate(isbn):
        if ch == 'X' and i == 9:
            val = 10
        elif ch.isdigit():
            val = int(ch)
        else:
            return False
        total += (i + 1) * val
    return total % 11 == 0

def validate_isbn13(isbn: str) -> bool:
    """Validate an ISBN-13 check digit."""
    isbn = isbn.replace('-', '')
    if len(isbn) != 13 or not isbn.isdigit():
        return False
    weights = [1, 3] * 6 + [1]
    total = sum(int(d) * w for d, w in zip(isbn, weights))
    return total % 10 == 0

# Examples
print(validate_isbn10("0-306-40615-2"))  # True
print(validate_isbn13("978-0-306-40615-7"))  # True
print(validate_isbn10("0-306-40615-3"))  # False (wrong check digit)

ISBN-10: Transposition Detection

The Luhn Algorithm

Python: Luhn Algorithm

def luhn_validate(number: str) -> bool:
    """Validate a number using the Luhn algorithm."""
    digits = [int(d) for d in number if d.isdigit()]
    # Process from right to left, doubling every second digit
    checksum = 0
    for i, d in enumerate(reversed(digits)):
        if i % 2 == 1:  # Every second digit from right
            d *= 2
            if d > 9:
                d -= 9
        checksum += d
    return checksum % 10 == 0

def luhn_generate_check_digit(partial: str) -> int:
    """Generate the Luhn check digit for a partial number."""
    for check in range(10):
        if luhn_validate(partial + str(check)):
            return check
    return -1  # Should never reach here

# Examples
print(luhn_validate("4539148803436467"))  # True
print(luhn_validate("4539148803436468"))  # False
print(luhn_generate_check_digit("453914880343646"))  # 7

Luhn: Strengths & Limitations

Rate vs. Correction Tradeoff

Limitations of Simple Codes

Summary & What's Next