Введение к работе
Актуальность темы. Объектом исследования настоящей работы являются блочные коды над недвоичным алфавитом, исправляющие случайные ошибки. В условиях современной жизни теория кодирования имеет широкое практическое применение в системах цифровой связи и в устройствах хранения информации.
Предметом исследования данной диссертации являются совершенные коды в алфавите из более чем двух символов. Код над полем Галуа GF(q) называется совершенным, если совокупность шаров некоторого радиуса, окружающих кодовые слова, задает разбиение всего пространства. Согласно широко известной теореме В. А. Зиновьева и В. К. Леонтьева, полученной независимо Э. Титвайненом, см. [3, 4, 16], нетривиальные совершенные g-значные коды длины N существуют только при N = (qm — 1)/(q — 1), где т — любое натуральное число не меньшее двух, такие коды имеют кодовое расстояние 3 и исправляют одну ошибку; при N = 23 — это двоичный код Голея с кодовым расстоянием 7, а также при N = 11 — это троичный код Голея с кодовым расстоянием 5. Оба кода Голея единственны с точностью до эквивалентности. Совершенные коды представляют собой один из наиболее важных предметов теории блочных кодов, исправляющих ошибки, поскольку они обладают важным свойством — оптимальностью, т. е. при заданной длине кода и кодовом расстоянии мощность кода максимальна.
В качестве основных задач теории кодирования выделяют разработку методов построения кодов, исследование свойств кодов, разработку эффективных методов кодирования и декодирования. Несмотря на активные исследования целого ряда ученых в области теории кодирования, остается открытым множество проблем, связанных с совершенными кодами. Например, по-прежнему остается нерешенной основная проблема построения и перечисления совершенных g-значных кодов для q, равного степени простого числа. Эта проблема включает в себя разработку методов построения кодов, а также методов
исследования свойств отдельных классов кодов с заданными характеристиками (параметрами или свойствами).
Ряд задач теории кодирования являются важными и для других математических дисциплин: комбинаторного анализа, теории групп, теории графов, криптологии. Таковой, например, является проблема упаковки шарами одного радиуса. Кроме того, многие из методов построения и изучения свойств совершенных g-значных кодов применяются для кодов с другими параметрами, например, для кодов с большими кодовыми расстояниями, которые способны обнаруживать и исправлять большее число ошибок.
Самостоятельный интерес в теории кодирования представляют собой исследования различных свойств кодов таких, как изучение групп автоморфизмов кодов, исследование спектральных свойств кодов, построение и исследование разбиений д-значного n-мерного куба на коды, исследование рангов и ядер кодов, пересечения кодов.
Все результаты данного исследования верны и для двоичных кодов, но в этом случае они преобразуются в уже известные, поскольку особенность строения многозначных полей является для данного исследования существенно важным.
Цель данной работы состоит в разработке новых методов построения совершенных кодов над недвоичным алфавитом, исследовании свойств таких кодов.
Методика исследований. В диссертации используются известные методы и аппарат алгебраической и комбинаторной теории кодирования, комбинаторного анализа. Для исследования свойств кодов применены методы построения кодов, предложенные в диссертации.
Научная новизна. Все результаты, представленные в диссертации, являются новыми. В работе предложено три разных свитчинговых метода построения совершенных g-значных кодов, а также применение этих методов для исследования пере-
сечений совершенных g-значных кодов (проблема Т. Этциона и А. Варди).
В диссертации предложено развитие свитчингового метода построения и исследования нелинейных кодов — метода й-компонент, который был предложен С. В. Августиновичем и Ф. И. Соловьевой в 1996 году и применен для построения широкого класса двоичных совершенных кодов.
Была предложена оригинальная модификация этого метода посредством так называемых конфигураций — перестановок, действующих на q элементах алфавита. Такие преобразования элементов g-значного алфавита значительно расширяют произвол в выборе сдвигаемого множества, не имеют аналогий в двоичном случае и позволяют получить более обширный класс совершенных кодов по сравнению с классом кодов, построенных методом свитчинга й-компонент.
Разработан новый метод свитчинга простых компонент для совершенных g-значных кодов над расширением простого поля, то есть при q = pr,r > 1. Этот метод позволил получить широкий класс различных совершенных g-значных кодов и, как следствие, рекордную на сегодняшний день нижнюю оценку числа таких кодов. Показано, что в коде Хэммин-га не существует г-компонент меньшей мощности, чем простая г-компонента специального вида. Этот факт свидетельствует о том, что полученная оценка не может быть существенно улучшена методом свитчинга компонент. Простые компоненты были введены К. Т. Фелпсом, И. Рифой и М. Виллануевой для исследования свойств специального вида линейных подкодов (р-ядер) g-значных кодов Хэмминга в работе [14].
4. Впервые исследована проблема пересечений совер
шенных нелинейных g-значных кодов, q > 2. Исполь
зуя предложенные свитчинговые методы построения совер
шенных g-значных кодов, получен широкий спектр воз
можных пересечений таких кодов. Для любого допустимого
N = (qm — 1)/(q — 1), где т — целое число, сконструированы
также два кода, пересечение которых меньше, чем пересече-
ние, которое может быть получено применением свитчинговых методов.
Практическая и теоретическая ценность. Работа носит теоретический характер. Полученные в ней результаты могут быть применены в теории кодов, исправляющих ошибки: для дальнейшего исследования и построения g-значных кодов, для построения кодов с большими кодовыми расстояниями, для исследования свойств g-значных кодов; в криптографии (в схемах распределения секрета, см. [9]), комбинаторике. Возможно практическое применение для передачи информации по каналам связи, допускающим больше двух состояний сигнала, например, в оптоволоконных сетях.
Апробация работы. Все результаты работы были апробированы на следующих международных конференциях: на конференциях по алгебраической и комбинаторной теории кодирования ACCT-IX (Кранево, Болгария, 2004 г.), АССТ-Х (Звенигород, 2006 г.); на конференции по дискретному анализу и исследованию операций DAOR-2004 (Новосибирск, 2004 г.); на конференции по оптимальным кодам и смежным областям ОС'2005 (Пампорово, Болгария, 2005 г.); на международной конференции "Математика в современном мире" (Новосибирск, 2007 г.). Результаты диссертации докладывались на семинаре "Теория информации и теория кодирования" ИППИ РАН, на семинаре "Синтез управляющих систем" мехмата МГУ, на семинаре "Дискретная математика и математическая кибернетика" факультета ВМК МГУ, на семинаре "Дискретный анализ" Института математики СО РАН. Все результаты были доложены на семинаре НГУ и Института математики СО РАН "Теория кодирования".
Публикации. Основное содержание диссертации отражено в 6 печатных работах. Среди них 3 работы в журналах из перечня ВАК, 3 работы в рецензируемых трудах международных конференций.
Основные результаты диссертации.
Для совершенных g-значных кодов, q > 2, развит свит-чинговый метод построения и исследования свойств кодов, известный как метод й-компонент.
Предложена модификация метода свитчинга компонент g-значного, q > 2, кода Хэмминга посредством конфигураций. Такие преобразования присущи g-значным, q > 2, кодам и не имеют аналогов в двоичном случае.
Предложен комбинаторный метод построения и исследования свойств g-значных кодов, для q = pr,r > 1 - метод свитчинга простых компонент. Метод позволил построить обширный класс различных совершенных g-значных кодов длины N = qn + 1 = (qm — 1)/(q — 1), которых оказалось не менее
(р!)«( r ) ( (
4. Исследована проблема пересечения нелинейных совер
шенных g-значных кодов. С помощью метода свитчинга про
стых компонент получен широкий ряд возможных пересечений
таких кодов. Показано, что существуют подвижные множества
мощности меньшей, чем минимальная г-компонента кода Хэм
минга.
На защиту выносятся новые свитчинговые методы построения совершенных g-значных кодов и применение этих методов для исследования пересечений таких кодов (проблема Т. Этциона и А. Варди).
Объем и структура диссертации. Диссертация состоит из введения, трех глав и списка литературы (36 наименований), в конце приведен список публикаций автора по теме диссертации. Объем диссертации — 64 страницы.
