galois.berlekamp_massey

galois.berlekamp_massey(sequence, config='fibonacci', state=False)

Finds the minimum-degree polynomial \(c(x)\) that produces the sequence in \(\mathrm{GF}(p^m)\).

This function implements the Berlekamp-Massey algorithm.

Parameters
  • sequence (galois.FieldArray) – A 1-D sequence of Galois field elements in \(\mathrm{GF}(p^m)\).

  • config (str, optional) – A string indicating the LFSR feedback configuration for the returned connection polynomial, either "fibonacci" (default) or "galois". See the LFSR configurations in galois.LFSR. The LFSR configuration will indicate if the connection polynomial coefficients should be reversed or not.

  • state (bool, optional) – Indicates whether to return the LFSR initial state such that the output is the input sequence. The default is False.

Returns

  • galois.Poly – The minimum-degree polynomial \(c(x) \in \mathrm{GF}(p^m)[x]\) that produces the input sequence.

  • galois.FieldArray – The initial state of the LFSR such that the output will generate the input sequence. Only returned if state=True.

References

Examples

The Berlekamp-Massey algorithm requires \(2n\) output symbols to determine the \(n\)-degree minimum connection polynomial.

In [1]: g = galois.conway_poly(2, 8); g
Out[1]: Poly(x^8 + x^4 + x^3 + x^2 + 1, GF(2))

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

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

In [4]: galois.berlekamp_massey(s)
Out[4]: Poly(x^8 + x^4 + x^3 + x^2 + 1, GF(2))