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

РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ НАУКИ ИНСТИТУТ МАТЕМАТИКИ им. С. Л. Соболева

На правах рукописи УДК 519.1

Ковалевская Дарья Игоревна

О ВЛОЖИМОСТИ СИСТЕМ ШТЕЙНЕРА В СОВЕРШЕННЫЕ КОДЫ

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

АВТОРЕФЕРАТ

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

1 4 НОЯ 2013

Новосибирск - 2013

005537728

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

Научный руководитель: доктор физико-математических наук,

профессор Ф. И. Соловьева

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

профессор В. А. Зиновьев, Институт проблем передачи информации им. А. А. Харкевича РАН

кандидат физико-математических наук, А. Л. Пережогин, Институт математики им. С. Л. Соболева СО РАН

Ведущая организация: Санкт-Петербургский государственный университет аэрокосмического приборостроения

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

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

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

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

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

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

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

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

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

~Г_1

п = ¡-, г > 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

да Хэмминга с помощью некоторой функции А : Н~2~~ —у {0,1} (которая, вообще говоря, может быть нелинейной). Код Васильева V" может быть, с точностью до эквивалентности, представлен в виде

V\ = {(N + + У'€ Fу е и(1)

для некоторой функции А : УГ^г -> {0,1}. Первое существенное улучшение нижней границы числа известных кодов Васильева было получено в 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{2r). Если совершенный (расширенный совершенный) код является кодом Хэмминга длины п (расширенным кодом Хэмминга длины N), то соответствующая ему система троек (четверок) Штейнера называ-

8 Doyen J., Hubaut X., Vandensavel M. Ranks of incidence matrices of Steiner

triple systems // Math. 1978. S. Z. N 163. P. 251-259. 9 Teirlinck L. On projective and affine hyperplanes // J Combin. Theory. 1980. S. A. N 28. P. 290-306. 10 Мак-

Вильямс Ф. Док., Слоэн Н. Дж. Теория кодов, исправляющих ошибки. Пер. с англ. М.: Связь. 1979. 744 с.

ется Хэмминговой системой троек Штейнера STS(H,n) (Хэм-минговой системой четверок Штейнера SQS("H, N)). Если для некоторой системы троек Штейнера STS(n) существует приведенный совершенный двоичный код С, носители всех кодовых слов веса 3 которого образуют данную STS(n), то указанную систему троек Штейнера будем называть вложимой в совершенный код С. Понятие системы четверок Штейнера, вложимой в расширенный совершенный двоичный код, определяется аналогично.

В 2007 - 2009 гг. П. Р. Остергардом и О. Поттоненом11,12 было доказано, что только 33 из 80 неизоморфных систем троек Штейнера порядка 15 являются вложимыми в совершенный код, и только 15590 из 1054163 неизоморфных систем четверок Штейнера порядка 16 вложимы в расширенный совершенный код.

В. Д. Тончевым13 найдено число различных систем троек Штейнера порядка 2Г — 1 ранга 2Г — г, что на 1 превышает минимально возможный ранг. Тем же автором14 получена аналогичная формула для числа различных систем четверок Штейнера порядка 2Г ранга 2г — г. Задача вложимости систем троек (четверок) Штейнера в совершенные (расширенные совершенные) двоичные коды В. Д. Тончевым не рассматривалась. Первые результаты, посвященные этой проблеме, принадлежат В. А. Зиновьеву и Д. В. Зиновьеву15, где доказано, что все системы четверок Штейнера порядка 2Г, г > 3, ранга 2Т — г (т.е. ранга " + 1") вложимы в расширенные коды Васильева длины 2Г такого же ранга. В.А. Зиновьевым и Д.В.

11 Östergärd P. R. J., Pottonen О. The perfect binary one-error-correcting codes of length 15: Part 1 - Classification // IEEE Trans. Inform. Theory. 2009. N 55.

P. 4657-4660. 12 Östergärd P. R. J., Pottonen O. There exist Steiner triple systems of order 15 that do not occur in a perfect binary one-error-correcting code // Journal of Combin. Designs. 2007. V. 15. P. 465-468. 13 Tonchev V. D. A

mass formula for Steiner triple systems STS(2n - 1) of 2-rank 2n - n // Journal of

Combin. Theory. 2001. Series A. N 95. P. 197-208. 14 Tonchev V. D. A formula for

the number of Steiner quadruple systems on 2n points of 2-rank 2" — n // Journal of Combin. Designs. 2003. N 11. P. 260-274. 15 Зиновьев В. А., Зиновьев Д. В. О кодах Васильева длины п = 2т и удвоение систем Штейнера 5(га, 4,3) заданного ранга // Пробл. передачи информ. 2006. Т. 42. Вып. 1. С. 13-33.

Зиновьевым16'17 показано, что все системы троек Штейнера порядка 2Г — 1, г > 3, ранга 2Г — г +1 вложимы в некоторые совершенные двоичные коды, но остается неясным ранг таких кодов.

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

Отображение / : С —> С', где С, С' - равномощные коды пространства Fg, называется изометрией кода С в код 1(C) = С', если выполняется d(x,y) = d(I(x), 1(у)) для всех кодовых слов х, у из С, где d — расстояние Хэмминга. Два кода С и D из F™ называются эквивалентными, если существует изометрия пространства F™, переводящая код С в код D.

Хорошо известно, что автоморфизмы пространства F™ исчерпываются всеми изометриями F™ и выглядят следующим образом:

Aut(F£) = {(тг; o-i,..., ап) : тг € Sn, сг, е Sg, 1 < i < п},

где Sn и S(] - симметрические группы порядка тг и q соответственно.

В литературе известно несколько определений метрической жесткости. Наиболее общим является следующее: код С С называется18'19,20 метрически жестким, если всякая изометрия I : С —> С', для любого кода С', равномощного коду С, продолжается до изометрии (автоморфизма) пространства F^. Код С С F™ - метрически жесткий в слабом смысле, если всякий код С" = 1(C) эквивалентен коду С. Наконец, код С С F™ называется метрически

16 Zinoviev D. V., Zinoviev V. A. Steiner Triple Systems S(2m - 1,3,2) of 2-rank

r < 2m — m + 1: Construction and Properties // Proc. of 13th Int. Workshop on Algebraic and Combinatorial Coding Theory (Pomorie, Bulgaria. June 15-21, 2012). P. 358—363. 17 Zinoviev V. A., Zinoviev D. V. Steiner Triple Systems

S(2m - 1,3,2) of Rank 2m - m + 1 over F2 // Problems of Inform. Transm. 2012. V. 48. N 2. P. 102-126. 18 Августинович С. В. Об изометричности плотно упакованных бинарных кодов // Труды института математики. СО

РАН. 1994. Т. 27. С. 3-5. 19 Solov'eva F. /., Avgustinovich S. V., Honold. Т., Heise W. Metrically rigid codes // Proc. of 6th Int. Workshop on Algebraic and Combinatorial Coding Theory. (Pskov, Russia. Sept. 6-12, 1998). P. 215-219.

20 Solov'eva F. I., Avgustinovich S. V., Honold Т., Heise W. On the Extendability of Code Isometries // J. of Geometry. 1998. V. 61. N 1/2. P. 3-16.

жестким в узком смысле, если для всякой изометрии I : С —> С существует некоторая изометрия I' пространства Р™, такая, что I и V на словах кода С действуют одинаково, т.е. 1\с = 1'\с-

Если код не является метрически жестким (метрически жестким в слабом смысле, метрически жестким в узком смысле), будем называть его метрически нежестким (метрически нежестким в слабом смысле, метрически нежестким в узком смысле).

Исследования метрической жесткости кодов начаты в 1994г. С. В. Августиновичем, которым была доказана метрическая жесткость в слабом смысле совершенных двоичных кодов длины больше 15. Хорошо известно, что некоторые двоичные коды Адамара длины п > 16, полученные из матриц Адамара одного порядка заменой 1 на 0 и —1 на 1 являются метрически нежесткими, поскольку существуют такие неэквивалентные матрицы и, соответственно, неэквивалентные коды Адамара. В 1998 г. Ф. И. Соловьева, С. В. Августинович, Т. Хонольд, В. Хайзе доказали, что:

а) все совершенные д-ичные коды являются метрически жесткими, за исключением двоичного кода Хэмминга длины 7 и троичного кода Хэмминга длины 4;

б) все д-ичные (п, п — 1) МРЗ-коды являются метрически жесткими, за исключением двух кодов длины 3 и одного кода длины 4;

в) все д-ичные 2) и (с/+1,2) М 1)5-коды являются метрически нежесткими, за исключением (2,2) и (3,2) МИБ-кодов;

