8.3. Последовательности максимальной длины

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

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

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

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