Свойства ЛРР
1. Свойство детерминированности. Символы выходной последовательности ЛРР начиная с n -ого такта полностью определяются своими предыдущими значениями. Это вытекает из рекуррентного соотношения
2. Период рекуррентной последовательности. Это время, по истечении которого повторится исходное состояние ЛРР. Период ЛРР зависит от полинома, на основе которого он строится. Максимальным периодом обладают ЛРР, построенные на примитивных полиномах. Определим максимальный период ЛРР. Если число разрядов ЛРР n, то максимально возможное число состояний разрядов ЛРР равно mn =2 n Учитывая, что одно состояние ЛРР является запрещенным, получаем Т=2 n -1 3. Cвойство группового сложения. Почленная сумма по модулю два любых двух выходных последовательностей одного ЛРР, получаемых при разных начальных заполнениях, является выходной последовательностью этого же ЛРР с другим начальным заполнением. Это начальное заполнение равно сумме исходных начальных заполнений.
Например, для ЛРР изображенного на рис.2 имеем 001 1 0 0 1 0 1 1 110 0 1 1 1 0 0 1 111 1 1 1 0 0 1 0
Рис. 2
4.Свойство сдвига. Циклический сдвиг выходной последовательности ЛРР есть его же выходная последовательность при другом начальном заполнении. 1110010111001 0101110011110 5.Свойство баланса. Любая последовательность максимального периода содержит 2 n -1 единиц и 2 n -2 нулей. 6.Свойство окна. Если по выходной последовательности максимальной длины перемещать " окно" шириной n элементов, то на периоде ЛРР каждая из возможных комбинаций длины n будет зафиксирована только один раз. 7.Свойство серий. Определим серию, как последовательность одинаковых элементов. Любая выходная последовательность максимальной длины имеет: -половину всех серий длины в 1 знак -четверть всех серий длины в 2 знака -одну восьмую всех серий длины в 3 знака и так далее, пока доли дают целое число. длина 1----------4 длина 2----------2 длина 3----------1 длина 4----------1 всего серий -----8 Если известна степень примитивного полинома n, но неизвестны его коэффициенты, то они могут быть однозначно определены по любым 2 n смежным элементам его выходной последовательности. Поиск коэффициентов hi, i =1, …, n -1 характеристического полинома сводится к решению системы n однородных линейных уравнений с n неизвестными. Это потребует порядка n 3 операций типа сложения, умножения. Существуют алгоритмы проверки любой двоичной последовательности на рекуррентность. Эти алгоритмы позволяют найти коэффициенты полинома h (x) при неизвестной длине ЛРР. В настоящее время известны несколько десятков свойств ЛРР. Выше перечисленные являются важнейшими из них для использования в криптографических приложениях. Рассмотренные выше свойства ЛРР легли в основу широкого применения их для построения цифровых узлов техники связи.
|
