Комбинаторные методы построения и исследования кодов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

На правах рукописи УДК 621 391 15

СОЛОВЬЕВА Фаина Ивановна

КОМБИНАТОРНЫЕ МЕТОДЫ ПОСТРОЕНИЯ И ИССЛЕДОВАНИЯ КОДОВ

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

АВТОРЕФЕРАТ

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

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

003167314

00316742234584

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

Официальные оппоненты доктор физико-математических наук,

профессор В А Зиновьев доктор физико-математических наук, профессор А А Нечаев, доктор технических наук, профессор Б Я Рябко Ведущая организация Московский физико-технический институт (государственный университет)

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

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

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

- Ц»

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

Ю В Шамардин

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

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

Предмет исследования настоящей работы - комбинаторная и алгебраическая теория блоковых кодов, исправляющих случайные ошибки, новые комбинаторные,методы построения и исследования таких кодов Комбинаторная и алгебраическая теория блоковых кодов является важным разделом теории кодирования В диссертации исследуются в основном двоичные нелинейные коды, среди них совершенные коды, коды с параметрами кодов Рида-Маллера, транзитивные коды, двоичные коды, содержащие схемы, системы Штейнера, КГОЭ-коды Большинство результатов, представленных в данной работе, получено для совершенных кодов или кодов, связанных с ними рядом свойств

Актуальность разработки новых методов построения кодов и исследования их свойств (как известных кодов, так и построения новых кодов) в теории кодирования диктуется, прежде всего, задачами поиска кодов и такого их задания, которое позволит разработать более эффективные алгоритмы кодирования и декодирования с целью экономной передачи информации по каналам связи, а также применением таких кодов в криптографии На практике зачастую используются линейные коды Однако в последнее время в теории кодирования все большую актуальность приобретают нелинейные коды, например, транзитивные коды, среди них £2^4-

линейные, ^-линейные, их конструирование, классификация Актуальность построения новых классов нелинейных кодов и изучения их свойств мотивирована следующими причинами Во-первых, классы нелинейных кодов намного мощнее классов линейных кодов с теми же параметрами и, кроме того, часто линейный д-значный код с заданными параметрами единствен (как, например, код Хэм-минга, двоичные коды Рида-Маллера) Во-вторых, за последние два десятилетия среди нелинейных кодов были открыты классы ^-линейных кодов, среди которых имеется много неэквивалентных кодов с фиксированными параметрами (например, коды Препараты, коды Кердока, коды с параметрами кодов Рида-Маллера) Кроме того, некоторые нелинейные коды имеют мощность, большую мощности линейных кодов той же длины и с тем же кодовым расстоянием (например, коды Препараты в два раза мощнее кодов БЧХ той же длины с расстоянием 5) Эти обстоятельства служат весомым основанием для поиска применения таких нелинейных кодов в криптографии в кодовых криптосистемах с открытыми ключами Таким образом для нелинейных кодов возникают естественные математические (комбинаторные) задачи существования и описания (классификации) кодов с данными параметрами Эти проблемы предусматривают, прежде всего, разработку методов построения кодов, а также методов исследования свойств классов кодов с заданными характеристиками (параметрами или свойствами)

Актуальность исследования совершенных кодов обусловлена следующими обстоятельствами Совершенные коды представляют собой один из наиболее важных (как своими свойствами, так и методами, разработанными для их построения и исследования) предметов теории кодов, корректирующих ошибки Код над полем Га-луа называется совершенным, если совокупность шаров од-

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

сификация даже двоичных совершенных кодов длины 15, недостаточно изучены коды полного ранга, нет полного описания групп автоморфизмов совершенных кодов, структуры их ¿-компонент Последние три проблемы непосредственно связаны с основной проблемой для совершенных кодов - проблемой их классификации Известно, что совершенные коды обладают целым рядом регулярных свойств (см их описание ниже при описании результатов диссертации) Плотная упакованность совершенных кодов предопределяет их оптимальность, т е максимальность мощности кода при заданной длине кода и кодовом расстоянии Проблема упаковки шарами одного радиуса - задача, важная как с точки зрения самой теории кодирования, так и с точки зрения целого ряда других математических дисциплин комбинаторного анализа, теории групп, теории графов, комбинаторной топологии, геометрии, криптоло-гии, синтеза схем Кроме того, совершенные коды представляют собой удобный модельный объект для развития подходов к построению и исследованию кодов с большими кодовыми расстояниями - многие из методов построения и изучения свойств совершенных двоичных кодов уже применены и успешно развиваются для кодов с другими параметрами, например, для равномерно упакованных кодов, кодов с параметрами кодов Рида-Маллера, четверичных кодов с метрикой Ли, д-значных, q > 2, кодов с метрикой Хэммин-га, диаметральных совершенных кодов с метрикой Джонсона, для совершенных раскрасок, центрированных функций Много усилий исследователей посвящено за последние десять лет разработке методов построения и методов исследования свойств совершенных кодов

К числу открытых проблем (полное или частичное решение которых приводится в данной работе) относились разработка прямых комбинаторных методов построения и исследования свойств нелинейных двоичных кодов, разработка методов построения транзитивных кодов, исследование метрической жесткости кодов, проблема классификации совершенных кодов, проблема Ф Хергерта о существовании несистематических совершенных кодов, выяснение структуры г-компонент совершенных кодов и строения группы, автоморфизмов таких кодов, проблема Т,,Этциона и А Варди построения и исследования разбиений д-значного п-мерного куба на совершенные коды

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

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

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

1 В диссертации предложен новый комбинаторный (свитчинго-вый) метод построения и исследования нелинейных кодов, названный методом а-компонент Этот метод применен к совершенным двоичным кодам и позволил сделать существенное продвижение в решении проблемы классификации совершенных двоичных кодов малых рангов Используя его, удалось улучшить, впервые после более чем 30-летнего перерыва, нижнюю оценку Ю Л Васильева [5] для числа неэквивалентных совершенных кодов Метод позволил получить дважды экспоненциальный по мощности класс неэквивалентных совершенных двоичных кодов С помощью этого метода был решен ряд открытых проблем для совершенных кодов

