Комбинаторные методы построения и исследования кодов

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

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

1 Построение совершенных двоичных кодов свитчинговы-

ми методами

1.1 Обзор методов построения совершенных двоичных кодов

1.2 Метод си-компонент построения совершенных кодов

1.3 Метод построения несистематических совершенных двоичных кодов

2 Методы построения транзитивных кодов

2.1 Конструкции транзитивных двоичных кодов

2.1.1 Модификация конструкции Васильева

2.1.2 Модификация конструкции Плоткина {(ж, х + у)}

2.1.3 Применение конструкции Моллара
2.1.4 Нижние оценки числа неэквивалентных совершенных транзитивных кодов
2.2 О Й4-линейных кодах с параметрами кодов Рида-Маллера
2.2.1 Z4-линeйныe коды, связанные с кодами Рида.-Маллера
2.2.2 Метод построения Х4-линейных кодов Рида-Маллера
3 Структура г-компонент совершенных двоичных кодов
3.1 Постановка задачи, основные идеи построения г-компонент
3.1.1 Конструкции г-компонент
3.2 Применение метода локального анализа к построению замощений

3.2.1 Обзор результатов о замощениях поверхностей системами троек Штейнера
3.2.2 Построение замощений
3.2.3 Существование неизоморфных замощений
4 Метрическая жесткость кодов
4.1 Двоичный,четно-весовой код
4.2 -значные (5,2) и (5 + 1,2) МБЭ-коды
4.3 (п, тг — 1) МОЭ-коды
4.4 Метрическая жесткость совершенных 5-значных кодов
4.5 Метрическая жесткость двоичных кодов, содержащих 2-
схемы
5 Группы автоморфизмов совершенных двоичных кодов и
систем троек Штейнера
5.1 Системы троек Штейнера с группой автоморфизмов максимального порядка
5.2 Совершенные двоичные коды с группой автоморфизмов
максимального порядка
6 Разбиения совершенных двоичных кодов
6.1 Нижняя оценка числа разбиений Еп на совершенные двоичные коды
6.2 Матрицы пересечений, отвечающие разбиениям совершенных двоичных кодов
6.2.1 Разбиения, использующие каскадирование и латинские квадраты, общий случай
6.2.2 Разбиения, использующие каскадирование и латинские квадраты, случай т
6.2.3 Случай диагональных матриц пересечения
6.2.4 Верхняя оценка числа неэквивалентных матриц пересечений
Литература

Введение
Актуальность темы. Объект исследования настоящей диссертации -теория кодов, исправляющих случайные ошибки. Основные проблемы теории кодирования - разработка методов построения кодов, исследование свойств кодов, классификация кодов с заданными параметрами (длиной кода, его мощностью и кодовым расстоянием), разработка эффективных алгоритмов кодирования и декодирования. Теория кодирования имеет широкое применение на практике как средство экономной, удобной, быстрой и надежной передачи сообщений по линиям связи с различного вида шумами (телефон, телеграф', радио, телевидение, компьютерная, космическая связи и т. д.), 'что, безусловно, характеризует актуальность этой науки. С 1949 г., с фундаментальных работ К. Шеи-нона, началось бурное развитие теории кодирования как отдельной научной дисциплины, а также развитие таких тесно с нею связанных научных дисциплин, как сжатие информации и криптология.
Предмет исследования настоящей работы - комбинаторная и алгебраическая теория блоковых кодов, исправляющих случайные ошибки, новые комбинаторные методы построения и исследования таких кодов. Комбинаторная и алгебраическая теория блоковых кодов является важным разделом теории кодирования. В диссертации исследуются в основном двоичные нелинейные коды, среди них совершенные коды, коды с параметрами кодов Рида-Маллера., транзитивные коды; двоичные коды, содержащие схемы, системы Штейнера, МБв-коды. Большинство результатов, представленных в данной работе, получено для совершенных кодов или кодов, связанных с ними рядом свойств.

автором диссертации были предложены два способа построения нетривиальных разбиений Еп на совершенные коды, один из которых каскадный, другой - свитчинговый (с использованием конструкции Ю. Л. Васильева). В этой главе приводится нижняя оценка, см. [185, 156] (лучшая на сегодняшний день) числа различных разбиений пространства Еп на совершенные коды, полученная свитчинговым методом:
Теорема 25. Для любого допустимого га > 31 число различных разбиений Р„ пространства Еп на совершенные коды длины га. удовлетворяет неравенству
Р„ > 22("~11/2.
Рассмотрим два произвольных разбиения га-куба Еп на совершенные расширенные двоичные коды и их матрицу пересечений. Она дает мощности попарных пересечений кодов из этих разбиений. В этой главе производится подсчет снизу и сверху количества различных матриц пересечений, полученных из произвольных двух разбиений га-куба Еп на совершенные расширенные двоичные коды.
Для получения оценок числа различных и неэквивалентных матриц пересечений, полученных из произвольных двух разбиений га-куба Е" на совершенные расширенные двоичные коды рассматриваются сначала различные разбиения Еп, которые используются для построения двух разбиений Е2п (здесь п = 2к). При этом используется и развивается далее с использованием свитчингов латинских квадратов каскадный способ построения совершенных расширенных кодов и разбиений из [147]. Для получения нижней оценки числа различных матриц пересечений двух разбиений Еп на совершенные расширенные двоичные коды потребовалось оценить число различных матриц пересечений латинских квадратов.
Для этой цели посредством свитчингов (локальных перестроек) подматриц порядка 2x2 внутри пары латинских квадратов специального вида (т. е. снова используя метод локального анализа) было сконструиро-