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

• Ковалевская, Дарья Игоревна
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Ковалевская, Дарья Игоревна

Оглавление

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

Литература

Введение диссертации (часть автореферата) на тему «О вложимости систем Штейнера в совершенные коды»

Введение

Теория кодирования в современном мире имеет широкое применение как средство передачи информации по каналам связи с шумами (телефон, телеграф, радио, телевидение, компьютерная, космическая связи и т. д.). Ее развитие началось после появления работы К. Шеннона [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"). Тем же автором в работе [48] получена аналогичная формула для числа различных систем четверок Штейнера порядка 2Г ранга 2г — г. Задача вложимости систем троек (четверок) Штейнера в совершенные (расширенные совершенные) двоичные коды В. Д. Тончевым не рассматривалась. Первые результаты, посвященные этой проблеме, принадлежат В. А. Зиновьеву и Д. В. Зиновьеву, см. [13], где доказано, что все системы четверок Штейнера порядка 2Г, г > 3, ранга 2г — г (т.е. ранга " + 1") вложимы в расширенные коды Васильева длины 2Г такого же ранга. В работах [53, 54] В. А. Зиновьевым и Д. В. Зиновьевым показано, что все системы троек Штейнера порядка 2Г — 1, г > 3, ранга 2Г — г +1 (т.е. ранга "+2") вложимы в некоторые совершенные двоичные коды, но остается неясным ранг таких кодов.

Отображение I : С —у С', где С, С' - равномощные коды пространства Р™, называется изометрией кода С в код С' = /(С), если (1(х, у) = (1(1 (х), 1(у)) для всех кодовых слов х, у из С. Два кода С и И из - эквивалентные, если существует изометрия пространства переводящая код С в код О.

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

АиЬ(¥™) = {(7г; ох,..., оп) : 7г € 5„, а, е 1 < г < п},

где 5П и - симметрические группы порядка п и д соответственно.

В литературе известно несколько определений метрической жесткости. Наиболее общим является следующее: код С С ¥™ называется метрически жестким, если всякая изометрия I : С —С, для любого кода С", равномощного коду С, продолжается до изометрии (автоморфизма) пространства ^. Код С С ^ называется метрически жестким в слабом смысле, если всякий код С' = /(С) эквивалентен коду С. Код С С .Р™ - метрически жесткий в узком смысле, если для всякой изометрии / : С —> С существует некоторая изометрия V всего пространства такая, что I и I' на словах кода С действуют одинаково, т.е. 1\с = 1'\с-

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

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

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

б) все д-ичные (п. п — 1) МИБ-коды являются метрически жесткими.

за исключением двух кодов длины 3 и одного кода длины 4;

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

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

Теми же авторами в 1998 г. установлено, что полные равновесные д-ичные коды являются метрически жесткими, см. [43]. В 2003 г. С. В. Августинович и Ф. И. Соловьева установили, см. [2], что при п > /с4 каждый приведенный двоичный код, содержащий 2-(п, /с, А)-схему, является метрически жестким. Поскольку любая £-(г>, к, А)-схема, £ > 2, является 2-(г>, /с, А')-схемой, для некоторого А', то любой приведенный код, содержащий 1-{у, /с, А)-схему, также является метрически жестким. Поэтому все расширенные примитивные коды БЧХ и расширенные совершенные коды являются метрически жесткими. Этим свойством обладают и равномерно упакованные коды, удовлетворяющие условию ё, — р > 2, где (I - кодовое расстояние, р - радиус покрытия, к которым относятся такие важные классы кодов, как коды БЧХ с расстоянием 5 и 7, коды Препараты в широком смысле, коды Геталса в широком смысле с расстоянием 7, см. [2], а также соответствующие им расширенные коды.

В данной диссертации предложены новые свитчинговые конструкции систем троек (четверок) Штейнера рангов не больше "+2". Дана классификация 5Т5(п) (8СдЗ(А^)), вложимых в совершенные (расширенные совершенные) двоичные коды длины п (Л^) таких же рангов. Кроме того, описан класс и приведена нижняя оценка числа различных систем троек (четверок) Штейнера ранга "+2". не вложимых в совершенные (расширенные совершенные) двоичные коды ранга 11+2". Также в диссертационной работе доказана метрическая нежесткость ряда классов кодов, среди них некоторых классов эквидистантных кодов и кодов, отвечающих одному классу аффинно разрешимых схем.

Приведем краткое описание настоящей работы. В первой главе пред-

ложен новый итеративный свитчинговый метод построения класса систем троек Штейнера БТЗ^п) порядка п = 2Г — 1, г > 3. Доказана вложимость данного класса 5Т5(п) ранга не более п—1) + 2 в совершенные двоичные коды длины п такого же ранга, найдены нижняя и верхняя оценки числа таких систем троек Штейнера. Также приведены различные системы троек Штейнера порядка п ранга n—\og(n + 1) + 2, не вложимые в совершенные двоичные коды длины п такого же ранга. Указана нижняя оценка числа таких систем троек Штейнера.

