Свитчинговые методы построения совершенных у|!-значных кодов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ им С. Л Соболева

На правах рукописи

УДК 519.725

Лось Антон Васильевич

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

Специальность 01 01 09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Новосибирск, 2008

Работа выполнена в Институте математики им С Л. Соболева СО РАН

Научный руководитель Официальные оппоненты

Ведущая организация

кандидат физико-математических наук, доцент Ф. й Соловьева доктор физико-математических наук, профессор В А. Зиновьев кандидат физико-математических наук, доцент А Л Пережогин факультет ВМК МГУ имени М В Ломоносова

Защита состоится 14 мая 2008 г в 16 часов 00 минут на заседании диссертационного совета Д 003 015.01 при Институте математики им С Л Соболева СО РАН по адресу, пр Академика Коптюга 4, г Новосибирск, 630090

С диссертацией можно ознакомиться в библиотеке Института математики им. С Л Соболева СО РАН

Автореферат разослан 14 апреля 2008 г

Ученый секретарь диссертационного совета, д.ф -м н

, Ю. В. Шамардин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Объектом исследования настоящей работы являются блочные коды над недвоичным алфавитом, исправляющие случайные ошибки. В условиях современной жизни теория кодирования имеет широкое практическое применение в системах цифровой связи и в устройствах хранения информации

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

В качестве основных задач теории кодирования выделяют разработку методов построения кодов, исследование свойств кодов, разработку эффективных методов кодирования й декодирования Несмотря на активные исследования целого ряда ученых в области теории кодирования, остается открытым множество проблем, связанных с совершенными кодами Например, по-прежнему остается нерешенной основная проблема построения и перечисления совершенных д-значных кодов для <7, равного степени простого числа. Эта проблема включает в себя разработку методов построения кодов, а также методов

исследования свойств отдельных классов кодов с заданными характеристиками (параметрами или свойствами)

Ряд задач теории кодирования являются важными и для других математических дисциплин, комбинаторного анализа, теории групп, теории графов, криптологии Таковой, например, является проблема упаковки шарами одного радиуса Кроме того, многие из методов построения и изучения свойств совершенных д-значных кодов применяются для кодов с другими параметрами, например, для кодов с большими кодовыми расстояниями, которые способны обнаруживать и исправлять большее число ошибок.

Самостоятельный интерес в теории кодирования представляют собой исследования различных свойств кодов таких, как изучение групп автоморфизмов кодов, исследование спектральных свойств кодов, построение и исследование разбиений д-значного п-мерного куба на коды, исследование рангов и ядер кодов, пересечения кодов

Все результаты данного исследования верны и для двоичных кодов, но в этом случае они преобразуются в уже известные, поскольку особенность строения многозначных полей является для данного исследования существенно важным

Цель данной работы состоит в разработке новых методов построения совершенных кодов над недвоичным алфавитом, исследовании свойств таких кодов.

Методика исследований. В диссертации используются известные методы и аппарат алгебраической и комбинаторной теории кодирования, комбинаторного анализа. Для исследования свойств кодов применены методы построения кодов, предложенные в диссертации.

Научная новизна. Все результаты, представленные в диссертации, являются новыми. В работе предложено три разных свитчинговых метода построения совершенных д-значных кодов, а также применение этих методов для исследования пере-

сечений совершенных д-значных кодов (проблема Т Этциона и А Варди).

1 В диссертации предложено развитие свитчингового метода построения и исследования нелинейных кодов — метода «-компонент, который был предложен С В Августиновичем и Ф И. Соловьевой в 1996 году и применен для построения широкого класса двоичных совершенных кодов.

2. Была предложена оригинальная модификация этого метода посредством так называемых конфигураций — перестановок, действующих на q элементах алфавита. Такие преобразования элементов д-значного алфавита значительно расширяют произвол в выборе сдвигаемого множества, не имеют аналогий в двоичном случае и позволяют получить более обширный класс совершенных кодов по сравнению с классом кодов, построенных методом свитчинга «-компонент.

3. Разработан новый метод свитчинга простых компонент для совершенных д-значных кодов над расширением простого поля, то есть при д = рг,г > 1. Этот метод позволил получить широкий класс различных совершенных д-значных кодов и, как следствие, рекордную на сегодняшний день нижнюю оценку числа таких кодов. Показано, что в коде Хэммин-га не существует г-компонент меньшей мощности, чем простая г-компонента специального вида Этот факт свидетельствует о том, что полученная оценка не может быть существенно улучшена методом свитчинга компонент Простые компоненты были введены К. Т Фелпсом, Й Рифой и М. Виллануевой для исследования свойств специального вида линейных подкодов (р-ядер) д-значных кодов Хэмминга в работе [14].

4 Впервые исследована проблема пересечений совершенных нелинейных д-значных кодов, д > 2 Используя предложенные свитчинговые методы построения совершенных д-значных кодов, получен широкий спектр возможных пересечений таких кодов. Для любого допустимого N = (дт — 1)/(д — 1), где т — целое число, сконструированы также два кода, пересечение которых меньше, чем пересече-

ние, которое может быть получено применением свитчинговых методов

Практическая и теоретическая ценность. Работа носит теоретический характер Полученные в ней результаты могут быть применены в теории кодов, исправляющих ошибки для дальнейшего исследования и построения д-значных кодов, для построения кодов с большими кодовыми расстояниями, для исследования свойств д-значных кодов, в криптографии (в схемах распределения секрета, см. [9]), комбинаторике Возможно практическое применение для передачи информации по каналам связи, допускающим больше двух состояний сигнала, например, в оптоволоконных сетях

Апробация работы. Все результаты работы были апробированы на следующих международных конференциях на конференциях по алгебраической и комбинаторной теории кодирования АССТ-1Х (Кранево, Болгария, 2004 г), АССТ-Х (Звенигород, 2006 г), на конференции по дискретному анализу и исследованию операций ВАОК-2004 (Новосибирск, 2004 г), на конференции по оптимальным кодам и смежным областям ОС'2005 (Пампорово, Болгария, 2005 г), на международной конференции "Математика в современном мире" (Новосибирск, 2007 г) Результаты диссертации докладывались на семинаре "Теория информации и теория кодирования" ИППИ РАН, на семинаре "Синтез управляющих систем" мехмата МГУ, на семинаре "Дискретная математика и математическая кибернетика" факультета ВМК МГУ, на семинаре "Дискретный анализ" Института математики СО РАН. Все результаты были доложены на семинаре НГУ и Института математики СО РАН "Теория кодирования"

Публикации. Основное содержание диссертации отражено в 6 печатных работах Среди них 3 работы в журналах из перечня ВАК, 3 работы в рецензируемых трудах международных конференций

Основные результаты диссертации.

1. Для совершенных д-значных кодов, д > 2, развит свит-чинговый метод построения и исследования свойств кодов, известный как метод а-компонент

2 Предложена модификация метода свитчинга компонент д-значного, д > 2, кода Хэмминга посредством конфигураций Такие преобразования присущи д-значным, д > 2, кодам и не имеют аналогов в двоичном случае

3 Предложен комбинаторный метод построения и исследования свойств д-значных кодов, для q = рг,г > 1 - метод свитчинга простых компонент Метод позволил построить обширный класс различных совершенных д-значных кодов длины N = дп + 1 = (дт — 1)/(д - 1), которых оказалось не менее

