Группы автоморфизмов кодов Хэмминга и их компонент тема автореферата и диссертации по математике, 01.01.09 ВАК РФ



На правах рукописи

ГОРКУНОВ Евгений Владимирович

ГРУППЫ АВТОМОРФИЗМОВ кодов ХЭММИНГА И ИХ КОМПОНЕНТ

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

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

1 1 НОЯ 2010

Новосибирск — 2010

004612363

Работа выполнена в Новосибирском государственном университете

Научный руководитель:

доктор физико-математических наук, профессор Соловьёва Фаина Ивановна

Официальные оппоненты:

доктор физико-математических наук, профессор Дьячков Аркадий Георгиевич, кандидат физико-математических наук Пережогин Алексей Львович

Ведущая организация:

Санкт-Петербургский государственный университет аэрокосмического приборостроения

Защита состоится 10 ноября 2010 г. в 15 часов 00 минут на заседании диссертационного совета Д 003.015.01 при Институте математики им. С. Л. Соболева СО РАН по адресу: пр. Академика Коптюга, 4, Новосибирск, 630090.

С диссертацией можно ознакомиться в библиотеке Института математики им. С. Л. Соболева СО РАН и в библиотеке Новосибирского государственного университета.

Автореферат разослан 8 октября 2010 г.

Учёный секретарь диссертационного совета

доктор физико-математических наук Ю.В. Шамардин

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

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

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

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

Группа автоморфизмов кода помогает детально прояснить внутреннюю структуру кода. Действуя на множестве кодовых слов, группа автоморфизмов кода позволяет понять, какие его части имеют одинаковое строение, а какие существенно различ-

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

Таким образом, группы автоморфизмов кодов имеют актуальные приложения. Вместе с тем их исследование — нетривиальная,- а подчас и трудная задача. В двоичном кубе , называемом также булевым, изометрйи исчерпываются перестановками позиций координат и сдвигами пространства на вектор. В общем случае это не так. Если д ^ 5, то не все изометрии пространства Р" могут быть выражены в терминах операций поля.

Неко торую аналогию с двоичным случаем имеют линейные коды в Р": В группе автоморфизмов линейного кода имеются полулинейные симметрии пространства и сдвиги на векторы. Полулинейные симметрии описываются при помощи операций поля и ег'о автоморфизмов из группы Галуа Са1(Рд). Поскольку Именно линейные или эквивалентные им коды используются на практике, то при рассмотрении автоморфизмов кодов часто1 имеет смысл ограничиться указанными видами преобразований. Однако при д ^ 4 все возможные композиции полулинейных симметрий и сдвигов на векторы порождают собственную подгруппу группы автоморфизмов пространства

Существуют многочисленные примеры нетривиальных линейных кодов, которые имеют автоморфизмы, не являющиеся ни линейными, ни даже полулинейными. Кроме того, к настоящему времени построены классы нелинейных кодов, которые представляют интерес для практики. Среди этих кодов можно выделить, например, ^2^4-линейные, ^-линейные, ДНК-коды и другие. Исследование групп автоморфизмов подобных кодов требует разработки новых методов.

В диссертации исследуются группы автоморфизмов кода Хэмминга над произвольным конечным полем, группы моно-миальных автоморфизмов различных компонент кода Хэмминга, активно используемых при построении и изучении кодов. Строение этих компонент, как и всего кода Хэмминга, тесно связано с проективными геометриями над полями Галуа.

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

Цель настоящей работы состоит в исследовании и полном описании группы автоморфизмов д-ичного кода Хэмминга, а также его подкодов, называемых компонентами, которые играют существенную роль как в изучении свойств совершенных кодов над конечными полями, так и в построении таких кодов.

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

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

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

Кодовые слова веса 3 в коде Хэмминга образуют так называемую обобщённую систему троек Штейнера. Это означает, что для любой пары координат найдётся единственная тройка, содержащая эту пару. Зафиксировав, например, 1 в первой координате троек, можно проследить за действием произвольной изометрии на любое значение всякой другой координаты. Такая техника позволила исследовать симметрии кода Хэмминга и мономиальные автоморфизмы его компонент. В числе прочих рассмотрены ^''-компоненты, которые предложены как обобщение линейной и простой компонент кода Хэмминга.

