Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 128
Текст из файла (страница 128)
Простая формула для 2 (Ь) в случае последовательности максимального периода была впервые получена в работе Оо1ошЬ [ ! ] для последовательностей над полем Г,. Теорема 8.82 доказана в статье МедеггеИег [6]. Оценка такого типа была аолучеиа раиьше комбинаториыми методами в работе НаИ [4) для случая однородной линейной рекурреитной последовательности Ьго порядка пад полем Гр с иеприводимым характеристическим миогочленом. Еще раньше Холл (НаИ [3]) показал, что если в этом случае минимальный период превосходит величину р"~', то в последовательности обязан встретиться элемент О. Селмер (Яе!гпег [3, 5]) получил аналог результатов Холла для случая, когда ч =- 2 и характеристический миогочлеи является произведением двух различных иеприводимых многочлеиов над полем [[',.
Теорема 8 84 доказана в работе МсЕИесе [5]: Распространение этого метода иа случай, когда минимальный многочлеи ие имеет кратных сомножителей, можно найти в работе ЛИег[егге!1ег [8), Результат теоремы 8,85 о распределении элементов поля на отрезках рекурРентных последовательностей длины, меньшей периода, был получек в работе%ег[егге!1ег [6].
Там же было показано, что эта оценка иеулучшаема. Распределение элементов, принадлежащих данному подмножеству поля Гч (например, принадлежащих множеству 10 Зак. 243 Гл. 8. Лннейные рекуррентные последовательности примитивных элементов поля Ге), в линейных рекуррентных:,, последовательностях над полем Е рассматривалось в следующих,! работах; Медегге]!ег [6), Коробов [1], Нечаев [4), Нечаев,: Степанова [1] и Шпарлинский [!). ттналогичные вопросы для " последовательностей, удовлетворяющих более общим рекуррент- 1 ным соотношениям, изучались Нечаевым и Полосуевым [1].
*' Многие результаты из этой работы могут быть перенесены на ~ случай линейных рекуррентных последовательностей над кольцом! К1(т) (см. [т]!едегге)(ег 16), Нечаев [4]). Голомб (бо]ошЬ [9)) рассматривал последовательности над т полем ]['т с периодом (не обязательно минимальным), равным я 2» — 1, в которых число появлений 0 и 1 такое же, как в мини ~ мальном периоде последовательностей и-го порядка, имеющих~ максимальный период.
В статье Непипа1Ь Соз!е!!о [1) построены тинейные рекуррентиые последовательности над полем Ке, длякоторых Я (0) = О. Макэлайс (МсЕВесе [4]) получил значений' для Л (Ь) по различным модулям, равным степеням характери-'. стики поля Ге. Исследование распределения элементов в линейных' рекуррентных последовательностях небольших порядков был, проделано в работах 5сагр)з [2], Магд ]3), На]1 [2], а также' в появившихся позднее работах В!оот [! ), Вгцс]снег [1], Впгг' [1], ЯЬаЬ [1], Лес]сепдог! [1]. Некоторые из этих работ охваты" анют случай последовательностей над кольцом Х'(т), Результаты] о свойствах распределения элементов поля в линейных рекурреит-'. ных последовательностях находит применение в теории кодирова»', ння (см.
МсЕ11есе [5], %едегге](ег [8)), а также при получении: псевдослучайных чисел (см., например, По1огпЬ [!), [4, сЬ. 3];У ЬВеде!те]1ег [7), [10]). Линейные рекуррентные последовательности над полем Ге,)т для которых Е (Ь) имеет одно и то же значение для всех Ь ь Г,' привлекают особое внимание. Последовательность р таким свой',')] ством называется равномерно распределенной (цпИогш!у д)з1г~',;,1 Ьц1ед, ецп[д]з[г!Ьы1ед) над Ее согласно определению, приведенномУ':.: впервые в работе По!цаво [1) (см, также Кшрегз, Ь]]едегге!]е)' [1, сЬ. 5].
Изучение равномерно распределенных линейных рекур'" рентных последовательностей было начато в работах Кшрегз, ВЬше [1], [2], [3], [4]. В них рассматривался случай последовательностей 2-го порядка над конечными простыми полями нли над кольцами вычетов 7,'(и). В частности, последовательность Фибоначчи является равномерно распределенной над л,'(тп) тогда и только тогда, когда т — степень числа 5 (по поводу доказательства необходимости см. Кшрегз, 5Ь!це [4], а достаточности— ЬВедеггейег [4]).
Равномерно распределенные линейные рекуррентные последовательности 2-го порядка над кольцом У/(лт) изучались в работе Ха1Ьапзоп [4) для случая простого числа т, в работе ВипдзсЬцЬ, БЬ!це [1] для случая т, равного степени Комментарии 579 .,!ростого числа (см. также ФеЬЬ, [.опя [1)), а также в работе ВпшЬу 11] для случая произвольного т. С этими исследованиями также связаны статьи Вппе[зсЬпЬ (!), Сан!ог (7(, Я!ше [1], 5Ьше, Нп [1!.
Равномерно распределенные линейные рекуррентиые последовательности 2-го и 3-го порядков над полем (['ч исследовались в работе Ы!ее[егге!(ег, 5Ь!це [1), а последовательности 1-го порядка — в работах (ч!е![егге!(ег, 5Ьше (1], (2). Найт и Уэбб (Кп!дЫ, ФеЬЬ [!]) изучали равномерно распределенные линейные рекуррентные последовательности 3-го порядка над кольцом ~".!(т). В статье (т(!едегге!!ег, 5Ь!це [1] показано, что если линейная рекуррентная последовательность произвольного порядка является равномерно распределенной последовательностью !ад полем Ге, то ее минимальный многочлен обязан иметь по меньшей мере один кратный корень, отличный от О. В этой же работе изучались последовательности, минимальные многочлены которых разлагаются на множители некоторым специальным образом.
Результаты, касающиеся равномерно распределенных линейных рекуррентных последовательностей произвольного порядка над кольцом Б(т), можно найти в работах Кшрегз [3), к!!ебегге!(ег [1!), К(едег [!), (2], (31. Вопрос о частоте появления того или иного элемента поля а линейной рекуррентиой последовательности можно обобщить следующим образом: какова частота появления того или иного блока элементов среди блоков, составленных из стоящих подряд членов данной последовательности.
Для последовательностей [а-го порядка над полем Гч, имеющих максимальный период, число появлений данного блока длины ! ( [т на отрезке последовательности длины, равной полному периоду, может быть определено непосредственно с помощью прямых комбинаторных подсчетов (см.
Со!ошЬ [1] для случая а = 2 и Х!ег1ег (4] для общего случая). Дальнейшие результаты, касающиеся распределения блоков, составленных из элементов основного поля, в линейных рекуррентных последовательностях, можно найти в работах !лепя (1], Ггедг!сззоп [1], Лог![ап, Фоат (!), 1 а[сзоч (!), ).[пбЬо!гп !11, Ве1гпег [3, сЬ.
5), 2[ег!ег [4). Связь с псевдослучайными ~ислами, полученными с помощью линейных рекуррентных соотношений, изучается в работах ЬВедегге11ег [9], [12], [13]. С этой же тематикой связан и вопрос о корреляционных функциях последовательностей, нашедших важное применение в исследованиях по электронике. Если за, з,, ...
и (а, [т, ... — две последовательности над полем Гч, имеющие период г, а )( — нетривиальный аддитивный характер г, то тогда соответствующая кросс- корреляционная функция С (1!) определяется формулой т — 1 С(й) = Е Х(з.)Х([..а), 880 Гл. 8. Линейные рекуррентные последовательности где й = О, 1, ..., г — 1, а 1г. означает сопряженный характер [см. 5 1 гл. 5 настоящей монографии). Если последовательности, з,, з,, ... и !з, 1„...
совпадают, то мы говорим об автокорреляцион-:, ной функции. Для последовательностей максимального периода т над полем Еь автокорреляцнонная функция изучалась в работе,, Сьо!огпЬ [1]. На случай произвольного поля этот результат рас- '! пространил Цирлер [2[ег!ег [4]). Кросс-корреляционная функция,", для двух последовательностей максимального периода над по-, лем з ь рассматривалась в статье ало!огпЬ [2], Другие результаты о корреляционных функциях можно найти в работах репа [ИЬ '. бо!«[ [2], [3], бо!огпЬ [4, сЬ. 3, 4, 6), [5], Сьо!ошЬ, %е!сЬ [!],,' НеИезеЬЬ [2], 1.ее, Егп!1Ь [1], 1.егпре!, СоЬп, Еаз1гпап [!], Ма- '": г![заз [1], МсЕИесе [7], МоЬап1у [1], Яе!гпег [3, сЬ. 6], Ипатов,:; [1], а также обзор в статье НеИезе!Ь [1]. Некоторые корреля-,,', ционные свойства последовательностей над полем Еь изучались:;, также в работе Мас%ИИашз, О«[!ух[«о [1]. [Соболь [1*], [2*] использовал теорию линейных рекуррент" ных последовательностей над конечным полем для построение':;, ,последовательностей точек, равномерно распределенных в еди,:, ничном з-мерном кубе с наименьшим возможным отклонением ' Шпарлинским [!'] показано, что для «почти всех» начальнык: условий вычеты членов линейной рекуррентной последователь'"' ности по простому модулю равномерно распределены.
Подоб.", ные же результаты были получены Эгами [Еяагп! [1']) в связни с одной задачей теории алгебраических чисел. По тематике восьмой главы кроме указанных имеются еще"' работы: Кисловская [1п] и Нечаев [1']. — Перев.] Упражнения 8.1. Построить регистр сдвига с обратной связью, реализующий линейное:; рекурреитное соотношение зп+ь = за+а зп+з зп+ь+ зп и = О 1 над полем Еь. 8лк Построить регистр сдвига с обратной связью, реализующий линейное:, рекурреитное соотношение зп+т =выла» же+а+за+э+ пап+ 1, л = О, 1, кад полем 8.3.
Пусты — период периодической последовательности зь, з, „, н пусть на — наименьшее неотрицательное целое число„для которого выполняется равенство зп+,= зп при всех л > пь. Доказать, что ла совпадает с предпернодом последовательности за, зо .... 8,4. Определить порядок матрицы 0 0 0 — 1 1 0 0 1 0 1 0 1 0 0 ! — 1 нак элемента общей линейной группы И.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
