Кратчайшая линейная рекурсия конечного префикса над GF(p)

Восстановить минимальную длину линейной рекурсии для заданного конечного набора остатков по одному из малых простых модулей.

Ваш пример

Числа и дроби: 0.5, 0,5 или 1/3. Числа в строке разделяются пробелами, строки — переносом. Выражения не выполняются.

Разбор примера

Длина рекурсии = 2

Проверяемые промежуточные данные
ИндексРасхождениеТекущая длина
011
101
212
302
402
502
602
702
  1. Коэффициенты для предыдущих членов: [1, 1].
  2. Подстановка проверена на всех применимых индексах заданного префикса.
  3. Никакое продолжение неизвестного источника не объявляется доказанным.

Метод и условия расчёта

Алгоритм обновляет связующий полином при ненулевом расхождении с текущей рекурсией.

Отчёт использует s[n]=Σcᵢs[n−i] mod p, а не противоположный знак коэффициентов связующего полинома.

Теория к методу

Алгоритм Берлекэмпа — Мэсси обновляет связующий полином, когда очередной символ расходится с текущей рекурсией. Полученная минимальная длина относится к заданному конечному префиксу. Продолжение неизвестного источника требует отдельной предпосылки о его генераторе.

Укажите простое поле заранее. Значения последовательности должны быть остатками от нуля до p−1, а вычисления выполняются по модулю p. Ненулевой элемент такого поля имеет обратный; именно это позволяет нормировать расхождение. Для составного модуля тот же шаг может быть незаконным, даже если все входные числа выглядят небольшими.

Пример: Двоичный префикс 1,1,0,1,1,0,1,1 удовлетворяет рекурсии s[n]=s[n−1]+s[n−2] по модулю два. Длина один не подходит: коэффициент ноль не объясняет второй символ, а единица не объясняет третий.

Минимальная длина равна двум, коэффициенты равны 1,1. Этот вывод проверяет все введённые символы и исключает меньшую длину, но без модели источника не вынуждает следующий символ быть нулём.

Вопросы по теме

Найденная рекурсия доказывает будущие члены?

Нет. Она описывает данный конечный префикс; без предпосылки о генераторе продолжение не идентифицировано.

Можно вводить составной модуль?

Нет. Обращение ненулевого расхождения требует поля; интерфейс ограничен перечисленными простыми.

Методы алгоритмов: углубление: объяснения, примеры и практика

Основа объяснения

Объяснения и примеры подготовлены для erudeet. По ссылкам можно сверить определения и условия модели.