И9 (« + !)'

4 Исследована проблема пересечения нелинейных совершенных д-значных кодов. С помощью метода свитчинга простых компонент получен широкий ряд возможных пересечений таких кодов Показано, что существуют подвижные множества мощности меньшей, чем минимальная г-компонента кода Хэмминга.

На защиту выносятся новые свитчинговые методы построения совершенных д-значных кодов и применение этих методов для исследования пересечений таких кодов (проблема Т Этциона и А Варди)

Объем и структура диссертации. Диссертация состоит из введения, трех глав и списка литературы (36 наименований), в конце приведен список публикаций автора по теме диссертации Объем диссертации — 64 страницы.

СОДЕРЖАНИЕ РАБОТЫ

Прежде чем перейти к обзору полученных результатов, приведем необходимые определения и обозначения

Пусть Vq — iV-мерное векторное пространство над полем Галуа GF(q), где q — степень простого числа В пространстве V^ фиксирован некоторый базис и задана метрика Хэммин-га Под расстоянием d(x,y) между двумя произвольными векторами х и у пространства подразумевается число координат, в которых они различаются Вес вектора z G V^ — это число его ненулевых координат. Произвольное подмножество С такого пространства является д-значным кодом Код в V^' называется совершенным q-значным кодом длины N с расстоянием 3 (далее просто совершенным кодом), если \С\ = qN~losq^N-N+i) и расстояние между любыми двумя кодовыми словами (так в дальнейшем будем называть элементы кода) не менее 3. Эти условия эквивалентны плотной упаковке пространства V^ шарами единичного радиуса с центрами в кодовых словах.

Код С линеен, если он является подпространством V^. Совершенный линейный код в пространстве V4N называется кодом Хэмминга. Будем обозначать его через Нд.

Всюду далее полагаем N = qn + 1, п = (gm_1 — 1 )/(q - 1) и m > 2

В настоящей диссертации предложено три новых метода построения совершенных g-значных кодов, последовательно улучшавших нижнюю оценку числа различных совершенных q-знач-ных кодов Все три метода различаются между собой и могут найти применение для построения и исследования д-значных кодов, необязательно совершенных.

Во введении обосновывается актуальность темы диссертации, характеризуется новизна работы, обсуждаются трудности, сопутствующие исследованию ç-значных кодов в отличии от изучения двоичных кодов Дается краткий обзор ранее известных конструкций совершенных g-значных кодов Приводится список основных результатов диссертации и обосновывается тесная связь между ними

В первой главе приводится описание свитчингового метода построения совершенных д-значных кодов, который является обобщением для д-значного случая способа построения двоичных совершенных кодов последовательными сдвигами «-компонент, предложенного в 1996 г С В Августиновичем и Ф И Соловьевой в [1] Этот метод был усовершенствован посредством дополнительных преобразований, не имеющих аналогов в двоичном случае Приведены нижние оценки числа различных совершенных д-значных кодов, построенных описанными методами

В параграфе 1.1 вводятся ключевые понятия для данного исследования подвижное множество, г-компонента и «-компонента, сдвиг множества, множество Яг Приведем определения этих понятий

Пусть С произвольный д-значный код длины И, М — некоторое подмножество его кодовых слов.

Пусть 3-(М) множество, полученное с помощью некоторого преобразования Р векторов множества М, причем множества М и Т{М) не совпадают Множество М называется подвижным множеством кода С, если множество

С' = {С\М) и Г{М)

является д-значным кодом с теми же параметрами.

Согласно [15], сдвигом множества М по направлению г, г € {1,2,..., Й}, на элемент а, где а — ненулевой элемент поля йР^), называется множество М' = {х+аег\х € М}, где ег — вектор длины N с нулевыми координатами, кроме г-й, равной 1, то есть М' = М + аег, здесь аег означает покомпонентное произведение вектора ег на элемент а

Множество М называется г-компонентой совершенного кода С, если код С' — (С\М) и (М 4- аег) является совершенным кодом

Пусть «С {1,2, . Множество М называется а-компо-нентой совершенного кода С, если для всех г € « множество М является г-компонентой кода С

Подпространство, порожденное совокупностью вершин веса 3 кода Нд с единичной г-й координатой, обозначим через Яг. Известно, см. [13], что множество является ¿-компонентой

Впервые свитчинговый метод построения совершенных двоичных кодов был предложен Ю Л. Васильевым в 1962 году, см. [2]. В 1968 году Дж Шонхайм, см [15], предложил свитчин-говую конструкцию для построения совершенных д-значных кодов. Следующее утверждение раскрывает механизм свит-чингового метода (от английского 5ш£сйт<7 — сдвиг, обмен), который предложен для д-значного случая в [13], (см также [10]) Однако следует различать свитчинговый метод, описанный здесь, от изложенного в [13], так как мы не ограничиваемся сдвигом только г-компонент, а сдвигаем (так же, как в [1]) еще и специального вида ^-компоненты.

Итак, рассмотрим произвольный совершенный код С длины N Пусть М*, , , попарно непересекающиеся подмножества кода С такие, что Мг® являются г5-компонентами кода С, причем «х, гг, ... , 1к € {1,2, .., Ы} не обязательно все различны

Утверждение.(См [13].) Пусть С произвольный совершенный код длины N = — 1)/(<? — 1), т > 2 Тогда для любого ненулевого элемента а3 поля множество

к к

8=1 8=1 является совершенным д-значным кодом длины N

В параграфе 1 2 рассмотрено разбиение д-значного кода Хэмминга на классы смежности линейной 5-компоненты, а также на классы смежности г-, ]- и ^-компонент Эти утверждения позволяют доказать Теорему 1 о том, что код, построенный из д-значного кода Хэмминга методом свитчинга 5-компонент, является совершенным.

Основная идея метода свитчинга 5-компонент заключается в следующем Сначала для каждой а-компоненты выбираем свое направление г из множества направлений а и делаем свитчинг, то есть сдвигаем все ¿-компоненты в каждой й-компоненте на произвольный элемент поля С-Р^д), затем производим свитчинг полученных новых а-компонент, делая сдвиги по неиспользованным из множества а направлениям В итоге результирующий код остается кодом с теми же параметрами, но отличным или даже неэквивалентным исходному

Параграф 1 3 посвящен получению нижней оценки числа различных совершенных д-значных кодов, описанных конструкцией Теоремы 1 Поскольку построенные коды не все различны, для их сравнения вводится понятие функции сдвига Функция сдвига /с определяет, на какие элементы поля и в каких

направлениях следует сдвигать кодовые слова кода Хэмминга, чтобы получить код С. Каждый совершенный код однозначно определяется своей функцией сдвига, причём несовпадающие коды имеют разные функции

В параграфе 1.3 доказана

Теорема 2. Количество Рд(Ы) различных совершенных д-значных кодов длины N не меньше, чем

«Г-("-х) • (3<7)^~М (1)

Эта оценка улучшает ранее известную нижнюю оценку Б. Линдстрема, см [12]

А М Романов в 2004 г, см. [5], для построения совершенных д-значных кодов использовал связь столбцов проверочной матрицы кода Хэмминга с проективной геометрией, впервые примененную для построения совершенных д-значных кодов К Т Фелпсом и М Виллануевой в [13]. Это позволило расширить класс совершенных д-значных кодов и получить новую нижнюю оценку, оценка А. М. Романова отличается от (1) тем, что вместо 3 во втором мультипликативном члене стоит ^+1)

