Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 126
Текст из файла (страница 126)
Дальнейшие исследования по этим направ.' лециям можно найти в работах Раде, !!оЬ!пзоп, Тацзз]су, %агта" Комментарии 5'Н [! ], г[е Саг[! 111, Рцрагс [! ], Ко[я!пяоп Р. Ж. [41 и 5[т!це, 5[зев [! ]. Линейные рекуррентные последовательности над модулями изучались в статьях й[а[папяоп [5] и %ег[егге!!ег [51, 161.
Линей. иые рекуррентные последовательности векторов рассматривались в работах ВоПшап 1[1, РауЫп [41, Яе!шег [3, сп. 71, Ч1псе !21. Свойства периодичности последовательностей над [Го и У/(пг), удовлетворяющих рекуррентным соотношениям вида яи,д — — ад,(п)я„,д, +ад,(п)я„,д,+ +ао(п)я„, где коэффициенты а; (и) периодичны по и, изучали Нечаев ]! ]„ [3 ! и Полосуев [! 1. Свойства периодичности, получаемые из рекуррентных соотношений других типов, были получены Дюпарком (Рцрагс 121). Линейные рекуррентные последовательности над полем ]Ге представляют собой одномерный случай в теории линейных рекуррентных массивов над Го. Эта теория была развита в работах Мас%!!!!ашя, 51оапе [11, г[опшга, Гц[гцда [! ], Хошцга, М]уа[еатка, !ша[, Гц]ецг[а [!1, ]21, [31, Ьа$са1а !11, [21.
й 2. Особая роль, которую играет импульсная функция, была отмечена еще в классической литературе по линейным рекуррентным последовательностям (см., наппимер, [.исая [2, сп. 17] и с['Осанне [! ]). Теоремы 8.!6 и 8.[9 были получены Уордом (!гааге[ [51), а теорема 8.17 была доказана для простого д Спейгером (Бре!яег [! 1). Другие результаты, имеющие отношение к импульсным функциям, можно найти в работах А!!а! 1! 1, К!яя, Вш М!пп Рйопй [11, Ко[э[цзпп Р. \Ч.
[21 и Ье[шег [3, с[з. 3, 41. Отметим в связи с теоремой 8.!9, что Грот (Ого![з 11!) использовал число линейно независимых векторов состояний для введения меры сложности на последовательностях над полем К . Понятие характеристического многочлена и основная идея теоремы 8.2! восходят еще к Лагранжу ([.афганце 111, [51), который получил аналогичную теорему для линейных рекуррентных последовательностей над полем действительных чисел. Результат, приведенный в замечании 8.23, хорошо известен для линейных рекуррентных последовательностей над полем действительных или комплексных чисел (см. 3огдап С[з.
[1, сп. [11, М]!пе-Тпошяоп [[, сЬ. [31 и Маркушевич [11). Нетрудно заметить, что этот результат может быть перенесен на случай конечных полей при наличии ограничений на кратность корней характеристического многочлепа. Но н без этих ограничений все же имеются способы получения представления в явном виде для членов последовательности (см.
Р!Пщоге, Магх [1 1). Положим в теореме 8.21 зсе ]]з равными 1. Получаемая при этом последовательность привлекала внимание исследователей (см. Бе!шег [21, [3, сп. 51, ц агг] [31, 141, %ейпег [21, [4!). Теорему 8.24 можно найти у ван Линга (чап 1.!п! [[, с[т, 3!). Более сложная формула справедлива для случая, когда характеристический многочлен не имеет крат- о72 Гл. З, Линейные ренуррентные последовательности ных корней (см. %едегге([ег [81 и упр. 8.41).
Аракелов и Варш мов [!1 показали, что и-й член однородной рекуррентной посл довательности й-го порядка над полем Г может быть представая' в виде Ял = Ие (и) во+ ' ' ' " яь-1 (и) зь-1 где де (и) 6 Ге. Здесь же изучались выражения для д; (и), Ал ритмы для вычисления з„при больших п обсуждаются в работа СПез, [.еч|п (! 1, М1!!ег, Вгоьчп (11, Ре((огозз! !! 1, РеНогоззу Вигз(а!1 [11, Бе1гпег (3, сЬ.
5(, [)гЬапе[г (1 (, %1!зоп, БЬог[1 [1[-, Теорема 8.25 по существу получена Уордом (гааге( !5 1). Резуль„" таты из линейной алгебры, использованные при доказательст' ' леммы 8.26, а именно то, что 7" является минимальным многочлен соответствующей сопровождающей матрицы, можно найти, вае пример, в книге Но[!шап, Кинзе [1, сЬ. 7!. Лемма 8.26 и теоре 8.27 непосредственно приводят к результатам о порядке сопрово дающих матриц как элементов группы 65 (я, Гч), таким, напр: мер, как верхняя граница д' — ! для порядка таких матри ' полученная Гуптой (Сир1а (! (). Линейные рекуррентные пос довательности, характеристические многочлены которых явля трехчленами, изучались в работах Со!дз[е(п, Ъег[ег [11, Еиппо" Р!еазап[з, 5[ерйепз [! 1, Упит [11 и Аракелов, Тененгольц [[1 Кумари (Кишат( 111) рассматривал другой специальный кл ' линейных рекуррентных последовательностей.
Первое детальное изучение последователь~)остей максимал ного периода (называемых также т-последоватвльносгпями ий' (в электронике) псевдослучайными последовательностями (рзеие[' поВе зепиепсез)) было предпринято Голомбом (Со!отЬ [1 но там эти исследования ограничивались случаем последоват настей над полем Ее (см. также Со(отЪ [21, [4, сЬ. 3, 4, 61, (ошЬ, '1че!зЬ [11).
Более глубокое исследование таких после вательностей над произвольным полем (Ге можно найти в работ ' Е(ег!ег [41, Бе(шег [3!. В статье ()ауй(й, Огезе!, Н(!1оп (11 р,' сматривались последовательности 2-го порядка, имеющие мак мальный период. Ряд работ был посвящен эффективным методв построения последовательностей максимального периода (см. Ва1Ф„' Бр(11!е, 1 ги [11, Е!ег, МаПес1е 111, Нагчеу [11, [.етре! 111, [.егарей~'; Еаз[шап (1 1, МоЬггпапп [! 1, [2!, Бсйо[е[(е!д (1), БигЬбсК %е[!еч НсЫег [1 !). Различные обобщения последовательностей максйу., мального периода встречаются в работах Мас'ьРЛ[1(ашз, Б(папе 11 Ь(отига, М(уакаьча, 1шаЬ Рикие(а [11, 131, 5ака[а (! )и Нечаев 11('." Построение последовательностей де Брейна с использование последовательностей максимального периода (см.
упр. 8.19) был предложено Мантелем (Мап1е! [11), см, также работу Реев (1)1 Существование (т, й)-последовательностей де Брейна для пронй[ вольных параметров т и й было впервые доказано Мартиной Комм«и»арии 573 !Маг!!п 1! )), а частный случай т = 2 был изучен ранее в работе Р!уе Ба!п!е-Маг!е [11. Последовательности де Брейна получили свое название после появления работы де Вгн!)п (1). Другие результаты о последовательностях де Брейна можно найти, например, в работах Агах! (21, Ргес(г!с(сзеп 111, Ргедг!скзеп, Кезз(ег !! 1, бо(овЬ [4, сЛ.
61, бо!овЬ, %е!сЛ (! ), боод (1), а также в обзорной статье Ргебг!с(сзеп [21. Связанное с этим понятие кодового кольца изучали Радченко н Филиппов !11, 121. Другое приложение к комбинаторике последовательности максимального периода находят в теории разностных множеств (см. определение 9.75). Этн вопросы освещаются в работах Вц!зоп (11, бо!овЬ 13, сЛ, 41. !.ах1оп, Апдегзоп [1), Бе(вег (3, сЛ. 61. Работа Вц(зоп 1! ) содержит также приложение к построению матриц Адамара (см. определение 9.86). Этой же тематике посвящена и работа Мас((Г!!!!авз, Ыоапе 111.
В статье Ваг(ее, БсЬпе!с(ег [1) векторы состояний последовательности й-го порядка над полем Р«, имеющей максимальный период, вместе с нулевым вектором использованы для описания элементов поля Р» (см. также Мас%1!1!авз, « 5!оапе (11, Мбпп!и [! 1). Голомб (бо!овЬ [1!) впервые начал использовать последовательности максимального периода в качестве генераторов псевдо-случайных чисел (см. также бо!овЬ [3, сЛ. 11, [4, сЛ. 31, КпцГЛ 13, сЬ.
31, Л[!ес(егге!!ег !71, [101, (!21, 1131, Тацзмог(Ле 111 и Павлов, Походзей [11. Некоторые приложения последовательностей максимального периода к теории кодирования встречаются в работах бгееп, Бап Боне!е 111, й!ас»т!!!!авз, Ыоапе [11, »«Ген [1), 'га(е (1), Е!ег!ег [3) и Грушко [11. По поводу других приложений последовательностей максимального периода отсылаем к работам Ваг1ее, ЯсЛпе!бег (11, бо!овЬ (3, сЛ. 2), Ьах1оп, Апбегэоп (11, МоЛап1у [!1, Ь(ас(!ег, Бепнир!а 111 и Сагалович 111. $3.
Использование производящих функций в теории линейных рекуррентных последовательностей над конечными полями началось с работ Голомба (бо!овЬ 11!) н Хаффмэна (Ннйвап (! 1, (21). Затем этот подход более полно использовался в работах Рг!ед(апс( [11, В!сЛа(е! [11, Ыегп, Рг!ед!апс( (11, Е!ег!ег 141 и Назаров 111; см. также книги [ цпеЬнгд (3, сЬ. 24, 25! и Бе1вег (3, сЛ. 3!. Формальные степенные ряды над полем Р„представляющие «почти периодические» последовательности, изучались в работе Ванги, НеггЬегд, 1овопасо, 5»чее! !11.
Более общие последовательности, имеющие в качестве производящих функций алгебраические функции над Р«, появились в работе Рцгз!епЬегн [11. Другой подход к линейным рекуррентным последовательностям над полем Р«основывается на теории идеалов — см. работы На!1 [31, Ре!егзой [11, [.а)сзоч (! 1 и айаг«( 151, Обзоры по этой 574 Гл. 8. Линейные рекурревтвые последовательности тематике можно найти в книгах Ре!егзоп, %е!акоп ]1, сЬ. 7] Ве!шег ]3, сЛ. 3). В работах НепцпаЬЬ Сов]е]]о ]1) и Пса)* Коза]со, Ко!!ша [! ], [2) применяется комбинированный подх с использованием теории производящих функций и теории нде ' лов в кольце Ге 1хЕ $4. Все осйовиые результаты о минимальных многочлена' можно найти в работе Х!ег]ег [4]. Теорему 8.44 можно найт также в статье Гг1еб!апс], 5!егп 11].
Наше доказательство теорем 8.42 имеет то преимущество, что оно является конструктивн (см, также %!!!е]1!! 1). Набросок более короткого, но неконстру, тивного доказательства приводится в упр. 8.25 (см. также 2!ег] ' ' [41). Другие подходы к понятию минимального многочлена мо найти в работах Ьайзоч [! ) н Яе!шег [3, сЬ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
