Совершенные коды и n-арные квазигруппы: конструкции и классификация тема диссертации и автореферата по ВАК РФ 01.01.09, доктор физико-математических наук Кротов, Денис Станиславович

• Кротов, Денис Станиславович
• доктор физико-математических наук
• 2010

Оглавление диссертации доктор физико-математических наук Кротов, Денис Станиславович

Введение

Содержание работы.

I Квазигруппы

Основные определения.

Обозначения.

1 О разложимости двукратных МДР-кодов и разделимости п-арных квазигрупп порядка

1.1 Введение.

1.2 Определения и обозначения.

1.3 Вспомогательные результаты.

1.4 Разложение 2-МДР-кодов.

1.5 Разложимость (п, 2)4 МДР-кодов.

1.6 Разделимость п-арных квазигрупп порядка 4.

Введение диссертации (часть автореферата) на тему «Совершенные коды и n-арные квазигруппы: конструкции и классификация»

3.2 Основные определения.107

3.3 Основной результат .109

3.4 Доказательство леммы 3.5.111

3.5 Сублинейные п-квазигруппы.116

4 О свитчинговой разделимости графов 118

4.1 Введение.118

4.2 Доказательство теоремы 4.2.119

4.2.1 Случай к > 3.119

4.2.2 Случай к = 3.122

4.3 Доказательство теоремы 4.3.124

4.4 Графы, булевы функции, квазигруппы .126

4.4.1 Расширенные булевы функции.126

4.4.2 n-Арные квазигруппы.129

II Совершенные коды 133

5 Вложение в совершенный код 134

6 О числе 1-совершенных двоичных кодов: нижняя оценка 141

6.1 Введение.141

6.2 Предварительные сведения.142

6.3 ДА конструкция расширенных 1-совершенных кодов . 145

6.4 Вычисления .148

6.5 Нижняя оценка числа 1-совершенных кодов.154

7 О диаметрально совершенных равновесных троичных кодах 159

7.1 Введение.159

7.2 Пространство Хп и ребра в {0,1}п.161

7.3 Совершенные коды с расстоянием 3.162

7.3.1 Совершенные коды с расстоянием 3 и совершенные па-росочетания в {0,1}га.164

7.3.2 Конструкция совершенных кодов с расстоянием 3. . . 165

7.3.3 Группа автоморфизмов и транзитивность.167

7.3.4 Неэквивалентность.169

7.4 Диаметрально совершенные коды с расстоянием 4.172

7.5 Диаметрально совершенный коды с расстоянием 5.174

7.5.1 Связь с кодами Препарата .177

8 О Z2k-дуальных двоичных кодах 182

8.1 Введение.182

8.2 Определения и основные факты.185

8.2.1 ^2т-Линейные коды.186

8.2.2 Ко-^-линейные коды.188

8.3 ^-Дуальность двоичных кодов.190

8.4 Ко-¿^-линейные расширенные 1-совершенные коды.193

8.4.1 1-Совершенные коды.193

8.4.2 Класс 1-совершенных кодов в .195

8.4.3 Ко-^-линейные расширенные 1-совершенные двоичные коды .197

8.4.4 Замечание об общем случае Z2^m.197

8.5 ¿^-Линейные коды Адамара.198

8.6 Несуществование неизвестных ко-^к-линейных расширенных совершенных кодов и ¿^-линейных кодов Адамара . . . 199

Литература 204

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

Введение

В диссертации рассматриваются комбинаторные вопросы теории парных квазигрупп и 1-совершенных двоичных кодов. Доказаны признаки разделимости п-арных квазигрупп, получена характеризация класса парных квазигрупп порядка 4. Рассмотрены конструкции 1-совершенных двоичных кодов и построение из них кодов в троичном алфавите.

Актуальность темы. Объектами исследования настоящей работы являются 1-совершенные двоичные коды и п-арные квазигруппы, которые также известны как латинские гиперкубы (многомерное обобщение латинских квадратов) и эквивалентны максимально дистанционно разделимым (МДР) кодам с расстоянием 2. Оба класса объектов рассматриваются в метрическом пространстве Хэмминга Н™, носителем которого является множество {0,1,., д — 1}" слов длины п алфавита {0,1,., д — 1}, а расстояние между двумя словами есть число позиций, в которых эти слова различаются. Если д есть степень простого числа, Н™ можно снабдить структурой векторного пространства над конечным полем СР(д), мы будем этим пользоваться в случае д = 2. Пространство Хэмминга удобно также рассматривать как граф, в котором два слова соединены ребром тогда и только тогда, когда они отличаются только в одной позиции. Максимальную клику этого графа будем называть линией (линия состоит из д слов, совпадающих во всех позициях кроме одной), а вершину вместе с ее окрестностью — 1-шаром с центром в этой вершине. Множество слов в Н™ называется 1 -совершенным кодом, если каждый 1-шар содержит ровно одну кодовую вершину. Множество слов в Н™ называется МДР-кодом с расстоянием 2, если каждая линия содержит ровно одну кодовую вершину. (Напомним, что кодовым расстоянием произвольного подмножества в Н™ из двух или более вершин называется минимальное расстояние между двумя различными вершинами. Так, 1-совершенный код, если у него больше одной вершины, имеет расстояние 3.) Функция из {0,1,., q — 1}п в {0,1,., q — 1} называется п-арной квазигруппой, порядка д, если на каждой линии она принимает все q различных значений, каждое ровно по одному разу. Если значение n-арной квазигруппы трактовать как дополнительный символ, то получится МДР-код с расстоянием 2.

Определения 1-совершенных кодов и МДР кодов в приведенной выше форме имеют определенную общность, которая в частности подчеркивает, что оба класса относятся к категории «точных» комбинаторных конфигураций. Эти классы кодов можно единообразно определить иначе: если удаление некоторого независимого множества вершин графа Н™ приводит к регулярному графу степени (q — 1)п — 1 или (q — 2)п, то это множество является 1-совершенным кодом или МДР-кодом с расстоянием 2 соответственно. Такая постановка близка к вопросам, изучаемым в алгебраической теории графов. На самом деле, как 1-совершенные коды, так и МДР-коды с расстоянием 2 являются важнейшими частными случаями так называемых регулярных разбиений, в англоязычной литературе известными также как equitable partitions (термин «equitable» в данном контексте не имеет удобного перевода), а на русском языке больше известными как совершенные раскраски. Наряду с дистанционно регулярными графами и схемами отношений, совершенные раскраски (equitable partitions) являются популярными объектами алгебраической комбинаторики, см. напр. [57], [73].

Отмеченная связь постановок была упомянута, чтобы подчеркнуть общую природу изучаемых объектов, к существу вопросов, рассматриваемых в диссертации, прямого отношения она не имеет. Для нас более важна конструктивная связь: существуют способы построения 1-совершенных кодов из n-арных квазигрупп, впервые предложенные К. Т. Фелпсом [110], [111], см. также [22], [83]. Поэтому результаты, полученные для п-арных квазигрупп, важны и для теории 1-совершенных кодов, к примеру, эта связь использовалась в работах [I], [51], [83], [28], [89]. В контексте диссертации эта конструктивная связь имеет также и историческое значение: именно она привлекла мой интерес к n-арным квазигруппам, сформировавшийся в одно из основных направлений исследований.

