Введение 3
Глава 1. Структура линейных циклических кодов 5
1.1 Автоморфизмы кодов 5
1.2 Кратные корни многочленов над конечными полями 9
1.3 Полиномиальное представление C (v, q) -кодов 13
1.4 Покомпонентное произведение C(v, q) - кодов 17
1.5 Перестановочные многочлены на множестве Fm q - и некоторых его подмножествах 20
1.6 Вычисление мономиальных автоморфизмов C(v, q) - кодов 23 Глава 2. Примеры вычисления групп автоморфизмов некоторых кодов 25
Заключение 42
Список использованной литературы 43
Приложения 45
Изучение групп автоморфизмов кодов является одним из важных направлений исследований в теории кодов, корректирующих ошибки. Группа автоморфизмов кода помогает детально прояснить его внутреннюю структуру.
Действие автоморфизмов на кодовые слова позволяет понять, какие части кода схожи и имеют одинаковое строение, а какие существенно различны. Обнаруженные особенности могут найти практическое применение в построении новых кодов, в разработке более эффективных алгоритмов кодирования и декодирования. Группы автоморфизмов используются также для классификации и систематизации кодов.
Кроме того, группа автоморфизмов кода позволяет найти число кодов, которые ему эквивалентны. Код, обладающий большим количеством эквивалентных кодов, может быть использован в криптографических системах как секретный ключ.
Актуальность исследований блочных кодов диктуется их широким практическим применением для надежной передачи информации, ее эффективной обработки, для восстановления целостности данных, которая может быть утрачена при длительном хранении, при передаче данных по каналу связи или в результате старения носителя информации.
Целью выпускной квалификационной работы является исследование и вычисление полных групп автоморфизмов некоторых линейных кодов над конечными полями, а также реализация алгоритмов вычисления групп автоморфизмов линейных кодов путём сведения задачи к решению систем уравнений в конечных полях.
Для достижения данной цели были решены следующие вопросы:
• реализация вычислений в конечных полях характеристики 2, в частности
в поле Fie;
• реализация операций с многочленами над конечными полями;
• решение алгебраических уравнений над конечными полями;
• разработка алгоритмов вычисления автоморфизмов, относительно которых код инвариантен.
В работе проиллюстрировано шесть примеров вычисления групп автоморфизмов кодов. В примерах 1 и 2 ограничимся двоичными кодами, то есть q = 2, а Fq = F2 - поле из двух элементов. Для кодов V1 и V2 необходимо вычислить группы симметрии, причем код V1 полупростой, а V2 - код с кратными корнями.
В примерах 3 и 4 для исследования были выбраны линейные циклические коды длины 15 над конечным полем из четырех элементов F4. Для каждого кода необходимо привести описание процедуры поиска перестановочных многочленов и множителей,а также его полной группы мономиальных автоморфизмов.
В примерах 5 и 6 рассматриваются коды длины 5 над конечным полем из 4 элементов F4. Для кодов V5 и V6 необходимо вычислить полные группы мономиальных автоморфизмов, а также группы конфигураций кодов
Цель выпускной квалификационной работы заключалась в исследовании и вычислении полных групп автоморфизмов некоторых линейных кодов над конечными полями. Были реализованы программные средства для автоматизации вычислений полных групп автоморфизмов линейных циклических кодов.
Проведена классификация возможных автоморфизмов в линейных кодах. Рассмотрены преобразования сдвигов, простые симметрии кодов путем одновременной перестановки компонент кодовых векторов, мономиальные преобразования кодов, преобразования - конфигурации и наиболее общие группы изометрий, то есть биективные преобразования кода на себя, сохраняющие определенную метрику (например, расстояние Хемминга или скалярное произведение между кодовыми словами).
Также в главе 2 приведены шесть примеров вычисления групп автоморфизмов кодов. В примерах 1 и 2 были исследованы двоичные коды, в примерах 3-6 рассматривались коды над конечным полем F4. Было установлено, что группа симметрии Sym(V) кода V1 изоморфна полной линейной группе GL(3, F2). Порядок Sym(V1) равен 168. Порядок группы симметрии Sym(V2) равен 3 • 7 • 210, причем V2 - код с кратными корнями.
Группы полных мономиальных автоморфизмов MAut(V3) и MAut(V4) кодов V3 и V4 совпадают и изоморфны полной линейной группе GL (2, F4). Их порядок равен 540.
Полные группы мономиальных автоморфизмов кодов V5 и V6 состоят из 180 преобразований (п,а) Е MAut(V5) и (п,а) Е MAut(V6) соответственно, которые приведены в таблицах 3 и 4 приложения 2. Было вычислено, что группы конфигураций CAut(V5) и CAut(V6) кодов V5 и V6 имеют порядок 5760. Причем, группа конфигураций CAut(V5) является собственной подгруппой группы изометрий Aut(V5), а CAut(V6) - собственная подгруппа Aut(V6).
Таким образом, процедуры поиска групп автоморфизмов, указанные в главе 2, могут быть применимы для вычисления полных групп автоморфизмов других C(v,q) - кодов.
