20. Линейный рекуррентный регистр, алгебраические свойства линейной рекуррентной последовательности, анализ свойства предсказуемости.

12 Июня 2022 г.

14:08

Схема ЛРР:

 

Cвойство периода:

Наименьшее число N такое, что b_j+N = b_j, j = 0, 1, ... называется периодом последовательности.

Полином h(х) с двоичными коэффициентами называется неприводимым, если его нельзя представить как произведение двух или более полиномов ненулевой степени с коэффициентами 0 или 1.

Если характеристический многочлен h(х) степени n является примитивным, то при любом ненулевом начальном заполнении ЛРР период выходной последовательности равен N = 2ⁿ - 1.

Такая последовательность называется последовательностью максимальной длины.

 

 

Алгебраические свойства:

1. Свойство линейности

Поэлементная сумма двух любых отрезков рекуррентных последовательностей, полученных из различных начальных состояний ЛРР с порождающим полиномом h(x), есть некоторый отрезок рекуррентной последовательности данного ЛРР, полученный из начального состояния равного сумме первых двух начальных состояний.

2. Свойство циклического сдвига.

Циклический сдвиг последовательности ЛРР на i тактов будет соответствовать выходной последовательности этого же ЛРР с начальным состоянием, соответствующим i-му состоянию ЛРР.

3. Свойство быстрого нахождения любого элемента последовательности

Существует способ, позволяющий непереборным путем вычислить элемент последовательности на любом i-м такте. Число операций R, требуемое для этого R ~ k^.log i, где k- некоторый коэффициент.

4. Свойство предсказуемости:

по любым 2n смежным элементам ЛРП можно однозначно вычислить характеристический многочлен ЛРР. Следовательно можно предсказать ЛРП вперед или назад;

 

Анализ свойства предсказуемости:

21. Линейный рекуррентный регистр, статистические свойства линейной рекуррентной последовательности.

12 Июня 2022 г.

14:08

Определение и свойство периода в вопросе 21.

 

Статистические свойства ЛРР:

1. Свойство баланса

Любая выходная последовательность ЛРР содержит на полном периоде 2^n-1 единиц и 2^n-1-1 нуль. Такая последовательность является сбалансированной.

2. Свойство серий

В любой выходной последовательности полного периода половина всех серий имеет длину 1, четверть - длину 2, восьмая часть - длину 3 и т.д.

3. Свойства окна

Если вдоль ЛРП перемещается "окно" шириной n символов, то в течение одного максимального периода, каждая ненулевая комбинация длины n будет "видна в окне" ровно один раз

4. Автокорреляционная функция выходной последовательности ЛРР (???)

Можно определить следующим образом:

Где A(k) B(k) означают число совпадений и несовпадений, соответственно между bi и bi+k на периоде T, причем сумма i+k рассчитывается по mod T.

Тогда для АКФ выходной последовательности ЛРР выполняется следующее соотношение

 

 

22. Принципы построения формирователя шифрующей гаммы на основе одного ЛРР (понятие эквивалентной линейной сложности (ЛЭС), применение нелинейных узлов для повышения ЛЭС, верхние и нижние границы ЛЭС).

12 Июня 2022 г.

14:10

Обобщенная структурная схема:

Определение:

 

Из типовых нелинейных узлов бывают

 

 

ЛЭС:

Пример увеличения сложности последовательности с помощью нелинейных устройств:

 

Верхние и нижние границы ЛЭС:

Оценка снизу