Транзитивные совершенные коды и разбиения

Гуськов, Георгий Константинович

Транзитивные совершенные коды и разбиения тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Гуськов, Георгий Константинович АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Новосибирск МЕСТО ЗАЩИТЫ

2013 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

Диссертация по математике на тему «Транзитивные совершенные коды и разбиения»

Автореферат диссертации на тему "Транзитивные совершенные коды и разбиения"

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ НАУКИ ИНСТИТУТ МАТЕМАТИКИ ИМ. С. Л. СОБОЛЕВА СИБИРСКОГО ОТДЕЛЕНИЯ РОССИЙСКОЙ

АКАДЕМИИ НАУК

На правах рукописи ГУСЬКОВ Георгий Константинович

ТРАНЗИТИВНЫЕ СОВЕРШЕННЫЕ КОДЫ И РАЗБИЕНИЯ

Специальность 01.01.09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата физико-математических наук

1 4 НОЯ 2013 005538100

Новосибирск - 2013

005538100

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте математики им. С. Л. Соболева Сибирского отделения Российской академии наук

Научный руководитель: доктор физико-математических наук,

профессор Соловьёва Фаина Ивановна

Официальные оппоненты: Дьячков Аркадий Георгиевич, доктор

физико-математических наук, профессор, Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Московский государственный университет имени М. В. Ломоносова;

Фионов Андрей Николаевич, доктор технических наук, профессор, Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования Сибирский государственный университет телекоммуникаций и информатики, проректор по научной работе

Ведущая организация: Федеральное государственное бюджетное

учреждение науки Институт проблем передачи информации им. А. А. Харкевича Российской академии наук

Защита состоится 18 декабря 2013 г. в 16 час. 00 мин. на заседании диссертационного совета Д 003.015.01 при Федеральном государственном бюджетном учреждении науки Институте математики им. С. Л. Соболева Сибирского отделения Российской академии наук по адресу: 630090, г. Новосибирск, пр. Академика Коптюга, 4, копференц-зал.

С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного учреждения науки Института математики им. С. Л. Соболева Сибирского отделения Российской академии наук. Автореферат разослан 5 ноября 2013 г.

Учёный секретарь

диссертационного совета Д 003.015.01, д.ф.-м.п.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. В настоящей диссертации исследуются проблемы существования и перечисления объектов, находящихся на стыке алгебраической комбинаторики и теории кодов, исправляющих ошибки в канале связи с шумами.

Объект исследования настоящей работы - транзитивные коды над двоичным алфавитом, исправляющие одиночные ошибки, а также разбиения пространства всех двоичных векторов на совершенные коды.

Двоичные коды являются одним из основных объектов исследования теории кодирования и служат базой для дальнейшего развития современных цифровых технологий. С 1949 года, с фундаментальных работ К. Шеннона по теории информации, началось бурное развитие теории кодирования как самостоятельной научной дисциплины, наряду с криптологисй и сжатием информации, без которых был бы невозможен сегодняшний уровень развития коммуникационных технологий.

Совершенный код, исправляющий одиночные ошибки, задаёт разбиение всего пространства на совокупность шаров радиуса 1 с центрами в кодовых словах. Из данного факта следует важное свойство совершенных кодов - их оптимальность, то есть, при заданной длине кода и кодовом расстоянии мощность всякого совершенного кода максимальна. Раздел теории кодирования, посвящёнпый построению и исследованию свойств совершенных кодов настолько богат, что, помимо свойств самих кодов, интерес представляют также методы их исследования. Заметим, что задача упаковки пространства шарами фиксированного радиуса важна с точки зрения целого ряда других математических дисциплин: комбинаторного анализа, криптологии, теории групп, теории графов, топологии. Таким образом, результаты теории кодирования могут быть использованы для решения задач в смежных областях дискретной математики. Например, коды с богатыми группами автоморфизмов могут быть использованы в криптографии.

Проблема исследования разбиений пространства (векторного пространства длины п над СГ(2) по отношению к метрике Хэмминга) на совершенные коды тесно связана с проблемой построения таких кодов и изучения их свойств, поскольку асимптотики двойных логарифмов (если опи существуют) числа различных совершенных кодов и числа различных разбиений на такие коды совпадают. Здесь и далее будем рассматривать только логарифмы по основанию 2. Также следует упомянуть о том, что некоторые разбиения пространства индуцируют раскраски векторов на коды, связанные с оптоволоконными сетями. Кроме того, совершенные коды являются частным случаем так называемых ре-

гулярных разбиений, в англоязычной литературе известных также как equitable partitions, а в отечественной литературе больше известных как совершенные раскраски. Наряду с дистанционно регулярными графами и схемами отношений, совершенные раскраски являются популярными объектами алгебраической комбинаторики. Различные методы построения разбиений могут быть использованы для исследования их нетривиальных свойств, а также для построения новых кодов, в частности, совершенных (такие методы, например, описаны в работе [7]). Важность поиска новых методов построения кодов, а также методов их задания, объясняется, в частности, тем, что на их основе можно разрабатывать новые, более эффективные, методы передачи информации, или криптографические системы-коды.

Несмотря на значительные усилия ряда исследователей, многие вопросы теории совершенных кодов всё ещё остаются нерешёнными. Так, по-прежнему не найдена классификация совершенных q-значных кодов для q - степеней простого, q > 2. Согласно теореме В. А. Зиновьева и В. К. Леонтьева (см. [3, 4]), независимо доказанной Э. Тиетвайненом, нетривиальные совершенные д-значные коды длины п, исправляющие ошибки, существуют только при п = (qk — 1 )/(<?— 1), к > 2, и имеют кодовое расстояние 3; при п = 23 - двоичный код Голея с кодовым расстоянием 7, а также при п = 11 - троичный код Голея с кодовым расстоянием 5. Оба кода Голея единственны с точностью до эквивалентности, в то время как существует дважды экспоненциальное число неэквивалентных совершенных кодов с кодовым расстоянием 3. Классификация расширенных совершенных двоичных кодов длины 16 и совершенных двоичных кодов длины 15, была получена П. Остергардом и О. Поттоне-ном в 2009 г. в работе [14].

Цель данной работы состоит в исследовании конструкций совершенных кодов и разбиений пространства F" на совершенные коды, а также в применении этих конструкций для изучения свойств разбиений и кодов. В работе рассматриваются только двоичные коды и разбиения на такие коды.

Методика исследований. В диссертации используются традиционные методы и аппарат алгебраической и комбинаторной теории кодирования, комбинаторного анализа и теории i-схем. Для исследования предельно-транзитивных кодов использован метод локального анализа, восходящий к работам Ф. И. Соловьёвой [7].

Научная новизна. Все результаты, представленные в диссертации, являются новыми.

