Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Раздел V
Линейные рекуррентные последовательности
над конечными полями
Рассматривается конечное поле Fq и k элементов этого поля:
.
Последовательность элементов конечного поля Fq назыв. линейной рекуррентной последовательностью порядка k над Fq, если она удовлетворяет соотношению
,
где операции умножения и сложения определены в поле Fq.
Из определения следует, что последовательность при имеет вид
,
,
т.е. каждый следующий член последовательности является линейной комбинацией предыдущих k членов.
Примеры.
0, 1, 1, 2, 3, 5, 8, 13, 21 и т.д.
0, 1, 1, 2, 3, 5, 8, 2, 10, 1
представляют собой конечную последовательность.
Линейные рекуррентные последовательности используются при построении генераторов псевдослучайных чисел, в радиолокации, при потоковом шифровании.
В технике линейные рекуррентные последовательности реализуются с помощью регистров сдвига с обратной связью.
Линейный регистр сдвига представляет собой набор ячеек для k элементов последовательности:
Регистр работает в дискретные моменты времени.
Содержимое ячеек в данный момент времени назыв. заполнением (состоянием регистра) в этот момент. Содержимое ячеек в начальный момент времени назыв. начальным заполнением.
Пример.
Рассматривается поле F2.
,
.
Пусть начальное заполнение – . Тогда получаем следующую последовательность:
Выход |
|
|
0 |
|
|
0 |
|
|
1 |
|
|
1 |
|
|
1 |
|
|
0 |
|
|
1 |
Периодом линейной рекуррентной последовательности назыв. число r такое, что , . Минимальное r, при котором выполняется это условие, назыв. минимальным периодом.
Утверждение 5.1 Максимально возможный период линейной рекуррентной последовательности порядка k над полем Fq равен .
Сопровождающей матрицей линейной рекуррентной последовательности назыв. матрица
.
Утверждение 5.2 Произвольный вектор состояния регистра представим в виде , где – вектор начального состояния регистра.
Доказательство по индукции.
При последовательность назыв. чисто периодической. При ,…, , последовательность назыв. финально периодической.
В дальнейшем будут рассматриваться только чисто периодические последовательности.
Пример.
Рассматривается поле F2.
.
Рассмотрим начальное заполнение . Тогда получаем следующую последовательность заполнений:
То есть период последовательности равен 4. Если рассмотреть начальное заполнение , то период будет равен 1; при начальном заполнении получаем:
– период равен 2.
Пример показывает, что период зависит от начального состояния регистра. Таким образом, все линейные рекуррентные последовательности, генерируемые одним регистром, распадаются в циклы, имеющие разные периоды.
Множество циклов, входящих в рекуррентную последовательность, назыв. цикловой структурой состояний.
Цикловая структура может определяться сопровождающей матрицей или характеристическим многочленом.
Характеристическим многочленом линейной рекуррентной последовательности назыв. многочлен вида
.
Степень характеристического многочлена совпадает с длиной соответствующего регистра.
Пример.
Утверждение 5.3 Если f – характеристический многочлен линейной рекуррентной последовательности, и , то g – тоже характеристический многочлен.
Характеристический многочлен наименьшей степени назыв. минимальным характеристическим многочленом данного рекуррентного соотношения.
Утверждение 5.4 Пусть – линейная рекуррентная последовательность над Fq с характеристическим многочленом . Тогда , где – порядок многочлена (см. разд. IV).
Примеры. Рассматривается поле .
,
,
,
,
,
то есть . Так как 7 – простое число, то по утв. 5.4 имеем последовательность с периодом 7.
.
Порядок – единица; по утв. 4.27 , где , . Таким образом, . Следовательно, данный многочлен задает три последовательности с периодами 1, 2 и 4.
Импульсной функцией назыв. последовательность с начальным заполнением .
Утверждение 5.5 Период импульсной функции равен порядку ее характеристического многочлена.
Пример. Рассматривается поле F2.
|
, . |
Период последовательности равен 5.
Период последовательности равен 5.
Утверждение 5.6 Пусть – линейная рекуррентная последовательность над Fq с характеристическим многочленом и ненулевым начальным заполнением регистра. Тогда если – неприводим, то .
ТЕОРЕМА 5.1 Если характеристический многочлен линейной рекуррентной последовательности порядка k над Fq примитивен, то период последовательности равен .
Линейная рекуррентная последовательность порядка k над Fq с периодом назыв. последовательностью максимального периода (m-последовательностью).
m-последовательности имеют хорошие статистические свойства (хороший разброс элементов). В бинарной m-последовательности есть единиц и нулей.
Пример. Рассмотрим характеристический многочлен над полем F2:
.
Соответствующее ему рекуррентное соотношение имеет вид .
Рассмотрим состояния регистра с начальным заполнением :
Период последовательности равен 7. Если взять начальное заполнение , то получим длину цикла, равную 1:
Возьмем начальное заполнение :
Период равен 7.
Вообще говоря, цикловая структура последовательности зависит от характеристического многочлена.
В общем случае задача звучит так: определить цикловую структуру рекуррентного соотношения для произвольного характеристического многочлена степени n.
Случай 1. – минимальный, неприводимый. Тогда последовательность имеет циклов, каждый из которых имеет длину .
Случай 2. – минимальный, примитивный. Тогда последовательность имеет один цикл длиной .
Случай 3. – приводимый. Тогда рассмотрим – множество всех последовательностей, заданных многочленом f. содержит в точности qk элементов (из них ненулевых), так как многочлену f соответствует регистр длины k.
5. Свойства меножества
Утверждение 5.7 Множество изоморфно линейному векторному пространству размерности k над Fq.
Каждому элементу из ставится в соответствие начальное заполнение. В качестве бузиса выбираются векторы вида , , …, .
ТЕОРЕМА 5.2 Множество E последовательностей над Fq совпадает с , , тогда и только тогда, когда E является линейным векторным пространством над Fq, замкнутым относительно сдвига.
ТЕОРЕМА 5.3 Свойства множества .
Примечание. Под операцией «+» здесь понимается следующее. Запись означает, что к каждой последовательности из E1 прибавляется каждая последовательность из E2:
Если складываемые последовательности имеют разный период, то период результата равен наименьшему общему кратному периодов.
ТЕОРЕМА 5.4 Пусть – каноническое разложение многочлена f. Тогда .
Рассмотрим : в силу п.2 теор. 5.3 имеем: . Пусть . Тогда содержит ненулевых последовательностей, содержит последовательностей, и т.д. …, содержит последовательностей.
Определим периоды последовательностей для . В силу утв. 4.27 (см. Раздел IV Элементы теории конечных полей) , где p – характеристика поля Fq, .
|
Количество последовательностей |
Период |
|
1 Это для какого множества S |
1 |
|
r |
|
|
pr |
|
|
pjr |
|
|
ptr |
Пример. Пусть , . Сколько последовательностей и с какими периодами содержит множество ?
Пусть , . Тогда .
|
Количество последовательностей |
Период |
Количество последовательностей |
Период |
|
|
1 |
1 |
1 |
1 |
|
3 |
15 |
15 |
||
6 |
||||
|
Количество последовательностей |
Период |
|||
|
1 |
1 |
|||
|
3 |
3 |
|||
|
12 |
6 |
|||
15 |
||||
30 |