Транзитивные совершенные коды и разбиения тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Гуськов, Георгий Константинович

• Гуськов, Георгий Константинович
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Гуськов, Георгий Константинович

Оглавление

Введение

1 Транзитивные совершенные коды

1.1 Предельно-транзитивные коды

1.1.1 Транзитивные совершенные коды длины 15 и транзитивные расширенные совершенные коды длины 16

1.1.2 Бесконечная серия предельно-транзитивных кодов

1.2 Проблема рангов транзитивных кодов

1.2.1 Пропелинейные совершенные коды длин 15 и 31 полного ранга

1.2.2 Проблема рангов

2 Вершинно-транзитивные разбиения

2.1 Вспомогательные утверждения

2.2 Конструкции вершинно-транзитивных разбиений

2.2.1 Конструкция А

2.2.2 Конструкция В

2.3 Нижние оценки

3 Конструкции разбиений пространства ^ на совершенные коды

3.1 Конструкция Васильева и разбиения на совершенные коды длины 15

3.2 Каскадная конструкция

3.3 Конструкция ijк-компонент. Нижняя оценка числа раз-

личных разбиений на совершенные коды

Заключение

Приложения

А Ранги и ядра транзитивных кодов длин 15 и 16

В Нетранзитивные координаты транзитивных кодов длины 16

С Матрицы пересечений разбиений пространства F7 на коды Хэмминга длины 7

Литература

Введение диссертации (часть автореферата) на тему «Транзитивные совершенные коды и разбиения»

Введение

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

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

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

Например, коды с богатыми группами автоморфизмов могут быть использованы в криптографии.

Проблема исследования разбиений пространства IFn (векторного пространства длины п над GF(2) по отношению к метрике Хэмминга) на совершенные коды тесно связана с проблемой построения таких кодов и изучения их свойств, поскольку асимптотики двойных логарифмов (если они существуют) числа различных совершенных кодов и числа различных разбиений на такие коды совпадают. Также следует упомянуть о том, что некоторые разбиения пространства Fn индуцируют раскраски векторов Fn на коды, связанные с оптоволоконными сетями, см., например, работу [36]. Кроме того, совершенные коды являются частным случаем так называемых регулярных разбиений, в англоязычной литературе известных также как equitable partitions, а в отечественной литературе больше известных как совершенные раскраски. Наряду с дистанционно регулярными графами и схемами отношений, совершенные раскраски являются популярными объектами алгебраической комбинаторики, см. [19]. Различные методы построения разбиений могут быть использованы для исследования их нетривиальных свойств, а также для построения новых кодов, в частности, совершенных (такие методы, например, описаны в работе [14]). Важность поиска новых методов построения кодов, а также методов их задания, объясняется, в частности, тем, что на их основе можно разрабатывать новые, более эффективные, методы передачи информации, или криптографические системы-коды.

Несмотря на значительные усилия ряда исследователей, многие вопросы теории совершенных кодов всё ещё остаются нерешёнными. Так, по-прежнему не найдена классификация совершенных д-значных кодов для q - степеней простого, q > 2. Согласно теореме В.А. Зиновьева и В.К. Леонтьева, независимо доказанной Э. Тиетвайненом (см. [6,7,51]), нетривиальные совершенные g-значные коды длины п, исправляющие ошибки, существуют только при п = (qk — l)/(q — 1), к > 2, и имеют кодовое расстояние 3; при п = 23 - двоичный код Голея с кодовым расстоянием

7, а также при п — 11 - троичный код Голея с кодовым расстоянием 5. Оба кода Голея единственны с точностью до эквивалентности, в то время как существует дважды экспоненциальное число неэквивалентных совершенных кодов с кодовым расстоянием 3. Классификация расширенных совершенных двоичных кодов длины 16 и совершенных двоичных кодов длины 15, была получена П. Остергардом и О. Поттоненом в 2009 г. в работе [37].

Цель данной диссертации состоит в исследовании конструкций совершенных кодов и разбиений пространства Fn на совершенные коды, а также в применении этих конструкций для изучения свойств разбиений и кодов. В работе будут рассматриваться только двоичные коды и разбиения на такие коды.

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

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