1. В диссертации продолжено развитие метода локального анализа из [7]. С его помощью установлено существование 5 бесконечных серий неэквивалентных нределыю-транзитивных расширенных совершенных кодов. Для доказательства предельной транзитивности в работе предложено использовать свойства Паш-конфигураций систем троек Штейпе-ра, соответствующих проверяемым совершенным кодам. Неэквивалентность кодов для каждой фиксированной длины была доказана с помощью сравнения значений их рангов и размерностей ядер. Впервые предельно-транзитивный код длины 16 был обнаружен С. А. Малюгиным1 в 2004 г. С помощью системы компьютерной алгебры MAGMA2 найдены все транзитивные расширенные совершенные коды длины 16, имеющие хотя бы одну петранзитивную координату. Проверка кода на транзитивность заключалась в проверке па транзитивность соответствующей ему структуры инцидентности.

2. В диссертации впервые исследуется спектр рангов пропелиней-ных кодов. Для этого были использованы методы построения транзитивных кодов из [5], основанные на конструкциях Моллара и Васильева для совершенных кодов. Тот факт, что конструкция Моллара сохраняет пропелипейность исходных кодов, был доказан в [9]. Зависимость ранга результирующего кода от рангов исходных кодов для конструкции Моллара была доказана в [5]. С помощью системы компьютерной алгебры Magma впервые были обнаружены пропелинейные коды длин 15 и 31 полного ранга. В ходе компьютерных исследований рассматривались только нормализованные пропелинейные структуры, данное понятие было введено в [9].

3. Продолжено исследование транзитивных разбиений пространства F" на совершенные двоичные коды, начатое в [6]. В данной диссертации впервые исследованы вершинно-транзитивные разбиения пространства F". С помощью компьютерных исследований проверены транзитивность, 2-транзитивность и вершинная транзитивность 11 неэквивалентных разбиений длины 7, классифицированных К.Т. Фелпсом в [15]. Было показано, что конструкции транзитивных разбиений па двоичные коды, введённые в [6], могут применяться для построения 2-транзитивных и вершинно-транзитивпых разбиений произвольной длины. Впервые получена нижняя оценка числа неэквивалентных разбиений для каждого из этих классов кодов. В качестве критерия неэквивалентности полученных разбиений использовались их матрицы пересечений, аналогичный метод

1 Малюгин С. А. Частное сообщение — 2004.

2 Bosma W., Cannon J., Playoust С. The Magma algebra system. I. The user language // J. Symbolic Comput. — 1997. — Vol. 24. — P. 233-265.

был применён в [8]. Была найдена зависимость матриц пересечений разбиений, полученных с помощью рассмотренных конструкций от матриц пересечений исходных разбиений.

4. С целью построения разбиений пространства Fn на совершенные двоичные коды малого ранга продолжено развитие свитчингового метода, предложенного C.B. Августиновичем и Ф.И. Соловьёвой в 1996 году для построения широкого класса двоичных совершенных кодов. Также предложена модификация конструкции разбиений на совершенные коды, основанная на конструкции Фелпса (см. [8]). Проведён сравнительный анализ семейств кодов, соответствующих данным конструкциям и показано, что нижняя оценка числа различных разбиений пространства Fn на совершенные двоичные коды малого ранга, полученная с помощью конструкции ¿^-компонент, является лучшей на сегодняшний день для почти всех допустимых длин кодов.

Практическая и теоретическая ценность. Работа носит теоретический характер. Полученные в ней результаты могут быть применены в теории кодов, исправляющих ошибки: для дальнейшего исследования и построения новых классов двоичных кодов, для построения совершенных кодов полного ранга, кодов с большими кодовыми расстояниями, для исследования разбиений пространства F" на коды.

Апробация работы. Все результаты диссертационной работы были апробированы на следующих конференциях: на XII международном симпозиуме по проблемам избыточности в информационных системах (С.-Петербург, Россия, 2009 г.); па VII молодёжной школе по дискретной математике и её приложениям (Москва, Россия, 2009 г.); на международной конференции по алгебраической комбинаторике и её приложениям ALCOMA-IO (Тырнау, Германия, 2010 г.); на международной конференции "Современные проблемы математики, информатики и биоинформатики" (Новосибирск, Россия, 2011 г.); на XXV конференции молодых учёных и специалистов "Информационные технологии и системы - 2012" (Петрозаводск, Россия); на международной конференции "Мальцевские чтения" (Новосибирск, Россия, 2012 г.); на международном симпозиуме по теории информации ISIT 2013 (Стамбул, Турция, 2013 г.).

Результаты работы докладывались на семинаре "Теория информации и теория кодирования" ИППИ РАН, на семинарах "Теория кодирования" и "Дискретный анализ" НГУ и Института математики СО РАН.

Основные результаты диссертации.

1. Получено (конструктивно) 5 бесконечных серий неэквивалентных предельно-транзитивных расширенных совершенных двоичных кодов любой возможной длины, начиная с шестнадцати.

2. Решена проблема рангов для пропелинейных совершенных двоичных кодов, за исключением случаев кодов полного ранга для длин 63,127,2047 и кодов длины 127 предполного ранга.

3. Предложены конструкции транзитивных, 2-транзитивных и вер-шинно-транзитивных разбиений пространства Р" на совершенные коды для любой допустимой длины, получены нижние оценки числа неэквивалентных таких разбиений.

4. С помощью свитчинговой конструкции получена лучшая на сегодняшний день нижняя оценка числа разбиений двоичного п-мерного векторного пространства на совершенные коды длины п > 31.

Объем и структура диссертации. Диссертация состоит из введения, трёх глав, приложения и списка литературы (62 наименования), в конце приведён список публикаций автора по теме диссертации. Объем диссертации 116 страниц, включая 2 иллюстрации и 5 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

Прежде чем перейти к обзору полученных в диссертации результатов, приведём необходимые определения и обозначения.

Расстояние Хэмминга ¿{х, у) между двумя произвольными векторами х и у пространства определяется как число координатных позиций, в которых эти векторы различаются. Вес вектора - это число его ненулевых координат. Произвольное подмножество пространства Ж" называется двоичным кодом длины п. Векторы из ¥п, принадлежащие коду, называются кодовыми словами. Код С из Р" называется совершенным двоичным кодом, исправляющим одиночные ошибки (далее кратко совершенным кодом), если каждый вектор пространства находится на расстоянии не больше 1 от некоторого единственного вектора из С. Как было отмечено ранее, такие коды существуют только при п = 2т — 1, т> 2. Кодовым расстоянием кода называется наименьшее из расстояний Хэмминга между всеми его попарно различными кодовыми словами. Код, содержащий нулевое кодовое слово, называют приведённым. Код называется линейным, если он является подпространством ¥п. Линейный совершенный код называется кодом Хэмминга. Известно, что для фиксированного п код Хэмминга длины п единствен с точностью до изоморфизма.

Ядро приведённого кода С состоит из всех кодовых слов х € С таких, что х + С = С. Размерность линейной оболочки множества всех кодовых слов приведённого кода называется рангом кода. Размерность ядра и ранг приведённого кода С обозначаются через к (С) и г (С), соот-

