class galois.GLFSR

A Galois linear-feedback shift register (LFSR).

Notes

A Galois LFSR is defined by its feedback (connection) polynomial

\[ f(x) = 1 + a_1 x + a_2 x^2 + \dots + a_{n} x^{n}, \]

where \(f(0) = 1\) and the degree \(n\) equals the length of the shift register. The associated output sequence \(y[t]\) satisfies the linear recurrence

\[ y[t] + a_1 y[t-1] + a_2 y[t-2] + \dots + a_{n} y[t-n] = 0. \]

The characteristic polynomial of the sequence is the reciprocal of the feedback polynomial

\[\begin{split} c(x) &= x^{n} + a_1 x^{n-1} + a_2 x^{n-2} + \dots + a_{n} \\ &= x^{n} f(x^{-1}). \end{split}\]

In the Galois configuration, the shift register is arranged so that its taps implement the recurrence directly. The taps are simply the feedback coefficients \([-a_n, -a_{n-1}, \dots, -a_1]\) in a fixed left-to-right order that matches the chosen shift direction.

Galois LFSR Configuration
 +--------------+<-------------+<-------------+<-------------+
 |              |              |              |              |
 | -a_n         | -a_{n-1}     | -a_{n-2}     | -a_1         |
 | T[0]         | T[1]         | T[2]         | T[n-1]       |
 |  +--------+  v  +--------+  v              v  +--------+  |
 +->|  S[0]  |--+->|  S[1]  |--+---  ...   ---+->| S[n-1] |--+--> y[t]
    +--------+     +--------+                    +--------+
                                                   y[t+1]

The shift register taps \(T\) are defined left-to-right as \(T = [T_0, T_1, \dots, T_{n-2}, T_{n-1}]\). The state vector \(S\) is also defined left-to-right as \(S = [S_0, S_1, \dots, S_{n-2}, S_{n-1}]\).

References

See also

berlekamp_massey

Examples

Create a Galois LFSR from a degree-4 primitive characteristic polynomial over \(\mathrm{GF}(2)\).

In [1]: feedback_poly = galois.primitive_poly(2, 4).reverse(); feedback_poly
Out[1]: Poly(x^4 + x^3 + 1, GF(2))

In [2]: lfsr = galois.GLFSR(feedback_poly)

In [3]: print(lfsr)
Galois LFSR:
  field: GF(2)
  feedback_poly: 1 + x^3 + x^4
  characteristic_poly: x^4 + x + 1
  taps: [1 1 0 0]
  order: 4
  state: [1 1 1 1]
  initial_state: [1 1 1 1]

Step the Galois LFSR and produce 10 output symbols.

In [4]: lfsr.state
Out[4]: GF([1, 1, 1, 1], order=2)

In [5]: lfsr.step(10)
Out[5]: GF([1, 1, 1, 0, 0, 0, 1, 0, 0, 1], order=2)

In [6]: lfsr.state
Out[6]: GF([1, 1, 0, 1], order=2)

Create a Galois LFSR from a degree-4 primitive characteristic polynomial over \(\mathrm{GF}(7)\).

In [7]: feedback_poly = galois.primitive_poly(7, 4).reverse(); feedback_poly
Out[7]: Poly(5x^4 + 3x^3 + x^2 + 1, GF(7))

In [8]: lfsr = galois.GLFSR(feedback_poly)

In [9]: print(lfsr)
Galois LFSR:
  field: GF(7)
  feedback_poly: 1 + x^2 + 3x^3 + 5x^4
  characteristic_poly: x^4 + x^2 + 3x + 5
  taps: [2 4 6 0]
  order: 4
  state: [1 1 1 1]
  initial_state: [1 1 1 1]

Step the Galois LFSR and produce 10 output symbols.

In [10]: lfsr.state
Out[10]: GF([1, 1, 1, 1], order=7)

In [11]: lfsr.step(10)
Out[11]: GF([1, 1, 0, 4, 6, 5, 3, 6, 1, 2], order=7)

In [12]: lfsr.state
Out[12]: GF([4, 3, 0, 1], order=7)