Впервые исследована группа перестановочных автоморфизмов РАиЦН) кода Хэмминга И при д > 2. Из ранее известных фактов (см. [18, теорема 7.1]) следует, что эта группа изоморфна стабилизатору множества столбцов проверочной матрицы кода Л по действию группы умножением на эти столбцы. Прямой проверкой для кода Хэмминга с проверочной матрицей в канонической форме удалось показать, что этот стабилизатор равен унитреугольной группе С/Тт(д). Вместе с тем выяснилось, что если Нс — циклический код Хэмминга, то РАи(;(Нс) ^ иТт(д), поскольку порядок циклической подгруппы ¥А.иЬ(Нс), равный длине кода п, не делит \иТт(д)\. Тем самым установлено, что разные коды Хэмминга неожиданно могут иметь неизоморфные группы перестановочных автоморфизмов несмотря на то, что все эти коды эквивалентны.

В настоящей работе продолжено исследование инвариантов двоичных кодов, которое ранее проводилось рядом авторов. Одним из наиболее сильных оказался набор размерностей подкодов, см. [1,4]. Здесь под размерностью кода понимается размерность минимальной грани булева куба, содержащей этот код. Оказалось, что этот инвариант избыточен для эквивалентности кодов и его можно ослабить, оставив лишь размерности подкодов чётной мощности. В итоге получены новые неулучша-емые достаточные условия эквивалентности двоичных кодов.

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

Апробация работы. Все результаты диссертации были доложены на следующих международных конференциях: 11-я и 12-я Международные конференции по алгебраической и комбинаторной теории кодирования (АССТ'2008, Пампорово, Болгария, 2008 г.; АССТ'2010, Новосибирск, 2010 г.); XVII Международная школа-семинар „Синтез и сложность управляющих систем" им. ак. О. Б. Лупанова (Новосибирск, 2008 г.); XII Международный симпозиум по проблемам избыточности в информационных и управляющих системах (Redundancy 2009, Санкт-Петербург, 2009 г.); Мальцевские чтения 2009 и 2010 (Новосибирск, 2009, 2010 гг.); 32-я Конференция молодых учёных и специалистов „Информационные технологии и системы" (ИТиС'09, Бекасово, Россия, 2009 г.); Международная конференция по вычислительным технологиям в разработке электротехники и электроники (SIBIRCON 2010, Иркутск, 2010 г.). Результаты, изложенные в диссертации, были представлены на семинарах Института математики им. C.JI. Соболева и НГУ „Теория кодирования" и „Дискретный анализ".

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

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

1. Доказано, что все симметрии д-ичных кодов Хэмминга являются полулинейными. Получено описание группы автоморфизмов этих кодов.

2. Для «7-ичного кода Хэмминга с проверочной матрицей в канонической форме показано, что его группа перестановоч-

ных автоморфизмов изоморфна унитреугольной группе. Обнаружены коды Хэмминга с неизоморфными группами перестановочных автоморфизмов.

3. Описана структура групп мономиальных автоморфизмов различных компонент д-ичного кода Хэмминга: простой, линейной и //-компоненты.

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

Объём и структура диссертации. Диссертация состоит из введения, 3 глав и списка литературы (65 наименований), в конце приведён список публикаций автора по теме диссертации. Объём диссертации — 78 страниц.

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

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

Код, образующий подпространство размерности к в пространстве Р™, называется линейным или [п, /с]-кодом. Наименьшее ненулевое расстояние между кодовыми словами из С обозначается (1 = <1(С) и называется кодовым расстоянием.

Если шары фиксированного радиуса £ ^ 0 с центрами в кодовых словах из С образуют разбиение пространства Е™, то код называется совершенным. В. А. Зиновьев и В. К. Леонтьев [9], а также независимо А. Титвайнен [24] в точности указали набор параметров, которые может иметь нетривиальный совершенный код над такой код либо исправляет одну ошибку, либо эквивалентен двоичному или троичному кодам Голея, исправляющим 3 или 2 ошибки соответственно.

Далее термин совершенный означает код с кодовым расстоянием 3, то есть исправляющий одну ошибку. Из условия

плотной упаковки (разбиения пространства F" шарами радиуса 1), такой код имеет длину п = qqSi ■ Единственным линейным совершенным кодом является код Хэмминга. Тем не менее, существует множество нелинейных совершенных д-ичных кодов, впервые построенных Ю. Л. Васильевым [8] для q = 2, а позднее — многими другими авторами для q = рг > 2 (см., например, лекции Ф. И. Соловьёвой [22]).

A.A. Марков в 1956 г. показал [12], что группа изометрий пространства F™ представляет собой полупрямое произведение

Aut(FJ) = X = {(тг; а) | тг е 5„, о- G .

Иначе говоря, каждая изометрия F™ представляется в виде пары (тг; а), где подстановка тг £ Sn переставляет координаты вектора х £ F™, в то время как а = (ау,... ,ап) есть набор, в котором каждая подстановка Oi € Sq действует на элементах поля Fg и в соответствии с этим изменяет значение координаты Xi- Набор er называется конфигурацией.

В этих терминах группой автоморфизмов кода С называется группа Aut(C) изометрий пространства F™, отображающих код С в себя. Автоморфизмы вида (я, е), где е — тождественная конфигурация, образуют подгруппу PAut(C) ^ Aut(C), называемую группой перестановочных автоморфизмов кода С.

Автоморфизм F™, заданный умножением векторов на моно-миальную матрицу, называется мономиалъным. Группа моно-миальных автоморфизмов кода С обозначается MAut(C).

Стабилизатор нулевого вектора в группе Aut(C) назовём группой симметрий кода С и обозначим через Sym(C). Отметим, что для двоичных кодов Sym(C) — MAut(C) = PAut(C). Кроме того, изометрия F™ является симметрией тогда и только тогда, когда она сохраняет вес произвольного вектора.

Поскольку сдвиг линейного кода С С F™ на принадлежащий ему вектор даёт в результате тот же самый код, то легко доказать известное соотношение Aut(C) = Sym(C) X С. Таким образом, в группе автоморфизмов линейного кода существенную часть представляют его симметрии.

Напомним, что функция /: F™ —> F" называется полулинейной с сопутствующим автоморфизмом 7 £ Gal(F,;), если

для любых а, /3 € и х, у С выполняется

/(ах + /Зу) = 7 (а)/(х) + 7 Ш(у)-

Группа полулинейных симметрии [п, п — ш]-кода с кодовым расстоянием й ^ 3 изоморфна некоторой подгруппе общей полулинейной группы ГЬт(д) = Са1(Р9) X СЬт(д). В частности, хорошо известно, что группа полулинейных симметрий кода Хэмминга Л длины п = изоморфна группе ГЬт(д), см. [18, теорема 7.2].

При д е {2,3} имеем Эут^) = МАи^Е^), так что справедливы соотношения

Бут[Н)^СЬт{д) и АЩН) £ Ыт{д) X П.

При д ^ 4 полулинейные симметрии пространства Р™ порождают собственную подгруппу группы Зут(¥"). Возникает естественный вопрос, будет ли при любом ц ^ 4 выполняться соотношение

АиЬ(Н) = Пт{д) ¿П.

В настоящей диссертации даётся положительный ответ на этот вопрос.

В первой главе представлены результаты исследования автоморфизмов д-ичного кода Хэмминга.

В параграфе 1.1 приводятся определения группы автоморфизмов кода, а также некоторых её подгрупп. Указываются связи между автоморфизмами кодов, подстановками симметрической группы и матрицами над конечными нолями. Необходимо отметить, что используемое в настоящей работе определение группы автоморфизмов кода согласуется с определением И. Константинеску и В. Хайзе [17] и отличается от традиционного, включая в рассмотрение все изометрии пространства Такой подход представляется целесообразным, в особенности для изучения автоморфизмов нелинейных кодов, практическое применение которых становится всё более актуальным.

В параграфе 1.2 излагаются известные факты о строении групп автоморфизмов линейных кодов. Также здесь содержатся замечания, раскрывающие характер действия полулинейных симметрий на векторы пространства Р™.

В параграфе 1.3 исследуется группа перестановочных автоморфизмов д-ичных кодов Хэмминга, где д > 2. В отличие от случая двоичных кодов перестановочные автоморфизмы пространства Р™ при д > 3 образуют собственную подгруппу его группы симметрий. Поэтому группа перестановочных автоморфизмов о-ичного кода представляет самостоятельный интерес.

„ .ш _ 1

Рассматривается код Хэмминга длины п = с прове-

рочной матрицей в каноническом виде, то есть столбцы которой имеют 1 в качестве первого ненулевого элемента и которую можно построить для любого целого 771 ^ 2. Доказано, что группа перестановочных автоморфизмов такого кода изоморфна унитреугольной группе матриц иТт{ц) (теорема 5). Показано, что группа перестановочных автоморфизмов циклического кода Хэмминга не может быть изоморфна 1/Тт(д) (утверждение 1). Как следствие, получено, что при д > 2 группы перестановочных автоморфизмов различных кодов Хэмминга могут быть неизоморфны друг другу (следствие 1).

Говоря неформально, перестановочные автоморфизмы вращают пространство вокруг прямой = ... = хп. Результаты параграфа 1.3 показывают, что при д > 2 коды Хэмминга имеют различную симметрию относительно этой прямой.

В параграфе 1.4 доказано, что любая симметрия кода Хэмминга над полем является полулинейной. Это доказательство проводится методом локального анализа, систематически разработанным Ф.И. Соловьёвой [14]. Он состоит в том, что сначала исследование рассматриваемого вопроса проводится на локальном фрагменте кода, например, на множестве кодовых слов веса 3. Затем проверка выполнимости обнаруженных свойств тем или иным образом распространяется на весь код.

В силу того, что симметрии пространства Р™ сохраняют вес любого вектора, справедливо соотношение Зут(>£) ^ 8ут(Г), где Т С И — подкод, образованный тройками кода Хэмминга. Доказано, что все симметрии множества троек Т полулинейны (леммы 5-7). Отсюда следует полулинейность симметрий кода Хэмминга. Таким образом получено описание группы автоморфизмов д-ичных кодов Хэмминга (теорема 6).

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

Во второй главе исследуются группы мономиальных автоморфизмов различных компонент g-ичного кода Хэмминга. Компоненты кода Хэмминга — это специальные его подкоды, которые могут быть сдвинуты по некоторой фиксированной координате г, в результате чего из кода Хэмминга получается другой совершенный код с теми же параметрами. Конструирование совершенных кодов сдвигами линейных компонент получило название метода ¿-компонент и восходит к работам Ю.Л. Васильева, который первым обнаружил нелинейные совершенные двоичные коды [8].

В настоящей диссертации рассматриваются компоненты кода Хэмминга, образованные линейной оболочкой множества его кодовых слов веса три с 1 в фиксированной ¿-й координате, которая (оболочка) взята над полем Fg, его простым подиолем Fp или, более общо, над произвольным подиолем Fp» ^ Fq. Такие компоненты называются соответственно линейными, простыми или ^-компонентами.

На основе сдвигов линейных компонент С. В. Августинович и Ф. И. Соловьёва [6] разработали новый метод построения совершенных кодов, названный методом ä-компонент. Развитием указанных подходов для случая g-ичных кодов (q > 2) стал метод простых компонент, используя который, A.B. Лось [11] построил богатое семейство совершенных кодов. Перечисленные методы оказались также весьма плодотворными для изучения структурных свойств совершенных кодов, см., например, работы К.Т. Фелгхса и др. [20,21], Ф.И. Соловьёвой и A.B. Лося [15,16] и других авторов.

Таким образом, компоненты кода Хэмминга активно применяются при решении важной задачи теории кодирования — при построении кодов с предписанными свойствами, например, совершенных кодов с тривиальными группами автоморфизмов.

В работе [7] доказано, что группа перестановочных автоморфизмов линейной компоненты двоичного кода Хэмминга длины N = 2m — 1 изоморфна полупрямому произведению Sn X где п = 2т-1 - 1.

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

изложения результатов, а также иллюстрируют строение рассматриваемых компонент. Доказано, что линейная компонента кода Хэмминга представляется в виде прямой суммы подкодов Хэмминга размерности д — 1 (лемма 8). Каждому из этих подкодов в проективной геометрии соответствует одна из прямых, проходящих через фиксированную точку.

Параграф 2.2 содержит описание группы мономиальных автоморфизмов линейной компоненты д-ичного кода Хэмминга (теорема 7). Линейная компонента допускает перестановки своих подкодов Хэмминга, а также независимые друг от друга мономиальные автоморфизмы, действующие на эти подкоды и оставляющие на месте г-ю координату кодовых слов.

В параграфе 2.3, наряду с простыми компонентами кода Хэмминга, рассматриваются р3-компоненты этого кода. Обобщение идей предыдущего параграфа позволило раскрыть структуру группы мономиальных автоморфизмов р"-компонент (теорема 8).

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

В третьей главе рассматриваются вопросы, связанные с восстановлением двоичных кодов. Возможности восстановления объекта по некоторой его части или по некоторой информации о нём представляют не только теоретический интерес, но также могут имегь ценность и с практической точки зрения. Какие параметры математического объекта, какие его инварианты определяют этот объект однозначно (возможно, с точностью до эквивалентности, изоморфизма и т.п.)? Трудно указать область математики, в которой бы изучение подобных вопросов не являлось актуальным.

Естественный подход к восстановлению кодов состоит в использовании их метрических свойств. Однако, как уже было отмечено выше, наличие изометрии между кодами не гарантирует их однозначного задания, даже с точностью до эквивалентности. Напомним, что если любая изометрия, определённая в вершинах кода, продолжается до изометрии всего пространства, то код называется метрически жёстким. Для некоторых классов кодов проблема метрической жёсткости была изучена и разрешена рядом авторов, см., например, [3,5,23].

Помимо попарных расстояний между кодовыми словами, которые сохраняются при изометрии, в качестве инвариантов для восстановления двоичного кода рассматривались следующие: граф минимальных расстояний, например, в работах [2, 13,19]; множество вершин, находящихся на фиксированном расстоянии р друг от друга, как в работе [10]; попарные расстояния между тройками вершин, которые порождают соответствующие тройки натуральных чисел [1].

В параграфе 3.1 приводится краткий обзор результатов, касающихся восстановимости кодов, графов, булевых функций и т. п. Одним из наиболее сильных инвариантов двоичного кода оказался набор размерностей его подкодов. Здесь под размерностью кода понимается размерность минимальной грани булева куба, содержащей этот код. Отображение кода в F", сохраняющее размерность любого его подкода, называется сильной иэометрией. В работе [4] доказано, что любая сильная изомет-рия однозначно расширяется до изометрии всего булева куба.

В параграфе 3.2 показано, что набор размерностей подкодов, как инвариант, избыточен, а именно: для восстановления двоичного кода с точностью до эквивалентности достаточно знать размерности всех его подкодов чётной мощности (теорема 9). Глава завершается примерами, показывающими неулуч-шаемый характер изложенных достаточных условий эквивалентности двоичных кодов.

Результаты третьей главы получены совместно с C.B. Ав-густиновичем и опубликованы в работах [28,29].

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

Список литературы

[1] Абдурахманов Ж. К. О геометрической структуре кодов, исправляющих ошибки: Дис. ... канд. физ.-мат. наук: 01.01.09. - Ташкент, 1991. - 66 с.

[2] Августинович С. В. К строению графов минимальных расстояний совершенных бинарных (и, 3)-кодов // Дискрета. анализ и исслед. операций. Сер. 1. — 1998. — Т. 3, № 5. - С. 3-5.

[3] Августинович С. В. Об изометричности плотно упакованных бинарных кодов // Тр. Ин-та математики / РАН. Сиб. отд-ние. — 1994. — Т. 27: Дискретный анализ. — С. 3-5.

[4] Августинович С. В. О сильной изометрии бинарных кодов // Дискретн. анализ и исслед. операций. Сер. 1. — 2000. - Т. 7, № 3. - С. 3-5.

[5] Августинович С. В., Соловьёва Ф. И. К метрической жесткости двоичных кодов // Пробл. передачи информ. — 2003. - Т. 39, вып. 2. - С. 23-28.

[6] Августинович С. В., Соловьёва Ф. И. Построение совершенных двоичных кодов последовательными сдвигами а-компонент // Пробл. передачи информ. — 1997. — Т. 33, вып. 3. - С. 15-21.

[7] Августинович С. В., Соловьёва Ф.И., Хедеп У. О структуре группы симметрий кодов Васильева // Пробл. передачи информ. - 2005. - Т. 41, вып. 2. - С. 42-49.

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

[9] Зиновьев В. А., Леонтьев В. К. Несуществование совершенных кодов над полями Гадуа. — М., 1972. — 10 с. — (Препр. / АН СССР. Ин-т пробл. передачи информ.; № 1).

[10] Красин В. Ю. О слабых изометриях булева куба // Дискреты. анализ и исслед. операций. Сер. 1. — 2006. — Т. 13, № 4. - С. 26-32.

[11] Лось А. В. Построение совершенных g-ичных кодов свит-чингами простых компонент // Пробл. передачи ин-форм. - 2006. - Т. 42, вып. 1. - С. 34-42.

[12] Марков А. А. О преобразованиях, не распространяющих искажения // Избранные труды. Т. II. Теория алгорифмов и конструктивная математика, математическая логика, информатика и смежные вопросы. — М.: МДНМО, 2003. - С. 70-93.

[13] Могильных И. Ю. О слабых изометриях кодов Препараты // Пробл. передачи информ. — 2009. — Т. 45, выи. 2. — С. 78-83.

[14] Соловьёва Ф. И. Комбинаторные методы построения и исследования кодов: Дис. ... докт. физ.-мат. наук: 01.01.09. — Новосибирск, 2008. — 202 с.

[15] Соловьёва Ф. И., Лось А. В. О пересечениях g-значных совершенных кодов // Сиб. мат. журнал. — 2008. — Т. 49, вып. 2. - С. 464-474.

[16] Соловьёва Ф.И., Лось А. В. О построении разбиений Fq на совершенные g-значные коды // Дискретн. анализ и исслед. операций. - 2009. - Т. 16, № 3. - С. 63-73.

[17] Constantinescu I., Heise W. On the consept of code-isomorphy 11 J. Geom. - 1996. - V. 57. - P. 63-69.

[18] Huffman W. C. Codes and groups / / Handbook of coding theory. — Amsterdam, New York: Elsevier Science, 1998. — P. 1345-1440.

[19] Mogilnykh I.Yu., Ostergard P.R.J., Pottonen O., Solov'eva F.I. Reconstructing extended perfect binary one-error-correcting codes from their minimum distance

graphs // IEEE Trans. Inform. Theory — 2009. - V. 55. -P. 2622-2625.

[20] Phelps К. Т., Rifu J., Villanueva M. Kernels and p-kerneis of pr-ary 1-perfect codes // Designs, Codes and Cryptography. —, 2005. - V. 37, № 2. - P. 243-261.

[21] Phelps К. Т., Villanueva M. Ranks of g-ary 1-perfect codes // Designs, Codes and Cryptography. - 2002. - V- 27, № 1-2. -P. 139-144.

[22] Solov'eva F. I. On perfect codes and related topics. — Pohang: Pohang University of Science and Technology, 2004. — 80 p. — (Com2MaC Lecture Note Series; 13).

[23] Solov'eva F. I., Avgustinovich S. V., Honold Т., Heise W. On the extendability of code isometries // J. Geom..— 1998. — V. 61. -P. 3-16. .

[24] Tietavainen A. On the nonexistence of perfect codes over finite fields. // SIAM J. Appl. Math. - 1973. - V: 24. -P. 88-96.

Публикации автора по теме диссертации

[25] Горкупов Е. В. Группа перестановочных автоморфизмов q-ичного кода Хэмминга // Пробл. передачи: информ. — 2009. - Т. 45, вып. 4. - С. 18-25.

[26] Горкупов Е. В. Мономиальные автоморфизмы линейной и простой компонент кода Хэмминга // Дискретн. анализ и исслед. опер. - 2010. - Т. 17, №1. - С. 11-33.

[27] Горкупов Е. В. Связь между перестановочными автоморфизмами кода Хэмминга и коллинеациями проективной геометрии // Материалы XVII Межд. школы-семинара „Синтез и сложность управляющих систем"

им. ак. О.В. Лупанова (Новосибирск, Россия. 27 октября - 1 ноября, 2008). — Новосибирск: Изд-во Института математики, 2008. - С. 30-32.

[28] Горкунов Е. В., Августпинович С. В. О восстановлении двоичных кодов по размерностям их подкодов // Дискретн. анализ и исслед. опер. — 2010. — Т. 17, № 5. — С. 15-21.

[29] Avgustinovich S. V., Gorkunov Е. V. On redundancy of strong isometries of binary codes // Proc. IEEE Int. Conference on Computational Technologies in Electrical and Electronics Engineering (Irkutsk, Russia. July 11-15,2010). — Piscataway: IEEE, 2010. - P. 50-51.

[30] Gorkunov E. V. Monomial automorphisms of linear components of the Hamming code // Proc. XII Int. Symposium on Probl. of Redundancy in Information and Control Systems (Saint-Petersburg, Russia. May 26-30, 2009). - Saint-Petersburg: Saint-Petersburg State University of Aerospace Instrumentation, 2009. - P. 76-80.

[31] Gorkunov E. V. On permutation automorphism groups of q-ary Hamming codes // Proc. 11th Int. Workshop on Algebraic and Combinatorial Coding Theory (Pamporovo, Bulgaria. June 16-22, 2008). — Sofia: Inst, of Math, and Informatics, 2008. - P. 119-124.

[32] Gorkunov E. V. On the monomial automorphism group of ps-components in the q-ary Hamming code // Сб. трудов 32-й Конф. молодых учёных и специалистов „Информационные технологии и системы" (Бекасово, Россия. 14-18 декабря 2009). — М.: Ин-т пробл. передачи информ., 2009. — С. 390-395.

[33] Gorkunov Е. F. Symmetries of a q-ary Hamming code // Proc. 12th Int. Workshop on Algebraic and Combinatorial Coding Theory (Novosibirsk, Russia. Sept. 5-11, 2010). — Novosibirsk: Sobolev Inst, of Math., 2010. - P. 144-149.

Горкунов Евгений Владимирович

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

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

Подписано в печать 30.09.2010 Формат 60 х 84 1/16 Печать офсетная Усл. печ. л. 1.0

Заказ № 242 Тираж 100 экз.

Редакционно-издательский центр НГУ ул. Пирогова, 2, Новосибирск, 630090

Введение

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

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

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

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

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

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

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

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

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

Глава 3. Восстановление двоичных кодов по их метрическим инвариантам

3.1. О восстановимости кодов и центрированных функций.

3.2. Полусильные изометрии двоичных кодов.

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

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

Актуальность изучения автоморфизмов определяется их исключительным свойством выявлять внутреннюю структуру рассматриваемого кода. Действие автоморфизмов на кодовые слова позволяет понять, какие части кода схожи и имеют одинаковое строение, а какие существенно различны. Обнаруженные особенности могут найти практическое применение в построении новых кодов, в разработке более эффективных алгоритмов кодирования и декодирования. Группы автоморфизмов используются также для классификации и систематизации кодов.

Рассмотрим множество последовательностей длины п над конечным алфавитом мощности q, называемое также q-ичным кубом. Снабжённый некоторой метрикой, g-ичный куб образует метрическое пространство Vй. В настоящей работе рассматриваются только пространства Хэмминга. Расстояние Хэмминга между двумя последовательностями х,у 6 V71 определяется числом позиций, в которых х и у различаются.

Произвольное подмножество С С Vй называется g-ичным кодом длины п. Элементы кода суть кодовые слова. Наименьшее ненулевое расстояние между кодовыми словами кода С обозначается d = d(C) и называется кодовым расстоянием. Длина, мощность и кодовое расстояние g-ичного кода составляют его параметры и записываются в виде (п, |С|, d)q. Число символов кодирующего алфавита q часто не указывают, если ясно, о каких кодах идёт речь.

Напомним, что изометрия — это преобразование метрического пространства, сохраняющее расстояние между его элементами. Автоморфизмом кода С С V"n называется изометрия пространства Vn, отображающая код С в себя. Два кода С\ и Сч являются эквивалентными, если существует изометрия пространства У™, отображающая эти коды друг в друга.

A.A. Марков в 1956 г. показал [19], что группа изометрий пространства Vй представляет собой полупрямое произведение

Aut(yn) = Sn X SJ = {(тг; а) | тг G Sni а G SJ} .

Иначе говоря, каждая изометрия Vn является парой преобразований (7г; от). Подстановка тг 6 Sn переставляет элементы каждой последовательности из Vй. Кортеж а = (сгх,., <тп) представляет собой набор подстановок из в котором каждая подстановка <У{ действует на символах кодирующего алфавита и в соответствии с этим изменяет элемент хг произвольной последовательности х е Vй.

Пусть задан некоторый код С С Vй с кодовым расстоянием (1. Легко видеть, что шары радиуса £ = [^р] с центрами в кодовых словах кода С не пересекаются. Предположим, что при передаче данных по каналу связи с использованием этого кода в последовательности х € С происходит не более I ошибок (замен символов). Тогда декодирование по принципу максимального правдоподобия — декодирование полученной последовательности в ближайшее к ней кодовое слово, которым является х, — даёт верный результат. В связи с этим говорят, что код С исправляет £ ошибок.

В пространстве Уп мощность произвольного шара радиуса £ рав-£ на ^ Сп(<7 — 1)г- Это означает, что для мощности кода С длины п с г=0 кодовым расстоянием в, справедлива следующая оценка, называемая границей Хэмминга: п

0\ < —--, (1)

Е с* (9 -*=0 где t = ] — число ошибок, которое исправляет код.

Код, достигающий границы Хэмминга, называется совершенным. Наличие равенства в (1) эквивалентно тому, что шары радиуса £ с центрами в кодовых словах кода С образуют разбиение, или плотную упаковку метрического пространства V71. Совершенный код, исправляющий £ ошибок, иногда также называют ¿-совершенным. Тривиальными примерами совершенных кодов являются одноэлементные множества, а также само Vй. Не менее простым примером служит двоичный код с повторением, имеющий нечётную длину п, исправляющий ^тр ошибок, однако содержащий всего два кодовых слова — 00. О и 11. 1.

В конце 1940-х гг. для исправления одиночных ошибок Р. У. Хэм-минг [35] использовал линейный совершенный двоичный код с кодовым расстоянием d = 3. Этот код сейчас называется кодом Хэмминга. Немного ранее, в 1948 г., М. Голей построил [33] два совершенных кода, исправляющих более одной ошибки. Это были двоичный код длины 23, исправляющий 3 ошибки, и троичный код длины 11, исправляющий 2 ошибки. В настоящее время эти замечательные линейные коды хорошо известны как коды Голея, каждый из них единственен с точностью до эквивалентности (см. [32,50,53]), и они имеют применение во многих областях математики. Например, двоичный код Голея широко используется в теории конечных групп (см., например, книгу [30]).

Было предпринято несколько попыток построить другие совершенные коды, исправляющие более одной ошибки, но безуспешно. Вместе с тем стали появляться результаты, перечисляющие параметры, при которых совершенные коды не могут существовать. Первые из них касались кодов над конечными полями ¥q = GF(q), где q = рт для некоторого простого р и целого г ^ 1, и опирались на необходимое условие существования совершенного кода с параметрами q, п, i, вытекающее из границы Хэмминга. Если такой код существует, то мощность шара радиуса t делит мощность всего пространства Vй. Отсюда следует, что существует целое 1 ^ s ^ пг, такое что t

ГCi(q-iy=ps. i=О n

Так как ^ Cln(q — 1)г = qn, то, вычитая предыдущее, находим: г=0 qn — ps = 0 (mod q - 1).

Следовательно, ps = qm для некоторого целого 1 ^ га ^ п. Таким образом, необходимым условием существования ¿-совершенного кода длины п над является равенство (условие сферической упаковки)

Некоторые решения равенств (2) и (3) легко обнаружить. В частности, £ = т = п соответствует коду из одного слова; п = 2Ь + 1 — двоичному коду с повторением; п — 2т ~ 1 и £ = 1 — кодам, исправляющим одну ошибку, число которых оказалось дважды экспоненциальным, а их свойства столь разнообразны, что активно исследуются уже на протяжении более полувека. Результатов этих исследований коснёмся ниже. Другие известные решения не столь очевидны: q = 2, п = 23, Ь = 3, а также д = 3, п = 11, £ = 2 соответствуют кодам Голея; кроме того, много раз было доказано (см., например, [33]), что для-д = 2,п = 90, £ = 2, удовлетворяющих условию (3), не существует совершенных кодов.

В поиске новых решений многие авторы обнаруживали параметры, при которых равенство (2) не имеет решений вовсе; это означает, что не. существует совершенных кодов с такими параметрами. Обзор первых подобных результатов см., например, у Дж. X. ван «Пинта [40]. При их получении в случае £ = 2 условие упаковки удалось связать с теорией диофантовых уравнений, а часть больших параметров были отсечены перебором при помощи компьютера.

Для дальнейшего отсечения «пустых» параметров требовались более тонкие необходимые условия существования совершенных кодов. Для двоичных кодов такое условие было найдено значительно ранее С. П. Ллойдом [43], в 1957 г. Позднее Ф. Дж. Мак-Вильямс [44] обобщила его для конечных полей, а П. Дельсарт [31] и X. У. Ленстра-мл. [38]

2) которое в двоичном случае принимает вид:

3) независимо показали, что структура алфавита не имеет значения и его мощность д может быть произвольной. Теорема Ллойда гласит, что если ¿-совершенный код длины п над алфавитом из д символов существует, то полином ь

Рь{х) = - 1 у-' г=О имеет £ различных корней среди чисел 1, 2,., п.

Рассмотрение нулей полинома Ллойда Р^х) в конечном итоге привело к полному описанию возможных параметров совершенных кодов над конечными полями. Дж. X. ван Линт [41,42] показал, что для t ^ 7 все параметры совершенных кодов уже известны и других не существует. Наконец, А. Титвайнен [56]; а также независимо В. А. Зиновьев и В. К. Леонтьев [13] разрешили проблему полностью и показали, что нетривиальный совершенный код над ¥д, исправляющий более одной ошибки, должен иметь параметры одного из кодов Голея.

Не так много результатов имеется для д, не равного степени простого числа, но те, что удалось получить, в значительной степени продвинули решение проблемы в общем. Используя обобщение теоремы Ллойда, М.Р. Вест [28] существенно ограничил широту поиска, установив, что в этом случае Ь € {1,2, 6,8}. До сих пор не удалось доказать, что таких кодов не существует вообще. Некоторые частные случаи в оставшемся наборе параметров покрываются работами С. В. Голома и Е. С. Познера [34], Л. А.-Вассалыго и др. [11] и некоторых других авторов (см., например, обзор У. Хедена [36]). Вместе с тем, исследование X. У. Ленстры-мл. [38] показывает, что код над «составным» алфавитом, возможно, трудно построить, так как он не может быть эквивалентным никакому групповому коду.

Куб над конечным полем образует п-мерное линейное пространство Всюду далее рассматриваются коды над конечными полями и, ввиду теоремы Зиновьева-Леонтьева-Титвайнена, под термином совершенный понимается совершенный код с кодовым расстоянием 3, то есть исправляющий одну ошибку. Из условия упаковки, такой код может иметь длину п = ^рг и мощность qn~m. В пространстве F^ существует единственный с точностью до эквивалентности линейный (образующий линейное подпространство) совершенный код. Это код код Хэмминга, который строится для любого m ^ 2.

После появления кодов Хэмминга и Голея некоторое время не удавалось обнаружить какие-либо другие совершенные коды. Г. С. Шапиро и Д. Л. Злотник в [52] доказали в 1959 г., что весовое распределение произвольного совершенного двоичного кода зависит только от веса того кодового слова, у которого он является минимальным в коде. Аналогичное свойство у равномерно упакованных g-ичных кодов, подклассом которых являются совершенные, выявили JT. А. Бассалыго и др. [10]1. В связи с этим в [52] было выдвинуто предположение, что все совершенные двоичные коды эквивалентны коду Хэмминга. Эта гипотеза была опровергнута Ю. J1. Васильевым [12]; который в 1962 г. построил дважды экспоненциальное число попарно неэквивалентных совершенных двоичных кодов любой допустимой длины; среди кодов Васильева при п ^ 15 имеет множество нелинейных. Позднее Й. Шёнхайм [51]* и Б. Линдстрём [39] в своих работах 1968-1969 гг. представили нелинейные совершенные коды над произвольными конечными полями. В дальнейшем было предложено более 20 различных конструкций, обзор которых можно найти, например, в лекциях Ф. И. Соловьёвой [54].

Долгое время оставался открытым вопрос, все ли совершенные коды в булевом кубе изометричны друг другу (см., например, [1]). Лишь в 1994 г. C.B. Августинович [3] доказал, что если два совершенных двоичных кода одинаковой длины п > 15 изометричны, то они эквивалентны. Несколько лет спустя аналогичный результат был получен Ф. И. Соловьёвой и др. [55] для совершенных g-ичных кодов.

Изометрии двоичного (или булева) куба исчерпываются перестановками координат и сдвигами пространства на вектор. Таким образом действие изометрии (-7г, v) е Аи^ПЛ,) на двоичный вектор хбЕ^ записывается в виде

Х(7Г, V) = хтг + V, где 7Г £ и V 6 Это происходит от того, что обе возможные подстановки элементов поля Ег могут быть представлены сложением в самом поле: тождественная подстановка есть сложение с 0, а результат подстановки (01) совпадает с прибавлением 1.

В общем случае это не так. Подстановки над представимы через операции поля, если в дополнение к сложению рассмотреть умножение. Аналогично, в случае д = 4 для этой цели можно использовать автоморфизмы самого поля из группы Галуа Оа!^). Например, подстановка (0 а2 1 о;), где а — примитивный элемент ¥4, представляется многочленом (х + а)2. Однако при д ^ 5 подстановок на элементах из ¥q значительно больше, чем тех, которые могут быть заменены операциями в поле. Как следствие, не все изометрии пространства Р™ могут быть выражены в терминах этих операций.

Примечателен результат К. Т. Фелпса [47] о том, что каждая конечная группа изоморфна группе перестановочных автоморфизмов некоторого совершенного двоичного кода. Однако задача нахождения группы автоморфизмов для заданного кода представляется ещё более трудной. Пусть С — совершенный двоичный код. Из свойства антиподаль-ности (см. [52]) кода С следует, что его группа автоморфизмов Аи^С) содержит тождественную подстановку координат е и сдвиг на вектор 1, состоящий из всех единиц. Группа Аи^С), образованная только этими двумя преобразованиями, называется тривиальной. С. В. Августино-вич и Ф. И. Соловьёва [26] построили несистематические совершенные двоичные коды с тривиальной группой автоморфизмов. Независимо