ветственно. Известно, что ранг и размерность ядра кода Хэмминга равны п — log (п+1), ранги совершенных (расширенных совершенных) кодов длины п (длины п + 1) могут принимать значения от и - 1од{п + 1) до п. Здесь и далее log обозначает логарифм по основанию 2. Если ранг совершенного (расширенного совершенного) кода длины п (длины N = п + 1) равен п, его называют кодом полного ранга.

Пусть С - произвольный совершенный код. Через ST(C) будем обозначать систему троек кода С, то есть ST(C) = {u+v|m, v € С : w(u+v) = 3}. Соответственно, для произвольного расширенного совершенного кода С через SQ(C) будем обозначать систему четвёрок, то есть SQ(C) = {и + v\u, v е С : w{u + v) = 4}.

Известно, что группа автоморфизмов пространства Fn исчерпывается всеми изометриями Fn, каждая такая изометрия определяется подстановкой 7г на множестве координат и сдвигом на произвольный вектор v £ Fn. Группа автоморфизмов Aut(F") пространства F" определяется как Aut(Fn) = {(v,7r) I v е F71, тг G Sn}, где Sn — симметрическая группа подстановок порядка п. Множество всех перестановок координатных позиций, сохраняющих код С, называется группой симметрии, кода С и обозначается через Sym(C). Группой автоморфизмов Aut(C) кода С длины п называется группа изометрий пространства F™, переводящих код в себя. Говорят, что два произвольных кода С и D эквивалентны, если существует такая изометрия ip пространства Fn, что С = f{D).

Код называется транзитивным, если его группа автоморфизмов действует транзитивно на всех его кодовых словах. Для приведённых кодов удобно использовать следующее определение транзитивного кода: для каждого кодового слова £ из С найдётся подстановка 7гх из Sn такая, что (х,пх) € Aut(C), то есть х + С = тгх(С), где тгх может не принадлежать группе симметрии Sym(C) = {тт € Sn | к(С) = С} кода С. Таким образом, в транзитивном приведённом коде для любого его кодового слова х найдётся автоморфизм (х, ттх) € Aut(C), переводящий слово х в нулевое кодовое слово. Легко видно, что оба этих определения эквивалентны.

Кодовое слово х из нетранзитивного кода С, для которого не существует такой подстановки жх, будем называть нетранзитивным кодовым словом. Координатную позицию транзитивного расширенного совершенного кода назовём нетранзитивной, если код, полученный её выкалыванием, нетранзитивен.

Во введении обосновывается актуальность темы диссертации, характеризуется новизна работы. Даётся краткий обзор полученных результатов по тематике диссертации. Приводится список основных результатов диссертации и объясняются связи между ними.

Первая глава диссертации посвящена исследованию транзитив-

ных совершенных и расширенных совершенных кодов. Задачу проверки объекта на транзитивность можно встретить и в других областях математики - например, поиск гамильтонова цикла в графах. Транзитивные коды но ряду свойств близки к линейным кодам, в частности, для приведённого транзитивного кода С верно следующее: |Aut(C)| = \С\ ■ |Sym(C)|. Данное обстоятельство позволяет сделать вывод о некотором богатстве групп автоморфизмов транзитивных кодов. Число транзитивных кодов, по всей вероятности, невелико, по сравнению с общим числом кодов с теми же параметрами. Тем не менее, для всякого оптимального нелинейного кода почти всегда можно найти транзитивный код с теми же параметрами. Например, двоичный образ (под действием отображения Грея) произвольного Z4- или Z2¿^-линейного кода является транзитивным кодом.

Очевидно, что применение общей проверки на чётность позволяет получать из транзитивных совершенных двоичных кодов транзитивные расширенные совершенные двоичные коды. Обратное не всегда верно, в частности, в 2004 г. С. А. Малюгиным был обнаружен один транзитивный расширенный совершенный двоичный код длины 16, такой, что все коды, полученные из него выкалыванием любой координаты, являются нетранзитивными. Всякий транзитивный расширенный совершенный код произвольной допустимой длины, обладающий свойством, что все коды, полученные из него выкалыванием любой координаты, являются нетранзитивными, будем называть предельно-транзитивным. Иными словами, это код, все координаты которого нетрапзитивны.

В разделе 1.1 решена задача классификации всех предельно-транзитивных кодов длины 16, а также доказано существование таких кодов для любой допустимой длины.

В разделе 1.1.1 приведены результаты, полученные в диссертации посредством дополнительных компьютерных исследований, проведённых с помощью системы компьютерной алгебры Magma. Для каждого транзитивного кода длины 15 и транзитивного расширенного кода длины 16 из [14] были вычислены ранг, размерность ядра, порядок группы симметрии, мощность множества ST(C) (SQ(C) - для расширенных кодов). Найдены3 все транзитивные расширенные совершенные коды длины 16, имеющие хотя бы одну нетранзитивную координату.

Для построения бесконечной серии предельно-транзитивных кодов в разделе 1.1.2 использованы известные конструкции Васильева [2] и

3 Guskov G. К., Solov'eva F. I. Properties of perfect transitive binary codes of length 15 and extended perfeet transitive binary codes of length 16, 2012, http://arxiv.org/abs/1210.5940.

Плоткина [12].

Рассмотрим произвольный расширенный совершенный код С" длины N = 2к. Через С2Ы обозначим расширенный код длины 2АГ, полученный из него с помощью конструкции Плоткина. Введём обозначение А/дг = {1,2...., М}. Через С?-1 обозначим код, полученный выкалыванием кода С" по уй координатной позиции, ] € Л/дг- Пусть У?п+1 - код, полученный из совершенного кода С", г 6 Л/л', п = 2к — 1, к > 3, применением конструкции Васильева с функцией А = 0. Сравнение этих конструкций позволило обнаружить связь между кодами Ц2п+1 и С2п+1, которая выражается в следующем утверждении

Лемма 1. Для любого ] € Агл' найдётся г € Л^у такое, что код С2п+1 изоморфен коду Васильева у2п+1.

Для проверки нетранзитивности выколотых кодов был применён метод локального анализа из [7], а именно, были детально исследованы Паш-конфигурации систем троек Штейнера полученных совершенных кодов. Напомним, что системой троек Штейнера 8Т8П порядка п называется система сочетаний из п-элементного множества Мп = {1,..., п} по три, называемых тройками, такая, что каждая неупорядоченная пара элементов содержится в точности в одной тройке. Известно (см. [12]), что множество кодовых слов веса 3 в приведённом совершенном коде Сп образует систему троек Штейнера (каждая тройка системы состоит из номеров ненулевых координат соответствующего кодового слова веса 3). Будем обозначать её через 8Т8(6т). Паш-конфигурацией для БТЭ,, называется множество троек из БТБп, изоморфное множеству

{(а, Ь, с), (а, у, г), (х, Ь, г), (х, у, с)},

то есть, троек, попарно пересекающихся по одному элементу, а в объединении дающих шесть элементов. Известно, что число Паш-конфигураций Р^ТЭп) системы троек Штейнера ЯТЯ« порядка п является инвариантом, часто позволяющим устанавливать неэквивалентность двух систем троек Штейнера.