1. В диссертации продолжено развитие метода локального анализа из [17]. С его помощью установлено существование 5 бесконечных серий неэквивалентных предельно-транзитивных расширенных совершенных кодов. Для доказательства предельной транзитивности в работе предложено использовать свойства Паш-конфигураций систем троек Штейне-ра, соответствующих проверяемым кодам. Неэквивалентность кодов для каждой фиксированной длины была доказана с помощью сравнения значений их рангов и размерностей ядер. Впервые такой код длины 16 был обнаружен С. А. Малюгиным [10] в 2004 г. С помощью системы компьютерной алгебры MAGMA [27] найдены все транзитивные расширенные совершенные коды длины 16, имеющие хотя бы одну нетранзитивную координату. Проверка кода на транзитивность заключалась в проверке на транзитивность соответствующей ему структуры инцидентности.

2. В диссертации впервые исследуется спектр рангов пропелинейных кодов. Для этого были использованы методы построения транзитивных кодов из [15], основанные на конструкциях Моллара и Васильева для со-

вершенных кодов. Тот факт, что конструкция Моллара сохраняет про-пелинейность исходных кодов, был доказан в [25]. Зависимость ранга результирующего кода от рангов исходных кодов для конструкции Моллара была доказана в [15]. С помощью системы компьютерной алгебры MAGMA впервые были обнаружены пропелинейные коды длин 15 и 31 полного ранга. В ходе компьютерных исследований рассматривались только нормализованные пропелинейные структуры, данное понятие было введено в [25].

3. Продолжено исследование транзитивных разбиений пространства Fn на совершенные двоичные коды, начатое в [16]. В данной диссертации впервые исследованы вершинно-транзитивные разбиения пространства Fn. С помощью компьютерных исследований проверены транзитивность, 2-транзитивность и вершинная транзитивность 11 неэквивалентных разбиений длины 7, классифицированных К.Т. Фелпсом в [40]. Было показано, что конструкции транзитивных разбиений на двоичные коды, введённые в [16], могут применяться для построения 2-транзитивных и вершинно-транзитивных разбиений. Впервые получена нижняя оценка числа неэквивалентных разбиений для каждого из этих классов кодов. В качестве критерия неэквивалентности полученных разбиений использовались их матрицы пересечений, аналогичный метод был применён в [21]. Была найдена зависимость матриц пересечений разбиений, полученных с помощью рассмотренных конструкций от матриц пересечений исходных разбиений.

4. С целью построения разбиений пространства Fn на совершенные двоичные коды малого ранга предложено развитие свитчингового метода, предложенного C.B. Августиновичем и Ф.И. Соловьёвой в 1996 году для построения широкого класса двоичных совершенных кодов. Также предложены модификации конструкций разбиений на совершенные коды, основанные на конструкциях Васильева (см. [32,48]) и Фелпса (см. [21]). Проведён сравнительный анализ семейств кодов, соответствующих трём данным конструкциям и показано, что нижняя оценка числа

различных разбиений пространства Fn на совершенные двоичные коды малого ранга, полученная с помощью конструкции ¿^-компонент, является лучшей на сегодняшний день почти для всех допустимых длин кодов.

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

Все результаты диссертационной работы были апробированы на следующих конференциях: на XII международном симпозиуме по проблемам избыточности в информационных системах (С.-Петербург, Россия, 2009 г.); на VII молодёжной школе по дискретной математике и её приложениям (Москва, Россия, 2009 г.); на международной конференции по алгебраической комбинаторике и её приложениям АЬСОМА-Ю (Тыр-нау, Германия, 2010 г.); на международной конференции "Современные проблемы математики, информатики и биоинформатики" (Новосибирск, Россия, 2011 г.); на XXV конференции молодых учёных и специалистов "Информационные технологии и системы - 2012" (Петрозаводск, Россия); на международной конференции "Мальцевские чтения" (Новосибирск, Россия, 2012 г.); на международном симпозиуме по теории информации ШГГ 2013(Стамбул, Турция, 2013 г.).

Результаты работы докладывались на семинаре "Теория информации и теория кодирования" ИППИ РАН, на семинарах "Теория кодирования" и "Дискретный анализ" НГУ и Института математики СО РАН.

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

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

1. Получено (конструктивно) 5 бесконечных серий неэквивалентных

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

2. Решена проблема рангов для пропелинейных совершенных двоичных кодов, за исключением случаев кодов полного ранга для длин 63,127, 2047 и кодов длины 127 предполного ранга.

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

