Берлекамп Мэсси, возможно, ошибся SAGEMATH

Это связано со встроенной функцией berlekamp_massey в SAGEMATH.

Вычисляя минимальный многочлен последовательностей с помощью функции Берлекэмпа Мэсси, я почувствовал, что функция Берлекэмпа Мэсси в Sagemath устроена таким образом, что для получения правильных результатов периодическая последовательность должна повторяться дважды. Рассматривая задачу вычисления линейной сложности периодической струны $$s = 110010100001110$$

Функция Берлекэмпа Мэсси с конкатенированным вводом $$ ввод = с+с$$ дает правильный результат.

Код: 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])

Почему удвоение последовательности требуется для вычисления правильного минимального многочлена в SAGEMATH. Однако исходный алгоритм ничего подобного не говорит. Это как-то связано с тем, почему эта функция принимает ввод с четной длиной, так ли определяется модуль в sagemath?

Примечание. Иногда для последовательности s = $(s_0, s_1,......, s_{N-1})$, минимальный многочлен для случаев, рассматривающих последовательность $s$ и последовательность $s+s$ разные, а в некоторых случаях одинаковые. Итак, в случае, когда она различна, должны ли мы взять минимальный многочлен для дважды повторяющейся последовательности, потому что это согласуется с соображениями о ганкелевой матрице?

Примечание. За последние несколько дней я привел еще много примеров, а затем привожу этот аргумент. Спасибо за помощь.

BMA — это рекурсивный алгоритм. Его вывод действителен для ввода, который вы ему представляете.

Его выход представляет собой характеристический полином, который может генерировать $$(s_1,\ldots,s_N)\quad(1)$$ но, как я объяснил в ответе на ваш связанный вопрос здесь с формулировкой Ганкеля, как правило, повторение может меняться по мере того, как вы рассматриваете более длинные сегменты.

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

последовательности и не может прийти к окончательному характеристическому полиному до тех пор, пока вы рассмотреть возможность $$(s_1,\ldots,s_{2N}).$$

Ваш выбор повторения начального сегмента только один возможный такое расширение. И по определению вывод БМА после этого расширения действителен и для первого $N$ биты последовательности в (1).