В работе найдена рекуррентная формула для числа Паш-конфигураций системы троек Штейнера кода Васильева У?п+1. Оказалось, что оно зависит только от числа Паш-конфигураций системы троек Штейнера исходного кода С":

Р(5Т5(^2п+1)) = 8 • Р(5Г5(СР)) + |5Т5(С?)| + 2 • • (х)

В результате исследования свойств десяти неэквивалентных пре-делыю-траизитивных расширенных совершенных кодов длины 16, обнаружено, что восемь из них таковы, что для любого направления г € А^е,

в нетранзитивном выколотом коде С", п = 15, найдётся такое нетранзитивное слово у, что системы троек Штейнера кодов С" и С]1 4- у имеют различное число Паш-конфигураций. Используя лемму 1, доказано, что, при подстановке таких кодов в конструкцию Плоткина (см. [12]), это свойство сохраняется, то есть верна

Лемма 4. Для любого N = 2к, к > 4, существует не менее 8 различных транзитивных расширенных совершенных кодов длины N таких, что для любого из этих кодов См для всякого направления г € Мн, в выколотом коде С", п = N — 1, найдётся такое нетранзитивное слово у, что Р(5Т5(С?)) ф Р(5Т5(С? + у)).

Используя зависимость (1), лемму 4 и результаты компьютерных исследований, представленные в приложении, доказана

Теорема 1. Для любого допустимого N > 16 существует не менее пяти неэквивалентных предельно-транзитивных расширенных совершенных кодов длины N. При N = 16 существует 10 неэквивалентных таких кодов.

Неэквивалентность кодов доказывалась с помощью сравнения соответствующих им пар значений (ранг, размерность ядра), используя подход из [5].

Применяя конструкцию Плоткина, каждый из восьми различных предельно-транзитивных расширенных совершенных кодов длины 16, обладающих описанным в лемме 4 свойством, можно продолжить до бесконечной серии. Таким образом, верно

Следствие 1. Для любого допустимого N > 16 существует не менее 8 различных предельно-транзитивных расширенных совершенных кодов длины N.

В разделе 1.2 решается задача нахождения всех значений, которые могут принимать ранги транзитивных совершенных кодов, то есть, решается проблема спектра рангов транзитивных совершенных кодов.

Из статьи [5] известно, что если в конструкцию Васильева с функцией А = 0 подставить код длины п, то разница между рангом полученного кода длины 2п 4- 1 и рангом кода Хэмминга длины 2п + 1 (так называемая прибавка ранга, см. [5]) остаётся той же, какой она была для исходного кода и кода Хэмминга длины п. Таким образом, с помощью конструкции Васильева с нулевой функцией А из кода полного ранга длины п (то есть, ранга п) можно получить лишь код длины 2п + 1 ранга на единицу меньше полного ранга. Однако, используя нелинейные функции А специального вида, ранг результирующего кода можно увеличить до полного, с сохранением транзитивности кода. В качестве таких функций А можно рассматривать пропелинейные функции и, соответственно, решать проблему рангов для пропелинейных кодов. Поскольку, по опре-

делению, всякий пропелинейный код является транзитивным, как следствие, будет решена проблема рангов и для транзитивных совершенных кодов.

Понятие пропелинейного кода (от латинского ргоре - близко, почти) было впервые введено Дж. Рифой с соавторами в 1989 г. Как известно, множество Aut(Fn) всех автоморфизмов пространства Fn образует группу под действием операции композиции: (и, 7г) о (и, т) = (и + тг(ь'), тгт) для всех (и, 7г), (v, г) е Aut(Fn), здесь и далее 7Гт(х) = 7г(т(х)) для a; G F".

Пусть для кода С задано означивание П кодовых слов подстановками: х i—>• 7ГХ: (х, тгх) 6 Aut{C), такое что = тгхтгу. Через П(С) обозначим множество всех подстановок, соответствующих словам из кода С. Определим групповую операцию на С вида х * у = (х, 7гх)у. Код с такой операцией называется пропелинейной структурой на С и обозначается (С,П,★) или, кратко, (С,*), если не требуется информация об означивании П. Код называется пропелинейным, если на нём определена пропелинейная структура. Очевидно, что любой пропелинейный код транзитивен. В 2001 г. Дж. Рифа с соавторами показали, что пропелиней-ные совершенные коды могут быть получены применением конструкции Васильева, а также конструкции Моллара, доказательство последнего факта см. в [9].

В разделе 1.2.1 с помощью системы компьютерной алгебры MAGMA доказано существование пропелинейных кодов полного ранга длин 15 и 31. Ранее в [9] было доказано существование пропелинейных совершенных кодов длины 15 любого допустимого ранга, за исключением полного ранга.

В разделе 1.2.2, на основании этих результатов, для кодов малых длин, используя конструкцию Васильева с функцией А = 0, а для кодов длин, начиная с 255 - конструкцию Моллара [13] с функцией / = 0, по индукции доказана

Теорема 5. Для любого n = 2m — l,m > 4 и произвольного г, такого, что п — log(n +1) < г < п, кроме случаев п = г = 63; п = 127, г € {126,127} и п = г = 2047, существует пропелинейный совершенный двоичный код длины п ранга г.

Результаты первой главы опубликованы в [19, 20, 22, 26, 27].

Во второй главе данной работы проводится исследование транзитивных разбиений пространства F" на совершенные коды, начатое в [6]. Изучение совершенных кодов, как уже упоминалось, неразрывно связано с изучением разбиений пространства Fn на совершенные коды. Некоторые свойства кодов справедливы для разбиений. Одним из таких свойств является транзитивность. Группой автоморфизмов произволь-

ного разбиения Рп = {Съ,С\,... , С„} пространства К™ на совершенные

коды С'0, СI,..., Сп, У С; = Р", называется группа изометрий простран-

г=0

ства Е", переводящих разбиение Рп в себя. Разбиение Рп называется к-транзитивным, 1 < к < п, если для любой пары упорядоченных подмножеств {¿1,..., г^} и {„/1; • ■ ■ >]к) из К существует автоморфизм а из АиЬ(Рп) такой, что а{Ск) = = 1 ,...,к. При к = 1 разбиение Рп

называется транзитивным. Если же рассмотреть кодовые слова кодов-элементов разбиения, можно определить более сильное свойство. Разбиение Рп назовём вершинно-транзитивгсым, если для любых двух кодовых слов и £ С\, v 6 С, существует автоморфизм а из Аи^Р") такой, что сг (и) = у. При этом, если г = ] для любого г € Л/*п, то получим вершинно-транзитивное разбиение на транзитивные коды (например, на классы смежности кода Хэмминга). Далее будем говорить, что разбиение имеет длину п, если оно состоит из кодов длины п.

В разделе 2.1 приведены вспомогательные утверждения и определения, необходимые для доказательства неэквивалентности полученных разбиений.

В разделе 2.2 представлены две конструкции транзитивных разбиений на совершенные коды. Доказано, что они сохраняют свойства вершинной транзитивности, транзитивности и также 2-транзитивности.

В разделе 2.3, используя утверждения из раздела 2.1 и ряд комбинаторных соображений, подсчитаны нижние оценки числа неэквивалентных транзитивных, вершинно-транзитивных и 2-транзитивных разбиений пространства Рг на совершенные коды.

Теорема 10. Для любого п > 2к — 1, к > 20, число неэквивалентных транзитивных разбиений на совершенные коды удовлетворяет следующей нижней оценке: Р^^гств >71+1.

Теорема 11. Справедливо

a) Для любого п > 2т — 1, т > 20, число Рп-^енех-^ат неэквивалентных вершитю-транзитив'ных разбиений Г" на совершенные коды длины тг удовлетворяет следующей нижней оценке: Рп^етгсх-ггапв >

b) Для любого п > 2т — 1, тп > 20, число Д^г-«™™ неэквивалентных 2-транзитивных разбиений на совершенные коды длины п удовлетворяет: /г„;2-«гап8 > НГ-

