galois.FLFSR

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

A Fibonacci linear-feedback shift register (LFSR).

Notes

A Fibonacci 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 Fibonacci 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}\]
Fibonacci LFSR Configuration
 +--------------+<-------------+<-------------+<-------------+
 |              ^              ^              ^              |
 |              | c_n-1        | c_n-2        | c_1          | c_0
 |              | T[0]         | T[1]         | T[n-2]       | T[n-1]
 |  +--------+  |  +--------+  |              |  +--------+  |
 +->|  S[0]  |--+->|  S[1]  |--+---  ...   ---+->| S[n-1] |--+--> y[t]
    +--------+     +--------+                    +--------+
     y[t+n-1]       y[t+n-2]                       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 Fibonacci configuration, the shift register taps are \(T = [c_{n-1}, c_{n-2}, \dots, c_1, c_0]\). Additionally, the state vector is equal to the next \(n\) outputs in reversed order, namely \(S = [y_{t+n-1}, y_{t+n-2}, \dots, y_{t+2}, y_{t+1}]\).

References

See also

berlekamp_massey

Examples

Create a Fibonacci 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.FLFSR(c.reverse())

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

Step the Fibonacci 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, 1, 0, 0, 0, 1, 0, 0], order=2)

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

Create a Fibonacci 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.FLFSR(c.reverse())

In [9]: print(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: [1, 1, 1, 1]
  initial_state: [1, 1, 1, 1]

Step the Fibonacci 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, 1, 1, 5, 5, 1, 3, 1, 4], order=7)

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

Create a Fibonacci 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.FLFSR(c.reverse())

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

Step the Fibonacci 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, 1, 2, 2, 2, 1, 4, 4], order=2^3)

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

Create a Fibonacci 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.FLFSR(c.reverse())

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

Step the Fibonacci 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,  1, 19, 19, 19,  1, 25, 25], order=3^3)

In [24]: lfsr.state
Out[24]: GF([ 6, 24,  4, 16], order=3^3)

Constructors

__init__(feedback_poly[, state])

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

Taps(taps[, state])

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

Special Methods

__repr__()

A terse representation of the Fibonacci LFSR.

__str__()

A formatted string of relevant properties of the Fibonacci LFSR.

Methods

reset([state])

Resets the Fibonacci LFSR state to the specified state.

step([steps])

Produces the next steps output symbols.

to_galois_lfsr()

Converts the Fibonacci LFSR to a Galois 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_{n-1}, c_{n-2}, \dots, c_1, c_0]\).
__init__(feedback_poly: Poly, state: ArrayLike | None = None)

Constructs a Fibonacci 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.

See also

irreducible_poly, primitive_poly

Notes

A Fibonacci 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) → FLFSR

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

Parameters
taps: FieldArray

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

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 Fibonacci LFSR with taps \(T = [c_{n-1}, c_{n-2}, \dots, c_1, c_0]\).

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:]; taps
Out[2]: GF([0, 6, 4, 2], order=7)

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

In [4]: print(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: [1, 1, 1, 1]
  initial_state: [1, 1, 1, 1]
__repr__() → str

A terse representation of the Fibonacci 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.FLFSR(c.reverse())

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

A formatted string of relevant properties of the Fibonacci 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.FLFSR(c.reverse())

In [3]: print(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: [1, 1, 1, 1]
  initial_state: [1, 1, 1, 1]
reset(state: ArrayLike | None = None)

Resets the Fibonacci 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 Fibonacci 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.FLFSR(c.reverse()); lfsr
Out[2]: <Fibonacci 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, 1, 1, 5, 5, 1, 3, 1, 4], order=7)

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

Reset the Fibonacci LFSR state.

In [6]: lfsr.reset()

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

Create an Fibonacci 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.FLFSR(c.reverse()); lfsr
Out[9]: <Fibonacci 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 Fibonacci 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 Fibonacci LFSR will step backward.

Returns

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

Examples

Step the Fibonacci LFSR one output at a time. Notice the first \(n\) outputs of a Fibonacci LFSR are its state reversed.

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

In [2]: lfsr = galois.FLFSR(c.reverse(), state=[1, 2, 3, 4]); lfsr
Out[2]: <Fibonacci 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([4, 1, 2, 3], order=7), GF(3, order=7))

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

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

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

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

Step the Fibonacci 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.FLFSR(c.reverse(), state=[1, 2, 3, 4]); lfsr
Out[10]: <Fibonacci 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, 2, 1, 4], order=7)

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

Step the Fibonacci LFSR 10 steps forward.

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

In [15]: lfsr = galois.FLFSR(c.reverse(), state=[1, 2, 3, 4]); lfsr
Out[15]: <Fibonacci 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, 2, 1, 4, 6, 4, 5, 0, 2], order=7)

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

Step the Fibonacci 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([2, 0, 5, 4, 6, 4, 1, 2, 3, 4], order=7)

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

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

Returns

An equivalent Galois LFSR.

Examples

Create a Fibonacci 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]: fibonacci_lfsr = galois.FLFSR(c.reverse(), state=[1, 2, 3, 4])

In [3]: 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: [1, 2, 3, 4]
  initial_state: [1, 2, 3, 4]

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

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

In [5]: 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: [2, 6, 3, 4]
  initial_state: [2, 6, 3, 4]

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

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

In [7]: galois_lfsr.step(10)
Out[7]: GF([4, 3, 2, 1, 4, 6, 4, 5, 0, 2], 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.FLFSR(c.reverse()); lfsr
Out[2]: <Fibonacci 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.FLFSR(c.reverse()); lfsr
Out[2]: <Fibonacci 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.FLFSR(c.reverse()); lfsr
Out[2]: <Fibonacci 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.FLFSR(c.reverse(), state=[1, 2, 3, 4]); lfsr
Out[2]: <Fibonacci 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 Fibonacci LFSR is stepped.

In [4]: lfsr.step(10)
Out[4]: GF([4, 3, 2, 1, 4, 6, 4, 5, 0, 2], 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.FLFSR(c.reverse(), state=[1, 2, 3, 4]); lfsr
Out[2]: <Fibonacci 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 Fibonacci LFSR is stepped.

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

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

The shift register taps \(T = [c_{n-1}, c_{n-2}, \dots, c_1, c_0]\). 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:]; taps
Out[2]: GF([0, 6, 4, 2], order=7)

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

In [4]: lfsr.taps
Out[4]: GF([0, 6, 4, 2], order=7)
Last update: May 12, 2022