0
# Linear Feedback Shift Registers
1

2
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.
3

4
## Capabilities
5

6
### Fibonacci Linear Feedback Shift Register
7

8
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.
9

10
```python { .api }
11
class FLFSR:
12
    """
13
    A Fibonacci Linear Feedback Shift Register over GF(q).
14
    
15
    In Fibonacci configuration, the feedback connections tap off multiple 
16
    stages and feed back to the input of the shift register.
17
    """
18
    
19
    def __init__(self, feedback_poly, state=None):
20
        """
21
        Create Fibonacci LFSR from feedback polynomial.
22
        
23
        Parameters:
24
        - feedback_poly (Poly): Feedback polynomial f(x) defining the LFSR.
25
          Must have degree n and constant term 1.
26
        - state (ArrayLike, optional): Initial state vector of length n.
27
          Defaults to all-ones if None.
28
        """
29
    
30
    @classmethod
31
    def Taps(cls, taps, state=None):
32
        """
33
        Create Fibonacci LFSR from tap configuration.
34
        
35
        Parameters:
36
        - taps (FieldArray): Tap coefficients [c_{n-1}, c_{n-2}, ..., c_1, c_0]
37
        - state (ArrayLike, optional): Initial state vector
38
        
39
        Returns:
40
        FLFSR: Fibonacci LFSR instance
41
        """
42
    
43
    # Properties
44
    @property
45
    def field(self) -> type:
46
        """The Galois field the LFSR operates over."""
47
    
48
    @property
49
    def feedback_poly(self) -> Poly:
50
        """The feedback polynomial f(x)."""
51
    
52
    @property
53
    def characteristic_poly(self) -> Poly:
54
        """The characteristic polynomial c(x) = x^n * f(1/x)."""
55
    
56
    @property
57
    def taps(self) -> FieldArray:
58
        """The tap configuration coefficients."""
59
    
60
    @property
61
    def order(self) -> int:
62
        """The order (degree) of the LFSR."""
63
    
64
    @property
65
    def state(self) -> FieldArray:
66
        """The current state vector."""
67
    
68
    @property
69
    def initial_state(self) -> FieldArray:
70
        """The initial state vector."""
71
    
72
    # Methods  
73
    def reset(self, state=None):
74
        """
75
        Reset LFSR to initial or specified state.
76
        
77
        Parameters:
78
        - state (ArrayLike, optional): New state vector, uses initial_state if None
79
        """
80
    
81
    def step(self, steps=1) -> FieldArray:
82
        """
83
        Step the LFSR forward and return output symbols.
84
        
85
        Parameters:
86
        - steps (int): Number of steps to advance, default 1
87
        
88
        Returns:
89
        FieldArray: Output symbols for each step
90
        """
91
    
92
    def generate(self, length) -> FieldArray:
93
        """
94
        Generate sequence of specified length.
95
        
96
        Parameters:
97
        - length (int): Length of sequence to generate
98
        
99
        Returns:
100
        FieldArray: Generated sequence
101
        """
102
    
103
    def to_galois_lfsr(self):
104
        """
105
        Convert to equivalent Galois LFSR.
106
        
107
        Returns:
108
        GLFSR: Equivalent Galois LFSR
109
        """
110
```
111

112
### Galois Linear Feedback Shift Register
113

114
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.
115

116
```python { .api }
117
class GLFSR:
118
    """
119
    A Galois Linear Feedback Shift Register over GF(q).
120
    
121
    In Galois configuration, the feedback connections tap off the output
122
    and feed into multiple intermediate stages of the shift register.
123
    """
124
    
125
    def __init__(self, feedback_poly, state=None):
126
        """
127
        Create Galois LFSR from feedback polynomial.
128
        
129
        Parameters:
130
        - feedback_poly (Poly): Feedback polynomial f(x) defining the LFSR.
131
          Must have degree n and constant term 1.
132
        - state (ArrayLike, optional): Initial state vector of length n.
133
          Defaults to all-ones if None.
134
        """
135
    
136
    @classmethod
137
    def Taps(cls, taps, state=None):
138
        """
139
        Create Galois LFSR from tap configuration.
140
        
141
        Parameters:
142
        - taps (FieldArray): Tap coefficients [c_0, c_1, ..., c_{n-2}, c_{n-1}]
143
        - state (ArrayLike, optional): Initial state vector
144
        
145
        Returns:
146
        GLFSR: Galois LFSR instance
147
        """
148
    
149
    # Properties (same as FLFSR)
150
    @property
151
    def field(self) -> type:
152
        """The Galois field the LFSR operates over."""
153
    
154
    @property
155
    def feedback_poly(self) -> Poly:
156
        """The feedback polynomial f(x)."""
157
    
158
    @property
159
    def characteristic_poly(self) -> Poly:
160
        """The characteristic polynomial c(x) = x^n * f(1/x)."""
161
    
162
    @property
163
    def taps(self) -> FieldArray:
164
        """The tap configuration coefficients."""
165
    
166
    @property
167
    def order(self) -> int:
168
        """The order (degree) of the LFSR."""
169
    
170
    @property
171
    def state(self) -> FieldArray:
172
        """The current state vector."""
173
    
174
    @property
175
    def initial_state(self) -> FieldArray:
176
        """The initial state vector."""
177
    
178
    # Methods (same interface as FLFSR)
179
    def reset(self, state=None):
180
        """
181
        Reset LFSR to initial or specified state.
182
        
183
        Parameters:
184
        - state (ArrayLike, optional): New state vector, uses initial_state if None
185
        """
186
    
187
    def step(self, steps=1) -> FieldArray:
188
        """
189
        Step the LFSR forward and return output symbols.
190
        
191
        Parameters:
192
        - steps (int): Number of steps to advance, default 1
193
        
194
        Returns:
195
        FieldArray: Output symbols for each step
196
        """
197
    
198
    def generate(self, length) -> FieldArray:
199
        """
200
        Generate sequence of specified length.
201
        
202
        Parameters:
203
        - length (int): Length of sequence to generate
204
        
205
        Returns:
206
        FieldArray: Generated sequence
207
        """
208
    
209
    def to_fibonacci_lfsr(self):
210
        """
211
        Convert to equivalent Fibonacci LFSR.
212
        
213
        Returns:
214
        FLFSR: Equivalent Fibonacci LFSR
215
        """
216
```
217