С. А. Малюгин [45] доказал, что существуют и систематические коды с таким свойством.

Изометрии пространства оставляющие неподвижным нулевой вектор, будем называть симметриями. Хорошо известно, что группа полулинейных симметрий кода Хэмминга длины п = изоморфна общей полулинейной группе ГЬш(д) = Оа1(¥д) X С?1/т(д) (см. [37, теорема 7.2]). В случае д > 4 среди симметрий пространства имеются те, которые не являются полулинейными. В связи с этим возникает естественный вопрос, все ли симметрии кода Хэмминга являются полулинейными. В настоящей диссертации дан положительный ответ на этот вопрос.

В булевом кубе код Хэмминга И является одним из самых симметричных среди совершенных кодов в том смысле, что его группа автоморфизмов максимальна по мощности. Этот интересный факт был получен Ф. И. Соловьёвой и С. Топаловой [24]. Затем эти же авторы доказали [25], что максимальный порядок группы автоморфизмов имеет только код Хэмминга. Вместе с тем, независимо С. А. Малюгин [18] для произвольного нелинейного совершенного двоичного кода С установил, что |А^(С)| <

С. В. Августинович с соавторами [9] исследовали структуру группы перестановочных автоморфизмов кодов Васильева. Перестановочные автоморфизмы задаются лишь подстановкой на позициях координат вектора. Там же доказано, что группа перестановочных автоморфизмов (или, что то же при д = 2, группа симметрий) линейной компоненты двоичного кода Хэмминга длины N = 2т — 1 изоморфна полупрямому произведению Бп X , где п = 2т~1 — 1. Ниже изучение группы автоморфизмов линейной компоненты продолжено для д ^ 2. Полученные результаты распространены на другие компоненты д-ичного кода Хэмминга, такие как простые компоненты и их обобщение, которое предложено называть ^-компонентой.

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