В параграфе 1.4 описана модификация метода свитчинга «-компонент за счет конфигураций (перестановок, действующих на элементах поля С?.Р(д)), такие преобразования не имеют аналогий в двоичном случае, поскольку в случае двоичного алфавита перестановка вырождается в обмен элементов 0 и 1.

Использование конфигураций демонстрирует следующее

Утверждение. Пусть Нд — д-значный код Хэмминга длины N = (дт—1)/(д—1), т> 2. Тогда для любой перестановки 7г на множестве {0,1,..., д — 1} множество

с" = (< угоитгф)

является совершенным д-значным кодом.

Следует отметить, что определение свитчинга в этом параграфе уже отличается от приведенного в параграфе 1.1, ранее речь шла о свитчинге (в терминах настоящего определения) по циклической перестановке длины д.

В этом параграфе доказана теорема о том, что коды, построенные с помощью описанной конструкции, являются совершенными.

В параграфе 1.5 получена нижняя оценка числа различных совершенных д-значных кодов, построенных модифицированным методом свитчинга а-компонент кода Хэмминга.

Теорема 4. Число /^(ЛГ) различных совершенных д-знач-ных кодов длины N — дп +1, п — (дт-1 - 1)/(д -1) не меньше, чем

(дО^^-З^"0"^. (2)

В доказательстве теоремы также учитывалось, что при построении не все коды получаются различными. Сравнивая с оценкой А. М. Романова [5], отметим, что оценка (2) лучше за счет первого главного мультипликативного члена.

Результаты первой главы опубликованы в работах [17] и [18].

Вторая глава посвящена описанию развития свитчинго-вого подхода к д-значному коду Хэмминга. Предложенная в этой главе конструкция позволяет для произвольной допустимой длины получить нижнюю оценку числа различных совершенных д-значных кодов, являющуюся на сегодняшний день лучшей. Оценка получается за счет свитчингов в коде Хэмминга специального вида компонент, называемых простыми компонентами (определение см. ниже)

В параграфе 2.1 и далее рассматривается поле Галуа <7.Р(д), где ц — степень простого и не равно простому, то есть д = рг, г > 1. В таком случае поле д) содержит простое подполе ОР(р) с элементами от 0 до р — 1 и возникает понятие простой ¿-компоненты.

Рассмотрим г-компоненту Иг кода Хэмминга Нд. Компонента Нг является подпространством над полем вР(д) кода Н^, д = ]/, г > 1. Подпространство над подполем С?Р(р), порожденное совокупностью векторов веса 3 с единичной г-й координатой, обозначим через Рг и назовем простой компонентой. То есть множеству Рг принадлежат векторы, полученные всевозможными линейными комбинациями с коэффициентами из подполя С>^(р) векторов, порождающих компоненту /?г. Такие компоненты, как было сказано выше, ввели К. Т. Фелпс, Ж. Рифа и М. Виллануева в работе [14]

Также в этом параграфе рассмотрена связь (т — 1)-мерной проективной геометрии РС?(т—1, д) со столбцами проверочной матрицы д-значного кода Хэмминга, см [13]. Приведено новое, отличное от известного в литературе, доказательство с помощью несложных законов проективной геометрии того факта, что ¿.^-компонента является ^-компонентой, где Ь — прямая в проективной геометрии РС(ш — 1,д), содержащая д +1 точку. То есть «^-компонента является г-компонентой по одному из д +1 возможных направлений.

В параграфе 2.2 описан метод свитчинга простых компонент Главное отличие от конструкции из параграфа 1.4 состоит

в том, что теперь в каждой г-компоненте Яг выделяются простые г-компоненты, что позволяет делать большее число свит-чингов уже для каждой простой г-компоненты в отдельности И в том и в другом случае свитчинги производятся по перестановкам, но в конструкции из параграфа 1 4 перестановки действуют на всех q элементах поля ¿^(д), где д = рг, г > 1, теперь же только на р элементах простого подпол я Доказана теорема о том, что множество, построенное из д-значного кода Хэмминга с помощью описанного метода, является совершенным д-значным кодом.

Предлагаемый здесь метод построения д-значных совершенных кодов является развитием метода свитчинга компонент д-значного кода из главы 1

В параграфе 2 3 доказана для любой допустимой длины N нижняя оценка числа различных совершенных д-значных кодов, при д = рг, г > 1

Теорема 6. Число ^(ЛГ) различных совершенных д-значных кодов длины N = не меньше, чем

Данная оценка является на сегодняшний день лучшей Более того в параграфе 2 1 доказано утверждение о том, что простая компонента специального вида является минимальной. Это свойство простых компонент означает, что приведенная выше оценка не может быть существенно улучшена с помощью свитчингов такого типа компонент.

Результаты второй главы опубликованы в работах [19] и [20].

В третьей главе исследована проблема пересечения д-значных совершенных кодов какие возможны мощности пересечения г](С\, С%) двух совершенных кодов С\ и Сч длины N7 Эта проблема была поставлена Т. Этционом и А. Варди в 1998

году в работе [11] Там же они предложили полное решение проблемы пересечения двоичных кодов Хэмминга, нашли наименьшее пересечение для совершенных двоичных нелинейных кодов любой допустимой длины, которое состоит из двух кодовых слов, а также получили возможные пересечения совершенных двоичных кодов, используя простые свитчинги двоичных кодов Хэмминга С В Августинович, У Хеден, Ф. И Соловьева (см. [6] и [7]) существенно продвинулись в решении проблемы пересечения для двоичных нелинейных кодов. В [7] доказано, что для всякого четного удовлетворяющего неравенствам

О < Ь < 2п+1-21°2(П+1)

найдутся совершенные двоичные коды С\ и Сг длины п = 2т - 1, т > 4, такие что ^(С^С^) = Ь СЕ Бар-Яшалом и Т. Этцион решили проблему пересечения для любых необязательно совершенных д-значных циклических кодов (см [8]), д>2

В параграфе 3 1 приводится более короткое, чем в [8], доказательство существования возможных мощностей пересечения д-значных кодов Хэмминга. Техника, развитая в этом параграфе для изучения пересечений линейных д-значных кодов Хэмминга, существенно использовалась для исследования пересечений произвольных нелинейных д-значных кодов одинаковой длины

В параграфе 3.2 описывается свитчинговый способ построения совершенных д-значных кодов, имеющих различные непустые пересечения с исходным кодом Хэмминга. Приведен спектр пересечений д-значных совершенных кодов, полученный сдвигами простых компонент.

Теорема 8. Для любого А; € {0,.. ,,р-К~21р-К} существуют два д-значных совершенных кода Нд и С длины N = щ+1 такие, что п(Н?,С) = к • \Рг\/р, где \Рг\ = />Кд~2)+п д = рГ

В параграфе 3 3с помощью комбинирования модификации конструкции Шонхайма из [15], методов свитчинга г-компонент и простых компонент, а также циклического сдвига координатных позиций кодов были доказаны Теоремы 9 (с помощью г-компонент) и 10 (с помощью простых компонент) о том, что для произвольной допустимой длины N = (qm — 1 )/{q - 1), т> 1, существуют два совершенных g-значных кода, пересечение которых меньше, чем минимальное непустое пересечение совершенных кодов той же длины, достигаемое сдвигами простых компонент, см теорему 8.

