Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
характеристический многочлен этой последовательности, a G (х) б Fg М) -
производящая функция этой последовательности, определенная в (8.13).
Тогда имеет место равенство
G"=fr?). (в. 15)
где
g(x) = - ? ? a,+^}SiXi ? F,W (8',6>
f-Q 1=0
u ah =¦- - 1. Обратно, если g (x) - производящий многочлен на полем Fg,
deg (g (x)) < &* a f* (x) ? fgfxl задается равенство.
(в. 14), то формальный степенной ряд G (дг) ? Fg |[х]], задавав мый
равенством (8.15), является производящей функцией од но рек ной линейной
рекуррентной последовательности k-го порядка на полем Fg* удовлетворяющей
линейному рекуррентному соотш
шению (8.7).
1) В литературе этот многочлен называется также двойственным
характеристическим многочленом. - Прим. перев.
522
Теперь, еслн последовательность s0> slt ... удовлетворяет
Доказательство. Имеем
Гл. 8. Линейные рекуррентные последовательности
то нз (8.12) следует, что /* (я) G (х) ~~ g (х). Тогда в силу тогй что по
теореме 8.37 /* (х) имеет обратный относительно опЗ рации умножения
элемент в [[х}]( получаем справедливост| равенства (8.15). Обратно, из
(8.17) следует, что произведен^ /* (х) G (х) равняется многочлену
степени, меньшей чем k, тольк| тогда, когда J
Последнее как раз означает, что последовательность %, 5,, .,1
составленная из коэффициентов формального степенного ряда G..(х||
удовлетворяет линейному рекуррентному соотношению (87).Д
Приведенную выше теорему можно коротко сформулироватй следующим образом:
существует взаимно однозначное соответ| ствие между однородными линеннымн
рекуррентными последо| вательностями &-го порядка с возвратным
характеристически)! многочленом [*(х) и дробями вида g(x)/f*(x)r такими,
чт| deg (g (х)) < k. Равенство (8.15) в этом случае может быть испол*|
зовано для вычисления членов линейной рекуррентной последЙ вательности с
помощью алгоритма деления углом. |
¦;С|
8,41. Пример. Рассмотрим линейное рекуррентное соотноше|| ние '. I
k
? = 0 для всех j > k.
над полем f2. Соответствующий возвратный характеристически многочлен
имеет вид
Если вектор начального состояния равен (1, 1, 0} 1), то много4 член g
(х). определенный в (8.16), равен g (х) = 1 f х2. Тогд^
§ 3. Производящие функции
523
производящая функция G (л:) рассматриваемой рекуррентной
последовательности может быть получена с помощью деления углом:
1 4 х2
! + х + х* 4 х1
1 -j- X + Xs 4 X4
1 _j_JC_j_jK*_|_JC44j?e
t " >
X 4 X2 4 х3 -f
х2 4- х4 -(¦- х5
X3 + X5
х3 + ¦ + Xе -(- х7
х4 4 я6 ~Ь ** + *7 х4 4 х6 -j- х7 4Х8
? + 7
Таким образом,
GW = r4rm- = 1 +jr + yJ + ^ + **+-,
что соответствует бинарной последовательности !, I, 0, 1, 1, О, 1, ...,
имеющей минимальный период 3. Импульсную функцию, связанную с данным
линейным рекуррентным соотношением, можно получить, если положить g (х) -
х3. Алгоритм деления углом дает в этом случае производящую функцию
G (х) = т- -г":-г - х3 4- х4 4 4 х* 4 *10 + хп
' f j х 4 х3 4 х
"Ч
что соответствует периодической бинарной последовательности О, 0, 0, 1,
I, I, 0, 0, 0, 1, 1, 1, ... с минимальным периодом, равным 6. ?
Из равенства (8.15) можно получить другое доказательство теоремы 8.25.
Действительно, ввиду того что последовательность 4, s1( ... является
чисто периодической последовательностью с минимальным периодом равным г,
ее производящая функция G (х) может быть записана в виде
G (х) = (s0 4 stx 4 * • * 4 sr_jXr--*) (! 4 & + & 4 •¦¦) = 7~*^7"
1 - x
где s* (х) = s0 4 Six 4 ..*4 sr-гхг~~1. С другой стороны, используя
обозначения теоремы 8.40, из (8.15) получаем, что G (х) - ~ 8 (х)if* (х).
Приравнивая полученные выражения для G (х), приходим к полиномиальному
равенству /* (х) s* (х) - (! - *г) S (х). Если f (х) и s (х) такие же,
как в (8.9), то
/ (х) s (х) = xhf* (! /х) xr"fs* (1/х) = (хг - 1) xk~] g (I /х).
524
Гл. 8. Линейные рекуррентные последовательности
- >у* fs
Сравнивая (8.10} и (8Л6}" получаем
xk-ig (\[х) = -h (х), откуда и следует равенство (8.9).
§ 4. Минимальный многочлен
. 'Щ
Щ
(8.18)
Хотя до сих пор мы этого не отмечали, очевидно, что линейная!
рекуррентная последовательность удовлетворяет множеству дру гих линейных
рекуррентных соотношений помимо того, которой определяет эту
последовательность. Так, если последовательное^ s0, sl( ... является
чисто периодической последовательностью щ периодом г, то она
удовлетворяет линейным рекуррентным соотношениям $п+г = sn (п = 0, 1,
...), sn+2r = sn (п - 0, 1, ...) н т. д. Экстремальный случай
представляет собой последователь! ность 0, 0, 0, ..., которая
удовлетворяет любому однородному линейному рекуррентному соотношению.
СледуюнГая теорема опщ сывает, как связаны между собой различные линейные
рекуррент ные соотношения, которым удовлетворяет данная однородная
линейная рекуррентная последовательность.
8.42. Теорема. Пусть s0, s,, ... - однородная линейная рекурщ^ рентная
последовательность над полем Ffr Тогда существуетf однозначно
определенный нормированный многочлен т (х) ? Fa [х],