4. С помощью свитчинговой конструкции получена лучшая на сегодняшний день нижняя оценка числа разбиений двоичного п-мерного векторного пространства на совершенные коды длины п > 31.

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

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

Ядро приведённого кода С состоит из всех кодовых слов х £ С таких,

что х + С = С. Размерность линейной оболочки множества всех кодовых слов приведённого кода называется рангом кода. Размерность ядра и ранг приведённого кода С обозначаются через к (С) и г (С), соответственно. Известно, что ранг и размерность ядра кода Хэмминга равны п — 1од{п +1), ранги совершенных (расширенных совершенных) кодов длины п (длины п +1) могут принимать значения от п — login + 1) до п. Здесь и далее log обозначает логарифм по основанию 2. Если ранг совершенного (расширенного совершенного) кода длины п (длины N = п+1) равен 71, его называют кодом полного ранга.

Пусть С - произвольный совершенный код. Через ST(C) будем обозначать систему троек кода С, то есть ST(C) = {и + v\u,v £ С : w{u + v) = 3}. Соответственно, для произвольного расширенного совершенного кода С через SQ(C) будем обозначать систему четвёрок, то есть SQ(C) = {и + v\u, v Е С : w(u + v) = 4}.

Известно, что группа автоморфизмов пространства ¥п исчерпывается всеми изометриями Fn, каждая такая изометрия определяется подстановкой 7г на множестве координат и сдвигом на произвольный вектор v G Fn. Группа автоморфизмов Aut(Fn) пространства Fn определяется как

Aut(Fn) = {(t>, 7г) |i;eFn, TTGSn},

где Sn — симметрическая группа подстановок порядка п. Множество всех перестановок координатных позиций, сохраняющих код С, называется группой симметрий кода С и обозначается через Sym(C). Группой автоморфизмов Aut(C) кода С длины п называется группа изометрий пространства Fn, переводящих код в себя. Говорят, что два произвольных кода С и D эквивалентны, если существует такая изометрия ip пространства Fn, что С = ip{D).

Код называется транзитивным, если его группа автоморфизмов действует транзитивно на всех его кодовых словах. Для приведённых кодов удобно использовать следующее определение транзитивного кода: для каждого кодового слова х из С найдётся подстановка пх из Sn такая,

что (х,тгх) «Е Аи^С), то есть х + С = 7гх(С), где пх может не принадлежать группе симметрий Эут(С) = {тт Е Зп | 7г(С) = С} кода С. Таким образом, в транзитивном приведённом коде для любого его кодового слова х найдётся автоморфизм {х, ттх) € Аи^С), переводящий слово х в нулевое кодовое слово. Легко видно, что оба этих определения эквивалентны.

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

Для полноты изложения результатов диссертации потребуются конструкция Васильева (см. [4]) и, являющаяся её обобщением, конструкция Моллара (см. [35]). Приведём их определения.

Конструкция Васильева. Пусть С - совершенный двоичный код длины п. Пусть А - произвольная функция, определённая на кодовых словах С и принимающая значения из множества {0,1}. Пусть |а;| = XI Н-----1- хп, где х = (х1,..., хп), х% е {0,1}. Код