Create a Galois LFSR from a degree-4 primitive characteristic polynomial over \(\mathrm{GF}(2^3)\).

In [13]: feedback_poly = galois.primitive_poly(2**3, 4).reverse(); feedback_poly
Out[13]: Poly(3x^4 + x^3 + 1, GF(2^3))

In [14]: lfsr = galois.GLFSR(feedback_poly)

In [15]: print(lfsr)
Galois LFSR:
  field: GF(2^3)
  feedback_poly: 1 + x^3 + 3x^4
  characteristic_poly: x^4 + x + 3
  taps: [3 1 0 0]
  order: 4
  state: [1 1 1 1]
  initial_state: [1 1 1 1]

Step the Galois LFSR and produce 10 output symbols.

In [16]: lfsr.state
Out[16]: GF([1, 1, 1, 1], order=2^3)

In [17]: lfsr.step(10)
Out[17]: GF([1, 1, 1, 0, 2, 2, 3, 2, 4, 5], order=2^3)

In [18]: lfsr.state
Out[18]: GF([4, 2, 2, 7], order=2^3)

Create a Galois LFSR from a degree-4 primitive characteristic polynomial over \(\mathrm{GF}(3^3)\).

In [19]: feedback_poly = galois.primitive_poly(3**3, 4).reverse(); feedback_poly
Out[19]: Poly(10x^4 + x^3 + 1, GF(3^3))

In [20]: lfsr = galois.GLFSR(feedback_poly)

In [21]: print(lfsr)
Galois LFSR:
  field: GF(3^3)
  feedback_poly: 1 + x^3 + 10x^4
  characteristic_poly: x^4 + x + 10
  taps: [20  2  0  0]
  order: 4
  state: [1 1 1 1]
  initial_state: [1 1 1 1]

Step the Galois LFSR and produce 10 output symbols.

In [22]: lfsr.state
Out[22]: GF([1, 1, 1, 1], order=3^3)

In [23]: lfsr.step(10)
Out[23]: GF([ 1,  1,  1,  0, 19, 19, 20, 11, 25, 24], order=3^3)

In [24]: lfsr.state
Out[24]: GF([23, 25,  6, 26], order=3^3)

Constructors

GLFSR(feedback_poly: Poly, state: ArrayLike | None = None)

Constructs a Galois LFSR from its feedback polynomial \(f(x)\).

classmethod Taps(taps: FieldArray, ...) → Self

Constructs a Galois LFSR from its taps \(T = [-a_n, \dots, -a_2, -a_1]\).

String representation

__repr__() → str

A terse representation of the Galois LFSR.

__str__() → str

A formatted string of relevant properties of the Galois LFSR.

Methods

reset(state: ArrayLike | None = None)

Resets the Galois LFSR state to the specified state.

step(steps: int = 1) → FieldArray

Produces the next steps output symbols.

to_fibonacci_lfsr() → FLFSR

Converts the Galois LFSR to a Fibonacci LFSR that produces the same output.

Properties

property field : type[FieldArray]

The FieldArray subclass for the finite field that defines the linear arithmetic.

property order : int

The order of the linear recurrence and linear recurrent sequence. The order of a sequence is defined by the degree of the connection, feedback, and characteristic polynomials that generate it.

property taps : FieldArray

The shift register taps \(T = [-a_n, \dots, -a_2, -a_1]\). The taps of the shift register define the linear recurrence relation.

Polynomials

property characteristic_poly : Poly

The characteristic polynomial \(c(x) = x^{n} + a_1 x^{n-1} + a_2 x^{n-2} + \dots + a_{n}\).

property feedback_poly : Poly

The feedback polynomial \(f(x) = 1 + a_1 x + a_2 x^2 + \dots + a_{n} x^{n}\).

State

property initial_state : FieldArray

The initial state vector \(S = [S_0, S_1, \dots, S_{n-2}, S_{n-1}]\).

property state : FieldArray

The current state vector \(S = [S_0, S_1, \dots, S_{n-2}, S_{n-1}]\).