tessl/pypi-galois

A performant NumPy extension for Galois fields and their applications

—

Pending

Overview

Eval results

Files

Linear Feedback Shift Registers

Name: tessl/pypi-galois
Author: tessl

Linear Feedback Shift Register (LFSR) implementations for sequence generation and analysis over finite fields. Includes both Fibonacci and Galois configurations along with the Berlekamp-Massey algorithm for minimal polynomial computation.

Capabilities

Fibonacci Linear Feedback Shift Register

The Fibonacci LFSR (FLFSR) uses feedback connections from multiple stages to generate pseudorandom sequences. The feedback is applied to the input of the shift register.

class FLFSR:
    """
    A Fibonacci Linear Feedback Shift Register over GF(q).
    
    In Fibonacci configuration, the feedback connections tap off multiple 
    stages and feed back to the input of the shift register.
    """
    
    def __init__(self, feedback_poly, state=None):
        """
        Create Fibonacci LFSR from feedback polynomial.
        
        Parameters:
        - feedback_poly (Poly): Feedback polynomial f(x) defining the LFSR.
          Must have degree n and constant term 1.
        - state (ArrayLike, optional): Initial state vector of length n.
          Defaults to all-ones if None.
        """
    
    @classmethod
    def Taps(cls, taps, state=None):
        """
        Create Fibonacci LFSR from tap configuration.
        
        Parameters:
        - taps (FieldArray): Tap coefficients [c_{n-1}, c_{n-2}, ..., c_1, c_0]
        - state (ArrayLike, optional): Initial state vector
        
        Returns:
        FLFSR: Fibonacci LFSR instance
        """
    
    # Properties
    @property
    def field(self) -> type:
        """The Galois field the LFSR operates over."""
    
    @property
    def feedback_poly(self) -> Poly:
        """The feedback polynomial f(x)."""
    
    @property
    def characteristic_poly(self) -> Poly:
        """The characteristic polynomial c(x) = x^n * f(1/x)."""
    
    @property
    def taps(self) -> FieldArray:
        """The tap configuration coefficients."""
    
    @property
    def order(self) -> int:
        """The order (degree) of the LFSR."""
    
    @property
    def state(self) -> FieldArray:
        """The current state vector."""
    
    @property
    def initial_state(self) -> FieldArray:
        """The initial state vector."""
    
    # Methods  
    def reset(self, state=None):
        """
        Reset LFSR to initial or specified state.
        
        Parameters:
        - state (ArrayLike, optional): New state vector, uses initial_state if None
        """
    
    def step(self, steps=1) -> FieldArray:
        """
        Step the LFSR forward and return output symbols.
        
        Parameters:
        - steps (int): Number of steps to advance, default 1
        
        Returns:
        FieldArray: Output symbols for each step
        """
    
    def generate(self, length) -> FieldArray:
        """
        Generate sequence of specified length.
        
        Parameters:
        - length (int): Length of sequence to generate
        
        Returns:
        FieldArray: Generated sequence
        """
    
    def to_galois_lfsr(self):
        """
        Convert to equivalent Galois LFSR.
        
        Returns:
        GLFSR: Equivalent Galois LFSR
        """

Galois Linear Feedback Shift Register

The Galois LFSR (GLFSR) uses feedback connections that tap off the output and feed into multiple stages. This configuration is also known as a "many-to-one" LFSR.

