Кратчайшая линейная рекурсия конечного префикса над GF(p)
Восстановить минимальную длину линейной рекурсии для заданного конечного набора остатков по одному из малых простых модулей.
Ваш пример
Разбор примера
Длина рекурсии = 2
| Индекс | Расхождение | Текущая длина |
|---|---|---|
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 2 | 1 | 2 |
| 3 | 0 | 2 |
| 4 | 0 | 2 |
| 5 | 0 | 2 |
| 6 | 0 | 2 |
| 7 | 0 | 2 |
- Коэффициенты для предыдущих членов: [1, 1].
- Подстановка проверена на всех применимых индексах заданного префикса.
- Никакое продолжение неизвестного источника не объявляется доказанным.
Метод и условия расчёта
Алгоритм обновляет связующий полином при ненулевом расхождении с текущей рекурсией.
Отчёт использует 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. По ссылкам можно сверить определения и условия модели.