Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
матрица, связанная с этой последовател ностыо и задаваемая равенством
(8.3), то для векторов состоя не последовательности s0, slT ...
справедливо равенство
$п SqA11, п ^ 0, 1, - . . * (Щ
*3
Г
ч.
Доказательство. Так как s7E = (sn, sn+b ..., s,^^), то, кЦ нетрудно
проверить, для всех п > 0 выполняется равенств" 5л+1 - sпАу откуда по
индукции получается (8.4).
I '
Заметим, что множество всех невырожденных k X &-матр# над полем jFff
образует конечную группу относительно онера матричного умножения. (Эта
группа называется общей линейно группой 0L(k, Fq}.)
8.13. Теорема, Пусть зо, sx, ... - однородная линейная petcyjjk рентная
последовательность k-го порядка над полем (Fg, такаМ что выполняется
соотношение (8.2) и а0 ф 0. Тогда минимальны период данной
последовательности делит порядок связанной с матрицы Л, определенной
формулой (8.3) и рассматриваемой каЕ элемент обшрй линейной группы GL{k,
f?).
Доказательство. Так как det А - (-I)*-1 а0 Ф 0, то мщ? три да А
действительно является элементом группы GL (k,
Если т - порядок А как элемента группы GL (k, fв), то из лем^| 8.12
получаем, что sn+m - = s04'* s" для всех п ^ $
Отсюда следует, что т является периодом рассматриваемой р4. куррентнон
последовательности. Утверждение теоремы вытекаС теперь из леммы 8.4.
Отметим, что приведенные выше рассуждения вместе с леммсС 8.6 дают другое
доказательство теоремы 8.11 для однородного случая. Кроме того, из
теоремы 8.13 следует, в частности, чт^ минимальный период
последовательности s0, sl% ... делит порядОу группы GL (k, F^), который,
как известно, равен
фк*-к№ ц __ 1) (^2 1) _ . (qk ^
Пусть теперь s0, s1( ... - неоднородная линейная рекурреитка^,
последовательность k-то порядка над полем удовлетворяющая соотношению
(8.1). Заменяя в (8.1) п на п + 1 и вычитая из пол^ ченного равенства
исходное равенство (8.1), получаем соотношек1|
. *-4
Sn+fc+1 " bhsn+h ~Ь 4" * * * Ь &0sn> П - 0, 1, , , (8,lj
где b0 ^ -я0, bj = as_x - aj для j = 1,2, .... k - I, bh 4
ak-i + 1. Таким образом, последовательность s0, sb ... можй|| свести к
однородной линейной рекуррентной последовательное^
•s А.
§ 2. Импульсная функция, Характеристический многочлен 503
(k f 1 )*го порядка иад полем Fff, и, следовательно, результаты,
полученные для однородных линейных рекуррентных последовательностей, дают
информацию и для неоднородного случая.
Существует и другой подход к рассмотрению неоднородного случая. Пусть $0,
... - неоднородная линейная рекуррентная
последовательность k-го порядка над полем F?> удовлетворяющая соотношению
(8Л). Рассмотрим связанную с ней матрицу С над полем F(], 'являющуюся
квадратной матрицей размера (к + 1) X < (к + 1) следующего вида:
1 о о ... о
о о о ... о
О 1 о ... о
О 0 1 ... о
а
а0
а2
(ООО...!
Еслн к = 1, то полагаем
С ~
1 а 0 аа
Введем модифицированный вектор состояния рекуррентной последовательности,
полагая
(1т -i) ДЛЯ ft ':==: 0, 1, . . , ¦
Тогда, как нетрудно заметить, для всех п > 0 справедливо равенство Srt+j
= s'nC, откуда по индукции получаем, что s" - ' SgC" для всех я >- 0.
Если в (8Л) коэффициент щ отличен от 0, то det С = (- ])*-1 Oq Ф 0,
откуда следует, что матрица С является элементом группы OL {к + 1, F^). В
этом случае, проведя рассуждения/ аналогичные доказательству теоремы
8.13, нетрудно показать, что минимальный период последовательности Ть Sj,
... делит порядок матрицы С, рассматриваемой как элемент
группы OL (к ~F 1, F*).
§ 2. Импульсная функция.
Характеристический многочлен
Из всех однородных линейных рекуррентных последовательностей над полем
F$, удовлетворяющих данному линейному референтному соотношению k-ro
порядка вида (8.2), можно выделить одну последовательность с максимальным
значением минимального периода, называемую импульсной функцией или после-
(овательностыо, порожденной импульсом. Эта последовательность
504
Гл. 8. Линейные рекуррентные последовательности
обозначается d{), dlt ... и однозначно определяется начальные значениями
d(i =¦¦ ... dh_2 0, dk_x ^ 1 (d0 = 1 для к = 1) л и н е й н ы м р е к у р
р е н т н ы м с оот нош е н нем
d
п+к
вк-i dn+k-i "Г ак~ч d
-b aQdni n 0, 1, . . .. (8,
8.14. Пример. Рассмотрим линейное рекуррентное соотио;
пне
Sfi+fi - S ,, | Sn,
п
0, 1................
над полем [р2. Импульсная функция d0t dlt соответствую^ этому
рекуррентному соотношению, представляет собой бинарн поеледователь иость
0, 0,0,0, 1,0, 0, 0, 1, 1,0,0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1,
и нмеет минимальный период, равный 21. Регистр сдвига с обр ной связью,
вырабатывающий эту последовательность, показ на рис. 8.5. Эту
последовательность можно рассматривать к
Выход
¦
I
4
• Я
г * . I if'i • < ii
Рис. 8,5
•! .fi
rJ>i>
ш
•Cl;
выходную последовательность указанного регистра сдвига, пещ ценную при
начальном заполнении следующего вида: все элемец задержки, кроме
последнего, в начальный момент времени ляются пустыми (т. е. содержат
заполнение 0), а в самый npai элемент задержки засылается импульс (т. е.