Настоящая диссертация содержит три главы. В первой главе описаны результаты исследования симметрий д-ичного кода Хэмминга. В параграфе 1.1 приведены необходимые обозначения и определения различных групп автоморфизмов кодов, показана связь автоморфизмов с матрицами над конечными полями. Параграф 1.2 включает в себя известные факты о строении групп автоморфизмов линейных кодов, а также содержит замечания, раскрывающие характер действия полулинейных симметрий на векторы пространства Е™. В параграфе 1.3 исследуются перестановочные автоморфизмы кода Хэмминга. Доказано, что группа перестановочных автоморфизмов кода Хэмминга длины п — ^рг с проверочной матрицей в каноническом виде изоморфна унитреуголыюй группе матриц ¿7Тто(д) (теорема 5). Вместе с тем показано, что группа перестановочных автоморфизмов циклического кода Хэмминга не может быть изоморфна ?7Тт(д) (утверждение 1). Таким образом установлено, ча;о в случае д > 2 группы перестановочных автоморфизмов различных кодов Хэмминга могут быть неизоморфны друг другу (следствие 1). В параграфе 1.4 доказано, что все симметрии кода

Хэмминга являются полулинейными. Этот результат позволил получить представление о всей группе автоморфизмов д-ичного кода Хэмминга (теорема 6).