Прежде чем перейти к рассмотрению классов 1-совершенных кодов и n-арных квазигрупп отдельно, хотелось бы отметить один общий для них вопрос, вопрос о числе объектов. Известно, что число 1-совершенных кодов в Hq растет дважды экспоненциально при росте п, если q есть степень простого числа, а п = (qm — l)/(q — 1) (это необходимое для существования 1-совершенных кодов условие на п следует из известных соображений: мощность пространства должна делиться на мощность 1-шара), то ocTi±o(;i) есть нижняя оценка на число кодов имеет вид , где с — некоторая константа. В двоичном случае такая оценка, с с = 1/2, была установлена Ю.Л.Васильевым одновременно с открытием нелинейных 1-совершенных кодов [10], на случай произвольного д, равного степени простого числа, конструкция обобщена Дж. Шонхеймом [122]. Следует отметить, что существование совершенных кодов в Н™ для q, не представимого в виде степени простого числа, является известной открытой проблемой в данной области; однако, если только существует хотя бы один такой код, известные методы позволяют построить коды для бесконечного числа значений п с тем же q [111], причем число таких кодов будет расти дважды экспоненциально по п. Известная верхняя оценка числа 1-совершенных кодов с точки зрения асимптотики двойного логарифма не отличается от числа всевозможных подмножеств Н* (в двоичном случае 22" const'logn) см> Улучшения нижних оценок в сериях работ [3], [33], [I], [V] (глава 6 диссертации), для двоичного случая, и [67], [30], [44], [31], [83], для кодов над д-значным алфавитом, важны больше с точки зрения понимания возможного строения совершенных кодов, чем в контексте проблемы асимптотики двойного логарифма числа кодов, хотя для q > 3 нижняя граница этой асимптотики была реально поднята [31], [83] (в последней работе для этого использовалась связь с n-арными квазигруппами).

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

Ситуация с n-арными квазигруппами порядка q > 3 аналогична. Дважды экспоненциальное по п число квазигрупп составного порядка следует из известной конструкции сплетения n-арных квазигрупп (термин «сплетение» в данном случае никак не соотносится со сплетением групп), а для простых порядков, начиная с 5, установлено относительно недавно [92]. Для порядка меньше 4 проблема с числом п-арных квазигрупп тривиальна, поскольку существует только одна п-арная квазигруппа, с точностью до простых преобразований эквивалентности. Верхнюю оценку числа объектов, с точки зрения асимптотики двойного логарифма, удается несколько улучшить по сравнению с числом всех функций, см. [43]. Однако в случае д > 4 асимптотики двойного логарифма нижней и верхней оценок числа п-арных квазигрупп порядка д, как и для 1-совершенных кодов, расходятся. Единственным классом объектов, для которых проблема асимптотики двойного логарифма числа решена, является класс п-арных квазигрупп порядка 4. Более того, существует и является одним из основных результатов данной диссертации характеризация этого класса и, как следствие, известна асимптотика самого числа объектов. (На самом деле, асимптотика получена В. Н. Потаповым ранее и опубликована в нашей совместной статье [42].) Проблема оценки дважды экспоненциального числа комбинаторных объектов известна и в других разделах дискретной математики. Одним из примеров является класс бент-функций, которые определяются как булевы функции {0,1}п —> {0,1}, на которых определенным образом заданная мера нелинейности достигает теоретической верхней границы. Бент-функции существуют при всех четных п, а нижняя и верхняя оценки их числа, как и для числа 1-совершенных двоичных кодов, имеют вид 2^ и 2А соответственно [60]. Таким образом, проблема оценок подобного рода достаточно широка, и осмысление способов ее решения — это дело будущего. Хочется подчеркнуть, что величины столь большого роста находятся за рамками интуитивного восприятия (по крайней мере автора диссертаи ции), поэтому бывает трудно вообразить природу тех факторов, которые могли бы оказать существенное влияние на верхнюю и, кроме известных конструктивных подходов, нижнюю оценки. Трудность восприятия таких чисел приводит порой к тому, что для некоторых исследователей получение дважды экспоненциальной нижней оценки закрывает вопрос о числе объектов — это число по своей величине в каком-то смысле сравнимо с числом всех подмножеств пространства. На самом же деле нижняя оценка по сравнению с верхней остается почти ничем даже после логарифмирования. п-Арные квазигруппы. Сам термин алгебраический и, строго говоря, обозначает пару (2,/), где I] — некоторое множество, а / — п-арная операция такая, что в уравнении х0 = /(а^,., хп) значения любых п переменных из а?о, жь хп всегда однозначно задают значение оставшейся переменной. Как видно из названия, понятие п-арной, или многоместной (в англоязычной терминологии используются термины «ро1уас1ю» или «тиН;агу»), квазигруппы является обобщением понятия группы. Действительно, в случае п = 2 добавление аксиомы ассоциативности приводит к определению группы. Некоторое стандартное упрощение терминологии, которым мы будем в дальнейшем пользоваться, — называть п-арной квазигруппой саму операцию, как правило это не приводит к разночтениям. В случае конечного носителя £ такие отображения также известны в комбинаторике как латинские гиперкубы порядка q— |Е| и часто, по аналогии с латинским квадратом (случай п — 2), интуитивно ассоциируются с п-мерной таблицей, д х д х . х д, заполненной символами алфавита £ правильным образом — так, что в каждом ряду (линии) каждого из п базовых направлений все символы встречаются в точности по одному разу. Однако в некоторых случаях оказывается гораздо удобней работать с графиком {(хо, XI,., хп) ' ^о = /(^ь • ■ •, жга)} п-аРной квазигруппы, а не с самой операцией. В теории кодирования такие множества известны как МДР-коды с расстоянием 2. При рассмотрении графика п-арной квазигруппы вместо самой операции оказывается, что зависимая переменная наделена теми же «правами», что и все остальные, что делает многие формулировки более естественными, а доказательства более короткими. Однако в некоторых вопросах, например, при рассмотрении суперпозиции двух или более квазигрупп, функциональная форма все же оказывается необходимой, поэтому порой приходится использовать одновременно обе терминологии.

Фундаментальные результаты в алгебраической теории п-арных квазигрупп, которыми во многом определяется развитие этой теории начиная с 60-х годов прошлого века, принадлежат В. Д. Белоусову (см. напр. [8], [7]), начинавшему свою деятельность в этой области под руководством А. Г. Куроша. Отдельные классы многоместных операций со свойством однозначной обратимости изучались значительно раньше. Одной из первых работ является работа В.Дёрнте [66], положившая начало изучению угарных групп (ассоциативных п-арных квазигрупп).

В последнее время возрастает интерес к п-арным квазигруппам как к комбинаторному объекту, что отчасти стимулируется возможными приложениями к теории кодирования и криптографии (см. напр. [123]), отчасти просто тем, что п-арные квазигруппы (латинские гиперкубы) являются очень естественным обобщением латинских квадратов — классических математических объектов, известных многим со школьной скамьи. В частности, появилось несколько работ с результатами по классификации латинских гиперкубов с малыми параметрами [104], [85], [18], [84], [124], [100], [103]. В последней работе известных австралийских математиков Б.Мак-Кэя и Я.Уонлеса [103] получено число латинских п кубов порядка 4 до п = 5, порядка 5 до п = 4 и порядка б до п — 3, причем сосчитано также число классов эквивалентности для различных естественно определенных эквивалентностей, представители классов доступны на веб-ресурсе [102]. Продвинуться в бблыние размерности при помощи переборных алгоритмов не представляется возможным па любых компьютерах, доступных в ближайшем будущем (напомним, что число объектов растет дважды экспоненциально). Число n-арных квазигрупп порядка 3 не было упомянуто не случайно. Существует только одна такая квазигруппа, с точностью до изотопии (перестановки элементов носителя независимо в каждом аргументе), а всего — 3 • 2п. Это факт достаточно простой и, хотя самая ранняя из известных ссылок [70] (см. также [94, Corollary 13.25], [80], [124], [136]) относится к последней декаде прошлого века, был известен намного раньше. Таким образом, порядок 4 — первый нетривиальный порядок с точки зрения п-арных квазигрупп. Именно этому порядку уделяется наибольшее внимание в диссертации и, хотя некоторые утверждения интересны в более общем контексте и применимы также и для других, не обязательно конечных, порядков, изначальной мотивацией и основным применением результатов исследований, описанных в первой части диссертации, в настоящий момент является классификация n-арных квазигрупп порядка 4.

В первой моей работе [I] 2000 года по n-арным квазигруппам порядка 4 нижняя оценка числа таких объектов устанавливается подсчетом числа изотопов /?,-арных квазигрупп, полученных сплетением квазигрупп порядка 2 (позже такие квазигруппы порядка 4 были названы полулинейными). После этого В.Н.Потапов сформулировал гипотезу, согласно которой любая п-арная квазигруппа порядка 4 полулинейна или разделима, то есть представима в виде бесповторной суперпозиции квазигрупп меньшей арности. В частности, из этого следовало бы, что класс полулинейных угарных квазигрупп асимптотически самый мощный, и нижняя оценка в [I] асимптотически точна. Несмотря на простоту формулировки и некоторые интуитивные соображения, на которых строилась гипотеза, найти короткое доказательство, по состоянию на текущий момент, не удалось. Полный текст имеющегося доказательства состоит из четырех статей [VII], [42], [IX], [X], каждая из которых представляет самостоятельное исследование, со своими подходами и терминологией и результатами, актуальность которых не ограничивается контекстом тг-арных квазигрупп порядка 4. (Две статьи принадлежат автору диссертации, две написаны в соавторстве в В.Н.Потаповым. В диссертацию не вошла только работа [42], поскольку основная лемма, как и главный результат статьи — асимптотика числа ?г-арных квазигрупп порядка 4, — принадлежат В.Н.Потапову.) Промежуточным этапом исследования, который позволил поближе ознакомиться с предметом и разработать инструментарий, являлось получение верхних оценок числа квазигрупп порядка 4 [91], [42].

Возможно, утверждение о строении п-арных квазигрупп порядка 4 не прошло достаточную проверку временем и вниманием математической общественности, чтобы говорить о вероятности того, что более короткое решение не будет найдено в ближайшее время. Однако разработанная для текущего доказательства теория обладает достаточной степенью общности, чтобы быть интересной вне контекста n-арных квазигрупп порядка 4. Кроме того, обнаруживаются некоторые связи, которые косвенно указывают на то, что все действительно не так просто, как может показаться из формулировок теорем. Мне бы хотелось упомянуть эти связи, не столько как какое-то обоснование, сколько просто потому, что они кажутся интересными. Недавно В.Н.Потапов анонсировал следующее утверждение [118]: (*) любая частичная п-арная квазигруппа порядка 4, значения которой заданы на {0,1,2,3}n1 х {0,1}; может быть дополнена до n-арной квазигруппы {0,1,2,3}п —> {0,1, 2,3}. Этот факт имеет следующую эквивалентную формулировку: пусть множество вершин графа Щ разбито на два подмножества, порождающие регулярные подграфы степени п, тогда эти подграфы являются или не являются двудольными одновременно. Оказывается [89], подобным образом (в терминах одновременной двудольности элементов регулярного разбиения множества вершин графа Хэмминга) можно переформулировать и следующую проблему: (**) каждый ли максимальный по мощности двоичный код длины 2Ш — 3 с расстоянием 3 можно получить двукратным укорочением некоторого 1 -совершенного кода длины 2Ш — 1 ? Более того, как отмечено в [89], для некоторого подкласса кодов положительный ответ на вопрос (**) эквивалентен утверждению (*). В то же время в общем случае ответ на вопрос (**) отрицательный [107], контрпример был найден с использованием компьютера. Это говорит о том, что не существует общих аргументов, доказывающих (*), которые могли бы быть обобщены на (**), и для доказательства (*) нужен подход, использующий специфику именно этой задачи. И действительно, имеющееся доказательство [41] использует характеризацию n-арпых квазигрупп порядка 4 и даже при этом достаточно трудоемко.

Вернемся к общим вопросам, касающимся п-арных квазигрупп. Важнейшую роль в их исследовании, • как комбинаторных объектов, играет понятие разделимости. Разного вида редуцируемость больших объектов к меньшим рассматривается для многих классов математических объектов, в частности, бесповторная суперпозиция исследуется как для дискретных (см. напр. [29]), так и для непрерывных объектов (см. напр. работу [23], связанную с решением тринадцатой проблемы Гилберта). Для класса многоместных квазигрупп, который замкнут относительно бесповторной суперпозиции, естественный вопрос представимости в виде такой суперпозиции возник на самом раннем этапе их исследования, как и вопрос существования неразделимых (не представимых в виде бесповторной суперпозиции) п-арных квазигрупп. Этот вопрос известен как одна из проблем В. Д. Белоусова (проблема номер 5 из монографии [7]) и решен для различных порядков в работах В. Д. Белоусова и М.Д. Сандика [8], Б. Р. Френкина [47], В. В. Борисенко [9], М. М. Глухова [12], М. А. Акивиса и В.В.Гольдберга [13], [14], [50], Кротова, В.В.Потапова и П.В.Соколовой [92]. Единственным известным в настоящее время способом строить неразделимые п-арные квазигруппы конечных порядков больше 3 является метод свитчинга, состоящий в локальной замене значений квазигруппы на некотором подмножестве области определения. (Следует заметить, что в алгебраической теории п-арных квазигрупп больше известно понятие приводимости, то есть представимости в виде бесповторной суперпозиции с тем же порядком переменных, что и в самой квазигруппе, см. напр. [7]. Это связано с тем, что порядок переменных существенен для выполнимости дополнительных алгебраических аксиом.) Крайне важным для понимания структуры разделимых п-арных квазигрупп фактом является существование и в определенном смысле единственность канонического разложения в древовидную бесповторную суперпозицию неразделимых квазигрупп и групп, установленные А. В. Черемушкиным [48]. Интересно, что аналогичное утверждение верно для существенно более широкого класса функций, сильно зависимых от каждой переменной [125].

Разделимости квазигрупп посвящены три из четырех глав первой части диссертации. Первоначально исследования ориентировались на описание п-арных квазигрупп порядка 4, которое можно считать главным результатом первой части диссертации. Однако результат главы 2 в представленном виде — завершенное утверждение, применимое к п-арным квазигруппам произвольного порядка (результаты, дополняющие теорию именно для произвольного порядка, получены в последней совместной работе [XI]) и полезное для исследования классов многоместных квазигрупп, замкнутых относительно взятия ретракта (ретракт многоместной квазигруппы получается при фиксации константами значений одного или более аргументов). Примеры использования полученного в главе 2 признака разделимости для характеризации классов п-арных квазигрупп приведены в главе 3. Интересно было бы, аналогично [125], обобщить результаты главы 2 на более широкий класс функций, сильно зависимых от каждой переменной.

Совершенные коды. Согласно широко известной теореме В.А.Зиновьева, В.К.Леонтьева и Э.Титвайнена [20], [21], [132], при q равном степени простого числа нетривиальные (т.е. 0 < г < п/2) г-совершенные коды существуют только в следующих случаях: пт — \ \ Ип1

- 1-совершенные коды в Щ " с параметрами кода Хэммин-га, который является единственным с точностью до эквивалентности линейным кодом из этого класса. (Р. У. Хэмминг рассматривал только двоичные коды [78]; общая конструкция, как и коды Голея, предложена М. Дж. Е. Голеем в полустраничной заметке [74].) Однако при непростых д существуют групповые (то есть замкнутые относительно сложения, но не обязательно относительно умножения на скаляр) 1-совершенные коды, неэквивалентные коду Хэмминга [97]. Число же негрупповых 1-совершенных кодов оценивается снизу дважды экспоненциальным относительно размерности пространства числом, см. последние нижние оценки в [V], [83].

- Коды Голея: построенные М. Дж. Е. Голеем [74] 3-совершенный код в Я|3 и 2-совершенный код в Я31. Каждый из этих кодов является единственным с точностью до эквивалентности [64].

Вопрос существования д-значных совершенных кодов в случае, когда д не есть степень простого числа, является известной открытой проблемой в общей теории совершенных кодов. Известно, что не существует ¿-совершенных кодов при Ь 0 {1,2,6,8} [54] и при I > 1 в случае д = 2аЗ/3 [6]; известно, что не существует групповых совершенных кодов [95]; известно, ЧТО не существует 1-СОВершеННОГО кода в #6 [75] (последнее следует из несуществования двух ортогональных латинских квадратов размера 6x6 [131]) — наименьших параметрах, удовлетворяющих необходимым условиям: п — 1 = 0 тос! д (следствие из теоремы Ллойда для произвольного алфавита [95], [5], [15]) и ^п"1)/^1 = 0 тос! (п(д-1) + 1) ([81], [121], следствие равномерной распределенности вершин 1-совершенного кода по подкубам размерности (п — 1)/д + 1 ).

Существование совершенных кодов исследуется и в отличных от хэмминговых метрических пространствах и графах. Ввиду применимости мощного аппарата алгебраической теории графов, особый интерес с этой точки зрения уделяется дистанционно-регулярным графам. Так, известная гипотеза Дельсарта [15] о несуществовании нетривиальных совершенных кодов в графах Джонсона на данный момент не решена (см. последнюю V работу [68] на эту тему и библиографию в ней), в то время как аналогичный факт для графов Грассмана и графов билинейных форм доказан относительно давно Л. Чихарой [62] (другое доказательство представлено У. Дж. Мартином и З.Дж. Жу [101]). Среди многообразия работ по совершенным кодам в разных экзотических метрических пространствах отметим работу [87].

В главе 7 рассматриваются совершенные коды с расстоянием 3 в пространстве троичных п-слов веса п — 1 (то есть содержащих ровно один нуль). Такие коды были построены в работах М. Сванстрёма [130], [129], Дж. Ван Линта и Л. Толхьюзена [135] на основе смежных классов по двоичному коду Хэмминга. В моей работе [88], уже используя технику из теории нелинейных совершенных кодов, построено дважды экспоненциальное число совершенных троичных равновесных кодов. В главе 7 показано, что на основе смежных классов по коду Хэмминга можно строить как неэквивалентные совершенные коды, так и коды с новыми параметрами — оптимальные коды с расстоянием 5, — в пространстве троичных п-слов веса п — 1. Заметим, что хотя рассматриваемое пространство, в отличие от случая равновесных двоичных кодов, не обладает свойством дистанционной регулярности, равновесные д-значные коды являются достаточно популярными объектами в теории кодирования.

Как уже было отмечено, над конечными полями непростой мощности возможно существование неэквивалентных 1-совершенных кодов, замкнутых относительно покоординатного сложения. В двоичном случае такой код единственный — код Хэмминга. Однако при помощи отображения Грея 0 —^ 00, 1 —» 01, 2 —» 11, 3 —>■ 10, при покоординатном действии являющимся изометрией между тг/2-мерным четверичным пространством с метрикой Ли и тг-мерным двоичным пространством Хэмминга, некоторые нелинейные коды представимы в виде образов линейных кодов над кольцом Zгí [93] (такие коды принято считать линейными, в смысле [93]) или над смешанным алфавитом. Возможность представлять хорошие нелинейные двоичные коды как линейные над недвоичными алгебраическими структурами была впервые обнаружена А. А. Нечаевым в работах [35], [36]. В статье А. Р. Хэммонса и др. [93] для подобного представления использованы изометрические свойства отображения Грея. Идея использования масштабных изометрий для построения кодов была развита в работе А.А.Нечаева и Т.Хонольда [37]. 1-Совершенные и расширенные 1-совершенные двоичные коды, представимые при помощи кода Грея как линейные коды над ^ или смешанным алфавитом, изучались в работе [II] и в работах Дж. Боргеса, К. Т. Фелпса и Дж. Рифы [56], [114], [55]; оказалось, что число таких неэквивалентных кодов растет примерно как логарифм от длины, и значения параметров, характеризующих «близость» к линейному коду (ранг — размерность линейной оболочки; размерность ядра — множества периодов), для них различные. Более широкое обобщение линейных кодов — транзитивные коды, то есть такие, что стабилизатор кода в группе изометрий пространства действует транзитивно на элементах кода. Классы транзитивных совершенных двоичных кодов строились Ф.И.Соловьевой [45] и В.Н.Потаповым [39], причем в последней работе установлено, что число неэквивалентных кодов растет экспоненциально с ростом длины. В диссертации (глава 8) предложен способ построения расширенных 1-совершенных кодов из линейных кодов над кольцом Использованное обобщение отображения Грея неоднозначно при к > 2, что позволяет сохранить плотность упаковки. Интересно, что в отличие от случая к = 2, в общем случае транзитивность полученных кодов не очевидна, и исследования по этому вопросу еще не проводились.

Цель работы: построение новых классов п-арных квазигрупп и кодов — 1-совершенных двоичных кодов, а также бесконечного класса оптимальных троичных равновесных кодов с новыми параметрами; характеризация классов тг-арных квазигрупп малого порядка и линейных аналогов расширенных 1-совершенных кодов над кольцами ; обнаружение новых зависимостей внутри исследуемых классов объектов.

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

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

1) Доказаны признаки разделимости п-арных квазигрупп: для порядка 4 в терминах связности прообраза двух значений и для произвольного порядка в терминах максимальной арности неразделимого ретракта.

