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

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

Оглавление
Введение

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 Конструкция гук-компонент. Нижняя оценка числа различных разбиений на совершенные коды
Заключение
Приложения
А Ранги и ядра транзитивных кодов длин 15 и 16
В Нетранзитивные координаты транзитивных кодов длины 16
С Матрицы пересечений разбиений пространства Ж7 на коды Хэмминга длины 7
Литература

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

Очевидно, что, задав, например, т следующим образом
1 2 ... N - 1 N N + 1 ... 2N 2N —
1 2 ... N - 1 iV + 1 JV + 2 ... 2 TV - 1 TV
получим r(C2n+1) = Vfn+1.
Для доказательства случая j G Л/Ьлг A/jv воспользуемся следующей заменой
w — и + и. (1.2)
Тогда C2iV преобразуется в код C2N = {(го, ги+н)|гу G Wq , v G который будет изоморфен коду C2N. Далее рассуждения аналогичны случаю г — j, только на этот раз полагаем г = j — N, а т определяется с учётом подстановки, соответствующей замене (1.2). q
Напомним, что через STSn обозначается система троек Штейнера порядка п, а через STS(C'n) будем обозначать систему троек Штейнера, соответствующую некоторому (приведённому) совершенному коду Сп.
Непосредственно из определения транзитивности вытекает следующее утверждение.
Лемма 2. Пусть С - произвольный совершенный двоичный код длины п, у G С - некоторое кодовое слово. Если STS(C) 2= STS(C + у), то у -нетранзитивное кодовое слово и код С нетранзитивен.
Для дальнейшего изложения нам понадобится частный случай известной конструкции Ассмуса и Маттсона из [20] для построения системы троек Штейнера порядка 2п + 1 из системы троек Штейнера порядка п.
Введём для краткости обозначение а — а + п + 1. Пусть STSn -система троек Штейнера порядка п, определённая на множестве Afn, п = 1,3 (mod 6). Тогда STS2n+i на множестве Min+x строится по двум следующим правилам:
STS2„+i содержит тройки следующего вида:
(I, п + 1,1), I G ЛД. (1-3)