Во второй главе исследуется структура групп мономиальных автоморфизмов различных компонент кода Хэмминга. Мономиальные автоморфизмы характеризуются тем, что действие каждого из них на векторы пространства Е™ может быть задано умножением векторов на некоторую мономиальную матрицу над полем В параграфе 2.1 приведены известные связи между кодом Хэмминга и конечными проективными геометриями, необходимые для изложения результатов второй главы. В параграфе 2.2 дано описание группы мономиальных автоморфизмов линейной компоненты д-ичного кода Хэмминга (теорема 7). В параграфе 2.3, наряду с понятием простой компоненты кода Хэмминга, рассматриваются ^/-компоненты, заданные как линейные пространства над подполями поля Идеи предыдущего параграфа обобщаются для таких компонент, в результате чего получена информация о структуре их групп мономиальных автоморфизмов (теорема 8).

Третья глава описывает исследование восстановимости двоичных кодов по размерностям их подкодов, которое было выполнено автором совместно с С. В. Августиновичем. Здесь, как и в работах [1,5], под размерностью кода понимается размерность наименьшей грани булева куба, содержащей этот код. Оказалось, что произвольный двоичный код определяется с точностью до эквивалентности набором размерностей всех своих подкодов чётной мощности (теорема 9). Глава завершается примерами, показывающими неулучшаемый характер обнаруженных достаточных условий эквивалентности двоичных кодов.

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