2 Разработаны новые свитчинговые методы построения транзитивных двоичных кодов Предложен новый метод построения неэквивалентных четверичных кодов Двоичные образы этих кодов под действием отображения Грея имеют параметры классических двоичных линейных кодов Рида-Маллера и обладают такими регулярными свойствами, как транзитивность, дистанционная регулярность Построен новый класс неэквивалентных совершенных транзитивных кодов длины п = 2к — 1, к > 4, таких кодов оказалось не менее [к/2\2 Аналогичный результат верен для расширенных совершенных транзитивных кодов

3 Новым является комбинаторный метод локального анализа, разработанный для исследования структуры компонент двоичных совершенных кодов, а именно строения г-компонент характеристического графа произвольного совершенного кода Этот метод позволил решить проблему существования неэквивалентных г-компонент максимальной мощности и построить новые классы кодов с максимальными по мощности связными г-компонентами для любой допустимой длины кода те > 7 Посредством этого метода была решена проблема построения неизоморфных замощений (сфер с пленками Мебиуса) с помощью специальных пар систем троек Штейнера порядка те для каждого те = 3 (mod 6)

4 Решена проблема Ф Хергерта - для каждого допустимого п > 127 доказано (конструктивно) существование класса несистематических совершенных двоичных кодов Для этой цели был развит метод свитчинга компонент минимальной мощности, названный методом г-компонент (независимо для решения других проблем такой подход был применен немного раньше Т Этционом и А Варди в [24], а также К Т Фелпсом и М ЛеВаном в [33])

5 Предложен новый метод (i,a)-star (выявление локально-жестких фрагментов кодов, который также является методом локального анализа) для исследования метрической жесткости кодов Посредством этого метода полностью выяснен вопрос о метрической жесткости g-значных совершенных кодов, q > 2, и некоторых классов MDS-кодов Доказано, что при п > к4 произвольный приведенный, т е. содержащий нулевой вектор, двоичный код длины п, содержащий 2-(те, к, А)-схему, является метрически жестким кодом

6 Предложен новый комбинаторный метод (который также можно отнести к методу локального анализа) исследования группы автоморфизмов произвольного совершенного двоичного кода, основанный на тех фактах, что каждое кодовое слово совершенного кода связано со своей системой троек Штейнера, характеристический граф совершенного кода связен, код представляет собой замощение всех своих систем троек Штейнера - локальных фрагментов Для этого потребовался также комбинаторный подход к изучению строения группы автоморфизмов кодовых систем троек Штейнера, что представляет самостоятельный интерес

7 Предложены новые комбинаторные (каскадные и свитчинго-

вые) методы построения богатых классов разбиений Хэммингова пространства на совершенные коды и совершенные расширенные коды

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

Апробация работы. Все результаты работы прошли апробацию на следующих международных конференциях на конференциях по алгебраической и комбинаторной теории кодирования АССТ-1У (Новгород, 1994 г), АССТ-У (Созополь, Болгария, 1996 г), АССТ-У1 (Псков, 1998 г), АССТ-УП (Банско, Болгария, 2000 г), АССТ-УШ (Царское Село, 2002), АССТ-1Х (Кранево, 2004), АССТ-Х (Звенигород, 2006), на минисеминаре по упаковкам и покрытиям (Варшава, Польша, 1996 г), на международном симпозиуме по теории информации (Ульм, Германия, 1997 г), на международной конференции по теории информации (Килларни, Ирландия, ] 998 г), на международном симпозиуме, посвященном 60-летию профессора Р Альсведе (Билефельд, Германия, 1998 г), на международной конференции по геометрии и ее приложениям (Новосибирск, 2000), Сибирской конференции по исследованию операций 8С011-98 и 8С(Ж-2000, на конференциях по дискретному анализу и исследованию операций БА011-2002, 2004 (Новосибирск, 2002 г, 2004 г), на международных конференциях по кодированию и криптографии \VCC-1999, 2001, 2003 и 2007 г г (Париж, Франция), на конференции "Математика в современном мире" (Новосибирск, 2007) Результаты диссертации докладывались на семинарах "Дискретный анализ" НГУ и Института математики СО РАН, "Теория информации и теория кодирования" ИППИ РАН, "Дискретная математика" НГУ и ИМ СО РАН, на семинарах Мюнхен-

ского технического университета и университета Ульма (Германия,

1997 г), в Билефельдском университете (Билефельд, Германия,

1998 г, 2003, 2007), в Институте математики Болгарской Академии Наук (София, Велико Тырново, Болгария, 1999 г), в Линче-пинском университете (Линчепинг, Швеция, 1999 г и 2000 г), в Королевском технологическом университете Стокгольма (Стокгольм, Швеция, 1999, 2000, 2001, 2002, 2004, 2006, 2007 г), в Похангском университете (Поханг, Корея, 2003, цикл из 8 лекций) Все результаты были доложены на семинаре НГУ и Института математики СО РАН "Теория кодирования" Некоторые результаты диссертации включены в книгу Ж Коэна с соавторами "Covering codes" и в "Handbook on coding theory" Результаты первой, третьей, четвертой (частично) глав диссертации были включены в цикл работ, занявших в 2002 г первое место на конкурсе научных работ в ИМ СО РАН

Публикации. По теме диссертации автором опубликовано 42 работы, см [39]-[80], среди них одна монография по совершенным кодам и одно учебное пособие по теории кодирования, опубликованное под грифом УМО

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

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

2ji_iog2(n+i) aJS-log2(n+i) 2 6

2 Решена проблема Хергерта о существовании несистематических совершенных двоичных кодов длины п для каждого допустимого п > 127

3 Предложено несколько свитчинговых методов построения бесконечных классов -транзитивных кодов Построено не менее [к/2J2 неэквивалентных совершенных транзитивных кодов длины п = 2к ~ 1,к > 4 Аналогичный результат получен для расширенных совершенных транзитивных кодов Построен класс неэквивалентных ^-линейных кодов длины 2т, т > 3, с параметрами клас-

сических кодов Рида-Маллера RM {г, m) для любой допустимого п и любого г g {1, ., m — 2}

4 Предложен новый метод исследования свойств кодов, являющийся методом локального анализа Посредством этого метода исследовано строение г-компонент произвольного совершенного кода Решена (конструктивно) проблема существования неэквивалентных компонент максимальной мощности, вложимых в совершенные коды Для каждого допустимого га построен класс совершенных кодов длины п с г-компонентами как неэкстремальной, так и максимально возможной мощностей

5 Полностью решен вопрос о метрической жесткости д-значных совершенных кодов, g > 2, и некоторых классов MDS-кодов Доказано также, что при п > кА произвольный приведенный код длины га, содержащий 2-(га, к, А)-схему, является метрически жестким

6 Решена (конструктивно) проблема существования неизоморфных неориентируемых двуцветных замощений (сфер с пленками Мебиуса) порядка га для каждого п = 3 (mod б) и половины классов вычетов n = l (mod 6)

Личный вклад. Диссертационная работа представляет собой единый цикл многолетних исследований автора, объединенных не только предметами, но и методами изучения В совместных работах соискателю принадлежат идеи новых методов кодирования (предложенных в этих работах) и методов исследования свойств кодов, ключевые моменты разработки этих методов, применение к решению открытых проблем теории кодирования Отдельные элементы доказательств утверждений и теорем выполнены в соавторстве при непосредственном участии соискателя Конфликт интересов с соавторами отсутствует

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

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

конце приведен список публикаций автора по теме диссертации Объем диссертации - 202 страницы

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

При решении каждой из задач, рассмотренных в данной работе, был разработан оригинальный математический аппарат, который получил дальнейшее развитие (см ниже описание результатов) и применение в теории кодирования. Особенность решенных задач определяется главным образом тем, что локальное строение исследуемого или конструируемого объекта (кода, блок-схемы, характеристического графа кода) однородно и регулярно, а глобальное строение специфично Совершенные коды обладают целым рядом регулярных свойств, таких как дистанционная инвариантность, равномерная распределенность кодовых слов в пространстве по граням больших размерностей, антиподальность для двоичных совершенных кодов (помимо вершины х совершенному двоичному коду всегда принадлежит вершина х + 1, где 1 - вектор, все координаты которого равны единице), совокупности кодовых слов веса 3 совершенного двоичного кода С длины та, содержащего нулевой вектор, отвечает система троек Штейнера STS(C) порядка п На фоне этих однородных свойств в классе совершенных кодов неожиданно проявляются нерегулярные свойства, например, все совершенные коды длины п > 15 (и даже линейный совершенный код - код Хэмминга) не являются дистанционно-регулярными, существует богатый класс несистематических кодов, ранги и размерности ядер совершенных кодов варьируются от минимально возможных до максимальных, каждая конечная группа изоморфна группе симметрия некоторого совершенного кода, порядок групп автоморфизмов совершенных двоичных кодов длины п варьируется от 2 до порядка общей линейной группы GL(\og(n + 1), 2) (здесь и далее под log будем понимать логарифм по основанию 2), умноженной на мощность кода, а количество г-компонент (специального вида компонент связности характеристического графа совершенного кода)

гг-j-l . . .

произвольного совершенного кода длины п - от 2 до 2 2 /(п + 1) и т. д Обзоры по построению совершенных двоичных кодов и изучению их свойств см в [23, 43, 60, 65, 66, 77, 80], д-значных - в [23]

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

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

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

Подмножество пространства Р71 всех д-значных векторов длины п над полем Галуа по отношению к метрике Хэмминга называется д-значным кодом С длины п. Элементы кода С называются кодовыми словами или векторами. Параметры д-значного линейного кода С над полем Галуа С^Р(д), д > 2, будем обозначать через [п,М,сС\д, где п - длины кода, М - его мощность, й - кодовое расстояние (наименьшее расстояние по Хэммингу между кодовыми словами) Для нелинейного кода С параметры будем обозначать через (п, М, сГ)я, в двоичном случае д будем опускать Векторное пространство размерности п над 2) обозначим через Еп

Два кода С, С' С Р"1 называются изоморфными, если существует подстановка ж такая, что С" = п(С) — (тг(х) : х € С} Коды С, С' С Рп эквивалентны, если найдется п подстановок т\, ,тп на д элементах поля Галуа ^ и подстановка 7Г на п координатных позициях такие, что

С' = {к(тх{хх),Т2{Х2), ■■,Тп(хп)) (Х1,Х2,. .,Хп)€С}.

Расстояние Хэмминга й(х, у) между векторами х,у е равно числу координат, в которых эти векторы различаются (далее век-

торы будем обозначать выделенными строчными латинскими буквами) Кодовое расстояние ё определяется как й — тгп у) для любых различных кодовых слов х, у е С. Группой автоморфизмов Аи1;(С) произвольного кода С длины п является группа изометрий пространства Еп, переводящих код в себя, те

А^(С) = {(«, 7г) | V Ч" тг(С) = С}

Множество

ЭутСС) = {-к е 5„ | тг(С) - С}

называется группой симметрий кода С Код С транзитивен, если его группа автоморфизмов действует транзитивно на всех его кодовых словах Размерность линейной оболочки < С > кода С называется рангом кода С Совокупность периодов кода С, те кодовых слов х £ С таких, что х + С — С называется ядром кода С Код мощности М (размерности к — 1о£дМ) длины п называется систематическим, если существуют такие к координатных позиций кода, что код, полученный из исходного выкалываем (удалением) оставшихся п—М координат, совпадает со всем пространством Ец Системой троек Штейнера 8Т8(п) порядка п называется система сочетаний из п элементов по три такая, что каждая неупорядоченная пара элементов содержится в точности в одной тройке Другие определения целесообразно привести ниже при описании результатов диссертации

Широко известна теорема В А Зиновьева и В К Леонтьева, полученная независимо Э Тиетвайненом, см [7, 8, 38], о том, что нетривиальные совершенные д-значные коды длины п, исправляющие ошибки, существуют только при п = (дк — 1)/(д - 1), к > 2, такие коды имеют кодовое расстояние 3 (далее упоминаемые как совершенные), при п — 23 - это двоичный код Голея с кодовым расстоянием 7, а также при п — 11 - троичный код Голея с кодовым расстоянием 5 Оба кода Голея единственны с точностью до эквивалентности Ю. Л. Васильевым [5] в 1962 г. был открыт класс совершенных двоичных кодов, число неэквивалентных таких кодов оказалось дважды экспоненциальным Тем самым была опровергнута гипотеза Г. С Шапиро и Г. Л. Злотника [37] о единственности существования совершенного двоичного кода (кода Хэмминга) для

каждой допустимой длины Для составных д известно, что для расстояний, больших 3, совершенные коды не существуют, и также не существуют совершенные коды с расстоянием 3 при д = 6, п = 7 и п = 19

В первой главе приводятся новые евитчинговые методы построения кодов метод «-компонент и метод последовательных сдвигов г-компонент Основная идея метода свитчинга состоит в следующем в произвольном коде С длины п рассмотрим некоторое подмножество М кодовых слов Если найдется в Fíl подмножество М', отличное от множества М такое, что множество

С' — (С \М) и М'

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

Рассмотрим основную идею метода а-компонент на примере совершенных кодов (из описания метода следует, что он имеет место для д-значных кодов, д > 2, отличных от совершенных) Пусть С -произвольный совершенный код длины п и Я - некоторое подмножество его кодовых слов Свитчингом множества Я в направлении г, где г € I ~ {1,2, ,п}, назовем множество Я', полученное из К сдвигом на вектор ег веса один (с единицей только в г-й координате) всех его кодовых слов, и обозначим его К' = Я(£ег Множество К назовем г-компонентой кода С, если К (Я) = К(Я®ег), где К (Я) - объединение шаров радиуса 1 с центрами в векторах Я Легко понять, что код С' — (С\Я) и (Я@ег) также является совершенным кодом Будем говорить, что С' получен из кода С свитчингом Пусть а С I Подмножество М кода С назовем а-компонентой, если для всех г € а множество М является «-компонентой кода С Понятие а-компоненты оказалось плодотворным при построении новых классов совершенных кодов и исследовании свойств совершенных кодов Непересекающиеся а-компоненты можно разбивать на компоненты меньшей мощности по разным направлениям. Это позволяет сдвигать сначала компоненты меньшей мощности, варьируя направления, затем полученные а-компоненты сдвигать по

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

Используя этот метод, в 1996 г удалось впервые улучшить нижнюю оценку Ю Л Васильева [5]

2 2 ,

полученную в 1962 г. для числа различных совершенных двоичных кодов длины п, а именно, в параграфе 1 2 доказана

Теорема 2. Количество различных совершенных двоичных кодов длины п не менее, чем

а£1_,ов2(„+1) 2а|6_1082(„+1)

Оценка достигается применением метода а-компонент к коду Хэмминга Н длины п. Сначала разбиваем код Хэмминга Н на (г, з, /с)-компоненты, где {г,з, к) - произвольная тройка из системы троек Штейнера 5Т5(Я) кода Хэмминга Я, затем независимо каждую (г,у, /с)-компоненту - на г, ] или ^-компоненты Для построения класса кодов существенно использовались свойства 5Т5'(Я) При этом проведен анализ свойств подмножеств с фиксированной координатой системы троек Штейнера кода Хэмминга Именно он позволил итеративно препарировать код Хэмминга (сначала на подко-ды большой мощности, затем меньшей) и применить к нему серии локальных преобразований - свитчингов компонент

Фактически при этом была получена нижняя оценка числа совершенных кодов ранга не больше п—к^(те+1)+2 С помощью этого метода построения кодов впервые, после Ю Л Васильева, была доказана мощностным способом неэквивалентность предложенных кодов ранее известным кодам (первый фактор в формуле теоремы

2 получается при варьировании «-компонент, второй фактор получен за счет варьирования (г, j, £:)-компонент) Следует отметить, что прежде производились многочисленные, но безуспешные, попытки улучшить оценку Ю JI Васильева

Этот свитчинговый метод построения совершенных кодов и исследования их свойств дал возможность решить целую серию проблем, например, положительно решить проблему рангов и ядер (проблему Т Этциона и А Варди 1998 г), см [2], для всех п = 2к — 1, к > 5, позволил доказать существование разбиения множества всех двоичных векторов длины п на попарно неэквивалентные совершенные двоичные коды длины п с кодовым расстоянием 3, см [4], этот метод был развит для g-значных совершенных кодов, см [12], что позволило получить наилучшую на сегодняшний день нижнюю оценку числа таких кодов, этот подход лег в основу развития метода г-компонент (см описание ниже) Метод ск-компонент получил активное развитие в работах С А Малюгина [13, 30], Д С Кротова [11], С В Августиновича и Д С Кротова [29] В работе [13] С А Малюгин предложил сначала заменить произвольную к)-компоненту в коде Хэмминга Н на изоморфную (г, j, к)-компоненту, затем производить сдвиги г и j компонент Эта модификация позволила обогатить получаемый класс совершенных кодов по мощности Затем этот метод был развит Д. С Кротовым [11] также для совершенных кодов ранга опять таки не больше п — log(n + 1) + 2, дополнительно к методу «-компонент он применил известный обобщенный каскадный метод К Т Фелпса-1984 Впоследствии, применяя многократно к коду Хэмминга длины п метод «-компонент, С В Августинович и Д С. Кротов, см [29], получили лучшую на сегодняшний день нижнюю оценку числа различных совершенных кодов длины п неполного ранга, первые три наибольших фактора в этой оценке совпадают с нижней оценкой Д С Кротова

Обзор свитчинговых конструкций и нетривиальных свойств совершенных кодов, полученных с помощью свитчингового подхода, см в работах |43, 65, 77].

Здесь же, в главе 1, приводится метод сдвига непересекающихся

г-компонснт Этот подход, примененный к коду Хэмминга, позволил решить проблему Ф Хергерта 1985 г о существовании несистематических совершенных кодов Доказать требуемое свойство (например, построить несистематические коды или г-компоненты максимальной мощности, см ниже результаты главы 3), имея в запасе только локально повторяющуюся одинаковую картину, означает воссоздать структуру объекта, сформированного из локальных фрагментов, суметь "склеить", имея только частичную информацию, весь предмет в целом или суметь перестроить код, являющийся глобально и локально однородным (например, код Хэмминга) таким образом, чтобы результирующий код, став нелинейным, обладал требуемыми свойствами и в целом и для фрагментов

Для решения проблемы Ф Хергерта 1985 г. потребовались локальные преобразования кода Хэмминга длины п Код Хэмминга можно униформизовать - он является систематическим, т е в п-кубе найдется такая к^(п + 1)-мерная грань, что в каждой параллельной ей грани содержится в точности одно кодовое слово Никакой несистематический код невозможно униформизовать в указанном смысле, т е какая бы 1о§(п+1)-мерная грань ни была выбрана в тг-кубе, найдется грань, параллельная ей, не содержащая кодовых слов и, соответственно, найдется параллельная грань, содержащая не менее двух кодовых слов, Для построения несистематических кодов, как правило, необходим достаточный "простор" в пространстве между кодовыми словами, какового нет для совершенного кода в силу его плотной упакованности Отсутствие простора было компенсировано строго скорректированными свитчингами специальных подкодов кода Хэмминга, не нарушающими плотную упа-кованность результирующего кода Для этого был разработан метод свитчингов (последовательных сдвигов) '¿-компонент в коде Хэмминга длины п для различных г, г = 1,. ,,п, были сдвинуты п достаточно далеких г-компонент При этом существенно использовались свойства специального вида подсистем системы троек Штейнера кода Хэмминга и свойства систем троек Штейнера полученного кода Долгое время предполагалось, согласно гипотезы Ф Хергерта 1985 г, см [28], что все совершенные коды систематические

В главе 1 доказана

Теорема 3. Существует класс несистематических совершенных двоичных кодов длины п для любого п > 127, где п — 2к — 1

