О вложимости систем Штейнера в совершенные коды тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Защита состоится 18 декабря 2013 г. в 17 час. 00 мин. па заседании диссертационного совета Д 003.015.01 при Институте математики им. С. Л. Соболева СО РАН по адресу: ауд. 417, пр. Академика Коптюга 4, г. Новосибирск 630090.

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

Автореферат разослан 06 ноября 2013 г. Ученый секретарь диссертационного совета, д.ф.-м.н.

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

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

Одной из основных задач теории блок-схем является задача классификации систем Штейнера. В настоящее время известна1'2 классификация систем троек Штейнера порядка не больше 19. Также открытым является вопрос о вложимости произвольной системы троек (четверок) Штейнера в некоторый совершенный (расширенный совершенный) двоичный код.

Двоичный код С длины п называется совершенным кодом, исправляющим одну ошибку (кратко - совершенным), если каждый вектор х из F™ находится на расстоянии не более 1 ровно от одного кодового слова С. Пусть С - расширенный совершенный код, полученный из совершенного кода С добавлением общей проверки на четность (т.е. добавлением координаты, равной сумме остальных по модулю 2). Далее будут рассматриваться только приведенные совершенные и приведенные расширенные совершенные двоичные коды (т.е. коды, содержащие нулевое кодовое слово). Рангом приведенного кода называется размерность линейного подпространства пространства IF", образованного векторами из этого кода.

Наиболее известным совершенным кодом является линейный код Хэмминга, открытый Р. Хэммингом в 1950 г. Известно, что такой код единственный с точностью до эквивалентности (далее код Хэмминга длины п будем обозначать через "Нп). Совершенные g-ичные коды Хэмминга имеют следующие параметры: длина

п = ¡-, г > 1, число кодовых слов qn

r, минимальное расстояние равно 3. В 1949 г. М. Голеем было открыто 2 линейных совершенных кода, отличных от кода Хэмминга, а именно — двоичный код длины 23, размерности 12 с расстоянием 7, а также троичный

Холл М. Комбинаторика. Пер. с англ. М.: Мир. 1970. 424 с. 2 Kaski Р.,

Östergärd Р. R. J. The Steiner Triple Systems of Order 19 // Math. Comput. 2004. N 73. P. 2075-2092.

код длины 11, размерности 6 с расстоянием 5. В. А. Зиновьев и В. К. Леонтьев3 и независимо А. Титвайнен4 доказали, что любой нетривиальный совершенный код имеет параметры кода Хэм-минга либо кода Голея. Первый свитчинговый метод построения нелинейных совершенных двоичных кодов был предложен в 1962 г. Ю.Л. Васильевым5. Известно6, что любой совершенный код длины п ранга п—log(n+l) + l является кодом Васильева, построенным

свитчингами г-компонент (по одной координатной позиции) из коп— 1

да Хэмминга с помощью некоторой функции А : Н

—у (которая, вообще говоря, может быть нелинейной). Код Васильева V" может быть, с точностью до эквивалентности, представлен в виде

для некоторой функции А : УГ^г -> . Первое существенное улучшение нижней границы числа известных кодов Васильева было получено в 1997 г. в работе С. В. Августиновича и Ф. И. Соловьевой7, где был предложен свитчинговый метод а-компонент построения совершенных кодов. В настоящее время полная классификация совершенных кодов все еще не получена.

Пусть V — множество, состоящее из v элементов, t-(v,k, А)-схе-мой называется такое размещение v различных элементов по блокам, что каждый блок содержит точно к различных элементов, любое i-элементное подмножество из V появляется точно в А блоках. Системой троек Штейнера порядка v (обозначаемой STS(v)) и системой четверок Штейнера порядка v (обозначаемой SQS(v)) называются 2-(г>, 3,1) и 3-(г>,4,1)-схемы соответственно.

Первая публично заявленная задача, связанная с системами троек и четверок Штейнера, была поставлена У.С.Б. Вулхаусом в

3 Зиновьев В. А., Леонтьев В. К. О совершенных кодах // Пробл. переда-

чи информ. 1972. Т. 8. № 1. С. 26-35. 4 Tietavainen A. A short proof for

the nonexistence of unknown perfect codes over GF(q), q > 2 // Ann. Acad. Sei. Fenn. 1974. A I 580. P.l-5. 5 Васильев Ю. JI. О негрупповых плотно-упакованных кодах // Проблемы кибернетики. М.: Физматгиз. 1962. Вып. 8. С. 337-339.

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

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

1844 г. и формулировалась как определение существования различных сочетаний fc-элементных множеств (также называемых блоками) из некоторого n-элементного множества, при условии, что никакие t символов, встречающиеся в некотором блоке, не встречаются ни в каком другом блоке из данного сочетания. То есть, из данного n-элементного множества необходимо построить такие fc-элементные блоки, что каждая комбинация из t символов встречается в единственном блоке. Задача оказалась чрезвычайно сложной, и сначала рассматривался ее частный случай при к = 3, t = 2, который был разрешен Т.П. Киркманом в 1847 г. Им было показано, что сочетание блоков с такими параметрами существует лишь при п = 1,3 (mod6). Независимо от работы Т.П. Киркмана, Я. Штейнер в 1853 г. представил частный случай задачи У.С.Б. Вулхауса при к = 3, t = 2. Следующий значимый прогресс в решении поставленной У.С.Б. Вулхаусом задачи в случае к = 4, t — 3 достигнут Х.Ханани только в 1960 г. Им было доказано, что сочетание блоков с такими параметрами существует лишь при п = 2,4 (mod 6). Впоследствии, сочетания блоков из задачи У.С.Б. Вулхауса были названы системами Штейнера, в частности — системами троек Штейнера при к = 3, t = 2 и системами четверок Штейнера при к — 4, t = 3.

Известно8,9, что ранг системы троек Штейнера STS(n) порядка п = 2Г — 1 (системы четверок Штейнера SQS(N) порядка N = 2Г) варьируется от 2Г — г — 1 = п—log(n + 1) = N—logN — 1, ранга кода Хэмминга длины 2Г — 1 до полного ранга 2Г — 1.

Нетрудно показать, что носители всех кодовых слов веса 3 в приведенном совершенном двоичном коде С длины п — 2Г — 1 образуют систему троек Штейнера STS(2Г — 1), а носители кодовых слов веса 4 в приведенном расширенном совершенном коде С длины N = 2Г образуют10 систему четверок Штейнера SQS