Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 130
Текст из файла (страница 130)
ПУсть [(х) = (х+ !)з (хз — х+ 1) Е й'з[х[. Найти значении, которые могут принимать минимальные периоды последовательностей нэ множества ([ (х)), а также число последовательностей, соответствующих каждому нз этих значений. 584 Гл. 8. Линейныс рекуррентные последовательности 8.49. Пусть 1'(х) = кз — 2х' хз 1 Б Кз (х(. Найти значения минимальных периодов, которые могут встречаться у последовательностей из множе. з ства 5 (1 (х)), а также число последовательностей, соответствующих каждому, из этих значений.
8.50. Найти нормированный многочлен 8 (х) с Кз (х), для которого 8 (х + 1) 5 (хз + х — 1) 5 (хт — х — 1) = 8 (я (х)). 8.51, Найти нормированный многочлен д (х) Р Ка (х), для которого Я (ха + х+ 1) 3 (х'+ х'+ 1) = 8 (д (х)). 8.52. Лла нечетных д найти ноРмиРованный многочлен 8 (х) с Ке (х), 1 такай, что 3 ((х . 1)э) 5 1(х — 1)е) — Б (8 (х)) с!то будет, если д четно? 8.53. Локазать, что ) м (88) = 11 М д) (1 У й), где 1, 8, й Б Кч (х) — мио.', гочлены, не являющиеся константами, прн условии, что сомножителн в правой, части приведенного выше равенства взаимно просты. 8.54. РассмотРим последовательность над полем Кз, поРожденнУю импУль-;,' сом и соответствующую линейному рекуррентному соотношению зн+, -- знез+7 + з„, и ==- О, 1, ., н линейную рекуррентную последовательность над тем же; полем, задаваемую рекуррентным соотношением зны =- з„, и — О, 1, ..., и век«' тором начального состояния (О, 1, 1, !).
На примере этих последовательностей,, показать, что аналог теоремы 8.59 для операции умножения последовательностей не справедлив. 8.55. Пусты Е И, ( Е Кч (х], бей 1)) > О, и пусть пг (1) обозначает сумму' г-х степеней различных корней многочлена 1 (х). Доказать, что для многочленов ), я Б Кч(х), не являющихся константами, справедливо равенство и, (1 ч 8) =. о, 11) о, (д) при условии, что число различных корней многочлеиа 1 Ч я рав-' няется произведению числа различных корней многочлена 1 и числа различных ' корней многочлена 8. 8.56.
Пусть з„, з,, ... произвольная последовательность элементов поля, (Гч, н пусть н з О, г ) 1 -- пелые числа. Доказать, что если ганкелевы определители Пгг) э и 7)ч' равны О, то и ()~~~1! =- О. 8.57. Доказать, что последовательность з„, з,, ...
над полем (Г4 является ' однородной линейной ренуррентной последовательностью с минимальйым много- ' членом степени и тогда и только тогда. когда ()1, + 1 = 0 для всех н)0 н Д + 1 является наименьшим натуральным числом, для которого это выполняется. 8.58. Получить полное доказательство второго неравенства в формуле (8.23). 8.59. Локазать неравенства из формулы (8.24). 8.60. Дать полное доказательство формулы (8.26). 8.61.
Локазать формулу (8.27). 8.62. Г!усть первые 10 членов однородной линейной рекуррентной после- ,' довательности над полем Ка порядка й ( 5 равны соответственно ' О, 1, 1, О, О, О, О, 1, 1, 1. С помощью алгоритма Берлекэмпа — Месси найти „! минимальный многочлен этой последовательности. 8 63. Пусть первые 8 членов однородной линейной рекуррентной последо- '1 вательности над полем К, порядка й < 4 равны ссютветственно 2, 1, О, 1, — 2, О, ! — 2, —. 1.
С помощью алгоритма Берлскэмпа — Месси найти миинмзльиый мною- ч член этой последовательности. 8.64. Пусть первые 10 членов однородной линейной рекуррентной после- ~ довательности над полем Кз порядка й ( 5 равны соответственно 1, — 1, О, '. --1, О, О, О, О, 1, О. С помощью алгоритма Берлекэмпа — Месси найти мини- .;" мальный многочлен этой последовательности.
8.85. Найти однородную линейную рекуррентную последовательность наи- ! меныпего порядка над полем у „, первые 10 членов которой равны соответственно 1 2,0,— 1,— 2,0,0,— 2,2, .1,— 2. Упражнения 8.66. Пусть выполняются условия теоремы 8.78, и пусть, кроме того, характеристический многочлен !'(х) последовательности з„, з,, ... удовлетворяет условию ((О) Ф О. Доказать следующую формулу, являющуюся усилением (8.31): и-1-г — ! )((з„) ( ( — ) (д~ — г)ыз для всех и~О. Чч И 1 о(о» вЂ” 1) Х е 1а! ~! 8.70. Из результата, полученного в упр.
8.69, вывести неравенство г (О; У,, У)— + '"" '( —.'" —,-" ) ще еь =. 0 при Л = о — 1 и е» = 2!5 при Л ) 4 — 1. 8.71. Из результата, полученного в упр. 8.69, вывестн для Ь Ф 0 неравенство Я(Ь; У», У) — — ~(( — !опт+ — + ) 4! !г 2 У(Л вЂ” г) Х» ! з — б . Л ) ф(8)а(Ф, д)а(ф', ц) ф( ) ф( ) Р (сс) — 1 (Указание. Воспользоваться тем, что в (8.33) случай Ь =- О можно исключить.) 8.67. Пусть выполнены условия теоремы 8.84, и пусть число г является делителем числа (д» вЂ” 1)!(6 — 1). Пусть также (д~ — 1)!г н» будут взаимно просты.
Доказать, что Я (0) = (4~ ' — 1) г)(д~ — 1). 8.68. Пусть выполнены условия теоремы 8,84, и пусть л будет нечетным числом, а Л = (4» — 1)/2. Доказать, что в зтом случае в формуле (8.37) имеет место равенство. 8.66. Пусть выполнены условия теоремы 8.84, а 2(Ь; Уз, У) такое же, как в теореме 8.85. Доказать справедливосп следующего равенства: г !Ь; У, У) = — г (Ь) + У Г Глава 9 Прнлоткення конечных полей Одной из основных областей нрнложения конечных н является теория кодировании. Эта теория берет свое на' ' в знаменитой теореме Шеннона о кодировании. В ней у ждается, что существуют коды, применение которых нозвол передавать информацию с произвольно малой вероятн ошибки на скоростях. близких к пропускной способности кан ' Одной из целей алгебраической теории кодирования — тео' кодов, исправляющих ошибки, и кодов, обиаружива ошибки, — является поиск методов построения таких ко В течение двух последних десятилетий на развитие тео кодирования все больше и больше оказывают влияние та разделы абстрактной алгебры, как теория конечных полМ теория многочленов над конечными полями.
В частности, ва вехой и этом направлении явилось описание избыточных к с помощью миогочленов над полем Кч. 'Гот факт, что реги сдвига можно использовать для кодйрования и декодирова информации, позволяет установить связь теории кодирова с теорией линейных рекуррентных последовательностей. В н 2, носвященных алгебраической теории кодированкя, мы О ннчнмся обсуждением основных свойств блочных кодов, Н средственно связанных с конечными полями, и не будем каса задач технической реалнзацик того или иного кода. ч 3 содержит некоторые результаты, касающиеся примене теории конечных нолей в геометрии, а именно для нсследова аффинных н нроектнвных плоскостей, содержащих конечное ч ..
точек н прямых. 5 4 посвящен комбинаторнке н содержит разнообразные н ложення конечных полей в этой области, особенно н задачах нировання экспериментов. В последнем, питом параграфе мы приведем определ линейной модулярной системы н покажем, как теория конечн полей иснользуется в теории линейных модулярных си Под системой можно понимать некоторое устроиство, в кото в определенные моменты времени что-то поступает (иаярим материи, энергия, информация) и которое само в онределен, моменты времени что-то выдает. Например, мы можем иагля !.
ЛННРЙНЫР ХОДЫ нрс!.тавлять себе некоторую систему как электрическую сеть н к,аОРУю постУпает электРнческий сигнал, а выходом Явлаютс! сныцие показания приборов. Систему можно также представлят* Виде сети переключательных элементов, входом которой яв !не!НЯ устаиОВка Входных )шреклЗОчателей, а ВыходОМ вЂ” кОн рш!пя горящих сигнальных лампочек. (! т!!,! особо подчеркиваем, что приводимые ниже приложенп« ,-.„!нпся лишь для того, чтобы привести примеры использовани! !',.! бра х свойств конечньх 'й Поз у 'и при ер! ка, !«мся скорее алгебраических и комбппаторпых аспектов прн дожсиий конечных Волен и оставляют в стороне вопросы практи «еского использования. Так.
например. Мы не будем обсуждать за «нчи анализа экспериментальных данных или вопросы анализа н г шгеза линейных модулярных систем, не будем мы также ка ыпы н тех свойств геометрических конструкций, которые непо средственно не связаны с конечными полями. 5 1. Линейные коды большое значение в настоящее время приобрели проблемы передачи информации п, в частности, вопросы кодирования лексо!Нрования информации в целях ее надежной передачи по -шп! умленным» каналам. Обычно бывает необходимо передать с!юбп!Рш!е, состояп!ее из конечной последовательности символов, нвлшшцпхся элементами некоторого конечного алфавита.
Если, например, этот алфавит состоит из символов О и Е то передаваемое РРн!б!щение можно рассматривать как некоторое двоичное шсло. В общем случае предполагается, что алфавит является некоторым конечным полем. Передача конечной последователь. ности элементов алфавита по каналу связи не обязательно осу. н!Рстн«!!!ется в «точном» виде в том смысле, что каждый бнт инфор«!Винп передается по каналу не изменяясь.
Ввиду того что пе сущссгнугт идеального канала без «шумов», получатель передаваемого сообщения может получить искаженную информацию и ш!шбшшо истолковать переданные сип!алы. г!шюй из основных задач теории кодирования является стрем л!Нше к тому, чтобы Вероятность ошибок. появляющихся в ре. зу«!ьтате шума в канале свнзи, была сведена к минимуму. Методы !'Оаьш!сипя надежности передачи сообщений в основном базиРун!тсн па свойствах конечных полей. гдчювной идеей алгебраической теории кодирования иване!'сч передача избьипочной информации вместе с тем сообщением, и"тонне необходимо передать.
Это означает, что последователь- носзР символов, составляющая передаваемое сообщение, !гекоторы' гннпнальным образом преобразуется в более длинную после- Донн гельность. Гл. 9, !!риложеиия коиечимх полей Простая модель системы связи изображена на рис. 9,! а сзе Рис. 9. ! предполагаем, что символы, составляющие исходное сообщен и символы, составлягощие закодированное сообщение, явля элементами одного н того же конечного полн ~Кч.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