class GLFSR:
    """
    A Galois Linear Feedback Shift Register over GF(q).
    
    In Galois configuration, the feedback connections tap off the output
    and feed into multiple intermediate stages of the shift register.
    """
    
    def __init__(self, feedback_poly, state=None):
        """
        Create Galois LFSR from feedback polynomial.
        
        Parameters:
        - feedback_poly (Poly): Feedback polynomial f(x) defining the LFSR.
          Must have degree n and constant term 1.
        - state (ArrayLike, optional): Initial state vector of length n.
          Defaults to all-ones if None.
        """
    
    @classmethod
    def Taps(cls, taps, state=None):
        """
        Create Galois LFSR from tap configuration.
        
        Parameters:
        - taps (FieldArray): Tap coefficients [c_0, c_1, ..., c_{n-2}, c_{n-1}]
        - state (ArrayLike, optional): Initial state vector
        
        Returns:
        GLFSR: Galois LFSR instance
        """
    
    # Properties (same as FLFSR)
    @property
    def field(self) -> type:
        """The Galois field the LFSR operates over."""
    
    @property
    def feedback_poly(self) -> Poly:
        """The feedback polynomial f(x)."""
    
    @property
    def characteristic_poly(self) -> Poly:
        """The characteristic polynomial c(x) = x^n * f(1/x)."""
    
    @property
    def taps(self) -> FieldArray:
        """The tap configuration coefficients."""
    
    @property
    def order(self) -> int:
        """The order (degree) of the LFSR."""
    
    @property
    def state(self) -> FieldArray:
        """The current state vector."""
    
    @property
    def initial_state(self) -> FieldArray:
        """The initial state vector."""
    
    # Methods (same interface as FLFSR)
    def reset(self, state=None):
        """
        Reset LFSR to initial or specified state.
        
        Parameters:
        - state (ArrayLike, optional): New state vector, uses initial_state if None
        """
    
    def step(self, steps=1) -> FieldArray:
        """
        Step the LFSR forward and return output symbols.
        
        Parameters:
        - steps (int): Number of steps to advance, default 1
        
        Returns:
        FieldArray: Output symbols for each step
        """
    
    def generate(self, length) -> FieldArray:
        """
        Generate sequence of specified length.
        
        Parameters:
        - length (int): Length of sequence to generate
        
        Returns:
        FieldArray: Generated sequence
        """
    
    def to_fibonacci_lfsr(self):
        """
        Convert to equivalent Fibonacci LFSR.
        
        Returns:
        FLFSR: Equivalent Fibonacci LFSR
        """

Berlekamp-Massey Algorithm

Algorithm for finding the shortest LFSR that can generate a given sequence, computing the minimal polynomial of a linear recurrence sequence.

def berlekamp_massey(sequence):
    """
    Find minimal polynomial of linear recurrence sequence using Berlekamp-Massey algorithm.
    
    This algorithm finds the shortest Linear Feedback Shift Register (LFSR)
    that can generate the given sequence.
    
    Parameters:
    - sequence (ArrayLike): Input sequence over finite field
    
    Returns:
    Poly: Minimal polynomial (characteristic polynomial of shortest LFSR)
    
    Note: The sequence must be from a finite field. The algorithm works over
    any finite field created by GF().
    """

Usage Examples

Creating and Using Fibonacci LFSR

import galois

# Create GF(2) for binary LFSR
GF = galois.GF(2)

# Define feedback polynomial: x^4 + x + 1 (primitive polynomial)
feedback_poly = galois.Poly([1, 0, 0, 1, 1], field=GF)  # x^4 + x + 1
print(f"Feedback polynomial: {feedback_poly}")

# Create Fibonacci LFSR
lfsr = galois.FLFSR(feedback_poly)
print(f"LFSR order: {lfsr.order}")
print(f"Initial state: {lfsr.state}")
print(f"Taps: {lfsr.taps}")

# Generate sequence
sequence = lfsr.generate(15)  # Generate 15 symbols
print(f"Generated sequence: {sequence}")

# Reset and step manually
lfsr.reset()
print(f"After reset: {lfsr.state}")

output = lfsr.step(5)  # Step 5 times
print(f"5 output symbols: {output}")
print(f"Current state: {lfsr.state}")

Creating LFSR from Taps

import galois

GF = galois.GF(2)

# Create LFSR using tap coefficients instead of polynomial
# For x^4 + x + 1, taps are [0, 0, 1, 1] in Fibonacci form
taps = GF([0, 0, 1, 1])  # [c_3, c_2, c_1, c_0]
lfsr = galois.FLFSR.Taps(taps)

print(f"Created from taps: {taps}")
print(f"Feedback polynomial: {lfsr.feedback_poly}")
print(f"Characteristic polynomial: {lfsr.characteristic_poly}")

# Generate with custom initial state
custom_state = GF([1, 0, 1, 0])
lfsr.reset(custom_state)
sequence = lfsr.generate(10)
print(f"Sequence with custom state {custom_state}: {sequence}")

Using Galois LFSR

import galois

GF = galois.GF(2)

# Same feedback polynomial as before
feedback_poly = galois.Poly([1, 0, 0, 1, 1], field=GF)

# Create Galois LFSR
glfsr = galois.GLFSR(feedback_poly)
print(f"Galois LFSR taps: {glfsr.taps}")

# Generate sequence (should be same as Fibonacci LFSR with same polynomial)
g_sequence = glfsr.generate(15)
print(f"Galois LFSR sequence: {g_sequence}")

