galois.FLFSR.to_galois_lfsr

galois.FLFSR.to_galois_lfsr() → GLFSR

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

Returns:¶: An equivalent Galois LFSR.

Notes¶

Let \(Y(x)\) be the polynomial formed from the next \(n\) outputs of the Fibonacci LFSR, where \(n\) is the order.

\[Y(x) = y[0] + y[1] x + ... + y[n-1] x^{n-1}\]

Here we take \(y[0], ..., y[n-1]\) to be the next \(n\) outputs, which in this implementation are exactly the current state reversed.

Let \(P(x)\) be the characteristic polynomial of the LFSR. In the Galois model, the state polynomial \(G(x)\) represents the element

\[G(x) = g_0 + g_1 x + ... + g_{n-1} x^{n-1} \in GF(q)[x] / (P(x)),\]

and one clock of the LFSR corresponds to multiplication by \(x \mod P(x)\).

\[G_{t+1}(x) = x G_t(x) \mod P(x)\]

\[y[t] = \left\lfloor \frac{x G_t(x)}{P(x)} \right\rfloor\]

If we start from an initial Galois state \(G_0(x)\) and clock \(n\) times, we have

\[x^n G_0(x) = Y(x) P(x) + G_n(x),\]

where \(\deg(G_n) < n\). Taking the polynomial quotient by \(x^n\) and using \(\left\lfloor G_n(x) / x^n \right\rfloor = 0\), we obtain

\[G_0(x) = \left\lfloor \frac{Y(x) P(x)}{x^n} \right\rfloor.\]

This method constructs \(Y(x)\) from the Fibonacci state, computes \(G_0(x)\) from the formula above, and then uses the coefficients of \(G_0(x)\) as the initial state of an equivalent Galois LFSR.

Examples¶

Create a Fibonacci 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]: fibonacci_lfsr = galois.FLFSR(feedback_poly, state=[1, 2, 3, 4])

In [3]: 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: [1 2 3 4]
  initial_state: [1 2 3 4]

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

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

In [5]: 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: [2 6 3 4]
  initial_state: [2 6 3 4]

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

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

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