galois.LFSR

class galois.LFSR(poly, state=1, config='fibonacci')

Implements a linear-feedback shift register (LFSR).

This class implements an LFSR in either the Fibonacci or Galois configuration. An LFSR is defined by its generator polynomial \(g(x) = g_n x^n + \dots + g_1 x + g_0\) and initial state vector \(s = [s_{n-1}, \dots, s_1, s_0]\).

Parameters

• poly (galois.Poly) – The generator polynomial \(g(x) = g_n x^n + \dots + g_1 x + g_0\).

• state (int, tuple, list, numpy.ndarray, galois.FieldArray, optional) – The initial state vector \(s = [s_{n-1}, \dots, s_1, s_0]\). If specified as an integer, then \(s_{n-1}\) is interpreted as the MSB and \(s_0\) as the LSB. The default is 1 which corresponds to \(s = [0, \dots, 0, 1]\).

• config (str, optional) – A string indicating the LFSR feedback configuration, either "fibonacci" (default) or "galois".

Notes

Below are diagrams for a degree-\(3\) LFSR in the Fibonacci and Galois configuration. The generator polynomial is \(g(x) = g_3x^3 + g_2x^2 + g_1x + g_0\) and state vector is \(s = [s_2, s_1, s_0]\).

Fibonacci LFSR Configuration

      ┌────────────⊕◀───────────⊕◀───────────┐
      │            ▲            ▲            |
 g0 ⊗─┤       g1 ⊗─┤       g2 ⊗─┤       g3 ⊗─┤
      │  ┏━━━━━━┓  |  ┏━━━━━━┓  |  ┏━━━━━━┓  |
      └─▶┃  s2  ┃──┴─▶┃  s1  ┃──┴─▶┃  s0  ┃──┴──▶ y[n]
         ┗━━━━━━┛     ┗━━━━━━┛     ┗━━━━━━┛

In the Fibonacci configuration, at time instant \(i\) the next \(n-1\) outputs are the current state reversed, that is \([y_i, y_{i+1}, \dots, y_{i+n-1}] = [s_0, s_1, \dots, s_{n-1}]\). And the \(n\)-th output is a linear combination of the current state and the generator polynomial \(y_{i+n} = (g_n s_0 + g_{n-1} s_1 + \dots + g_1 s_{n-1}) g_0\).

Galois LFSR Configuration

      ┌────────────┬────────────┬────────────┐
 g0 ⊗─┤       g1 ⊗─┤       g2 ⊗─┤       g3 ⊗─┤
      │            |            |            |
      │  ┏━━━━━━┓  ▼  ┏━━━━━━┓  ▼  ┏━━━━━━┓  |
      └─▶┃  s0  ┃──⊕─▶┃  s1  ┃──⊕─▶┃  s2  ┃──┴──▶ y[n]
         ┗━━━━━━┛     ┗━━━━━━┛     ┗━━━━━━┛

In the Galois configuration, the next output is \(y = s_{n-1}\) and the next state is computed by \(s_k = s_{n-1} g_n g_k + s_{k-1}\). In the case of \(s_0\) there is no previous state added.

References

• https://core.ac.uk/download/pdf/288371609.pdf

• https://www.wseas.org/multimedia/journals/control/2018/a945903-022.pdf

• https://jhafranco.com/2014/02/15/n-ary-m-sequence-generator-in-python/

• https://www.cs.uky.edu/~klapper/pdf/galois.pdf

Methods

reset()	Resets the LFSR state to the initial state.
step([steps])	Steps the LFSR and produces steps output symbols.

Attributes

config	The LFSR configuration, either "fibonacci" or "galois".
field	The Galois field that defines the LFSR arithmetic.
initial_state	The initial state vector \(s = [s_{n-1}, \dots, s_1, s_0]\).
poly	The generator polynomial \(g(x) = g_n x^n + \dots + g_1 x + g_0\).
state	The current state vector \(s = [s_{n-1}, \dots, s_1, s_0]\).

reset()

Resets the LFSR state to the initial state.

Examples

In [1]: lfsr = galois.LFSR(galois.primitive_poly(2, 4)); lfsr
Out[1]: <Fibonacci LFSR: poly=Poly(x^4 + x + 1, GF(2))>

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

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

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

In [5]: lfsr.reset()

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

step(steps=1)

Steps the LFSR and produces steps output symbols.

Parameters

steps (int, optional) – The number of output symbols to produce. The default is 1.

Returns

An array of output symbols of type field with size steps.

Return type

galois.FieldArray

Examples

Step the LFSR one output at a time.

In [1]: lfsr = galois.LFSR(galois.primitive_poly(2, 4)); lfsr
Out[1]: <Fibonacci LFSR: poly=Poly(x^4 + x + 1, GF(2))>

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

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

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

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

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

Step the LFSR 10 steps.

In [7]: lfsr.reset()

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

property config

The LFSR configuration, either "fibonacci" or "galois". See the Notes section of LFSR for descriptions of the two configurations.

Examples

In [1]: lfsr = galois.LFSR(galois.primitive_poly(2, 4)); lfsr
Out[1]: <Fibonacci LFSR: poly=Poly(x^4 + x + 1, GF(2))>

In [2]: lfsr.config
Out[2]: 'fibonacci'

In [3]: lfsr = galois.LFSR(galois.primitive_poly(2, 4), config="galois"); lfsr
Out[3]: <Galois LFSR: poly=Poly(x^4 + x + 1, GF(2))>

In [4]: lfsr.config
Out[4]: 'galois'

Type

str

property field

The Galois field that defines the LFSR arithmetic. The generator polynomial \(g(x)\) is over this field and the state vector contains values in this field.

Examples

In [1]: lfsr = galois.LFSR(galois.primitive_poly(2, 4)); lfsr
Out[1]: <Fibonacci LFSR: poly=Poly(x^4 + x + 1, GF(2))>

In [2]: lfsr.field
Out[2]: <class 'numpy.ndarray over GF(2)'>

In [3]: print(lfsr.field.properties)
GF(2):
  characteristic: 2
  degree: 1
  order: 2
  irreducible_poly: x + 1
  is_primitive_poly: True
  primitive_element: 1

Type

galois.FieldClass

property initial_state

The initial state vector \(s = [s_{n-1}, \dots, s_1, s_0]\).

Examples

In [1]: lfsr = galois.LFSR(galois.primitive_poly(2, 4)); lfsr
Out[1]: <Fibonacci LFSR: poly=Poly(x^4 + x + 1, GF(2))>

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

Type

galois.FieldArray

property poly

The generator polynomial \(g(x) = g_n x^n + \dots + g_1 x + g_0\).

Examples

In [1]: lfsr = galois.LFSR(galois.primitive_poly(2, 4)); lfsr
Out[1]: <Fibonacci LFSR: poly=Poly(x^4 + x + 1, GF(2))>

In [2]: lfsr.poly
Out[2]: Poly(x^4 + x + 1, GF(2))

Type

galois.Poly

property state

The current state vector \(s = [s_{n-1}, \dots, s_1, s_0]\).

Examples

In [1]: lfsr = galois.LFSR(galois.primitive_poly(2, 4)); lfsr
Out[1]: <Fibonacci LFSR: poly=Poly(x^4 + x + 1, GF(2))>

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

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

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

Type

galois.FieldArray