С.И. Гуров, Д.А. Кропотов - Конспект лекций по курсу Прикладная алгебра (1127136), страница 10
Текст из файла (страница 10)
(х-аР ) . х- аРгде а- произвольный корень•2·... ·g(x)вn -1х- аР'F;не имеет корней ни в каком конечном поле, содержащим менее, чемpnэлементов .3. Рассмотрим поле 1Fз[x]l(g(x)) расширения мно2гочленаg( х) == х + 2х + 2.В этом поле если а- кореньg(x),то и аз- тожеего корень. В ычисляем :2а == - 2а - 2 == а+ 1,2аз ==а (а + 1) == а +а == 2а + 1Построенное поле [F з [х]найденный ранее корень1(х2+ 2х + 2) - содержит2, поэтому многочлен f(x)Глава1062. Конечные поляв этом поле раскладывается на следу1ощие линейныемножители :f (х) ==хз + х + 2 == (х - 2) ( х - а) (х - 2а - 1)== (х + 1)(х + 2а)(х +а+ 2) .4. Определить корни многочлена g(x)2а)(х - 2а - 1) в поле 1Fз[х]/ (х + 2х + 2)всегдааз==можно2а + 1==взятьах,(х-легко :откуда второйкорень2х + 1.Ответ: многочлен f (х) == хз + х + 2 имеет корни222, х, 2х + 1 в поле 1Fз[х]/(х + 2х + 2) == GF(3 ) .Задача2.24.
Haumu4IF2/(x + х + 1)..м . .м. дл.я всех эле.меrнтовпол.я(3Решение.(3 == 0: mo(x) == х .(3 == 1: m 1 (x) == х + 1.(3 == а : сопряжённые с а элементы - а 2 , а4 , а 8 иma(x)248== (х- а)(х- а )(х- а )(х- а ) ==4== х +х+ 1.6(3 == аз : сопряжённые с аз элементы суть а а''249а == а , их м . м. таз (х)==6(х - аз) (х- а ) (х - а ) (х - а )==912==х4+ (аз+аб+аg+а12) хз++ (азаб + азаg + аза12 + а6а9 + аба12+122. 7.(IIIпоток) Конечные поля107+ aga12) х2+ (аза6а9 + аза6а12 + азаgа12 + a6a9al2) х++ (азаб а9а12 )х4 + (аз + (аз+ а2) +(аз+ а)+=232+ (аз + а + а + 1)) х + ( ...
) х + ( ... ) х + аза =4х + хз + х + х + 1.=/325= а : единственный сопряжённый с а5элемент -а 10 (т. к. а 20 = а 5 ), их м.м. -mas(x)/35(х- а )(х- а ) = х=7а : сопряжённые с=а28 = аlз' а56 =ma1(x)10=а72+ х + 1.элементы -all' их м.м . 711114(х- а )(х- а )(х- а з)(х- а ) =4х + хз + 1.=Задачат(х)Haumu..,.миrни.малъrнъtи.М'НО20"-lЛе'Нrк;omopыu имеет rк;ореrнъ аз) где а -Епри.митивrныu эле.меrнт пол.яРешение .1. Известно ,m(x)вполечтоминим альныйхарактеристики5вместенемазсодержитвсесопряжённые23( аз)s = al5, ( аз)5 = а75, (аз)s = аЗ75 и т.д.2.
В поле F52будет а -1=ам ногочлен24= 1сс::::}15корнимсо-пряжённым с аз будет только элемент а(т. к .а 75 = а 24 ·З+З = аз). Поэтому минимальный многочленГлава1082. Конечные поляимеет степень 2 класс, образованный аз содер15жит только два элемента аз и а :m(x)1521518m(x) = (х- аз)(х- а ) = х - (аз+ а )х + а .3. Найдём коэффициенты многочлена m(x) учётома 2 = - а - 2= 4а + 3:22аз = а · а = а(4а + 3) = 4а +За == 4(4а + З) +За = 4а + 2,а15= (аз)5= (4а + 2)5= 4а + 2 =52= 4а аз+2 = 4(4а+З)(4а+2)+2 =2= 4(а +1)+2 = 4(4а+4)+2 = а+З,аз+ аа1815= 4а + 2 +а+ З = О ,= аза15= (4а + 2)(а + З) == 4(4а + З) + 4а + 1 = З.Ответ:m(x)= х2+ З.Задание: убедитесь, что хполя-примитивный элементF.Задача2.26 . H aumuк;ор'Нu м'Ногочл е'На2f(x) = хз + Зх + 4х + 4 Е lF5[x] .Решение.х ЕВычисляемзначенияf(x)дляG F(5) = {О , 1, 2, З , 4 }:j(O) = 4, j(1) = 2, f(2) = 1,Таким образом , х = 3 - корень f(x).Деля <<уголком >> f(x) на f 1 (x) =2j(З) = О.х- З (или на2х+2) , получи м хз+3х +4х+4 = (х-З) · (х +х+2).2.
7.поток) Конечные поля(IIIПеребором элементовf 2 (x) ==Вх109ЕубеждаемсяGF(5)2х + х + 2 - неприводимый многочлен .2поле lr 5 [х] / (х + х + 2)корни многочлена5суть { х, х } и хf 2 (x) == 02== -х-2 == 4х+3.Вычисляем:5222х == (х ) х == х(4х + 3) == х(х + 4х + 4) ==22== х( 4х + 3 + 4х + 4) == х(3х + 2) == 3х + 2х== 2х + 4 + 2х == 4х + 4.Ответ: { 3, х, 4х + 4 }.Задача2.27.Явл.яетс.я ли М'Ного'l~ле'Нпримитив'Ным?Решение .О,... , 4Подстановкойполяlr5вf(x)всехэлементовубеждаемся, что данный многочлен2-й степени не имеет линейных делителей и, следовательно, неприводим.Порядок мультипликативной группы GF(5 2 ) есть25 - 1 == 24 == 23 · 3.
Определим порядок элемента её х ,2для которого х == - х - 2 == 4х + 3.Поскольку простые делителирим равенствоxd== 1 для d ЕИмеем:х == (х )222{ 224суть2и3, прове== 12,243== 8} .== (4х + 3) == х + 4х + 4 == .... . . == 3х + 2 -/= 1,4 2228х ==(х ) == (3х + 2) == -х + 2х + 4 == ...4224Глава110х12. . . == Зх + 1 =1= 1.8 4==х х == (Зх + 1) (Зх + 2). .
. == 4=/= 1.2. Конечные поля-х2+ 4х + 2ord х == 24 и рассматриваемый2член примитивен в поле lr 5 [х] / ( х + х + 2) .Следовательно• • •много3.1 . (IIIпоток) Коды, исправляrощие ошибкиГлава1113Коды, исправляющиеошибки3.1Блоковое кодирование. Коды ХэммингаЗадача помехоустойчивого кодирования.По каналу с шумом проходит поток битавой инфор мации(или хранимая информация искажается) , вследствиечего возникают ошибки.•Модель ошибок: биты случайно, независимо и сравнымивероятностямитированнымимогутоказатьсяинв ер( двоичнъtй симметричный rк;анал),вставки/выпадения битов нет.•Задача: обеспечить автоматическое испр авлениеошибок .Подход к решениiо (один из возможных ! ) :1)входной поток информации разбить на сообщ ения-длины2)непересека1ощиеся блоки фиксированнойk;каждый блок rк;одироватъ (модифицировать)а) независимо от других--блоrк;овое rк;одиро вание;б) в зависимости от предыдущих-свёрточноеили потоrк;овое rк;одирование (турбо-коды и др.).11 2 IIIпоток: Глава3.Коды, исправляrощие ошибкиДалее рассматривается искл}очительно блоковое кодирование :• есть набор всех сообщении sl ' ...
' St, ДЛИНЫ kкаждоекоторые нужно передать по ка(t == 2k),налу связи с шумом;•дляобеспеченияпомехозащишённостивместоэтих сообщений переда}ОТ к;одовые слова, каждоедлиныn > k, т. е .вводят избъtточностъ п ри п ередаче информации .Более формально :к;од-инъективное отображениеер : {О,1 } k ~ {О , 1 } n, k < n;к;одовые словаС- область значений== I т ерС { О,1 } n кода.Ч ем меньше избыточность т== n - kи чем большечисло ошибок , которые может исправить код , тем онлучше.Ясно, что эти требования противоречат друг другу и••одн о дости гается за счет другого .Понятия, связанные с булевым кубом-н апоминание из дискретной математики .•Нор.маj;=yборе ;у Е вп.число единичных координат в на-3.1 .
(III•поток) Коды, исправляrощие ошибкиМетри'К;а (вспоминаем, что это такое) на множестве бинарных наборов( Е9 - сумма по mod 2) :хэммипгово рассто.япиеf3Р а,•113Шар Хэммипга с чептром в а и радиусомSr (а) =(3Е Впr > 0:•Ричард Уэсли Хэ.м.ми'l-tг(Rich ard Wesley Ha m1ning, 1915- 1998)- амер иканский математик, р аботыкоторого в сфере теории информацииоказали существенное влияние накомпы{)терные науки ителекоммуникации.В1950г. опубликовал способ построения кода,испр авля1ощего одну ошибку и названныйвпоследствии его именем.Кодовое расстояниеОпр еделениевами кода3.1. Минимальное расстояние между слоСн азывается его 'К;Одовым рассто.япием,символическиd.Утве ж ение3.1.Мпо ;нсествоправлением не менееrСобразует 'К;О д с ис ошибо'К;, если11 4 IIIпоток: Глава3.Коды, исправляrощие ошибкиДоказа тельство .
Если при передаче сообщения а сделано не более r ошибок , то набор останется в тлареSr (а) .Если шары не пересека1отся, то искомое кодовое словоа-ближайшее к полученному набору.Сле ствие. У к;ода, исправляющегорасстояни е дола+Сно бъtm/ь не .менееr ошибоrк;,2r + 1.оrк;одовоеОпределение кодового расстояния произвольногакода С-трудоёмкая задача : требуется перебрать все2k(2k -l )пар кодовых2уже с k ~50 .П оэтомуприслов, что практически невозможнопомехоустойчивомкодированиинапервый план выходит проблема построения кодов с заданным кодовым расстоянием.
Она решается при и спользовании, например , т. н. БЧХ-кодов, которые будутрассмотрены далее .Блоковое кодирование и декодированиеВл ок;овое rк;одирование-взаимно- однозначное преобразование сообщений длиныны nkв кодовые слова дли> k.Деrкодировапи е- определение сообщения по принятому слову.Пример3.1 (тривиальный код с повторением k ~ 1,n ~ 3, d ~ 3) .
Информация разбивается на блоки поодному биту (т.е . длины k ~ 1 и передаются t ~ 2сообщения: 8 0 ~ О и S 1 ~ 1).КодированиеО 1--t 000, 1 1--t 111исправляет одну ошибку. Однако такое кодированиекрайне неэффективно : длина сообщения утраивается.3.1 . (III поток) Коды, исправляrощие ошибки11 5Tpuв uaJ//b'I-1/ЫU х;од-повторение а 1-----t ~ ••• ~ исправляетV'2r+lr ошибок.Блоковое кодирование.Б удем обозначать каждоесообщение вектором-столбцом и Е {0, 1}k:и• • •Определение• v -3.2.кодовое слово длиныпомимоknk + т,~содержащееинформачион'!-l'ЫХ ещё и т проверочных бит (раз делимое блох;овое х;одирование).• Множество {v1 , ...
, Vt} всех t ~ 2k кодовыхСЛОВ ДЛИНЫ n - (n, k) -х;од, ИЛИ, С КОДОВЫМ расСТОЯНИеМ - (n, k, d) - х;од.• R~kjn-сх;оростъ, тjn ~ 1 -избыточR-ност ъ к; ода.Блоковое кодирование (отображение S---+С) всегда может быть осуществлено с использованием таблицы размера 2k xn. Однако такое <<табличное>> кодирование весьма неэффективно: значенияnиkмогутдостигать десятков и сотен тысяч .При передаче по каналу с шумом кодовое словопревращается в принятое словоv ---+ w~vwтой же длины+ е,n:v116 IIIпоток : Главагде е Е{0, 1}n - веrк;тор ошибок; :(п,3.Коды, исправляrощие ошибки1,если в i-ом бите произошла ошибка .О,если о шибки нет .k, d)-код исправляет не менееl (d- 1) / 2 J ошибок .Декодирование кодов обычно значительно сложнее1кодирования .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