218
### Berlekamp-Massey Algorithm
219

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

222
```python { .api }
223
def berlekamp_massey(sequence):
224
    """
225
    Find minimal polynomial of linear recurrence sequence using Berlekamp-Massey algorithm.
226
    
227
    This algorithm finds the shortest Linear Feedback Shift Register (LFSR)
228
    that can generate the given sequence.
229
    
230
    Parameters:
231
    - sequence (ArrayLike): Input sequence over finite field
232
    
233
    Returns:
234
    Poly: Minimal polynomial (characteristic polynomial of shortest LFSR)
235
    
236
    Note: The sequence must be from a finite field. The algorithm works over
237
    any finite field created by GF().
238
    """
239
```
240

241
## Usage Examples
242

243
### Creating and Using Fibonacci LFSR
244

245
```python
246
import galois
247

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

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

255
# Create Fibonacci LFSR
256
lfsr = galois.FLFSR(feedback_poly)
257
print(f"LFSR order: {lfsr.order}")
258
print(f"Initial state: {lfsr.state}")
259
print(f"Taps: {lfsr.taps}")
260

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

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

269
output = lfsr.step(5)  # Step 5 times
270
print(f"5 output symbols: {output}")
271
print(f"Current state: {lfsr.state}")
272
```
273

274
### Creating LFSR from Taps
275

276
```python
277
import galois
278

279
GF = galois.GF(2)
280

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

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

290
# Generate with custom initial state
291
custom_state = GF([1, 0, 1, 0])
292
lfsr.reset(custom_state)
293
sequence = lfsr.generate(10)
294
print(f"Sequence with custom state {custom_state}: {sequence}")
295
```
296

297
### Using Galois LFSR
298

299
```python
300
import galois
301

302
GF = galois.GF(2)
303

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

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

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

315
# Convert between LFSR types
316
flfsr_equivalent = glfsr.to_fibonacci_lfsr()
317
print(f"Converted to Fibonacci LFSR: {flfsr_equivalent.feedback_poly}")
318
```
319

320
### Working with Non-Binary Fields
321

322
```python
323
import galois
324

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

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

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

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

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

346
### Berlekamp-Massey Algorithm
347

348
```python
349
import galois
350

351
GF = galois.GF(2)
352

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

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

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

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

372
### Maximum Length Sequences
373

374
```python
375
import galois
376

377
GF = galois.GF(2)
378

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

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

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

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

395
# Check period properties
396
unique_states = set()
397
lfsr.reset()
398
for i in range(16):  # Check one more than period
399
    state_tuple = tuple(lfsr.state)
400
    if state_tuple in unique_states:
401
        print(f"Period detected at step {i}")
402
        break
403
    unique_states.add(state_tuple)
404
    lfsr.step(1)
405
```
406

407
### Sequence Analysis
408

409
```python
410
import galois
411

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

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

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

424
# Find what initial state produces this sequence
425
# Try different initial states
426
for trial_state in GF.elements[:2**minimal_poly.degree]:
427
    if trial_state.size == 1:
428
        continue  # Skip scalar, need vector
429
        
430
    # Convert to proper shape
431
    state_vector = GF([trial_state] * minimal_poly.degree)
432
    analysis_lfsr.reset(state_vector)
433
    
434
    test_seq = analysis_lfsr.generate(len(unknown_sequence))
435
    if np.array_equal(test_seq, unknown_sequence):
436
        print(f"Found matching initial state: {state_vector}")
437
        break
438
```
439

440
## Performance and Implementation Notes
441

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