г) двоичный линейный код с параметрами (п, 2П_1,2) является метрически жестким тогда и только тогда, когда п ф 4.

Теми же авторами в 1998 г. установлено, что полные равновесные д-ичные коды являются метрически жесткими. В 2003 г. С. В. Августинович и Ф. И. Соловьева21 установили, что при п > кА каждый приведенный двоичный код, содержащий 2-(п, к, А)-схему, является метрически жестким. Поскольку любая ¿-(и, к, А)-схема, Ь > 2, является 2-(г>, к, А')-схемой, то любой приведенный код, содержащий к, А)-схему, также является метрически жестким. Поэтому все расширенные примитивные коды БЧХ и расширенные совершенные коды являются метрически жесткими. Этим свойством обладают и равномерно упакованные коды, удовлетворяю-

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

щие условию в, — р > 2, где (1 - кодовое расстояние, р - радиус покрытия, к которым относятся такие важные классы кодов, как коды БЧХ с расстоянием 5 и 7, коды Препараты в широком смысле, коды Геталса в широком смысле с расстоянием 7, а также соответствующие им расширенные коды.

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

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

Научная новизна.

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

1. Предложена новая итеративная свитчинговая конструкция для систем троек Штейнера. С помощью свитчингового подхода, найдена классификация систем троек Штейнера 8Т8(п) порядка п = 2Г — 1, г > 3, ранга не больше n—\og(n + 1) + 2, вложимых в совершенные двоичные коды длины п такого же ранга. Приведены нижняя и верхняя оценки для числа таких различных систем троек Штейнера порядка п. Доказано также, что любая система троек Штейнера порядка п ранга п—кщ(п + 1) + 1 вложима в совершенный код длины п такого же ранга, и этим кодом является код Васильева. Кроме того, описан класс различных систем троек Штейнера порядка п ранга п—к^(п+ 1) + 2, не вложимых в совершенные двоичные коды длины п ранга п—+ 1) + 2, а также приведена нижняя оценка числа таких систем.

Хорошо известно, что при удалении одного и того же произвольного элемента из всех блоков любой фиксированной системы четверок Штейнера порядка N получившееся множество троек является системой троек Штейнера порядка ./V — 1. В то же время, несмотря на приведенное свойство и на тот факт, что результаты для систем троек и четверок Штейнера имеют аналогичные форму-

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

2. Разработан новый итеративный свитчинговый метод построения систем четверок Штейнера, являющийся модификацией метода Линднера. С помощью свитчингового подхода, дана классификация систем четверок Штейнера БС^Б^) порядка N = 2Г, г > 3, ранга не больше /V—-I-1, вложимых в расширенные совершенные двоичные коды длины N такого же ранга. В работе приводятся верхняя и нижняя оценки числа таких различных систем четверок Штейнера порядка N. Описан класс различных систем четверок Штейнера порядка N ранга N—logN + 1, не являющихся вложи-мыми в расширенные совершенные двоичные коды длины N ранга N—logN + 1, найдена нижняя оценка числа таких систем.

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

Научная и практическая значимость. Результаты работы являются теоретическими и могут быть применены в теории коди-

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

Апробация работы. Все результаты диссертации докладывались на следующих конференциях: на международных конференциях по алгебраической и комбинаторной теории кодирования АССТ-ХП (Новосибирск, Россия, 2010 г.) и АССТ-ХШ (Поморие, Болгария, 2012 г.); на конференции "Современные проблемы математики, информатики и биоинформатики" (Академгородок, Новосибирск, Россия, 2011 г.); на конференции "Информационные технологии и системы" (Петрозаводск, Россия, 2012 г.); на конференции "Мальцевские чтения" (Академгородок, Новосибирск, Россия, 2012 г.); на молодежной школе-семинаре "Дискретные модели и методы принятия решений" (Академгородок, Новосибирск, Россия, 2013 г.). Результаты диссертации были доложены на семинаре кафедры "Комплексной защиты информации" СПбГУАП и на семинарах "Теория кодирования" и "Дискретный анализ" НГУ и Института математики СО РАН. Отдельные результаты диссертации отмечены грантом Президента РФ для молодых российских ученых в 2011-2012 гг., а также грантом "Академическая мобильность" Российского Фонда Фундаменальных Исследований в 2012 году.

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