Существенную роль в проверке несистематичности построенного кода сыграл метод локального анализа окрестностей кодовых слов полученного совершенного кода - систем троек Штей-нера 6Т(х) кодовых слов (это множество таких троек (г,у, к), что х@у £ С, где вершине у € С отвечает т'ройка (г,у, к), здесь х € С) и в особенности БТ8(Н) кода Хэмминга Я Нетрудно видеть, что 5Т(х) = 5Г5(хф С) Определим систему троек кода С следующим образом

5Т(С) = У 5Г(х)

хес

Систему троек назовем полной, если она содержит всевозможные тройки координат Оказалось, что построенный код имеет полную систему троек.

Результаты этой главы получены совместно с С В Августино-вичем (см (54, 42, 55, 40])

Метод сдвига непересекающихся '¿-компонент различных направлений, безусловно, тесно связан с методом «-компонент, но не является его частным случаем, поскольку имеются ситуации, когда метод г-компонент применим, а метод а-компонент - нет, и наоборот Нетрудно видеть, что известный итеративный метод построения совершенных кодов Васильева является методом г-компонент, для этого достаточно в конструкции Васильева взять произвольный код Васильева в качестве кода предыдущей кодовой размерности, см также [65] Но всякий раз при решении конкретной задачи методом г-компонент требуются дополнительные условия, вследствие чего этот метод модифицируется в новую конструкцию кодов. Этот метод был независимо предложен Т Етционом и А Вар-ди [24] для перечисления спектра рангов нелинейных совершенных кодов, К Т Фелпсом и М ЛеВаном [33] для описания спектра размерностей ядер нелинейных совершенных кодов длины п > 15 Позднее этот метод был использован для построения класса совершенных кодов полного ранга с тривиальной группой автоморфизмов и, следовательно, с тривиальным ядром (см [57])

Метод построения несистематических кодов получил дальнейшее развитие в следующих работах были построены несистемати-

ческие коды для п < 127 К Т Фелпсом и М ЛеВаном в работе [34], А М Романовым для п — 15, С А Малюгиным в [15] опубликован результат о том, что минимальное количество «-компонент, которые необходимо сдвинуть в коде Хэмминга длины п для получения несистематического кода, не зависит от п и равно 7 К Т Фелпс и М ЛеВан [35], используя конструкцию [39] автора диссертации, доказали в 1999 г, что существуют совершенные коды длины 15, которые невозможно получить из кода Хэмминга методом свит-чинга. Следует отметить, что на сегодняшний день перечислены все совершенные и совершенные расширенные коды длин 15 и 16 соответственно, кроме кодов полного ранга, равного 15, см работы [9, 16] Обзор конструкций, а также нетривиальных свойств, присущих всем совершенным кодам, полученных методом свитчингов, см в [65, 77, 80]

Вторая глава посвящена разработке методов построения и исследования транзитивных кодов В этой главе приводится новых несколько новых свитчинговых методов построения бесконечных классов транзитивных двоичных кодов Будучи примененными к совершенным кодам, эти методы позволили (конструктивно) доказать, что существует не менее [к/2]2 неэквивалентных совершенных транзитивных кодов длины п — 2к — & > 4 Аналогичный результат справедлив для расширенных совершенных транзитивных кодов Кроме того, в этой главе приведен метод построения неэквивалентных ¿^-линейных кодов с параметрами классических кодов Рида-Маллера для любых допустимых параметров этих кодов

Транзитивные объекты, обладая богатым набором симметрий, играют важную роль как в теории кодирования, так и в комбинаторике, теории групп, теории графов Следует отметить, что по ряду свойств транзитивные коды близки к линейным кодам и, по всей видимости, по этой причине количество таких кодов невелико Однако для большинства оптимальных нелинейных кодов почти всегда можно найти транзитивные коды с такими же параметрами Например, двоичный образ (под действием отображения Грея) произвольного аддитивного кода является транзитивным кодом

Пусть В и С - произвольные двоичные коды длины п с кодовыми расстояниями <¿1 и ¿ч соответственно, где й% нечетно Пусть

А - произвольная функция из кода С в множество {0,1}, \х\ = XI + . + ж„(гшх12), где х — (х\, ,хп) € Еп Код

С2п+1 = {(ж, \х\ + Х(у), х + у) | х € В,у € С)

будем называть кодом Васильева, см [5] Он имеет длину 2п + 1, мощность |Б| \С\ и кодовое расстояние с1 =шт{2с?1 + 1, ¿2}

Теорема 4. Пусть С является произвольным транзитивным кодом с параметрами (п, |С|, ¿2)1 В - таким линейным кодом с параметрами [п, \В\, (¿1] с нечетным кодовым расстоянием (!.} , что для любого автоморфизма (у, ж) е АиЬ(С) выполняется 7Г е Бут (В) Тогда код Васильева С2п+г, для которого А = 0, является транзитивным

Множество

С2п = {(х,х + у) \хеВ,уеС}

называется кодом Плоткина длины 2п, он имеет мощность \В\ \С\ и кодовое расстояние с? =тш{2Й1, ¿2}

Нетрудно видеть, что расширение транзитивного кода с помощью общей проверки на четность всегда дает транзитивный код Обратное, вообще говоря, неверно Более того, известны примеры таких транзитивных кодов, что коды, полученные из них выкалыванием некоторой координаты, не являются транзитивными Следовательно, построение и исследование расширенных транзитивных кодов целесообразно проводить независимо от построения транзитивных кодов, не являющихся расширенными

Теорема 5. Пусть С является произвольным транзитивным кодом с параметрами (п, |С|, <¿2), В - таким линейным кодом с параметрами [п, \В\,6\], что для любого автоморфизма {у,тг) € А^ (С) выполняется тг 6 Бут (В) Тогда код Плоткина С2п тран-зитивен

Пусть Рь и Ст - произвольные двоичные коды длин í и т, соответственно с кодовыми расстояниями не менее 3, содержащие нулевые векторы. Пусть

Ж = (жп,®12, ,®1т,Я2Ъ т, -,Ха, . . ,®4т) £ Е*т

Функции рх(х) и р%{х), определенные следующим образом

Рх (ж) = (<Т1,о-2, ,аь) €Е\ р2(х) = (а[,а'2, ,а'т) £ Ет,

где сгг = и сг^ = хгз, называются обобщенными

проверками на ■четность Пусть / - произвольная функция из Р* в Ет Множество

Сп = {(ж,у + Р1(х)^ + Р2(х) + /(у)) | я е Еш,у € Р\г € (7го)

называется двоичным кодом Моллара длины п = + с кодовым расстоянием 3 (см [31]) В параграфе 2 2 3 главы 2 доказана следующая

Теорема 6. Пусть Рг и 6,тп - произвольные двоичные транзитивные коды длин £ и т соответственно Тогда код Моллара Сп, для которого / = От, является двоичным транзитивным кодом длины п — Ьт + 1 + т

Все три приведенных выше метода построения транзитивных двоичных кодов допускают построение совершенных транзитивных кодов длины п для любой допустимой длины разных рангов, начиная от минимально возможного, равного размерности кода Хэм-минга длины п до п - \ к^ (п + 1) Были получены следующие результаты

Теорема 7. Число неэквивалентных совершенных транзитивных кодов длины п — 2к — 1, & > 4 не менее [к/2_)2.

Теорема 8. Для любого п = 16г—1,2 > 1, и каждого натурального числа 5, удовлетворяющего 1 < § < \ к^ (п + 1), существует совершенный транзитивный код длины п ранга п — к^ (п + 1) + 6

Ранее было известно /2\ совершенных аддитивных кодов

длины п = 2к -1, см [22] (аналогично для расширенных совершенных аддитивных кодов, см [11]) Нетрудно показать, что все эти коды являются транзитивными и дистанционно инвариантными Малюгиным в 2004 г перечислены все совершенные транзитивные коды длины 15 из свитчингового класса кода Хэмминга длины 15 В работе [18] В Н Потаповым для каждого п было построено экспоненциальное число неэквивалентных расширенных транзитивных

совершенных кодов длины 4п ранга на единицу больше ранга кода Хэмминга такой же длины

Здесь же, в главе 2, в параграфе 2.4, приводится свитчинговый метод построения для каждого г, 0 < г < т, класса четверичных линейных кодов £КЛ4(г,т), двоичные образы которых под действием отображения Грея являются двоичными кодами с параметрами классических двоичных линейных кодов Рида-Маллера ДМ (г, т) порядка г Эти коды являются транзитивными и дистанционно-регулярными На сегодняшний день известно много хороших двоичных нелинейных кодов, представимых в качестве линейных над кольцом Ъ^, среди них следует отметить подклассы кодов Препараты, Кердока, Дельсарта-Гёталса, Геталса-Дельсарта, совершенных, Адамара, см [17, 26]

Напомним определение двоичного кода Рида-Маллера Пусть V = («х, , ьт) - вектор, пробегающий пространство Пусть г е {0,1, , т}, т > 1 Рассмотрим все булевы функции, равные многочленам, степень которых не превосходит г Двоичный код Рида-Маллера ЯМ (г, т) порядка г определяется как линейная оболочка множества всех векторов длины 2ТО, отвечающих значениям таких булевых функций В главе 2 доказан следующий результат

Теорема 9. Для любого г, г € {0,1,. , ш}, т > 1, существует четверичный линейный код с параметрами

(п = 2я»"1, 2\ <1 = 2т~г), где к = £ ( ™ ) , (1)

1=0 4 '

чей образ под действием отображения Грея является двоичным кодом с параметрами кода РидагМаллера ЯМ (г, т) порядка г При каждом г € {1,. ,т — 2}, т > 4, существуют неэквивалентные четверичные коды

Поскольку под действием отображения Грея двоичный образ любого из четверичных кодов является ¿^-линейным кодом, который является транзитивным кодом, то применение теоремы 5 дает бесконечный класс транзитивных двоичных кодов с параметрами кодов Рида-Маллера, которые уже могут не быть ¿¡^-линейными Результаты этой главы опубликованы в работах [76, 78, 47, 49]

Полное решение проблемы пересечения произвольных двух аддитивных, в частности четверичных (т е перечисление всех возможных мощностей кодов, равных пересечению аддитивных кодов), совершенных кодов было дано в работе [36] Были найдены верхняя и нижняя оценки этих мощностей, для любого допустимого числа между этими оценками были построены коды, дающие в пересечении код мощности, равной этому числу, описана аддитивная структура этих кодов

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

Изучение структуры, а также спектра мощностей г-компонент важно для решения основной проблемы теории совершенных кодов - проблемы их перечисления и классификации Известно, что верхняя и нижняя оценки числа т неразложимых (не разбивающихся на компоненты меньшей мощности) г-компонент произвольного совершенного кода длины га, п — 2е — 1, удовлетворяют неравенству

2 < т < 2й2й/(гг + 1).

Обе оценки точны, см [5, 19, 20]. Мощность неразложимых г-компонент варьируется от до 2п~1/(п + 1) Согласно [6, 19], для совершенных кодов длины п (для всех допустимых п > 7) существуют г-компоненты неэкстремальной мощности В работе [53] для любого га > 7 был предложен совершенный код длины п с г-компонентами различных структур и мощностей

В этой главе для каждого допустимого п предлагается класс совершенных кодов длины га с г-компонентами как максимально возможной, так и неэкстремальной мощностей В параграфе 3.2 доказана

Теорема 12. Существует класс совершенных кодов длины п с неразложимыми г-компонентами мощности

(к 4- 1)2п~к/(п + 1)

для каждого п = 2я - > 2 и к— 2Г ~ 1, где г = 2, ,5-1

Основным результатом этой главы является следующая

Теорема 13. Для каждого п = 2е—1, й > 3, существуют неизоморфные «-компоненты максимальной мощности, принадлежащие различным совершенным кодам длины та

При построении г-компонент, имеющих максимально возможную мощность, а также при построении г-компоиент, не являющихся минимальными, важным моментом явилось следующее обстоятельство оказалось существенным обеспечить связность этих множеств (как специальных компонент характеристического графа совершенного кода), их экстремальность и протяженность в та-кубс Факт связности также важен для выяснения того обстоятельства, что г-компонента неразложима, т е не разбивается на г-компоненты меньшей мощности На сегодняшний день в литературе не известны другие методы построения компонент совершенных кодов, кроме случая кодов длины 15 Для этого случая К Т Фелпс и М Д ЛеВан в [35] доказывают связность компонент совершенного кода длины 15, используя компьютер При доказательстве Теоремы 13 посредством метода локального анализа строятся классы кодов с протяженными связными г-компонентами для любой допустимой длины кода п > 7 Особенные трудности возникают при построении неизоморфных г-компонент максимальной мощности, равной половине размера всего совершенного кода, поскольку приходится, учитывая максимальность, "склеивать" большое количество локально одинаковых фрагментов подкодов, максимальное Хэммингово расстояние в которых равно только 6 Получение этой совокупности г-компонент еще раз убеждает в нетривиальности задачи перечисления всех совершенных кодов, а также в некоторой ограниченности возможностей свитчингового подхода, который эффективно работает для линейных компонент кода Хэм-минга, хотя в то же время существует много других более сложно устроенных компонент совершенных кодов

Следует также отметить, что методы построения обоих классов кодов с г-компонентами максимально возможной и неэкстремальной мощностей совпадают и представляют собой одновременное комбинирование каскадного [39] и свитчингового [5] методов построения совершенных кодов При этом снова используются структурные свойства систем троек Штейнера совершенных кодов Хэмминга, лежащих в основе каскадного метода построения результирующих кодов, предложенного автором диссертации в 1981 г, см [39] Использование метода локального анализа, с учетом свойств этих специальным образом выбранных систем троек Штейнера, позволило обеспечить связность г-компонент полученного кода, а также найти количестйо этих компонент

Эти результаты опубликованы в работах [59, 61, 63, 64, 71]

Вторая половина третьей главы посвящена (конструктивному) решению проблемы существования неизоморфных замощений не-ориентируемых поверхностей парами систем троек Штейнера порядка п для каждого п = 3 (mod 6) и половины классов вычетов п = 1 (mod 6) (известно, что системы троек Штейнера существуют при та = 1,3 (mod 6) Эта проблема тесно связана с широко известной в теории графов проблемой нитей, успешно решенной Г Ринге-лем и Дж У Т. Янгсом в 1968 г Проблема нитей касается исследования триангулированных вложений (необязательно двухцветных) полного графа в замкнутые поверхности В отличие от проблемы нитей, проблема существования неизоморфных замощений состоит в построении и перечислении триангулированных двухцветных вложений полного графа в замкнутые поверхности Сопоставим каждой тройке к) из системы троек Штейнера порядка п (кратко STS(n)) топологический треугольник с вершинами г, j и к Склеивание по одноименным сторонам треугольников, отвечающих специального вида паре непересекающихся STS{n) позволяет получить черно-белое замощение некоторой замкнутой поверхности Существование неизоморфных замощений ориентируемых поверхностей (сфер с ручками) было решено С П Боннонгтоном с соавторами, см [21].

Теорема 14. Для каждого п = 3 (mod 6) доказано существование неизоморфных замощений неориентируемых поверхно-

стей (сфер с пленками Мебиуса) парами систем троек Штейнера порядка п

Теорема 15. Для любого п = 3 (mod 6), п > 19 существует не менее 2(п~1)(гг~3)/6 неизоморфных неориентируемых замощений порядка Зп — 2

Следствие. Существуют неэквивалентные замощения неори-ентируемой замкнутой поверхности (сферы с (тг — 3)(п — 4)/6 пленками Мебиуса) посредством пар систем троек Штейнера порядка п для половины классов вычетов п = 1 (mod 6)

Следует отметить идейную аналогию и параллелизм результата о замощениях и основного результата главы 3 о построении неизоморфных г-компонент максимально возможной мощности В обоих ситуациях имеем пару нетривиальных структур, которые в объединении дают совершенную структуру (в случае замкнутых поверхностей также имеем в некотором смысле "совершенность", а именно сферу с ручками Мебиуса, которая не является псевдосферой, т е не получается склеиванием нескольких сфер с ручками Мебиуса и (или) отождествлением некоторого количества точек поверхности), в обоих ситуациях необходимо обеспечить связность характеристических графов специального вида и, наконец, в основе каждой из этих конструкций лежит пара непересекающихся систем троек Штейнера специального вида (следует отметить, что пары STS, использованные для построения максимальных г-компонент и замощений различны). Кроме того, в обоих случаях для построения этих совершенных структур использовался метод локального анализа, а именно, исследовались свойства локальной структуры каждого из этих объектов (в случае замощений таким свойством является свойство цикличности, которое должно выполняться для каждого элемента г € N — {1,2, ,п} обоих систем троек Штейнера порядка п), затем склеивание этих локальных фрагментов позволило построить объекты в целом в одном случае совершенных кодов с максимально мощными г-компонентами, в другом -"совершенных" замощений двумерных многообразий

Четвертая глава настоящей диссертации посвящена вопросам метрической жесткости широкого класса двоичных кодов и неко-

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

Код С называется метрически жестким, если каждая изомет-рия ф С Fn по отношению к метрике Хэмминга расширяема до изометрии всего пространства Fn (напомним, что здесь Fn -векторное пространство над полем Галуа GF(q) характеристики

q >2)

В 1994 г С В Августиновичем, см [1], доказано, что все совершенные двоичные коды длины п > 15 являются метрически жесткими Два кода С\, Сг слабо изометричны, если существует такое отображение J С% —* что равенство rf(x,y) = 3,х,у € С\, справедливо тогда и только тогда, когда d(J(x), j(у)) = 3. В 1998 г С В. Августиновичем, см [1], доказано, что любые два слабо изометричных совершенных двоичных кода эквивалентны

Пусть R - произвольное метрическое пространство с достаточно богатой группой автоморфизмов Два метрических подпространства Ri и i?2 из R эквивалентны, если существует автоморфизм I из группы автоморфизмов пространства R такой, что I{R\) = R2 Достаточно часто все проблемы относительно метрических пространств изучаются с точностью до эквивалентности Рассмотрим ситуацию, когда важна только структура метрического подпространства, но не способ, как метрическое подпространство вложено в пространство R Исследование такой ситуации, имея ввиду только эквивалентность, крайне затруднительно Подход с учетом изометрии позволяет преодолевать все возникающие трудности. Описанная ситуация имеет место как в геометрии (см [27]), так и в дискретной математике (см [1, 10, 58, 62])

Код из Fn над GF(q) называется (п, к) MDS-кодом (maximal-distance separable - максимально-дистанционно разделимым), если его параметры достигают границы Синглтона d = п — k + 1, где п - длина кодового слова, к = log? М - размерность кода, М -мощность кода, d - кодовое расстояние кода С.

В этой главе методом (г, a)—star (выявлением локально-жестких

фрагментов кодов), предложенным в диссертации, доказаны следующие утверждения

Теорема 19. Все д-значные (п,п —1) МОЭ-коды являются метрически жесткими за исключением двух кодов длины 3 и одного кода длины 4

Теорема 20. Все совершенные коды с кодовым расстоянием 3 над С?.Р(д) являются метрически жесткими за исключением двоичного кода Хэмминга длины 7 и троичного кода Хэмминга длины 4.

В параграфе 4 1 доказано, что двоичный четно-весовой код длины п является метрически жестким тогда и только тогда, когда п ф 4 В параграфе 4 2 выяснено, что д-значные (д, 2) и (д + 1,2) МБв-коды метрически жесткие, если и только если ц — 2

Метрическую жесткость кодов удается доказать, исследуя локально-жесткие подкоды д-значных совершенных кодов и МВБ-кодов Эти подкоды являются в некотором смысле аналогами подмножеств систем троек Штейнера совершенного двоичного кода с фиксированной координатой

Определим 2-(п,к,Х) -схему на множестве N как систему к-элементных подмножеств (блоков) из N такую, что каждое неупорядоченное двухэлементное подмножество из N содержится в точности в А блоках схемы

Теорема 21. При п > кА произвольный приведенный двоичный код, содержащий 2-(п, к, А)-схему, является метрически жестким кодом

Класс таких кодов включает все семейства равномерно упакованных кодов достаточно большой длины, удовлетворяющих условию й — р> 2, где (I - кодовое расстояние и р- радиус покрытия Известно, что множество равномерно упакованных кодов содержит (<1 — р)-схемы (и, следовательно, 2-схемы) и включает БЧХ-коды с расстоянием 5 и 7, коды Препараты, коды Геталса с расстоянием 7, расширенные совершенные коды.

Последняя теорема получена совместно с С В. Августинови-чем, см [46], остальные результаты этой главы получены совместно с С В Августиновичем, В Хайзе и Т Хонольдом, см [58, 62]

Пятая глава посвящена исследованию групп автоморфизмов совершенных кодов и систем троек Штейнера Известный результат К Т Фелпса [32] о том, что каждая конечная группа изоморфна группе перестановочных автоморфизмов некоторого совершенного кода к сожалению не позволяет прояснить строение полной группы автоморфизмов произвольного совершенного кода длины п = 2к — 1, А; > 3 и оценить ее порядок, поскольку полная группа автоморфизмов содержит группу симметрий только в качестве подгруппы Систематическое исследование групп автоморфизмов совершенных кодов было начато в работах [57, 30], до этого изучались только группы симметрий кодов, что оправдано лишь для линейных двоичных кодов Автором диссертации (совместно с С В Ав-густиновичем), см [57], было доказано (конструктивно) существование класса совершенных двоичных кодов с тривиальной группой автоморфизмов для любого п = 2к—1, п > 127 Эти коды оказались несистематическими С А Малюгин [30] доказал существование класса систематических кодов с тривиальной группой автоморфизмов для любого п = 2к — 1, п > 31 Для кодов длины 15 вопрос существования таких кодов пока остается открытым

Хорошо известно, что группы симметрий кода Хэмминга Я длины п и расширенного кода Хэмминга длины п + 1 (с одной проверочной координатой) изоморфны полной линейной (?£(1о§(п+1), 2) и полной аффинной GA(log(n ~Ь 1)) группам соответственно Для кода Хэмминга Н длины п справедливо

\АиЬ{Н)| = |ОЬ(1о§(п + 1),2) х Кег(Н)\ = 2П-ю8(п+1)п(п _ 1)(п _ щп _ 7) _ (п _ (п _ 1)/2).

Порядок группы автоморфизмов совершенного кода оказался тесно связанным с порядком группы автоморфизмов его системы троек Штейнера В 2000 г, в работах [67, 68, 44], автором диссертации совместно с С Т Топаловой было доказано, что порядок группы автоморфизмов произвольного нелинейного совершенного двоичного кода с расстоянием 3 не превосходит порядка группы автоморфизмов кода Хэмминга той же длины Для получения этого результата потребовалось развить комбинаторную технику для получения аналогичного результата для порядков групп автоморфизмов систем троек Штейнера Там же была получена верх-

няя оценка порядка группы автоморфизмов произвольной системы Штейнера + 1,п)

Развивая далее этот подход, была доказана в параграфе 5.2 следующая теорема

Теорема 23. Если порядок группы автоморфизмов произвольной системы троек Штейнера порядка п равен порядку полной линейной группы СЬ(^(п + 1), 2), то эта система хэммингова и с точностью до изоморфизма единственна

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

Теорема 24, Порядок группы автоморфизмов произвольного совершенного двоичного кода длины п меньше порядка группы автоморфизмов кода Хэмминга той же длины

Аналогичная теорема верна для групп автоморфизмов расширенных совершенных кодов

Результаты опубликованы в [67, 44, 45] и получены совместно с С Т Топаловой

Аналогичный результат был независимо получен С А Малюгиным в работе [14]

Исследования групп автоморфизмов были продолжены в работе [3]

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

В этой главе приводится нижняя оценка, см [77, 48] (лучшая на сегодняшний день) числа различных разбиений пространства Еп на совершенные коды, полученная свитчинговым методом

Теорема 25. Для любого допустимого п > 31 число различных разбиений Рп пространства Еп на совершенные коды длины п удовлетворяет неравенству

Р„ > 22(-1)/2

Рассмотрим два произвольных разбиения п-куба Еп на совершенные расширенные двоичные коды и их матрицу пересечений Она дает мощности попарных пересечений кодов из этих разбиений В этой главе производится подсчет снизу и сверху количества различных матриц пересечений, полученных из произвольных двух разбиений п-куба Еп на совершенные расширенные двоичные коды

Для получения оценок числа различных и неэквивалентных матриц пересечений, полученных из произвольных двух разбиений п-куба Еп на совершенные расширенные двоичные коды рассматриваются сначала различные разбиения Еп, которые используются для построения двух разбиений Е2п (здесь п = 2к) При этом используется и развивается далее с использованием свитчингов латинских квадратов каскадный способ построения совершенных расширенных кодов и разбиений из [39]

Для получения нижней оценки числа различных матриц пересечений двух разбиений Еп на совершенные расширенные двоичные коды потребовалось оценить число различных матриц пересечений латинских квадратов Для этой цели посредством свитчингов (локальных перестроек) подматриц порядка 2x2 внутри пары латинских квадратов специального вида (т е. снова используя метод локального анализа) было сконструировано мощное множество различных матриц пересечения двух латинских квадратов. В параграфе 6 4 были доказаны следующие теоремы

Теорема 29. Для любого п — 2к > 8, число различных матриц пересечения двух латинских квадратов порядка п не меньше чем 2П"

Теорема 30. Для п = 2к,к > 2, число различных матриц пересечений разбиений Еп на совершенные расширенные двоичные коды не меньше 2сп , где с - положительная константа.

Теорема 31. Для п — 2к, к > 3, число неэквивалентных матриц пересечений разбиений Еп на совершенные расширенные двоичные коды не меньше 2е'п2, где с! - положительная константа

В параграфе 6.5 доказано, что число неэквивалентных матриц пересечений разбиений Еп на совершенные расширенные двоичные коды не больше 2е"™ , где п достаточно велико и с" - положительная константа

Проблема построения разбиений Еп рассматривалась также в ряде других работ, например, Т. Етционом и А Варди в работе [25], а также в работах Ж Рифы, К. Боргеса, М. Виллануевой, К. Фернандес

Результаты по исследованию матриц пересечений разбиений пространства на совершенные расширенные двоичные коды были получены совместно с С В Августиновичем и А Лобстейном [70, 72]

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

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

[1] Августинович С. В. Комбинаторные и метрические свойства совершенных кодов и раскрасок, Канд дисс., Новосибирск, 2000. 33 с

[2] Августинович С В, Соловьева Ф И, Хеден У О проблеме рангов и ядер совершенных кодов // Пробл передачи информ 2003 Т 39. N 4. С 341-345

[3] Августинович С В, Соловьева Ф. И, Хеден У. О структуре группы симметрий кодов Васильева // Пробл передачи информ 2005 Т. 41 N 2. С 105-112

[4] Августинович С. В, Соловьева Ф И, Хеден У О разбиениях n-куба на неэквивалентные совершенные коды // Пробл передачи информ 2007. Т. 43 N 4. С 45-50.

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

[6] Васильев Ю. Л, Соловьева Ф И Кодообразующие факторизации п-мерного единичного куба и совершенных двоичных кодов // Пробл передачи информ 1997 Т 33 Вып 1. С 64-74

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

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

[9] Зиновьев В А., Зиновьев Д В Двоичные расширенные совершенные коды длины 16 ранга 14 // Пробл передачи информ. 2006. Т 42 N 2 С 63-80

[10] Кабатянский Г. А., Левенштейн В И. О границах для упаковок на сфере и в пространстве // Пробл передачи информ. 1978 Т 14 N 1. С. 1-17

[11] Кротов Д С Конструкции плотно упакованных кодов и нижние оценки их числа, Канд дисс , Новосибирск, 2000. 64 с

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

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

[14] Малюгин CAO порядке группы автоморфизмов совершенных двоичных кодов // Дискрет, анализ и исслед операций Сер 1 2000 Т 7. N. 4. С. 91-100

[15] Малюгин С. А Несистематические совершенные двоичные коды // Дискрет анализ и исслед операций Сер 1 2001. Т 8 N

1 С 55-76

[16] Малюгин С А О перечислении неэквивалентных совершенных двоичных кодов длины 15 и ранга 15 // Дискрет анализ и исслед операций. Сер 1 2006 Т. 13. N. 1 С 77-98

[17] Нечаев А. А. Коды Кердока в циклической форме // Дискрета. Матем 1989 V 1 № 4 Р 123-139.

[18] Потапов В.Н О нижней оценке числа транзитивных совершенных кодов // Дискрет анализ и исслед операций Сер 1 2006 Т 13. N. 4. С 49-59.

[19] Соловьева ФИ. О факторизации кодообразующих д.н.ф. // Методы дискретного анализа в исследовании функциональных систем Новосибирск- Ин-т математики СО АН СССР 1988 Вып 47 С 66-88

[20] Соловьева Ф И Точные границы связности кодообразующих д н ф , Препринт N 10 Новосибирск Институт математики СО РАН, 1990. С. 15

[21] Bonmgton С Р, Grannell М J, Griggs Т S, Sir an J Exponential Families of Non-Isomorphic Triangulations of Complete Graphs //J. Combm. Theory. Ser B. 2000 V 78 №

2 P 169-184

[22] Borges J, Rifa J A characterization of 1-perfect additive codes // IEEE Trans. Inform Theory 1999 V. 45 № 5. P 1688-1697

[23] Cohen G, Honkala I, Lobstem A , Litsyn S Covering codes, Elsevier, 1998

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

[25] Etzion T, Vardy A On perfect codes and tilings problems and solutions /'/ SIAM J. Discrete Math 1998 V. 11 N. 2 P 205-223

|26l Hammons A R., Kumar P V , Calderbank A R , Sloane N J A and Sole P , "The ^-linearity of Kerdock, Preparata, Goethals and related codes," IEEE Trans Inform. Theory, V. 40 P. 301-319, 1994

[27] Herburt I, Ungar S Rigid sets of dimension n — 1 m Rn // Geom Dedicata 1999 V. 76. P 331-339

[28] Hergert F Algebraische Methoden fur Nichtlineare Codes, Thesis Darmstadt 1985

[29] Krotov D S, Avgustmovich S V On the number of 1-perfect binary codes a lower bound // IEEE Trans. Inform Theory, V 54. N 4 2008. P. 1760-1765

[30] Malyugm S A Perfect codes with trivial automorphism group, Proc Second Int Workshop on Optimal Codes and Related Topics Sozopol, Bulgaria June 1998 P 163-167

[31] Mollard M A generalized parity function and its use m the construction of perfect codes // SIAM J Alg Disc Meth 1986 V. 7. N 1 P. 113-115

[32] Phelps K T Every finite group is the automorphism group of some perfect code // J Combm Theory, series A 1986 V 43 N 1. P 45-51

[33] Phelps K T., LeVan M J Kernels of nonlinear Hamming codes // Des., Codes and Cryptography 1995. V 6 P. 247-257

[34] Phelps K T, LeVan M J Non-systematic perfect codes // SIAM Journal of Discrete Mathematics 1999 V. 12 N. 1 P 27-34

[35] Phelps K T, LeVan M J Switching equivalence classes of perfect codes /1 Des , Codes and Cryptogr 1999. V. 16 N 2 P 179-184

[36] Rifa J, Solov'eva F.I., Villanueva M On the intersection of additive perfect codes // IEEE TVans Inform Theory, V 54 N 3 2008. P. 1346-1356

[37] Shapiro G S, Slotmk D L On the mathematical theory of error correcting codes // IBM J Res and Devel 1959 V 3 N 1 P 25-34 (Русский перевод-Шапиро Г С, Злотник Д Л К математической теории кодов с исправлением ошибок // Кибернетический сб М Изд-во иностр лит, 1962 Вып 5 С 7-32 )

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

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

[39] Соловьева ФИ. О двоичных негрупповых кодах // Методы дискретного анализа в изучении булевых функций и графов Новосибирск Ин-т математики СО АН СССР 1981 Вып 37 С 65-76

[40] Августинович С В , Соловьева ФИО несистематических совершенных двоичных кодах // Пробл передачи информ 1996 Т 32 Вып 3 С 47-50

[41] Соловьева Ф И Системы троек Штейнера и проблема нитей, Второй Сибирский конгресс по прикладной и индустриальной математике (ИНПРИМ-96) Новосибирск, 25-30 июня, 1996 С 125-126

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

[43] Августинович С В, Соловьева Ф И Новые конструкции и свойства совершенных кодов, Труды Междунар. конференции по дискретному анализу и исследованию операций, Новосибирск, Россия, Июнь 2000 С 5—10

[44] Соловьева Ф. И., Топалова СТО группах автоморфизмов совершенных двоичных кодов и систем троек Штейнера // Пробл передачи информ. 2000 Т. 36 Вып 4 С 53-58

[45] Соловьева Ф И., Топалова С Т Совершенные двоичные коды и системы троек Штейнера с максимальными порядками групп автоморфизмов // Дискрет анализ и исслед. операций. Сер 1 2000 Т 7 N 4 С 101-110

[46] Августинович С В, Соловьева ФИО метрической жесткости двоичных кодов // Пробл передачи информ 2003 Т 39. Вып 2 С 63-68

[47] Соловьева ФИО построении транзитивных кодов // Пробл передачи информ 2005 Т. 41 Вып 3 С 23-31

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

[49] Соловьева ФИО Z^-линейных кодах с параметрами кодов Рида-Маллера//Пробл передачи информ 2007. Т. 43 Вып 1 С 41-47

[50] Соловьева Ф И Замощения неориентируемых поверхностей системами троек Штейнера // Пробл передачи информ 2007 Т 43 Вып 3 С 54-65

[51] Соловьева Ф И. Построение замощений неориентируемых поверхностей системами троек Штейнера, Труды конференции "Математика в современном мире", 17-23 сентября 2007. Новосибирск, С 286-287

[52] Solov'eva FI.A combinatorial construction of perfect binary codes, Proc of Fourth Int Workshop on Algebraic and Comb Coding Theory Novgorod, Russia September 1994 P 171-174

[53] Avgustmovich S. V, Solov 'eva F. I On projections of perfect binary codes, Proc Seventh Jomt Swedish-Russian Workshop on Information Theory, St -Petersburg, Russia June 1995 P 25-26

[54] Avgustmovich S V, Solov'eva F I Construction of perfect binary codes by sequential translations of the г-components, Proc. of Fifth Int Workshop on Algebraic and Comb Coding Theory Sozopol, Bulgaria June 1996 P 9-14.

[55] Avgustmovich S V, Solov 'eva F I Existence of nonsystematic perfect binary codes, Proc of Fifth Int Workshop on Algebr. and Comb Coding Theory, Sozopol, Bulgaria, June 1996 P 15-19

[56] Avgustmovich S V, Solov'eva F I Structural properties of perfect binary codes, Proc of Int Symp on Inform Theory, Ulm, Germany. 1997 P 456

[57] Avgustmovich S V, Solov'eva F I Perfect binary codes with trivial automorphism group, Proc of Int Workshop on Information Theory, Killarney, Ireland. June 1998 P. 114-115

[58] Solov'eva F I, Avgustmovich S V, Honold T, Heise W On the extendabihty of code isometries // J of Geometry. 1998 V 61 P 3-16

[59] Solov'eva FI On components of perfect binary codes, Preprint 98-041, Universität Bielefeld, Sonderforschungsbereich 343 Discrete Structuren m der Mathematik 1998 8 p

[60] Solov'eva F I Constructions of perfect binary codes, Preprint 98042, Universität Bielefeld, Sonderforschungsbereich 343 Discrete Structuren m der Mathematik 1998 12 p

[61] Solov'eva F I Cardinality of i-components of perfect codes, Proc of Siberian conference on Operation Research, Russia, Novosibirsk 1998 P 139

[62] Solov'eva F I, Avgustmovich S V, Honold T, Heise W Metrically rigid codes, Proc Sixth Int. Workshop on Algebraic and Comb Coding Theory Pskov, Russia September 1998. P 215-219

[63] Solov 'eva F I Components on perfect binary codes, Proc of 1998 Optimal codes Workshop, Sozopol Bulgaria 1998. P 188-192

[64] Solov'eva F I Perfect binary codes components, Proc of Workshop on Coding and Cryptography WCC'99 Pans, France January 3999 P. 29-32

[65] Solov'eva F.I Switchings and perfect codes, Numbers, Information and Complexity, Kluwer Academic Publisher 2000 311-314

[66] Solov'eva F I Perfect binary codes bounds and properties // Discrete Math. 2000 V 213 P 283-290

[67] Solov'eva F I, Topalova ST On the automorphism groups of perfect binary codes, Proc Seventh Int Workshop on Algebr and Comb Coding Theory Bansko, Bulgaria June 2000 P 283-287

[68] Solov'eva F I, Topalova S T On the automorphism groups of Sterner Systems, Proc of Int Workshop on Discrete Analiz and Operation Research, Novosibirsk, Russia June 2000 P 90

[69] Avgustmovich S. V, Solov'eva F I On the rigidity of binary codes, Proc of Int Conference "Geometry and applications", Novosibirsk, Russia March 2000 P 16-17

[70] Avgustmovich S V, Lobstem A , Solov'eva F I Partitions by perfect binary codes, using concatenation and latin qsuares, Proc Seventh Int Workshop on Algebraic and Comb. Coding Theory Bansko, Bulgaria June 2000 P 45-50.

[71] Solov'eva F I Structure of t-components of perfect binary codes // Discrete Appl Math 2001 V 111 N 1-2 P 189-197.

[72] Avgustmovich S V, Lobstem A, Solov'eva F I Intersection matrices for partitions by binary perfect codes // IEEE Trans Inform Theory 2001 V 47 N 4 P 1621-1624

[73] Solov'eva F I., Avgustmovich, S V On the metrical rigidity of binary codes, Proc of Workshop on Coding and Cryptography WCC'2001, Paris, Prance January 2001 P 35-42

[74] Solov'eva F I Automorphism groups of perfect codes, Proc of EWM Intern Workshop on Groups and Graphs, Varna, Bulgaria August 2002 P. 95-100

[75] Solov'eva F I. Tilings of closed surfaces by Sterner triple systems, Proc of Workshop on Coding and Ciyptogr WCC'2003, Veisaille, Prance. March 2003 P 425-431

[76] Solov'eva F I On transitive codes, Proc of Int Workshop on Discrete Analysis and Operation Research, Novosibirsk, Russia June 2004 P 99.

[77] Solov'eva F I On perfect codes and related topics, Com2Mac Lecture Note Series 13, Pohang 2004 80 p

[78] Solov'eva F I Some constructions of transitive codes, Proc of Int Workshop on Optimal codes and related topics Pamporovo, Bulgaria June 2005 P 254-260

[79] Solov'eva F I Designs and perfect codes // Lecture Notes in Computer Science, V 4123 November 2006 P 1104-1105

[80] Solov'eva FI On perfect binary codes // Discrete Appl Math , to appear

Соловьева Фаина Ивановна

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

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

Подписано в печать 02 04 08 Формат 60x84 1/16 Уел печ л 2,44 Уч -изд л 2,0 Тираж 120 экз Заказ N 58

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

Введение

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 Метод построения Z4-линeйныx кодов Рида-Маллера

3 Структура ¿-компонент совершенных двоичных кодов

3.1 Постановка задачи, основные идеи построения г-компонент 86 3.1.1 Конструкции г-компонент.

3.2 Применение метода локального анализа к построению замощений.

3.2.1 Обзор результатов о замощениях поверхностей системами троек Штейнера.

3.2.2 Построение замощений.

3.2.3 Существование неизоморфных замощений

4 Метрическая жесткость кодов

4.1 Двоичный,четно-весовой код.

4.2 g-значные (q, 2) и (g + 1, 2) MDS-коды.

4.3 (n, п - 1) MDS-коды.

4.4 Метрическая жесткость совершенных g-значных кодов

4.5 Метрическая жесткость двоичных кодов, содержащих 2-схемы.

5 Группы автоморфизмов совершенных двоичных кодов и систем троек Штейнера

5.1 Системы троек Штейнера с группой автоморфизмов максимального порядка.

5.2 Совершенные двоичные коды с группой автоморфизмов максимального порядка.

6 Разбиения совершенных двоичных кодов

6.1 Нижняя оценка числа разбиений Еп на совершенные двоичные коды.

6.2 Матрицы пересечений, отвечающие разбиениям совершенных двоичных кодов.

6.2.1 Разбиения, использующие каскадирование и латинские квадраты, общий случай

6.2.2 Разбиения, использующие каскадирование и латинские квадраты, случай т = 2.

6.2.3 Случай диагональных матриц пересечения.

6.2.4 Верхняя оценка числа неэквивалентных матриц пересечений

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

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

Актуальность разработки новых методов построения кодов и исследования их свойств (как известных кодов, так и построения новых кодов) в теории кодирования диктуется, прежде всего, задачами поиска кодов и такого их задания, которое позволит разработать более эффективные алгоритмы кодирования и декодирования с целью экономной передачи информации по каналам связи, а также применением в криптографии. На практике зачастую используются линейные коды. Однако в последнее время в теории кодирования все большую актуальность приобретают нелинейные коды, например, транзитивные коды, среди них Хч^-линейные, ^-линейные, их конструирование, классификация. Актуальность построения новых классов нелинейных кодов и изучения их свойств мотивирована следующими причинами. Во-первых, классы нелинейных кодов намного мощнее классов линейных кодов с теми же параметрами и, кроме того, часто линейный д-значный код с заданными параметрами единствен (как, например, код Хэмминга, двоичные коды Рида-Маллера). Во-вторых, за последние два десятилетия среди нелинейных кодов были открыты классы ¿^-линейных кодов, среди которых имеется много неэквивалентных кодов с фиксированными параметрами (например, коды Препараты, коды Кердока, коды с параметрами кодов Рида-Маллера). Кроме того, некоторые нелинейные коды имеют мощность, большую мощности линейных кодов той же длины и с тем же кодовым расстоянием (например, коды Препараты в два раза мощнее кодов БЧХ той же длины с расстоянием 5). Последние два обстоятельства служат весомым основанием для поиска применения таких нелинейных кодов в криптографии в кодовых криптосистемах с открытыми ключами. Таким образом для нелинейных кодов возникают естественные математические (комбинаторные) задачи существования и описания (классификации) кодов с данными параметрами. Эти проблемы предусматривают, прежде всего, разработку методов построения кодов, а также методов исследования свойств классов кодов с заданными характеристиками (параметрами или свойствами).

Актуальность исследования совершенных кодов обусловлена следующими обстоятельствами. Совершенные коды представляют собой один из наиболее важных (как своими свойствами, так и методами, разработанными для их построения и исследования) предметов теории кодов, корректирующих ошибки. Код над полем Галуа GF{q) называется совершенным, если совокупность шаров одного радиуса, окружающих кодовые слова, задает разбиение пространства. Теория совершенных кодов на сегодняшний день является глубоко разработанной наукой, интенсивно развиваемой как в России, так и за рубежом. Несмотря на значительные усилия целого ряда исследователей, остается открытым множество проблем, связанных с совершенными кодами. По-прежнему остается нерешенной основная проблема построения и перечисления совершенных g-значных кодов для q - степеней простого, не найдена классификация даже двоичных совершенных кодов длины 15, недостаточно изучены коды полного ранга, нет полного описания групп автоморфизмов совершенных кодов, структуры их г-компонент. Последние три проблемы непосредственно связаны с основной проблемой для совершенных кодов - проблемой Pix классификации. Известно, что совершенные коды обладают целым рядом регулярных свойств (см. их описание ниже при описании результатов диссертации). Плотная унакованность совершенных кодов предопределяет их оптимальность, т. е. максимальность мощности кода при заданной длине кода и кодовом расстоянии. Проблема упаковки шарами одного радиуса - задача, важная как с точки зрения самой теории кодирования, так и с точки зрения целого ряда других математических дисциплин: комбинаторного анализа, теории групп, теории графов, комбинаторной топологии, геометрии, криптологии, синтеза схем. Кроме того, совершенные коды представляют собой удобный модельный объект для развития подходов к построению и исследованию кодов с большими кодовыми расстояниями - многие из методов построения и изучения свойств совершенных двоичных кодов уже применены и успешно развиваются для кодов с другими параметрами, например, для равномерно упакованных кодов, кодов с параметрами кодов Рида-Маллера, четверичных кодов с метрикой Ли, <?-значных, д > 2, кодов с метрикой Хэмминга, диаметральных совершенных кодов с метрикой Джонсона, для совершенных раскрасок, центрированных функций. Много усилий исследователей посвящено за последние десять лет разработке методов построения и методов исследования свойств совершенных кодов.

К числу открытых проблем (полное или частичное решение которых приводится в данной работе) относились: разработка прямых комбинаторных методов построения и исследования свойств нелинейных двоичных кодов, разработка методов построения транзитивных кодов, исследование метрической жесткости кодов, проблема классификации совершенных кодов, проблема Ф. Хергерта о существовании несистематических совершенных кодов, выяснение структуры ¿-компонент таких кодов и строения группы автоморфизмов произвольного совершенного кода, проблема Т. Этциона и А. Варди построения и исследования разбиений д-значного п-мерного куба на совершенные коды.

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

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

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

1. В диссертации предложен новый комбинаторный (свитчинговый) метод построения и исследования нелинейных кодов, названный методом а-компонент. Этот метод применен к совершенным двоичным кодам и позволил сделать существенное продвижение в решении проблемы классификации совершенных двоичных кодов малых рангов. Используя его, удалось улучшить, впервые после более чем 30-летнего перерыва, нижнюю оценку Ю. Л. Васильева [17] для числа неэквивалентных совершенных кодов. Метод позволил получить дважды экспоненциальный по мощности класс неэквивалентных совершенных двоичных кодов. С помощью этого метода был решен ряд проблем для совершенных кодов.

2. Разработаны новые свитчинговые методы построения транзитивных двоичных кодов. Предложен новый метод построения неэквивалентных четверичных кодов. Двоичные образы этих кодов под действием отображения Грея имеют параметры классических двоичных линейных кодов Рида-Маллера и обладают такими регулярными свойствами, как транзитивность, дистанционная регулярность. Построен новый класс неэквивалентных совершенных транзитивных кодов длины п = 2k — 1, к > 4, таких кодов оказалось не менее [к/2J2. Аналогичный результат верен для расширенных совершенных транзитивных кодов.

3. Новым является комбинаторный метод локального анализа, разработанный для исследования структуры компонент двоичных совершенных кодов, а именно строения ¿-компонент характеристического графа произвольного совершенного кода. Этот метод позволил решить проблему существования неэквивалентных ¿-компонент максимальной мощности и построить новые классы кодов с максимальными по мощности связными ¿-компонентами для любой допустимой длины кода п > 7. Посредством этого метода была решена проблема построения неизоморфных замощений (сфер с пленками Мебиуса) с помощью специальных пар систем троек Штейнера порядка п для каждого п ^ 3 (mod 6).

4. Решена проблема Ф. Хергерта - для каждого допз^стимого п > 127 доказано (конструктивно) существование класса несистематических совершенных двоичных кодов. Для этой цели был развит метод свитчин-га компонент минимальной мощности, названный методом г-компонент (независимо такой подход был применен немного раньше Т. Этционом и А. Варди в [87], а также К. Т. Фелпсом и М. ЛеВаном в [121] для решения других проблем).

5. Предложен новый метод (г, а)^аг (выявление локально-жестких фрагментов кодов), который также является методом локального анализа, для исследования метрической жесткости кодов. Посредством этого метода полностью выяснен вопрос о метрической жесткости д-значных совершенных кодов, д > 2, и некоторых классов МОБ-кодов. Доказано, что при п > к4 произвольный приведенный, т. е. содержащий нулевой вектор, двоичный код длины п, содержащий 2-(п, к, А)-схему, является метрически жестким кодом.

6. Предложен новый комбинаторный метод (который также можно отнести к методу локального анализа) исследования группы автоморфизмов произвольного совершенного двоичного кода, основанный на тех фактах, что каждое кодовое слово совершенного кода связано со своей системой троек Штейнера, характеристический граф совершенного кода связен, код представляет собой замощение всех своих систем троек Штейнера - локальных фрагментов. Для этого потребовался также комбинаторный подход к изучению строения группы автоморфизмов кодовых систем троек Штейнера, что представляет самостоятельный интерес.

7. Предложены новые комбинаторные (каскадные и свитчинговые) способы построения богатых классов разбиений Хэммингова пространства на совершенные коды и совершенные расширенные коды.

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

Апробация работы. Все результаты работы прошли апробацию на следующих международных конференциях: на конференциях по алгебраической и комбинаторной теории кодирования АССТ-1У (Новгород, 1994 г.), АССТ-У (Созополь, Болгария, 1996 г.), АССТ-У1 (Псков, 1998 г.), АССТ-УП (Банско, Болгария, 2000 г.); АССТ-УШ (Царское Село, 2002), АССТ-1Х (Кранево, 2004), АССТ-Х (Звенигород, 2006); па ми-нисеминаре по упаковкам и покрытиям (Варшава, Польша, 1996 г.); на международном симпозиуме по теории информации (Ульм, Германия, 1997 г.); на международной конференции по теории информации (Кил-ларни, Ирландия, 1998 г.); на международном симпозиуме, посвященном 60-летию профессора Р. Альсведе (Билефельд, Германия, 1998 г.); на международной конференции по геометрии и ее приложениям (Новосибирск, 2000); Сибирской конференции по исследованию операций БСОК-98 и ЗССЖ-2000, на конференциях по дискретному анализу и исследованию операций БА(Ж-2002, 2004 (Новосибирск, 2002 г., 2004 г.); на международных конференциях по кодированию и криптографии \VCC-1999, 2001, 2003 и 2007 г.г. (Париж, Франция), на конференции "Математика. в современном мире" (Новосибирск, 2007). Результаты диссертации докладывались на семинаре "Дискретный анализ" НГУ и Института математики СО РАН, на семинаре "Теория информации и теория кодирования" ИППИ РАН, на семинаре "Дискретная математика"НГУ и ИМ СО РАН, на семинарах Мюнхенского технического университета и университета Ульма (Германия, 1997 г.), в Билефельдском университете (Билефельд, Германия, 1998 г., 2003, 2007), в Институте математики Болгарской Академии Наук (София, Велико Тырново, Болгария, 1999 г.), в Линчепинском университете (Линчепинг, Швеция, 1999 г. и 2000 г.), в Королевском техническом университете Стокгольма (Стокгольм, Швеция, 1999, 2000, 2001, 2002, 2004, 2006, 2007 г.), в Похангском университете (Поханг, Корея, 2003, цикл из 8 лекций). Все результаты были доложены на семинаре НГУ и Института математики СО РАН "Теория кодирования". Некоторые результаты диссертации включены в книгу Ж. Коэна. с соавторами "Covering codes "и в "Handbook on coding theory". Результаты первой, третьей, четвертой (частично) были включены в цикл работ, занявших в 2002 г. первое место на конкурсе научных работ в ИМ СО РАН.

Публикации. По теме диссертации автором опубликованы 42 работы, см. [147]-[188], среди них одна монография по совершенным кодам и одно учебное пособие по теории кодирования, опубликованное под грифом У МО.

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

1. Предложен новый комбинаторный метод построения и исследования свойств кодов - метод а-'компонент. Метод позволил построить обширный класс неэквивалентных совершенных двоичных кодов длины п, которых оказалось не менее

2^-log2(n+l) n|5log2(n+1) Z * D

2. Решена проблема Хергерта о существовании несистематических совершенных двоичных кодов длины п для каждого допустимого п > 127.

3. Предложено несколько свитчинговых методов построения бесконечных классов транзитивных кодов. Построено не менее [к/2J2 неэквивалентных совершенных транзитивных кодов длины п — 2к — 1, к > 4. Аналогичный результат верен для расширенных совершенных транзитивных кодов. Построен класс неэквивалентных Z4-линейных кодов длины 2 т,т > 3, с параметрами классических кодов Рида-Маллера ДМ (г, т) для любой допустимого п и любого г £ {1,., га — 2}.

4. Предложен новый метод исследования свойств кодов, являющийся методом локального анализа. Посредством этого метода исследовано строение г-компонент произвольного совершенного кода. Решена (конструктивно) проблема существования неэквивалентных компонент максимальной мощности, вложимых в совершенные коды. Для каждого допустимого п построен класс совершенных кодов длины п с ¿-компонентами как неэкстремальной, так и максимально возможной мощностей.

5. Полностью решен вопрос о метрической жесткости g-зна/чных совершенных кодов, q > 2, и некоторых классов MDS-кодов. Доказано также, что при п > кА произвольный приведенный код длины п, содержащий 2-(п, к, А)-схему, является метрически жестким.

6. Решена (конструктивно) проблема существования неизоморфных неориентируемых двуцветных замощений (сфер с пленками Мебиуса) порядка п для каждого п = 3 (mod 6) и половины классов вычетов п = 1 (mod 6).

Личный вклад. Диссертационная работа представляет собой единый цикл многолетних исследований автора, объединенных не только предметами, но и методами изучения. В совместных работах соискателю принадлежат идеи новых методов кодирования (предложенных в этих работах) и методов исследования свойств кодов, ключевые моменты разработки этих методов, применение к решению открытых проблем теории кодирования. Отдельные элементы доказательств утверждений и теорем выполнены в соавторстве при непосредственном участии соискателя. Конфликт интересов с соавторами отсутствует.

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

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

Выводы

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

1. Доказано, что для любого допустимого п > 15 число различных разбиений пространства Еп на совершенные коды длины п удовлетворяет неравенству п(п —1)/2

Р п > 2

2. Установлено, что для п = 2к, к > 2, число различных матриц пересечений разбиений Еп на совершенные расширенные двоичные коды не 2 меньше 2са , где с - положительная константа.

3. Доказано, что для п = 2к, к > 3, число неэквивалентных матриц пересечений разбиений Еп на совершенные расширенные двоичные ко

I 2 ды не меньше 2° п , где с' - положительная константа. Также доказано, н 3 что число неэквивалентных матриц пересечений не больше 2е п , где п достаточно велико и с" - положительная константа.

Заключение

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

1. Для каждого допустимого п предложен класс совершенных кодов длины п с г-компонентами как неэкстремальной, так и максимально возможной мощностей. Решена проблема существования неэквивалентных компонент максимальной мощности.

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

22е£1~1о82(п+1) ^г1^-10««*"4-1)

Была улучшена оценка Васильева для числа неэквивалентных совершенных кодов.

3. Решена проблема Хергерта: для каждого допустимого п > 127 построен класс несистематических совершенных двоичных кодов.

4. Предложено несколько новых комбинаторных методов построения бесконечных классов транзитивных кодов. В частности построено не менее [к/2\2 неэквивалентных совершенных транзитивных кодов длины п — 2к — 1, к > 4. Аналогичный результат справедлив для расширенных совершенных транзитивных кодов. Построен класс неэквивалентных ^-линейных кодов длины 2т,га > 3, с параметрами классических кодов Рида-Маллера ИМ (г, т) для любой допустимого п и любого г е {1,. ,га - 2}.

5. Предложен метод выявления локально-жестких фрагментов кодов для исследования метрической жесткости кодов. Посредством этого метода полностью выяснен вопрос о метрической жесткости д-значных совершенных кодов, д > 2, и некоторых классов МВБ-кодов. Доказано также, что при п > к4 произвольный приведенный код длины п, содержащий 2-(п, к, А)-схему, является метрически жестким кодом.

6. Исследована группа автоморфизмов совершенных кодов. Доказано, что порядок группы автоморфизмов произвольного совершенного кода С длины п меньше порядка группы автоморфизмов кода Хэмминга Н той же длины.

7. Предложены комбинаторные (каскадные и свитчинговые) методы построения богатых классов разбиений хэммингова пространства на совершенные коды и совершенные расширенные коды. Для построения разбиений на совершенные расширенные коды было сконструировано мощное множество латинских квадратов, которое получается посредством локальных преобразований (свитчингов) подматриц порядка 2x2 специальных латинских квадратов. Исследованы матрицы пересечения разбиений n-куба на совершенные коды, найдены нижняя и верхняя оценки числа таких разбиений.

8. Решена проблема построения неизоморфных замощений неориен-тируемых поверхностей парами систем троек Штейнера порядка п для каждого п = 3 (mod 6) и половины классов вычетов п = 1 (mod 6).

1. Августинович С. В. О неизометрии совершенных бинарных кодов // Труды Института математики СО РАН. 1994. Т. 74. С. 3-5.

2. Августинович С. В. Об одном свойстве совершенных бинарных кодов // Дискрет, анализ и исслед. операций. 1995. Т. 2. N. 1. С. 4-6.

3. Августинович С. В., Соловьева Ф. И. О дистанционной регулярности совершенных двоичных кодов // Пробл. передали информ. 1998. Т. 34. Вып. 3. С. 47-49.

4. Августинович С. В. К строению графов минимальных расстояний совершенных бинарных (п, 3)-кодов // Дискрет, анализ и исслед. операций. Сер. 1. 1998. Т. 5. N. 4. С. 3-5.

5. Августинович С. В. О строгой изометрии двоичных кодов // Дискрет. анализ и исслед. операций. Сер. 1. 2000. Т. 7. N. 3. С. 3-5.

6. Августинович С. В. Комбинаторные и метрические свойства совершенных кодов и раскрасок, Канд. дисс., Новосибирск, 2000. 33 с.

7. Августинович С.В., Васильева А.Ю. О восстановлении центрированной функции, Труды Междунар. конференции по дискретному анализу и исследованию операций, Новосибирск, Россия, Июнь. 2000. С. 64.

8. Августинович С. В., Соловьева Ф. И., Хеден У. Совершенные коды полного ранга с ядрами больших размерностей // Дискрет, анализ и исслед. операций. Сер. 1. 2001. Т. 8. N. 4. С. 3-8.

9. Августинович С. В., Соловьева Ф. И., Хеден У. О проблеме рангов и ядер совершенных кодов // Пробл. передачи информ. 2003. Т. 39. N. 4. С. 341-345.

10. Августинович С. В., Соловьева Ф. И., Хеден У. О структуре группы симметрий кодов Васильева // Пробл. передачи информ. 2005. Т. 41. N. 2. С. 105-112.

11. Августинович С. В., Соловьева Ф. И., Хеден У. О разбиениях га-куба на неэквивалентные совершенные коды // Пробл. передачи информ. 2007. Т. 43. N. 4. С. 45-50.

12. Августинович С. В., Васильева А.Ю. Теоремы восстановления для центрированных функций и совершенных кодов // Сибирский матем. журнал, принято к печати.

13. Александров В. А. Пример одномерного жесткого множества на плоскости // Сибирский математический журнал. 1993. Т. 34. N. 6. С. 999-1004.

14. Бабаш А. В., Глухое М. М., Шанкин Г. П. О преобразованиях множества слов в конечном алфавите, не размножающих искажений // Дискретная математика. 1997. Т.9. N 3.

15. Бассалыго Л. А., Зайцев Г. В., Зиновьев В. А. О равномерно упакованных кодах // Пробл. передачи информ. 1974. Т. 10. Вып. 1. 9-14.

16. Бассалыго Л. А., Зайцев Г. В., Зиновьев В. А. Замечание о равномерно упакованных кодах // Пробл. передачи информ. 1977. Т. 13. Вып. 3. 22-25.

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

18. Васильев Ю. Л. О сравнении сложности тупиковых и минимальных дизъюнктивных нормальных форм // Проблемы кибернетики. М: Физматгиз, 1963. Вып. 10. С. 5-61.

19. Васильева А.Ю. Спектральные свойства совершенных двоичных (п, 3)-кодов // Дискрет, анализ и исслед. операций. 1995. Т. 2. N. 2. С. 16-25.

20. Васильев Ю. Л., Соловьева Ф. И. Кодообразующие факторизации п-мерного единичного куба и совершенных двоичных кодов // Пробл. передачи информ. 1997. Т. 33. Вып. 1. С. 64-74.

21. Васильева А.Ю. О расстояниях между совершенными двоичными кодами // Дискрет, анализ и исслед. операций. 1998. Т. 5. N. 4. С. 16-25.

22. Васильева А. Ю. Локальные спектры совершенных двоичных кодов // Дискрет, анализ и исслед. операций. 1999. Т. 6. N. 1. С. 16-25.

23. Васильева А. Ю. Спектральные свойства совершенных двоичных кодов, Канд. дисс., Новосибирск, 1999. 79 с.

24. Зейферт Г., Трельфалль В. Топология. М.-Л.: ГОНТИ, 1938.

25. Зиновьев В. А., Леонтьев В. К. О совершенных кодах // Проблемы управления и теории информации. 1972. Вып. 1. С. 26-35.

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

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

28. Зиновьев В. А. Комбинаторные методы построения и анализа нелинейных корректирующих кодов. Дисс. докт. физ.-мат. наук: 01.01.09. Москва, 1988, 300 с.

29. Зиновьев В. А., Лобстейн А. Об обощенных каскадных конструкциях совершенных двоичных нелинейных кодов // Пробл. передачи информ. 2000. Т. 36. Вып. 4. С. 59-73.

30. Зиновьев В.А., Зиновьев Д.В. Двоичные расширенные совершенные коды длины 16 ранга // Пробл. передачи информ. 2006. Т. 42. N. 2. С. 63-80.

31. Кабатянский Г. А., Левенштейн В. И. О границах для упаковок на сфере и в пространстве // Пробл. передачи информ. 1978. Т. 14. N. 1. С. 1-17.

32. Кротов Д. С. Об универсальном совершенном коде, содержащем все заданные совершенные коды // Дискрет, анализ и исслед. операций. Сер. 1. 2000. Т. 7, N. 1. С. 40-48.

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

34. Кротов Д. С. Я^-линейные совершенные коды // Дискрет, анализ и исслед. операций. Сер. 1. 2000. Т. 7, N. 4. С. 78-90.

35. Кротов Д. С. Комбинированная конструкция совершенных двоичных кодов // Пробл. передачи информ. 2000. Т. 36. Вып. 4. С. 74-79.

36. Кротов Д. С. Конструкции плотно упакованных кодов и нижние оценки их числа. Канд. дисс., Новосибирск, 2000. 64 с.

37. Кротов Д. С. Индуктивные конструкции совершенных троичных равновесных кодов // Пробл. передачи информ. 2001. Т. 37. Вып. 1. С. 3-11.

38. Курляндчик Я. М. О логарифмической асимптотике длины максимального цикла разброса г > 2 // Методы дискретного анализа. Новосибирск: Ин-т математики СО АН СССР, 1971. Вып. 19. С. 48-55.

39. Левин А. И. Конструкции систем Штейнера: Дипломная работа. Якутск, Якутский госуниверситет, 1977.

40. Лось A.B. Построение совершенных g-ичных кодов свитчингами простых компонент // Пробл. передачи информ. 2006. Т. 42. N. 1. С. 34-42.

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

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

43. Малюгин С. А. О критерии несистематичности совершенных двоичных кодов, Труды конференции "Дискретный анализ и исследование операций". Новосибирск, июнь. 2000. С. 77.

44. Малюгин С. А. О порядке группы автоморфизмов совершенных двоичных кодов // Дискрет, анализ и исслед. операций. Сер. 1. 2000. Т. 7, N. 4. С. 91-100.

45. Малюгин С. А. Несистематические совершенные двоичные коды // Дискрет, анализ и исслед. операций. Сер. 1. 2001. Т. 8, N. 1. С. 55-76.

46. Малюгин С.А. Транзитивные совершенные коды длины 15, Тр. конф. "Дискретный анализ и исследование операций". Новосибирск: Изд-во Ин-та математики, 2004. С. 96.

47. Малюгин С. А. О классах эквивалентности совершенных двоичных кодов длины 15. Препринт № 138. Новосибирск: Институт математики СО РАН, 2004. С. 34.

48. Малюгин С. А. О перечислении неэквивалентных совершенных двоичных кодов длины 15 и ранга 15 // Дискрет, анализ и исслед. операций. Сер. 1. 2006. Т. 13, N. 1. С. 77-98.

49. Мальцев А.И. Основы линейной алгебры. М.: Наука. 1970. 400 с.

50. Нечаев А. А. Коды Кердока в циклической форме // Дискретн. Ма-тем. 1989. V. 1. № 4. Р. 123-139.

51. Потапов В. Н. О нижней оценке числа транзитивных совершенных кодов // Дискрет, анализ и исслед. операций. Сер. 1. 2006. Т. 13. N. 4. С. 49-59.

52. Пулатов А. К. О геометрических свойствах и схемной реализации подгрупп в Еп // Методы дискретного анализа в теории кодов и схем. Новосибирск: Ин-т математики СО АН СССР, 1973. Вып. 23. С. 3237.

53. Пулатов А. К. Нижняя оценка сложности схемной реализации для одного класса кодов // Методы дискретного анализа в теории кодов и схем. Новосибирск: Ин-т математики СО АН СССР, 1974. Вып. 25. С. 56-61.

54. Пулатов А. К. Нижняя оценка сложности схемной реализации для одного класса кодов // Методы дискретного анализа в теории кодов и схем. Новосибирск: Ии-т математики СО АН СССР, 1974. Вып. 29. С. 56-61.

55. Романов А. М. О несистематических совершенных кодах длины 15 // Дискрет, анализ и исслед. операций. 1997. Т. 4, N. 4. С. 75-78.

56. Рыбников К. А. Введение в комбинаторный анализ. Москва, МГУ, 1972.

57. Рычков К. Л. Модификация метода В. М. Храпченко и применение ее к оценкам сложности П-схем для кодовых функций // Методы дискретного анализа в теории графов и схем, Новосибирск: Ин-т математики СО АН СССР, 1985. Вып. 42. С. 91-98.

58. Семаков Н.Б., Зиновьев В. А., Зайцев Г. В. Равномерно упакованные коды // Пробл. передачи информ. 1971. Т. 7. Вып. 1. 38-50.

59. Соловьева Ф. И. О факторизации кодообразующих д.н.ф. // Методы дискретного анализа в исследовании функциональных систем. Новосибирск: Ин-т математики СО АН СССР. 1988. Вып. 47. С. 66-88.

60. Соловьева Ф. И. Класс двоичных плотно упакованных кодов, порождаемых g-ичными кодами // Методы дискретного анализа в изучении булевых функций и графов. Новосибирск: Ин-т математики СО АН СССР. 1989. Вып. 48. С. 70-72.

61. Соловьева Ф. И. Точные границы связности кодообразующих д.н.ф., Препринт N 10. Новосибирск: Институт математики СО РАН, 1990. С. 15.

62. Соловьева Ф. И., Лось А. В. О пересечениях g-значных совершенных кодов, Сибирский математический журнал, принято к печати.

63. Ahlswede R., Aydinian В., Khachatrian L. On perfect codes and related concepts // Des., Codes and Cryptogr. 2001 V. 22. P. 221-237.

64. Assmus E. F. Jr., Mattson H. F. Jr. On tactical configurations and error-correcting codes // J. Comb. Theory. V. 2. 1967. P. 243-257.

65. Avgustinovich S. V., Solov'eva F. I. Distance regularity and perfect binary codes, Proc. Sixth Int. Workshop on Algebraic and Comb. Coding Theory. Pskov, Russia. September. 1998. P. 13-16.

66. Avgustinovich S. V., Heden O., Solov'eva F. I. The classification of some perfect codes, Stockholm: Royal Inst, of Technology, 2001. (Preprint / Trita-mat.-2001-9).

67. Avgustinovich S. V., Heden O., Solov'eva F. I. Oil ranks and kernels of perfect codes, Stockholm: Royal Inst, of Technology, 2001. (Preprint / Trita-mat.-2001-13).

68. Avgustinovich S. V., Heden O., Solov'eva F. I. On intersections of perfect binary codes // Bayreuther Mathematische Schriften, 2005. V. 71. P. 8-13.

69. Avgustinovich S. V, Heden 0., Solov'eva F. I. On intersection problem for perfect binary codes // Des. Codes Crypt., 2006. V. 39. pp. 317-322.

70. S.V. Avgustinovich, A.Yu. VasiVeva, Testing sets for 1-perfect codes// Lecture Notes in Computer Science, V. 4123, November, (2006), pp. 938940.

71. Bauer H., Ganter B., Hergert F. Algebraic Techniques for nonlinear codes. Darmstadt. 1981. Preprint N. 609. 25 p.

72. Bennett G.K, Grannell M.J., Griggs T.S. Bi-Embeddings of Steiner Triple Systems of Order 15 // Graphs and Combinatorics. 2001. V. 17. № 2. P. 193-197.

73. Bonnigton C.P., Grannell M.J., Griggs T.S., 8irán J. Exponential Families of Non-Isomorphic Triangulations of Complete Graphs // J. Combin. Theory. Ser. B. 2000. V. 78. № 2. P. 169-184.

74. Borges J., Rifa J. A characterization of 1-perfect additive codes // IEEE Trans. Inform. Theory. 1999. V. 45. № 5. P. 1688-1697.

75. Borges J., Fernandez C., Rifa J., Villanueva M. Constructions of 1-perfect partitions on the n-cube (Z/2)n // Technical report PIRDI 1/01, ETSE, July, 2001.

76. Borges J., Phelps K. T., Rifa J. K. The rank and kernel of extended 1-perfect ¿^-linear and additive non-.^-linear codes // IEEE Trans. Inform. Theory. 2003. V 49. N 8. P. 2028-2034.

77. Borges J., Phelps K. T., Rifa J., Zinoviev V. A. On Z4-Linear Preparata-Like and Kerdock-Like Codes // IEEE Trans. Inform. Theory. 2003. V. 49. № 11. P. 2834-2843.

78. Borges J., Fernandes C., Phelps K. T. Quaternary Reed-Muller codes 11 IEEE Trans. Inform. Theory. 2005. V. 51. №. 7. P. 2686-2691.

79. Bauer H., Ganter B., Hergert F. Algebraic Techniques for nonlinear codes // Combinatorica. 1983. V. 3. N. 1. P. 21-33.

80. Calderbank A. R., Cameron P. J., Kantor W. M., Seidel J. J. Z4-Kerdock Codes, Orthogonal Spreads, and Extremal Euclidean Line-Sets // Proc. London Math. Soc. 1997. V. 75. P. 436-480.

81. Cohen G., Honkala I., Lobstein A., Litsyn S. Covering codes, Elsevier, 1998.

82. Colbourn C., Mathon R. Steiner Systems, CRC Handbook of Combinatorial Designs, C. Colbourn and J. Dinitz eds., CRC Press, New York 1996, P. 66-75.

83. Constantinescu I., Heise W. On the concept of code-isomorphy // Journal of Geometry. 1996. V. 57. P. 63-69.

84. Delsarte P. Bounds for unrestricted codes by linear programming, Philips Res. Report. 1972. N. 27. P. 272-289.

85. R.J.Duglas, Upper bounds on the length of circuits of even spread in the d-cube // J. Combin. Theory. 1969. V. 7. N 3. P. 206-214.

86. Ducrocq P.M., Sterboul F. On G-Triple Systems // Publications du Laboratoire de Calcul de l'Université des Sciences at Techniques de Lille. 1978. № 103.

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

88. Etzion T., Vardy A. On perfect codes and tilings: problems and solutions // SIAM J. Discrete Math. 1998. V. 11. N. 2. P. 205-223.

89. Golomb S. W., Posner E. C. Rook domains, latin squares, affine and error distributing codes // IEEE Trans, on Inform. Thoery. 1964. V. 10. P. 196-208.

90. Grannell M.J., Griggs T.S., Siráñ J. Face 2-Colourable Triangular Embeddings of Complete Graphs // J. Combin. Theory. Ser. B. 1998. V. 74. № 1. P. 8-19.

91. Grannell M.J., Griggs T.S., Siráñ J. Surface Embeddings of Steiner Triple Systems // J. Combin. Des. 1998. V. 6. № 5. P. 325-336.

92. Hall M. Jr. Combinatorial Theory, Waltham Mass.: Blaisdell Publ. Co., 1967.

93. Hammons A. R., Kumar P. V.; Galderbank A. R., Sloane N. J. A., Solé P. The ^-Linearity of Kerdock, Preparata, Goethals, and Related Codes // IEEE Trans. Inform. Theory. 1994. V. 40. № 2. P. 301-319.

94. Heden 0. A new construction of group and nongroup perfect codes // Inform, and Control. 1977. V. 34. N. 4. P. 314-323.

95. Heden 0. A binary perfect code of length 15 and codimension 0 // Designs, Codes and Cryptography. 1994. V.4. P. 213-220.

96. Heise W., Quattrocchi P. Informations- und Codierungtheorie. 3. Aufl., Springer-Verlag, Berlin-Heidelberg-New York-Tokio. 1995.

97. Handbook on coding theory, Elsevier. 1998.

98. I. Herburt, Rigidity of products, Geom. Dedicata 1993. V. 46 P. 243-248.

99. Herburt /., Ungar S. Rigid sets of dimension n — 1 in Rn // Geom. Dedicata. 1999. V. 76. P. 331-339.

100. Hergert F. Algebraische Methoden fur Nichtlineare Codes, Thesis Darmstadt. 1985.

101. Hou X.-D., Lahtonen J. T., Koponen S. The Reed-Muller code R(r, m) is not Z4-linear for 3 < r < m 2 // IEEE Trans. Inform. Theory. 1998. V. 44. № 2. P. 798-799.

102. Krotov D. S. Combining construction of perfect binaty codes and of perfect ternary constant-weight codes, Proc. Seventh Int. Workshop on Algebraic and Comb. Coding Theory, Bansko, Bulgaria, June. 2000. P. 193-198.

103. Krotov D. S. Z^linear Hadamard and extended perfect codes, Proc. of the Int. Workshop on Coding and Cryptography WCC 2001, Jan. 8-12, 2001. Paris, France. P. 329-334.

104. Krotov D. S., Avgustinovich S. V. On the number of 1-perfect binary codes: a lower bound // IEEE Trans. Inform. Theory, V. 54. N. 4. 2008. P. 1760-1765.

105. Kiihnel W. Topological Aspects of Twofold Triple Systems // Expo. Math. 1998. V. 16. P. 289-332.

106. Kuzmin A. S., Nechaev A. A. Construction on error-correcting codes using linear recurrences // J. of Math. Sci. 1992. V. 47. № 5. P. 183-184.

107. Laborde J.-M. Une nouvelle famille de codes binaires, parfaits, non lineares // C. R. Acad. Sci. Paris. 1983. V. 297. N 1. P. 67-70.

108. Laman G. On graphs and rigidity of plane skeletal structures // J. Engrg. Math. 1970. V. 4. P. 331-340.

109. Lefmann H., Phelps К. T., Roedl V. Rigid linear binary codes //J. Comb. Theory, Ser. 1993. V. A 63. N. 1. P. 110-128.

110. Liu C. L., Ong B. G., Ruth G. R. A construction scheme for linear and non-linear codes // Discrete Math. 1973. V. 4. № 2. P. 171-184.

111. Lloyd S. P. Binary block coding // Bell Syst. Techn. J., 1957. T.36. P. 517-535. (Русский перевод: С.П. Ллойд. Бинарное блочное кодирование // Кибернетический сб. М.: Изд-во иностр. лит., 1960. Вып. 1. С. 206-226.)

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

113. Malyugin S. A. Perfect codes with trivial automorphism group, Proc. Second Int. Workshop on Optimal Codes and Related Topics. Sozopol, Bulgaria. June. 1998. P. 163-167.

114. Mollard M. A generalized parity function and its use in the construction of perfect codes // SIAM J. Alg. Disc. Meth. 1986. V. 7. N. 1. P. 113-115.

115. Nechaev A. A., Kuzmin A. S. Z^-linearity, two approaches, Proc. of Fourth Int. Workshop on Algebraic and Comb. Coding Theory, Sozopol, Bulgaria. September 1996. P. 112-115.

116. Pujol J., Rifa J. Additive Reed-Muller codes, Proc. of Int. Symp. on Inform. Theory, Ulm, Germany, 1997. P. 508.

117. Oral H., Phelps К. T. Almost all self-dual codes are rigid //J. Comb. Theory, 1992. V. A 60. N. 2. P. 264-276.

118. Phelps К. T. A combinatorial construction of perfect codes // SIAM J. Alg. Disc. Meth., 1983. V. 4. P. 398-403.

119. Phelps К. T. A General Product Construction for Error Correcting Codes // SIAM J. Algebraic and Discrete Methods, 1984. V. 5. 224-228.

120. Phelps К. T. Every finite group is the automorphism group of some perfect code // J. of Combin. Theory, series A. 1986. V. 43 N. 1. P. 45-51.

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

122. Phelps К. Т., LeVan M. J. Non-systematic perfect codes // SIAM Journal of Discrete Mathematics. 1999. V. 12. N. 1. P. 27-34.

123. Phelps К. T., LeVan M. J. Switching equivalence classes of perfect codes // Des., Codes and Cryptogr. 1999. V. 16. N. 2. P. 179-184.

124. Phelps К. T. An enumeration of 1-perfect binary codes of length 15 // Australian Journal of Combin., 2000. V. 21. P. 287-298.

125. Phelps K. T., Rifa J. K. On binary 1-perfect additive codes // IEEE Trans. Inform. Theory. 2002. V 48. N 9. P. 2587-2592.

126. Ringel G. Map Color Theorem. Yew York-Berlin: Springer-Verlag, 1974.

127. Rifa J., Pujol J. Translation-invariant propelinear codes // IEEE Trans. Inform. Theory, V. 43. N. 2. 1997. P. 590-598.

128. Rifa J., Vardy A. On partitions of space into perfect codes, Workshop on Coding and Information Integrity. Ein Boqeq. Israel. October 1997.

129. Rifa J. Well-ordered Steiner triple systems and 1-perfect partitons of the тг-cube // SIAM J. Discrete Math., 1999. V. 12. N. 1. P. 35-47.

130. Rifa J., Pujol J., Borges J. 1-Perfect uniform and distance invariant partitions // Applicable Algebra in Engineering, Communucation and Computing, 2001. V. 11. P. 297-311.

131. Rifa J., Solov'eva F. I., Villanueva M. On the intersection of additive perfect codes // IEEE Trans. Inform. Theory, V. 54. N. 3. 2008. P. 13461356.

132. Simonis J. On generator matrices of codes // IEEE Trans. Inform. Theory. 1992. V. 38. P. 516.

133. Solov'eva F. I., Vasiïev Y. L. Interdependence between perfect binary-codes and their projections, Proc. Seventh Joint Swedish-Russian Int. Workshop on Inform. Theory. St.-Petersburg, Russia. June. 1995. P. 239242.

134. Svanstrom M. Ternary codes with weight constraints. Ph. Dissertation, N. 572. Linkôping Univ., 1999.

135. Taussky O., Todd J. Covering theorems for Abelian groups // Ann. Soc. Polonaise de Math., 1948. V. 21. P. 303-305.

136. Tietàvàinen A. On the nonexistence of perfect codes over finite fields. // SIAM J.Appl.Math. 1973. V. 24. P. 88-96.

137. Vasil'eva A. Y. On centered characteristic functions of perfect binary codes, Proc. of Sixth Int. Workshop on Algebraic and Combin. Coding Theory, Pskov, Russia. September. 1998. P. 224-227.

138. Zhe-Xian Wan. Quaternary codes. Singapore: World Scientific Publishing Co. Pte. Ltd, 1997.

139. Wielandt H. Finite permutation groups. New York: Academic Press Inc. 1964.

140. Winkler R. M. Isometric embeddings in products of complete graphs // Discrete Appl. Math. 1984. V. 7. P. 221-225.

141. Youngs J.W.T. The Mistery of the Heawood Conjecture // Graph Theory and its Applications. New York: Academic Press. 1970. P. 17-50.

142. Zaremba S. K. A covering theorem for Abelian groups // Journal of the London Math. Society, 1951. V. 1. N. 26. P. 71-72.

143. Zinoviev V. A. On Generalized Concatenated Codes // Colloquia Mathematica Societatis Jànos Bolyai, V. 16, Topics in Information Theory, Keszthely, Hungary. 1975. P. 587-592.

144. Zinov'ev V. A., Lobstein A. C. On new perfect binary nonlinear codes // Applicable Algebra in Engin. Comm. and Comput., 1997. V. 8. P. 415-420. Theory, Keszthely, Hungary. 1975. P. 587-592.

145. Zinov'ev V. A., Lobstein A. C. Constructions of perfect binary nonlinear codes, Proc. Sixth Int. Workshop on Algebraic and Comb. Coding Theory. Pskov, Russia. September. 1998. P. 249-254.

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

147. Соловьева Ф. И. О двоичных негрупповых кодах // Методы дискретного анализа в изучении булевых функций и графов. Новосибирск: Ин-т математики СО АН СССР. 1981. Вып. 37. С. 65-76.

148. Августинович С. В., Соловьева Ф. И. О несистематических совершенных двоичных кодах // Пробл. передачи информ. 1996. Т. 32. Вып. 3. С. 47-50.

149. Соловьева Ф. И. Системы троек Штейнера и проблема нитей, Второй Сибирский конгресс по прикладной и индустриальной математике (ИНПРИМ-96). Новосибирск, 25-30 июня, 1996. С. 125-126.

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

151. Августинович C.B., Соловьева Ф.И. Новые конструкции и свойства совершенных кодов, Труды Междунар. конференции по дискретному анализу и исследованию операций, Новосибирск, Россия, Июнь. 2000. С. 5-10.

152. Соловьева Ф. И., Топалова С. Т. О группах автоморфизмов совершенных двоичных кодов и систем троек Штейнера // Пробл. передачи информ. 2000. Т. 36. Вып. 4. С. 53-58.

153. Соловьева Ф. И., Топалова С. Т. Совершенные двоичные коды и системы троек Штейнера с максимальными порядками групп автоморфизмов // Дискрет, анализ и исслед. операций. Сер. 1. 2000. Т. 7, N. 4. С. 101-110.

154. Августинович С. В., Соловьева Ф. И. О метрической жесткости двоичных кодов // Пробл. передачи информ. 2003. Т. 39. Вып. 2. С. 63-68.

155. Соловьева Ф. И. О построении транзитивных кодов // Пробл. передачи информ. 2005. Т. 41. Вып. 3. С. 23-31.

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

157. Соловьева Ф. И. О ^-линейных кодах с параметрами кодов Рида-Маллера // Пробл. передачи информ. 2007. Т. 43. Вып. 1. С. 41-47.

158. Соловьева Ф. И. Замощения неориентируемых поверхностей системами троек Штейнера // Пробл. передачи ииформ. 2007. Т. 43. Вып. 3. С. 54-65.

159. Соловьева Ф. И. Построение замощений неориентируемых поверхностей системами троек Штейнера, Труды конференции "Математика в современном мире", 17-23 сентября 2007. Новосибирск, С. 286287.

160. Solov'eva F. I. A combinatorial construction of perfect binary codes, Proc. of Fourth Int. Workshop on Algebraic and Comb. Coding Theory. Novgorod, Russia. September. 1994. P. 171-174.

161. Avgustinovich S. V., Solov'eva F. I. On projections of perfect binary codes, Proc. Seventh Joint Swedish-Russian Workshop on Information Theory, St.-Petersburg, Russia. June. 1995. P. 25-26.

162. Avgustinovich S. V., Solov'eva F. I. Construction of perfect binary codes by sequential translations of the «-components, Proc. of Fifth Int. Workshop on Algebraic and Comb. Coding Theory. Sozopol, Bulgaria. June. 1996. P. 9-14.

163. Avgustinovich S. V., Solov'eva F. I. Existence of nonsystematic perfect binary codes, Proc. of Fifth Int. Workshop on Algebraic and Comb. Coding Theory, Sozopol, Bulgaria, June. 1996. P. 15-19.

164. Avgustinovich S. V., Solov'eva F. I. Structural properties of perfect binary codes, Proc. of Int. Symp. on Inform. Theory, Ulm, Germany. 1997. P. 456.

165. Avgustinovich S. V., Solov'eva F. I. Perfect binary codes with trivial automorphism group, Proc. of Int. Workshop on Information Theory, Killarney, Ireland. June. 1998. P. 114-115.

166. Solov'eva F. I., Avgustinovich S. V., Honold T., Heise W. On the extendability of code isometries // J. of Geometry. 1998. V. 61. P. 3-16.

167. Solov'eva F. I. On components of perfect binary codes, Preprint 98-041, Universität Bielefeld, Sonderforschungsbereich 343 Discrete Struct.uren in der Mathematik. 1998. 8 p.

168. Solov'eva F. I. Constructions of perfect binary codes, Preprint 98-042, Universität Bielefeld, Sonderforschungsbereich 343 Discrete Structuren in der Mathematik. 1998. 12 p.

169. Solov'eva F. I. Cardinality of i-components of perfect codes, Proc.- of Siberian conference on Operation Research, Russia, Novosibirsk. 1998. P. 139.

170. Solov'eva F. I., Avgustinovich S. V., Honold T., Heise W. Metrically rigid codes, Proc. Sixth Int. Workshop on Algebraic and Comb. Coding Theory. Pskov, Russia. September. 1998. P. 215-219.

171. Solov'eva F. I. Components on perfect binary codes, Proc. of 1998 Optimal codes Workshop, Sozopol. Bulgaria. 1998. P. 188-192.

172. Solov'eva F. I. Perfect binary codes components, Proc. of Workshop on Coding and Cryptography WCC'99. Paris, France. January. 1999. P. 29-32.

173. Solov'eva F. I. Switchings and perfect codes, Numbers, Information and Complexity, Kluwer Academic Publisher. 2000. 311-314.

174. Solov'eva F. I. Perfect binary codes: bounds and properties // Discrete Math. 2000. V. 213. P. 283-290.

175. Solov'eva F. I., Topalova S. T. On the automorphism groups of perfect binary codes, Proc. Seventh Int. Workshop on Algebraic and Comb. Coding Theory. Bansko, Bulgaria. June. 2000. P. 283-287.

176. Solov'eva F. I., Topalova S. T. On the automorphism groups of Steiner Systems, Proc. of Int. Workshop on Discrete Analiz and Operation Research, Novosibirsk, Russia. June. 2000. P. 90.

177. Avgustinovich S. V., Solov'eva F. I. On the rigidity of binary codes, Proc. of Int. Conference "Geometry and applications", Novosibirsk, Russia. March. 2000. P. 16-17.

178. Avgustinovich S. V., Lobstein A., Solov'eva F. I. Partitions by perfect binary codes, using concatenation and latin qsuares, Proc. Seventh Int. Workshop on Algebraic and Comb. Coding Theory. Bansko, Bulgaria. June. 2000. P. 45-50.

179. Solov'eva F.I. Structure of ¿-components of perfect binary codes // Discrete Appl. Math. 2001. V. 111. N. 1-2. P. 189-197.

180. Avgustinovich S. V., Lobstein A., Solov'eva F. I. Intersection matrices for partitions by binary perfect codes // IEEE Trans, on Inform. Theory. 2001. V. 47. N. 4. P. 1621-1624.

181. Solov'eva F. /., Avgustinovich S. V. On the metrical rigidity of binary codes, Proc. of Workshop on Coding and Cryptography WCC'2001, Paris, France. January. 2001. P. 35-42.

182. Solov'eva F. I. Automorphism groups of perfect codes, Proc. of EWM Intern. Workshop on Groups and Graphs, Varna, Bulgaria. August. 2002. P. 95-100.

183. Solov'eva F. I. Tilings of closed surfaces by Steiner triple systems, Proc. of Workshop on Coding and Cryptogr. WCC'2003, Versaille, France. March. 2003. P. 425-431.

184. Solov'eva F. I. On transitive codes, Proc. of Int. Workshop on Discrete Analysis and Operation Research, Novosibirsk, Russia. June (2004) 99.

185. Solov'eva F. I. On perfect codes and related topics, Com2Mac Lecture Note Series 13, Pohang 2004.

186. Solov'eva F. I. Some constructions of transitive codes, Proc. of Int. Workshop on Optimal codes and related topics. Pamporovo, Bulgaria. June. 2005. P. 254-260.

187. Solov'eva F. I. Designs and perfect codes // Lecture Notes in Computer Science, V. 4123. November. 2006. P. 1104-1105.

188. Solov'eva F. I. On perfect binary codes // Discrete Appl. of Math., to appear.