class galois.FLFSR

A Fibonacci linear-feedback shift register (LFSR).

Notes

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

f(x)=c0xnc1xn1cn2x2cn1x+1=xnc(x1)

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)=xncn1xn1cn2xn2c1xc0

yt=cn1yt1+cn2yt2++c1ytn+2+c0ytn+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=[T0,T1,,Tn2,Tn1]. The state vector S is also defined left-to-right as S=[S0,S1,,Sn2,Sn1].

In the Fibonacci configuration, the shift register taps are T=[cn1,cn2,,c1,c0]. Additionally, the state vector is equal to the next n outputs in reversed order, namely S=[yt+n1,yt+n2,,yt+2,yt+1].

References

See also

berlekamp_massey

Examples

Create a Fibonacci LFSR from a degree-4 primitive characteristic polynomial over 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 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 GF(23).

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 GF(33).

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

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

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

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

Constructs a Fibonacci LFSR from its taps T=[cn1,cn2,,c1,c0].

String representation

__repr__() str

A terse representation of the Fibonacci LFSR.

__str__() str

A formatted string of relevant properties of the Fibonacci LFSR.

Methods

reset(state: ArrayLike | None = None)

Resets the Fibonacci LFSR state to the specified state.

step(steps: int = 1) FieldArray

Produces the next steps output symbols.

to_galois_lfsr() GLFSR

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

Properties

property field : type[galois._fields._array.FieldArray]

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

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 taps : FieldArray

The shift register taps T=[cn1,cn2,,c1,c0]. The taps of the shift register define the linear recurrence relation.

Polynomials

property characteristic_poly : Poly

The characteristic polynomial c(x)=xncn1xn1cn2xn2c1xc0 that defines the linear recurrent sequence.

property feedback_poly : Poly

The feedback polynomial f(x)=c0xnc1xn1cn2x2cn1x+1 that defines the feedback arithmetic.

State

property initial_state : FieldArray

The initial state vector S=[S0,S1,,Sn2,Sn1].

property state : FieldArray

The current state vector S=[S0,S1,,Sn2,Sn1].