1. Предложены итеративные свитчинговые конструкции систем троек и четверок Штейнера.

2. Приведены классификации систем троек и четверок Штейнера порядков п = 2г — 1,г>ЗиА/" = п+1 ранга не больше n—log(n + 1) + 2, вложимых в совершенные и расширенные совершенные двоичные коды длины п и N таких же рангов соответственно. Найдены нижние и верхние оценки для числа таких различных систем троек и четверок Штейнера порядков пи N соответственно.

3. Доказано, что произвольная система троек Штейнера поряд-

ка п ранга п — log{n + 1) + 1 вложима в некоторый совершенный код Васильева длины тг такого же ранга.

4. Построены классы различных систем троек и четверок Штей-нера порядков п и N ранга п—log(n + 1) + 2, не вложимых в совершенные и расширенные совершенные двоичные коды длины пи N соответственно такого же ранга. Приведены нижние оценки числа таких систем.

5. Доказано, что два класса <?-ичных эквидистантных кодов, один класс двоичных эквидистантных кодов, а также коды, отвечающие одному классу аффинно разрешимых схем, являются метрически нежесткими.

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

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

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

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

В первой главе предложен новый итеративный свитчинговый метод построения класса систем троек Штейнера STS(n) порядка п = 2г — 1, г > 3. Доказана вложимость данного класса STS(n) ранга не более тг—log(n+1) + 2 в совершенные двоичные коды длины п такого же ранга, найдены нижняя и верхняя оценки числа таких систем троек Штейнера. Также приведены различные системы троек Штейнера порядка п ранга п—log(n+l)-(-2, не вложимые

в совершенные двоичные коды длины п такого же ранга. Указана нижняя оценка числа таких систем троек Штейнера.

В параграфе 1.1 приведены основные понятия, относящиеся к методу свитчингов для совершенного кода, такие, как свитчинг в коде, ¿-компонента кода, у'¿-компонента кода, свитчинг в системе троек Штейнера. Приведем определения этих понятий.

В общем случае говорят, что код С" = (C\R) U R' получен свит-чингом множества R на множество R' в двоичном коде С, если код С' имеет те же параметры, что и С. Такое множество R называется компонентой кода С. Более подробно, пусть R - произвольное подмножество совершенного двоичного кода С. Свитчингом множества R по г-ой координатной позиции называется замена значения г-й координатной позиции всех векторов множества R. Получившееся в результате такого свитчинга множество будем обозначать через R + i (такое множество часто обозначается22 через R + ei, где ег - вектор веса 1 с ненулевой г-й координатной позицией, но в диссертации, в целях более удобного изложения, используется первое обозначение).

Пусть K{R) - множество всех векторов из Fn, находящихся на расстоянии не больше 1 от R. Множество R называется г-компонентой совершенного кода С, если K(R) = K(R 4- г). Полученный в результате новый совершенный код С' = (С \ R) U (R. + г) имеет те же параметры, что и С. В этом случае говорят, что код С' получен из кода С свитчингом ¿-компоненты R. Пусть а С {1,..., п}. Множество R называется а-компонентой совершенного кода С, если R является ¿-компонентой для любого i G а.

Понятие свитчинга для t-(v, к, 1)-схемы определяется аналогично понятию свитчинга в коде. Два множества R и R', состоящие из k-элементных подмножеств множества V, называются равновесны-

по

ми , если каждое неупорядоченное подмножество из t элементов, которое может быть найдено в fc-элементных подмножествах одного множества, встречается также и в ¿-элементных подмножествах другого множества. Говорят, что t-(v, к, 1)-схема А' = (A\R) U R' получена свитчингом множества блоков R на множество блоков R'

22 Solov'eva F. I. On perfect codes and related topics // Com2Mac Lecture Note

Series 13, Pohang. 2004. 80 P. 23 Петренюк А. Я. Признаки неизоморфности систем троек Штейнера // Укр. матем. ж. 1972. Т. 24. Вып. 6. С. 772-780.

в t-(v,k, 1)-схеме А, если R и R' - равновесные множества. Такое множество R (равно как и множество R') В. А. Зиновьев и Д. В. Зиновьев24 называют компонентой.

Понятие свитчинга для системы троек Штейнера определяется как частный случай свитчинга для t-(v, к, 1)-схемы. Говорят, что система троек Штейнера STS'(n) = (STS(n)\R) U R' получена свитнингом множества блоков R на множество блоков R' в STS(n), если R и R' - равновесные множества, т.е. каждая пара элементов, которая может быть найдена в тройках множества R, встречается также и в тройках множества R'.

В параграфе 1.2 приведена итеративная свитчинговая конструкция систем троек Штейнера, позволяющая из произвольной системы троек Штейнера порядка т = l,3(rnod6) строить систему троек Штейнера порядка п = 4т + 3. В частности, с помощью этого метода можно из Хэмминговой системы троек Штейнера порядка т строить Хэммингову систему троек Штейнера порядка п.

Также указаны определенные правила (обозначенные в работе через Al, А2, Bl, В2, ¡33), позволяющие делать свитчинги Паш-конфигураций исходной системы троек Штейнера порядка п, построенной по указанному методу из произвольной системы троек Штейнера порядка т. Приведенные правила позволяют получать различные системы троек Штейнера порядка п разного ранга, превосходящего ранг Хэмминговой системы троек Штейнера. Обозначим класс таких систем троек Штейнера порядка п ранга г через Sw(STS(n),r). Через Sw(STS(n),r) обозначим подкласс класса Sw(STS(n),r), содержащий системы троек Штейнера порядка п ранга г, которые получены из произвольной системы троек Штейнера порядка п посредством правил -41, Bl, В2.

Найдена нижняя оценка числа различных STS(n), построенных с помощью приведенной конструкции.