Для малых значений длин кодов п < 220 — 1 с помощью этого метода удалось получить только следующие нижние оценки:

Утверждение 1. Для любого п > 2т — 1, где 3 < т < 20, число неэквивалентных транзитивных, вершинно-транзитивных и 2-транзи-тивных разбиений на совершенные коды удовлетворяет следующим нижним оценкам соответственно:

aj fin;trans — 2 ' / ri:vertex—trans _ 3 ) С J trans _ 4 •

Результаты второй главы опубликованы в [17, 23].

В третьей главе изучаются и анализируются три конструкции различных разбиений пространства Fn па совершенные коды малого ранга с целью получения нижней оценки числа таких различных разбиений. Данная проблема связана с проблемой подсчёта числа различных совершенных двоичных кодов. Напомним, что, как известно, асимптотики двойных логарифмов (при условии, что они существуют) числа различных совершенных двоичных кодов и числа различных разбиений на такие коды совпадают. Причина подробного изучения разбиений малого ранга состоит в том, что на сегодняшний день в наилучшей нижней оценке числа различных совершенных двоичных кодов, полученной в статье [11], первые три сомножителя определяются именно совершенными кодами ранга не больше п — log (п + 1) + 2.

В разделе 3.1 изучается конструкция из работы 2004 г. [16], основанная на конструкции Васильева (она также использовалась в [10], но с некоторыми ограничениями).

Основываясь на классификации неэквивалентных разбиений длины 7, приведённой К. Т. Фелпсом в [15] (таких разбиений оказалось всего 11), легко подсчитать число различных разбиений F7 на совершенные коды длины 7:

Утверждение 2. Существует Л47 = 27360 > 1.66 ■ 214 различных разбиений F7 на совершенные коды длины 7.

На основе этого утверждения доказана

Лемма 18. Число Мц различных разбиений F15 на совершенные коды ранга не больше 12 удовлетворяет следующей нижней оценке: Mis > 2147.

Утверждение 2 и лемма 18 позволяют сделать вывод, что полученная ранее, см. [1, 16], нижняя оценка числа Л4п различных разбиений пространства Fn на совершенные коды длины п,п > 15, справедлива

п-1 г>-3

для всех допустимых длин п > 7: Л4п > 22^г~ • 22^*~.

В разделе 3.2 изучается каскадная конструкция, являющаяся частным случаем каскадного метода построения разбиений, введённого в 2001 г. в статье [8], и исследуется класс разбиений Fn ранга не более п — log (n + 1) + 2.

Основываясь на известных асимптотиках числа различных расширенных кодов Хэмминга и числа четверичных MDS кодов, доказана

Теорема 13. Для числа М^ различных разбиений FN на расширенные совершенные коды длины N > 16 ранга не больше N — log N + 1

-л ЛЛ ^ 02Т-1 2^+log(N+8)-2

верна следующая нижняя оценка: Л1дг > / • ¿ -о

2f-[log£]-21og^-logf+2>

Извлекая квадратный корень из оценки теоремы 13, получим нижнюю оценку числа различных разбиений F" малого ранга

Следствие 4. Для числа Л4п различных разбиений Fn на совершенные коды длины п > 15 pajiza не больше п — log (п + 1) +2 вер-

и к А \ огт^ o2Iif5+logT 02nTU+1°s<"+9>

на следующая нижняя оценка: ЛЛп > ¿ ■ ¿ ■ á

В разделе 3.3 изучается конструкция, основанная на методе ijfc-компопснт. Впервые аналогичная конструкция была предложена в 2007 г. в работе [1] для построения разбиений на попарно неэквивалентные совершенные коды, но не было исследовано многообразие возможных конструируемых разбиений и не был проведён подсчёт числа различных разбиений. Результирующие разбиения имеют ранг не больше п — log (n 4- 1) 4- 2. С помощью данного метода получена следующая нижняя оценка числа различных разбиений пространства F" на совершенные коды малого ранга:

Теорема 14. Число Л4п различных разбиений пространства Fn на совершенные коды длины п ранга не больше п — log (п + 1) + 2 удовлетворяет следующей нижней оценке

Мп > 22 V ■ б2^

для любого допустимого п >7.

Результаты третьей главы опубликованы в [18, 21, 24, 25].

В приложениях А, В, С диссертации приводятся результаты компьютерных исследований, проведённых как с помощью системы компьютерной алгебры Magma, так и с помощью компьютерной программы автора диссертации (см. приложение С в диссертации для главы 2).

Результаты раздела 1.2 получены совместно с И. Ю. Могильных и Ф. И. Соловьёвой, см. [20, 27]. Результаты раздела 3.3 и компьютерные исследования с использованием системы компьютерной алгебры Magma были проведены автором диссертации. Остальные результаты получены совместно с Ф. И. Соловьёвой.

Автор выражает глубокую искреннюю признательность своему научному руководителю д.ф.-м.н. проф. Ф. И. Соловьёвой, под руководством которой была выполнена эта работа.

Литература

1. Августинович С. В., Соловьёва Ф. И., Хедеп О. О разбиениях п-куба на неэквивалентные совершенные коды // Пробл. передачи информ.

- 2007. - Т. 43, Р 4. - С. 45-50.

2. Васильев Ю. Л. О пегрунповых плотно упакованных кодах // Проблемы кибернетики. — М: Физматгиз. — 1962. — № 8. — С. 337-339.

3. Зиновьев В. А., Леонтьев В. К. О совершенных кодах // (Препринт ИППИ АН СССР). - 1972. - Вып. 1. - С. 26-35.

4. Зиновьев В. А., Леонтьев В. К. Несуществование совершенных кодов над полями Галуа // Проблемы управления и теории информации. — 1973. - Вып. 2. - С. 123-132.

5. Соловьёва Ф. И. О построении транзитивных кодов // Проблемы передачи информации. — 2005. — Вып. 3. — С. 23-31.

6. Соловьёва Ф. И. О транзитивных разбиениях n-куба на коды // Проблемы передачи информации. — 2008. — Т. 44, № 4. — С. 27-35.