1. Доказано, что все симметрии д-ичных кодов Хэмминга являются полулинейными. Получено описание группы автоморфизмов таких кодов.

2. Для д-ичного кода Хэмминга с проверочной матрицей в каноническом виде показано, что его группа перестановочных автоморфизмов изоморфна унитреугольной группе. Обнаружены коды Хэмминга с неизоморфными группами перестановочных автоморфизмов.

3. Описана структура групп мономиальных автоморфизмов различных компонент кода Хэмминга над полем ¥д: простой, линейной и ^-компоненты.

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

Основные результаты опубликованы в работах [57-65].

Заключение

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

1. Абдурахманов Ж. К. О геометрической структуре кодов, исправляющих ошибки: Дис. . канд. физ.-мат. наук: 01.01.09. — Ташкент, 1991. - 66 с.

2. Августииович С. В. К строению графов минимальных расстояний совершенных бинарных (п, 3)-кодов // Дискретн. анализ и исслед. операций. Сер. 1. 1998. — Т. 3, № 5. — С. 3-5.

3. Августииович С. В. Об изометричности плотно упакованных бинарных кодов // Тр. Ин-та математики / РАН. Сиб. отд-ние. — 1994. Т. 27: Дискретный анализ. - С. 3-5.

4. Августииович С. В. Об одном свойстве совершенных двоичных кодов // Дискретн. анализ и исслед. операций. Сер. 1. — 1995. — Т. 2, № 1. С. 4-6.

