Спектральные свойства совершенных двоичных кодов

• Автор: Васильева, Анастасия Юрьевна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1999
• Место защиты: Новосибирск
• Количество страниц: 79 с.

1 Граневые спектры совершенных кодов
1.1 Обобщение теоремы Шапиро - Злотника
1.2 Граневой спектр совершенного кода
1.3 К строению дополнений совершенных кодов
1.4 Расстояния между совершенными кодами
1.5 О мощности пересечения совершенного кода с к-мерной
.гранью
2 Локальные и межвесовые спектры совершенных кодов
2.1 Связь между локальными спектрами совершенного кода в ортогональный гранях п-куба
2.2 Свойства локальных спектров
2.3 Межвесовые спектры совершенных кодов
3 Линейное представление характеристических функдий
совершенных кодов
3.1 Характеризация совершенных кодов в терминах линейного многообразия
3.2 Свойства множества совершенных кодов
3.3 Новое представление некоторых классов совершенных
кодов
Литература

Объектом исследования в данной работе являются совершенные двоичные коды длины п с кодовым расстоянием 3. В диссертации устанавливаются некоторые структурные свойства таких кодов, и на этой основе проводится изучение множества всех совершенных двоичных кодов с расстоянием 3 и дается характеризация этого множества в терминах линейных многообразий.
Задаче описания всех совершенных двоичных кодов уделяется большое внимание в теории кодов, исправляющих ошибки, однако ввиду большой сложности этой задачи, она до сих пор не получила решения. Имеющиеся на данный момент работы по теории совершенных кодов можно условно разделить на два больших направления: работы, главным содержанием которых является построение новых совершенных кодов с целью пополнения запаса известных кодов или с целью нахождения кодов с новыми свойствами, и работы, изучающие общие для всех совершенных кодов свойства. Данная работа относится к последнему направлению.
Везде далее под совершенными кодами мы будем иметь ввиду совершенные двоичные коды с расстоянием 3, если специально не оговорено иное. Исключительное рассмотрение совершенных кодов с расстоянием 3 обусловлено несуществованием других совершенных д-ичных (д > 2) кодов, кроме кодов с параметрами кода Хэмминга — длина п = (д* — 1)/(
В.А. Зиновьевым и В.К. Леонтьевым [12, 13, 14] и независимо А. Ти-твайненом [36]).
Отметим некоторые результаты, касающиеся совершенных кодов.
Ряд свойств, общих для всех совершенных кодов, свидетельствуют о большой регулярности строения произвольного совершенного кода. В 1957 году С.П. Ллойд [29] и в 1959 году независимо Г.С. Шалиро и Д.Л. Злотник [35] установили, что количество вершин совершенного кода, находящихся на заданном расстоянии от данной кодовой вершины, не зависит ни от выбора этой вершины, ни от выбора совершенного кода. В 1972 году Ф. Дельсарт [23] и независимо в 1973 году А.К. Пулатов [16] доказали, что количество вершин произвольного совершенного кода в любой грани размерности не менее (п + 1)/2 зависит только от размерности грани. В 1995 году С.В. Августинович [2] показал, что любой совершенный код однозначно определяется своими кодовыми вершинами, имеющими вес (п + 1)/2.
Однако различных совершенных кодов весьма много. Первый мощный класс совершенных кодов был построен в 1962 году Ю.Л. Васи-льевым [5, 6] и содержит 2 2 неэквивалентных совершенных кодов, наилучшая на данный момент нижняя оценка количества совершенных кодов длины п получена в 1996 году С.В. Августиновичем и Ф.И. Соловьевой [21] и равна 22~*~ s< +1)62_,_ °51 + ', а наилучшая верхняя оценка количества совершенных кодов получена в 1995 году С.В. Августиновичем [2] и равна 22“ 151,1е(п+1)+1°8“«(”+1* Опишем некоторые свойства, свидетельствующие об отсутствии единообразия строения совершенных кодов.
Код С называется дистанционно регулярным, если выполнено следующее условие: если вершины х,у € С находятся на расстоянии к, то количество вершин z g С, для которых расстояние до вершины х равно г и расстояние до вершины у равно j, зависит только от г, j и к, но не зависит от выбора вершин х и у. С.В. Августинович и Ф.И. Соловьева [4] доказали, что все совершенные коды длины 15 и более

Тогда
4, = Ка € Щ | 7,1 Э ^(х,у)}|
= |{аеТТПае7ь(х,у)}|=((* + '’“<г)/2)-
Следовательно, формула (2.11) верна. Лемма 6 доказана.
Лемма 7. Пусть 0 < I < т < к. Тогда
Е «С(1?Ы)«С(Ь'Ы)
- Е ЙЧ.-М^2). (2.12)
П — к )
Доказательство аналогично доказательству предыдущей леммы. Пусть х,у 6 С, причем х € 6 и расстояние между ними равно ё, где
т — I < ё < I + т. Пусть — количество вершин а € ТУ/,, для
которых х,у е 7а. Обозначим через и(х,у) вершину максимального
веса в грани 7х у. Нетрудно вычислить, что
, , .. , I + т
ш<(и(х,у )) = к
Аналогично лемме 6,
*х,у = |{а £ ИТ I 7а Э 7и(х,у)}|
IГ 42 I х 11 ( п - к + (I + т - ё) /2
= ]{а 6 Ц?к | а в 7ц(х,у)}| = _к ) ■
Следовательно, формула (2.12) верна. Лемма 7 доказана.
Целью леммы 8 будет выражение чисел
№) 11 > О,
через числа