2) Получена характеризация п-арных квазигрупп порядка 4: любая п-арная квазигруппа порядка 4 является полулинейной или разделимой. Показано, что все п-арные квазигруппы порядков 5 и 7, бинарные ретракты которых изотопны циклической группе, являются разделимыми при п > 4.

3) Введено понятие свитчинговой разделимости графов, которая эквивалентна разделимости п-арных квазигрупп, построенных по этим графам определенным образом. Показано, что если при удалении любой вершины или любых двух вершин графа получается разделимый подграф, то сам граф является разделимым. С другой стороны, построена бесконечная серия неразделимых графов, у которых удаление любой вершины приводит к разделимому подграфу. Это дает пример неразделимых п-ариых квазигрупп, все (п—1)-арные ретракты которых разделимы.

4) Доказано, что любой, в том числе нелинейный, двоичный код с расстоянием 3 всегда можно вложить в 1-совершенный код некоторой большей длины.

5) Предложен метод построения 1-совершенных кодов, дающий самый многочисленный из известных в настоящий момент класс 1-совершенных двоичных кодов.

6) Построен бесконечный класс диаметрально совершенных (как следствие, оптимальных) троичных равновесных кодов с расстоянием 5.

7) Представлено новое обобщение отображения Грея Ф : Z™k — связанное с известным обобщенным отображением Грея ц) следующим образом: если взять два дуальных линейных Я2*-кода и построить из них двоичные коды, используя обобщения (р и Ф отображения Грея, то весовые нумераторы полученных двоичных кодов будут связаны тождеством Мак-Вильямс. Описаны классы кодов Адамара и расширенных 1-совершенных кодов, полученных из линейных ^2*-КОДОВ при помощи старого и нового обобщенного отображения Грея.

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

Апробация работы. Результаты работы докладывались на научных семинарах «Математические вопросы кибернетики» ММФ НГУ, «Теория информации и теория кодирования» ИППИ РАН, семинаре Кафедры безопасности информационных систем ГУАП, «Теория кодирования» и Общеинститутском семинаре Института математики им. С. Л. Соболева СО РАН, в Похангском государственном университете (г. Поханг, Республика Корея, цикл из 6 лекций), включены в список важнейших научных результатов ИМ СО РАН за 2006, 2008 и 2009 годы, прошли апробацию на следующих научных конференциях и совещаниях:

• Международные конференции по алгебраической и комбинаторной теории кодирования АССТ (2002 в Царском Селе, 2004 в Болгарии, 2006 в Звенигороде);

• Международная конференция по оптимальным кодам и смежным вопросам ОС 2005 (Болгария);

• Международная конференция по кодированию и криптографии WCC 2001 (Париж);

• Международная конференция по схемам отношений, кодам и дизайнам Сот2МаС 2004 (Ю. Корея);

• Международная конференция «Coding Theory Days in St.-Petersburg» (2008, Санкт-Петербург);

• Конференция «Математика в современном мире» (2007, Новосибирск) ;

• IX международный семинар «Дискретная математика и ее приложения» (2007, Москва);

• VI сибирская научная школа-семинар «Компьютерная безопасность и криптография» SIBECRYPT (2007, Горно-Алтайск);

• Конференции «Дискретный анализ и исследование операций» DAOR (2000, 2004, Новосибирск). ч

Публикации. Основные материалы диссертации опубликованы в 12 статьях в научных журналах, рекомендованных ВАК. Работы [XI] и [X], результаты которых изложены в главах 2 (кроме раздела 2.2) и 3, написаны в неразделимом соавторстве с Владимиром Николаевичем Потаповым. Работы [IV] и [V] (главы 5 и 6) — в неразделимом соавторстве с Сергеем Владимировичем Августиновичем. По главам, результаты опубликованы:

Список литературы диссертационного исследования доктор физико-математических наук Кротов, Денис Станиславович, 2010 год

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

2. Августинович С. В., Соловьева Ф. И. О несистематических совершенных двоичных кодах // Проблемы передачи информации. — 1996. — Т. 32, № 3.— С. 47-50. http://mi.mathnet.ru/ppi344.

3. Августинович С. В., Соловьева Ф. И. Построение совершенных двоичных кодов последовательными сдвигами «-компонент // Проблемы передачи информации.— 1997.— Т. 33, № 3.— С. 15-21.http://mi.mathnet.ru/ppi374.

4. Августинович С. В., Соловьева Ф. И., Хеден У. О проблеме рангов и ядер совершенных кодов // Проблемы передачи информации. — 2003. — Т. 39, № 4. — С. 30-34. http://mi.mathnet.ru/ppi313.

5. Бассалыго Л. А. Обобщение теоремы Ллойда на произвольный алфавит // Проблемы управления и теории информации. — 1973. — Т. 2, № 2. С. 133-137.

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

7. Белоусов В. Д. п-Арные квазигруппы. — Кишинев: Штиинца, 1972.

8. Белоусов В. Д., Сандик М. Д. п-арные квази-группы и лупы // Сибирский математический журнал. — 1966. — Т. 7, № 1. — С. 31-54.

9. Борисенко В. В. Неприводимые п-квазигруппы на конечных множествах составного порядка // Квазигруппы и лупы. — Кишинев: Штиинца, 1979. Т. 51 из Мат. Исслед. — С. 38-42.

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

11. Васильев Ю. Л., Августинович С. В., Кротов Д. С. О подвижных множествах в двоичном гиперкубе // Дискрет, анализ и исслед. операций.— 2008. — Т. 15, № 3.— С. 11-21. http://mi.mathnet.ru/da530.

12. Глухое М. М. О многообразиях (г, ^-приводимых п-квазигрупп // Сети и квазигруппы. — Кишинев: Штиинца, 1976. — Т. 39 из Мат. Исслед. С. 67-72.

13. Гольдберг В. В. Об инвариантной характеристике некоторых условий замыкания в тернарных квазигруппах // Сибирский математический журнал. — 1975. Т. 16, № 1. — С. 29-43.

14. Гольдберг В. В. О приводимых, групповых и (2п+2)-эдричных (п+1)-тканях многомерных поверхностей // Сибирский математический журнал. 1976. - Т. 17, № 1. - С. 44-57.

15. Дельсарт Ф. Алгебраический подход к схемам отношений теории кодирования: Пер. с англ. Библиотека Кибернетического Сборника.— М.: Мир, 1976.- 136 с.

16. Думер И. И. Некоторые новые равномерно упакованные коды. — М.: МФТИ, 1976.— Труды МФТИ. Серия «Радиотехника и электроника». Рр. 72-78.

17. Зиновьев В. А. Обобщенные каскадные коды // Проблемы передачи информации. — 1976. —Т. 12, № 1.— С. 5-15. http://mi.mathnet.ru/ppil670.

18. Зиновьев В. А., Зиновьев Д. В. Двоичные расширенные совершенные коды длины 16, построенные обобщенной каскадной конструкцией // Проблемы передачи информации. — 2002. — Т. 38, № 4. — С. 56-84.http: //mi.mathnet.ru/ppil325.

19. Зиновьев В. А., Зиновьев Д. В. Двоичные расширенные совершенные коды длины 16 ранга 14 // Проблемы передачи информации. — 2006. — Т. 42, № 2. — С. 63-80. http://mi.mathnet.ru/ppi45.

20. Зиновьев В. А., Леонтьев В. К. О совершенных кодах // Проблемы передачи информации. — 1972. — Т. 8, № 1. — С. 26-35.http://mi.mathnel.ru/ppi772.

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

22. Зиновьев В. А., Лобстейн А. Об обобщенных каскадных конструкциях совершенных двоичных нелинейных кодов // Проблемы передачи информации. — 2000. — Т. 36, № 4. — С. 59-73. http://mi.mathnet.ru/ppi495.

23. Колмогоров А. Н. О представлении непрерывных функций нескольких переменных в виде суперпозиций непрерывных функций одной переменной и сложения // ДАН СССР. — 1957. — Т 114, № 5. — С. 953956.

24. Константинеску И., Хайзе В. Метрика для кодов над кольцами классов вычетов целых чисел // Проблемы передачи информации.— 1997. — Т 33, № 3. — С. 22-28. http://mi.mathnet.ru/ppi375.

25. Кротов Д. С. Комбинированная конструкция совершенных двоичных кодов // Проблемы передачи информации. — 2000. — Т. 36, № 4. — С. 74-79. http://mi.mathnet.ru/ppi496.

26. Кротов Д. С. Индуктивные конструкции совершенных троичных равновесных кодов // Проблемы передачи информации.— 2001.— Т. 37, № 1.—С. 3-11. http://mi.mathnet.ru/ppi505.

27. Кротов Д. С., Потапов В. Н. О кратных МДР- и совершенных кодах, не расщепляемых на однократные // Проблемы передачи информации.— 2004.— Т. 40, № 1.— С. 6-14. http://mi.mathnet.ru/ppill9.

28. Кротов Д. С., Потапов В. Н. О свитчинговой эквивалентности парных квазигрупп порядка 4 и совершенных двоичных кодов // Проблемы передачи информации. — 2010. — Т. 46, № 3. — С. 22-28.http://mi.inathnet.ru/ppi2019.

29. Лось А. В. Построение совершенных g-значных кодов последовательными сдвигами а-компонент // Проблемы передачи информации.— 2004. — Т. 40, № 1. — С. 40-47. http://mi.mathnet.ru/ppil22.

30. Лось А. В. Построение совершенных g-ичных кодов свитчингами простых компонент // Проблемы передачи информации. — 2006. — Т. 42, № 1.— С. 34-42. http://mi.mathnet.ru/ppi35.

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

32. Малюгин С. А. О нижней оценке числа совершенных двоичных кодов // Дискрет, анализ и исслед. операций. Сер. 1. — 1999. — Т. 6, № 4. — С. 44-48. http://mi.mathnet.ru/da327.

33. Малюгин С. А. Несистематические совершенные двоичные коды // Дискрет, анализ и исслед. операций. Сер. 1.— 2001.— Т. 8, № 1.— С. 55-76. http: / / mi.mathnet.ru/da215.

34. Нечаев А. А. Функции «след» в кольце Галуа и помехоустойчивые коды // Тезисы сообщений V Всесоюзн. симп. по теории колец, алгебр и модулей. — Новосибирск, Россия: 1982,— С. 97.

35. Нечаев А. А. Код кердока в циклической форме // Diskretnaya Matematika.— 1989. — Т. 1, № 4.— С. 123-139. http://mi.mathnet.ru/dm948.

36. Нечаев А. А., Хонолъд Т. Полновесные модули и представления кодов // Проблемы передачи информации. — 1999. — Т. 35, № 3. — С. 1839. http://mi.mathnet.ru/ppi450.

37. Пережогип А. Л. О специальных совершенных паросочетаниях в булевом кубе // Дискрет, анализ и исслед. операций. Сер. 1. — 2005. — Т. 12, № 4. — С. 51-59. http://mi.mathnet.ru/da79.

38. Потапов В. Н. О нижней оценке числа транзитивных совершенных кодов // Дискрет, анализ и исслед. операций. Сер. 1. — 2006. — Т. 13, № 4. — С. 49-59. http://mi.mathnet.ru/dall.

39. Потапов В. Н. О полностью коммутативно разделимых п-квази-группах // Труды XVI международной школы-семинара «Синтез и сложность управляющих систем». — Санкт-Петербург, Россия: 2006. — Июнь.-С. 88-91.

40. Потапов В. Н. О дополняемости частичных п-квазигрупп порядка 4 // Математические труды. — 2010. — Подано в печать.

41. Потапов В. Н., Кротов Д. С. Асимптотика числа п-квазигрупп порядка 4 // Сибирский математический журнал. — 2006. — Т. 47, № 4.— С. 873-887. http://mi.mathnet.ru/smj902.

42. Потапов В. Н., Кротов Д. С. О числе п-арных квазигрупп конечного порядка // Дискретная математика, — 2010.— Принято в печать.

43. Романов А. М. О разбиениях д-ичных кодов хемминга на непересекающиеся компоненты // Дискрет, анализ и исслед. операций. Сер. 1. — 2004. —Т. 11, № 3. — С. 80-87. http://mi.matimet.ru/dall4.

44. Соловьева Ф. И. О построении транзитивных кодов // Проблемы передачи информации.— 2005.— Т. 41, № 3.— С. 23-31.http://mi.mathnet.ru/ppil04.

45. Токарева Н. Н. Представление ¿^-линейных кодов Препараты с помощью векторных полей // Проблемы передачи информации. — 2005. — Т. 41, № 2. — С. 50-62. http://mi.mathnet.ru/ppi95.

46. Френкин Б. Р. О приводимости и сводимости в некоторых классах n-группоидов. II.— Кишинев: Штиинца, 1972.— Т. 7:1(23) из Мат. Исслед. — С. 150-162.

47. Черемушкин А. В. Каноническая декомпозиция п-арных квазигрупп // Исследование операций и квазигрупп. — Кишинев: Штиинца, 1988.- Т. 102 из Мат. Исслед.-С. 97-105.

48. Ahlswede R.} Aydinian Н. К., Khachatrian L. К. On perfect codes and related concepts // Des. Codes Cryptography. — 2001, —Vol. 22, no. 3.— Pp. 221-237. — DOI: 10.1023/A:1008394205999.

49. Akivis M. A., Goldberg V. V. Solution of Belousov's problem // Discuss. Math., Gen. Algebra Appl. — 2001. — Vol. 21, no. 1, — Pp. 93-103.

50. Avgustinovich S. V., Heden O., Solov'eva F. I. The classification of some perfect codes // Des. Codes Cryptography.— 2004.— Vol. 31, no. 3.— Pp. 313-318.— DOI: 10.1023/B:DESI.0000015891.01562.cl.

51. Avgustinovich S. V., Solov'eva F. I. Perfect binary codes with trivial automorphism group / / Proc. the Information TheoryWorkshop.— Killarney, Ireland: 1998. —June. — Pp. 114-115.—DOI: 10.1109/ITW.1998.706460.

52. Baker R. D., van Lint J. H., Wilson R. M. On the Preparata and Goethals codes // IEEE Trans. Inf. Theory.— 1983. — Vol. 29, no. 3.- Pp. 342345.— DOI: 10.1109/TIT. 1983.105 6675.

53. Best M. R. Perfect codes hardly exist // IEEE Trans. Inf. Theory.— 1983. — Vol. 29, no. 3. — Pp. 349-351. — DOI: 10.1109/TIT.1983.1056677.

54. Borges J., Phelps K. T., R.ifä J. The rank and kernel of extended 1-perfect Zi-linear and additive lion-^-linear codes // IEEE Trans. Inf. Theory.— 2003, — Vol. 49, no. 8. — Pp. 2028-2034. — DOI: 10.1109/TIT.2003.814490.

55. Borges J., Rifä J. A characterization of 1-perfect additive codes // IEEE Trans. Inf. Theory.— 1999.- Vol. 45, no. 8.— Pp. 1688-1697.- DOI:10.1109/18.771247.

56. Brouwer A. E., Cohen A. M.7 Neumaier A. Distance-Regular Graphs.— Berlin: Springer-Verlag, 1989.

57. Bryant D., Horsley D. A proof of Lindner's conjecture on embeddings of partial Steiner triple systems // J. Comb. Des. — 2008. — Vol. 17, no. 1. — Pp. 63-89. — DOI: 10.1002/jcd.20189.

58. Carlet C. Z2fc-linear codes // IEEE Trans. Inf. Theory. — 1998. — Vol. 44, no. 4. — Pp. 1543-1547. — DOI: 10.1109/18.681328.

59. Cadet C., Charpin P., Zinoviev V. Codes, bent functions and permutations suitable for DES-like cryptosystems // Des. Codes Cryptography.— 1998,— Vol. 15, no. 2.— Pp. 125-156.— DOI: 10.1023/A:1008344232130.

60. Chihara L. On the zeros of the askey-wilson polynomials, with applications to coding theory // SI AM J. Math. Anal — 1987. — Vol. 18, no. 1.— Pp. 191-207. — DOI: 10.1137/0518015.

61. Colbourn C. J., Rosa A. Triple Systems. — Oxford: Clarendon Press, 1999.

62. Delsarte P., Goethals J. M. Unrestricted codes with the Golay parameters are unique // Discrete Math. — 1975, — Vol. 12, no. 3, — Pp. 211-224.— DOI: 10.1016/0012-365X(75)90047-3.

63. Dillon J. F. APN polynomials: An update.— Fq9, International Conference on Finite Fields and their Applications. — 2009. — Available online: http://mathsci.ucd.ie/ gmg/Fq9Talks/Dillon.pdf.

64. Dornte W. Untersuchungen iiber einen verallgemeinerten Gruppenbegrieff // Mathem.atische Zeitschrift.— 1928.— Vol. 29.— Pp. 1-19.

65. Etzion T. Nonequivalent q- ary perfect codes / / SI AM J. Discrete Math. — 1996. Vol. 9, no. 3. - Pp. 413-423.

66. Etzion T., Schwartz M. Perfect const ant-weight codes // IEEE Trans.1.f. Theory.- 2004.— Vol. 50, no. 9.— Pp. 2156-2165,— dol10.1109/TIT.2004.833355.

67. Etzion T., Vardy A. Perfect binary codes: Constructions, properties and enumeration // IEEE Trans. Inf. Theory.— 1994.— Vol. 40, no. 3.— Pp. 754-763. — DOI: 10.1109/18.335887.

68. Finizio N. J., Lewis J. T. Enumeration of maximal codes // Congr. Numer. 1994. - Vol. 102. - Pp. 139-145.

69. Fon-Der-Flaass D. A bound on correlation immunity // Sib. Ehlektron. Mat. Izv. — 2007.— Vol. 4.— Pp. 133-135.— Avialable online athttp://semr.math.nsc.ru/v4/pl33-135.pdf.

70. Ganter B. Finite partial quadruple systems can be finitely embedded // Discrete Math. — 1974. — Vol. 10, no. 2. — Pp. 397-400. — DOI: 10.1016/0012365X(74) 90130-7.

71. Godsil C. D. Algebraic Combinatorics. — New York: Chapman and Hall, 1993.

72. Golay M. J. E. Notes on digital coding // Proc. IRE. 1949. - Vol. 37, no. 6. — P. 657. — DOI: 10.1109/JRPROC. 1949.233620.

73. Golomb S. W., Posner E. C. Rook domains, latin squares, and error-distributing codes // IEEE Trans. Inf. Theory. — 1964. — Vol. 10, no. 3. — Pp. 196-208. — DOI: 10.1109/TIT. 1964.1053680.

74. Gupta M. K., Bhandari M. C., Lai A. K. On linear codes over » // Des. Codes Cryptography. — 2005. — Vol. 36, no. 3. — Pp. 227-244. — DOI:10.1007/sl0623-004-1717-l.

75. Hamiltonian double latin squares / A. J. W. Hilton, M. Mays, C. A. Rodger, C. St. J. A. Nash-Williams // J. Comb. Theory, Ser. B.— 2003. —Vol. 87, no. 1.— Pp. 81-129. — DOI: 10.1016/S0095-8956(02)00029-1.

76. Hamming R. W. Error detecting and error correcting codes // Bell Syst. Tech. J. 1950. - Vol. 29, no. 2. - Pp. 147-160.

77. Hammons A. R., Kumar P. V., Jr, Calderbank A. R., Sloane N. J. A., Sole P. The ^-linearity of Kerdock, Preparata, Goethals, and related codes // IEEE Trans. Inf. Theory.— 1994. — Vol. 40, no. 2.- Pp. 301319.— DOI: 10.1109/18.312154.

78. Hartinger T. Cubes with the same number of filled cells in every line of sight.— Web publishing.— 2002-2004.— Available online:http: / / thartmge.de/binaryCube/BinaryCube4.htm.

79. Heden O. A Study of Mixed Perfect Codes: Thesis / University of Stockholm. — Stockholm,, 1977.

80. Heden O. A survey of perfect codes // Adv. Math. Commun. — 2008. — Vol. 2, no. 2,— Pp. 223-247.— DOI: 10.3934/amc.2008.2.223.

81. Heden O., Krotov D. S. On the structure of non-full-rank perfect q-ary codes // Adv. Math. Commun. — 2010. — Accepted. Eprint version:http://arXiv.org/abs/1001.0001.

82. Ito T. Creation method of table, creation apparatus, creation program and program storage medium. — 2004. — http: //ip.com/patapp/US20040243621

83. Jia X. W., Qin Z. P. The number of latin cubes and their isotopy classes // J. Huazhong Univ. Sci. TechnoL— 1999. —Vol. 27, —Pp. 104106. — In Chinese.

84. Kaski P., Ostergard P. R. J., Pottonen O. The Steiner quadruple systems of order 16 // J. Comb. Theory, Ser. A.— 2006.— Vol. 113, no. 8.— Pp. 1764-1770. — DOI: 10.1016/j.jcta.2006.03.017.

85. Kim H. K., Krotov D. S. The poset metrics that allow binary codes of codimension m to be m-, (m — 1)-, or (m — 2)-perfect // IEEE Trans. Inf. Theory.— 2008,— Vol. 54, no. 11.— Pp. 5241-5246.- DOI:10.1109/TIT.2008.929972.

86. Krotov D. S. Inductive constructions of perfect ternary constant-weight codes with distance 3 // Probl. Inf. Transm. — 2001. — Vol. 37, no. 1.— Pp. 1-9. — DOI: 10.1023/A:1010424208992.

87. Krotov D. S. On the binary codes with parameters of doubly-shortened 1-perfect codes // Des. Codes Cryptography. — 2010. — Vol. 57, no. 2. — Pp. 181-194. — DOI: 10.1007/sl0623-009-9360-5.

88. Krotov D. S., Avgustinovieh S. V. On the number of 1-perfect binary codes: A lower bound // IEEE Trans. Inf. Theory.— 2008.- Vol. 54, no. 4. — Pp. 1760-1765. — DOI: 10.1109/TIT.2008.917692.

89. Krotov D. S., Potapov V. N., Sokoloua P. V. On reconstructing reducible n-ary quasigroups and switching subquasigroups // Quasigroups Relat. Syst. 2008. - Vol. 16, no. 1. - Pp. 55-67.

90. Lay wine C. F., Mullen G. L. Discrete Mathematics Using Latin Squares. — Wiley, New York, 1998.

91. Lenstra Jr H. W. Two theorems on perfect codes // Discrete Math.— 1972. — Vol. 3, no. 1-3.— Pp. 125-132. — DOI: 10.1016/0012-365X(72)90028-3.

92. Lindner C. C. A survey of embedding theorems for Steiner sysrems // Topics on Steiner Systems / Ed. by C. C. Lindner, A. Rosa. — North-Holland, 1980. Vol. 7 of Ann. Discrete Math. — Pp. 175-202.

93. Lindstrom B. On group and nongroup perfect codes in q symbols // Math. Scand.- 1969,- Vol. 25.- Pp. 149-158.http: //www.mscand.dk/article.php?id=1942.

94. MacWilliams F. J., Sloane N. J. A. The Theory of Error-Correcting Codes. — Amsterdam, Netherlands: North Holland, 1977.

95. Malyugin S. A. Perfect codes with trivial automorphism group // Proc.the Int. Workshop on Optimal Codes.— Sozopol, Bulgaria: 1998,— June. Pp. 163-167.

96. Markovski S., Dimitrova V., Mileva A. A new method for computing the number of 77-quasigroups // Buletinul Academiei de Stiinte a Republicii Moldova. Matematica. — 2006. — Vol. 52, no. 3. — Pp. 57-64.

97. Martin W. JZhu X. J. Anticodes for the grassman and bilinear forms graphs // Des. Codes Cryptography.— 1995.— Vol. 6, no. 1.— Pp. 7379. — doi: 10.1007/bf01390772.

98. McKay B. D., Wanless I. M. Combinatorial data. Latin cubes and hypercubes. — http://cs.anu.edu.au/ bdm/data/latincubes.html.

99. McKay B. D., Wanless I. M. A census of small Latin hypercubes // SIAM J. Discrete Math. 2008. - Vol. 22, no. 2. - Pp. 719-736. - DOI:10.1137/070693874.

100. Mullen G. L., Weber R. E. Latin cubes of order < 5 // Discrete Math. — 1988. — Vol. 32, no. 3. — Pp. 291-298. — doi: 10.1016/0012-365x(80)90267-s.

101. Ostergard P. R. J., Pottonen O. There exist Steiner triple systems of order 15 that do not occur in a perfect binary one-error-correcting code // J. Comb. Des. — 2007,- Vol. 15, no. 6.- Pp. 465-468.— doi:10.1002/jcd.20122.

102. Ostergard P. R. J., Pottonen O. The perfect binary one-error-correcting codes of length 15: Part I—classification // IEEE Trans. Inf. Theory.— 2009. — Vol. 55, no. 10, — Pp. 4657-4660. — doi: 10.1109/tit.2009.2027525.

103. Ostergard P. R. J., Pottonen O. Two optimal one-error-correcting codes of length 13 that are not doubly shortened perfect codes // Des. Codes Cryptography. — 2010. — To appair.

104. Ostergard P. R. J., Pottonen O., Phelps K. T. The perfect binary one-error-correcting codes of length 15: Part II—properties // IEEE Trans. Inf. Theory.— 2010.— Vol. 56, no. 6,— Pp. 2571-2582.— DOI: 10.1109/TIT.2010.2046197.

105. Ostergard P. R. J., Svanstrom M. Ternary constant weight codes // Electr. J. Comb.— 2002.- Vol. 9, no. 1.- P. R41.http://www.combinatorics.org/Voluine9/Abstracts/v9ilr41.htriil.

106. Phelps K. T. A general product construction for error correcting codes // SI AM J. Algebraic Discrete Methods. — 1984. — Vol. 5, no. 2. — Pp. 224228. — DOI: 10.1137/0605023.

107. Phelps K. T. A product construction for perfect codes over arbitrary alphabets 11 IEEE Trans. Inf. Theory.— 1984.— Vol. 30, no. 5.— Pp. 769-771. — DOI: 10.1109/TIT. 1984.1056963.

108. Phelps K. T., LeVan M. Kernels of nonlinear Hamming codes // Des. Codes Cryptography.— 1995.— Vol. 6, no. 3,— Pp. 247-257,— doi:10.1007/BF01388478.

109. Phelps K. T., LeVan M. Nonsystematic perfect codes // SIAM J. Discrete Math.— 1999.— Vol. 12, no. 1,— Pp. 27-34.— doi:10.1137/S0895480196312206.

110. Phelps K. T., R.ifa J. On binary 1-perfect additive codes: Some structuralproperties // IEEE Trans. Inf. Theory.— 2002.— Vol. 48, 110. 9.— Pp. 2587-2592. — doi: 10.1109/tit.2002.801474.

111. Phelps K. T.} Bifa J., Villanueva M. Rank and kernel of additive (Z4-linear and non-Z4-linear) Hadamard codes // Proc. Ninth Int. Workshop on Algebraic and Combinatorial Coding Theory ACCT'2004. — Kranevo, Bulgaria: 2004. June. — Pp. 327-332.

