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

Returns:¶

An equivalent Fibonacci LFSR.

Notes¶

To construct an equivalent Fibonacci LFSR, we use the fact that a Fibonacci LFSR with feedback polynomial \(f(x)\) and initial state

will produce the sequence \(y[0], y[1], \dots, y[n-1], \dots\).

This method therefore:

1. Takes the next \(n\) outputs \(y[0], \dots, y[n-1]\) of the Galois LFSR.

2. Forms the Fibonacci initial state \(S = [y[n-1], \dots, y[0]]\).

3. Constructs a Fibonacci LFSR with the same feedback polynomial \(f(x)\) and state \(S\).

The Galois LFSR is stepped forward \(n\) times to obtain these outputs and then stepped backward \(n\) times, so its state is unchanged.

Examples¶

Create a Galois LFSR with a given initial state.

In [1]: feedback_poly = galois.primitive_poly(7, 4).reverse(); feedback_poly
Out[1]: Poly(5x^4 + 3x^3 + x^2 + 1, GF(7))

In [2]: galois_lfsr = galois.GLFSR(feedback_poly, state=[1, 2, 3, 4])

In [3]: print(galois_lfsr)
Galois LFSR:
  field: GF(7)
  feedback_poly: 1 + x^2 + 3x^3 + 5x^4
  characteristic_poly: x^4 + x^2 + 3x + 5
  taps: [2 4 6 0]
  order: 4
  state: [1 2 3 4]
  initial_state: [1 2 3 4]

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

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

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

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

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

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