7. Соловьёва Ф. И. Комбинаторные методы построения и исследования кодов (докторская диссертация). - 2008. — 202 С.

8. Avgustinovich S. V., Lobstein A. and Solov'eva F. I. Intersection matrices for partitions by binary perfect codes // IEEE Trans. Inform. Theory. — 2001. - Vol. 47, N 4. - P. 1621-1624.

9. Borges J., Mogilnykh I. Yu., Rifa J. K., Solov'eva F. I. Structural properties of binary propelinear codes // Advances in Math, of Commun.

- 2012. - Vol. 6, N 3. - P. 329-346.

10. Heden O., Solov'eva F. I. Partitions of Fn into nonparallel Hamming codes // Advances in Math, of Communications. — 2009. — Vol. 3, N 4.

- P. 385-397.

11. Krotov D. S., Avgustinovich S. V. On the number of 1-perfect binary codes: A lower bound // IEEE Trans. Inf. Theory. - 2008. - Vol. 54, N 4. - P. 1760-1765.

12. MacWilliams F. G., Sloane N. J. A. The theory of error correcting codes /1 New York: North-Holland. — 1977. — P. 744. (Русский перевод: Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки: Пер. с англ. // Москва: Связь. — 1979. — 744 С.)

13. Mallard M. A generalized parity function and its use in the construction of perfect codes // SIAM J. Alg. Discrete Math. - 1986. - Vol. 7, N 1.

- P. 113-115.

14. Ostergard P. R. J., Pottonen 0. The Perfect Binary One-Error-Correcting Codes of Length 15: Part I - Classification // IEEE Trans. Inform. Theory. - 2009. - Vol. 55. - P. 4657-4660. Codes at arXiv:0806.2513v3.

15. Phelps К. T. An enumeration of 1-perfect binary codes // Australas. J. Comb. - 2000. - Vol. 21. - P. 287-298.

16. Solov'eva F. I. On perfect codes and related topics // Com2Mac Lecture Note Seriesl3. - Pohang. - 2004. - 80 P.

Публикации автора по теме диссертации Публикации в научных журналах

17. Соловьёва Ф. И., Гуськов Г. К. О построении вершинно-транзитив-ных разбиений n-куба на совершенные коды // Дискретный анализ и исследование операций. — 2010. - Т. 17, № 3. — С. 84 - 100.

18. Гуськов Г. К. О разбиениях двоичного векторного пространства на совершенные коды // Дискретный анализ и исследование операций.

- 2013. - Т. 20, 2. - С. 15-25.

19. Гуськов Г. К., Соловьёва Ф. И. О предельно-транзитивных расширенных совершенных кодах // Дискретный анализ и исследование операций. - 2013. - Т. 20, Л"» 5. - С. 31-44.

20. Guskov G. К., Mogilnykh I. Ум., Solov'eva F. I. Ranks of propelinear perfect binary codes // Siberian Electronic Mathematical Reports. — 2013. - Vol. 10. - P. 443-449.

Труды конференций

21. Гуськов Г. К. О числе различных разбиений куба Е15 на совершенные двоичные коды // Материалы 47 Международной научной студенческой конференции "Студент и научно-технический прогресс". — Новосибирский государственный университет. — 2009. — 235 с. — С. 160.

22. Гуськов Г.К., Соловьева Ф.И. О рангах и ядрах совершенных двоичных транзитивных кодов. // Материалы VII молодежной школы по дискретной математике и её приложениям, М. Изд-во ИПМ РАН. — Москва, 18-23 мая 2009. - Часть I. - С. 23-28.

23. Solov'eva F.I., Guskov G.K. On vertex-transitive and 2-transitive partitions of Fn into perfect codes // Proc. XII Int. Symposium on problems of Redundancy in Information and Controls Systems. St.-Petersburg, Russia. — May, 26-30, 2009. - P. 104-108.

24. Гуськов Г. К., Соловьева Ф.И. О разбиениях n-куба на совершенные двоичные коды / / Международная конференция "Современные проблемы математики, информатики и биоинформатики" (ISBN 978-5-905569-03-6). Россия, Новосибирск, 11 - 14 октября, 2011. — С. 65. — http://conf.nsc.ru/files/ conferences/LyaplOO/fulltext/74556/74659/Guskov.Soloveva. LowcrBoundPartitions.pdf

25. Гуськов Г. К., Соловьёва Ф. И. Об одной каскадной конструкции разбиений n-куба на совершенные двоичные коды // Тр. международной конф. "Информационные технологии и системы". Россия, Петрозаводск, 19 - 25 августа. - М: ИППИ РАН. — 2012. - С. 124-128.

26. Гуськов Г. К., Соловьёва Ф. И. Существование расширенных совершенных транзитивных в узком смысле кодов // Мальцевские чтения — 12-16 ноября 2012. — Новосибирск. - С. 25.

27. Guskov G. К., Mogilnykh I. Yu., Solov'eva F. I. Rank Spectrum of Propelinear Perfect Binary codes // IEEE International Symposium on Information Theory (ISBN 978-1-4799-0445-7). Istanbul, Turkey. - July 7-12, 2013. - P. 879-881.

Гуськов Георгий Константинович

Транзитивные совершенные коды и разбиения

Автореферат диссертации на соискание учёной степени кандидата физико-математических наук

Подписано в печать 23.10.2013 г. Печать цифровая. Бумага офсетная. Формат 60x84/16. Усл. печ. л. 1,1. Тираж 100 экз. Заказ № 179

Отпечатано в типографии "Срочная полиграфия" ИП Малыгин Алексей Михайлович 630090, Новосибирск, пр-т Академика Лаврентьева, 6/1, оф.104 Тел. (383) 217-43-46, 8-913-922-19-07

Текст научной работы диссертации и автореферата по математике, кандидата физико-математических наук, Гуськов, Георгий Константинович, Новосибирск

АКАДЕМИИ НАУК

04201451258 на Правах руКОписи

Гуськов Георгий Константинович

Транзитивные совершенные коды и

разбиения

Специальность 01.01.09 — дискретная математика и математическая

кибернетика

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель: д.ф.-м.н., профессор Ф. И. Соловьёва

Новосибирск - 2013

Оглавление

Введение 4

1 Транзитивные совершенные коды 29

1.1 Предельно-транзитивные коды................................30

1.1.1 Транзитивные совершенные коды длины 15 и транзитивные расширенные совершенные коды длины 16 30

1.1.2 Бесконечная серия предельно-транзитивных кодов . 33

1.2 Проблема рангов транзитивных кодов........................42

1.2.1 Пропелинейные совершенные коды длин 15 и 31 полного ранга............................................43

1.2.2 Проблема рангов........................................46

2 Вершинно-транзитивные разбиения 50

2.1 Вспомогательные утверждения................................51

2.2 Конструкции вершинно-транзитивных разбиений ..........53

2.2.1 Конструкция А..........................................54

2.2.2 Конструкция В..........................................58

2.3 Нижние оценки..................................................62

3 Конструкции разбиений пространства ^ на совершенные коды 67

3.1 Конструкция Васильева и разбиения на совершенные коды длины 15 ........................................................68

3.2 Каскадная конструкция........................................72

3.3 Конструкция ijк-компонент. Нижняя оценка числа раз-

личных разбиений на совершенные коды ....................76

Заключение 85

Приложения 86

А Ранги и ядра транзитивных кодов длин 15 и 16 86

В Нетранзитивные координаты транзитивных кодов длины 16 99

С Матрицы пересечений разбиений пространства F7 на коды Хэмминга длины 7 102

Литература 108

Введение

Двоичные коды являются одним из основных объектов исследования теории кодирования и служат базой для дальнейшего развития современных цифровых технологий. С 1949 года, с фундаментальных работ К. Шеннона по теории информации, началось бурное развитие теории кодирования как самостоятельной научной дисциплины, наряду с крип-тологией и сжатием информации, без которых был бы невозможен сегодняшний уровень развития коммуникационных технологий.

Совершенный код, исправляющий одиночные ошибки, задаёт разбиение всего пространства на совокупность шаров радиуса 1 с центрами в кодовых словах. Из данного факта следует важное свойство совершенных кодов - их оптимальность, то есть, при заданной длине кода и кодовом расстоянии мощность всякого совершенного кода максимальна. Раздел теории кодирования, посвящённый построению и исследованию свойств совершенных кодов настолько богат, что, помимо свойств самих кодов, интерес представляют также методы их исследования. Заметим, что задача упаковки пространства шарами фиксированного радиуса важна с точки зрения целого ряда других математических дисциплин: комбинаторного анализа, криптологии, теории групп, теории графов, топологии. Таким образом, результаты теории кодирования могут быть использованы для решения задач в смежных областях дискретной математики.

Например, коды с богатыми группами автоморфизмов могут быть использованы в криптографии.

Проблема исследования разбиений пространства IFn (векторного пространства длины п над GF(2) по отношению к метрике Хэмминга) на совершенные коды тесно связана с проблемой построения таких кодов и изучения их свойств, поскольку асимптотики двойных логарифмов (если они существуют) числа различных совершенных кодов и числа различных разбиений на такие коды совпадают. Также следует упомянуть о том, что некоторые разбиения пространства Fn индуцируют раскраски векторов Fn на коды, связанные с оптоволоконными сетями, см., например, работу [36]. Кроме того, совершенные коды являются частным случаем так называемых регулярных разбиений, в англоязычной литературе известных также как equitable partitions, а в отечественной литературе больше известных как совершенные раскраски. Наряду с дистанционно регулярными графами и схемами отношений, совершенные раскраски являются популярными объектами алгебраической комбинаторики, см. [19]. Различные методы построения разбиений могут быть использованы для исследования их нетривиальных свойств, а также для построения новых кодов, в частности, совершенных (такие методы, например, описаны в работе [14]). Важность поиска новых методов построения кодов, а также методов их задания, объясняется, в частности, тем, что на их основе можно разрабатывать новые, более эффективные, методы передачи информации, или криптографические системы-коды.

7, а также при п — 11 - троичный код Голея с кодовым расстоянием 5. Оба кода Голея единственны с точностью до эквивалентности, в то время как существует дважды экспоненциальное число неэквивалентных совершенных кодов с кодовым расстоянием 3. Классификация расширенных совершенных двоичных кодов длины 16 и совершенных двоичных кодов длины 15, была получена П. Остергардом и О. Поттоненом в 2009 г. в работе [37].

Цель данной диссертации состоит в исследовании конструкций совершенных кодов и разбиений пространства Fn на совершенные коды, а также в применении этих конструкций для изучения свойств разбиений и кодов. В работе будут рассматриваться только двоичные коды и разбиения на такие коды.

В диссертации используются известные методы и аппарат алгебраической и комбинаторной теории кодирования, комбинаторного анализа.

Все результаты, представленные в диссертации, являются новыми.

1. В диссертации продолжено развитие метода локального анализа из [17]. С его помощью установлено существование 5 бесконечных серий неэквивалентных предельно-транзитивных расширенных совершенных кодов. Для доказательства предельной транзитивности в работе предложено использовать свойства Паш-конфигураций систем троек Штейне-ра, соответствующих проверяемым кодам. Неэквивалентность кодов для каждой фиксированной длины была доказана с помощью сравнения значений их рангов и размерностей ядер. Впервые такой код длины 16 был обнаружен С. А. Малюгиным [10] в 2004 г. С помощью системы компьютерной алгебры MAGMA [27] найдены все транзитивные расширенные совершенные коды длины 16, имеющие хотя бы одну нетранзитивную координату. Проверка кода на транзитивность заключалась в проверке на транзитивность соответствующей ему структуры инцидентности.

2. В диссертации впервые исследуется спектр рангов пропелинейных кодов. Для этого были использованы методы построения транзитивных кодов из [15], основанные на конструкциях Моллара и Васильева для со-

вершенных кодов. Тот факт, что конструкция Моллара сохраняет про-пелинейность исходных кодов, был доказан в [25]. Зависимость ранга результирующего кода от рангов исходных кодов для конструкции Моллара была доказана в [15]. С помощью системы компьютерной алгебры MAGMA впервые были обнаружены пропелинейные коды длин 15 и 31 полного ранга. В ходе компьютерных исследований рассматривались только нормализованные пропелинейные структуры, данное понятие было введено в [25].

3. Продолжено исследование транзитивных разбиений пространства Fn на совершенные двоичные коды, начатое в [16]. В данной диссертации впервые исследованы вершинно-транзитивные разбиения пространства Fn. С помощью компьютерных исследований проверены транзитивность, 2-транзитивность и вершинная транзитивность 11 неэквивалентных разбиений длины 7, классифицированных К.Т. Фелпсом в [40]. Было показано, что конструкции транзитивных разбиений на двоичные коды, введённые в [16], могут применяться для построения 2-транзитивных и вершинно-транзитивных разбиений. Впервые получена нижняя оценка числа неэквивалентных разбиений для каждого из этих классов кодов. В качестве критерия неэквивалентности полученных разбиений использовались их матрицы пересечений, аналогичный метод был применён в [21]. Была найдена зависимость матриц пересечений разбиений, полученных с помощью рассмотренных конструкций от матриц пересечений исходных разбиений.

4. С целью построения разбиений пространства Fn на совершенные двоичные коды малого ранга предложено развитие свитчингового метода, предложенного C.B. Августиновичем и Ф.И. Соловьёвой в 1996 году для построения широкого класса двоичных совершенных кодов. Также предложены модификации конструкций разбиений на совершенные коды, основанные на конструкциях Васильева (см. [32,48]) и Фелпса (см. [21]). Проведён сравнительный анализ семейств кодов, соответствующих трём данным конструкциям и показано, что нижняя оценка числа

различных разбиений пространства Fn на совершенные двоичные коды малого ранга, полученная с помощью конструкции ¿^-компонент, является лучшей на сегодняшний день почти для всех допустимых длин кодов.

Работа носит теоретический характер. Полученные в ней результаты могут быть применены в теории кодов, исправляющих ошибки: для дальнейшего исследования и построения новых классов двоичных кодов, для построения совершенных кодов полного ранга, кодов с большими кодовыми расстояниями, для исследования разбиений пространства Fn на совершенные коды.

Все результаты диссертационной работы были апробированы на следующих конференциях: на XII международном симпозиуме по проблемам избыточности в информационных системах (С.-Петербург, Россия, 2009 г.); на VII молодёжной школе по дискретной математике и её приложениям (Москва, Россия, 2009 г.); на международной конференции по алгебраической комбинаторике и её приложениям АЬСОМА-Ю (Тыр-нау, Германия, 2010 г.); на международной конференции "Современные проблемы математики, информатики и биоинформатики" (Новосибирск, Россия, 2011 г.); на XXV конференции молодых учёных и специалистов "Информационные технологии и системы - 2012" (Петрозаводск, Россия); на международной конференции "Мальцевские чтения" (Новосибирск, Россия, 2012 г.); на международном симпозиуме по теории информации ШГГ 2013(Стамбул, Турция, 2013 г.).

Основное содержание диссертации отражено в 11 печатных работах. Среди них 4 работы в журналах из перечня ВАК, 3 работы в рецензируемых трудах международных конференций.

Основные результаты диссертации.

1. Получено (конструктивно) 5 бесконечных серий неэквивалентных

предельно-транзитивных расширенных совершенных двоичных кодов любой возможной длины, начиная с шестнадцати.

2. Решена проблема рангов для пропелинейных совершенных двоичных кодов, за исключением случаев кодов полного ранга для длин 63,127, 2047 и кодов длины 127 предполного ранга.

3. Предложены конструкции транзитивных, 2-транзитивных и вершинно-транзитивных разбиений для любой допустимой длины, получены нижние оценки числа неэквивалентных таких разбиений.

Расстояние Хэмминга с1(х,у) между двумя произвольными векторами х и у пространства Е™ определяется как число координатных позиций, в которых эти векторы различаются. Вес вектора - это число его ненулевых координат. Произвольное подмножество пространства ¥п называется двоичным кодом длины п. Векторы из ¥п, принадлежащие коду, называются кодовыми словами. Код С из ¥п называется совершенным двоичным кодом, исправляющим одиночные ошибки (далее кратко совершенным кодом), если каждый вектор пространства Fn находится на расстоянии не больше 1 от некоторого единственного вектора из С. Как было отмечено ранее, такие коды существуют только при п = 2т — 1, т > 2. Кодовым расстоянием кода называется наименьшее из расстояний Хэмминга между всеми его попарно различными кодовыми словами. Если код содержит нулевое кодовое слово, его называют приведённым. Код называется линейным, если он является подпространством Линейный совершенный код называется кодом Хэмминга. Известно, что для фиксированного п код Хэмминга длины п единствен с точностью до изоморфизма.

Ядро приведённого кода С состоит из всех кодовых слов х £ С таких,

что х + С = С. Размерность линейной оболочки множества всех кодовых слов приведённого кода называется рангом кода. Размерность ядра и ранг приведённого кода С обозначаются через к (С) и г (С), соответственно. Известно, что ранг и размерность ядра кода Хэмминга равны п — 1од{п +1), ранги совершенных (расширенных совершенных) кодов длины п (длины п +1) могут принимать значения от п — login + 1) до п. Здесь и далее log обозначает логарифм по основанию 2. Если ранг совершенного (расширенного совершенного) кода длины п (длины N = п+1) равен 71, его называют кодом полного ранга.