В общем случае (см. [4]) говорят, что код С' = (С\Я) и Я' получен свитчингом множества Я на множество Я' в двоичном коде С, если код С' имеет те же параметры, что и С. Такое множество Я называется компонентой кода С.

Более подробно, пусть Я - произвольное подмножество совершенного двоичного кода С. Свитчингом множества Я по г-ой координатной позиции называется замена значения г-й координатной позиции всех векторов множества Я. Получившееся в результате такого свитчинга множество будем обозначать через Я + г. Множество Я называется г-компонентой совершенного кода С, если код С' = (С \ Я) и (Я 4- г) имеет те же параметры, что и С, т.е. является совершенным. Множество Я называется а-компонентой совершенного кода С, если Я является г-компонентой для любого г € <х

Понятие свитчинга для ¿-(г», к. 1)-схемы определяется аналогично понятию свитчинга в коде. Два множества Я и Я', состоящие из к-элемент-ных подмножеств множества V, называются равновесными, если каждое неупорядоченное подмножество из £ элементов, которое может быть найдено в /с-элементных подмножествах одного множества, встречается также и в /с-элементных подмножествах другого множества. Говорят, что £-(г>, к, 1)-схема А' = (А\Я)иЯ' получена свитчингом множества блоков Я на множество блоков Я' в £-(г>, к, 1)-схеме А, если Я и Я' - равновесные множества. Такое определение равновесных множеств можно найти, например, в работах о свитчинговых методах [14, 18]. В статье [14] такое

множество Я (равно как и множество Я') называется компонентой.

Понятие свитчинга для системы троек Штейнера определяется как частный случай свитчинга для 1)-схемы. Говорят, что система тро-

ек Штейнера 5Т5'(п) = (5Т5(п)\.й) и Я' получена свитчингом множества блоков Я на множество блоков Я! в 5Т5(гг), если Я и Я! - равновесные множества, т.е. каждая пара элементов, которая может быть найдена в тройках множества Я, встречается также и в тройках множества Я1.

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

Также указаны определенные правила (обозначенные в работе через Л1, Л2, АЗ, В\, В2), позволяющие делать свитчинги Паш-конфигураций исходной системы троек Штейнера порядка п, построенной по указанному методу из произвольной системы троек Штейнера порядка т. Приведенные правила позволяют получать различные системы троек Штейнера порядка п различного ранга, превосходящего ранг Хэмминговой системы троек Штейнера. Обозначим класс таким образом построенных систем троек Штейнера порядка п ранга г через Зии(ЗТЗ(п),г). Через 5«;(5Т5(п),г) обозначим подкласс класса 5гу(5Т5'(п),г), содержащий такие системы троек Штейнера порядка п ранга г, которые получены из произвольной системы троек Штейнера порядка п посредством правил Л1, 81, 52.

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

Теорема 2. Для числа Я(п) всех различных 8Т8(п); п = 4т + 3. т > 3; лежащих в классах Зи)(ЗТЗ(п),г) при всех г > п—1од(п + 1).

верно

