Констркции плотно упакованных кодов и нижние оценки их числа тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

РГБ 08

РОССИЙСКАЯ АКАДЕМИЯ НАУК - б СЕН 2(100 СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ им. С. Л. Соболева

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

Кротов Денис Станиславович

КОНСТРУКЦИИ ПЛОТНО УПАКОВАННЫХ кодов И НИЖНИЕ ОЦЕНКИ ИХ ЧИСЛА

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

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

АВТОРЕФЕРАТ

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

Новосибирск 2000

Работа выполнена

л Институте математики им. С. Л. Соболева СО РАН

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

Ю. Л. Васильев

Официальные оппоненты: доктор физико-математических наук,

профессор В.А.Зиновьев, кандидат физико-математических наук, Ю. А. Кочетов Ведущая организация: Московский государственный

университет км. М. В. Ломоносова

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

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

Автореферат разослан «_»_2000 г.

.Учёный секретарь диссертационного совета Д 002.23.03, доктор физико-математических наук

З'ЯМ и,4 и п

А. В. Косточка

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

Объектом исследования в данной работе являются плотно упакованные, или совершенные, двоичные коды и плотно упакованные троичные равновесные коды.

Актуальность темы. В теории кодов, исправляющих ошибки, большое внимание уделяется совершенным, пли плотно упакованным, кодам. В. А.'Зиновьевым и В. К. Леонтьевым [10, 11, 12] (независимо А.Титвай-нено.м [*1(5]) было показано, что не существует других нетривиальных совершенных </-пчиых кодов, кроме кодов с параметрами кодов Хеммннга

(длина мощность кодовое расстояние 3) и кодов

Голея- - двоичного (23, 212,7) и троичного (11,3е, 5)-кодов. Последние два, кода единственны с точностью до эквивалентности. Ю.Л.Васильев [4] построил первый класс неэквивалентных кодов с параметрами двоичных кодов Хеммннга, опровергнув гипотезу о том, что класс совершенных кодов с расстоянием 3 также исчерпывается только линейными кодами Хеммннга.. Возникшая таким образом задача описания всех совершенных двоичных (а также д-ичных) кодов с расстоянием 3 до сих пор не решена ввиду большой сложности.

Известные результаты по теории совершенных кодов условно делятся на два направления: построение новых совершенных кодов (к чтому направлению относится данная работа), в том числе кодов с новыми нетривиальными свойствами, и изучение свойств всех совершенных кодов.

Ряд свойств, общих для всех совершенных кодов, свидетельствуют о большой регулярности строения произвольного совершенного кода. (II. Ллойд [3-гз] и независимо Г. С. Шапиро и Д. Л. Злотник [21] установили, что количество вершин совершенного кода, находящихся на заданном расстоянии от данной кодовой вершины, не зависит ни от выбора этой вершины, ни от выбора совершенного кода. Ф. Дельсарт [27] и независимо Л. К. Пулатов [18] доказали, что количество вершин произвольного совершенного кода в любой грани размерности не менее (л +1)/2 зависит только от размерности грани. С. В. Августинович [1] показал, что любой совершенный код однозначно определяется своими кодовыми вершинами, имеющими вес {п + 1)/2. А.Ю.Васильевой в работах [5, 6, 7, 8, 17] был существенно расширен список свойств, присущих всем совершенным двоичным кодам, в частности, был установлен ряд обобщённых спектральных теорем и охарактеризовано множество всех кодов в терминах линейного многообразия в 2"-мерном евклидовом пространстве.

Конструкции совершенных двоичных кодов условно делятся на свит-чинговые (свитчинг, или «переключение» - замена некоторой «старой» части кода на «новую») и конструкции произведения кодов. В некоторых конструкциях произведения также присутствует элемент свитчингп.

Перечислим известные конструкции бесконечных классов совершенных двоичных кодов. Первый класс нелинейных кодов был построен 1С). Л. Васильевым [4] в 1962 г. В 1977г. О. Хеден [31] построил коды,

неэквивалентные кодам Васильева. Коды, описанные Ф. И. Соловьёвой

[19] в 1981г., содержат коды Хедена. Два года спустя К.Фелпг [40] независимо переоткрыл конструкцию Соловьёвой и затем в 1984 г. обобщил её конструкцией [41], использующей т-квазигруипы. Коды, построенные Дж.-М. Лабором [33], содержатся в конструкции Хедена. В 1986 г. М. Молл ар [39] описал конструкцию произведения кодов, обобщающую коды Васильева. В 1970г. и 1988 г. В. А. Зиновьев [9] привёл две конструкции совершенных двоичных кодов на основе конкатенации. В 1988 г.. Ф. И.Соловьёва представила ещё один класс совершенных кодов

[20], обобщив его в [43]. Алгебраическая конструкция ¿^-линейных совершенных кодов описана в 1994 г. в работе [30]. Эти коды (которые можно описать также как частный случай кодов Васильева) представляют интерес как пример нелинейных транзитивных кодов - любой кодовый вектор при помощи автоморфизма кода можно перевести в нулевой вектор. 'Гам же показано, что расширенный совершенный код Хеммннга длины больше 16 не является ¿^-линейным. В 1994 г. Т.Этцион и А.Вардн [28] описали класс совершенных кодов полного ранга. В этой же работе предложен способ построения совершенных кодов при помощи так называемых совершенных сегментаций. В 1995г. К.Фелпс и М.ЛеВан построили совершенные коды, размерности ядер которых принимают все возможные значения. В 1996 г. С. В. Августинович и Ф. И. Соловьёва в [2] описали метод г\-компонент построения совершенных кодов, дающий не

менее чем 2~ ' о различных совершенных кодов длины

п, а в [3, 22] построили класс несистематических совершенных кодов для п > 255 (двоичный код мощности 2к систематический, если можно так выбрать к координат, называемых информационными, что в них кодовые слова принимают все возможные 2к наборов значений, каждый но одному разу). В 19971. А.Лобстейн и В. А. Зиновьев предложили обобщенный метод конкатенации для построения совершенных кодов [36, 37]. В 1998 г. С. В. Августинович и Ф.И.Соловьёва [23], а также С. А. Малюгин [38] представили классы несистематических совершенных кодов (длин > 127 и > 15 соответственно), имеющих тривиальную группу автоморфизмов. 15 1999г. С. А.Малюгину удалось улучшить нижнюю оценку числа двоичных совершенных кодов, построив не менее 2~ 2" таких кодов.

Наибольшее внимание в теории кодирования заслуженно уделяется двоичным кодам, и связано это с тем, что многие явления, имеющие место в общем у-ичном случае, могут быть исследованы в двоичном и * затем обобщены. В последние годы более интенсивно стали изучаться также троичные коды. В диссертации М. Сванстрёма [44] изложена серия результатов но троичным равновесным кодам. Там же, а так же в [45] описан класс совершенных (я,3;п— 1)з-кодов, п — 2к > 4 (совершенных троичных равновесных кодов длины п с весом п — 1 и расстоянием 3), построенный на основе циклического представления двоичного кода

Хемминга. В таких кодах максимальное подмножество слов с одним и тем же носителем образует линейный двоичный совершенный код с расстоянием 3 код Хемминга в алфавите {1,2} (в этом смысле этот код Хемминга содержится в соответствующем троичном равновесном коде). Дж. ванЛннт и Л.Толхьюзен показали в [34], что не существует нетривиальных совершенных равновесных кодов с расстоянием .'}, кроме (п, 3; и — 1 )з-кодов н (п, 3; п)з-кодов.

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

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

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

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

2. Установлена нижняя оценка числа ???,-ква.зигрупп порядка 4, с помощью которой получена новая нижняя оценка числа совершенных двоичных кодов.

3. Описаны все (с точностью до эквивалентности) /^-линейные совершенные коды.

4. Описаны индуктивные способы построения совершенных троичных равновесных кодов с расстоянием 3. Показана нижняя оценка 2-"/" для числа таких кодов длины п веса п — 1 и для числа совершенных ааросочеталнй в Е" без параллельных рёбер на расстоянии меньше 3.

Г». Построен класс оптимальных (плотно упакованных в слое веса п) троичных равновесных кодов длины п — 22&+1 веса п — 1 с расстоянием 5.

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

Апробация работы. Результаты работы докладывались на международных конференциях: Седьмой международной конференции по алгебраической и комбинаторной теории кодирования АССТ'2000 (Болгария, Нанско, 2000 г.) и конференции "Дискретный анализ и исследование операций" БАОН^ООО (Новосибирск, 2000 г.) - и на Второй научной молодёжной школе по дискретной математике (Нижний Новгород, 1998 г.). Все результаты докладывались на семинарах НГУ и Института математики СО РАН "Дискретный анализ" и "Теория кодирования".

Публикации. По теме диссертации автором опубликованы работы [48]-[о2].

Объём и структура диссертации. Диссертация состоит из введения, двух глав и списка литературы. Объём диссертации - 64 страницы.

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

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

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

В разделе 1.2 "Комбинированная конструкция совершенных двоичных кодов" приводится конструкция расширенных совершенных кодов, ко торая объединяет в себе элемеЕггы нескольких ранее известных способов построения совершенных кодов. Построенный в Еп код (длины + 1) состоит из компонент (в тексте они называются //-компонентами, где ц € Е'"+1, т +1=2''' < п+ 1), каждая из которых является частью кода Фелпса [41], кода Моллара [39], кода Малюгина [16], кода, построенного при помощи метода а-компонент [2], или построена каким-нибудь другим, может быть неизвестным на данный момент, способом. Таким образом, с одной стороны, новая конструкция выделяет общее звено в построении некоторых ранее известных кодов, с другой стороны, возникает новая подзадача задачи конструирования и описания совершенных кодов конструирование и описание /¿-компонент, которая интересна даже в частных случаях, например, при т + 1 = (п + 1)/4.

Частными случаями комбинированной конструкции являются обобщения конструкций Фелиса н Моллара, которые получаются за счёт возможности независимо выбирать параметры /¿-компонент. Интересным следствием является новое нетривиальное свойство совершенных кодов -"универсальность": для данного набора из М совершенных кодов длины г существует совершенный код длины тг+т + г, где М < 2т-1о8-'<т + 1!, содержащий в«- заданные коды (а также любые их сдвиги) в параллельных г-мерных гранях.

В разделе 1.3 приводится конструкция »(-квазигрупп порядка 1. которая даёт нижнюю оценку их числа и в сочетании с основанной на »/»-квазигруппах конструкцией совершенных кодов Фелиса [41] позволя-

рт получить новую нижнюю оценку числа совершенных кодов, равную ^ ^ - <»+1) ^ ~ к,|4(1 >

Раздел 1.1 посвящен построению и полному перечислению ^-линейных расширенных совершенных кодов. Описываются неэквивалентные /^-линейные расширенные совершенные коды, которые (с точностью до эквивалентности) полностью исчерпывают класс таких кодов.

13 разделе 2.2 предлагаются индуктивные способы построения совершенных (л,3;и - 1)з-кодов, п = 2к > 16, которые являются аналогом комбинированной конструкции нелинейных совершенных двоичных кодов, и описывается конструкция, при помощи которой можно построить болес-22 различных совершенных (п,3;н— 1)з-кодов, откуда сразу следует, что такие коды содержат в себе (в описанном выше смысле) много различных нелинейных совершенных двоичных кодов.

Таким образом, способы построения совершенных (п,3;п — 1)3-кодов родственны конструкциям совершенных двоичных кодов с расстоянием 3, последние коды в свою очередь являются частным случаем совершенных троичных равновесных кодов, а именно являются (»!,3;?!)з-кодами.

В разделе 2.3 строится класс оптимальных (п, 5; а — 1)3-кодов, которые не являются совершенными, но порождают плотную упаковку в соседнем слое веса п (каждая вершина веса находится на расстоянии не более 2 от одной кодовой вершины веса п — 1, отсюда сразу следует, что зти коды оптимальны). При построении этих кодов используются почти совсем нелинейные функции, которые применялись ранее для построения хороших двоичных кодов с расстоянием 5 - линейных кодов БЧХ и их обобщений и кодов Препараты [26].

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

На множестве Еп — {0,1}™ слов длины п в алфавите {0,1}'! определим метрику (Хеммннга) следующим образом:

%..-) = "¿'л»,.,), «»,=,) = {? ¡¡Л

г—О

Совершенным двоичным коболе длины п с расстоянием 3 называется .множество С слов из {О,!}11 мощности = такое что

''(<"ь<':>) > •> для любых различных слов Г] и с2 из С (такие коды существуют при любом п = 2к — 1, см., например, [15]).

Расшартны.и совершенным двоичным кодом длины п + 1 с расстоянием 4 называется множество С слов из {0,1}'!+\ такое что с/(с], (••>) > 4 для любых различных слов С1 и с2 из С" и после удаления из всех кодовых слов последней буквы получается совершенный двоичный код.

Пусть число » + 1 представлено в виде ?! + 1 = (т + 1)(г+ 1). где |и + 1 и г + 1 - степени двойки. Позиции в словах из £" + 1 пометим двумя индексами и представим элементами массива размера (т+ 1) х (г 4- 1):

У— (.'/00, Мл,-~,У0г, ■ ■ Ую, УтО, •••.2/тог) = \_ihj )

| Де У1} £ {0, 1}. Сумму строк такого массива обозначим через р[у):

Пусть т - произвольное натуральное число, А - конечное множество мощности >■, и ч : А'п —> А - ш-ариая операция. Если на любых наборах с, с' 6 Ат, различающихся ровно в одной координате, (/(с) ф </(с'), то пара (Л,</) называется пьквазигруппой порядка г и А называется посипи мм этой квазигруппы.

Пусть £ А,"|+1 = (0,1}"г+1. Назовём ц-компонентой такое подмножество К[, пространства Еп+1, что ¡Л',,1 = ('"+1), р(с) — // для любого с. £ К¡1 и с1(с!, сг) > 4 для любых различных о и с2 из К^.

Пусть <7,п+| - расширенный совершенный двоичный код длины ш + 1 и для каждого /г £ задана /г-компонента Л'(1. Теорема 3 утвержда-

ет, что объединение компонент

является расширенным совершенным двоичным кодом.

Таким образом, если имеется способ построения /«-компоненты, то с помощью этой теоремы мы можем построить расширенный совершенный код. С этой точки зрения конструкции Фелпса [41] и Моллара [39] совершенных кодов можно интерпретировать как способы построения ^-компонент (теоремы 4 и 6 соответственно). За счёт возможности независимо выбирать параметры построения каждой ^-компоненты упомянутые конструкции обобщены в теоремах 5 и 7.

Из описанных конструкций вытекает возможность построения совершенного кода, содержащего все наперёд заданные совершенные коды одной длины в параллельных гранях. Точнее, для любого множества {("[',...,( .'д;} мощности М совершенных кодов длины г и целого положительного)», такого что 2т-1°82(т+1) > м, существует такой "универсальный'" совершенный код С"' длины п = тг + т + г, что каждый код (''■, 1 < У < Л/, можно получить (в последних г координатах), зафиксировав некоторым образом первые тг + га координат кода С". Теорема 8 утверждает, чт о при любом натуральном т число »«-квазигрупп порядка 4 с фиксированным носителем не меньше чем Зт+122 +1 — 2т+33"'.

Пусть 1 - любое натуральное число и п = 2г — 1. Из теоремы 9, являющейся следствием теоремы 8 и конструкции Фелпса [41]. следует, ч то число совершенных двоичных кодов длины п — 1 не меньше че.м

С= и

Так как эта оценка усиливает оценку Малюгина, то в множестве кодов, описанных приведённой конструкцией, есть коды, неизвестные ранее. Квате¡тарным кодом длины т называется множество С С ¿4'1 слов длины га в алфавите {0, 1,2,3}, замкнутое относительно операции сложения по модулю 4. Заменив символы 0, 1, 2, 3 на двоичные пары 00, 01, 11, 10 соответственно, коду С сопоставим двоичный код Ф{С) длины 2т. Код ф(С), а также любой код, который можно получить из него перестановкой координат, называется ^-линейным.

Пусть Г1, г>> - неотрицательные целые числа, А''1"''2 - матрица размера (?1 -И'2 +1) х 2~Г|+Г2, составленная из всевозможных столбцов, в которых первый элемент равен 1, последние г2 элементов принадлежат множеству {0,2}, остальные г\ элементов принадлежат множеству {0,1,2,3}. Пусть С1-''2 = {г- е zf"i'+r2 : ЛГ1'Г*ХТ — О (тос14)}, где О - столбец из нулей.

Из теоремы 10 следует, что код Сг,'гз ~ ф(С1,Г2) является расширенным совершенным кодом с расстоянием 4.

Теоремы 11 и 12 утверждают, что построенные таким образом ^4-лпнейные совершенные коды попарно неэквивалентны и любой /4-линейный (п. 2"/2п, 4)-код эквивалентен одному из построенных.

Теорема 13 подводит итог: при любом п — 2к > 16 существует ров)го [(А + 1)/2] попарно неэквивалентных ¿4-линейных (и,2"/2я,4)-

кодов. Пусть V,, = {0,1, X}" - множество слов длины п в алфавите {0,1,Х}. Весом и;1(а) слова а € Уя назовём число позиций, в которых а содержит 0 или 1.

Для слов а и Ь из V,, через ё(а,Ь) обозначим число координат, в которых а и Ь различны.

Троичным пространством Джонсона Уз(п,и>) называется подпространство метрического пространства \'п, состоящее из всех его слов веса ик Множество С С ¿1з(п, и>) назовём троичным равновесным кодом веса и> длины п с расстоянием или {7г,<1;ю)з-кодом, если для любых различных а и Ь из С выполнено неравенство с1{а,Ь) > ¡1.

/

Если с € ¿Ь{п- Ш) и 0 < ги' < п, то через В™'и' (с) обозначим множество слов нз ,7з(п,1с'), расположенных на расстоянии не более 6 от с. Мощность такого множества зависит только от п, «>, и>' и <5 и не зависит от с.

(п,(1\и>)з-код С плотно упакован в ¿?з(п,и>'), или плотно упакован ь слое веса «', если для любого х £ ¿7з(п>и>') найдётся ровно одно с € С, такое что <1{х, с) < {(й — 1)/2]. Такой код является оптимальным, т. е. не существует кода с теми же параметрами, но большей мощности, (н, г/; <е)з-код С называется совершенным, если он плотно упакован в слое веса /р.

Сложение Ф по модулю два чисел из {0,1} доопределим на множество {0,1, X} равенствами ОфХ = 1фХ = ХфХ = Х (символ X можно

ю .

трактовать как множество {0,1}).

Совершенный (п, 3; га — 1)з~код назовём совершенным Х-кодом длины п (каждое слово такого кода содержит ровно один символ X).

В подразделе 2.1.1 показывается, что совершенным Х-кодам длины »i можно взаимно однозначно поставить в соответствие совершенные паросочетання в Еп без параллельных рёбер, находящихся на расстоянии 1 или 2.

Пусть число п представлено в виде произведения п = inv, где т > 4 и г > 4 - степени двойки. Позиции в словах из {О, 1,Х}" пометим двумя индексами и представим элементами массива размера т х г: У - (У11,У12.-,У1г,У21.--мУтг) = {»¿i}.-=MÍ,j=T7' где f'J € {0.1.Х}. Сумму строк такого массива обозначим через р(у), т. е.

(г г г \

J=1 J=1 J=1 /

Пусть fi € ¿h{m, m — 1). Назовём fi-компонентой такое подмножество Л"(4 пространства Jz{n,n — 1), что = 2n_m, р(с) — /i для любого с € Л";, и rf(ci, со) > 3 для любых различных с\ и с-, из А',,.

Пусть С"' - совершенный Л'-код длины т и для каждого // £ С" задана //-компонента Кц. Теорема 15 утверждает, что объединение /«компонент

С= U

рее™

является совершенным Л'-кодом.

Таким образом, чтобы построить совершенный Л'-код длины и, нужно задать базовый код Ст размерности т и для каждого кодового слова ¡i из С'" построить /i-компоненту, параметры построения которой зависят только от /«. В теоремах 16 и 17 (аналогах теорем 4 и 6) приводятся два способа построения /¿-компонент.

Оператор / : Ек —> Ек называется почти совсем нелинейным, если el IC.TCM а у равнени й

( а + b = а

1 л«) + т = /з

при (а, ¡3) ф (0,0) либо не имеет решений, либо имеет ровно два решения.

Пусть / : Ек —> Ек - взаимно однозначный оператор. Пусть 7ь72>----7 п " все элементы Ек, п = Рассмотрим два линейных двоичных кода длины п:

п ti

Со = {.Г = (*,,х-2,.. ■, ar„) G : £i = £ Ч-» =0},

¿=l i=i

я n

С\ = {.с = (д , .г2,..., Х„) € Еп : Y, = l> Е > =

!=1 1=1

Очевидно, что С о - расширенный код Хемминга. Поскольку оператор / обратим, то /(71),/(72), ■ • ■,/(Tu) ~ все элементы Ек, и С] - смежный класс некоторого другого кода Хемминга. Множество рёбер

('= {{í-o, СХ> :с0 € Со,С! € Сь</(с0,с,) = 1}

является наросочетанием мощности |С| = |Со| — КМ = 2"/2п, причём любые два различных ребра из С расположены на расстоянии Хемминга не менее 3 друг от друга.

Предположим далее, что оператор / почти совсем нелинейный. Тогда (лемма 9) все рёбра фиксированного направления из С расположены на расстоянии не менее 5 друг от друга.

Пусть \ - взаимнооднозначное отображение между множеством рёбер булева куба 1С" и множеством Vn, определяемое равенством

Л({(04.....fj-ь 0,cr¿+i, ■ • • > с«), (""ь • ■ - (Ot-i, 1,0-j+b----fn)})

• = (""i.....fi-i,X, cr,+1,.. ,,crn).

По теореме 19 код Cx — {\'(e) : e G 6'} является (n,5;n — 1)з-кодом, плотно упакованным в слое веса п.

Взаимно однозначные почти совсем нелинейные операторы существуют при всех нечётных к (например, f(x) = хл, г £ GF(2k)). Таким образом, при всех п = существуют (п,5;п — 1)з-коды, плотно упа-

кованные в слое веса п.

Литература

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

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

[3] Августинович С. В., Соловьева Ф. И. О несистематических совершенных кодах // Проблемы передачи информации. 1996. Т. 32. Вып. 3. С. 17-50.

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

[•5] Васильева А. Ю. Спектральные свойства совершенных двоичных (н,3}~ кодов // Дискрет, анализ и исслед. операций. 1995. Т. 2. №'.2. С. 16-25.

[G] Васильева А. Ю. О расстояниях между совершенными двоичными кодами // Дискрет, анализ и исслед. операций. Серия 1. 1098. Т. 5. К-. 1. С. 16-25.

[7] Васильева А. Ю. Локальные спектры совершенных двоичных кодов // Дискрет, анализ и исслед. операций. Серия 1. 1999. Т. 6. №. 1. С. 16-25.

[8] Васильева А. Ю. Характеризация совершенных кодов через принадлежность линейному многообразию // Проблемы теоретической кибернетики, XII международная конференция (Нижний Новгород, 17-22 мая 1999). Тезисы докладов, часть 1. М.: Изд-во мех.-мат. фак-та МГУ, 1999. С. 31.

[9] Зиновьев В. А. Комбинаторные методы конструкции и анализа нелинейных кодов, исправляющих ошибки. Автореферат, док. дисс. М., 1988. 30с.

[10] Зиновьев В. А., Леонтьев В. К. Теорема о несуществовании совершенных кодов над полями Галуа. М., 1973. (Препринт / ИППИ АН СССР).

[11] Зиновьев В. А., Леонтьев В. К. О совершенных кодах // М.: ИППИ, 1972. Выи. I. С. 26-35.

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

[13] Кузьмин A.C., Нечаев A.A. Построение помехоустойчивых кодов с использованием линейных рекурренг над кольцами Галуа // Успехи математических наук. 1992. Т. 47, вып. 5. С. 183-184.

[14] Кузьмин А. С., Нечаев А. А. Линейно представимые коды и код Кер-дока над произвольным полем Галуа характеристики 2 // Успехи математических наук. 1994. Т. 49, вып. 5. С. 165-166.

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

[16] Малюгин С. А. О нижней оценке числа совершенных двоичных кодов // Дискрет, анализ и исслед. операций. Серия 1. 1999. Т. 6, №4. С. 44-48.

[17] Нечаев A.A. Код Кердока в циклической форме // Дискретная математика. 1989. Т. 1, вып. 4. С. 123-139.

[18] Пулатов А. К. К структуре плотно упакованных (п, 3)-кодов // Методы дискретного анализа в теории кодов и схем: Сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1976. Вып. 29. С. 53-60.

[19] Соловьёва Ф. И. О двоичных негрунповых кодах // Методы дискретного анализа в изучении булевых функций и графов: Сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1981. Вып. 37. С. 65-76.

[20] Соловьёва Ф. И. Факторизация кодогенерирующих дизъюнктивных нормальных форм // Методы дискретного анализа в изучении булевых функций и графов: Сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1988. Вып. 47. С. 66-88.

[21] Шапиро Г. С., Злотник Д. Л. К математической теории кодов с исправлением ошибок // Кибернетический сб. М.: Изд-во иностр. лит., 1962. Вып. 5. С. 7-32.

[22] Avgustiiiovich S. V., Solov'eva F. I. Existence of nonsystematic perfect binary codes // Proc. of Fifth Int. Workshop on Algebraic and Comb. Coiling Theory, Sozopol, Bulgaria, June 1996. P. 15-19.

[23] Avgustinovich S.V., Solov'cva F.I. Perfect binary codes with trivial automotphism group // Proc. of Int. Workshop on Information Theory, Killarney, Ireland, June 1998. P. 114-115.

[21] Avgnstinovich S. V., Lobstein A. C., Solov'eva P.I. Partitions by perfect binary codes, using concatenation and latin squares // Proc. Seventh Int. Workshop on Algebraic and Comb. Coding Theory. Bansko, Bulgaria. June, 2000. P. 15-50.

[25] Cohen G.. Honkala I., Litsyn S., Lobstein A. Covering codes. North-Holland: Elsevier, 1998.

[26] van Dam E.R., Fon-Der-Flaas D. Uniformly packed codes and more distance ragular graphs from crooked functions //J. Algebraic Combinatorics, to appear (2000).

[27] Delsarte P. Bounds for unrestricted codes by linear programming, Philips Res. Reports. 1072. V. 27, 272-289.

[28] Etzioii Т.. Vardy A. Perfect binary codes: Constructions, properties and enumeration // IEEE Trans. Inform. Theory, 1994. Vol. 10. N3. P. 751-763.

[29] Hamburger P., PippertR.E., and Weakley W.D. On a leverage problem in the hyperenbe // Networks, 1992. Vol. 22. P. 435-439.

[ 30] Haininons A. R., Jr, Kumar P. V., Calderbank A. R., Sloane N.J. A., Sole P. The linearity of Kerdock, Preparata, Goethals, and related codes // IEEE Trans. Inform. Theory., 1994. Vol.40, №'2. P.301-319.

[31] Heclen О. Л new construction of group and nongroup perfect codes // Inform, and Control, 1977. Vol.34. N4. P.314-323.

[32] Kurakin V. L., Kuzmin A.S., Mikhalev A. V., and Nechaev A. A.

Linear recurring sequences over rings and modules // J. of Math. Sciences, 1995. Vol.70, NG. P. 2793-2915.

[33] Laborde J.-M. Une nouvelle famille de codes binaires, parfait, not) lineaires // C. R. Acad. Sci. Paris., 1983. Vol. 297, N 1. P. 67-70.

[31] van Lint J., Tolhuizen L. On perfect ternary constant-weight, codes // Desighns, Codes and Cryptography, 1999. Vol. IS, N 1-3. P. 231-234.

[35] Lloyd S. P. Binary block coding, Bell Syst. Techn. J., 3G (1957) 517. (Русский перевод: С.П. Ллойд. Бинарное блочное кодирование // Кибернетический сб. М.: Ичд-iio иностр. лит., 19G0. Вып. 1. С. 206-226.)

[30] Lobstein А. С., Zinov'ev V. A. On new perfect binary nonlinear codes // Appl. Algebra Eng. Common. Comput.., 1997. Vol.8. P. 415-420.

[37] Lobstein A. C., Zinov'ev V. A. Constructions of perfect binary nonlinear codes // Proceedings of Sixth international workshop "Algebraic and combinatorial coding theory'". Pskov, Russia, September, 6-12, 1998. P.249-254.

[38] Malyugin S. A. Perfect codes with trivial automorphism group // Proc. of If Int. Workshop on Optimal Codes, Sozopol, Bulgaria, June 1998. P. 163-167.

[39] Mollard M. A generalized parity function and its use in the construction of perfcct codes // S1AM J. Algebraic Discrete Methods. 1986. Vol.7. N1. P. 113-115.

[40] Phelps K.T. A combinatorial construction of perfect codes // SIAM J. Algebraic Discrete Methods. 1983. Vol.4, N.3. P.398-403.

[41] Phelps K.T. A general product construction for error correcting codes // SIAM J. Algebraic Discrete Methods, 1984. Vol.5, N.2. P. 224-228.

[42] Solov'eva F.I. Constructions of perfect binary codes // Preprint 98-042. Univ. Bielefeld, 1998. 12p.

[43] Solov'eva F.I., Vasil'ev Y. L. Interdependence between perfect binary codes and their projections // Proc. Seven Joint Swedish-Russian Workshop on Information Theory. St.-Petersburg, 1995, 17-22 June. M.: Institute for Information Transmission Problems. RAS. 1995. P. 239-242.

[44] Svanstrom M. Ternary codes with weight constraints. Dissertation X-572. Linkôping Univ., 1999.

[45] Svanstrom M. A class of perfect ternary constant-weight, codes // Desighns, Codes and Cryptography. 1999. Vol. 18, N 1-3. P. 223-230.

[IC] Tietavamen A. On the nonexistence of perfect codes over finite fields // SIAM J. Appl. Math. 1973. Vol.24, N1. P.88-96.

[47] Vasil'eva A.Yu. On centered characteristic function of perfect binary codes // Proceedings of Sixth international workshop "Algebraic and combinatorial coding theory". Pskov, Russia, September, 6-12, 1998. P.224-227.

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

[18] Кротов Д.С. Векторные поля, коды Препараты и разбиения булева куба на цилиндры // Проблемы теоретической кибернетики, ХП международная конференция (Нижний Новгород, 17-22 мая 1999). Тезисы докладов, часть 1. U.: Изд-во мех.-мат. фак-та МГУ, 1999. С. 122.

[49] Кротов Д. С. О совершенном коде, содержащем в качестве гюдкодов заданный набор совершенных кодов // Дискрет, анализ и исслед. операций. Серия 1. 2000. Т. 7, №1. С. 40-48.

[50] Кротов Д. С. Нижние оценки числа m-квачигрупп порядка 4 и числа совершенных двоичных кодов // Дискрет, анализ и исслед. операций. Серия 1. 2000. Т. 7, №2. С. 47-53.

[51] Кротов Д. С. -ST-i-линейные совершенные коды // Международная конференция "Дискретный анализ и исследование операций": материалы конференции (Новосибирск, 26 июня - 1 июля 2000). Новосибирск: Изд-во Института математики, 2000. С. 74.

[52] Krotov D.S. Combining construction of perfect binary codes and of perfect ternary constant-weight codes // Proc. Seventh Int. Workshop on Algebraic and Comb. Coding Theory. Bansko, Bulgaria. Juni