5. Августииович С. В. О сильной изометрии бинарных кодов // Дискретн. анализ и исслед. операций. Сер. 1. — 2000. — Т. 7, № 3. — С. 3-5.

6. Августииович С. В., Васильева А. Ю. Вычисление центрированной функции по её значениям на средних слоях булева куба // Дискретн. анализ и исслед. операций. Сер. 1. — 2003. — Т. 10, № 2. С. 3-16.

7. Августинович С. В., Соловьёва Ф. И. К метрической жесткости двоичных кодов // Пробл. передачи информ. — 2003. — Т. 39, вып. 2. С. 23-28.

8. Августинович С. В., Соловьёва Ф. И. Построение совершенных двоичных кодов последовательными сдвигами ¿-компонент // Пробл. передачи информ. — 1997. — Т. 33, вып. 3. — С. 15-21.

9. Августинович С. В., Соловьёва Ф. ИХеден У. О структуре группы симметрий кодов Васильева // Пробл. передачи информ. — 2005. Т. 41, вып. 2. - С. 42-49.

10. Бассалыго Л. А., Зайцев Г. В., Зиновьев В. А. О равномерно упакованных кодах // Пробл. передачи информ. — 1974. — Т. 10, вып. 1. С. 9-14.

11. Бассалыго Л. А., Зиновьев В. А., Леонтьев В. К., Фельдман Н.И. Несуществование совершенных кодов для некоторых составных алфавитов // Пробл. передачи информ. — 1975. — Т. 11, вып. 3. — С. 3-13.

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

13. Зиновьев В. А., Леонтьев В. К. Несуществование совершенных кодов над полями Галуа. — М., 1972. — 10 с. — (Препр. / АН СССР. Ин-т пробл. передачи информ.; № 1).

14. Красин В. Ю. О слабых изометриях булева куба // Дискретн. анализ и исслед. операций. Сер. 1. — 2006. — Т. 13, № 4. С. 26-32.

15. Лось А. В. Построение совершенных д-значных кодов последовательными сдвигами а-компонент // Пробл. передачи информ. — 2004. Т. 40, вып. 1. - С. 40-47.

16. Лось А. В. Построение совершенных g-ичных кодов свитчингами простых компонент // Пробл. передачи информ. — 2006. — Т. 42, вып. 1. С. 34-42.

17. Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А. Теория кодов, исправляющих ошибки. — М.: Связь, 1979. — 744 с.

18. Малюгин С. А. О порядке группы автоморфизмов совершенных двоичных кодов // Дискретн. анализ и исслед. операций. Сер. 1. — 2000. Т. 7, № 4. - С. 91-100.

19. Марков А. А. О преобразованиях, не распространяющих искажения // Избранные труды. Т. II. Теория алгорифмов и конструктивная математика, математическая логика, информатика и смежные вопросы. М.: МЦНМО, 2003. - С. 70-93.

20. Могильных И. Ю. О слабых изометриях кодов Препараты // Пробл. передачи информ. — 2009. — Т. 45, вып. 2. — С. 78-83.