Я(п) > (((та + 1) • 2<п"5>/2 + 2та - 6) х

х 310(п»-10п+21)/з.2' _3п + 9) . п(п — 1)/12 • Д((та — 3)/4).

Параграфы 1.3 и 1.4 посвящены вопросу вложимости построенных в параграфе 1.2 систем троек Штейнера в совершенные коды и основаны на свитчинговом методе построения совершенных двоичных кодов.

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

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

"Утверждение 4. (См. [4]) Код Хэмминга Нп представим в виде

N2

Нп = и Я\зк, где Щ к - различные непересекающиеся ъ^к-компоненты, = к ■

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

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

(та) = •та!/|5?/гта(Я^)|, где ^ш(К^) - груп-

па симметрий кода Хэмминга С помощью этой работы, используя

Список литературы диссертационного исследования кандидат наук Ковалевская, Дарья Игоревна, 2013 год

Литература

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

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

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

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

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

6] Алиев И. Ш. о. Комбинаторные схемы и алгебры // Сиб. матем. журн. - 1972. Т. 13. №. 3. С. 499-509.

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

8] Богданова Г. Т.. Зиновьев В. А., Тодоров Т. Й. О построении д-ичных эквидистантных кодов // Пробл. передачи информ. 2007. Т. 43. № 4. С. 13-36.

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

[10] Глухих Е. С. Вложимоеть систем троек Штейнера в совершенные коды. // Магистерская диссертация. Новосибирск. 2005.

[11] Егорычев Г. П. Доказательство гипотезы Ван дер Вардена для перманентов // Сиб. мат. журн. 1981. Т. 22. № 6. С. 65-71.

[12] Зиновьев В. А., Зиновьев Д. В. О разрешимости систем Штейнера S(v = 2m,4, 3) ранга г < v — т + 1 над F2 // Пробл. передачи информ. 2007. Т. 43. Вып. 1. С. 39-55.

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

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

[15] Зиновьев В. А., Леонтьев В. К. О совершенных кодах // Пробл. передачи информ. 1972. Т. 8. №. 1. С. 26-35.

[16] Кротов Д. С., Потапов В. Н. О свитчинговой эквивалентности n-арных квазигрупп порядка 4 и совершенных двоичных кодов // Пробл. передачи информ. 2010. Т. 46. №. 3. С. 22-28.

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

[18] Петренюк А. Я. Признаки неизоморфности систем троек Штейнера // Укр. матем. ж. 1972. Т. 24. Вып. 6. С. 772-780.

[19] Семаков Н. В., Зиновьев В. А., Зайцев Г. В. Класс максимальных эквидистантных кодов // Пробл. передачи информ. 1969. т. 5. № 2. С. 84-87.

[20] Семаков Н. В., Зиновьев В. А. Эквидистантные g-ичные коды с максимальным расстоянием и разрешимые уравновешенные неполные блок-схемы // Пробл. передачи информ. 1968. Т. 4. № 2. С. 3-10.

[21] Соловьева Ф. И. Введение в теорию кодирования. Учеб. пособие. -Новосиб. гос. ун-т. Новосибирск. 2006. 124 с.

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

[23] Филимонова (Глухих) Е. С. Вложимость систем троек Штейнера в совершенные коды // Магистерская диссертация. Новосибирск. 2005.

[24] Хачатрян Л. Г. Эквидистантные коды и эквидистантные подстановочные таблицы // Пробл. передачи информ. 1981. Т. 17. № 4. С. 116-119.

[25] Холл М. Комбинаторика. Пер. с англ. М.: Мир. 1970. 424 с.

[26] Assmus Е. F., Mattson Н. F. Jr. On tactical configurations and error correcting codes // Journal of Combin. Theory. 1967. № 2. P. 243-257.

[27] Doyen J., Hubaut X., Vandensavel M. Ranks of incidence matrices of Steiner triple systems // Math. 1978. S. Z. № 163. P. 251-259.

[28] Doyen J., Vandensavel M. Nonisomorphic Steiner Quadruple Systems // Bull. Soc. Math. Belg. 1971. V. 23. P. 393-410.

[29] Golay M. J. E. Notes on Digital Coding. 1949. Proc. IRE 37: 657.

[30] Hamming R. W. Error detecting and error correcting codes // Bell System Technical Journal. 1950. V. 29. № 2. P. 147-160.

[31] Hanani H. On quadruple systems // Can. Journ. Math. 1960. V. 12. P. 145-157.

[32] Hanani H. The Existence and Construction of Balanced Incomplete Block Designs // Ann. Math. Statist. 1961. V. 32. № 2. P. 361-386.

