Score:1

Berlekamp massey possibly wrong SAGEMATH

cn flag

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.

Score:2
sa flag

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

Mathpdegeek497 avatar
cn flag
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.
kodlu avatar
sa flag
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.$
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.