Параграф 3 4 посвящен построению различных разбиений пространства V^ на совершенные g-значные коды для любой допустимой длины N = (qm — l)/(g — 1), используя конструкцию совершенных g-значных кодов Шонхайма [15] и технику свитчингового метода простых компонент из параграфа 2.2. Доказана

Теорема 11. Для любого N = qn + 1, g = рг, существует не менее

«ГП+log г

V

различных разбиений пространства VqN на совершенные д-значные коды длины N.

Результаты этой главы получены совместно с Ф И. Соловьевой, опубликованы в [21] и [22].

Автор выражает глубокую искреннюю благодарность и признательность научному руководителю к ф -м н , доценту Ф И Соловьевой, под руководством которой была выполнена эта работа.

Список литературы

[1] Августинович С. ВСоловьева Ф. И. Построение совершенных бинарных кодов последовательными сдвигами

S-компонент // Пробл передачи информ 1997. Т. 33 Вып 3 С 15-21

[2] Васильев ЮЛ О негрупповых плотно упакованных кодах // Проблемы кибернетики М Наука, 1962 Вып 8 С. 337-339.

[3] Зиновьев В А , Леонтьев В. К О совершенных кодах // (Препринт/ ИППИ АН СССР). 1972 Вып 1 С. 26-35.

[4] Зиновьев В. А., Леонтьев В К. Несуществование совершенных кодов над полями Галуа // Проблемы управления и теории информации 1973. Вып. 2 С 123-132

[5] Романов А. М О разбиениях g-значных кодов Хэмминга на непересекающиеся компоненты // Дискрет, анализ и ие-след. операций 2004. Т. 11 № 3 С 80-87

[6] Avgustmovich S. V, Heden О., Solov'eva F I On intersections of perfect binary codes // Bayreuther Mathematische Schriften 2005 No 74. P 1-6

[7] Avgustmovich S. V., Heden О , Solov'eva F. I. On intersection problem for perfect binary codes // Des Codes Cryptogr 2006. V 39. No 3 P 317-322.

[8] Bar-Yahalom, S E., Etzion T. Intersection of isomorphic linear codes // Journal of Comb. Theory, Series A. 1997. V 80 No. 1. P. 247-256.

[9] Blakley G. R., Kabahartsh G. A When perfect secret sharing schemes with veto exist, Sixth Int. Workshop "Algebraic and Combinatorial Coding Theory", Pskov, Russia. September 1998 P 30-33

[10] Etzion T, Vardy A. Perfect binary codes, constructions, properties and enumeration // IEEE Trans Inform. Theory. 1994 V 40, N 3. P. 754-763

[11] Etzion T., Vardy A. Perfect binary codes and tilings: problems and solutions // SIAM J Discrete Math 1998. V. 11 No 2 P. 205-223

[12] Lvndstrom B On group and nongroup perfect codes m q symbols//Math Scand 1969. V 25 P 149-158

[13] Phelps K T, Vîllanueva M Ranks of <?-ary 1 perfect codes // Des Codes Cryptogr 2002 V. 27. No 1-2 P. 139-144.

[14] Phelps K T, Rifâ J, Vîllanueva M. Kernels of q-ary 1 perfect codes // Proc. Int Workshop on Coding and Cryptography, March 2003, Versailles (Prance), P 375-382

[15] Schonhevm J On linear and nonlinear smgle-error-correcting q-ary perfect codes // Information and Control. 1968. V. 12. No 1. P. 23-26.

[16] Tietàvavnen A On the nonexistence of perfect codes over finite fields // SIAM J Appl Math. 1973. V 24 P 88-96

Публикации автора по теме диссертации

[17] Лось А В Построние совершенных д-значных кодов последовательными сдвигами S-компонент // Пробл. передачи информ 2004 Т 40 Вып 1 С 33-39

[18] Construction of perfect q-ary codes // Proc Nmth Int. Workshop "Algebraic and Combinatorial Coding Theory" Bulgaria (Kranevo) June 2004 P 272-276.

[19] Los' A. V Construction of perfect q-ary codes by switchings of simple components // Proc. of Int Workshop on Optimal codes and related topics. Pamporovo, Bulgaria. June. 2005. P. 226-231.

[20] Лось А В. Построение совершенных g-значных кодов свитчингами простых компонент // Пробл передачи ин-форм 2006 Т 42 № 1 С 34-42

[21] Solov'eva F I, Los' А V On intersections of g-ary perfect codes // Proc Tenth Int. Workshop "Algebraic and Combinatorial Coding Theory" Zvenigorod, Russia September, 3-9 2006 P 244-247

[22] Соловьева Ф И, Лось А. В О пересечениях д-значных совершенных кодов // Сиб мат журнал 2008 Т 49 № 2 С 465-475

Лось Антон Васильевич

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

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Подписано в печать 02 04 08 Формат 60x84 1/16

Усл. печ. л. 1,2. Уч.-изд л. 1,0. Тираж 100 экз. Заказ N 60.

Отпечатано в ООО "Омега Принт" 630090 Новосибирск, пр. Лаврентьева, 6.

Введение

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

1.1. Основные понятия и определения

1.2. Свитчинговая конструкция А совершенных g-значных кодов

1.3. Нижняя оценка, полученная посредством конструкции А.

1.4. Свитчинговая конструкция В совершенных g-значных кодов

1.5. Нижняя оценка, полученная с помощью конструкции В.

Глава 2. Метод свитчинга простых компонент

2.1. Простые г-компоненты

2.2. Конструкция С совершенных g-значных кодов

2.3. Нижняя оценка числа различных совершенных g-значных кодов, полученная посредством конструкции С.

Глава 3. Свойства g-значных кодов

3.1. Пересечение g-значных кодов Хэмминга.

3.2. Пересечения совершенных g-значных кодов, построенных свитчингами простых компонент

3.3. О пересечениях совершенных g-значных кодов, полученных с использованием конструкции Шонхайма

3.4. О разбиениях пространства V^ на совершенные коды

Объектом исследования настоящей работы являются блочные коды над недвоичным алфавитом, исправляющие случайные ошибки. В условиях современной жизни теория кодирования имеет широкое практическое применение в системах цифровой связи и в устройствах хранения информации.

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

В качестве основных задач теории кодирования выделяют разработку методов построения кодов, исследование свойств кодов, разработку эффективных методов кодирования и декодирования. Несмотря на активные исследования целого ряда ученых в области теории кодирования, остается открытым множество проблем, связанных с совершенными кодами. Например, по-прежнему остается нерешенной основная проблема построения и перечисления совершенных д-значных кодов для q, равного степени простого числа. Эта проблема включает в себя разработку методов построения кодов, а также методов исследования свойств отдельных классов кодов с заданными характеристиками (параметрами или свойствами).

Ряд задач теории кодирования являются важными и для других математических дисциплин: комбинаторного анализа, теории групп, теории графов, криптологии. Таковой, например, является проблема упаковки шарами одного радиуса. Кроме того, многие из методов построения и изучения свойств совершенных g-значных кодов применяются для кодов с другими параметрами, например, для кодов с большими кодовыми расстояниями, которые способны обнаруживать и исправлять большее число ошибок.

