У. Питерсон - Коды, исправляющие ошибки (1267328), страница 102
Текст из файла (страница 102)
Таблицы неприводимых многочленов над полем И" (2) В этом приложении даны таблицы, с помощью которых можно найти все неприводимые над полем 6Р(2) многочлены степени 16 или меньше. В таблицах указаны некоторые свойства этих много- членов и ссютношения между ними. Приводятся примитивные многочлены с минимальным числом ненулевых коэффициентов н многочлены, принадлежащие всем возможным показателям для каждой степени от 17 до 34. Многочлены даны в восьмеричном представлении.
Каждый символ в таблице обозначает три двоичных знака в соответствии со следующим кодом: 0 000 2 010 4 100 6 1!О 1 001 3 011 5 101 7 1!1 Двоичные знаки являются коэффициентами многочленов, коэффициенты высших порядков расположены слева.
Например, 3525 обозначает многочлен !О-й степени. В двоичной записи числу 3525 эквивалентно число 01110! 010101, и соответствующий много- член равен Х'о+ Хв+ Хз+ Ха+ Х'+ Ха+ 1. Двойственный многочлен нсприводимого многочлена также не- приводим, а двойственный многочлен примитивного многочлена примитивен.
Поэтому каждый раз в таблице приводится либо сам многочлен, либо двойственный многочлен. Каждая запись в таблице, оканчивающаяся некоторой буквой, соответствует некоторому неразложимому многочлену указанной степени. Для степеней от 2 до 16 этими многочленами, а также двойственными к ним исчерпываются все неразложимые многочлены этих степеней. Буквы, которые приведены после восьмеричного представления многочлепа, дают о нем следующую информацию: А, В, С. В Ненримитивный Е, Р, С, Н Примитивный А, В, Е, Р Корни линейно зависимы С, В, С, Н Корни линейно независимы А, С, Е, 0 Корни двойственного многочлена линейно зависимы В, В, Р, Н Корни двойственного многочлена линейно независимы Остальные числа в таблице характеризуют соотношения между многочленами.
Для каждой степени был выбран примитивный многочлеи с минимальным числом ненулевых коэффициентов, и этот многочлен стоит первым в таблице многочленов соответствующей степени. Пусть а обозначает один из его корней. Тогда запись в таблице, начинающаяся числом /, соответствует минимальному многочлену для корня а~. Эти многочлены включаются в таблицу для каждого значения /, если только не оказывается„что при некотором 1(/ или а' и а~ являются корнями одного и того же неразложимого многочлена, илн а~ и а — ! являются корнями одного и того же многочлена. Минимальный многочлен для а! включается в таблицу, даже если его степень меньше, чем степень, соответствующая данному разделу таблицы. В таком случае после многочлена не указывается буква.
Примеры. Первой записью в таблице неразложимых многочленов 6-й степени является примитивный многочлен (103), или Ха+' +Х+1 = р(Х). Если а — корень р(Х), то ссз — корень много- члена (127) и сгэ — корень многочлена (!47). Минимальным многочленом для сР является многочлен (015) = Хз + Хэ + 1, степень которого равна 3, т.
е. меньше 6. В таблице нет записи, соответствующей а'г. Другими корнями минимального многочлена для элемента ап являются ам, ем=аз, а'~, гР и гР. Таким образом, минимальный многочлен для а'т совпадает с минимальным многочленом для о', т. е. с многочленом (147). В таблице нет записи, соответствующей а'з. Другими корнями минимального многочлена р„(Х) для а" являются в ', сР, акч=в4', <Р=вм и гР. Ни один из этих корней не входит в таблицу. Корнями многочлена р*„(Х), двойственного к многочлену р„(Х), являются а и сР о.
и гР сс аз=он е-м сР в-м ем а м=а~. В качестве минимального многочлена для ап в таблице указан многочлен (155), или Хз + Хз+ Хз + Х'+ 1. Минимальным многочленом для ам является, таким образом, многочлеи, двойственный к этому многочлену„т. е. многочлен рж(Х)=Х~+Хэ+ + Хз + Х + 1. Показатель, к которому принадлежит многочлен, может быть найден следующим образом. Пусть а — примитивный элемент поля 6Г(2 ).
Тогда порядок е элемента а! задается равенством 2~ КОД(Я~ — 1, /) ' С другой стороны, порядок е равен показателю, к которому принадлежит минимальная функция для а~. Так, например, в поле бг" (2ю) элемент а" имеет порядок 93, так как 93 = 1023/НОД (1023, 55) = 1023/11. Таким образом, многочлен (3453) принадлежит показателю 93. С этой точки зрения полезна табл.
В.!. тавлица 8.1. Разложение 2 — ! иа простые сомиожители 2'6 — 1 = 524 287 266 1 ЗХ5ХЗХ!1ХЗ!Х41 21' 1 = 7Х7Х127Х337 211 — 1 = ЗХ23Х89Х683 1=7 1 =3Х5 1 =31 1 = ЗХЗХ7 26 21 26 Зе 266 211— 216 2'6— 1 =47Х178481 1 = ЗХЗХЗХ7Х1ЗХ17Х241 1= 31Х601Х180! 1 = ЗХ2731Х819! 1= 127 1 = ЗХ5Х17 1 = 7Х73 1 = ЗХ11ХЗ1 21 26 26 216 2гг 2гз 216 260 1 = 7Х73Х262657 1 = ЗХ5Х29Х43Х1!ЗХ127 1 = 23ЗХ 1103Х2089 1 = ЗХЗХ7Х11ХЗ!Х151Х331 1 = 23Х89 1 ЗХЗХ5Х7Х13 1 =8191 1 = ЗХ43Х 127 2и 216 2" 2'з 2зз— 2зз 2зз 2Я— 1 2 147 483 647 1 ЗХ5Х17Х257Х65 537 ! 7Х23Х89Х 599 479 1 = ЗХ43 691Х13! 071 1 = 7Х31Х 15! 1 = ЗХЗХ17Х257 1 = 131 071 1 = ЗХЗХЗХ7Х19Х73 2'з 216 211 2'з Марш [204) опубликовал таблицу всех неприводимых много- членов степени !9 или меньше над полем егг"(2). В этой таблице многочлены расположены в лексикографическом порядке.
Это наиболее удобный способ определения того, является ли данный многочлен неприводимым. Многочлены минимального веса в приводимой ниже таблице для степеней, не превосходящих !9, были найдены по таблицам Марша. Для степеней от 19 до 34 многочлены минимального веса были получены методом проб и ошибок, при котором рассматривался каждый многочлен веса 3, затем каждый многочлен веса 5 и т. д. Для того чтобы проверить, является ли многочлен 7(Х) степени лз примитивным, применяется следующая последовательность операций: !.
Находятся вычеты (, Х, Х', Х', ..., Х' -' по модулю 7(Х). 2. Этн вычеты умножаются и приводятся по модулю )(Х) для того, чтобы построить вычет Х' — !. Если результат отличается от 1, то многочлен отвергается. Если результат равен 1, то испытание продолжается. 3, Для каждого сомножителя и в разложении числа 2 — 1 вычет для Х" образуется перемножением подходящей комбинации вычетов, найденных на 1-м этапе. Если все эти вычеты не равны 1, то многочлен является примитивным.
Каждый из остальных многочленов в таблице был найден с использованием соотношений зависимости для его корней методом, лроиллюстрированным в конце разд. 8.!. Тавлнца В.Э. Неприводнмые мяогочлены степени, не превосходящей 36, над полем сгР (2) С)ЛЕПЕНЬ 2 Сщелень з С)леленб С)ЛЕЛЕиб 5 С)пелене ь 1! 155Е Рпепень т 11 325б Э 370 3 750 3 1278 5 07 5 67Н 5 1ЯТН 9 015 7 1!)Д 7 367Н 3 217Е 19 31ЗН 9 2!ТЕ $235Е 21 3458 Сп)елень в 11 ТФ7Н 23 ЗФЗГ 51 037 7 551Е 19 545Е 43 ТОЗН 3 ЭЬТВ 15 7270 гт Яттв 1 ЯЗЭЕ 1Э 45ЗГ 25 4338 85 007 5 7630 17 023 Э7 5377 9 675С 21 6130 45 4714 Сп)ЕЛЕНЬ 9 11 1055Е 23 1751Е 39 171$Е 55 1275Е 3 1131Е 15 15Я1Е 27 16)тн Яз 1713Н 75 17730 1 102!Е 13 1)ЬТГ 25 17ВЗН 4! !Эбэн 73 0013 5 14610 17 1ЗЗЗГ 29 155ЗН 45 1175Е 77 1511С 7 123)А 19 16058 35 1401С 51 17250 63 1Ф250 9 1ягзб 21 102!А Зт !!ЭТГ 5Э 1225Е 85 1267Е 11 ТФ13Н 47578 Я505Е 71ТЗН 453ЗГ 6227Н 5265Е 7107Н 731)С 7243Н 77450 ВЬЗЗГ Ь013Н 7273Н 6ЯЯТН ЙПЕЛЕНЬ )2 11 1564ТЕ 23 11015Е 35 105778 47 1$621Е 59 11Ф17Е 71 11471Е 83 12255Е 95 177054 107 141350 119 14315С 139 12067Г 151 1Ф7177 9 )176$А 21 10065А 33 133114 45 1517ЗС 57 12331А 69 16663С 81 17545С 93 14755С 105 136)Т4 !!7 16475С 137 1$437б 149 121479 165 10621А 4)ЛЕПЕНЬ 11 гз 55 47 $9 83 99 147 179 Сл)елень 11 23 35 «7 59 75 87 103 115 1Ф7 163 179 203 219 ЭЗ1 10 2065А 203ЭГ 3023Н Э177Н зат)б 3623Н ООЬТ 2355А 32110 1 7Н 1 157 1 2ЗГ 1 45Е 1 1ОЗГ г) оот 1 211Е 13 20ЗГ 1 2011Е 13 21577 25 24437 37 ЗЗЯЗГ 49 33250 Ь9 2701Я Ь$ 2707Е 101 2055Е 149 50250 341 0007 1 4005Е 13 Ф1ФЗГ 25 Ф57ТГ ЗТ 5ЭЗТГ Ф9 5711Е 61 4541Е 77 6263Н 89 53438 105 70410 117 54637 149 762!б 165 73)тн 181 5411Е 205 7447Н 293 77гэн ЗЗЭ 514!Е ! )о)гзГ 13 125138 25 133778 Зт 13565Е 49 17703С 61 13505Е 73 1Ь237Е 65 11673В 97 1712)б 109 )Я!110 121 16521Е 1Ф1 13571Я 153 )53178 Э 20178 15 2ЬЗЗВ 27 35730 39 21078 5) 25478 71 332ЗН вт 23!)А 103 35750 155 22514 3 ФФЯ5Е 15 ЯЗЬЗГ 27 623ЭН 39 згьзГ 51 522)Е 67 67110 79 5235Е 91 ФТЬТГ 107 Я251Е 119 5755Е 151 71610 167 520$Е 183 55ФЗЕ 211 ЬЭОТН 299 43038 339 74610 3 121338 1$1Э0778 27 14Я054 39 13321Д 51 10355А 63 10761Я 75 1Ь2670 87 17361Я 99 173230 111 15415С 123 \3475Я 143 12111А 155 14241С 5 2415Е 17 35)50 29 2Я61Е я! гтазе зэ 26!ТГ тэ ззотн 89 23272 105 ЗЬОТС 1ЬЗ 0051 5 4215Е 17 40537 29 6673Н 41 5361Е 5Э 6307Н 69 67770 81 74310 93 56077 109 5675Е 137 Ь6750 153 4731Е 169 4565Е 185 75650 213 6037Н 301 50077 341 525ЭГ 5 101154 !т )ьзззн 29 14127Н Ф1 153Ф18 5Э 153210 65 00141 77 )511$С В9 11271Е 101 14227Н 113 1313)Е 133 11ФЗЗВ 145 1ЬЭЗЗС 157 146750 7 37710 31 ЭОЯЗО аз газ)е 55 345ЭО 75 24ЭТВ 91 32650 107 31710 171 33150 7 4055Е 19 5023Г 31 7237Н 4Э $171Е 55 62116 71 77150 83 64550 99 ЯЬОЗГ Щ1 4!ТЗГ 139 76550 155 4451Е 171 67656 199 6543Н 215 736ЭН 307 75550 Т 121538 !9 160Ь7Н Э1 )Т673Н 43 1$053Н 55 10201А Ь7 1$275Е 79 12515Е 91 10011А 103 12117Е из )эггэд 135 105714 147 176570 163 10663Г 9 ггзтв 21 37530 $3 0075С 45 306)С 57 3121С 77 24138 93 ЗТТ70 109 2047Г !тз зэзтн 9 60150 21 56232 33 73350 45 6637Н 57 ЗТЬТГ 73 634ЗН 85 5247Г 101 65610 113 Ф707Г 141 5531Е 157 6557Н 173 75356 201 5613Г 217 т2010 309 4261Е тбйлнце В.г.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