Пусть С - произвольный совершенный код. Через ST(C) будем обозначать систему троек кода С, то есть ST(C) = {и + v\u,v £ С : w{u + v) = 3}. Соответственно, для произвольного расширенного совершенного кода С через SQ(C) будем обозначать систему четвёрок, то есть SQ(C) = {и + v\u, v Е С : w(u + v) = 4}.

Известно, что группа автоморфизмов пространства ¥п исчерпывается всеми изометриями Fn, каждая такая изометрия определяется подстановкой 7г на множестве координат и сдвигом на произвольный вектор v G Fn. Группа автоморфизмов Aut(Fn) пространства Fn определяется как

Aut(Fn) = {(t>, 7г) |i;eFn, TTGSn},

где Sn — симметрическая группа подстановок порядка п. Множество всех перестановок координатных позиций, сохраняющих код С, называется группой симметрий кода С и обозначается через Sym(C). Группой автоморфизмов Aut(C) кода С длины п называется группа изометрий пространства Fn, переводящих код в себя. Говорят, что два произвольных кода С и D эквивалентны, если существует такая изометрия ip пространства Fn, что С = ip{D).

что (х,тгх) «Е Аи^С), то есть х + С = 7гх(С), где пх может не принадлежать группе симметрий Эут(С) = {тт Е Зп | 7г(С) = С} кода С. Таким образом, в транзитивном приведённом коде для любого его кодового слова х найдётся автоморфизм {х, ттх) € Аи^С), переводящий слово х в нулевое кодовое слово. Легко видно, что оба этих определения эквивалентны.