Самостоятельный интерес в теории кодирования представляют собой исследования различных свойств кодов таких, например, как изучение групп автоморфизмов кодов, исследование спектральных свойств кодов, построение и исследование разбиений д-значного n-мерного куба на коды, исследование рангов и ядер кодов, пересечения кодов.

Все результаты данного исследования верны и для двоичных кодов, но в этом случае они преобразуются в уже известные, поскольку особенность строения многозначных полей Галуа является для данного исследования существенно важным.

Цель данной диссертации состоит в разработке новых методов построения совершенных кодов над недвоичным алфавитом, исследовании свойств таких кодов.

В диссертации используются известные методы и аппарат алгебраической и комбинаторной теории кодирования, комбинаторного анализа. Для исследования свойств кодов применены методы построения кодов, предложенные в диссертации.

Все результаты, представленные в диссертации, являются новыми. В работе предложено три разных свитчинговых метода построения совершенных g-значных кодов, а также применение этих методов для исследования пересечений совершенных g-значных кодов (проблема Т. Этциона и А. Вар-Ди).

1. В диссертации предложено развитие свитчингового метода построения и исследования нелинейных кодов — метода 5-компонент, который был предложен С. В. Августиновичем и Ф. И. Соловьевой в 1996 году и применен для построения широкого класса двоичных совершенных кодов.

2. Была предложена оригинальная модификация этого метода посредством так называемых конфигураций — перестановок, действующих на g элементах алфавита. Такие преобразования элементов g-значного алфавита значительно расширяют произвол в выборе сдвигаемого множества, не имеют аналогий в двоичном случае и позволяют получить более обширный класс совершенных кодов по сравнению с классом кодов, построенных методом свитчинга а-компонент.

3. Разработан новый метод свитчинга простых компонент для совершенных g-значных кодов над расширением простого поля, то есть при q = pT,r > 1. Этот метод позволил получить широкий класс различных совершенных g-значных кодов и, как следствие, рекордную на сегодняшний день нижнюю оценку числа таких кодов. Показано, что в коде Хэмминга не существует г-компонент меньшей мощности, чем простая г-компонента специального вида. Этот факт свидетельствует о том, что полученная оценка не может быть существенно улучшена методом свитчинга компонент. Простые компоненты были введены К. Т. Фелпсом, Й. Рифой и М. Виллануевой для исследования свойств специального вида линейных подкодов (р-ядер) g-значных кодов Хэмминга в работе [25].

4. Впервые исследована проблема пересечений совершенных нелинейных g-значных кодов, g > 2. Используя предложенные свитчинго-вые методы построения совершенных g-значных кодов, получен широкий спектр возможных пересечений таких кодов. Для любого допустимого N = (gm — l)/(g — 1), где т — целое число, сконструированы также два кода, пересечение которых меньше, чем пересечение, которое может быть получено применением свитчинговых методов.

Работа носит теоретический характер. Полученные в ней результаты могут быть применены в теории кодов, исправляющих ошибки: для дальнейшего исследования и построения g-значных кодов, для построения кодов с большими кодовыми расстояниями, для исследования свойств g-значных кодов; в криптографии (в схемах распределения секрета, см. [18]), комбинаторике. Возможно практическое применение для передачи информации по каналам связи, допускающим больше двух состояний сигнала, например, в оптоволоконных сетях.

Все результаты работы были апробированы на следующих международных конференциях: на конференциях по алгебраической и комбинаторной теории кодирования ACCT-IX (Кранево, Болгария, 2004 г.), АССТ-Х (Звенигород, 2006 г.); на конференции по дискретному анализу и исследованию операций DAOR-2004 (Новосибирск, 2004 г.); на конференции по оптимальным кодам и смежным областям ОС'2005 (Пампорово, Болгария, 2005 г.); на международной конференции "Математика в современном мире" (Новосибирск, 2007 г.). Результаты диссертации докладывались на семинаре "Теория информации и теория кодирования" ИППИ РАН, на семинаре "Синтез управляющих систем" мехмата МГУ, на семинаре "Дискретная математика и математическая кибернетика" факультета ВМК МГУ, на семинаре "Дискретный анализ" Института математики СО РАН. Все результаты были доложены на семинаре НГУ и Института математики СО РАН "Теория кодирования".

Основное содержание диссертации отражено в 6 печатных работах. Среди них 3 работы в журналах из перечня ВАК, 3 работы в рецензируемых трудах международных конференций.

Основные результаты диссертации.

1. Для совершенных g-значных кодов, q > 2, развит свитчинговый метод построения и исследования свойств кодов, известный как метод S-компо-нент.

2. Предложена модификация метода свитчинга компонент д-значного, q > 2, кода Хэмминга посредством конфигураций. Такие преобразования присущи g-значным, q > 2, кодам и не имеют аналогов в двоичном случае.

3. Предложен комбинаторный метод построения и исследования свойств <?-значных кодов, для q = pr, г > 1 - метод свитчинга простых компонент. Метод позволил построить обширный класс различных совершенных 9-значных кодов длины N = qn + 1 = (qm — l)/(q — 1), которых оказалось не менее

4. Исследована проблема пересечения нелинейных совершенных д-знач-ных кодов. С помощью метода свитчинга простых компонент получен широкий ряд возможных пересечений таких кодов. Показано, что существуют подвижные множества мощности меньшей, чем минимальная г-компонента кода Хэмминга.

Прежде чем перейти к обзору полученных результатов, приведем необходимые определения и обозначения.

Пусть V^ — N-мерное векторное пространство над полем Галуа GF(q), где q — степень простого числа. В пространстве V^ фиксирован некоторый базис и задана метрика Хэмминга. Под расстоянием Хэмминга d(x, у) между двумя произвольными векторами х и у пространства подразумевается число координат, в которых они различаются. Вес вектора z G VqN — это число его ненулевых координат. Произвольное подмножество С такого пространства является g-значным кодом. Код в VqN называется совершенным q-значным кодом длины N с расстоянием 3 (далее просто совершенным кодом), если \С\ = и расстояние между любыми двумя кодовыми словами (так в дальнейшем будем называть элементы кода) не менее 3. Эти условия эквивалентны плотной упаковке пространства V^ шарами единичного радиуса с центрами в кодовых словах.

Код С линеен, если он является подпространством V^. Совершенный линейный код в пространстве V^ называется кодом Хэмминга. Будем обозначать его через Hq.

Всюду далее полагаем N = qn + 1, п = (qTn~l - 1 )/{q — 1) и т > 2.

