Обработка и передача дискретных сообщений, лекции и материалы, страница 157

,

что в точности соответствует значению , полученному из рекуррентного соотношения.

Аналогично можно показать формирование и всех остальных решений. В результате первых k сдвигов на выход схемы поступит содержимое разрядов регистра в исходном состоянии. Значение коэффициента  появится на выходе схемы в результате (k +1)-го сдвига, значение  - в результате (k +2)-го сдвига и т.п. Поскольку для каждого значения исходных символов решение однозначно, то по последним k решениям сформируется и запишется в регистр , затем  и т.д., т.е. схема будет генерировать решение рекуррентного уравнения непрерывно с периодом, равным n-1. Максимальное значение решений, т.е. максимальный период последовательности, можно определить из следующих соображений. Каждому решению соответствует свое вполне определенное значение разрядов регистра сдвига, следовательно, возможное число решений определяется числом различных состояний регистра. Так как каждая ячейка может характеризоваться двумя состояниями (запись нуля или единицы), а число ячеек в регистре равно k, то максимальное значение n равно 2^k, а максимальный период последовательности равен 2^k -1 и минимальный период равен k. В тех случаях, когда схема для решения рекуррентных соотношений генерирует последовательность с максимальным периодом, ее называют генератором последовательности максимальной длины. В силу того, что многочлен h(x) степени k, по которому стоится схема генератора последовательности максимальной длины, должен быть сомножителем двучлена  при  и не может быть сомножителем никакого двучлена с меньшим значением п (т.к. период равен 2^k -1), то h(x) должен быть неприводимым сомножителем  и не должен быть сомножителем двучленов меньших степеней, т.е. должен принадлежать показателю п. Поскольку последовательности максимальной длины соответствует 2^k -1 различных состояний регистра сдвига (все возможные векторы длины k, кроме чисто нулевого), то для генерирования последовательности максимальной длины в качестве исходного состояния может быть взято любое, кроме чисто нулевого. Обычно для этой цели в младший разряд регистра предварительно записывают “1”. Некоторые из неприводимых многочленов, по виду которых строятся обратные связи в регистре, приводятся в таблице 6.3 для п=2+15.