Вычисление длины периода линейной рекуррентной последовательности — КиберПедия 

Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...

Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...

Вычисление длины периода линейной рекуррентной последовательности

2020-07-07 164
Вычисление длины периода линейной рекуррентной последовательности 0.00 из 5.00 0 оценок
Заказать работу

Теорема 1. Пусть d Î S (f).  Тогда

t(d) = ord m d(l).

Доказательство. Пусть t = t(d), t = ord m d(l). Тогда для любого x Î N 0 имеемd x = d x + t. Следовательно, (T t - 1)·d = 0. Поэтому, t £ t. С другой стороны,

m d(l)| (lt - 1).

Таким образом, (T t - 1)·d = 0, т.е. для любого x Î N 0 имеемd x = d x + t. Поэтому t£ t. Из полученных неравенств получаем t =t.

Теорема 2. Если характеристический многочлен f уравнения ЛРП не приводим, то

f = m d(l)

для любого ненулевого решения d этого уравнения.

Доказательство. По свойству минимального многочлена

m d(l)| f.

Так как deg m d(l) ³1, f неприводим и оба многочлена f и m d(l) имеют старшие коэффициенты равные 1, то f = m d(l).

Теорема 3. Если характеристический многочлен f уравнения ЛРП не приводим и d - решение этого уравнения, то

t(d) | (pn - 1).

Доказательство. Из теорем 2 и 3 следует, что наименьший период решения d равен порядку характеристического уравнения ЛРП. Порядок характеристического уравнения ЛРП делит число pn – 1. Поэтому  t(d) | (pn - 1).

Следствие. Если характеристический многочлен f уравнения ЛРП примитивен и d - решение этого уравнения, то

t(d) = pn - 1.

Доказательство. По определению примитивного многочлена, многочлен f –неприводим и имеет порядок равный pn – 1. Тогда по теореме 2  

t(d) = ord m d(l) = ord f = pn - 1.

Теорема 4. Если d – главное решение ЛРУ, то

t(d) = ord f.

Доказательство. Если d – главное решение ЛРУ, то по определению набор решений (d, T ·d,…, Tn - 1· d) является базисом пространства S (f). Поэтому эти решения линейно независимы над F. Поэтому минимальный многочлен d имеет степень n и поэтому совпадает с характеристическим многочленом f. Тогда по теореме 1 t(d) = ord f.

Определение 1. Максимальной линейной рекуррентной последовательностью порядка n  называют ЛРП, если она является главным решением линейного рекуррентного уравнения с характеристическим многочленом степени n.

Следствие. Период максимальной линейной рекуррентной последовательности равен pn - 1.

Пусть t = t(d), t = ord m d(l). Тогда для любого x Î N 0 имеемd x = d x + t. Следовательно

и 3 следует, что наименьший период решения d равен порядку характеристического уравнения ЛРП. Порядок характеристического уравнения ЛРП делит число pn – 1. Поэтому t(d) | (pn - 1).

Регистр сдвига

Определение 1. Регистром сдвига называют электронную схему, позволяющую вырабатывать последовательность, определяемую линейным рекуррентным уравнением.

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

Сумматор имеет два входа и один выход. Задержка имеет один вход и один выход. Они изображаются следующим образом:

 

 

Сумматор работает следующим образом: если на оба его входа подаются одинаковые сигналы (0 и 0 или 1 и 1), то на выход подается 0; если на оба его входа подаются разные сигналы (0 и 1 или 1 и 0), то на выход подается 1. Таким образом сумматор реализует сложение по mod 2.

 Задержка работает следующим образом: если на вход задержки подается в данный момент времени какой-нибудь сигнал (0 или 1), то в следующий момент времени на ее выход подается тот же сигнал.

Пример 1. Рассмотрим схему, отвечающую уравнению

d x +4 = d x + d x +1 + d x +3.

 

Выбирая первоначальное заполнение следующим образом:

d0 = 1, d1 = 0, d2 = 1, d3 = 1,

получим периодическую последовательность: 10110110110… с наименьшим периодом, равным 3.

Пример 2. Рассмотрим схему, отвечающую уравнению

d x +4 = d x + d x +3.

 

Выбирая первоначальное заполнение следующим образом:

d0 = 1, d1 = 0, d2 = 1, d3 = 1,

получим периодическую последовательность: 10110010001111010110… с наименьшим периодом, равным 15.

Опишем электронную схему, физическая реализация которой позволяет вырабатывать псевдослучайную последовательность в любом конечном поле Z p, задаваемую линейным рекуррентным уравнением общего вида:

d x+n = a 1d x+n- 1 + a 2d x+n- 2 + …+  an d x                                              (1)

Схема уже состоит из элементов трех видов: один из них называется сумматором, другой задержкой или ячейкой памяти, а третий умножитель.

Сумматор и задержка имеют тот же самый вид, что и выше.

Сумматор реализует сложение в поле Z p, т.е. сложение по mod p.

 Задержка работает следующим образом: если на вход задержки подается в данный момент времени какой-нибудь сигнал (0, 1,…, p -1), то в следующий момент времени на ее выход подается тот же сигнал.

Умножитель имеет один вход и один выход и имеет следующий вид: он реализует умножение элемента из поля Z p на элемент ai того же поля, т.е. умножение по mod p.

Пример 3. Рассмотрим схему, отвечающую уравнению

d x +4 = d x +  d x +1 +2d x +3 в поле Z3

 

 


Выбирая первоначальное заполнение следующим образом:

d0 = 1, d1 = 0, d2 = 1, d3 = 1,

получим периодическую последовательность: 10110110110… с наименьшим периодом, равным 3.

 


Поделиться с друзьями:

Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...

История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...

Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...

Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...



© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!

0.01 с.