Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 111
Текст из файла (страница 111)
Заменяя в (8.1) и на п + 1 и вычитая из полУ ченного равенства исходное равенство (8.1), получаем соотношен э,ь,1 = Ьлэ +а+ Ьл-ьзаьь-ь+ ' ' ' + Ьова и = О, 1,..., (8. где Ь,= — а„, Ьг=ау,— а; для 1=1,2,...,я — 1, Ьь =- аа, + 1. Таким образом, последовательность зь э„... мож, свести к однородной линейной рекуррентной последовательност. й 2, Импульсная функция. Характеристический миогочаея 503 1)-го порядка над полем !)а, и, следовательно, результаты, полученные для однородных лийейных рекуррентных последова,етьностей, дают информацию и для неоднородного случая. Существует и другой подход к рассмотрению неоднородного случссч. Пусть з„зы ... — неоднородная линейная рекуррентная последовательность й-го порядка над полем Ка, удовлетворяющая соотношению (8.1).
Рассмотрим связанную с ней матрицу С над шлем гч, 'являющуюся квадратной матрицей размера (й + 1) х (й Р !) следующего вида: ! 0 0...0 а о о о ... о 0 1 0...0 а, 0 0 1...0 а, 0 О 0...1 пад 1:.сли й:= 1, то полагаем с-( Введем модифицированный вектор состояния рекуррентной последовательности, полагая аа =(1 з„, за+о за+а ~) для и =О, 1, Гогда, как нетрудно заметить, для всех п ) 0 справедливо раяенство з,',, =- з,',С, откуда по индукции получаем, что з,' = а;С' для всех и )~ О. Если в (8.1) коэффициент аа отличен от О, то а)е1 С --- ( — !)"- ' а, ~ О, откуда следует, что матрица С является элементом группы бь (и + 1, К ).
В этом случае, проведя рассуждения,' аналогичные доказательству теоремы 8.!3, нетрудно показать, что минимальный период последовательности '» ао ... делит порядок матрицы С, рассматриваемой как элемент "Руины И. (й -1 ф 2. Импульсная функция. Характеристический многочлен Из всех однородных линейных рекуррентных последовательиостен над полем Кч, удовлетворяющих данному линейному рекуррентному соотношению и-го порядка вида (8.2), можно выделить одну последовательность с максимальным значением минидоап "ал" ного периода, называемую импульсной функцией или после'аптельностью, порожденной импульсом, Эта последовательность Гл.
8. Линейные ренуррентные последовательности обозначается да, й,, ... и однозначно определяется начальны значениями с(е ... = йа ., --- О, й„л =- 1 (йе = 1 для й = 1) линейным рекуррентным соотношением й„„, = ан лй,ь-л-ьа«- й а-т р ° .згаой„, и =-О, 1,.... (8 8.!4. Пример. Рассмотрим линейное рекуррентное соотно ние в„,» --- в„„-.
'х„, и — - О, 1,..., над полем !«Импульсная функция йе, й,, ..., соответствую зтому рекуррентному соотношению, представляет собой бинарн ' последовательность 0,0,0,0,1,0,0,0,1,1,0,0, 1, О, 1, О, 1, 1, 1, 1, 1, О, 0,0,0, 1, и имеет минимальный период, равный 21. Регистр сдвига с обр ной связью, вырабатывающий зту последовательность, пока на рис. 8.5. Эту последовательность можно рассматривать к Рис.
8.8 выходную последовательность указанного регистра сдвига, по" ченпую при начальном заполнении следующего вида: все злеме задержки, кроме последнего, в начальный момент времени лаются пустыми (т. е. содержат заполнение 0), а в самый пра' злемент задержки засылается импульс (т. е. он содержит заи' пенне 1). Этим, кстати, и объясняются термины <импульс ' функция» или «последовательность, порожденная импульсом», ' 8.!5.
Лемма. Пусть йе, йл, ... — последовательность над лем г<, являющаяся импульсной функцией, удовлетворяющей куррентному соотношению (8.6), и пусть А — связанная с иатрици вида (8.3). Тогда два вектора состояния д и д„рек рентной последовательности йа, йл, ... совпадают в том и тола толл случае, когда А"' А". е Дллназателлютео.
Достаточность следует из леммы 8.12. доказательства необходимости предположим, что й„, — — — л! . Из Л, нейного.рекуррентного соотношения (8.6) получаем, что «(,л, — «!н„л для всех 1, О. Из леммы 8,12 следует, что «!лА'" — — «1' для всех ! . О. Тогда в силу того, что векторы «1„, а„..., т! образуют базис й-мерного векторного пространства Г, над п Г«, получаем требуемое равенство А~ — А". 4 2.
Импульсная функции. Характеристический многочлен 505 8.16. Теорема. Минимальный период однородной линейной рекуррентной последовательности над полем Кч делит минимальный период соответствующей импульсной функции. Доказательство. Пусть а„а„,... — однородная линейная реиуррентная последовательность над полем Гч, удовлетворяющая соотношению (8.2), а д„й„.,.
— соответствующая импульсная ~! енкция, и пусть А — матрица вида (8.3). Если г — минимальный период последовательности йа, й„..., а и, ее предпернод, то й„,. = д„для всех и ) и,. Из леммы 8.15 следует, что А"+' = =-. А" для всех и ) п„а тогда по лемме 8.12 а„,„=- а для всех и ':. па. Следовательно, г является периодом последовательности аа, во .... Из леммы 8.4 получаем теперь утверждение теоремы. Д 8. ! 7.
Теорема. Если последовательность йа, й„... является илтульсной функцией й-го порядка над полем 4Г и удовлетворяет соотношению (8.6) при а, чь О, а А — соответствующая матрица вида (8.3), то тогда минимальный период этой последовательности ровен порядку матрицы А как элемента общгй линейной группы ОЕ (й, Г~). Доказательство. Если г — минимальный период последовательности й„й„..., то по теореме 8.!3 г делит порядок матрицы А. С другой стороны, по теореме 8.11 имеет место равенство оа = й„, Применяя лемму 8.15, получаем, что А' = А', откуда следует искомый результат. Д 8.!8. Пример.
Мы видели, что для линейного рекуррентного соотношения э„„== э„„+ э„, и — -- О, 1, ..., над полем Г,, рассмотренного в примере 8.14, минимальный период соответствующе|! импульсной функции равняется 21, что совпадает с порядком матрицы 0 0 0 0 1 ! 0 О 0 1 О 1 0 0 0 0 0 1 0 0 0 О 0 1 0 как элемента группы 6) (5, Ка). Если вектор начального состоя'шя некоторой линейной рекуррентной последовательности над полем К„удовлетворяющей данному линейному рекуррентному соотношению, совпадает с одним из 2! различных векторов состояний, которые появляются в соответствующей импульсной Функции, то минимальный период такой последовательности снова равняется 21 (так как такая последовательность представляет собой сдвиг этой импульсной функции), Если для того же Рекуррентного соотношения в качестве вентора начального со- 506 Гл.
8. Линейные ренуррентные нооледоннтельностн стояния выбрать вектор (1, 1, 1, О, 1), то мы получим бинарную последовательность 1, 1, 1, О, 1, О, О, 1, 1, 1, О, 1, .... Мини-' мальный период этой последовательности равен 7. Такой же минимальный период будет иметь любая рекуррентная последовательность, удовлетворяющая этому соотношению и получающаяся, если в качестве вектора начального состояния взять любой и ' 7 различных векторов состояний этой последовательности. Есл в качестве вектора начального состояния взять вектор (1, 1, О, 1, !);; то мы получаем бинарную последовательность 1, 1, О, 1, 1, 0$ 1, 1, ..., имеющую минимальный период, равный 3.
Такой жф минимальный период получается, если в качестве вектора цачаль! ного состояния рекуррентной последовательности взять любо" из трех различных векторов состояния этой последовательностнг Вектор начального состояния, равный (О, О, О, О, 0), порождает последовательность с минимальным периодом !.
Таким образом,." мы рассмотрели все 32 возможности выбора вектора начального состояния для рекуррентной последовательности, удовлетворяю-" щей нашему рекуррентному соотношению. и' 8.19. Теорема. Пусть аь з„... — однородная линейная рекуррентная последовательность и-го порядка над полем Гд, а и„— ' предпериод этой последовательности. Если существует й векторов состояний а, а, ..., зм„, т; ) и (1 ( !' ~~ )г), которые ли«.: чейно независимы над К», то как сима последовательность зе,'-'!: з,, гпак и соответствующая импульсная функция являются,', чисто периодическими последовательностя.ни, имеющими один' и тот же минимальный период.
Доказательство. Пусть г — минимальный период последовательности аь з,, .... По лемме 8.12 для 1 ( ! .( я справедливсь Г равенство ам А — — — з,„., =- а ., и, таким образом, А" равняется. единичной й х я-матрице над полем !)' . Отсюда получаем а„= ',, = а,А' == а„откуда следует, что ан з„... является чисто периоди-',. ческой прследовательностью. Аналогично если через д„обозна-',, чить и-й вектор состояния соответствующей импульсной функции, ', то и, =- д,А' == по. Применив теперь теорему 8.!б, получаем': утверждение теоремы. ):) ' 8.20.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
