Б5. Коды сцепления

Назовем регистром сдвига систему, позволяющую осуществлять последовательное изменение мест -выборки. Например, если в момент времени имеем выборку в которой места элементов можно характеризовать полиномом то в момент имеем выборку характеризуемую полиномом в момент выборку и полином Можно также усложнить систему, накладывая различные соотношения на компоненты выборки в разные моменты времени, например,

Пусть в момент времени регистр находится в состоянии Для обозначения последующих состояний будем использовать верхние индексы. Так, в момент времени новое состояние регистра выражается через предыдущее состояние с помощью системы соотношений:

Это можно записать в матричной форме:

где вектор-столбец с компонентами

В моменты времени получаем последовательно

Мы попытаемся определить такую матрицу чтобы для нее существовало целое число со свойством

и чтобы наименьшее из таких чисел было равно

Необходимое и достаточное условие для этого дает теорема Гамильтона — Кэли, которая утверждает, что каждая матрица является корнем своего характеристического уравнения:

Пусть Если можно найти такое что делит т. е. то по теореме Гамильтона — Кэли имеем (так как

т. е.

или

что реализует первое из условий. Заметим, что для реализации второго условия достаточно, чтобы был примитивен.

Эти два условия будут, следовательно, удовлетворены, если выбрать регистр сдвига с позициями и — в качестве соотношения между различными позициями — условие, которому должен удовлетворять корень а примитивного полинома степени е.

Пример. Пусть Попытаемся получить двоичную цепь длины 7. Пусть Это — примитивный

многочлен. На позиции в регистре налагаем условия

Каждое состояние регистра можно получить тогда из предыдущего с помощью матрицы (см. Б5.2))

например,

Напишем характеристическое уравнение матрицы

Можно проверить непосредственно, что матрица удовлетворяет уравнению

Придадим компонентам вектора начального состояния произвольные значения, не все равные нулю, например,

Имеем

Вместо того чтобы продолжать дальше, заметим, что при применении матрицы к вектору состояния компоненты и сдвигаются в положения соответственно

и представляется как сумма по модулю 2. Образование цепи теперь видно непосредственно:

Заметим, что если в этой последовательности брать три идущих один за другим двоичных знака (в циклическом порядке), то получим все числа от 1 до 7 в двоичной записи

Вообще двоичных знаков в цепи максимальной длины достаточно, чтобы осуществить пересчет требующий двоичных знаков. Это — принцип кода Бодо.