# Convert between LFSR types
flfsr_equivalent = glfsr.to_fibonacci_lfsr()
print(f"Converted to Fibonacci LFSR: {flfsr_equivalent.feedback_poly}")

Working with Non-Binary Fields

import galois

# Create LFSR over GF(3)
GF3 = galois.GF(3)

# Define feedback polynomial over GF(3)
feedback_poly = galois.Poly([1, 2, 0, 1], field=GF3)  # x^3 + 2x^2 + 1
print(f"GF(3) feedback polynomial: {feedback_poly}")

# Create LFSR
lfsr_gf3 = galois.FLFSR(feedback_poly)
print(f"Order: {lfsr_gf3.order}")
print(f"Field: {lfsr_gf3.field.name}")

# Generate sequence over GF(3)
sequence_gf3 = lfsr_gf3.generate(20)
print(f"GF(3) sequence: {sequence_gf3}")

# Calculate period (should divide 3^3 - 1 = 26)
full_period = lfsr_gf3.generate(30)
print(f"First 30 symbols: {full_period}")

Berlekamp-Massey Algorithm

import galois

GF = galois.GF(2)

# Create a known LFSR and generate sequence
original_poly = galois.Poly([1, 0, 1, 1], field=GF)  # x^3 + x + 1
lfsr = galois.FLFSR(original_poly)
known_sequence = lfsr.generate(10)

print(f"Original polynomial: {original_poly}")
print(f"Known sequence: {known_sequence}")

# Use Berlekamp-Massey to recover minimal polynomial
recovered_poly = galois.berlekamp_massey(known_sequence)
print(f"Recovered minimal polynomial: {recovered_poly}")

# Verify by creating LFSR with recovered polynomial
recovered_lfsr = galois.FLFSR(recovered_poly)
recovered_sequence = recovered_lfsr.generate(10)
print(f"Recovered sequence: {recovered_sequence}")
print(f"Sequences match: {np.array_equal(known_sequence, recovered_sequence)}")

Maximum Length Sequences

import galois

GF = galois.GF(2)

# Use primitive polynomial to get maximum length sequence (m-sequence)
primitive_poly = galois.primitive_poly(GF, 4)  # Degree 4 primitive polynomial
print(f"Primitive polynomial: {primitive_poly}")

# Create LFSR with primitive polynomial
lfsr = galois.FLFSR(primitive_poly)

# Generate full period (should be 2^4 - 1 = 15 for degree 4)
max_length_seq = lfsr.generate(15)
print(f"Maximum length sequence: {max_length_seq}")
print(f"Sequence length: {len(max_length_seq)}")

# Next symbol should repeat the sequence
next_symbol = lfsr.step(1)
print(f"Next symbol (should equal first): {next_symbol[0]} == {max_length_seq[0]} ? {next_symbol[0] == max_length_seq[0]}")

# Check period properties
unique_states = set()
lfsr.reset()
for i in range(16):  # Check one more than period
    state_tuple = tuple(lfsr.state)
    if state_tuple in unique_states:
        print(f"Period detected at step {i}")
        break
    unique_states.add(state_tuple)
    lfsr.step(1)

Sequence Analysis

import galois

# Analyze unknown sequence
GF = galois.GF(2)
unknown_sequence = GF([1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1])

# Find minimal polynomial
minimal_poly = galois.berlekamp_massey(unknown_sequence)
print(f"Minimal polynomial: {minimal_poly}")
print(f"LFSR complexity (degree): {minimal_poly.degree}")

# Create LFSR from minimal polynomial
analysis_lfsr = galois.FLFSR(minimal_poly)

# Find what initial state produces this sequence
# Try different initial states
for trial_state in GF.elements[:2**minimal_poly.degree]:
    if trial_state.size == 1:
        continue  # Skip scalar, need vector
        
    # Convert to proper shape
    state_vector = GF([trial_state] * minimal_poly.degree)
    analysis_lfsr.reset(state_vector)
    
    test_seq = analysis_lfsr.generate(len(unknown_sequence))
    if np.array_equal(test_seq, unknown_sequence):
        print(f"Found matching initial state: {state_vector}")
        break

Performance and Implementation Notes

Optimized Stepping: Efficient step operations using vectorized field arithmetic
State Management: Automatic state tracking and reset capabilities
Field Integration: Works with any finite field created by GF()
Conversion: Bidirectional conversion between Fibonacci and Galois configurations
Algorithm Efficiency: Berlekamp-Massey algorithm has O(n²) complexity
Memory Efficiency: Minimal memory footprint for state storage