Впервые свитчинговый метод построения совершенных двоичных кодов был предложен Ю, JL Васильевым в 1962 году, см. [2]. Обзор свит-чинговых конструкций совершенных двоичных кодов можно найти в [9]. Первую свитчинговую конструкцию нелинейных совершенных д-значных кодов предложил в 1968 году Дж. Шонхайм, см. [29], эта конструкция является обобщением на случай q > 2 конструкции двоичных кодов Ю. JI. Васильева. Коды, получаемые с помощью конструкции Дж. Шонхайма были также описаны в 1969 году Б. Линдстремом, см. [19], там же приведена нижняя оценка числа таких кодов. В 1976 году В. А. Зиновьев в работе [5] предложил обощенную каскадную конструкцию совершенных д-значных кодов. В 1984 году К. Т. Фелпс предложил конструкцию, совершенных g-значных кодов, см. [22], обобщающую при q = 2 конструкцию Ю. JL Васильева. В 1986 году М. Моллар предложил конструкцию, см. [21], которая также обобщает конструкцию Ю. JI. Васильева и дает более широкий класс нелинейных совершенных двоичных кодов, кроме того при q > 2 она обобщает конструкцию Дж. Шонхайма. Еще одна каскадная конструкция совершенных g-значных кодов была предложена в 1998 году И. Думером в работе [14]. Развитие свитчинговых методов для g-значных кодов отражено в результатах Т. Етциона 1996 года [15], К. Т. Фелпса и М. ЛеВана 1995 года [23], а также К. Т. Фелпса и М. Виллануевой [24]. Более полный обзор существующих конструкций совершенных двоичных и g-значных кодов приведен в книге [13], см. главу 11.

В настоящей диссертации предложено три новых свитчинговых метода построения совершенных g-значных кодов, последовательно улучшавших нижнюю оценку числа различных совершенных g-значных кодов. Все три метода различаются между собой и могут найти применение для построения и исследования g-значных кодов, необязательно совершенных.

В первой главе приводится описание свитчингового метода построения совершенных g-значных кодов, который является обобщением для g-значного случая способа построения двоичных совершенных кодов последовательными сдвигами й-компонент, предложенного в 1996 г. С. В. Ав-густиновичем и Ф. И. Соловьевой в [1]. Этот метод был усовершенствован посредством дополнительных преобразований, не имеющих аналогов в двоичном случае. Приведены нижние оценки числа различных совершенных g-значных кодов, построенных описанными методами.

В параграфе 1.1 вводятся ключевые понятия для данного исследования: подвижное множество, «-компонента и a-компопента, сдвиг множества, множество R^. Приведем определения этих понятий.

Пусть С произвольный g-значный код длины N, М — некоторое подмножество его кодовых слов.

Пусть .F(M) множество, полученное с помощью некоторого преобразования J7 векторов множества М, причем множества М и ^(М) не совпадают. Множество М называется подвиоюным множеством кода С, если множество

С' = (С\М) U F(M) является g-значным кодом с теми же параметрами.

Согласно [29], сдвигом множества М по направлению г, г £ {1,2,., N}, на элемент а, где а — ненулевой элемент поля GF(q), называется множество М' = {х + aei\x е М}, где — вектор длины N с нулевыми координатами, кроме г-й, равной 1, то есть М' — М + aei, здесь aei означает покомпонентное произведение вектора ei на элемент а.

Множество М называется г-компонентой совершенного кода С, если код С' — (С\М) U (М + aei) является совершенным кодом.

Пусть а С {1,2,., N}. Множество М называется а-компонентой совершенного кода С, если для всех г Е а множество М является г-компо-нентой кода С.

Подпространство, порождённое совокупностью вершин веса 3 кода 7 с единичной г-й координатой, обозначим через Щ. Известно, см. [24], что множество Ri является г-компонентой.

Следующее утверждение раскрывает механизм свитчингового метода (от английского: switching — сдвиг, обмен), который предложен для-g-значного случая в [24], (см. также [15] и [23]). Однако следует различать свитчинговый метод, описанный здесь, от изложенных в [24], [15], [2], так как мы не ограничиваемся сдвигом только г-компонент, а сдвигаем (так же, как в [1]) ещё и специального вида гу/г-компоненты.

Итак, рассмотрим произвольный совершенный код С длины N. Пусть М/г,Mf2, . ,попарно непересекающиеся подмножества кода С такие, что М? являются ^-компонентами кода С, причём гх,«2, ,ik £ {1,2,., N} не обязательно все различны.

Утверждение.(См [24].) Пусть С произвольный совершенный код длины N = (qm — l)/(g — 1), m > 2. Тогда для любого ненулевого элемента as поля GF(q) множество к к C' = (C\UM^)U(Q(M?+as.eJ)

S=1 s=1 является совершенным g-значным кодом длины N.

В параграфе 1.2 рассмотрено разбиение g-значного кода Хэмминга на классы смежности линейной 5-компоненты, а также на классы смежности г-, j- и fc-компонент. Эти утверждения позволяют доказать Теорему 1 о том, что код, построенный из g-значного кода Хэмминга, методом свитчинга 5-компонент, является совершенным.

Основная идея метода свитчинга 5-компонент заключается в следующем. Сначала для каждой S-компоненты выбираем свое направление г из множества направлений а и делаем свитчинг, то есть сдвигаем все «-компоненты в каждой 5-компоненте на произвольный элемент поля GF(q), затем производим свитчинг полученных новых а-компонент, делая сдвиги по неиспользованным из множества а направлениям. В итоге результирующий код остается кодом с теми же параметрами, но отличным или даже неэквивалентным исходному.

Параграф 1.3 посвящен получению нижней оценки числа различных совершенных g-значных кодов, описанных конструкцией Теоремы 1. Поскольку построенные коды не все различны, для их сравнения вводится понятие функции сдвига. Функция сдвига /с определяет, на какие элементы поля GF(q) и в каких направлениях следует сдвигать кодовые слова кода Хэмминга, чтобы получить код С. Каждый совершенный код однозначно определяется своей функцией сдвига, причём несовпадающие коды имеют разные функции.

В параграфе 1.3 доказана

Теорема 2. Количество Fq(N) различных совершенных g-значных кодов длины N не меньше, чем g^(m-,} . (3g)^"(ro2). - (1)

Эта оценка улучшает ранее известную нижнюю оценку Б. Линдстрема, см. [19].

А. М. Романов в 2004 г., см. [8], для построения совершенных g-значных кодов использовал связь столбцов проверочной матрицы кода Хэмминга с проективной геометрией, впервые примененную для построения совершенных g-значных кодов К. Т. Фелпсом и М. Виллануевой в [24]. Это позволило расширить класс совершенных g-значных кодов и получить новую нижнюю оценку:

2)

В параграфе 1.4 описана модификация метода свитчинга 3-компонент за счет конфигураций (перестановок, действующих на элементах поля GF{q)), такие преобразования не имеют аналогий в двоичном случае, поскольку в случае двоичного алфавита перестановка сводится к обмену элементов 0 и 1.

Использование конфигураций демонстрирует следующее

Утверждение. Пусть Н^ — g-значный код Хэмминга длины N = (qm — 1)/(g — 1), т > 2. Тогда для любой перестановки 7г на множестве {0,1,., q — 1} множество

С' = (H?\Ri) U тг(Rt) является совершенным g-значным кодом.

Следует отметить, что определение свитчинга в этом параграфе уже отличается от приведенного в параграфе 1.1, ранее речь шла о свитчинге (в терминах настоящего определения) по циклической перестановке длины q.

В этом параграфе доказана теорема о том, что коды, построенные с помощью описанной конструкции, являются совершенными.

В параграфе 1.5 получена нижняя оценка числа различных совершенных g-значных кодов, построенных модифицированным методом свитчинга S-компонент кода Хэмминга.

Теорема 4. Число Fq(N) различных совершенных g-значных кодов длины N = qn + 1, п = (gm1 — l)/(q — 1) не меньше, чем д!)«п-(т-1}.3^"(м"4. (3)