ные совершенные коды длин ¿и т соответственно. Пусть х = (хп,..., х1т, £21, • • ■, .. .,хц,..., хш) £ ¥ш. Определим две функции р\(х) и ^(зО, называемые обобщёнными проверками на чётность, следующим образом:

с2п+1 = {(х + у, \х\ + А (у),х) I хе¥п,уеС}

называется совершенным кодом Васильева долины 2п+ 1. Конструкция Моллара. Пусть С1 и Ст -

<т

произволь-

(1)

где аг --

Сь в ¥т. Множество

М(С1,Ст) = {(х,у + Р1(х),г + р2(х) + /Ы) I X € Г",

у е С\г<= Ст}

называется совершенным двоичным кодом Моллара длины п = tm + Ь + т.

Заметим, что в обозначение Л4(ССт) включены исходные коды С1 и где верхние индексы ¿и т указывают длины этих кодов, соответственно. Ясно, что могут найтись такие и ттт/, что совершенный код АЛ{С1',Ст') будет иметь те же параметры, что и код Л4(С^Ста), Оба этих кода могут как совпадать, так и быть различными, более того, они могут быть неэквивалентными.

Первая глава диссертации посвящена исследованию транзитивных совершенных и расширенных совершенных кодов. Задачу проверки объекта на транзитивность можно встретить и в других областях математики - например, поиск гамильтонова цикла в графах. Транзитивные коды по ряду свойств очень близки к линейным кодам - в частности, для транзитивного приведённого кода С верно следующее: |А^(С)| = \С\ • |8ут(С)|. Данное обстоятельство позволяет сделать вывод о некотором богатстве групп автоморфизмов транзитивных кодов. Число транзитивных кодов, по всей вероятности, невелико, по сравнению с общим числом кодов с теми же параметрами. Тем не менее, для всякого оптимального нелинейного кода почти всегда можно найти транзитивный код с теми же параметрами. Например, двоичный образ (под действием отображения Грея) произвольного или -линейного кода является транзитивным кодом.

В [26] получена классификация [(к + 1)/2] совершенных линейных кодов длины п = 2fc — 1. В работе [8] классифицированы линейные расширенные совершенные коды. С. А. Малюгиным в 2004 г. (см. [11]) перечислены все неэквивалентные транзитивные совершенные двоичные коды длины 15, получаемые из одношаговых свитчингов кода Хэмминга длины 15, их оказалось 16, включая код Хэмминга. Применение известных методов построения кодов, таких как методы Васильева, Плоткина и Моллара, к транзитивным кодам, удовлетворяющим некоторым дополнительным условиям, позволило получить бесконечные клас-

сы транзитивных кодов больших длин. В частности, в работах [15, 49] построено не менее [к/2\2 неэквивалентных транзитивных совершенных кодов длины п — 2к — 1, А; > 4 с кодовым расстоянием 3, среди которых имеются коды больших рангов. Для доказательства неэквивалентности построенных кодов использовался анализ значений рангов и размерностей ядер этих кодов. Так как из неравенства значений этих параметров следует неэквивалентность соответствующих кодов, то, подсчитывая число различных пар чисел, реализуемых в качестве ранга и размерности ядра некоторого кода, можно получить нижнюю оценку числа неэквивалентных кодов. В [12] В. Н. Потаповым построено экспоненциальное число неэквивалентных транзитивных расширенных совершенных кодов малого ранга, а именно, ранга на единицу больше ранга кода Хэмминга такой же длины, что отличает их от класса кодов, полученных в [15,49]. В работе [25] доказано, что все транзитивные коды длины 15 из статьи [11] являются пропелинейными. В [24] доказано, что существует экспоненциальное число неэквивалентных пропелинейных кодов, а именно, было доказано, что любой транзитивный код Потапова из [12] является пропелинейным. Согласно классификации [37] П. Р. Дж. Остергарда и О. Поттонена всех совершенных и расширенных совершенных двоичных кодов длин 15 и 16 соответственно, для п = 15 существует 201 транзитивный совершенный код, а для п = 16 имеется 101 транзитивный расширенный совершенный код.

Очевидно, что применение общей проверки на чётность позволяет получать из транзитивных совершенных двоичных кодов транзитивные расширенные совершенные двоичные коды. Обратное не всегда верно, в частности, в 2004 г. С. А. Малюгиным [10] был обнаружен один транзитивный расширенный совершенный двоичный код длины 16, такой, что все коды, полученные из него выкалыванием любой координаты, являются нетранзитивными. Всякий транзитивный расширенный совершенный код произвольной допустимой длины, обладающий свойством, что все коды, полученные из него выкалыванием любой координаты, являют-

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

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

В качестве основы для исследований послужила классификация расширенных совершенных двоичных кодов длины 16 и совершенных двоичных кодов длины 15, полученная П. Остергардом и О Поттоненом в работе [37].

В разделе 1.1.1 приведены результаты, полученные в диссертации посредством дополнительных компьютерных исследований, проведённых с помощью системы компьютерной алгебры MAGMA. Для каждого транзитивного кода длины 15 и транзитивного расширенного кода длины 16 были вычислены ранг, размерность ядра, порядок группы симметрий, порядок ST(C) (SQ(C) - для расширенных кодов). Эти характеристики, вместе с порядковым номером соответствующего кода из классификации [37], перечислены в таблицах А.1 и А.2 в приложении к данной работе. Также найдены все транзитивные расширенные совершенные коды длины 16, которые имеют хотя бы одну нетранзитивную координату. Полный список таких неэквивалентных кодов приведён в таблице В.1 приложения диссертации, их оказалось 51, и только 10 из них являются предельно-транзитивными. Второй столбец таблицы В.1 содержит номер кода согласно классификации [37], далее следуют, соответственно, номера нетранзитивных координат, ранг, размерность ядра, порядок группы автоморфизмов и порядок множества SQ(C).

Для построения бесконечной серии предельно-транзитивных кодов

в разделе 1.1.2 использованы известные конструкции Васильева (1) и Плоткина [34].

Рассмотрим произвольный расширенный совершенный код Сы длины N = 2к. Через Сш обозначим расширенный код длины 2N, полученный из него с помощью конструкции Плоткина. Введём обозначение А/дг = {1,2,..., УУ}. Через обозначим код, полученный выкалыва-

нием кода См по координатной позиции, ] 6 Мм-

Пусть Уг2п+1 - код, полученный из совершенного кода Сгп, г € А/дг, п = 2к — 1, к > 3, применением конструкции Васильева (1) с функцией А = 0.

Сравнение конструкций позволило обнаружить связь между кодами У2п+1 и С|п+1, которая может быть выражена в следующем утверждении

Лемма 1. Для любого ] 6 Л/глт найдётся г £ Л/дт такое, что код С2п+1 изоморфен коду Васильева У2п+1.

