Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
он содержит за иен не 1). Этим, кстати, и объясняются термины "импульс
функция" или "последовательность, порожденная импульсом"..;
8.15. Лемма. Пусть diU dlt ... - пос ледова те льность над i лем fg,
являющаяся импульсной функцией, удовлетворяющей \ кур рентному
соотношению (8.6), и пусть А -связанная с матрица вида (8.3). Тогда два
вектора состояния dт и dn рещ рентной последовательности du, db ...
совпадают в том и таМ том случае, когда Ат - Ап.
Доказательство. Достаточность следует из леммы 8.12. ДЙ доказательства
необходимости предположим, что dm = dn. Из || нейного рекуррентного
соотношения (8.6) получаем, что dmfT =г" для всех t > 0. Из леммы 8.12
следует, что dtAm = d для всех / 0. Тогда в силу того, что векторы d0,
db
образуют базис ^-мерного векторного пространства pj над п> получаем
требуемое равенство Ат - Ап.
•:т
I •
§ 2. Импульсная функция. Характеристический многочлен 505
8.18. Теорема. Минимальный период однородной линейной рекуррентной
последовательности над полем SF9 делит минимальный период соответствующей
импульсной функции.
Доказательство. Пусть Sq, slt...- однородная линейная рекуррентная
последовательность над полем SFg, удовлетворяющая соотношению (8.2), a
dQi - соответствующая импульсная
функция, и пусть А -матрица вида (8.3). Если г - минимальный период
последовательности d0t du .... а п0 ее предпериод, то dn+r - для всех п >
н0. Из леммы 8.15 следует, что Ап+Г ~ = Ап для всех п > щ, а тогда по
лемме 8.12 sn+r - sn для всех п > и о. Следовательно, г является периодом
последовательности s0, sx, ... .Из леммы 8.4 получаем теперь утверждение
теоремы. ?
8.17. Теорема. Если последовательность d#, dlt ... является импульсной
функцией k-го порядка над полем фф и удовлетворяет соотношению (8.6) при
Ф 0, а А - соответствующая матрица вида (8.3), то тогда минимальный
период этой последовательности оавен порядку матрицы А как элемента общей
линейной группы GL (С fQ).
Доказательство. Если г - минимальный период последовательности d0, dlt
..., то по теореме 8.13 г делит порядок матрицы Л. С другой стороны, по
теореме 8.11 имеет место равенство d0 = dr. Применяя лемму 8.15,
получаем, что Аг = Л°, откуда следует искомый результат.
8.18. Пример. Мы видели, что для линейного рекуррентного
соотношения sn+5 = sn+t j sn, n = 0, 1,
над полем !F2, рас-
смотренного в примере 8.14, минимальный период соответствующей импульсной
функции равняется 21, что совпадает с порядком матрицы
А
0
1
0
О
0
0
0
1 О 0
0
0
О
0
0
0
О
0
1
П 1
о о о
как элемента группы GL (5, ра). Если вектор начального состояния
некоторой линейной рекуррентной последовательности над полем р2,
удовлетворяющей данному линейному рекуррентному соотношению, совпадает с
одним из 21 различных векторов состояний, которые появляются в
соответствующей импульсной Функции, то минимальный период такой
последовательности снова равняется 21 (так как такая последовательность
представ-л нет собой сдвиг этой импульсной функции). Если для того же
рекуррентного соотношения в качестве вектора начального со-
506
Гл, 8, Линейные рекуррентные последовательности
стояния выбрать вектор (1, 1, 1, 0, 1}" то мы получим бинарную
последовательность 1, If 1, 0, 1, 0, 0, 1, 1, 1,0, I, ... . Минимальный
период этой последовательности равен 7. Такой жё минимальный период будет
иметь любая рекуррентная последовательность, удовлетворяющая этому
соотношению и получающаяся, если в качестве вектора начального состояния
взять любой и 7 различных векторов состояний этой последовательности. Есл
в качестве вектора начального состояния взять вектор (1, 1, 0, 1, 1}| то
мы получаем бинарную последовательность 1, 1,0, 1, I, 0| 1, 1, имеющую
минимальный период, равный 3. Такой ж минимальный период получается, если
в качестве вектора началь ного состояния рекуррентной последовательности
взять любой из трех различных векторов состояния этой
последовательности.*-Вектор начального состояния, равный (0, 0, 0, 0, 0),
порождает последовательность е минимальным периодом 1. Таким образом,/ мы
рассмотрели все 32 возможности выбора вектора начального состояния для
рекуррентной последовательности, удовлетворяющей нашему рекуррентному
соотношению. НЕ
Ш
8.19. Теорема. Пусть s)(
однородная линейная ре-
куррентная последовательность k-го порядка над полем рА, а пи пред период
этой последовательности, Если существует к векторов
состоянии Sm.
№
А'
т
• r*.w
7 ^ % I1 X J К), которые ли
ней но независимы над fq, то как сама последовательность s Sj, так и
соответствующая импульсная функция являются^ чисто периодическими
последовательностями, имеющими один и тот же минимальный период.
Доказательство. Пусть г - минимальный период последах! вательноети s0, sb
... . По лемме 8.12 для 1 .< / k справедлива!
равенство $тЛг - sm.+r --- sm., и, таким образом, Аг равняется
единичной k X ^-матрице над полем fq. Отсюда получаем sr -
щ
stiAr = s0, откуда следует, что%, ... является чисто период"-