Теорема 1. Для числа R(n) всех различных STS(n), п = 4т+3, т > 3, лежащих в классах Sw(STS(n),r) при всех г > п—1од(п + +1), верно R(n) > (ci • п ■ 2"/2 • 3ю("2-10")/9б) . п(п - 1)/12 • R{{n -3)/4)(1 - о(1)), где ci = 2"219/96 • 15521/96.

24 Зиновьев В. А., Зиновьев Д. В. Системы Штейнера S(v, k, k — 1): компоненты и ранг // Пробл. передачи информ. 2011. Т. 47. № 2. С. 52-71.

Параграфы 1.3 и 1.4 посвящены вопросу вложимостп построенных в параграфе 1.2 систем троек Штейнера в совершенные коды и основаны на свитчинговом методе (С. В. Августинович, Ф. И. Соловьева, 1997 г.) построения совершенных кодов.

Основные идеи этого метода состоят в следующем. Пусть множество а содержится в множестве {1, 2,..., п} для некоторого числа п. Предположим, что имеется некоторый совершенный код длины п, разбитый на а- и ¿-компоненты, причем г € а. Сначала для каждой а-компоненты выбирается элемент г из множества а и производится свитчинг произвольного числа г-компонент этой а-компоненты на множество новых г-компонент той же самой мощности. После этого можно заменить (или не менять) полученную а-компоненту на новую а-компоненту с помощью свитчингов неиспользованных ранее координат из множества а. В результате получается совершенный код, который является отличным от первоначального совершенного кода, или даже неэквивалентным ему. Часто в качестве первоначального кода используют код Хэмминга

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

Следующее утверждение позволяет производить свитчинги г- и ¿^¿-компонент в коде Хэмминга.

"Утверждение 1. (С. В. Августинович, Ф. И. Соловьева7) Код

N2

Хэмминга Нп представим в виде Нп = и где - различ-

ные непересекающиеся г^к-компоненты, = Я^к-

В параграфе 1.4 приведены оценки для числа систем троек Штейнера порядка п рангов не больше n—\og{n + 1) + 2, вложи-мых в совершенные двоичные коды таких же рангов, а также для числа систем троек Штейнера порядка п ранга тг—к^(п + 1) + 2, не вложимых в совершенные двоичные коды таких же рангов.

В. Д. Тончевым в 1997 г. было получено число /?1 (п) различных систем троек Штейнера порядка п ранга не больше п—к^(п+1) +1:

Д!(п) = " ^ - . п\/\Зут(Н^)\, где Бут^)

— группа симметрий кода Хэмминга ~Н 2 . С помощью этой работы,

используя известную конструкцию Ассмуса-Маттсона25 для систем троек Штейнера, вложимых в коды Васильева, а также результаты работы С. В. Августиновича, Ф. И. Соловьевой, У. Хедена 2005 г., доказана следующая

Теорема 2. Любая система троек Штейнера порядка п > 15, ранга n—log{n +1) +1 вложима в совершенный код длины п такого же ранга, а именно, в код Васильева V™.

Пусть Q(n) = (С2 • 2"/2 • 130("2-10")/96) • - о(1)), где

С2 = 2-47/96 • 6521/9б, и S(n) = 2lSTS(^)l • п\/2^ • iSymin^l Д. С. Кротовым, В. Н. Потаповым26 доказано, что любой совершенный двоичный код С длины п ранга не больше n—log(n +1) + 2 может быть получен из некоторого кода Хэмминга последовательными свитчингами г-компонент не более чем по двум координатным позициям г. С помощью данного результата, утверждения 1, описанной в параграфе 1.2 конструкции и правил для свитчин-гов этой конструкции доказана теорема, представляющая системы троек Штейнера, вложимые в совершенные коды, построенные методом ¿jfc-комионент из двоичного кода Хэмминга:

Теорема 3. Любая система троек Штейнера порядка п = 4m + 3, т > 63, из класса Sw{STS(n),n—log(n+1) + 2), вложима в некоторый совершенный двоичный код длины п такого же ранга. Число В,2(п) таких различных систем троек Штейнера удовлетворяет неравенствам Q(n) ■ R(H, (n — 3)/4) — S(n) < i?2(n) < Q(n) ■ R(H, n) - S(n), где R{4, n) = n!/(n(n - l)(n + 1 - 22)(n + 1 -■ ... • (n + l)/2) - число различных кодов Хэмминга длины п. Отсюда вытекает следующее утверждение о системах троек Штейнера, не вложимых в совершенные коды, построенные методом г^Тс-компонент из двоичного кода Хэмминга.

Следствие 1. Системы троек Штейнера порядка п — 4ш + 3, полученные свитчингами по правилам А2 и (или) ВЗ (в сочетании с правилами ¡31, В2 или Al соответственно), применёнными к Хэмминговой системе троек Штейнера порядка п, не вложи-мы в совершенные коды, построенные методом свитчингов ijk-

25 Assmus Е. F., Mattson Н. F. Jr. On tactical configurations and error correcting

codes 11 Journal of Combin. Theory. 1967. N 2. P. 243-257. 26 Кротов Д. С.,

Потапов В. Н. О свитчинговой эквивалентности n-арных квазигрупп порядка

4 и совершенных двоичных кодов //Пробл. передачи информ. 2010. Т. 46. № 3.

С. 22-28.

компонент из двоичного кода Хэмминга длины п.

Также найдена нижняя оценка для числа систем троек Штей-нера порядка п ранга п—log(n+1) + 2, не вложимых в совершенные коды длины n такого же ранга. Пусть Р(п) — (((n + 1) • +

2п - 6) • 3io(n2-iO"+2i)/3.25 _3п + 9у _ 12

"Утверждение 2. Число различных систем троек Штейнера порядка п > 511 ранга n—log(n+1)+2, не вложимых в совершенные коды длины п ранга n—log(n + 1) + 2, можно оценить снизу как Р{п) ■ R{M, (п - 3)/4) - Q(n) ■ R(H, п).

Заметим, что в связи с результатами В. А. Зиновьева и Д. В. Зиновьева 2012 г., указанные в Утверждении 2 системы троек Штейнера порядка п ранга п—log(n + 1) + 2 вложимы в совершенные двоичные коды длины тг больших рангов.

Во второй главе исследуются вопросы, аналогичные рассматриваемым в главе 1, но для систем четверок Штейнера.

В параграфе 2.1 приводятся основные понятия, относящиеся к методу свитчингов в расширенном совершенном коде, такие, как свитчинг множества по двум координатным позициям, И- и ijkl-компонента расширенного кода, свитчинг в системе четверок Штейнера. Приведем определения этих понятий.

Свитчингом множества R по г-ой и I-ой координатным позициям называется замена значения г-й и 1-й координатных позиций всех векторов множества R. Получившееся в результате такого свитчинга множество будем обозначать через R + г + I.

Пусть R и R' - два множества из определения свитчинга в произвольном двоичном коде, данного при описании параграфа 1.1. Множество R называется И-компонентой расширенного совершенного двоичного кода С длины N, полученного из С расширением по 1-ой координатной позиции, если R' — R + г + I для некоторого i (Е {1,2,..., N}. Множество R называется ijkl-компонентой кода С, если R является í^-компонентой для любых Í1,Í2 S {i,j,k,/}.

Понятие свитчинга для системы четверок Штейнера определяется аналогично понятию свитчинга для расширенного совершенного двоичного кода. Два множества R и R', состоящие из 4-элементных подмножеств множества U = {1,2,..., N}, называются равновесными, если каждая тройка элементов, встречающаяся в четверках одного множества, может быть найдена также и в чет-

верках другого множества. Говорят, что система четверок Штей-нера SQS'(N) = (SQS(N)\R) U R' получена свитчингом множества блоков R на множество блоков R' в SQS(N), если R и R' -равновесные множества. В. А. Зиновьев и Д. В. Зиновьев также называют такие множества R и R' компонентами.

В параграфе 2.2 приведена свитчинговая конструкция систем четверок Штейнера. Данная конструкция позволяет из произвольной системы четверок Штейнера порядка т = 2,4(mod6) строить систему четверок Штейнера порядка N = 4т, в том числе, из Хэм-минговой системы четверок Штейнера порядка m получать Хэм-мингову систему четверок Штейнера порядка N.

С помощью упомянутой выше работы С. В. Августиновича, Ф. И. Соловьевой, 1997 г., доказана следующая лемма о разбиении на компоненты Хэмминговой системы четверок Штейнера:

Лемма 2. Пусть k,l} - носитель любого вектора ве-

са 4 произвольного расширенного двоичного кода Хэмминга длины N. Тогда Хэммингова система четверок Штейнера SQS{1-L, N) представима в виде объединения подмножеств 1 + N(N — 4)(N — 8)/(3-29) непересекающихся ijkl-компонент, каждая из которых, в свою очередь, является объединением подмножеств либо N/4 + (N — 4)(N — 8)/25, либо 8 непересекающихся И-компонент.

Также в параграфе 2.2 указаны свитчинги компонент исходной Хэмминговой системы четверок Штейнера порядка N, позволяющие получать различные системы четверок Штейнера порядка N различного ранга, превосходящего ранг Хэмминговой системы четверок Штейнера. Обозначим класс таких систем четверок Штейнера порядка N ранга г через Sw(SQS(N),r). Доказано, что классы Sw(SQS(N),r) при N - logN - 1 < г < N - logN + 1 вложимы в расширенные совершенные коды, полученные методом свитчин-гов zj/d-KOMnoiieiiT из расширенного кода Хэмминга HN. Найдена нижняя оценка числа таких различных SQS(N):

Теорема 4. Для числа R2(N) различных систем четверок Штейнера из классов Sw(SQS(N),r) при N — logN — 1 < г < N — logN + 1, вложимых в расширенный совершенный код, верно

R2(N) > (З2 ■ 2« - S)"3-1^432" . 2^ • . R(fl,N/4).

■(l-o(l)),

zdeR{Ü,N/4) = (JV/4)!/((iV/4— l)(iV/4 — 2)(iV/4 — 22) •... • (iV/4)/2) - число различных SQS(H,N/4).

Параграф 2.3 посвящен вопросу вложимости построенных в параграфе 2.2 систем четверок Штейнера порядка N ранга не более N— logiV + 1 в расширенные совершенные двоичные коды такого же ранга. Приведены нижняя и верхняя оценки числа таких систем четверок Штейнера.

Известен факт6, что расширенный код Васильева длины N имеет ранг N— log N. В диссертации, с помощью свитчингового подхода, доказано, что всякая система четверок Штейнера SQS(N) ранга N— logAT вложима в некоторый расширенный совершенный двоичный код длины N такого же ранга, и таким кодом является расширенный код Васильева.

Теорема 5. Любая система четверок Штейнера порядка N ранга N — logN вложима в некоторый расширенный совершенный код Васильева длины N такого же ранга.

Заметим, что другое доказательство этого факта, использующее каскадный метод, в отличие от рассматриваемого в данной работе свитчингового метода, было ранее опубликовано В.А. Зиновьевым и Д.В. Зиновьевым27.

Известно26, что всякий расширенный совершенный двоичный код длины N ранга не больше N—logJV + 1 может быть получен из некоторого расширенного кода Хэмминга свитчингами il-компонент не более чем по двум парам координатных позиций.

Пусть P(N) = (З2 • 2« - S)"3-"^ . ■ -

о(1)), a S{N) = 2l5Qs(f)l"f ■ N\/\Sym{H,%)\. Справедлив следующий основной результат данной главы:

Теорема 6. Класс Sw(SQS(N), N - logN + 1), N> 64, совпадает с классом систем четверок Штейнера порядка N, вложи-мых в расширенные совершенные двоичные коды такого же ранга, построенные методом ijkl-компонент из расширенного кода Хэмминга длины N. Число R2(N) таких различных систем четверок Штейнера удовлетворяет неравенствам

P(N) ■ R(H,N/4) - S(N) < R2{N) < P(N) ■ R(H,N) - S{N).

27 Зиновьев В. А., Зиновьев Д. В. О кодах Васильева длины п = 2т и удвоение систем Штейнера S(n, 4,3) заданного ранга // Пробл. передачи информ. 2006. Т. 42. Вып. 1. С. 13-33.

В параграфе 2.4 приведены системы четверок Штейнера порядка N ранга N— logiV+1, не вложимые в расширенные совершенные двоичные коды ранга N— log N + 1, и доказана следующая

Теорема 7. Для числа R (N) различных систем четверок Штейнера порядка N > 128 ранга N — logN + 1, не вложимых в расширенные совершенные двоичные коды, построенные методом ijkl-компонент из расширенного двоичного кода Хэмминга, верно

Я' (N) > (591ДГ2 + 9456ЛГ)&■ (N3 - 12JV2 + 32N) • Щ- • ЦП, f)(1 - о(1)).

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

В параграфе 3.1 приведены основные понятия, касающиеся метрической жесткости кодов.

Группой автоморфизмов Aut(C) кода С называется совокупность автоморфизмов пространства F™, переводящих код в себя: Aut(C) = {(тг; <7Ь ..., О е Aut(F£) : ..........ап){С) = С}.

Эквидистантным кодом с расстоянием d называется код, в котором расстояние между любыми двумя кодовыми словами совпадает и равно d.

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

Нетрудно увидеть отличие определений метрической жесткости и метрической жесткости в слабом смысле на примере кода Хэмминга длины 7. Код Хэмминга длины 7 метрически жесткий в слабом смысле, поскольку он единствен с точностью до эквивалентности. С другой стороны, код Хэмминга является метрически

нежестким в силу того, что мощность множества его изометрий, фиксирующих нулевое слово, больше мощности группы симметрий этого кода. Отличие определений метрической жесткости и метрической жесткости в узком смысле покажем на следующем примере. Рассмотрим двоичный код С = {0000,1100,1010,1001}. Легко проверить, что всякая изометрия кода С, переводящая этот код в себя, продолжаема до изометрии всего пространства F4. Следовательно, данный код является метрически жестким в узком смысле. С другой стороны, он метрически нежесткий в слабом смысле, поскольку существует код, например, код D = {0000,1100,1010,0110}, изо-метричный коду С, но не эквивалентный ему.

В параграфе 3.2 доказана метрическая нежесткость некоторых классов кодов.

Теорема 8. Эквидистантный код с параметрами (q, (q—l)2, q— l)q, где q> 5, q и q — 1- степени простых чисел, является метрически нежестким.

Теорема 9. Оптимальный q-ичный эквидистантный код с параметрами , g2/x, qn)q, где q > 3, /х > 1, является метрически нежестким.

Теорема 10. Эквидистантные коды с параметрами (п, [^р], d), при \/16 + 4п—4 < d < п/2, d = 0 (mod 2), являются метрически нежесткими.

Также доказана метрическая нежесткость кодов, соответствующих одному классу аффинно-разрешимых схем:

Теорема 11. Код, отвечающий аффинно разрешимой схеме с параметрами (n,qs, s,qfi, А), где п = q^/jL, q > 3, s > п ■ Cq, Cg = log2n/log2(q\ ■ n), является метрически нежестким.

Результаты первой главы были получены совместно с Ф.И. Соловьевой и Е.С Филимоновой и опубликованы в работах [3], [7], [8]. Результаты второй главы, за исключением результатов параграфа 2.4, получены совместно с Ф.И. Соловьевой. Результаты второй главы опубликованы в [2], [4], [6], [7], [10].

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

фессору В. А. Зиновьеву за полезные обсуждения и замечания.

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

1. Ковалевская Д. И. О метрической жесткости некоторых классов кодов // Пробл. передачи информ. 2011. Т. 47. Вып. 1. С. 19—32.

2. Ковалевская Д. И., Соловьева Ф. И. О системах четверок Штейнера малого ранга, вложимых в расширенные совершенные двоичные коды // Дискрет, анализ и исслед. операций. 2012. Т.19. № 5. С. 47-62.

3. Ковалевская Д. И., Соловьева Ф. И., Филимонова Е. С. О системах троек Штейнера малого ранга, вложимых в совершенные двоичные коды // Дискрет, анализ и исслед. операций. 2013. Т.20. № 3. С. 3-25.

4. Ковалевская Д. И., Соловьева Ф. И. Системы четверок Штейнера малых рангов и расширенные совершенные двоичные коды // Дискрет, анализ и исслед. операций. 2013. Т.20. № 4. С. 46—64.

5. Kovalevskaya D. I. On metrical rigidity of some classes of codes // Proc. of 12th Int. Workshop on Algebraic and Combinatorial Coding Theory (Novosibirsk, Russia. Sept. 5-11, 2010). Novosibirsk: Sobolev Inst, of Math. 2010. P. 189-194.

6. Ковалевская Д. И., Соловьева Ф. И. О системах четверок Штейнера малого ранга, вложимых в расширенные совершенные коды // Современные проблемы математики, информатики и биоинформатики (Академгородок, Новосибирск, Россия. 11-14 октября 2011). http://conf.nsc.ru/files/conferences/Lyap-100/abstracts/744 71/74521/ KovalSol_Theses.pdf.

7. Kovalevskaya D. I., Filimonova E. S., Solov'eva F. I. Steiner triple (quadruple) systems of small ranks embedded into perfect (extended perfect) binary codes // Proc. of 13th Int. Workshop on Algebraic and Combinatorial Coding Theory (Pomorie, Bulgaria. June 15-21, 2012). Bulgaria: Institute of Mathematics and Informatics BAS. 2012. P. 203-208.

8. Ковалевская Д. И., Соловьева Ф. И., Филимонова Е. С. Систе-

мы троек Штейнера малого ранга и совершенные двоичные коды // Информационные технологии и системы (Петрозаводск, Россия. 19-25 августа, 2012). http://www.itas2012.iitp.ru/pdf/1569601371.pdf.

9. Ковалевская Д. И., Соловьева Ф. И. О системах четверок Штейнера малых рангов и расширенных совершенных двоичных кодах // Мальцевские чтения (Академгородок, Новосибирск, Россия. 12-16 ноября, 2012). http://www.math.nsc.ru/conference/malm eet/12/malmeet2012 .pdf.

10. Ковалевская Д. И. Системы Штейнера малых рангов и совершенные двоичные коды // Материалы школы-семинара "Дискретные модели и методы принятия решений" (Академгородок, Новосибирск, Россия. 21-23 июня, 2013). Новосибирск: издательство Института математики. 2013. С. 263-264.

Ковалевская Дарья Игоревна

О вложимости систем Штейнера в совершенные коды

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

Подписано в печать 24.10.2013 г. Печать цифровая. Бумага офсетная. Формат 60x84/16. Усл. печ. л. 3 Тираж 100 экз. Заказ № 180

Отпечатано в типографии «Срочная полиграфия» ИП Малыгин Алексей Михайлович 630090, Новосибирск, пр-т Академика Лаврентьева, 6/1, оф. 104 Тел. (383) 217-43-46, 8-913-922-19-07

РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ НАУКИ ИНСТИТУТ МАТЕМАТИКИ им. С. Л. Соболева

О ВЛОЖИМОСТИ СИСТЕМ ШТЕЙНЕРА В СОВЕРШЕННЫЕ КОДЫ

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

кибернетика

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

04201451259

УДК 519.1

Ковалевская Дарья Игоревна

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

Научный руководитель: д.ф.-м.н., проф. Ф. И. Соловьева

Новосибирск - 2013

Оглавление

Введение 4

1 Системы троек Штейнера малого ранга и совершенные

двоичные коды 24

1.1 Основные понятия....................... 25

1.2 Конструкция систем троек Штейнера............ 27

1.3 Вложимость S(T,n) в совершенный код........... 38

1.4 Число различных STS(n) рангов не больше п— log(n+l) + 1 и п—log(n + 1) + 2, вложимых в совершенные двоичные коды............................... 44

2 Системы четверок Штейнера малых рангов и расширенные совершенные двоичные коды 51

2.1 Основные определения..................... 53

2.2 Системы четверок Штейнера SQS(4m). вложимые в расширенные совершенные коды................. 55

2.3 Число различных SQS(N) рангов N—\ogN и N— log N + 1, вложимых в расширенные совершенные двоичные коды таких же рангов........................ 66

2.4 Системы четверок Штейнера, не вложимые в расширенные совершенные коды, построенные методом ¿^/-компонент . 76

3 О метрической жесткости некоторых классов кодов 84

3.1 Определения и понятия.................... 85

3.2 -Метрическая нежесткость трех классов эквидистантных кодов, а также кодов, соответствующих аффинно разрешимым схемам........................... 88

Заключение 103

Литература 104

Введение

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

Классификация систем Штейнера является одной из основных задач теории блок-схем. Известна классификация систем троек Штейнера порядка не больше 19, см. [25, 33]. Также открытым является вопрос о вложимости произвольной системы троек (четверок) Штейнера в некоторый совершенный (расширенный совершенный) двоичный код. Интересен также вопрос соответствия разных конструкций для систем троек (четверок) Штейнера с конструкциями для совершенных (расширенных совершенных) двоичных кодов, например, взаимосвязь свитчинговых и каскадных методов построения данных объектов.

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

точки зрения практического применения кодов для передачи информации и может найти применение в криптографии.

Основной целью данной работы является выяснение вопроса о том, какие системы троек и четверок Штейнера малых рангов вложимы в совершенные и расширенные совершенные двоичные коды таких же рангов, а также исследование вопроса метрической жесткости для некоторых классов кодов.

Хорошо известно, что при удалении одного и того же произвольного элемента из всех блоков любой фиксированной системы четверок Штейнера порядка N получившееся множество троек является системой троек Штейнера порядка А^ — 1. В то же время, несмотря на приведенное свойство и на аналогичные формулировки задач для систем троек и четверок Штейнера, методы решения этих задач не всегда могут быть напрямую перенесены с объектов одного вида на объекты другого вида. Системы четверок Штейнера являются более сложными объектами, чем системы троек Штейнера, и приведенные задачи, связанные с этими объектами, требуют различных способов решения.

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

1. Предложена новая итеративная свитчинговая конструкция для систем троек Штейнера. С помощью свитчингового подхода, найдена классификация систем троек Штейнера 5Т5"(п) порядка п = 2Г — 1, г > 3, ранга не больше n—\og(n + 1) + 2, вложимых в совершенные двоичные коды длины п такого же ранга. Приведены нижняя и верхняя оценки для числа таких различных систем троек Штейнера порядка п. Доказано также, что любая система троек Штейнера порядка п ранга n—log(n+1) +1 вложима в совершенный код длины п такого же ранга и этим кодом является код Васильева. Кроме того, описан класс различных систем троек Штейнера поряд-

ка п ранга n—\og(n + 1) + 2, не вложимых в совершенные двоичные коды длины п ранга n—\og(n + 1) + 2, а также приведена нижняя оценка числа таких систем.

2. Разработан новый итеративный свитчинговый метод построения систем четверок Штейнера, являющийся модификацией метода Линд-нера. Посредством свитчингового подхода, дана классификация систем четверок Штейнера БС^Б^) порядка ТУ = 2Г, г > 3, ранга N—\ogNJrl, вложимых в расширенные совершенные двоичные коды длины N такого же ранга. В работе приводятся верхняя и нижняя оценки числа таких различных систем четверок Штейнера порядка N. Также описан класс различных систем четверок Штейнера порядка N ранга А^—logУV + 1, не являющихся вложимыми в расширенные совершенные двоичные коды длины N ранга N—\ogN+l, и найдена нижняя оценка числа таких систем.

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

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

Все результаты диссертации докладывались на следующих конференциях: на международных конференциях по алгебраической и комбинаторной теории кодирования ACCT-XII (Новосибирск, Россия, 2010 г.) и ACCT-XIII (Поморие, Болгария, 2012 г.); на конференции "Современные проблемы математики, информатики и биоинформатики" (Академгородок, Новосибирск, Россия, 2011 г.); на конференции "Информационные технологии и системы" (Петрозаводск, Россия, 2012 г.); на конференции "Мальцевские чтения" (Академгородок, Новосибирск, Россия, 2012 г.); на молодежной школе-семинаре "Дискретные модели и методы принятия решений" (Академгородок, Новосибирск, Россия, 2013 г.). Результаты диссертации были доложены на семинаре кафедры "Комплексной защиты информации" СПбГУАП и на семинарах "Теория кодирования" и "Дискретный анализ" НГУ и Института математики СО РАН. Отдельные результаты диссертации отмечены грантом Президента РФ для молодых российских ученых в 2011-2012 гг., а также грантом "Академическая мобильность" Российского Фонда Фундаменальных Исследований в 2012 году.

Материалы диссертации опубликованы в 13 печатных работах, из них 4 статьи в рецензируемых журналах [55, 56, 57, 58], рекомендованных ВАК, и 4 работы в рецензируемых сборниках трудов конференций [59, 61, 62, 64].

Диссертация состоит из введения, трех глав, заключения и библиографии. Общий объем диссертации составляет 111 страниц. Библиография включает 67 наименований на 8 страницах.

Основные утверждения, выносимые на защиту:

1. Предложены итеративные свитчинговые конструкции систем троек и четверок Штейнера.

2. Приведена классификация систем троек и четверок Штейнера порядков п — 2Г —1, г > 3 и N = 2Г ранга не больше п—log(n+l)+2 =

= N — logN+1, вложимых в совершенные и расширенные совершенные двоичные коды длины п и N таких же рангов соответственно. Найдены нижняя и верхняя оценки для числа указанных различных систем троек и четверок Штейнера порядков п и N соответственно.

3. Доказано, что произвольная система троек Штейнера порядка п ранга п — login + 1) + 1 вложима в некоторый совершенный двоичный код Васильева длины п такого же ранга.

4. Построены классы различных систем троек и четверок Штейнера порядков пи N ранга п—log(n+1) + 2 = N — logN +1, не вложимых в совершенные и расширенные совершенные двоичные коды длины п и N соответственно такого же ранга. Приведены нижние оценки числа таких систем.

5. Доказано, что оптимальные д-ичные эквидистантные коды с параметрами {q■> gV; 9а0<? пРи Я ^ 3, ¡1 > 1, д-ичные эквидистантные коды с параметрами (q, (q — l)2, q — 1)9 при q > 5, где q и q — 1 -степени простых чисел, двоичные эквидистантные коды с параметрами (n, [^р], d) при условии у/16 + 4п — 4 < d < п/2, d = 0[mod 2), а также коды, отвечающие классу аффинно разрешимых схем с параметрами (n,qs, s,qfi, А), где п = д2/л, q > 3, s > п • с^, с^ = 1од2П/log2(ql ■ п). являются метрически нежесткими.

Приведем необходимые определения и понятия.

Пусть F™ - гг-мерное векторное пространство над полем Галуа GF(q) с метрикой Хэмминга. Кодом длины п называется произвольное подмножество метрического пространства F™. Для двоичного кода q = 2 будет опущено, вместо Fi; будем использовать ¥п. Элементы кода называются кодовыми словами. Хэммингово расстояние d(x,y) между векторами х.у из F™ определяется как число координат, в которых отличаются х и у. вес Хэмминга w(x) вектора х - как число ненулевых координатных позиций х. Множество ненулевых координатных позиций вектора

х Е называется носителем х и обозначается через зирр(х). Кодовым расстоянием (1 произвольного кода является наименьшее из расстояний Хэмминга между любой парой различных кодовых слов. Параметры произвольного д-ичного кода обозначаются через (п, М, сГ)д, где п - длина кодовых слов, М - мощность кода, (1 - кодовое расстояние; для двоичного кода д = 2 будет опущено. Непустое множество из называется двоичным кодом, векторное подпространство в - двоичным линейным кодом. Далее, в главах 1 и 2 будут рассматриваться лишь двоичные коды, в главе 3 - двоичные или д-ичные коды, что будет понятно из контекста. Код, содержащий нулевое кодовое слово, называется приведенным. Рангом приведенного кода называется размерность линейного подпространства пространства образованного векторами из этого кода.

Двоичный код С длины п называется совершенным кодом, исправляющим одну ошибку (далее, кратко - совершенным), если каждый вектор х из Fn находится на расстоянии не более 1 ровно от одного кодового слова С. Пусть С - расширенный совершенный код, полученный из совершенного кода С длины 2Г — 1, г > 2, добавлением общей проверки на четность (т.е. добавлением координаты, равной сумме остальных по модулю 2). Далее, в главах 1 и 2, будут рассматриваться только приведенные совершенные и приведенные расширенные совершенные двоичные коды.

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

„Г _ ^

Хэмминга имеют следующие параметры: длина п = т > 1. чис-

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

мерности 6 с расстоянием 5. В. А. Зиновьев и В. К. Леонтьев в 1972 г., см. [15] и независимо А. Титвайнен в 1973 г., см. [47], доказали, что любой нетривиальный совершенный код имеет параметры кода Хэмминга либо кода Голея. Первый свитчинговый метод построения нелинейных совершенных двоичных кодов был предложен в 1962 г. Ю.Л. Васильевым в работе [9]. Известно (см. [5]), что любой совершенный код длины п ранга п—log(n + 1) + 1 является кодом Васильева V™ ([9]), построенным свитчингами г-компонент (по одной координатной позиции) из кода

^_I

Хэмминга с помощью некоторой функции Л : Н~ —{0,1}. Код Васильева УЛП может быть, с точностью до эквивалентности, представлен в виде

У\ = {{\х\ + \{у),х + у,х)\х е F"Н(1)

^_I

для некоторой функции Л : —у {0,1}. Первое существенное улуч-

шение нижней границы числа известных кодов Васильева было получено в 1997 г. в работе [4] C.B. Августиновича и Ф.И. Соловьевой. В [4] предложен свитчинговый метод а-компонент построения совершенных двоичных кодов, который позволяет строить богатый класс нелинейных совершенных двоичных кодов.

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

Первая публично заявленная задача, связанная с системами троек и четверок Штейнера, была поставлена У.С.Б. Вулхаусом в 1844 г. в [52] и формулировалась как определение существования различных сочета-

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

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

Нетрудно показать, что носители всех кодовых слов веса 3 в приведенном совершенном двоичном коде С длины п = 2Г — 1 образуют систему троек Штейнера STS(2r — 1), а носители кодовых слов веса 4 в приведенном расширенном совершенном двоичном коде С длины N = 2Г образуют систему четверок Штейнера SQS(2r). см., например. [17]. Если совершенный (расширенный совершенный) код является кодом Хэмминга длины п (расширенным кодом Хэмминга длины N). то соответствующая ему система троек (четверок) Штейнера называется Хэмминговой системой троек Штейнера STS(H^n) (Хэмминговой системой четве-

рок Штейнера 3(^3(4, ТУ)/ Если для некоторой системы троек Штей-нера 5Т5(п) существует приведенный совершенный двоичный код С, носители всех кодовых слов веса 3 которого образуют данную 5Т5(п), то указанную систему троек Штейнера будем называть вложимой в совершенный код С. Понятие системы четверок Штейнера, вложимой в расширенный совершенный двоичный код, определяется аналогично.

В 2007 - 2009 гг. П. Р. Остергардом и О. Поттоненом в работах [38, 39] доказано, что только 33 из 80 неизоморфных систем троек Штейнера порядка 15 являются вложимыми в совершенный код, и только 15590 из 1054163 неизоморфных систем четверок Штейнера порядка 16 вложимы в расширенный совершенный код.

В статье [49] В. Д. Тончевым найдено число различных систем троек Штейнера порядка 2Г — 1 ранга 2Г — г, что на 1 превышает минимально возможный ранг (говорят также, что такие коды имеют ранг "+1"). Тем же авторо