[33] Kaski P., Ostergard P. R. J. The Steiner Triple Systems of Order 19 // Math. Comput. 2004. № 73. P. 2075-2092.

[34] Kirkman T. P. On a Problem in Combinations // The Cambridge and Dublin Mathematical Journal (Macmillan, Barclay, and Macmillan). 1847. V. II. P. 191-204.

[35] Lenz H. On the number of Steinei Quadruple Systems // Mitt. Math. Seminar Giessen. 1985. V. 169. P. 55-71.

[36] Lindner C. C. On the construction of nonisomorphic Steiner quadruple systems // Colloq. Math. 1974. V. 29. P. 303-306.

[37] Linial N., Luna Z. An upper bound on the number of Steiner triple systems // Random Structures &; Algorithms, accepted, 2013. D01:10.1002/rsa.20487.

[38] Ostergard P. R. J., Pottonen O. The perfect binary one-error-correcting codes of length 15: Part 1 - Classification // IEEE Trans. Inform. Theory. 2009. № 55. P. 4657-4660.

[39] Ostergard 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.

[40] Shannon C. E. A Mathematical Theory of Communication // Bell System Technical Journal. 1948. V. 27. P. 379-423.

[41] Solov'eva F. I. On perfect codes and related topics // Com2Mac Lecture Note Series 13, Pohang. - 2004. - 80 P.

[42] Solov'eva F. I. Switchings and perfect codes // Numbers, Information and Complexity, Kluwer Academic Publisher. 2000. P. 311-324.

[43] 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.

[44] Solov'eva F. I., Avgustinovich S. V.; Honold T., Heise W. On the Extendability of Code Isometries // J. of Geometry. 1998. V. 61. № 1/2. P. 3-16.

[45] Steiner J. Combinatorische Aufgabe // Journal fur die Reine und Angewandte Mathematik. 1853. V. 45. P. 181-182.

[46] Teirlinck L. On projective and affine hyperplanes //J Combin. Theory. 1980. S. A. № 28. P. 290-306.

[47] 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. 1-5.

[48] Tonchev V. D. A formula for the number of Steiner quadruple systems on 2n points of 2-rank 2n — n // Journal of Combin. Designs. 2003. № 11. P. 260-274.

[49] 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. № 95. P. 197-208.

[50] Tonchev V. D. Codes and Designs // Handbook on coding theory, Pless V. S., Huffman W. C. Eds., Elsevier, Amsterdam, 1998. Ch. 15. P. 1231-1268.

[51] Witt E. Theorie der quadratischen Formen in beliebigen Körpern // J. Reine Angew. Math. 1936. Bd. 176. P. 31-44.

[52] Woolhouse W. S. B. Prize Question 1733, Lady's and Gentleman's Diary. 1844.

[53] Zinoviev D. V.; Zinoviev V. A. Steiner Triple Systems S(2TO — 1,3,2) of 2-rank r < 2m — m + 1: Construction and Properties // Proc. of Thirteenth Int. Workshop "Algebraic and combinatorial coding theory"(Pomorie, Bulgaria, June 15-21, 2012). P. 358-363.

[54] Zinoviev V. A., Zinoviev D. V. Steiner Triple Systems S(2TO — 1,3,2) of Rank 2m — m + 1 over ¥2 / / Problems of Inform. Transm. 2012. V. 48. № 2. P. 102-126.

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

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

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

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

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

[59] 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.

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

KovalSol_Theses.pdf.

[61] 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.

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

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

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

[65] Ковалевская Д. И. Об одном свойстве кодов Рида - Маллера первого порядка // Материалы ХЬУ1 Международной научной студенческой конференции "Студент и научно-технический прогресс": Математика / Новосиб. гос. ун-т. Новосибирск. 2008. С. 190-191.

[66] Ковалевская Д.И. О метрической жесткости некоторых классов эквидистантных кодов // Материалы Х1УП Международной научной студенческой конференции "Студент и научно-технический прогресс": Математика / Новосиб. гос. ун-т. Новосибирск. 2009. С. 166-167.

[67] Ковалевская Д. И. Метрическая жесткость некоторых классов кодов // Материалы ХЬУШ Международной научной студенческой конференции "Студент и научно-технический прогресс": Математика / Новосиб. гос. ун-т. Новосибирск. 2010. С. 159-160.