tessl/pypi-galois

A performant NumPy extension for Galois fields and their applications

—

Pending

Overview

Eval results

Files

Error Correction Codes

Name: tessl/pypi-galois
Author: tessl

Forward error correction implementations including BCH (Bose-Chaudhuri-Hocquenghem) and Reed-Solomon codes. These codes provide robust error detection and correction capabilities for digital communications and data storage systems.

Capabilities

BCH Codes

BCH codes are cyclic linear block codes that can correct multiple random errors. They are particularly useful for correcting random errors in digital communications.

class BCH:
    """
    A general BCH(n, k) code over GF(q).
    
    BCH codes are [n, k, d]_q linear block codes with codeword size n,
    message size k, minimum distance d, and symbols from alphabet of size q.
    """
    
    def __init__(self, n, k, c=1, extension_field=None, primitive_poly=None, primitive_element=None, systematic=True):
        """
        Construct BCH(n, k) code.
        
        Parameters:
        - n (int): Codeword size (must divide q^m - 1)
        - k (int): Message size  
        - c (int): First consecutive root, default 1
        - extension_field: Extension field for code construction
        - primitive_poly: Primitive polynomial for extension field
        - primitive_element: Primitive element for extension field
        - systematic (bool): Whether to use systematic encoding, default True
        """
    
    # Properties
    @property
    def field(self) -> type:
        """The Galois field the code is defined over."""
    
    @property
    def n(self) -> int:
        """The codeword size."""
    
    @property
    def k(self) -> int:
        """The message size."""
    
    @property
    def d(self) -> int:
        """The minimum distance."""
    
    @property
    def t(self) -> int:
        """The error correcting capability."""
    
    @property
    def generator_poly(self) -> Poly:
        """The generator polynomial g(x)."""
    
    @property
    def parity_check_poly(self) -> Poly:
        """The parity check polynomial h(x)."""
    
    @property
    def G(self) -> FieldArray:
        """The generator matrix G."""
    
    @property
    def H(self) -> FieldArray:
        """The parity check matrix H."""
    
    @property
    def is_systematic(self) -> bool:
        """Whether the code is systematic."""
    
    # Encoding and decoding
    def encode(self, message, parity_only=False):
        """
        Encode message into codeword.
        
        Parameters:
        - message: Message array of length k (or multiple messages)
        - parity_only (bool): Return only parity symbols if True
        
        Returns:
        FieldArray: Encoded codeword(s) of length n (or n-k if parity_only=True)
        """
    
    def decode(self, codeword, errors=False, output="message"):
        """
        Decode received codeword.
        
        Parameters:
        - codeword: Received codeword array of length n (or multiple codewords)
        - errors (bool): Return number of corrected errors if True
        - output (str): Output format - "message", "codeword", or "both"
        
        Returns:
        FieldArray or tuple: Decoded message/codeword, optionally with error count
        """
    
    def detect(self, codeword):
        """
        Detect errors in received codeword without correction.
        
        Parameters:
        - codeword: Received codeword array of length n
        
        Returns:
        bool or np.ndarray: True if errors detected, False otherwise
        """

Reed-Solomon Codes

Reed-Solomon codes are a subset of BCH codes that achieve the Singleton bound and are optimal for correcting burst errors. They are widely used in digital communications, data storage, and QR codes.

class ReedSolomon:
    """
    A general RS(n, k) code over GF(q).
    
    Reed-Solomon codes are [n, k, n-k+1]_q linear block codes with
    maximum distance separable property.
    """
    
    def __init__(self, n, k, c=1, field=None, primitive_poly=None, primitive_element=None, systematic=True):
        """
        Construct RS(n, k) code.
        
        Parameters:
        - n (int): Codeword size (must be ≤ field order)
        - k (int): Message size
        - c (int): First consecutive root, default 1  
        - field: Galois field for the code, auto-selected if None
        - primitive_poly: Primitive polynomial for field construction
        - primitive_element: Primitive element for field construction
        - systematic (bool): Whether to use systematic encoding, default True
        """
    
    # Properties (same as BCH)
    @property
    def field(self) -> type:
        """The Galois field the code is defined over."""
    
    @property
    def n(self) -> int:
        """The codeword size."""
    
    @property
    def k(self) -> int:
        """The message size.""" 
    
    @property
    def d(self) -> int:
        """The minimum distance (equals n-k+1)."""
    
    @property
    def t(self) -> int:
        """The error correcting capability (equals floor((d-1)/2))."""
    
    @property
    def generator_poly(self) -> Poly:
        """The generator polynomial g(x)."""
    
    @property
    def parity_check_poly(self) -> Poly:
        """The parity check polynomial h(x)."""
    
    @property
    def G(self) -> FieldArray:
        """The generator matrix G."""
    
    @property
    def H(self) -> FieldArray:
        """The parity check matrix H."""
    
    @property
    def is_systematic(self) -> bool:
        """Whether the code is systematic."""
    
    # Encoding and decoding (same interface as BCH)
    def encode(self, message, parity_only=False):
        """
        Encode message into codeword.
        
        Parameters:
        - message: Message array of length k (or multiple messages)
        - parity_only (bool): Return only parity symbols if True
        
        Returns:
        FieldArray: Encoded codeword(s) of length n (or n-k if parity_only=True)
        """
    
    def decode(self, codeword, errors=False, output="message"):
        """
        Decode received codeword with error correction.
        
        Parameters:
        - codeword: Received codeword array of length n (or multiple codewords)
        - errors (bool): Return number of corrected errors if True
        - output (str): Output format - "message", "codeword", or "both"
        
        Returns:
        FieldArray or tuple: Decoded message/codeword, optionally with error count
        """
    
    def detect(self, codeword):
        """
        Detect errors in received codeword without correction.
        
        Parameters:
        - codeword: Received codeword array of length n
        
        Returns:
        bool or np.ndarray: True if errors detected, False otherwise
        """

