Научная литература
booksshare.net -> Добавить материал -> Физика -> Лидл Р. -> "Конечные поля. Том 1" -> 233

Конечные поля. Том 1 - Лидл Р.

Лидл Р., Нидеррайтер Г. Конечные поля. Том 1 — М.: Мир, 1988. — 430 c.
ISBN 5-03-000065-8
Скачать (прямая ссылка): konechniepolya1988.djvu
Предыдущая << 1 .. 227 228 229 230 231 232 < 233 > 234 235 236 237 238 239 .. 371 >> Следующая

М0, Ы) обозначим число таких я, М0 п М0 + Ы - 1, для которых
sn = Ь.
8.85. Теорема. Пусть s0, sb ... - линейная рекуррентная
последовательность k-го порядка над полем fq, г - ее минимальный период,
a n(i - предпериод, и пусть число R выбрано так же, пак и в теореме 8.78.
Тогда для любого элемента b ? fq справедливо неравенство
АП Л 1.\ ( Т V/2"bJ9. ( 2 * ¦ 2 . N\
566
Гл. 8. Линейные рекуррентные последовательности
• /'
Доказательство. Используя обозначения и метод до к аз ат ель ства теоремы
8.82, нетрудно получить равенство
ад-_лг-1
Z(ft; JV" JV)-4- = 45]'х(*) ^ X(*")-
VI!
Ч
ч
%
я--А'в
J}f.
В силу того, что имеется ровно ^ - I нетривиальных аддитив*! ных
характеров поля F?. из теоремы 8,81 получаем
ЛГ.Ч-JV-1
X (sn)
Г \1/2
Я
Z(b\ NQt N) -
N
_1_
4
%
1
4
R
,k/2
logr
N
+ 7
"ЧГ
$
!s"*X
.
• v^i r • J
Kb
y;'4j
Ы
Метод доказательства теоремы 8.84 также может быть исполй зован для
исследования распределения элементов поля Fg и отрезках
последовательности, меиьших полного период (см. упр. 8.69, 8.70 и 8.71).
т
<v
/• !>*Г
Комментарии
т
¦д|
щ
§ !. Теория линейных рекуррентных последовательносте имеет очень давнюю
историю, В гл. 17 книги Диксона Dickson [40 она прослеживается с 1202 по
1918 г. Первоначально внимани уделялось линейным рекуррентным
последовательностям целы чисел, особенно знаменитой последовательности
Фибоначчи Р0, Fj F2, ... , определяемой условиями Рй = 0, F, ^ 1 и
соотношение!! рп^ = рп+Л ~r Fn, п ~ 0, 1, .... Позднее линейные
рекуррен'й ные последовательности над полем действительных или комплекс!
ных чисел рассматривались в основном в связи с исчислением конечных
разностей. Интерес к линейным рекуррентным после довательностям над
конечными полями возник после того, как! линейные рекуррентные
последовательности над Z стали рассматг ривать по модулю простого числа
р, получая таким образом ли* нейные рекуррентные последовательности над
полем Fp. Начинай с 50-х г. XX в., линейные рекуррентные
последовательности над конечными полями нашли важное приложение в теории
кодиро вання и в электронике ввиду их связи с переключательными схе мамн.
Краткий обзор истории развития этого направления за период с 1918 г.
можно найти в книге Selmer [3, ch. 21.
Важными классическими работами по теории линейных рекуррентных
последовательностей являются работы Lucas [11 й d'Ocagne [1 ]. Обзор этой
тематики можно также найти в книгах: Lucas [2, ch. 17, 18] и Bachman [5,
ch. 2]. Первый заметный; вклад в теорию линейных рекуррентных
последовательностей над конечными полями был сделан в статьях Mantel [1 ]
для слу
-до
щ
\L.
чуб
II
Комментарии
567
чаи простого поля IF,, и Scarp is 12] для общего случая FQ. Все
последующие работы вплоть до середины XX в. сконцентрированы вокруг
линейных рекуррентных последовательностей над кольцами Z и Z!(т) (см.
Bell U I, Carmichael U ], 12 ], 131, Engslrom [Ц, 12], Hall 11], [2],
[31, [4], Ward [2], [3], [4], [7], [81, [91, [ill, [(21. [14], [16] и
особенно фундаментальную работу Ward [5 |), Кроме того, линейные
рекуррентные последовательности над произвольными полями рассматривались
в работе Ward [1 ], а линейные рекуррентные последовательности над
произвольными коммутативными кольцами - в статьях Ward [13], 115].
Основополагающей работой по современной теории линейных ре-курреитных
последовательностей над конечными полями является работа Zierler [4 ].
Обсуждение этой теории можно найти в книгах Birkhoff, Bartee [1, ch. 13],
Dornhoff. Hohn [1, ch. 81. Gill [2]. Golomb, [4]. Luneburg, [2].
Peterson, Weldon, [1 ], а также в'лекциях Selrner [3 | и в обзорной
статье Fillmore, Marx [1 ]. По поводу более подробной информации о
последовательностях Фибоначчи см, Bachmann [5, ch. 21, Jarden [1 ], Knuth
[2, ch. 1 ] и Воробьев И ], а также журнал "Fibonacci Quarterly".
Линейные рекуррентные последовательности действительных или комплексных
чисел исследовались, в частности, в книгах Jordan Ch. [1, ch. Ill, Milne-
Thomson [1, ch. 131, Montel [11, Norlund [1, ch. 10], Гель-фоид [1, гл.
5] и Маркушевич [1].
Описание технической реализации регистров сдвига с обрат-иой связью и
составляющих их элементов приводится в работе McCluskey [1 ]. В статье
Roth [1 ] обсуждается эффективное построение регистров сдвига с обратной
связью с полем в качестве основного поля. Связь между регистрами сдвига с
обратной связью и линейными рекуррентными последовательностями
подчеркивается в работах Golomb [4]. Peterson, Weldon [1 ] и Selmer [3 ].
Обсуждение работы регистра сдвига с обратной связью с точки зрения теории
переключательных схем и теории конечных автоматов можно найти в книгах
Booth [1, ch. 8], Gill [21. Golomb 14, ch, 2|, Zadeh, Polak [1, ch. 21. а
с еще более общей точки зрения - в § 5 гл. 9 настоящей монографии.
Теорема 8.7 в сущности была получена в работе Mantel И 1. Георема 8.11
является частным случаем результата, доказанного в статье Ward [15].
Предыдущая << 1 .. 227 228 229 230 231 232 < 233 > 234 235 236 237 238 239 .. 371 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed