galois.GLFSR

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

A Galois linear-feedback shift register (LFSR).

Notes

A Galois LFSR is defined by its feedback polynomial \(f(x)\).

\[f(x) = -c_{0}x^{n} - c_{1}x^{n-1} - \dots - c_{n-2}x^{2} - c_{n-1}x + 1 = x^n c(x^{-1})\]

The feedback polynomial is the reciprocal of the characteristic polynomial \(c(x)\) of the linear recurrent sequence \(y\) produced by the Galois LFSR.

\[c(x) = x^{n} - c_{n-1}x^{n-1} - c_{n-2}x^{n-2} - \dots - c_{1}x - c_{0}\]
\[y_t = c_{n-1}y_{t-1} + c_{n-2}y_{t-2} + \dots + c_{1}y_{t-n+2} + c_{0}y_{t-n+1}\]
Galois LFSR Configuration
 +--------------+<-------------+<-------------+<-------------+
 |              |              |              |              |
 | c_0          | c_1          | c_2          | c_n-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}]\).

In the Galois configuration, the shift register taps are \(T = [c_0, c_1, \dots, c_{n-2}, c_{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]: c = galois.primitive_poly(2, 4); c
Out[1]: Poly(x^4 + x + 1, GF(2))

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

In [3]: print(lfsr)
Galois LFSR:
  field: GF(2)
  feedback_poly: x^4 + x^3 + 1
  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]: c = galois.primitive_poly(7, 4); c
Out[7]: Poly(x^4 + x^2 + 3x + 5, GF(7))

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

In [9]: print(lfsr)
Galois LFSR:
  field: GF(7)
  feedback_poly: 5x^4 + 3x^3 + x^2 + 1
  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]: c = galois.primitive_poly(2**3, 4); c
Out[13]: Poly(x^4 + x + 3, GF(2^3))

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

In [15]: print(lfsr)
Galois LFSR:
  field: GF(2^3)
  feedback_poly: 3x^4 + x^3 + 1
  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]: c = galois.primitive_poly(3**3, 4); c
Out[19]: Poly(x^4 + x + 10, GF(3^3))

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

In [21]: print(lfsr)
Galois LFSR:
  field: GF(3^3)
  feedback_poly: 10x^4 + x^3 + 1
  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

__init__(feedback_poly[, state])

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

Taps(taps[, state])

Constructs a Galois LFSR from its taps \(T = [c_0, c_1, \dots, c_{n-2}, c_{n-1}]\).

Special Methods

__repr__()

A terse representation of the Galois LFSR.

__str__()

A formatted string of relevant properties of the Galois LFSR.

Methods

reset([state])

Resets the Galois LFSR state to the specified state.

step([steps])

Produces the next steps output symbols.

to_fibonacci_lfsr()

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

Attributes

characteristic_poly

The characteristic polynomial \(c(x) = x^{n} - c_{n-1}x^{n-1} - c_{n-2}x^{n-2} - \dots - c_{1}x - c_{0}\) that defines the linear recurrent sequence.

feedback_poly

The feedback polynomial \(f(x) = -c_{0}x^{n} - c_{1}x^{n-1} - \dots - c_{n-2}x^{2} - c_{n-1}x + 1\) that defines the feedback arithmetic.

field

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

initial_state

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

order

The order of the linear recurrence/linear recurrent sequence.

state

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

taps

The shift register taps \(T = [c_0, c_1, \dots, c_{n-2}, c_{n-1}]\).

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

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

Parameters
feedback_poly: Poly

The feedback polynomial \(f(x) = -c_{0}x^{n} - c_{1}x^{n-1} - \dots - c_{n-2}x^{2} - c_{n-1}x + 1\).

state: ArrayLike | None = None

The initial state vector \(S = [S_0, S_1, \dots, S_{n-2}, S_{n-1}]\). The default is None which corresponds to all ones.

Notes

A Galois LFSR may be constructed from its characteristic polynomial \(c(x)\) by passing in its reciprocal as the feedback polynomial. This is because \(f(x) = x^n c(x^{-1})\).

classmethod Taps(taps: FieldArray, state: ArrayLike | None = None) GLFSR

Constructs a Galois LFSR from its taps \(T = [c_0, c_1, \dots, c_{n-2}, c_{n-1}]\).

Parameters
taps: FieldArray

The shift register taps \(T = [c_0, c_1, \dots, c_{n-2}, c_{n-1}]\).

