Группы автоморфизмов кодов Хэмминга и их компонент

• Автор: Горкунов, Евгений Владимирович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Новосибирск
• Количество страниц: 78 с. : ил.

Оглавление
Введение

Глава 1. Группы автоморфизмов кодов Хэмминга

1.1. Группы автоморфизмов и их связь с группами матриц

1.2. Симметрии линейных кодов

1.3. Группа перестановочных автоморфизмов кода Хэмминга

1.4. Симметрии кода Хэмминга

Глава 2. Мономиальные автоморфизмы компонент кода Хэмминга

2.1. Связь кода Хэмминга и конечных проективных геометрий

2.2. Мономиальные автоморфизмы линейной компоненты

2.3. Простая компонента и её обобщение

Глава 3. Восстановление двоичных кодов по их метрическим инвариантам
3.1. О восстановимости кодов и центрированных функций
3.2. Полусильные изометрии двоичных кодов
Заключение
Литература

Введение
Исследования в теории кодирования, дискретном анализе, теории графов и других областях дискретной математики имеют дело с кодами, схемами отношений, раскрасками, булевыми функциями, группами; квазигруппами, графами и многими другими объектами. В ряду таких характеристик регулярности объектов, как ранг, размерность ядра, степень нелинейности, однородность и т.п., группа автоморфизмов является наиважнейшей мерой симметрии. Все симметрии, встречающиеся в природе, описываются на языке автоморфизмов.
В настоящей диссертации исследуются группы автоморфизмов кодов Хэмминга и некоторых их подкодов, играющих важную роль, при решении ряда задач теории кодирования. Кодом называется подпространство метрического пространства. Метрические свойства кодов находят широкое практическое применение для надёжной передачи информации, её эффективной обработки, для восстановления целостности данных, которая может быть утрачена при длительном хранении или в результате старения носителя. Кроме того, результаты теории кодирования используются для решения задач в смежных областях дискретной математики, например, в криптографии, сжатии данных, обработке изображений, биоинформатике и др.
Актуальность изучения автоморфизмов определяется их исключительным свойством выявлять внутреннюю структуру рассматриваемого кода. Действие автоморфизмов на кодовые слова позволяет понять, какие части кода схожи и имеют одинаковое строение, а какие суще-

ственно различны. Обнаруженные особенности могут найти практическое применение в построении новых кодов, в разработке более эффективных алгоритмов кодирования и декодирования. Группы автоморфизмов используются также для классификации и систематизации кодов.
Рассмотрим множество последовательностей длины п над конечным алфавитом мощности g, называемое также q-ичным кубом. Снабжённый некоторой метрикой, g-ичный куб образует метрическое пространство V71. В настоящей работе рассматриваются только пространства Хэмминга. Расстояние Хэмминга между двумя последовательностями х, у € Vй определяется числом позиций, в которых х и у различаются.
Произвольное подмножество С С Vй называется ç-ичным кодом длины п. Элементы кода суть кодовые слова. Наименьшее ненулевое расстояние между кодовыми словами кода С обозначается d = d(C) и называется кодовым расстоянием. Длина, мощность и кодовое расстояние g-ичного кода составляют его параметры и записываются в виде (п, C,d)q. Число символов кодирующего алфавита g часто не указывают, если ясно, о каких кодах идёт речь.
Напомним, что изометрия — это преобразование метрического пространства, сохраняющее расстояние между его элементами. Автоморфизмом кода С Ç Vй называется изометрия пространства Vn, отображающая код С в себя. Два кода Ci и 6Д являются эквивалентными, если существует изометрия пространства Vn, отображающая эти коды друг в друга.
А. А. Марков в 1956 г. показал [19], что группа изометрий пространства Vй представляет собой полупрямое произведение
Aut(V”) = Sn X Snq = {(тг; а) | тг G Sn, a G £”} .
Иначе говоря, каждая изометрия Vn является парой преобразований (7г;<т). Подстановка тг G Sn переставляет элементы каждой последова-
Глава 2 Мономиальные автоморфизмы компонент кода Хэмминга
Важной задачей теории кодирования является построение кодов с предписанными свойствами. Построение совершенных кодов, образующих плотную упаковку метрического пространства, являет собой пример такой задачи.
В этой главе рассматриваются компоненты кода Хэмминга — специальные подкоды, которые могут быть сдвинуты по некоторой фиксированной координате г, в результате чего из кода Хэмминга получается другой совершенный код с теми же параметрами. Такое преобразование называется свитчиигом (от англ. switch — переключать), поскольку при этом в двоичном случае в г-й координате кодовых слов 0 заменяется на 1 и наоборот. Конструирование совершенных кодов сдвигами линейных компонент получило название метода г-компонент. На основе таких сдвигов С. В. Августинович и Ф. И. Соловьёва [8] разработали оригинальный метод построения совершенных кодов, названный методом й-компонент.
Развитием указанных подходов для случая q > 2 стал метод простых компонент, разработав который, А. В. Лось [16] построил новое семейство совершенных g-ичных кодов. На тот момент оно являлось