Usage Examples

Basic BCH Code Usage

import galois
import numpy as np

# Create BCH(15, 7) code over GF(2)
bch = galois.BCH(15, 7)
print(f"BCH code: {bch}")
print(f"Field: {bch.field.name}")
print(f"Parameters: n={bch.n}, k={bch.k}, d={bch.d}, t={bch.t}")

# Get field for creating messages
GF = bch.field

# Encode a message
message = GF([1, 0, 1, 1, 0, 1, 0])  # k=7 bits
codeword = bch.encode(message)
print(f"Message: {message}")
print(f"Codeword: {codeword}")

# Add errors to codeword
received = codeword.copy()
received[0] ^= 1  # Flip first bit
received[5] ^= 1  # Flip sixth bit
print(f"Received (with 2 errors): {received}")

# Decode with error correction
decoded_msg, num_errors = bch.decode(received, errors=True)
print(f"Decoded message: {decoded_msg}")
print(f"Number of corrected errors: {num_errors}")
print(f"Decoding successful: {np.array_equal(decoded_msg, message)}")

Reed-Solomon Code Usage

import galois
import numpy as np

# Create RS(255, 223) code (commonly used in telecommunications)
rs = galois.ReedSolomon(255, 223)
print(f"Reed-Solomon code: {rs}")
print(f"Field: {rs.field.name}")
print(f"Parameters: n={rs.n}, k={rs.k}, d={rs.d}, t={rs.t}")

# Get field for creating messages
GF = rs.field

# Encode a message
message = GF.Random(rs.k)  # Random k-symbol message
codeword = rs.encode(message)
print(f"Message length: {len(message)}")
print(f"Codeword length: {len(codeword)}")

# Simulate burst errors
received = codeword.copy()
error_positions = [10, 11, 12, 13, 14]  # 5 consecutive errors
for pos in error_positions:
    received[pos] = GF.Random()  # Random error

print(f"Added {len(error_positions)} errors at positions {error_positions}")

# Decode with error correction
try:
    decoded_msg, num_errors = rs.decode(received, errors=True)
    print(f"Number of corrected errors: {num_errors}")
    print(f"Decoding successful: {np.array_equal(decoded_msg, message)}")
except Exception as e:
    print(f"Decoding failed: {e}")

Shortened Codes

import galois

# Create full RS(31, 21) code
rs_full = galois.ReedSolomon(31, 21)
print(f"Full code: {rs_full}")

# Use as shortened RS(25, 15) code
k_short = 15  # Shortened message length
n_short = 25  # Shortened codeword length

# Encode shortened message
GF = rs_full.field
message_short = GF.Random(k_short)
codeword_short = rs_full.encode(message_short)[:n_short]

print(f"Shortened message length: {len(message_short)}")
print(f"Shortened codeword length: {len(codeword_short)}")

# Decode shortened codeword
decoded_short = rs_full.decode(codeword_short)
print(f"Shortened decoding successful: {np.array_equal(decoded_short, message_short)}")

Systematic vs Non-Systematic Encoding

import galois

# Systematic encoding (default)
bch_sys = galois.BCH(15, 7, systematic=True)
message = galois.GF(2)([1, 0, 1, 1, 0, 1, 0])

# In systematic encoding, message appears unchanged in codeword
codeword_sys = bch_sys.encode(message)
print(f"Message: {message}")
print(f"Systematic codeword: {codeword_sys}")
print(f"Message part: {codeword_sys[:bch_sys.k]}")
print(f"Parity part: {codeword_sys[bch_sys.k:]}")

# Get only parity symbols
parity_only = bch_sys.encode(message, parity_only=True)
print(f"Parity symbols only: {parity_only}")

Error Detection Only

import galois

# Create RS code for error detection
rs = galois.ReedSolomon(31, 21)
GF = rs.field

# Encode message
message = GF.Random(rs.k)
codeword = rs.encode(message)

# Test error detection
clean_detected = rs.detect(codeword)
print(f"Clean codeword errors detected: {clean_detected}")

# Add errors
corrupted = codeword.copy()
corrupted[0] = GF.Random()
corrupted[10] = GF.Random()

errors_detected = rs.detect(corrupted)
print(f"Corrupted codeword errors detected: {errors_detected}")

Batch Processing

import galois

# Create RS code
rs = galois.ReedSolomon(15, 9)
GF = rs.field

# Encode multiple messages at once
messages = GF.Random((5, rs.k))  # 5 messages
codewords = rs.encode(messages)  # Batch encoding

print(f"Batch encoded {messages.shape[0]} messages")
print(f"Messages shape: {messages.shape}")
print(f"Codewords shape: {codewords.shape}")

# Add errors to all codewords
corrupted = codewords.copy()
corrupted[:, 0] = GF.Random(5)  # Error in first position of each codeword

# Batch decode
decoded_messages, error_counts = rs.decode(corrupted, errors=True)
print(f"Decoded messages shape: {decoded_messages.shape}")
print(f"Error counts: {error_counts}")
print(f"All decoded correctly: {np.array_equal(decoded_messages, messages)}")

Performance and Implementation Notes

Algorithmic Efficiency: Uses efficient syndrome-based decoding algorithms
Memory Optimization: Systematic encoding reduces storage requirements
Batch Processing: Supports vectorized encoding/decoding of multiple messages
Field Integration: Seamlessly works with any finite field created by GF()
Error Bounds: BCH codes can correct up to t errors, RS codes achieve maximum distance separable bound
Shortened Codes: Support for shortened codes without reconstructing the full code