Ad
More Related Content
Similar to Александра Торгашова (12)
More from LiloSEA (20)
Ad
Александра Торгашова
- 1. Исследование полиномиальных кодов Торгашова А.В.
- 2. № 1 : создание систем кодирования, которые по своим характеристикам не уступали бы уже существующим. Будут рассматриваться циклические полиномиальные коды, исправляющие до трех ошибок.
- 3. Основная трудность возникает при кодировании тогда, когда надо выбрать «нужный» многочлен, т.е. многочлен, при использовании которого код приобретает заданные свойства. Поэтому одной из актуальных задач является создание методики построения порождающего многочлена.
- 4. Суть методики построения циклического полиномиального кода. Если взять примитивный многочлен f ( x ) степени n с корнем α, реально можно найти β=α ^( (2 n - 1)/ d ) – корень искомого неприводимого многочлена, который является характеристическим многочленом элемента β , то есть порождающим многочленом для кода.
- 5. Пример 1. Полиномиальный циклический код, порождённый симметричным неприводимым многочленом степени 16, обладает свойством d min ≥ 5. Так как порядок d равен 257, то при одинаковой степени многочлена БЧХ-кода (255,16) и симметричного многочлена полученного выше кода (257,16), получается, что последний может исправлять тоже две ошибки, но длина кода на два бита больше, чем кода БЧХ. Пример 2. Полиномиальный циклический код (641,64), порождённый симметричным неприводимым многочленом степени 64, обладает свойством d min ≥ 7 и может исправлять три ошибки, так как 5≡2 25 ( mod 641).
- 6. № 2: последовательное построение (генерация) неприводимых многочленов данной степени. Генерация неприводимых многочленов является актуальной и сложной на сегодняшний день прикладной задачей, широко востребованной в криптографических приложениях и теории кодирования.
- 7. Один из методов – получение новых неприводимых многочленов из данного неприводимого многочлена той же степени, при условии, что корни этих многочленов связаны степенными зависимостями. В ходе работы были явно выписаны и программно реализованы переходы х х 3 и х х 5 . Их эффективность проверена и доказана.
- 8. Один из полученных многочленов с использованием преобразования x x 3 для многочлена 64-й степени: x 64 + x 63 + x 62 + x 61 + x 60 + x 56 + x 54 + x 52 + x 51 + x 48 + x 47 + x 4 4 + x 43 + x 41 + x 39 + x 35 + x 34 + x 33 + x 32 + x 31 + x 30 + x 29 + x 25 +x 23 +x 21 +x 20 +x 17 +x 16 +x 13 +x 12 +x 10 +x 8 +x 4 +x 3 +x 2 +x+1
- 9. Итоги: 1. С помощью новой методики построены коды (23, 11) и (47, 23), которые исправляют до трех ошибок, а также код (257, 16), исправляющий две ошибки. 2. Доказан ряд теорем, применимых к полиномиальному кодированию, в том числе о существовании неприводимых симметричных многочленов, применяемых для кодов и дающих d min не меньше трех, пяти и семи. 3. Явно выписаны и программно реализованы переходы х х 3 и х х 5 . Проанализированы свойства переходов х х 11 и х х 17 .