Свитчинговые методы построения совершенных у|!-значных кодов

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

Глава 1. Метод свитчинга 5-компонент

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.4. О разбиениях пространства на совершенные коды
Заключение
Список литературы

Объектом исследования настоящей работы являются блочные коды над недвоичным алфавитом, исправляющие случайные ошибки. В условиях современной жизни теория кодирования имеет широкое практическое применение в системах цифровой связи и в устройствах хранения информации.
Код над полем Галуа СР(д) называется совершенным, если совокупность шаров некоторого радиуса, окружающих кодовые слова, задает разбиение всего пространства. Согласно широко известной теореме В. А. Зиновьева и В. К. Леонтьева, полученной независимо Э. Титвайненом, см. [3, 4, 30], нетривиальные совершённые д-значные коды,длины.А" существуют только при N — (дт — 1)/(д — 1), где т — любое натуральное число не меньшее двух, такие коды имеют кодовое расстояние 3 и исправляют одну ошибку; при N = 23 — это двоичный код Голея с кодовым расстоянием 7, а также при N = 11 — это троичный код Голея с кодовым расстоянием 5. Оба кода Голея единственны с точностью до эквивалентности. Класс неэквиваленитных совершенных кодов с кодовым расстоянием 3 достаточно обширен, его мощность составляет дважды экспоненциальное число. Совершенные коды представляют собой один из наиболее важных предметов теории блочных кодов, исправляющих ошибки, поскольку они обладают важным свойством — оптимальностью, т. е. при заданной длине кода и кодовом расстоянии мощность кода максимальна.
В качестве основных задач теории кодирования выделяют разработку методов построения кодов, исследование свойств кодов, разработку эффективных методов кодирования и декодирования. Несмотря на активные исследования целого ряда ученых в области теории кодирования, остается открытым множество проблем, связанных с совершенными кодами. Например, по-прежнему остается нерешенной основная проблема построения

и перечисления совершенных д-значных кодов для q, равного степени простого числа. Эта проблема включает в себя разработку методов построения кодов, а также методов исследования свойств отдельных классов кодов с заданными характеристиками (параметрами или свойствами).
Ряд задач теории кодирования являются важными и для других математических дисциплин: комбинаторного анализа, теории групп, теории графов, криптологии. Таковой, например, является проблема упаковки шарами одного радиуса. Кроме того, многие из методов построения и изучения свойств совершенных д-значных кодов применяются для кодов с другими параметрами, например, для кодов с большими кодовыми расстояниями, которые способны обнаруживать и исправлять большее число ошибок.
Самостоятельный интерес в теории кодирования представляют собой исследования различных свойств кодов таких, например, как изучение групп автоморфизмов кодов, исследование спектральных свойств кодов, построение и исследование разбиений д-значного тг-мерного куба на коды, исследование рангов и ядер кодов, пересечения кодов.
Все результаты данного исследования верны и для двоичных кодов, но в этом случае они преобразуются в уже известные, поскольку особенность строения многозначных полей Галуа является для данного исследования существенно важным.
Цель данной диссертации состоит в разработке новых методов построения совершенных кодов над недвоичным алфавитом, исследовании свойств таких кодов.
В диссертации используются известные методы и аппарат алгебраической и комбинаторной теории кодирования, комбинаторного анализа. Для исследования свойств кодов применены методы построения кодов, предложенные в диссертации.
Все результаты, представленные в диссертации, являются новыми. В работе предложено три разных свитчинговых метода построения совершенных д-значных кодов, а также применение этих методов для исследования пересечений совершенных д-значных кодов (проблема Т. Этциона и А. Вар-Ди).
1. В диссертации предложено развитие свитчиигового метода построения и исследования нелинейных кодов — метода а-компонент, который

см. [31]. Используя свитчинги по г-й координате, легко получить следующее достаточно богатое множество чисел пересечений q-знaчныx совершенных кодов: к ■ Рг/р для каждого к 6 {0,1,... ,р ■ К — 2,р • К}.
Минимальная мощность непустого пересечения равна Pifp. Это значение достигается при пересечении кода С с кодом, полученным свитчинга-ми всех простых компонент кода С за исключением единственной простой компоненты, на которую действуем свитчингом по перестановке, не изменяющей только один элемент поля в г-й координате.
Следует отметить, ЧТО пересечение двух КОДОВ МОЩНОСТИ (р-К—1)-Рг/р невозможно в силу ТОГО, что единичный свитчинг одной компоненты не может изменить только один элемент поля СР(р) в некоторой координате кодовых слов компоненты, он переставит как минимум два элемента поля. Теорема доказана.
3.3 О пересечениях д-значных совершенных кодов, полученных с использованием конструкции Шонхай-ма
В данном параграфе для произвольного допустимого N = щ + 1,п>1, приводится модификация конструкции Шонхайма из [29], позволяющая с помощью использования техники свитчингов компонент кода Хэмминга, а также циклического сдвига некоторого подмножества координатных позиций, получить два нелинейных совершенных д-значных кода длины N, пересечение которых меньше, чем минимальное непустое пересечение совершенных кодов той же длины, достигаемое сдвигами простых компонент, см. теорему 8.
Пусть Сд — д-значный совершенный код длины п — (дт-1 — 1)/(д — 1), п > 1, напомним, что элементы множества Рч = {1,2 д — 1} находятся во взаимно однозначном соответствии, с ненулевыми элементами поля
С.Р(д). Рассмотрим следующую модификацию известной конструкции совершенных д-значных кодов Шонхайма (см. [29]):
д-1 д
Сд — {(щ, г>2,... ,г>д_1, |гд| + А(с), ^ свд + с)|гд 6 Р",се С^,а( 6 Рд},
г=1 г