Кодовое слово х из нетранзитивного кода С, для которого не существует такой подстановки ттх, будем называть нетранзитивным кодовым словом. Координатную позицию транзитивного расширенного совершенного кода назовём нетранзитивной, если код, полученный её выкалыванием, нетранзитивен.

Для полноты изложения результатов диссертации потребуются конструкция Васильева (см. [4]) и, являющаяся её обобщением, конструкция Моллара (см. [35]). Приведём их определения.

Конструкция Васильева. Пусть С - совершенный двоичный код длины п. Пусть А - произвольная функция, определённая на кодовых словах С и принимающая значения из множества {0,1}. Пусть |а;| = XI Н-----1- хп, где х = (х1,..., хп), х% е {0,1}. Код

ные совершенные коды длин ¿и т соответственно. Пусть х = (хп,..., х1т, £21, • • ■, .. .,хц,..., хш) £ ¥ш. Определим две функции р\(х) и ^(зО, называемые обобщёнными проверками на чётность, следующим образом:

с2п+1 = {(х + у, \х\ + А (у),х) I хе¥п,уеС}

называется совершенным кодом Васильева долины 2п+ 1. Конструкция Моллара. Пусть С1 и Ст -

<т

произволь-

(1)

где аг --

Сь в ¥т. Множество

М(С1,Ст) = {(х,у + Р1(х),г + р2(х) + /Ы) I X € Г",

у е С\г<= Ст}

называется совершенным двоичным кодом Моллара длины п = tm + Ь + т.

Заметим, что в обозначение Л4(ССт) включены исходные коды С1 и где верхние индексы ¿и т указывают длины этих кодов, соответственно. Ясно, что могут найтись такие и ттт/, что совершенный код АЛ{С1',Ст') будет иметь те же параметры, что и код Л4(С^Ста), Оба этих кода могут как совпадать, так и быть различными, более того, они могут быть неэквивалентными.

Первая глава диссертации посвящена исследовани