1
$\begingroup$

This is in context with the inbuilt berlekamp_massey function in SAGEMATH.

While computing the minimal polynomial of the sequences using the Berlekamp Massey function, I have felt that the Berlekamp Massey function in Sagemath is so designed that it requires the periodic sequence to be repeated twice for correct results. Considering the problem of computing the linear complexity of the periodic string $$s = 110010100001110$$

The Berlekamp Massey function with concatenated input $$input = s+s$$ yields the correct result.

Code: berlekamp_massey([GF(2)(1), 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0])

Why does doubling the sequence is required for computing the correct minimal polynomial in SAGEMATH. The original algorithm doesn't say anything like this though. Is this something related to why this function accepts input with even length, is this the way the module in sagemath is defined?

Note: Sometimes for a sequence s = $(s_0, s_1,......, s_{N-1})$, the minimal polynomial for the cases considering the sequence $s$ and the sequence $s+s$ are different and in some cases it is same. So, in the case when it is different should we take the minimal polynomial for the doubly repeated sequence because it agrees with Hankel matrix considerations?

Note: I have done many more examples over the past few days and then I am presenting this argument. Thanks for the help.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
3
$\begingroup$

BMA is a recursive algorithm. Its output is valid for the input you present it with.

Its output is a characteristic polynomial that can generate $$(s_1,\ldots,s_N)\quad(1)$$ but as I explained in an answer to your related question here with the Hankel formulation, in general the recurrence may change as you consider longer segments

$$(s_1,\ldots,s_{N+i})$$

of the sequence and may not settle down to a final characteristic polynomial until you consider $$(s_1,\ldots,s_{2N}).$$

Your choice of repeating the initial segment is only one possible such extension. And by definition the output of BMA after this extension is also valid for the first $N$ bits of the sequence in (1).

Improve this answer
$\endgroup$
2
  • $\begingroup$ thanks, I think, now I am starting to bride some gaps while studying the Berlekamp Massey algorithm, just one thing which now also bothers me is "should we have to take the extension of the sequence $s_N$ until the recurrence settles down or the output of algorithm for first N bits can be considered as a correct answer in every case"? This question about settling the minimal polynomial with increasing extension is what bothers me over days. I would be glad if you could help me to sort this out. $\endgroup$
    – Mathpdegeek497
    Nov 7, 2021 at 8:56
  • $\begingroup$ Actually it should not bother you at all. It is the way it should be. Given the first $N$ bits of the sequence there are $2^N$ different ways of extending the sequence to $2N$ bits. Only one of those is your concatenation. Of course for BMA to be valid each of these extensions can in principle have its own characteristic polynomial defined over a sequence of length $2N.$ $\endgroup$
    – kodlu
    Nov 7, 2021 at 9:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.