Для построения бесконечной серии из каждого из полученных десяти неэквивалентных предельно-транзитивных расширенных совершенных кодов длины 16 потребовалось найти инвариант, с помощью которого можно было бы проверять нетранзитивность выколотых кодов. Для этого был применён метод локального анализа, развитый в [17], в частности, были исследованы специальные свойства систем троек Штейне-ра, отвечающих каждому из шестнадцати выколотых кодов для каждого из этих десяти неэквивалентных предельно-транзитивных расширенных совершенных кодов. А именно, были детально исследованы Паш-конфигурации полученных совершенных кодов. Напомним, что системой троек Штейнера ЗТ8П порядка п называется система сочетаний из п-элементного множества Мп = {1,... ,п} по три (называемых тройками) такая, что каждая неупорядоченная пара элементов содержится в точности в одной тройке. Известно (см. [34]), что множество кодовых слов веса 3 в приведённом совершенном коде Сп образует систему троек Штейнера (каждая тройка системы состоит из номеров ненулевых координат соответствующего кодового слова веса 3). Будем обозначать

её через 8ТЗ(СП). Паш-конфигурацией для ЭТЭ™ называется множество троек из 8Т8П, изоморфное множеству

{(а, 6, с), (а, у, г), (х, Ъ, г), (ж, у, с)},

то есть, троек, попарно пересекающихся по одному элементу, а в объединении дающих шесть элементов. Кроме того, в Паш-конфигурации поэлементная сумма любых трёх троек даёт оставшуюся тройку. Известно, что число Паш-конфигураций Р(8Т8П) системы троек Штейнера ЭТЭп порядка п является инвариантом, часто позволяющим установить неэквивалентность двух систем троек Штейнера.

Путём несложных комбинаторных преобразований, можно найти рекуррентную формулу для числа Паш-конфигураций системы троек Штейнера кода Васильева . Оказалось, что оно зависит только от числа Паш-конфигураций системы троек Штейнера исходного кодаСг'г:

