С.И. Гуров, Д.А. Кропотов - Конспект лекций по курсу Прикладная алгебра (1127136), страница 17
Текст из файла (страница 17)
Итак , данный полином локаторов ошибок имееткорни а58и а .Определяем позиции ошибок:3.8.поток) Коды, исправляrощие ошибки(III-5-810,15 7,15(и полином ошибок есть е( х) ~ х 10Задача181+ х 7 ).Построитъ 31-разр.ядныu Б ЧХ- 'Х;од дл.я ис3.6.правления не менееr~3ошибо'Х;.Решение . Имеем n ~ 31 ~ 25 - 1, q ~ 5, dc- 1 ~ 2r ~ 6.Порождающий многочленg(x)конструируемого2кода должен иметь корни а, а , аз, а , а , а , гдеа- примитивный элемент поля F ~ [F~ .Пр иразбиенииF*'''56на циклотомические классывсегда будет присутствовать{ а а2 а4 as а16 }'4пятиэлементный класс.Остальные рассматриваемые степени а будут вхо-дить в циклотомические классы6{ аз, а ,...
}5и { а ,... } .Н етрудно установить , что эти классы также будутпя тиэлементными:(т. к . 34(т. к.з1 3);36 -з1 5) .1Ранее з были приведены веприводимые многочлены5- йстепени над [F 2 : их шесть1) х135+ х + 1,см. с. З42-4) х542+ х + х + х + 1,182 III2) хпоток: Глава5+ хз + 1,523.Коды, исправляrощие ошибки5) х + х + хз + х + 1,3) х + хз + х + х + 1,545426) х + х + хз + х + 1.Во многих монографиях 14 есть соответствуi{)ЩИе таблицы .
Все эти многочлены, как указано в таблицах, являются примитивными (корень а==х - генератор мультипликативной группы соответствующего поля) и всеони могут быть выбраны в качестве порожда1ощего поле полинома а( х) .Положим а(х) == х 5 +х 3 + 1 (многочлен No2) и тогда15gQ(x) == а(х), а == аз+ 1, аз == 1.Определи м, какие из остальных многочленов соответствуют циклотомическим классам для а35и а .И меем :для многочленаNP 3 -(х5 + хз + х2 + х + 1) х=Qз == а15 + ag + а6 + аз + 1 ==4== (аз+ 1) з +а (аз + 1) +а (аз + 1) +аз + 1 == .
. . == О ,для многочленаNP 5 -(х5 + х4 + хз + х + 1)==x = Q5==а25 + а2о + al5 + а5 + 1(аз+ 1)5 + (аз+ 1)4 +(аз+ 1)з + а5 + 1== . . . ====О.Таким образом,gQз ( х)52== х + хз + х + х + 1,g Qs ( х)54== х + х + хз + х + 1и порождаi{)ЩИй многочлен для (31, 16, 7)-кода Б ЧХесть14 Например , Лидл Р.
, Нидерраuтер Г Конечные поля, Том1, Таблица С.(III поток) Коды, исправляrощие ошибки3.8.g(x)183== 9а(х)х15Зада ча+ х113.7.· 9аз (х) · 9as(x) ==+ х1о + xg + хв + х7 + xs + хз + х2 + х + 1,degg(x) ==т== 15, k == n- т== 16.Рассм отрим В ЧХ-под, Nули потарог о определ.я ютс.я стеnе'l-l.ями примитивNого элемеNта а пол.яF == !F 2 [х] / (х4+ х + 1) .Пустъ дл.я '1-lепоторого приN.ятого слова поли'l-lомлопаторав ошибоп естъ О"(х) == а 6 х+а15.Определитъ позиrции ошибоп в дa'J-l'l-toм слове.Решение . Для вычислений в полетаблица, выражающая элементыF нам понадобитсяF * в полиноми альнойформе и как степени примитивного элемента а.
Такая15таблица уже построенав начале раздела Существование и единственность поля15 см. с.71 и 177GF(pn) ив Задаче3.4.184 IIIпоток : ГлаваКоды, исправляrощие ошибки3.ааа2а2азаза4а+ 1asа +аабаз+ а2а7аз+ а+ 1авagа1о22а + 1аз +а2а +а+ 1all аз+ а 2 +аal2а1зal4a1s2аз+ а +а+ 12аз+ а + 1аз+ 11П еребором найдём корни полинома ошибок6CJ (x) == а х + а == (аз+ а )х + 1 :4CJ(a) ==а +аз+ 1152а+ 1 +аз #О;22254CJ(a ) == а + а + 1 == а +а+ а+ 1 + 1 == а# О;• • • • • •CJ( ag) == а12 + all + 1 ==22== (аз+ а +а+ 1) +(аз+ а +а)+ 1Линейный полином CJ(x) имеет один корень поэтому позиция единственной ошибки есть- 9==О.а9 , и15 6.4.1 . (IIIпоток) Теория перечислении ПойаГлава1854Теория перечисленияПой аДействие группы на множестве4.1• Группа•9(G, о, е), G=Множество Т ,Т=n.=N.- B ij(T) - множество всех биекций (перестановок) элементов Т.- Sym(T) -симметрическая группа множества Т:( B ij(T ), *, lт),Sym(T)Оп редел е н и е4 .1 ( 1) .а ЕHom ( 9 , Sym(T ) ).Дей ствие а группыски-9:9на множестве Т : символичеТ.аОпределение 4.2(11).а =(9 , Т,о, *,е, lтгдеоG --+ G -GхGх Т*--+Т-групповая операция;н овая операция.),186IIIпоток : ГлаваТеория перечисления Пойа4.Аксиомы для операций:• е* t ~ t·'• (g о h) * t~ hЗапись операцииАксиомы:e(t) ~* (g * t) .*: g(t)t и (g~1t •о h)(t)Т.
е . элементы g группыG~h(g(t)).порождаrот перестановки на Т , обладаrощие вышеуказанными свойствами .Ggеt"t'Рис.4. 1. Копределению действия группы на множествеДля данной перестановкиg:Введём отношение эквивалентностиtrv gРефлепсивrностъrv gна Тt {::} 3 k Е 1_ : gk (t) ~ t(R) , си.м.метричrностъ (S)1тивrностъ (Т) отношения-1rv gи траrнзилегко показывается.4.1 . (IIIпоток) Теория перечисления Пойа187Смежные классы эквивалентности 1"...) 9 называютсяg-чикла.ми : элементы этих классов образуFот циклы :~-тtt1~-т~t,-т•.•и у каждого элемента-по единственной входящей и исходящей стрелке .Обозначения :• ( v1, v2, ... ,g -VN )== Type(g) -тип перестановк;иупорядоченная совокупность количеств циклов: (количества циклов длины1, 2, .
. . , N соответственно);• C(g)-число всех g-циклов.NПонятно, чтоL==vk (g)С (g) иN.k=lПримерgТи== { 1, ... , 10 }1 2 3 4 5 6 7 8 9 109 6 1 8 5 2 7 10 3 4====4.1 . Пусть(1, 9, 3)(2, 6)(4, 8, 10)(5)(7) == (1, 9, 3)(2, 6)(4, 8, 10) .Туре (g)Тогда== ( 2, 1, 2,с (g) == 2 + 1 + 2 == 5'По всей группетО,==..., О )2 · 1+1 · 2+2 · 310.9:Отношение эквивалентности I"'Vg на Тtи1"...)9t1def ==:~==::J( )g :g t==-t.1GСвойства•(R), (S) и (Т) отношенияI"'Vg очевидны .Классы этой эквивалентности называют орбита ми; они образуют разбиение множества Т .188III•поток: Глава4.Теория перечисления ПойаКласс эквивалентности, в которую попадает элемент t обозначаемOrb (t).• Число получившихся орбит - C(Q).Если C(Q) == 1 (любой элемент Т может быть переведён в любой), то действие g : Т называют транзитива1-l'Ы.М.Фиксатор перестановки и стабилизатор элемента множества.Б удем реш ать уравнениеg(t) == t .При выполнении этого равенства можно фиксироватьлибо1.t,либо g.Фиксируемg,т.е .
находим все элементы множества Т, которые перестановкасте-g оставляет на меэто фиrх;сатор перестановrх;иgЕg:{ t Е Т g(t) == t} == Fix (g) ~ Т.2.Фиксируемкоторыеt,т. е. находим все перестановкиоставляют данныйэлементg,неподвижным- это стабилизатор элеме'Нта t Е Т :{ g Е G g(t) == t } == Stab (t) С G .Очевидно Vt Е Т : е Е Stab (t), т. е . Stab (t)-/=0 .Более того, стабилизатор есть подгруппа группыStab(t) ~ Q.Q:4.1.поток) Теория перечисления Пойа(IIIДоказательство.
Зафиксируемg, hЕStab (t). Тогда g(t)==Еth(t)189Т и р ассмотримt==и1h- (t)==t.Следовательно(g о h-1)*t==t*Поэтому стабилизаторg о h- Е Stab (t).1Dназывают ещё стаStab (t)цио?-lар?-lой подгруппой (или из отопичеспой подгруппой) элеме'l-lтаStab (t)t.будем также обозначатьGt.Утве ж ение 4.2. Пр и действии группыGна множе ство Т ме;.нсду мно :нсеством левых смеJfсных плассовGпо стационарной подгруппеего орбитойOrb (t)Gtэлемента t Е Т исуществует вз аимно однозначноесоответствие.Доказательство.
Левые смежные классызначаемgGt , gЕG , считаяGпоGtпри этом , что на элементыТ сначала действует некоторая перестановка иззатем-фиксированная перестановкаН о тогда л1обая перестановкаподействует навсе элементыtЕ Т:h(t)обо==hg(t)==Gt ,аg.ЕgGt одинаковоt' Е Orb (t) (т. к .Gt оставля1от t на месте) и утверждениедоказано .оИз этого утверждения вытекает важноеСле ствие. Длина орбитъtционарной подгруппыOrb (t)==Orb (t) paв'J-la индепсуStab (t) группъt Q:GStab (t)==[G : Stab (t)].ста190IIIпоток : Глава4.Теория перечисления ПойаДоказательство.
По теореме ЛагранжаН~ GG == Н · [ G: H J==?число смежн ых классов группыпо её подгруппеGН~ G равно индексу [ G: HJ.4.2~оЛемма Бёрнсайда4.1 ( « не-Бёрнсайда » ,C(Q) ==1GLили Коши-Фробениуса) .1Fix (g) =GLgEGStab (t) ;tETпервое рав енств о называется лемм ой В ёрнсаuда.Доказательство.
ПустьТ задаётсяg:nхG== п, !Т==Nи действиеN матрицей А == l9i(tj) , i == 1, п ,аj== 1,N.Подсчитаем двумяразличныминость множества М == {способами(g, t) Е G х Тg(t)мощ==t }:по столбцам и по строкам матрицы А. ПолучимLFix (g) == М ==LgEGStab (t) .tETЕсли х и у принадлежат одному классу эквивалентности по rvg , тоOrb (х)==Orb (у) и их стационарны е подгруппы имеiо т одинаковую мощность :Stab (х)GOrb (х)GOrb (у)Stab (у) .4.2.(IIIпоток) Теория перечисления ПойаВыберем по представителJоC(Q)Мt 1,...
, tc(Q)191из всехорбит. ТогдаC(Q)L==LStab (t)tETStab (ti) · Orb (ti)i=lIG . C(Q) .оПример4.2.Действие четверной группы Клейн амножестве Т == {наt1, . .. , t6 }:*tоеаьаЬееаьаЬеааеаЬьаььаЬеаьаЬаЬьаеаЬgtl t2 tзtl t2 tзt2 tl t4tз t4 tlt4 tз t2t4 t5 t6t4 t5 t6tз t6 t5t2 t5 t6tl t6 tsЬ:а:аЬV4:t3Туре (е)t4t6== (6, О , О, О, О, О) , Туре (а) == (О, 3, О , О , О , О) ,Туре(Ь) == (2, 2, О , О , О , О) ,Туре( аЬ) == (0, 3, О , О , О , О).С( е) == 6, С(а) == С(аЬ) == 3, С(Ь) == 4.Stab (t 1) == Stab (t2) == Stab (tз) == Stab (t4) == е ~ V4,192IIIFix (а)==поток: Глава4.Теория перечисления ПойаStab (ts) == Stab (tб) == (е, Ь) ~ V4 .Fix (аЬ) == е5, Fix (Ь) == {t5, t5}, Fix (е)==Т.44Orb (t 1) ==== 4,Orb (ts) ==== 2.1216+ 2Fix (g) ==== 2,-4 LgEtET4G4·1+2·2Stab (t) ==== 2.4Как применять лемму «не-Бёрнсайда?»Для определения числа классов эквив алентности н адопр едставитьотождествляемые элементы множеg :Тства Т как классы эквивалентности действиявекоторой группыопределитьЗадачаgана Т и по лемме БёрнсайдаC(Q).4.1 (про слова;решение прямым использованиемлеммы Бёрнсайда) .
Составл.яютс.я слова дли'Н/Ыиз алфавита Аl ~ 2== { а1, ... , aq }.Слова считаются эк;вивалептпы.ми, если опи получаются одпо из другого перестаповк;оu к;раuних бук;в.Определитъ числоSнеэк;вивал ептных слов.Решение. Т- множество слов дл иныТlв алфав ите А ,== N == ql.Надопредставитьэквивалентностив екоторого действия подходящей группыкакGорбитына Т .4.2.(IIIпоток) Теория перечисления Пойа193Очевидно, двукр атная перестановка не меняет ничего, И ПОЭТОМУ ПОДХОДИТ Уf:rv== { е, j } . ДейСТВИе71_2переставляет в слове крайние буквы .Число неэквивалентных словвалентности действия 71_2 : Т==число классов экви-аFix (е)==Т == ql ,21.q== ql== qz- .Fix (f)•2Для2GgEимеемl == 3, q == 2Пусть А==Т2== 8 иS =={ а, Ь} , тогда слова и классы -Ь аааЬааЬЬЬЬаЬаЬьььПлатоновы тела-6.(1)(2)(3)(4)(5)(6)аааааЬ4·32пр авильные 3- мерные м ногогранники .
Рассматриваем их группы вращений ( самосовмещений) .Платоновы телаГруппаПорядоквращенияг р уппытетраэдрТ (тетраэдра)куб и октаэдрО (октаэдра)икосаэдр и додекаэдрУ (икосаэдра)4 . 3 == 128 . 3 == 2412 . 5 == 60Икосаэдр имеет20гр ан ей ,30рёбер и12вершин.194IIIпоток : ГлаваОктаэдрТ-4.Теория перечисления ПойаИ косаэдрДодекаэдргруппа вращения тетраэдраТо32== ( t, f), t == f ==t -вращение на120°е, где:вокруг оси ,проходящей через вершину и центртетраэдра ( 6 - 6); таких осейf -вращение на180°4.вокруг оси ,проходящей через центры двух проотивоположных рёберосейт(D- D);таких3.== (3 - 1) .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