112. Phelps K. T., R.ifa J., Villanueva M. On the additive (^-linear and non-^-linear) Hadamard codes: Rank and kernel // IEEE Trans. Inf. Theory.- 2006,— Vol. 52, no. 1,— Pp. 316-319.— dol10.1109/tit.2005.8c0452.

113. Phelps K. T., Villanueva M. On perfect codes: Rank and kernel // Des. Codes Cryptography.- 2002.- Vol. 27, no. 3,— Pp. 183-194.— doi: 10.1023/a:1019936019517.

114. Potapov V. N. On completion of latin hypercuboids of order 4 // Proc. Twelfth Int. Workshop on Algebraic and Combinatorial Coding Theory ACCT 2010. — Novosibirsk, R.ussia: 2010.— September. Pp. 251-255.

115. Preparata F. P. A class of optimum nonlinear double-error correcting codes // Inform. Contr.— 1968.- Vol. 13, no. 4, — Pp. 378-400. doi:10.1016/s0019-9958(68)90874-7.

116. B.ifa JPujol J. Translation-invariant propelinear codes // IEEE Trans. Inf. Theory.— 1997,— Vol. 43, no. 2,— Pp. 590-598.— DOI: 10.1109/18.556115.

117. R.00s C.: Preprint: Delft, the Netherlands, 1979.