21. Соловьёва Ф. И. Комбинаторные методы построения и исследования кодов: Дис. . докт. физ.-мат. наук: 01.01.09. — Новосибирск,2008. 202 с.

22. Соловьёва Ф. И., Лось A.B. О пересечениях g-значных совершенных кодов // Сиб. математич. журнал. — 2008. — Т. 49, вып. 2. — С. 464-474.

23. Соловьёва Ф. И., Лось A.B. О построении разбиений F^ на совершенные g-значные коды // Дискретн. анализ и исслед. операций. —2009. Т. 16, № 3. - С. 63-73.

24. Соловьёва Ф. И., Топалова С. Т. О группах автоморфизмов совершенных двоичных кодов и систем троек Штейнера // Пробл. передачи информ. — 2000. — Т. 36, вып. 4. — С. 3-8.

25. Соловьёва Ф. И., Топалова С. Т. Совершенные двоичные коды и системы троек Штейнера с максимальными порядками групп автоморфизмов // Дискретн. анализ и исслед. операций. Сер. 1. — 2000. Т. 7, № 4. - С. 101-110.

26. Avgustinovich S. V., Solov'eva F.I. Perfect binary codes with trivial automorphism group // Proc. Int. Workshop on Information Theory (Killarney, Ireland. June 22-26, 1998). — Piscataway: IEEE, 1998. — P. 114-115.

27. Avgustinovich S. V., VasiVeva A. Yu. Testing sets for 1-perfect code // General Theory of Information Transfer and Combinatorics. — Berlin: Springer, 2006. — P. 938-940. — (Lecture Notes in Computer Science; V. 4123).

28. Best M. R. Perfect codes hardly exist //IEEE Trans. Inform. Theory. — 1983. V. 29. - P. 349-351.

29. Constantinescu I., Heise W. On the consept of code-isomorphy // J. Geom. 1996. - V. 57. - P. 63-69.

30. Conway J. H., Sloane N. J. A. Sphere packings, lattices and groups. — Berlin: Springer, 1988. 691 p.

31. Delsarte P. Bounds for unrestricted codes, by linear programming // Philips Research Reports. 1972. - V. 7. - P. 289-296.

32. Delsarte P., Goethals J. M. Unrestricted codes with the Golay parameters are unique // Discrete Math. — 1975. — V. 12. — P. 211-224.

33. Golay M. J. E. Notes on digital coding // Proc. IRE 1949. - V. 37, № 6. - P. 657.

34. Golomb S. W., Posner E. S. Rook domains, Latin squares, affine plains and error-distributing codes // IEEE Trans. Inform. Theory — 1964. — V. 10, № 1. P. 196-208.

35. Hamming R.W. Error detecting and error correcting codes // Bell System Tech. J. 1950. - V. 29. - P. 147-160.

36. Heden 0. A survey of perfect codes // Advances in Math, of Communications. — 2008. V. 2, № 2. — P. 223-247.

37. Huffman W. C. Codes and groups // Handbook of coding theory. — Amsterdam, New York: Elsevier Science, 1998. — P. 1345-1440.

38. Lenstra H. W., Jr. Two theorems on perfect codes // Discrete Math. — 1972. V. 3. - P. 125-132.

39. Lloyd S. P. Binary block coding // Bell System Tech. J. 1957. -V. 36. - P. 517-535.

40. MacWilliams F.J. Combinatorial problems of elementary Abelian groups: Doctoral thesis. — Harvard: Harvard University, 1962.

41. Malyugin S.A. Perfect codes with trivial automorphism group // Proc. II Int. Workshop «Optimal Codes and Related Topics» (Sozopol, Bulgaria. June 9-15, 1998). — Sofia: Inst, of Math, and Informatics, 1998. P. 163-167.

42. Mogilnykh I.Yu., Ostergârd P.R.J., Pottonen 0., Solov'eva F.I. Reconstructing extended perfect binary one-error-correcting codes from their minimum distance graphs // IEEE Trans. Inform. Theory — 2009. V. 55. - P. 2622-2625.

43. Phelps K. T. Every finite group is the automorphism group of some perfect code //J. Combinatorial Theory. Ser. A. — 1986. — V. 43. — P. 45-51.

44. Phelps K. T., Rifà J., Villanueva M. Kernels and p-kernels of pr-ary 1-perfeet codes // Designs, Codes and Cryptography. — 2005. — V. 37, m 2. P. 243-261.

45. Phelps K. T., Villanueva M. Ranks of ç-ary 1-perfect codes // Designs, Codes and Cryptography. 2002. - V. 27, № 1-2. - P. 139-144.

46. Pless V. On the uniqueness of the Golay codes //J. Combinatorial Theory. 1968. - V. 5. - P. 215-228.

47. Schônheim J. On linear and nonlinear single-error-correcting q-ary perfect codes // Information and Control. — 1968. — V. 12. — P. 23-26.

48. Shapiro G. S., Slotnik D. L. On the mathematical theory of error correcting codes // IBM J. Research and Development. — 1959. — V. 3, № 1. P. 25-34.

49. Snover S. L. The uniqueness of the Nordstrom-Robinson and the Golay binary codes: Doctoral thesis. — Michigan: Michigan State University, 1973.

50. Solov'eva F. I. On perfect codes and related topics. — Pohang: Pohang University of Science and Technology, 2004. 80 p. - (Com2MaC Lecture Note Series; 13).

51. Solov'eva F.I., Avgustinovich S. V., Honold Т., Heise W. On the extendability of code isometries //J. Geom. — 1998. — V. 61. — P. 3-16.

52. Tietavainen A. On the nonexistence of perfect codes over finite fields. // SIAM J. Appl. Math. 1973. - V. 24. - P. 88-96.

53. Публикации автора по теме диссертации

54. Горкунов Е. В. Группа перестановочных автоморфизмов д-ичного кода Хэмминга // Пробл. передачи информ. — 2009. — Т. 45, вып. 4. С. 18-25.

55. Горкунов Е. В. Мономиальные автоморфизмы линейной и простой компонент кода Хэмминга // Дискретн. анализ и исслед. операций. 2010. - Т. 17, № 1. - С. 11-33.

56. Горкунов Е.В., Августинович С. В. О восстановлении двоичных кодов по размерностям их подкодов // Дискретн. анализ и исслед. операций. 2010. - Т. 17, № 5. - С. 15-21.

57. Gorkunov E. V. On permutation automorphism groups of q-ary Hamming codes // Proc. 11th Int. Workshop on Algebraic and Combinatorial Coding Theory (Pamporovo, Bulgaria. June 16-22, 2008). Sofia: Inst, of Math, and Informatics, 2008. - P. 119-124.

58. Gorkunov Е. V. Symmetries of a q-ary Hamming code // Proc. 12th Int. Workshop on Algebraic and Combinatorial Coding Theory (Novosibirsk, Russia. Sept. 5-11, 2010). — Novosibirsk: Sobolev Inst, of Math., 2010. P. 144-149.м