Построение генераторов с линейными обратными связями.

Одним из главных преимуществ метода генерирования ПС–последовательностей максимальной длины является простота его реализации. Важнейшим классом ПСП являются последовательности, формируемые генераторами на основе регистров сдвига с линейными обратными связями –LFSR (Linear Feedback Shift Register) .

Используемый при анализе генераторов с линейными обратными связями математический аппарат – теория линейных последовательностных машин и теория конечных полей. Основными достоинствами этих генераторов являются

- простота аппаратурной реализации;

- максимальное быстродействие;

- хорошие статистические свойства формируемых последовательностей;

- возможность на их основе построение генераторов, обладающих свойствами, ценными при решении специфических задач защиты информации (формирование последовательностей произвольной длины, формирование последовательностей с предпериодом , формирование ПСП с произвольным законом распределения ,построение генераторов, обладающих свойством самоконтроля и т.п.)

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

Аппаратурный генератор ПСП, функционирующий в соответствии с выражением (1.1), содержит m—разрядный регистр сдвига (РС) и набор сумматоров по модулю два, включенные во внешние цепи обратной связи (ОС) (рис.1.1). В процессе функционирования генератора РС выполняет хранение и сдвиг вправо предшествующих символов последовательности, а сумматоры в цепи обратной связи производят вычисление значений очередных символов, которые последовательно записываются в самый левый разряд регистра .

рис.1.1.

Если последовательность состояний РС представить как последовательность m—мерных векторов А = (a₁,a₂,…a_m), где α_n€{0,1}, n=1,m то преобразование, осуществляемое схемой в некотором к – м такте работы, можно записать в матричной форме:

(1.3)

или в более компактном виде

(1.3а)

где

(1.3б)

Последовательное применение (1.1) позволяет найти состояние РС генератора в произвольный последующий такт работы:

(1.3в)

Аппаратурный генератор ПСП, в котором ОС включены в межразрядные связи элементов памяти регистра сдвига, представлен на рис.1.2.

Рис.1.2

Для построения таких генераторов выражение 1.2, матрица V записывается как (1.3), а коэффициенты α определяются из обратного полинома .

(1.4)