sdr.FLFSR

class sdr.FLFSR

Implements a Fibonacci linear-feedback shift register (LFSR).

Notes¶

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

f (x) = - c_{0} \cdot x^{n} - c_{1} \cdot x^{n - 1} - \dots - c_{n - 2} \cdot x^{2} - c_{n - 1} \cdot x + 1 = x^{n} \cdot 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} \cdot x^{n - 1} - c_{n - 2} \cdot x^{n - 2} - \dots - c_{1} \cdot x - c_{0}

y_{t} = c_{n - 1} \cdot y_{t - 1} + c_{n - 2} \cdot y_{t - 2} + \dots + c_{1} \cdot y_{t - n + 2} + c_{0} \cdot 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]
         |              |              |             |              |
         v  +--------+  |  +--------+  |             |  +--------+  |
 x[t] -->@->|  S[0]  |--+->|  S[1]  |--+---  ...  ---+->| S[n-1] |--+--> y[t]
            +--------+     +--------+                   +--------+
             y[t+n-1]       y[t+n-2]                      y[t+1]

 S[k] = State vector
 T[k] = Taps vector
 x[t] = Input sequence
 y[t] = Output sequence
 @ = Finite field adder

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¶

Gardner, D. 2019. “Applications of the Galois Model LFSR in Cryptography”.

See also

berlekamp_massey

Examples¶

GF(2) GF(p) GF(2^m) GF(p^m)

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 = sdr.FLFSR(c)

In [3]: print(lfsr)
Fibonacci LFSR:
  field: GF(2)
  characteristic_poly: x^4 + x + 1
  feedback_poly: x^4 + x^3 + 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 = sdr.FLFSR(c)

In [9]: print(lfsr)
Fibonacci LFSR:
  field: GF(7)
  characteristic_poly: x^4 + x^2 + 3x + 5
  feedback_poly: 5x^4 + 3x^3 + x^2 + 1
  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 (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 = sdr.FLFSR(c)

In [15]: print(lfsr)
Fibonacci LFSR:
  field: GF(2^3)
  characteristic_poly: x^4 + x + 3
  feedback_poly: 3x^4 + x^3 + 1
  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 (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 = sdr.FLFSR(c)

In [21]: print(lfsr)
Fibonacci LFSR:
  field: GF(3^3)
  characteristic_poly: x^4 + x + 10
  feedback_poly: 10x^4 + x^3 + 1
  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(characteristic_poly: PolyLike | None = None, ...): Creates a new Fibonacci LFSR.

classmethod Taps(taps: FieldArray, ...) → Self: Creates a Fibonacci LFSR from its taps.

Special methods¶

__call__(x: NDArray[int_]) → FieldArray: Processes the input symbols $x [n]$ through 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[FieldArray]: The FieldArray subclass for the finite field that defines the linear arithmetic.

property taps : FieldArray: The shift register taps $T = [c_{n - 1}, c_{n - 2}, \dots, c_{1}, c_{0}]$ .

property order : int: The order of the linear recurrence/linear recurrent sequence.

Polynomials¶

property characteristic_poly : Poly: The characteristic polynomial $c (x)$ that defines the linear recurrent sequence.

property feedback_poly : Poly: The feedback polynomial $f (x)$ that defines the feedback arithmetic.

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}]$ .