Сравнивая с оценкой А. М. Романова (2), отметим, что оценка (3) лучше за счет первого главного мультипликативного члена.

Результаты первой главы опубликованы в работах [31] и [32].

Вторая глава посвящена описанию развития свитчингового подхода к g-значному коду Хэмминга. Предложенная в этой главе конструкция позволяет для произвольной допустимой длины получить нижнюю оценку числа различных совершенных g-значных кодов, являющуюся на сегодняшний день лучшей. Оценка получается за счет свитчингов в коде Хэмминга специального вида компонент, называемых простыми компонентами (определение см. ниже).

В параграфе 2.1 и далее рассматривается поле Галуа GF(q), где q — степень простого и не равно простому, то есть q = pr, г > 1. В таком случае поле GF(q) содержит простое подполе GF{p) с элементами от 0 до р — 1 и возникает понятие простой г-компопенты. рассмотрим г-компоненту iV кода Хэмминга . Компонента Ri является подпространством над полем GF(q) кода Н^, q = pr, г > 1. Подпространство над подполем GF(p), порожденное совокупностью векторов веса 3 с единичной i-й координатой, обозначим через Д и назовем простой компонентой. То есть множеству Pi принадлежат векторы, полученные всевозможными линейными комбинациями с коэффициентами из подполя GF(p) векторов, порождающих компоненту Ri. Такие компоненты, как было сказано выше, ввели К. Т. Фелпс, Ж. Рифа и М. Виллануева в работе [25].

Также в этом параграфе рассмотрена связь (т — 1)-мерной проективной геометрии PG(m— 1, q) со столбцами проверочной матрицы g-значного кода Хэмминга, см. [24]. Приведено новое, отличное от известного в литературе, доказательство того факта, что ^-компонента является L-компонентой, где L — прямая в проективной геометрии PG(m — 1, g), содержащая q + Т точку. То есть г//г;-компонента является i-компонентой по одному из q + 1 возможных направлений.

В параграфе 2.2 описан метод свитчинга простых компонент. Главное отличие от конструкции из параграфа 1.4 состоит в том, что-теперь в каждой г-компоненте Ri выделяются простые г-компоненты, что позволяет делать большее число свитчингов уже для каждой простой г-компоненты в отдельности. И в том и в другом случае свитчинги производятся по перестановкам, но в конструкции из параграфа 1.4 перестановки действуют на всех q элементах поля GF(q), где q — pr,r > 1, теперь же только на р элементах простого подполя GF(p). Доказана теорема о том, что множество, построенное из g-значного кода Хэмминга с помощью описанного метода, является совершенным g-значным кодом.

Предлагаемый здесь метод построения g-значных совершенных кодов является развитием метода свитчинга компонент g-значного кода из главы 1.

В параграфе 2.3 доказана для любой допустимой длины N нижняя оценка числа различных совершенных g-значных кодов, при g = pr, г > 1.

Теорема16. Число Fq(N) различных совершенных g-значных кодов длил т am — 1 ны N — -—т- не меньше, чем <7-1 '

Данная оценка является на сегодняшний день лучшей. Более того в параграфе 2.1 доказано утверждение о том, что простая компонента специального вида является минимальной. Это свойство простых компонент означает, что приведенная выше оценка не может быть существенно улучшена с помощью свитчингов такого типа компонент.

Результаты второй-главы опубликованы в работах [33] и [34].

• В третьей главе исследована проблема пересечения g-значных совершенных кодов: какие возможны мощности пересечения Г}(С\, Сг) двух совершенных кодов С\ и Сг длины iV? Эта проблема была поставлена Т. Эт-ционом и А. Варди в 1998 году в работе [16]. Там же они предложили полное решение проблемы пересечения двоичных кодов Хэмминга, нашли наименьшее пересечение для совершенных двоичных нелинейных кодов любой допустимой длины, которое состоит из двух кодовых слов, а также получили, возможные пересечения совершенных двоичных кодов, используя простые свитчинги двоичных кодов Хэмминга. С. В. Августинович, У. Хе-ден, Ф. И. Соловьева (см. [10] и [11]) существенно продвинулись в решении-проблемы пересечения для двоичных нелинейных кодов. В работе [11] они доказали, что для всякого четного t, удовлетворяющего

0 < t < 2n+1-21og(n+1) найдутся совершенные двоичные коды С\ и С2 длины п = 2т — 1, т > 4, такие что t](Ci,C2) = t. Проблема пересечения для любых необязательно совершенных g-значных циклических кодов (см. [12]), q > 2, была решена С. Е. Бар-Яшаломом и Т. Этционом.

В параграфе 3.1 приводится более короткое, чем в [12], доказательство существования возможных мощностей пересечения g-значных кодов Хэмминга. Техника, развитая в этом параграфе для изучения пересечений линейных g-значных кодов Хэмминга, существенно использовалась для исследования пересечений произвольных нелинейных g-значных кодов одинаковой длины.

В параграфе 3.2 описывается свитчинговый< способ построения совершенных g-значных кодов, имеющих различные непустые пересечения с исходным кодом Хэмминга. Приведен спектр пересечений g-значных совершенных кодов, полученный сдвигами простых компонент.

Теорема 8. Для любого k £ {0,. ,р • К — 2,р • К} существуют два g-значных совершенных кода и С длины N = ng + 1 такие, что г1(Н^С) = к-\Рг\/Р, где |Pi| =p"K<7-2)+n> q =

В параграфе 3.3 с помощью комбинирования предложенной в диссертации модификации конструкции Шонхайма из [29], методов свитчинга г-компонент и простых компонент, а также циклического сдвига координатных позиций кодов были доказаны Теоремы 9 (с помощью г-компонент) и 10 (с помощью простых компонент) о том, что для произвольной допустимой длины N = (gm — l)/(g — 1), ш > 1, существуют два совершенных g-значных кода, пересечение которых меньше, чем минимальное непустое пересечение совершенных кодов той же длины, достигаемое сдвигами простых компонент, см. теорему 8.

Параграф 3.4 посвящен построению различных разбиений пространства V^ на совершенные g-значные коды для любой допустимой длины N = (gm — l)/(g — 1). При этом были использованы конструкцию совершенных g-значных кодов Шонхайма [29] и техника свитчингового метода простых компонент из параграфа 2.2. Была получена следующая нижняя оценка числа различных разбиений пространства

Теорема 11. Для любого N = qn + 1, g = рг, существует не менее rn+logr Y различных разбиений пространства VqN на совершенные д-значные коды длины N.

Результаты этой главы получены совместно с Ф. И. Соловьевой, опубликованы в [35] и [36].

Автор выражает глубокую искреннюю благодарность и признательность научному руководителю к.ф.-м.н., доценту Ф. И. Соловьевой, под руководством которой была выполнена эта работа.

Заключение

В диссертации получены следующие результаты:

1. Для совершенных g-значных кодов, q > 2, развит свитчинговый метод построения и исследования свойств кодов, известный как метод а-компо-нент.

2. Предложена модификация метода свитчинга компонент g-значного, g > 2, кода Хэмминга посредством конфигураций — перестановок на элементах поля GF(q). Такие преобразования свойственны g-значным, д > 2, кодам и не имеют аналогов в двоичном случае.

