О вложимости систем Штейнера в совершенные коды

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

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

1 Системы троек Штейнера малого ранга и совершенные

двоичные коды

1.1 Основные понятия

1.2 Конструкция систем троек Штейнера

1.3 Вложимость S(T,n) в совершенный код

1.4 Число различных STS(n) рангов не больше п— log(n+l) +

1 и п—log(n + 1) + 2. вложимых в совершенные двоичные коды

2 Системы четверок Штейнера малых рангов и расширенные совершенные двоичные коды

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

2.2 Системы четверок Штейнера SQS(4m). вложимые в расширенные совершенные коды
2.3 Число различных SQS(N) рангов N—logiV и N— log N +
1, вложимых в расширенные совершенные двоичные коды таких же рангов
2.4 Системы четверок Штейнера, не вложимые в расширенные совершенные КОДЫ, построенные методом о^^-компонент .
3 О метрической жесткости некоторых классов кодов
3.1 Определения и понятия

3.2 -Метрическая нежесткость трех классов эквидистантных кодов, а также кодов, соответствующих аффинно разрешимым схемам
Заключение
Литература

Введение
Теория кодирования в современном мире имеет широкое применение как средство передачи информации по каналам связи с шумами (телефон, телеграф, радио, телевидение, компьютерная, космическая связи и т. д.). Ее развитие началось после появления работы К. Шеннона [40]. Теория кодирования тесно связана с такими дисциплинами, как теория блок-схем, теория графов, теория групп, дискретный анализ. В данной диссертации исследуются совершенные и расширенные совершенные двоичные коды, эквидистантные и двудистантные коды над двоичным и недвоичным алфавитом, а также системы троек и четверок Штейнера.
Классификация систем Штейнера является одной из основных задач теории блок-схем. Известна классификация систем троек Штейнера порядка не больше 19, см. [25, 33]. Также открытым является вопрос о вложимости произвольной системы троек (четверок) Штейнера в некоторый совершенный (расширенный совершенный) двоичный код. Интересен также вопрос соответствия разных конструкций для систем троек (четверок) Штейнера с конструкциями для совершенных (расширенных совершенных) двоичных кодов, например, взаимосвязь свитчинговых и каскадных методов построения данных объектов.
Изучение свойства метрической жесткости в теории кодирования представляет собой один из важных вопросов, который является недостаточно глубоко исследованным. В каждом конкретном случае выяснение вопроса о метрической жесткости кода представляет из себя довольно нетривиальную задачу. Изучение метрической жесткости кодов важно с

По правилу Л1 для каждого столбца Т, кроме первого, можно независимо построить четыре различных Паш-конфигурации на элементах {а) ia,ja> ко}- Следовательно, имеем 4т различных возможностей выбрать тройки на столбцах Т. По правилу Л2 дополнительно существуют 4т вариантов выбора троек на столбцах Т. С учётом комбинаций правил Л1 и Л2, получаем всего 4т + 4т + 4т ■ 4m_1 = 4m(m + 1) + 4т = (n + 1) • 2(п^7)/2 _)_ п — з возможностей выбрать тройки на столбцах Т.
Далее, для каждой тройки (а,Ь, с) Є STS (то), с учётом приведённых рассуждений, получаем 46 + 84 + 180 = 310 различных свитчингов по
правилам 81, 82 и 83. Таким образом, существует по крайней мере 31Q|STS(m)| = 310(n-3)(n-7)/3-2s
различных возможных свитчингов. С учётом того, что свитчинги можно применять независимо, получаем ((п + 1) • 2("~Н/2 + п — 3) • ЗЮ^-3^“7)/3'25 различных систем троек Штейнера, которые можно построить из фиксированной STS(m) и множества {i,j,k}. я
Следствие 3. Число различных систем троек Штейнера порядка п = 4т+3, полученных из фиксированной таблицы, отвечающей некоторой системе троек Штейнера порядка т и множеству {i,j,k}, по правилу Л1 в сочетании с одним из правил 81 или 82, равно 2^п~3^2 •
Ш(п-Ъ){п-7)/Х2
Найдём нижнюю оценку числа систем троек Штейнера порядка п, которые можно получить с помощью указанной выше конструкции.
Теорема 2. Для числа R{n) всех различных STS(п), п = 4то + 3, т > 3, лежащих в классах Sw(STS(n),r) при всех г > п— login + 1), верно
R(n) > (((n + 1) • 2(п~5)/2 + 2п - 6) х
х зю()г2-10п+21)/3-25 - Зп + 9) • п(п - 1)/12 • Д((п - 3)/4).
Доказательство. Число R(n) различных систем троек Штейнера порядка п = 4т + 3 удовлетворяет неравенству R(n) > Р(п) ■ R(m), где