Р(5Т5(Т/27г+1)) = 8 • Р{ЗТЗ(СИ) + \ЗТЗ(С™)\ + 2 • ^ . (3)

В результате исследования свойств десяти неэквивалентных предельно-транзитивных расширенных совершенных кодов длины 16, обнаружено, что восемь из них таковы, что для любого направления ъ Е Л/*1б, в нетранзитивном выколотом коде Сгп, п = 15, найдётся такое нетранзитивное слово у, что системы троек Штейнера кодов Сгп и Сгп Л-у имеют различное число Паш-конфигураций. Используя лемму 1, доказано, что, при подстановке таких кодов в конструкцию Плоткина, это свойство сохраняется, то есть верна

Лемма 4. Для любого N = 2к, к > 4; существует не менее 8 различных транзитивных расширенных совершенных кодов длины N таких, что для любого из этих кодов См для всякого направления г Е Ми, в выколотом коде С™, п = N—1, найдётся такое нетранзитивное слово у, что

Р(5Т5(Сгп)) ф Р(5Т5(С.п + у)).

Основываясь на зависимости (3), лемме 4 и результатах компьютерных исследований, представленных в таблице В.1 приложения В, доказана

Теорема 1. Для любого допустимого N > 16 существует не менее пяти неэквивалентных предельно-транзитивных расширенных совершенных кодов длины N. При N = 16 существует 10 неэквивалентных таких кодов.

Неэквивалентность кодов доказывалась с помощью сравнения соответствующих им пар значений (ранг, размерность ядра)> используя подход из [15].

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

Следствие 1. Для любого допустимого N > 16 существует не менее 8 различных предельно-транзитивных расширенных совершенных кодов длины N.

В разделе 1.2 решается задача нахождения всех значений, которые могут принимать ранги транзитивных совершенных кодов, то есть, решается проблема спектра рангов транзитивных совершенных кодов. Эта задача связана с более общей проблемой рангов и ядер совершенных кодов, которая была сформулирована в 1998 г. Т. Этционом и А. Варди [28] и состоит в том, чтобы выяснить, какие пары (г, к) являются реализуемыми в качестве ранга г и размерности ядра к некоторого совершенного двоичного кода длины п > 15.

Пусть 6(г) - такое наименьшее целое число, что — 5(г) — 1 > г — п + log (n + 1). Определим U(n, г) следующим образом:

Список литературы диссертационного исследования кандидат наук Гуськов, Георгий Константинович, 2013 год

Литература

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

2. Августинович С. В., Соловьёва Ф. И, Хеден О. О проблеме рангов и ядер совершенных кодов // Проблемы передачи информации. — 2003.

- Т. 29, Вып. 4. - С. 30-34.

3. Августинович С. В., Соловьёва Ф. И., Хеден 0.0 разбиениях п-куба на неэквивалентные совершенные коды // Пробл. передачи информ.

- 2007. - Т. 43, № 4. - С. 45-50.

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

5. Вероятность и математическая статистика. Энциклопедический словарь // Научн. изд-во БРЭ, Москва. — 2003.

6. Зиновьев В. А., Леонтьев В. К. О совершенных кодах // (Препринт ИППИ АН СССР). - 1972. - Вып. 1. - С. 26-35.

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

8. Кротов Д. С. ^4-линейные совершенные коды // Дискрет, анализ и исслед. операций. - 2000. - Сер. 1, Т. 7, № 4. - С. 78-90.

9. Кротов Д. С. Нижние оценки числа ш-квазигрупп порядка 4 и числа совершенных двоичных кодов // Дискретн. анализ и исслед. операций.

- 2000. - Т. 7, № 2. - С. 47-53.

10. Малюгин С. А. Частное сообщение — 2004.

11. Малюгин С. А. О классах эквивалентности совершенных двоичных кодов длины 15 // Препринт № 138. — Новосибирск: Институт математики СО РАН, 2004. - С. 34.

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

13. Потапов В. П., Кротов Д. С. Асимптотика числа п-квазигрупп порядка 4 // Сибирский математический журнал. — 2006. — Т. 47, № 4.

- С. 873-887.

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

15. Соловьёва Ф. И. О построении транзитивных кодов // Проблемы передачи информации. — 2005. — Вып. 3. — С. 23-31.

16. Соловьёва Ф. И. О транзитивных разбиениях п-куба на коды // Проблемы передачи информации. — 2008. — Т. 44, № 4. — С. 27-35.

17. Соловьёва Ф. И. Комбинаторные методы построения и исследования кодов (докторская диссертация). - 2008. — 202 С.

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

19. Фон-Дер-Флаасс Д. Г. Совершенные 2-раскраски гиперкуба // Сиб. матем. журн. - 2007. - Т. 48, № 4. - С. 923-930.

20. Assmus E. F., Jr., Mattson H. F., Jr. On tactical configurations and error correcting codes //J. Comb.Theory. — 1967. — Vol. 2. — P. 243257.

21. Avgustinovich S. V., Lobstein A. and Solov'eva F. I. Intersection matrices for partitions by binary perfect codes // IEEE Trans. Inform. Theory. - 2001. - Vol. 47, N 4. - P. 1621-1624.

22. Avgustinovich S. V., Heden 0., Solov'eva F. I. The classification of some perfect codes // Des. Codes Cryptogr. - 2004. - Vol. 31, N 3. - P. 313318.

23. Bauer H., Ganter B., Hergert F. Algebraic techniques for nonlinear codes // Combinatorica. - 1983. - Vol. 3. - P. 21-33.

24. Borges J., Mogilnykh I. Yu., Rifd J. K., Solov'eva F. I. On the number of nonequivalent propelinear extended perfect codes // The Electronic J. of Combinatorics. - 2013. - Vol.20, N. 2. - P. 37-50.

25. Borges J., Mogilnykh I. Yu., Rifd J. K., Solov'eva F. I. Structural properties of binary propelinear codes // Advances in Math, of Commun. - 2012. - Vol. 6, N 3. - P. 329-346.

26. Borges J., Rifd J. K. A characterization of 1-perfect additive codes // IEEE Trans. Inform. Theory. - 1999. - Vol. 45. - P. 1688-1697.

27. Bosma W., Cannon J., Playoust C. The Magma algebra system. I. The user language // J. Symbolic Comput. - 1997. - Vol. 24. - P. 235-265.

28. Etzion T.; Vardy A. Perfect Binary Codes and Tilings: Problems and Solutions // SIAM J. Discrete Math. - 1998. - Vol. 11, N 2. - P. 205-223.

29. Guskov G. K., Solov'eva F. I. Properties of perfect transitive binary codes of length 15 and extended perfect transitive binary codes of length 16. - 2012. - ArXiv, http://arxiv.org/abs/1210.5940.

30. Heden О. A Binary Perfect Code of Length 15 and Codimension 0 // Desings, Codes and Cryptography. - 1994. - Vol. 4, N 3. - P. 213-220.

31. Heden 0. A full rank perfect code of length 31 // Desings, Codes and Cryptography. - 2006. - Vol. 38, N 1. - P. 125-129.

32. Heden 0., Solov'eva F. I. Partitions of F" into nonparallel Hamming codes // Advances in Math, of Communications. — 2009. — Vol. 3, N 4. - P. 385-397.

33. Krotov D. S., Avgustinovich S. V. On the number of 1-perfect binary codes: A lower bound // IEEE Trans. Inf. Theory. - 2008. - Vol. 54, N 4. - P. 1760-1765.

34. MacWilliams F. G., Sloane N. J. A. The theory of error correcting codes // New York: North-Holland. — 1977. — P. 744. (Русский перевод: Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки: Пер. с англ. // Москва: Связь. - 1979. — 744 С.)

35. Mollard М. A generalized parity function and its use in the construction of perfect codes // SIAM J. Alg. Discrete Math. - 1986. - Vol. 7, N 1.-P. 113-115.

36. Ostergard P. R. J. On a hypercube coloring problem //J. Combin. Theory, Ser. A. - 2004. - Vol. 108, N 2. - P. 199-204.

37. Ostergard P. R. J., Pottonen 0. The Perfect Binary One-Error-Correcting Codes of Length 15: Part I - Classification // IEEE Trans. Inform. Theory. - 2009. - Vol. 55. - P. 4657-4660. Codes at arXiv:0806.2513v3.

38. Phelps K.T. A combinatorial construction of perfect codes // SIAM J. Alg. Disc. Math. - 1983. - Vol. 5. - P. 398-403.

39. Phelps К. T. A general product construction for error correcting codes // SIAM J. Alg. Discr. Methods. - 1984. - Vol. 5. - P. 224-228.

40. Phelps К. T. An enumeration of 1-perfect binary codes // Australas. J. Comb. - 2000. - Vol. 21. - P. 287-298.

41. Phelps К. T., LeVan M.J. Kernels of Nonlinear Hamming Codes // Desings, Codes and Cryptography. - 1995. - Vol. 6, N 3. - P. 247-257.

42. Phelps К. T., Rifà J. On binary 1-perfect additive codes: some structural properties // IEEE Trans, on Inform. Theory. — 2002. — Vol. 48. — P. 2587-2592.

43. Phelps К. T., Villanueva M. On Perfect Codes: Rank and Kernel // Desings, Codes and Cryptography. - 2002. - Vol. 27. - P. 139-144.

44. Rifà J. Well-Ordered Steiner Triple Systems and 1-Perfect Partitons of the n-Cube // SIAM J. Discrete Math. - 1999. - Vol. 12, N 1. - P. 35-47.

45. Rifà J., Basart J. M., Huguet L. On completely regular propelinear codes // Proc. 6th Int. Conference, AAECC-6. - 1989. - 357 LNCS. - P. 341355.

46. Rifà J., Pujol J. Translation invariant propelinear codes // IEEE Trans, on Inform. Theory. - 1997. - Vol. 43. - P. 590-598.

47. Rifà J., Pujol J., Borges J. 1-Perfect Uniform and Distance Invariant Partitions // Appl. Algebra in Engineering, Commun, and Computing. — 2001. - Vol. 11. - P. 297-311.

48. Solov'eva F. I. On perfect codes and related topics // Cow?Mac Lecture Note Seriesl3. - Pohang. - 2004. - 80 P.

49. Solov'eva F.I. On transitive codes // Тр. конф. "Дискретный анализ и исследование операций". — Новосибирск: Изд-во Ин-та математики. - 2004. - С. 99.

50. Solov'eva F. I. Existence of transitive partitions into binary codes, Proc. Eleventh Int. Workshop on Algebraic and Comb. Coding Theory. — June. 2008. - Pamporovo, Bulgaria. - P. 267-272.

51. Tietavainen A. On the nonexistence of perfect codes over finite felds. // SIAM J. Appl. Math. - 1973. - Vol. 24. - P. 88-96.

Публикации автора по теме диссертации Публикации в научных журналах

52. Соловьёва Ф. И., Гуськов Г. К. О построении вершинно-транзитив-ных разбиений n-куба на совершенные коды // Дискретный анализ и исследование операций. — 2010. - Т. 17, № 3. - С. 84 - 100.

53. Гуськов Г. К. О разбиениях двоичного векторного пространства на совершенные коды // Дискретный анализ и исследование операций. — 2013. - Т. 20, № 2. - С. 15-25.

54. Гуськов Г. К., Соловьёва Ф. И. О предельно-транзитивных расширенных совершенных кодах // Дискретный анализ и исследование операций. - 2013. - Т. 20, № 5. - С. 31-44.

55. Guskov G. К., Mogilnykh I. Yu., Solov'eva F. I. Ranks of propelinear perfect binary codes // Siberian Electronic Mathematical Reports. — 2013. - Vol. 10. - P. 443-449.

Труды конференций

56. Гуськов Г. К. О числе различных разбиений куба Е15 на совершенные двоичные коды // Материалы 47 Международной научной студенческой конференции "Студент и научно-технический прогресс". — Новосибирский государственный университет. — 2009. — 235 с. — С. 160.

57. Гуськов Г.К., Соловьева Ф.И. О рангах и ядрах совершенных двоичных транзитивных кодов. // Материалы VII молодежной школы по дискретной математике и её приложениям, М. Изд-во ИПМ РАН. — Москва, 18-23 мая 2009. - Часть I. - С. 23-28.

58. Solov'eva F.I., Guskov G.K. On vertex-transitive and 2-transitive partitions of Fn into perfect codes // Proc. XII Int. Symposium on problems of Redundancy in Information and Controls Systems. St.-Petersburg, Russia. - May, 26-30, 2009. - P. 104-108.

59. Гуськов Г. К., Соловьева Ф.И. О разбиениях n-куба на совершенные двоичные коды // Международная конференция "Современные проблемы математики, информатики и биоинформатики" (ISBN 978-5-905569-03-6). Россия, Новосибирск, 11-14 октября, 2011. — С. 65. — http://conf.nsc.ru/files/conferences/Lyap-lOO/fulltext/74556/74659/Guskov.Soloveva.LowerBoundPartitions.pdf

60. Гуськов Г. К., Соловьёва Ф. И. Об одной каскадной конструкции разбиений n-куба на совершенные двоичные коды // Тр. международной конф. "Информационные технологии и системы". Россия, Петрозаводск, 19 - 25 августа. - М: ИППИ РАН. - 2012. - С. 124-128.

61. Гуськов Г. К., Соловьёва Ф. И. Существование расширенных совершенных транзитивных в узком смысле кодов. // Мальцевские чтения - 12-16 ноября 2012. - Новосибирск. - С. 25.

62. Guskov G. K., Mogilnykh I. Yu., Solov'eva F. I. Rank Spectrum of Propelinear Perfect Binary codes // IEEE International Symposium on Information Theory (ISBN 978-1-4799-0445-7). Istanbul, Turkey. - July 7-12, 2013. - P. 879-881.