state: ArrayLike | None = None

The initial state vector \(S = [S_0, S_1, \dots, S_{n-2}, S_{n-1}]\). The default is None which corresponds to all ones.

Returns

A Galois LFSR with taps \(T = [c_0, c_1, \dots, c_{n-2}, c_{n-1}]\).

Examples

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

In [2]: taps = -c.coeffs[1:][::-1]; taps
Out[2]: GF([2, 4, 6, 0], order=7)

In [3]: lfsr = galois.GLFSR.Taps(taps)

In [4]: print(lfsr)
Galois LFSR:
  field: GF(7)
  feedback_poly: 5x^4 + 3x^3 + x^2 + 1
  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]
__repr__() str

A terse representation of the Galois LFSR.

Examples

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

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

In [3]: lfsr
Out[3]: <Galois LFSR: f(x) = 5x^4 + 3x^3 + x^2 + 1 over GF(7)>
__str__() str

A formatted string of relevant properties of the Galois LFSR.

Examples

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

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

In [3]: print(lfsr)
Galois LFSR:
  field: GF(7)
  feedback_poly: 5x^4 + 3x^3 + x^2 + 1
  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]
reset(state: ArrayLike | None = None)

Resets the Galois LFSR state to the specified state.

Parameters
state: ArrayLike | None = None

The state vector \(S = [S_0, S_1, \dots, S_{n-2}, S_{n-1}]\). The default is None which corresponds to the initial state.

Examples

Step the Galois LFSR 10 steps to modify its state.

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

In [2]: lfsr = galois.GLFSR(c.reverse()); lfsr
Out[2]: <Galois LFSR: f(x) = 5x^4 + 3x^3 + x^2 + 1 over GF(7)>

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

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

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

Reset the Galois LFSR state.

In [6]: lfsr.reset()

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

Create an Galois LFSR and view its initial state.

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

In [9]: lfsr = galois.GLFSR(c.reverse()); lfsr
Out[9]: <Galois LFSR: f(x) = 5x^4 + 3x^3 + x^2 + 1 over GF(7)>

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

Reset the Galois LFSR state to a new state.

In [11]: lfsr.reset([1, 2, 3, 4])

In [12]: lfsr.state
Out[12]: GF([1, 2, 3, 4], order=7)
step(steps: int = 1) FieldArray

Produces the next steps output symbols.

Negative values may be passed which reverses the direction of the shift registers and produces outputs in reverse order.

Parameters
steps: int = 1

The direction and number of output symbols to produce. The default is 1. If negative, the Galois LFSR will step backward.

Returns

An array of output symbols of type field with size abs(steps).

Examples

Step the Galois LFSR one output at a time.

In [1]: c = galois.primitive_poly(7, 4)

In [2]: lfsr = galois.GLFSR(c.reverse(), state=[1, 2, 3, 4]); lfsr
Out[2]: <Galois LFSR: f(x) = 5x^4 + 3x^3 + x^2 + 1 over GF(7)>

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

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

In [5]: lfsr.state, lfsr.step()
Out[5]: (GF([6, 6, 0, 5], order=7), GF(5, order=7))

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

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

# Ending state
In [8]: lfsr.state
Out[8]: GF([2, 4, 2, 5], order=7)

Step the Galois LFSR 5 steps in one call. This is more efficient than iterating one output at a time. Notice the output and ending state are the same from the Scalar output tab.

In [9]: c = galois.primitive_poly(7, 4)

In [10]: lfsr = galois.GLFSR(c.reverse(), state=[1, 2, 3, 4]); lfsr
Out[10]: <Galois LFSR: f(x) = 5x^4 + 3x^3 + x^2 + 1 over GF(7)>

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

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

# Ending state
In [13]: lfsr.state
Out[13]: GF([2, 4, 2, 5], order=7)

Step the Galois LFSR 10 steps forward.

In [14]: c = galois.primitive_poly(7, 4)

In [15]: lfsr = galois.GLFSR(c.reverse(), state=[1, 2, 3, 4]); lfsr
Out[15]: <Galois LFSR: f(x) = 5x^4 + 3x^3 + x^2 + 1 over GF(7)>

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

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

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

Step the Galois LFSR 10 steps backward. Notice the output sequence is the reverse of the original sequence. Also notice the ending state is the same as the initial state.

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

In [20]: lfsr.state
Out[20]: GF([1, 2, 3, 4], order=7)
to_fibonacci_lfsr() FLFSR

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

