# galois.berlekamp_massey¶

galois.berlekamp_massey(sequence: FieldArray, output: Literal['minimal'] = 'minimal') Poly
galois.berlekamp_massey(sequence: FieldArray, output: Literal['fibonacci'])
galois.berlekamp_massey(sequence: FieldArray, output: Literal['galois'])

Finds the minimal polynomial $$c(x)$$ that produces the linear recurrent sequence $$y$$.

This function implements the Berlekamp-Massey algorithm.

Parameters
sequence

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

output

The output object type.

• "minimal" (default): Returns the minimal polynomial that generates the linear recurrent sequence. The minimal polynomial is the characteristic polynomial $$c(x)$$ of minimal degree.

• "fibonacci": Returns a Fibonacci LFSR that produces $$y$$.

• "galois": Returns a Galois LFSR that produces $$y$$.

Returns

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

Notes

The minimal polynomial is the characteristic polynomial $$c(x)$$ of minimal degree that produces the linear recurrent sequence $$y$$.

$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}$

For a linear 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))


Use the Berlekamp-Massey algorithm to return equivalent Fibonacci and Galois LFSRs that reproduce the sequence.

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

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

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

In [7]: np.array_equal(y, z)
Out[7]: True

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

In [9]: print(lfsr)
Galois LFSR:
field: GF(7)
feedback_poly: 5x^4 + 3x^3 + x^2 + 1
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 [10]: z = lfsr.step(y.size); z
Out[10]: GF([5, 5, 1, 3, 1, 4, 6, 6, 5, 5], order=7)

In [11]: np.array_equal(y, z)
Out[11]: True


Last update: May 18, 2022