galois.berlekamp_massey(sequence: FieldArray, output: 'characteristic' = 'characteristic') → Poly
galois.berlekamp_massey(sequence: FieldArray, output: 'connection') → Poly
galois.berlekamp_massey(sequence: FieldArray, output: 'fibonacci') → FLFSR
galois.berlekamp_massey(sequence: FieldArray, output: 'galois') → GLFSR

Finds the characteristic polynomial \(c(x)\) of the input linear recurrent sequence using the Berlekamp-Massey algorithm.

Parameters:
sequence: FieldArray

A linear recurrent sequence \(y\) in \(\mathrm{GF}(p^m)\).

output: 'characteristic' = 'characteristic'
output: 'connection'
output: 'fibonacci'
output: 'galois'

The output object type.

  • "characteristic" (default): Returns the characteristic polynomial \(c(x)\) that generates the linear recurrent sequence. This is equivalent to the minimal polynomial. The characteristic polynomial is the reciprocal of the connection polynomial, \(c(x) = x^{n} C(x^{-1})\).

  • "connection": Returns the connection polynomial \(C(x)\) that generates the linear recurrent sequence. The connection polynomial is equivalent to the feedback polynomial \(f(x)\) of an LFSR.

  • "fibonacci": Returns a Fibonacci LFSR whose next \(n\) outputs produce \(y\).

  • "galois": Returns a Galois LFSR whose next \(n\) outputs produce \(y\).

Returns:

The characteristic (minimal) polynomial \(c(x)\), the connection polynomial \(C(x)\), a Fibonacci LFSR, or a Galois LFSR, depending on the value of output.

Notes

The characteristic polynomial of a linear recurrent sequence is defined as

\[\begin{split} c(x) &= x^{n} + a_1 x^{n-1} + a_2 x^{n-2} + \dots + a_{n} \\ &= x^{n} f(x^{-1}). \end{split}\]

The connection polynomial \(C(x)\) is defined as

\[\begin{split} C(x) &= 1 + a_1 x + a_2 x^2 + \dots + a_{n} x^{n} \\ &= f(x) = x^{n} c(x^{-1}), \end{split}\]

where \(C(0) = f(0) = 1\) and the degree \(n\) equals the length of the shift register. The associated output sequence \(y[t]\) satisfies the linear recurrence

\[ y[t] + a_1 y[t-1] + a_2 y[t-2] + \dots + a_{n} y[t-n] = 0. \]

For a linear recurrent sequence with order \(n\), at least \(2n\) output symbols are required to determine the minimal polynomial.

References

Examples

The sequence below is a degree-4 linear recurrent sequence over \(\mathrm{GF}(7)\).

In [1]: GF = galois.GF(7)

In [2]: y = GF([5, 5, 1, 3, 1, 4, 6, 6, 5, 5])

The characteristic polynomial is \(c(x) = x^4 + x^2 + 3x + 5\) over \(\mathrm{GF}(7)\).

In [3]: galois.berlekamp_massey(y)
Out[3]: Poly(x^4 + x^2 + 3x + 5, GF(7))

The connection (feedback) polynomial is \(C(x) = 5x^4 + 3x^3 + x^2 + 1\) over \(\mathrm{GF}(7)\).

In [4]: galois.berlekamp_massey(y, output="connection")
Out[4]: Poly(5x^4 + 3x^3 + x^2 + 1, GF(7))

Use the Berlekamp-Massey algorithm to return equivalent Fibonacci LFSR that reproduces the sequence.

In [5]: lfsr = galois.berlekamp_massey(y, output="fibonacci")

In [6]: print(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: [3 1 5 5]
  initial_state: [3 1 5 5]

In [7]: z = lfsr.step(y.size); z
Out[7]: GF([5, 5, 1, 3, 1, 4, 6, 6, 5, 5], order=7)

In [8]: assert np.array_equal(y, z)

Use the Berlekamp-Massey algorithm to return equivalent Galois LFSR that reproduces the sequence.

In [9]: lfsr = galois.berlekamp_massey(y, output="galois")

In [10]: print(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 5 5]
  initial_state: [2 6 5 5]

In [11]: z = lfsr.step(y.size); z
Out[11]: GF([5, 5, 1, 3, 1, 4, 6, 6, 5, 5], order=7)

In [12]: assert np.array_equal(y, z)