Введение в прикладную комбинаторику, Кофман А. (984071), страница 53
Текст из файла (страница 53)
Исходя из одного из этих определений, можно определить поле непосредственно. Элементы поля (Е,е, .) удовлетворяют следующим аксиомам. 432 сз) Существует аддитивная коммутативная группа (Е, о), а именно: для всех, х, у, г ~ Е (30ев Е)х *0=0 *х =х, (3х ~ Е) х о х = х з х = О, (х о у) з и = х * (у * г), х* п=у*х. (А4.5) (А4.6) (А4.7) по отношению (х о у) о г = (х о и) * (у о г), (А4.8) г о (х о у) = (г о х) * (г а у), (А4.9) Если мультипликативная группа коммутативна, т. е. Хоу=уах, (А4.10) то поле называется коммутативнсам *) и обозначается (Е, +, ), Например, множество Е = (О, 1, а, Ь, с) с законами композиции «+» и «», как на рис.
524, образует поле. Рис. 524. Множества 1.1 (рациональных чисел), К (действительных чисел), С (комплексных чисел) образуют (коммутатнвные) поля относительно обычного сложения и умножения. Характеристика поля. Характеристика поля (Е, о, а ) — это характеристика соответствующего ему кольца. Характеристика поля может быть как нулевой (как в случае б), К н С), так и *) В математической литературе в Советском Союзе часто называют полем только коммутативное поле, некоммутатпвные же поля называют телами. (Приза ред.) ()) Существует мультнпликативная группа Ео — — Š— (О,', такая, что для всех х, у, ген Ез (Б1 е:- Е,) х о 1 = 1 о х = х, (:-1х ' ~ Ез) х ' о х = х о х ' = 1, (Хоу)ох=хо (уог), у) Умножение дистрибутнвно слева и справа к сложению: (А4.1) (А4.2) (А4.3) (А4.4) (Е,, о), где положительной, в последнем случае она необходимо будет про- стым числом.
Действительно, если п=рд, где и, р, дев 1Ч, п о е = (рд) о е = (ре) о (ее), (ре) о(ее) =О, (А4.11) то (А4.12) т. е. (А4.13) что невозможно, так как поле не имеет собственных делителей нуля '). Очевидно, что кольпо Х7п (и простое) есть коммутатив- ное поле характеристики п. Рис. 525. Поля Галуа характеристики р. Коммутатнвное поле Х7р (р простое) является полем Галуа характеристики р, т. е. оно является кольцом классов вычетов по простому модулю. На х' Рис.
527. рис. 525 †5 представлены поля Галуа характеристик 2, 3, б соответственно. В дальнейшем мы будем интересоваться исключительно полем Галуа с характеристикой 2, которое называют часто «алгеброй по модулю 2». ') Это означает, что для всех х,у св Е если х у = О, то (х ~ О оу = О) или (уФ О =ф х = О). 434 ,Б У: а / Рис. 526. УПРАЖНЕНИЯ А4.А.
Пусть Š— множество пар (х,у), х,у ем 0 (множество рациоиальнык чисел) со следуюцсими законами композиции: для всех (хо уг), (х», уз) ~ Е (х„у,) * (хл, ул) = (х, + у„х, + уа), (х,, уг) (х,, уз) = (хгхз + у1уг, хгуз + х,у1), где «+» и « » — соответственно обычное сложение и умножение.
Показать, что (Е, е, ) — поле. А4.Б. Составить таблицы сложения и умножения элементов поля Галуа характеристики 7. А4.В. Показать, что операции в Е = (..., — 1, О, 1, ...), определяемые свойствами «четный» или «нечетиый» соответственно, образуют поле Галуа с характеристикой 2. А5. Алгебра по модулю 2 Не следует смешивать алгебру по модулю 2 с двухэлементной булевой алгеброй, хотя обе они связаны с множеством (О, 1).
Булеза алгебра Алгебра ае малулю 3 Отличие их состоит в том, что 1 + 1 = 1 (булева алгебра), (А5.!) ! + 1=0 (алгебра по модулю 2). (А5.2) Сравним эти алгебры. В двухэлементной булевой алгебре если а=1, то а=О, несли а=О, топ=1; в алгебре по модулю 2 если а = 1, то а = О, если а = О, то а = 1.
Имеем а+а=! и па=О, (А5.3) а+а=1 и па=О. (А5.4) Далее, а=1+а. (А5.5) а+Ь=а+Ь+аЬ, (А5.6) аЬ = 1+ а+ Ь+ аЬ, (А5.7) а+ Б = 1+аЬ, (А5.8) аЬ+аЬ = 1+ а+ Ь, (А5.9) а+ Ь=1+ а+ аЬ. (А.5.10) Следовательно, чтобы перейти от формулы в двухэлементной булевой алгебре и формуле в алгебре по модулю 2 и обратно, 435 достаточно выразить операции -+ и + друг через друга, используя формулы а+Ь=а+Ь+аЬ, (А5.11) а+ Ь=аЬ+ аЬ. (А5.12) Заметим, что операция + есть не что иное, как операция (9 (дизъюнктивная сумма), хорошо известная в булевой алгебре: а9Ь=аЬ+ аЬ ').
(А5.! 3) Следовательно, можно не различать символы Я и +. Переход от булевых формул к формулам по модулю 2 не всегда прост: Нельзя составить таблицу истинности для функции, определяемой в алгебре по модулю 2; эта таблица имеет смысл только в двухэлементной булевой алгебре. Алгебра полиномов в Х/2. Лем ми. Пусть [* (г) = ае + а,г + ... + а„г" (А5Л6) — полинам степени п, где ген [О, 1], с коэффициентами из 2/2. Существует такое поле К, содержащее 772, что все корни )'(г) принадлежат К. Если а †коре полинома ] (г) = а, + а,г + ... + а„г", (А5.17) то )'(а)=а,+а,а+ ...
+а„а"=0 (а„=1). (А5.18) Выразим а" и аа ы через а, аз, ..., а"-': а"=а,+а,а+ ... +а„,а" ', а" г' = а а + а а'+ ... + а„за" ' + а„,а" = = аеа + а,а' + ... + ал яач-' + ая ,[ае + ага + ... + а„ ,а"-']. (А5.20) (Ао.! 9) ') Напомним, что операциям 0 и + в двухзначной логике соответствует неисключающее «или», в то время как операциям гт) нля + соответствуег исключающее «или» (либо один, либо другой, но не оба вместе). а + Ь + с = (а + Ь) + с = (а + Ь + а Ь) + с + (а + Ь + аЬ) с = = а + Ь+ с + аЬ + Ьс + са + аЬс, (А5.14) а + Ь + с = (а + Ь) + с = (аЬ + аЬ) с + (аЬ + аЬ) с = = аЬс + аЬс .+ аЬс +. аЬс.
(А5.15) Следовательно, все степени а линейно выражаются через первые и степеней а', а',..., а"-'. а'=~р,(а", а', ..., а' '), 1=0, 1, 2, ... (А5.21) Так как таких функций самое большее 2" — 1, то и число различных степеней а не превосходит 2" — 1. Последовательность этих степеней периодическая с периодом д(2" — 1, (А5.22) т. е. а', а', а', ..., ае ', ач=а", а', а'-, ... (А5.23) Действительно, так как среди 2" первых степеней по крайней мере две совпадают, то существуют такие г и г', что а'= а', т. е, а' '=1. (А5.24) Пусть о — наименшпее число, для которого а4=1. Тогда а'=а', где з' — остаток от деления з на д: з=йд+з', (А5.25 а'=а"а"= а*.
А5.26 ) ( ) Корни а' и а' периодически повторяются (с периодом о): з+1=йо+з'+1, (А5.27) з+ о= й'о+ з'. (А5.28) Обозначим через а~ корни 1'(г). Так как они содержатся среди д различных степеней а, то 1'(г) =(г+ ао) (г+ а,) ... (г+ а„,). (А5,29) Рассмотрим полипом Н (г) = ге + 1. (А5.30) Его можно представить в виде Н (г) = (г + 1) (г + а) (г + ах) (г + ач ') = =(г+аэ)(г+а,) ... (г,+а„,)(г+а„) ... (г+а,,) (А5,31) или (А5.33) 437 Н (г) 1'(г) %'(г), (А5,32) где %'(г) — полином с коэффициентами из К. Более того, из (А5.32) следует, что коэффициенты 27(г) принадлежат Х~2, Теперь мы в состоянии сформулировать основную теорему Галуа.
Т е о р е м а Г а л у а. Для любого полинома 1*(г) степени и найдутся такой полинам $'(г) и число о, что 7" (г) Ж (г) = 1+ гт, а -~ 2" — 1 Рассмотрим несколько свойств. 1) Если 1*(г) таков, что в = 2" — 1, то говорят, что 1'(г)— примитивнв4й полинам, а У(г) дополнительный к )*(г). 2) Примитивный полипом 1*(г) неприводим.
3) Корень Ь примитивного полннома 1*(г) степени п называют примитивным элементом; остальными корнями 1*(г) будут Ь2 Ь4 Ь2з 4) Все корни примитивного полинома )*(г) различны. П р и м е р. Пусть 4"( ) з+ ф1 (А5.34) и а — его корень. Все различные степени а: аз=1 а', аз, а'=а+1, а'=аз+а, аз=а'+аз= =1+а+а', а'=а+ аз+а'=! +а' а'=а+ аз=! (А535) Имеем (гз+ г + 1) (г4+ г'+ г+ 1) = г" + 1 (А5,36) 1'(г) =г'+ г+ 1=(г+ а) (г+ аз)(г+аз), (А5.37) Ж(г) =г'+г'+г+1=(г+а')(г+а')(г+аз)(г+а') = =(г+ 1) (гз+ гз+ 1) (А5 38) Полинам ге+ г+1 также примитивный, так как Ьз Ьз+1 Ь4 Ьз ( Ь+1 Ьз Ь+ Ьз Ьз+Ь Ьз (А5.39) ПРИЛОЖЕНИЕ Б КОДИРОВАНИЕ.
КОДЪ|, ОБНАРУЖИВАЮЩИЕ ОШИБКИ Б1. Введение Ввиду большого значения теории кодирования для многих комбинаторных задач автору показалось целесообразным включить в настоящую книгу приложение, посвященное этой теории. В этом автору содействовал Ж. Кульман, и настоящее приложение может рассматриваться как краткое резюме его книги «Коды, обнаруживающие и исправляющие ошибки» (О. С ц11- ш а п п, Сос(ез с(е1ес1енгз е1 соггес1епгз д'еггепгз, Рппод, 1967).
В основном тексте книги мы намеренно не касались теоретико-вероятностных приложений комбинаторики, так как они широко освещаются в сочинениях по теории вероятностей, Здесь мы отступим от этого правила. Б2. Передача г-выборки Передача информации по линии связи осуществляется, как показано на схеме рис. 528. Источник информации уподобляется случайной величине 5, принимающей значения зь з,, ..., з„, составляющие «алфавит», с вероятностями рь рм..., ры р~+рс+ +...
+ рд = 1. Сообщение — это последовательность символов йроеннон Лонон Псреоап гон Н,П;--1 — ~---;П П онрсриацоо Рис. 528. (з„з,, ..., з„). При кодировании каждый символ источника заменяется последовательностью букв некоторого другого алфавита Х = (хь хм..., х;,..., х„), каждая нз которых определяет значение некоторого физического феномена, предназначенного для непосредственной передачи информации по линии связи. 439 Очевидно, что каждой х, можно в свою очередь приписать некоторую вероятность иь 1= 1, 2, ..., и.
Последовательность букв, соответствующая некоторому символу источника, называется кодовым словом. Прн декодировании осуществляется обратная операция с целью восстановления информации. Для правильной передачи информации необходимо, чтобы значения физического явления, соответствующие буквам алфавита, различались достаточно хорошо одно от другого.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
