Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
этом ее минимальный период г удовлетворяет неравенству г < qk, as случае
однородной последовательности -
Неравенству г qk - 1.
k Доказательство. Заметим прежде всего, что существует ровно Я различных
упорядоченных наборов по k элементов нз поля F,?.
5+
500 Гл. 8. Линейные рекуррентные последовательности
Поэтому если рассмотреть совокупность векторов состояний s 0 m gkt данной
линейной рекуррентной последовательное" k-го порядка над нолем Fg, то для
некоторых i, j, 0 < / < / -< | должно выполняться равенство sу = st. Из
соответствующе| линейного рекуррентного соотношения и принципа математик
ской индукции можно получить равенство $n+j_i = $п для вщ п ^ i.
Последнее означает, что наша линейная рекуррентная следовательность
является периодической последовательностью || если г - ее минимальный
период, то г / - i < дк. Рассмотри теперь однородную линейную
рекуррентную последовательности Если ни один из ее векторов состояний не
является нулевЕ* вектором, то, проведя аналогичные рассуждения с заменой
^ на qk- 1, можно получить неравенство г дк- 1. Если один нз ее векторов
состояний является пулевым вектором, ¦? все следующие за ним векторы
состояний тоже являются нул^ выми векторами н, значит, последовательность
имеет периа т - 1 <; дк - 1, Теорема доказана.
8.8. Пример. Верхняя оценка для г, полученная в теореме 8;j достижима.
Это можно показать, рассмотрев линейную рекуррелу ную последовательность
первого порядка иад нолем Fp (р - пр стое число), задаваемую соотношением
sn+l sn ¦ 1, п -
1, ..., и произвольным начальным значением Sq?Fp- Если Fg произвольное
конечное поле, a g - примитивный элемент это| поля (см. определение 2,9),
то однородная линейная рекуррентн| последовательность первого порядка над
этим полем, задаваем! соотношением sn+1 = gsn, п - 0,1, -*¦" so Ф имеет
минимад^ ный период г - д ~ 1. Таким образом, доказана достижимое*!
верхней границы для г и в однородном случае. Позже мы покаже" что в
случае произвольного поля Fg и любого целого k 1 сущ ствует однородная
линейная рекуррентная последовательное! k-ro порядка над полем F?,
имеющая минимальный период г | - qk - 1 (см. теорему 8.33).
8.9. Пример. Нетрудно заметить, что минимальный neptfj однородной
линейной рекуррентной последовательности первой порядка над полем F?
делит число q- 1. Однако для к минимальный период однородной линейной
рекуррентной nj следовательности &~го порядка не обязан делить число дк -
Так, например, можно проверить, что рекуррентная последов!; тельность s0,
slt ... над полем Fs. задаваемая рекуррентным сшЩ ношением sn+2 = 4-
sn. п 0, 1, ..., и начальными зкаШ ниями s0' = 0, st - 1, имеет
минимальный период, равный 20.
8.10. Пример. Линейная рекуррентная последовательное! над конечным полем
является периодической последовательность^ ио не обязана быть чисто
периодической последовательность^
Для доказательства этого достаточно, например, рассмотрев
§ 1. Регистры сдвига с обратной связью
501
линейную рекуррентную последовательность Sq, s1} ... 2-го порядка над
нолем F?, задаваемую рекуррентным соотношением
п + 1*
п ^ 0, 1, ..., и условием s$ Ф sx.
• t
?
Следующий результат дает важное достаточное условие для чистой
периодичности линейной рекуррентной последовательное! и.
8.11. Теорема. Пусть s0, ... -линейная рекуррентная по-
следовательность над конечным полем, удовлетворяющая линейному
рекуррентному соотношению (8.1). Если коэффициент а0 в (8.1) не равен 0,
то последовательность s0, sx, ... является чисто периодической.
Доказательство. По теореме 8.7 линейная рекуррентная последовательность
s0, sb ... является периодической последовательностью. Если г - ее
минимальный период, а п0 - предпе-риод, то - sn для всех п > п0.
Допустим, что в нашем случае пп > 1. Из соотношения (8.1), полагая п ~ nQ
+ г- 1 и учитывая, что а0 ф 0, получаем
1-fr
"О 2-f-г
¦ - alSn0+.
"Isn. - а).
а)
•4
Используя соотношение (8.1) для п = п0- U приходим к такому же выражению
и для , откуда следует равенство
sna \+г $п0~ 1 . Последнее противоречит тому, что п0 является
нредпериодом последовательности sx, ... . ?
Пусть s(t, slf ... - однородная линейная рекуррентная последовательность
степени k над полем FQ, удовлетворяющая инейному рекуррентному
соотношению
Sn+h - ak-lSn+k-l -j-
п
= 0, 1 (8.2)
где aj ? F9, 0 < / хУ k - 1. С этой линейной рекуррентной
последовательностью можно связать матрицу А над полем размера k X k
следующего вида:
А
0 0 1 О О 1
о ... о о... о о... о
а0
ах
а%
О 0 0 ... 1
(8.3)
Если k - 1, то нод матрицей А понимается матрица А - (а0) Размера 1 х 1,
Заметим, что матрица А зависит только от линейно рекуррентного
соотношения, определяющего данную рекуррентную последовательность.
502 Гл, 8. Линейные рекуррентные последовательности
... - ......... - ............. - ¦¦¦¦ -¦ "-¦¦!,! -И . ,
у
j*
8.12, Лемма. Еслиз^ slf ... - однородная линейная рекурренд пая
последовательность над полем удовлетворяющая соотн ше.нию (8.2), а А -
