Введение к работе
Объектом исследования в данной работе являются плотно упакованные, или совершенные, двоичные коды и плотно упакованные троичные равновесные коды.
Актуальность темы. В теории кодов, исправляющих ошибки, большое внимание уделяется совершенным, или плотно упакованным, кодам. В. Л. Зиновьевым и В. К. Леонтьевым [10, 11, 12] (независимо А.Тнтвай-неном [46]) было показано, что не существует других нетривиальных совершенных (/-ичных кодов, кроме кодов с параметрами кодов Хеммпнга (^-fy-,yn~',3) (длина ^гт~, мощность ?"-', кодовое расстояние 3) и кодов Голея- - двоичного (23, 212,7) и троичного (11,3е, 5)-кодов. Последние два, кода единственны с точностью до эквивалентности. Ю.Л.Васильев [4] построил первый класс неэквивалентных кодов с параметрами двоичных кодов Хеммпнга, опровергнув гипотезу о том, что класс совершенных кодов с расстоянпем 3 также исчерпывается только линейными кодами Хеммпнга. Возникшая таким образом задача описания всех совершенных двоичных (а также (j-ичных) кодов с расстоянием 3 до сих пор не решена ввиду большой сложности.
Известные результаты по теории совершенных кодов условно делятся на два направлення: построение новых совершенных кодов (к чтому направлению относится данная работа), в том числе кодов с новыми нетривиальными свойствами, и изучение свойств всех совершенных кодов.
Ряд свойств, общих для всех совершенных кодов, свидетельствуют о большой регулярности строения произвольного совершенного кода. ('. П. Ллойд [Зо] и независимо Г. С. Шапиро и Д. Л. Злотник [21] установили, что количество вершин совершенного кода, находящихся на заданном расстоянии от данной кодовой вершины, не зависит нн от выбора этой вершины, ни от выбора совершенного кода. Ф.Дельсарт [27] и независимо Л. К. Пулатов [18] доказали, что количество вершин произвольного совершенного кода в любой грани размерности не менее (л +1 )/2 зависит только от размерности грани. СВ. Августинович [1] показал, что любой совершенный код однозначно определяется своими кодовыми вершинами, имеющими вес {п + 1)/2. А.Ю.Васильевой в работах [5. 6, 7, 8, 47] был существенно расширен список свойств, присущих всем совершенным двоичным кодам, в частности, был установлен ряд обобщённых спектральных теорем и охарактеризовано множество всех кодов в терминах линейного многообразия в 2п-мерном евклидовом пространстве.
Конструкции совершенных двоичных кодов условно делятся на СВНТ-чннговые (свитчннг, или «переключение» - замена некоторой «старой» части кода на «новую») и конструкции произведения кодов. В некоторых-конструкциях произведения также присутствует элемент свитчинга.
Перечислим известные конструкции бесконечных классов совершенных двоичных кодов. Первый класс нелинейных кодов был построен К).Л.Васильевым [4] в 1962г. В 1977г. О.Хеден [31] построил коды,
неэквивалентные кодам Васильева. Коды, описанные Ф. И. Соловьёвой [19] в 1981с, содержат коды Хедена. Два года спустя К.Фелпс [40] независимо переоткрыл конструкцию Соловьёвой и затем в 1984 г. обобщил её конструкцией [41], использующей m-квазигруппы. Коды, построенные Дж.-М. Лабором [33], содержатся в конструкции Хедена. В 1986 г. М. Моллар [39] описал конструкцию произведения кодов, обобщающую коды Васильева. В 1970г. и 1988г. В.А.Зиновьев [9] привёл две конструкции совершенных двоичных кодов на основе конкатенации. В 1988 г.. Ф. И.Соловьёва представила ещё один класс совершенных кодов [20], обобщив его в [43]. Алгебраическая конструкция ^-линейных совершенных кодов описана в 1994 г. в работе [30]. Эти коды (которые можно описать также как частный случай кодов Васильева) представляют интерес как пример нелинейных транзитивных кодов - любой кодовый вектор при помощи автоморфизма кода можно перевести в нулевой вектор. 'Гам же показано, что расширенный совершенный код Хеммнпга длины больше 16 не является /?4-линейным. В 1994 г. Т.Этцион и А.Вардп [28] описали класс совершенных кодов полного ранга. В этой же работе предложен способ построения совершенных кодов при помощи так называемых совершенных сегментаций. В 1995г. К.Фелпс и М.ЛеВан построили совершенные коды, размерности ядер которых принимают все возможные значения. В 1996 г. СВ. Августинович и Ф. И. Соловьёва в [2] описали метод rv-компонент построения совершенных кодов, дающий не
менее чем 2- ' о различных совершенных кодов длины
п, а в [3, 22] построили класс несистематических совершенных кодов для и > 255 (двоичный код мощности 2к систематический, если можно так выбрать к координат, называемых информационными, что в них кодовые слова принимают все возможные 2к наборов значений, каждый но одному разу). В 1997 г. А.Лобстейн и В. А. Зиновьев предложили обобщенный метод конкатенации для построения совершенных кодов [36, 37]. В 1998 г. С В. Августинович и Ф.И.Соловьёва [23], а также С. А. Малюгин [38] представили классы несистематических совершенных кодов (длин > 127 и > 15 соответственно), имеющих тривиальную группу автоморфизмов. 15 1999г. С. А.Малюгину удалось улучшить нижнюю оценку числа дво-
ичных совершенных кодов, построив не менее 2~ 2- таких
кодов.
Наибольшее внимание в теории кодирования заслуженно уделяется двоичным кодам, и связано это с тем, что многие явления, имеющие место в общем у-ичном случае, могут быть исследованы в двоичном и * затем обобщены. В последние годы более интенсивно стали изучаться также троичные коды. В диссертации М. Сванстрёма [44] изложена серия результатов по троичным равновесным кодам. Там же, а так же в [45] описан класс совершенных (я,3;п— 1)з-кодов, п = 2к > 4 (совершенных троичных равновесных кодов длины п с весом п — 1 и расстоянием 3), построенный на основе циклического представления двоичного кода
Хеммнига. В таких кодах максимальное подмножество слов с одним її тем же носителем образует линейный двоичный совершенный код с расстоянием 3 код Хеммнига в алфавите {1,2} (в этом смысле тгот код Хеммнига содержится в соответствующем троичном равновесном коде). Дж.ванЛинт и Л.Толхьюзен показали в [34], что не существует нетривиальных совершенных равновесных кодов с расстоянием .'}, кроме (и, 3; и — I )з-кодов и (п, 3; п)з-кодов.
Цель работы состоит в получении новых классов плотно упакованных кодов, двоичных и троичных равновесных, выявлении новых свойств, которые могут быть присущи таким кодам, получении нижней оценки числа плотно упакованных кодов.
Методика исследований. Результаты работы доказываются путем алгебраического и комбинаторного анализа.
Научная новизна. В диссертации получены следующие новые результаты.
1. Описана комбинированная конструкция совершенных двоичных ко
дов, обобщающая несколько известных ранее конструкций и позволяю
щая построить «универсальный» совершенный код, содержащий в парал
лельных гранях все наперёд заданные совершенные коды фиксированной
длины.
2. Установлена нижняя оценка числа m-квазигрупп порядка 4, с
помощью которой получена новая нижняя оценка числа совершенных
двоичных кодов.
-
Описаны все (с точностью до эквивалентности) /^-линейные совершенные коды.
-
Описаны индуктивные способы построения совершенных троичных
равновесных кодов с расстоянием 3. Показана нижняя оценка 2-' для числа таких кодов длины п веса п — 1 и для числа совершенных пароеочетаннй в Е" без параллельных рёбер на расстоянии меньше 3.
Г». Построен класс оптимальных (плотно упакованных в слое веса п) троичных равновесных кодов длины и = 22fe+1 веса п — 1 с расстоянием 5.
Практическая ценность. Работа носит теоретический характер. Полученные в ней результаты применимы в теории корректирующих кодов и криптографии.
Апробация работы. Результаты работы докладывались на международных конференциях: Седьмой международной конференции по алгебраической и комбинаторной теории кодирования АССТ2000 (Болгария, Вапско, 2000 г.) и конференции "Дискретный анализ и исследование операций" DAOR'2000 (Новосибирск, 2000 г.) - и на Второй научной молодёжной школе по дискретной математике (Нижний Новгород, 1998 г.). Все результаты докладывались на семинарах НГУ и Института математики СО РАН "Дискретный анализ" и "Теория кодирования".
Публикации. По теме диссертации автором опубликованы работы
I)
Объём и структура диссертации. Диссертация состоит из введения, двух глав и списка литературы. Объём диссертации - 64 страницы.