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 ingalois.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))