3. Предложен комбинаторный метод построения и исследования свойств g-значных кодов, для g = pr, г > 1 — метод свитчинга простых компонент. Метод позволил построить обширный класс различных совершенных g-значных кодов длины N = qn + 1 = (дш — 1)/(д — 1), которых оказалось не менее

4. Исследована проблема пересечения нелинейных совершенных g-значных кодов. С помощью метода свитчинга простых компонент получен широкий ряд возможных пересечений таких кодов. Показано, что существуют подвижные множества мощности меньшей, чем минимальная г-компонента кода Хэмминга.

1. Августинович С. В., Соловьева Ф. И. Построение совершенных бинарных кодов последовательными сдвигами й-компонент // Пробл. передачи информ. 1997. Т. 33. Вып. 3. С. 15-21.

2. Васильев Ю. Л. О негрупповых плотно упакованных кодах // Проблемы кибернетики. М: Наука, 1962. Вып. 8. С. 337-339.

3. Зиновьев В. А., Леонтьев В. К. Теорема о несуществовании; совершенных кодов над полями Галуа // (Препринт/ ИППИ АН СССР). 1972.

4. Зиновьев В. А., Леонтьев В. К. Несуществование совершенных кодов над полями Галуа // Проблемы управления и теории информации. 1973. Вып. 2. С. 123-132.

5. Зиновьев В. А. Обобщенные каскадные коды // Пробл. передачи информ. 1976. Т. 12. Вып. 1. С. 2-9.

6. Кротов Д. С. Нижние оценки числа m-квазигрупп порядка 4 и числа совершенных двоичных кодов // Дискрет, анализ и исслед. операций. Сер. 1. 2000. Т. 7, № 2. С. 47-53.

7. Малюгин С. А. О нижней оценке числа совершенных двоичных кодов // Дискрет, анализ и исслед. операций. Сер. 1. 1999. Т. 6, № 1. С. 44-48.

8. Романов A.M. О разбиениях g-ичных кодов Хэмминга на непересекающиеся компоненты // Дискрет, анализ и исслед. операций. 2004. Т. И. № 3. С. 80-87.

9. Соловьева Ф. И. Введение в теорию кодирования, учебное пособие // Изд. Новосибирского гос. университета, г. Новосибирск. 2006. 123 с.

10. Avgustinovich S. V., Heden 0., Solov'eva F. I. On intersections of perfect binary codes // Bayreuther Mathematische Schriften. 2005. No. 74. P. 1-6.

11. Avgustinovich S. V., Heden O., Solov'eva F. I. On intersection problem for perfect binary codes // Des. Codes Cryptogr. 2006. V. 39. No. 3. P. 317-322.

12. Bar-Yahalom S. E., Etzion T. Intersection of isomorphic linear codes // Journal of Combin. Theory. Series A. 1997. V. 80. No. 1. P. 247-256.

13. Cohen G., Honkala I., Litsyn S., Lobstain A. Covering Codes // North-Holand. Elsevier. Amsterdam. 1997.

14. Dumer I.I. Concatinated codes and their multylevel generalizations. // In Handbook of coding theory. 1998. Huffman and Pless. P. 1911-1988.

15. Etzion Т., Vardy A. Perfect binary codes: constructions, properties and enumeration // IEEE Trans. Inform. Theory. 1994. V. 40. No. 3. P. 754-763.

16. Etzion Т., Vardy A. Perfect binary codes and tilings: problems and solutions // SIAM J. Discrete Math. 1998. V. 11. No. 2. P. 205-223.

17. Krotov D. S., Avgustinovich S. V. On the number of 1-perfect binary codes: a lower bound, Tenth Int. Workshop "Algebraic and Combinatorial Coding Theory", Zvenigorod, Russia. September. 2006. P. 161-164.

18. Blakley G. R., Kabatianski G. A. When perfect secret sharing schemes with veto exist, Sixth Int. Workshop "Algebraic and Combinatorial Coding Theory", Pskov, Russia. September. 1998. P. 30-33.

19. Lindstrom B. On group and nongroup perfect codes in q symbols // Math. Scand. 1969. V. 25. P. 149-158.

20. MacWilliams F.G., Sloane N.J. A. The theory of error correcting codes. New York: North-Holland. 1977. P. 744. (Русский перевод: Мак-Вилъямс Ф. Дж., Слоэн Н. Дою. А. Теория кодов, исправляющих ошибки: Пер. с англ. М.: Связь. 1979. 744 С.)

21. Mollard M. A generalized parity function and its use in the construction of perfect codes // SIAM J. Algebraic Discrete Methods. 1986. V. 7. P. 113-115.

22. Phelps К. T. A product construction for perfect codes over-: arbitrary alphabets // IEEE Trans. Inform. Theory. 1984. V. 30. P. 769-771.

23. Phelps К. Т., LeVan M. J. Kernels of nonlinear Hamming codes, Designs // Codes and Cryptography. 1995. V. 6. P. 247-257.

24. Phelps К. Т., Villanueva. M. Ranks of q-ary 1 perfect codes // Des. Codes Cryptogr. 2002. V. 27. No. 1-2. P. 139-144.

25. Phelps К. Т., Rifa J., Villanueva M. Kernels of g-ary 1 perfect codes // Proc. Int. Workshop on Coding and Cryptography, March 2003, Versailles (Prance), P. 375-382.

26. Phelps К. Т., Villanueva M. Intersection of Hadamard codes // IEEE Trans. Inf. Theory. 2007. V. 53. No. 5. P. 1924-1928.

27. Rifa JSolov'eva F. I., Villanueva M. On the intersection of additive perfect codes // IEEE Trans. Inf. Theory. 2008. V. 54. No. 3. to appear.

28. Rifa J.; Solov'eva F.I., Villanueva M. On the intersection of additive extended and non-extended perfect codes // Proc. Int. Workshop on Coding and Cryptography. Versailles, France. April, 16-20. 2007. P. 333-341.

29. Schonheim J. On linear and nonlinear single-error-correcting q-ary perfect codes // Inform. Control. 1968. V. 12. No. 1. P. 23-26.

30. Tietavainen A. On the nonexistence of perfect codes over finite fields. I/ SIAM J. Appl. Math. 1973. V. 24. P. 88-96.

31. Лось А. В. Построние совершенных g-значных кодов последовательными сдвигами 5-компонент // Пробл. передачи информ. 2004. Т. 40. Вып. 1. С. 33-39.

32. Los' А. V. Construction of perfect g-ary codes // Proc. Ninth Int. Workshop "Algebraic and Combinatorial Coding Theory" Bulgaria (Kranevo), June 2004. P. 272-276.

33. Los' A. V. Construction of perfect g-ary codes by switchings of simple components // Proc. of Int. Workshop on Optimal codes and related topics. Pamporovo, Bulgaria. June. 2005. P. 226-231.

34. Лось А. В. Построение совершенных д-ичных кодов свитчингами простых компонент j j Пробл. передачи информ. 2006. Т. 42. № 1.

35. Solov'eva F.I., Los' А. V. On intersections of g-ary perfect codes // Proc. Tenth Int. Workshop "Algebraic and Combinatorial Coding Theory". Zvenigorod, Russia. September, 3-9. 2006. P. 244-247.

36. Соловьева Ф. И., Лось А. В. О пересечениях д-значных совершенных кодов // Сиб. мат. журнал. 2008. Т. 49. № 2. С. 465-475.1. С. 34-42.