Для двоичной последовательности 01100101, применяя алгоритм Берлекемпа - Месси, найти линейный регистр сдвига слева направо, на котором она реализуется, с указанием начального заполнения этого регистра сдвига и его характеристического многочлена.

Добавлена: 10.06.2026
Обновлена: 10.06.2026
Предмет: Высшая математика
Автор: Кэмп

#Дискретная математика
#Математическая логика

Условие:

Для двоичной последовательности 01100101, применяя алгоритм Берлекемпа - Месси, найти линейный регистр сдвига слева направо, на котором она реализуется, с указанием начального заполнения этого регистра сдвига и его характеристического многочлена. Представить пошаговое выполнение алгоритма.

Решение:

Для решения задачи с помощью алгоритма Берлекемпа — Месси нам необходимо найти минимальный многочлен $C(x)$ и длину регистра сдвига $L$ , которые порождают заданную последовательность $S = \{s_0, s_1, \dots, s_7\} = \{0, 1, 1, 0, 0, 1, 0, 1\}$ .

Обозначения

$S^{(n)}$ — префикс последовательности длины $n$ .
$C^{(n)}(x)$ — многочлен связи после $n$ шагов.
$L_n$ — длина регистра после $n$ шагов.
$d_n$ — расхождение (discrepancy) на шаге $n$ : $d_n = s_n + \sum_{i=1}^{L_n} c_i s_{n-i} \pmod 2$ .
$B(x)$ — вспомогательный многочлен, $m$ — число шагов с момента последнего изменения $C(x)$ ....