Returns

An equivalent Fibonacci LFSR.

Examples

Create a Galois LFSR with a given initial state.

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

In [2]: galois_lfsr = galois.GLFSR(c.reverse(), state=[1, 2, 3, 4])

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

Convert the Galois LFSR to an equivalent Fibonacci LFSR. Notice the initial state is different.

In [4]: fibonacci_lfsr = galois_lfsr.to_fibonacci_lfsr()

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

Step both LFSRs and see that their output sequences are identical.

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

In [7]: fibonacci_lfsr.step(10)
Out[7]: GF([4, 3, 5, 0, 1, 5, 2, 6, 6, 5], order=7)
property characteristic_poly : Poly

The characteristic polynomial \(c(x) = x^{n} - c_{n-1}x^{n-1} - c_{n-2}x^{n-2} - \dots - c_{1}x - c_{0}\) that defines the linear recurrent sequence. The characteristic polynomial is the reciprocal of the feedback polynomial \(c(x) = x^n f(x^{-1})\).

Examples

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

In [2]: lfsr = galois.GLFSR(c.reverse()); lfsr
Out[2]: <Galois LFSR: f(x) = 5x^4 + 3x^3 + x^2 + 1 over GF(7)>

In [3]: lfsr.characteristic_poly
Out[3]: Poly(x^4 + x^2 + 3x + 5, GF(7))

In [4]: lfsr.characteristic_poly == lfsr.feedback_poly.reverse()
Out[4]: True
property feedback_poly : Poly

The feedback polynomial \(f(x) = -c_{0}x^{n} - c_{1}x^{n-1} - \dots - c_{n-2}x^{2} - c_{n-1}x + 1\) that defines the feedback arithmetic. The feedback polynomial is the reciprocal of the characteristic polynomial \(f(x) = x^n c(x^{-1})\).

Examples

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

In [2]: lfsr = galois.GLFSR(c.reverse()); lfsr
Out[2]: <Galois LFSR: f(x) = 5x^4 + 3x^3 + x^2 + 1 over GF(7)>

In [3]: lfsr.feedback_poly
Out[3]: Poly(5x^4 + 3x^3 + x^2 + 1, GF(7))

In [4]: lfsr.feedback_poly == lfsr.characteristic_poly.reverse()
Out[4]: True
property field : type[FieldArray]

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

Examples

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

In [2]: lfsr = galois.GLFSR(c.reverse()); lfsr
Out[2]: <Galois LFSR: f(x) = 5x^4 + 3x^3 + x^2 + 1 over GF(7)>

In [3]: lfsr.field
Out[3]: galois.GF(7)
property initial_state : FieldArray

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

Examples

In [1]: c = galois.primitive_poly(7, 4)

In [2]: lfsr = galois.GLFSR(c.reverse(), state=[1, 2, 3, 4]); lfsr
Out[2]: <Galois LFSR: f(x) = 5x^4 + 3x^3 + x^2 + 1 over GF(7)>

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

The initial state is unaffected as the Galois LFSR is stepped.

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

In [5]: lfsr.initial_state
Out[5]: GF([1, 2, 3, 4], order=7)
property order : int

The order of the linear recurrence/linear recurrent sequence. The order of a sequence is defined by the degree of the minimal polynomial that produces it.

property state : FieldArray

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

Examples

In [1]: c = galois.primitive_poly(7, 4)

In [2]: lfsr = galois.GLFSR(c.reverse(), state=[1, 2, 3, 4]); lfsr
Out[2]: <Galois LFSR: f(x) = 5x^4 + 3x^3 + x^2 + 1 over GF(7)>

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

The current state is modified as the Galois LFSR is stepped.

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

In [5]: lfsr.state
Out[5]: GF([3, 4, 3, 1], order=7)
property taps : FieldArray

The shift register taps \(T = [c_0, c_1, \dots, c_{n-2}, c_{n-1}]\). The taps of the shift register define the linear recurrence relation.

Examples

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

In [2]: taps = -c.coeffs[1:][::-1]; taps
Out[2]: GF([2, 4, 6, 0], order=7)

In [3]: lfsr = galois.GLFSR.Taps(taps); lfsr
Out[3]: <Galois LFSR: f(x) = 5x^4 + 3x^3 + x^2 + 1 over GF(7)>

In [4]: lfsr.taps
Out[4]: GF([2, 4, 6, 0], order=7)

Last update: May 12, 2022