118. Schônheim J. On linear and nonlinear single-error-correcting ç-ary perfect codes // Inform. Contr.— 1968.— Vol. 12, no. 1.— Pp. 23-26.— DOI:10.1016/S0019-9958(68)90167-8.

119. Shcherbacov V. A. Quasigroups in cryptology: E-print 1007.3572: arXiv.org, 2010. — Available at http://arxiv.org/abs/1007.3572.

120. Soedarmadji E. Latin hypercubes and MDS codes // Discrete Math. — 2006. — Vol. 306, no. 12. — Pp. 1232-1239. — DOI: io.ioi6/j.disc.2006.02.on.

121. Solov'eva F. I. Switchings and perfect codes // Numbers, Information and Complexity / Ed. by I. Althôfer, N. Cai, G. Dueck et al. — Kluwer Academic Publisher, 2000.- Pp. 311-314.

122. Solov'eva F. I. On perfect binary codes // Discrete Appl. Math. — 2008. — Vol. 156, no. 9. — Pp. 1488-1498. — DOI: 10.1016/j.dam.2005.10.023.

123. Spence E. Two-graphs // CRC Handbook of Combinatorial Designs / Ed. by C. J. Colbourn, J. H. Dinitz.— Boca Raton, FL: CR.C Press, 1996,— Pp. 686-694.

124. Svanstrôm M. A class of perfect ternary constant-weight codes // Des. Codes Cryptography. — 1999,— Vol. 18, no. 1-3.— Pp. 223-230.— DOI: 10.1023/A:1008361925021.

125. Svanstrôm M. Ternary Codes with Weight Constraints: Dissertation 572 / Linkoping University. — 1999.

126. Tarry G. Le problème des 36 officers // Comptes Rendu de l'Association Française pour l'Avancement de Science Naturel (National Academy of Sciences).- 1900, 1901, —Vol. 1, 2.- Pp. 122-123, 170-203.

127. Tietàvàinen A. On the nonexistence of perfect codes over finite fields // SIAM J. Appl. Math. 1973. - Vol. 24. - Pp. 88-96.

128. Zaslavsky T. Associativity in multary quasigroups: the way of biased expansions: eprint math.CO/0411268: arXiv.org, 2004.— Available athttp: / / arxiv. org/abs / math/0411268.Публикации автора по теме диссертации