class galois.FLFSR

A Fibonacci linear-feedback shift register (LFSR).

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         | T         | T[n-2]       | T[n-1]
|  +--------+  |  +--------+  |              |  +--------+  |
+->|  S  |--+->|  S  |--+---  ...   ---+->| 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}]$$.

Examples

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

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

In : lfsr = galois.FLFSR(c.reverse())

In : 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 : lfsr.state
Out: GF([1, 1, 1, 1], order=2)

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

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


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

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

In : lfsr = galois.FLFSR(c.reverse())

In : 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 : lfsr.state
Out: GF([1, 1, 1, 1], order=7)

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

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


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

In : c = galois.primitive_poly(2**3, 4); c
Out: Poly(x^4 + x + 3, GF(2^3))

In : lfsr = galois.FLFSR(c.reverse())

In : 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 : lfsr.state
Out: GF([1, 1, 1, 1], order=2^3)

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

In : lfsr.state
Out: 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 : c = galois.primitive_poly(3**3, 4); c
Out: Poly(x^4 + x + 10, GF(3^3))

In : lfsr = galois.FLFSR(c.reverse())

In : 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 : lfsr.state
Out: GF([1, 1, 1, 1], order=3^3)

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

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


## Constructors¶

FLFSR(state: = None)

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

classmethod Taps(...) Self

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

## 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: = None)

Resets the Fibonacci LFSR state to the specified state.

step(steps: int = 1)

Produces the next steps output symbols.

to_galois_lfsr()

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

## Properties¶

property field :

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 = [c_{n-1}, c_{n-2}, \dots, c_1, c_0]$$. The taps of the shift register define the linear recurrence relation.

## Polynomials¶

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.

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.

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