Коды, свободные от перекрытий Полянский Никита Андреевич

Содержание к диссертации

Введение

1 Свободные от перекрытий коды 18

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

1.2 Нижние оценки R(s,) 19

1.3 Верхние оценки R(s,) 34

1.4 Таблица наилучших границ R(s,) 36

1.5 Конструкции СП (Й,)-КОДОВ 36

2 Почти свободные от перекрытий коды 42

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

2.2 Нижние оценки C(s,) 44

2.3 Верхние оценки C(s,) 55

2.4 Таблица наилучших границ C(s,) 61

2.5 Сравнение R(s,) и C(s,) 61

3 Задача поиска скрытого гиперграфа 63

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

3.2 Оценки Rh(s,) 66

3.3 Оценки Ch{s,) 69

Заключение 74

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

• Верхние оценки R(s,)
• Нижние оценки C(s,)
• Таблица наилучших границ C(s,)
• Оценки Rh(s,)

Введение к работе

Актуальность темы

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

Двоичный код называется дизъюнктивным s-кодом, если он является матрицей инцидентности семейства множеств, для которого никакое множество не содержится в объединении s любых других множеств данного семейства.

Если множества данного семейства есть некоторые подмножества множества {1,2..., N}, то число N назовем длиной кода, а мощность такого семейства - объемом кода, и будем обозначать через t. Определим скорость кода R = log₂ t/N. Столбцы соответствующей матрицы инцидентности будем называть кодовыми словами.

Дизъюнктивные коды были введены У. Каутсом и Р. Синглтоном в 1964 году в основополагающей статье¹, где был описан ряд прикладных задач и построены некоторые важные конструкции таких кодов. Отметим, что многие авторы изучали вопросы, относящиеся к дизъюнктивным кодам, с принципиально разных точек зрения и зачастую проводили свои исследования независимо от других ученых. Именно поэтому многие результаты были сперва найдены в теории информации, а позднее были переоткрыты в комбинаторике или в теории группового тестирования, и наоборот. В подтверждение вышесказанного можно выделить статью², написанную в 1982 году П. Эрдешем и др., в которой вводится определение дизъюнктивного 2-кода, а позднее, в 1985 году, в своей следующей работе³ авторы обобщили его уже для произвольного значения s.

Определим асимптотическую скорость дизъюнктивных s-кодов как

— log₂

itfs, 1) = lim , (1)

t-^oo N(t, s, 1)

где число N(t, s, 1) равно минимальной длине дизъюнктивного s-кода объема t. Из определения сразу следует¹ теоретико-информационная верхняя граница скорости R(s, 1) ^ І/s. В 1982 году П. Эрдеш доказал² оценки, из

¹Kautz W. H., Singleton R. C., Nonrandom Binary Superimposed Codes // IEEE Trans. Inform. Theory, 10:4 (1964), 363-377.

²Erdos P., Frankl P., Furedi Z., Families of Finite Sets in Which No Set Is Covered by the Union of two Others // J. Combin. Theory, Ser. A, 33 (1982), 158-166.

³Erdos P., Frankl P., Furedi Z., Families of Finite Sets in Which No Set Is Covered by the Union of r Others // Israel J. Math., 51 (1985), 79-89.

которых следует, что

0.183 ^ R(2,1) ^ 0.322. (2)

В том же году А.Г. Дьячковым и В.В. Рыковым независимо была построена⁴ верхняя граница скорости R(s, 1), которая к настоящему моменту является наилучшей. Следует сказать, что они использовали собственную технику при выводе оценки. Эта граница при s = 2 совпадает с (2), а в случае произвольного s было доказано, что верна следующая граница

, 2 log₂[e(s + 1)/2]
Ris_} 1) ^ т. (3)

Отметим, что позднее, в 1994 году, М. Ружинко сумел привести⁵ более простое доказательство этого факта, но уже в ослабленной форме

, 81og₂s
Ris_} 1) ^ т. (4)

Нижняя граница скорости R(s, 1) была получена А.Г. Дьячковым и В.В. Рыковым в 1983 году в работе⁶, в которой с помощью метода случайного кодирования на ансамбле двоичных кодов с независимыми компонентами показано, что асимптотика границы имеет вид

log₂ е 0.531

Ris, 1) ^z(1 + oil)) =—т. (1 + о(1)), s —> оо. (5)

Определенный интерес представляет собой работы, написанные независимо П. Эрдешом³ в 1985 году и Ф. Хуонгом⁷ в 1987 году, которые, в частности, содержат следующую оценку

log₂ е 0.361

Ris, 1) ^ (1 + oil)) = —т. (1 + oil)), s —> оо. (6)

4:S^Z s^z

В дальнейшем, была построена более точная границы снизу для R(s, 1). В 1989 году методом случайного кодирования на ансамбле двоичных равновесных кодов А.Г. Дьячков и др. показали⁸, что асимптотика нижней

Дьячков А. Г., Рыков В. В., Границы длины дизъюнктивных кодов // Пробл. передачи информ., 18:3 (1982), 7-13.

⁵Ruszinko M., On the upper bound of the size of the r-cover-free families // J. Combin. Theory, Ser. A., 66 (1994), 302-310.

⁶D’yachkov A. G., Rykov V. V., A Survey of Superimposed Code Theory // Prob. of Control and Inform. Theory, 12:4 (1983), 229-242.

⁷Hwang F.K., Sos V. Z., Non adaptive hypergeometric group testing // Studia Sci. Math. Hungarica, 22 (1987), 257-263.

⁸D’yachkov A.G., Rykov V.V., Rashad A.M., Superimposed Distance Codes // Prob. of Control and Inform. Theory, 18:4 (1989), 237-250.

границы имеет вид

R(s,l) ^ ^ (1 + oil)) =—т. (1 + oil)), s —> оо. (7)

s^ log₂ e s^

В частности, при s = 2 полученная авторами оценка совпадает с (2).

Практически все классические проблемы теории дизъюнктивных кодов допускают обобщения. Одним из естественных таких обобщений является следующее определение.

Двоичный код называется свободным от перекрытий (s,)-кодом, если он является матрицей инцидентности семейства множеств, для которого пересечение любых множеств не покрывается объединением s любых других множеств данного семейства.

Свободные от перекрытий коды были введены⁹ К. Митчеллом и Ф. Пай-пером в 1988 году в связи с криптографической задачей распределения ключей. Основные конструкции свободных от перекрытий кодов, построенные на укороченных кодах Рида-Соломона, были описаны¹⁰ в 2002 году. Для малых значений параметров s и Ш.Х. Ким и В.С. Лебедев привели¹¹'¹²'¹³ оптимальные конструкции свободных от перекрытий (й,)-кодов, а также получили некоторые конструктивные оценки для минимальной длины таких кодов. В 2009 году была найдена¹⁴ скорость конструкций свободных от перекрытий кодов, основанных на алгебро-геометрических кодах.

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

— log₂

itfs, г) = lim , (8)

t-^oo N(t, s,)

где число N(t,s,) равно минимальной длине дизъюнктивного свободного от перекрытия (й,)-кода объема t. Первые результаты исследования верхних границ скорости R(s,) для СП (й,)-кодов, 2 ^ ^ s, были получены

⁹Mitchell C. J., Piper F. C., Key storage in Secure Networks // Discrete Applied Mathematics, 21 (1988), 215-228.

¹⁰D’yachkov A., Vilenkin P., Macula A., Torney D., Families of Finite Sets in Which No Intersection of Sets Is Covered by the Union of s Others // J. Combin. Theory, Ser. A, 99 (2002), 195-218.

¹¹Kim H., Lebedev V.S., On Optimal Superimposed Codes // Journal of Combinatorial Designs, 12:2 (2004), 79-91.

¹²Ким Ш. Х., Лебедев В. С, Об оптимальности тривиальных кодов, свободных от (w, г)-перекрытий // Пробл. передачи информ., 40:3 (2004), 13-20.

¹³Kim H., Lebedev V., Oh D., Some new results on superimposed codes, J. Combin. Des., 13:4 (2005), 276—285.

¹⁴Сидельников В. М., Приходов О.Ю., О построении кодов, свободных от (w, г)-перекрытий // Пробл. передачи информ., 45:1 (2009), 36-40.

в 2000 году в работе¹⁵ Д. Стинсона и др., а также в 2002 году в работе¹⁰ А.Г. Дьячкова и др. Было показано¹⁵, что выполняется следующая оценка

R(s,) ^ —ггк —,

>-7 (s-\-i\ ( /Л '

7 s +)

а также верно рекуррентное неравенство

R(s,) R(s, — 1) R(s —1,) В 2003 году В.С. Лебедев доказал¹⁶ неравенство

R(s — i, — j) R[s — і Л — 7) + /.,-

которое представляет собой уточнение неравенства

R[s,) ^ г-^7X7, і Є \s — 1 , 7 Є — 1 , (10)

^ + * (9)

i* J⁷'
R[s,) ^ R[s — i, — 7 b г^, і є s — 1 , 7 є -t — 1 , (11)

ранее установленного¹⁷ П. Энгелом в 1996 году. Рекуррентное неравенство (10) и верхняя граница (3) дают¹⁸ для скорости R(s,), 2 ^ ^ s наилучшую известную верхнюю границу для R(s,), асимптотическое поведение которой при фиксированном ^ 2 и s —> оо описывается следующим неравенством

( + 1)^⁺¹ log₂ s
R(s,) ^ т_Л гг(1 + о(1)). (12)

Нижняя граница скорости R(s,), 2 ^ ^ s, была получена¹⁰ с помощью метода случайного кодирования на ансамбле с независимыми двоичными компонентами кодовых слов и на некотором специальном ансамбле с независимыми двоичными равновесными словами, предложенном¹⁹ ранее

¹⁵Stinson D. R., Wei R., Zhu L., Some New Bounds for Cover-Free Families // J. Combin. Theory, Ser. A, 90 (2000), 224-234.

¹⁶Лебедев В.С., Асимптотическая верхняя граница скорости кодов, свободных от (w, г)-перекрытий // Пробл. передачи информ., 39:4 (2003), 3-9.

¹⁷Engel K., Interval Packing and Covering in the Boolean Lattice // Combinatorics Prob. and Computing, 5 (1996), 373-384.

¹⁸D’yachkov A. G., Vilenkin P. A., Yekhanin S.M., Upper Bounds on the Rate of Superimposed (s,)-Codes Based on Engel’s Inequality // Proc. Eighth Int. Workshop «Algebraic and Combinatorial Coding Theory», Tsarskoe Selo, (2002), 95-99.

¹⁹Quang A. N., Zeisel T., Bounds on Constant Weight Binary Superimposed Codes // Problems of Control and Inform. Theory, 17:4 (1988), 223-230.

Н. Куонгом и Т. Зейселем. При фиксированном ^ 2 и s —> оо асимптотика этой границы имеет вид

^log₂e 1
R(s,z) ^ т гг(1 + о(1)). (13)

Одним из следующих направлений в теории дизъюнктивных кодов стало вероятностное обобщение дизъюнктивного s-кода. В 2004 году Э. Ма-кула и др. ввели²⁰ определение почти дизъюнктивных кодов. В недавней статье²¹ А.Г. Дьячковым и др. было описано такое обобщение для более широкого класса дизъюнктивных кодов. Дадим основное определение.

Под плохим событием будем понимать следующее: «дизъюнктивная сумма некоторых s кодовых слов покрывает некоторое другое кодовое слово» (подмножество из s кодовых слов выбирается равновероятно). Тогда пропускной способностью C(s, 1) почти дизъюнктивных кодов будем называть точную верхнюю грань для скорости кодов, для которых вероятность плохого события убывает экспоненциально с ростом длины кода. Для пропускной способности почти дизъюнктивных кодов И. Воробьевым была доказана²¹ следующая граница

In 2

G(s,l)^ (1 + о(1)), s —> оо. (14)

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

Аналогичным образом можно обобщить определение для свободного от перекрытий (й,)-кода. В данном случае под плохим событием подразумевать следующее: «дизъюнктивная сумма некоторых s кодовых слов покрывает конъюнкцию некоторых других кодовых слов» (подмножество из S кодовых слов выбирается равновероятно). Тогда в схожей манере (см. случай = 1) определим пропускную способность C(s,) почти свободных от перекрытий кодов. Отметим, что всякий код X является почти свободным от перекрытий (s,, є)-кодом, где параметр є = є(Х) равен вероятности плохого события.

²⁰Macula A. J., Rykov V.V., Yekhanin S., Trivial two-stage group testing for complexes using almost disjunct matrices // Discrete Applied Mathematics, 137:1 (2004), 97—107.

²¹Дьячков А. Г., Воробьев И. В., Полянский Н. А., Щукин В.Ю., Почти дизъюнктивные коды со списочным декодированием // Пробл. передачи информ., 51:2 (2015), 27-49.

²²Бассалыго Л. А., Рыков В. В., Гиперканал множественного доступа //Пробл. передачи информ., 49:4 (2013), 3-12.

²³D’yachkov A.G., Macula A. J., Rykov V. V., New Applications and Results of Superimposed Code Theory Arising from the Potentialities of Molecular Biology // In the book «Numbers, Information and Complexit», Kluwer Academic Publishers, (2000), 265-282.

Одним из важных приложений свободных от перекрытий кодов является²⁴ задача поиска скрытого гиперграфа из семейства локализованных гиперграфов. Предположим, что задан скрытый гиперграф Н_ип = (V,E), ребра которого нам неизвестны, но мы знаем, что этот гиперграф Н_ип принадлежит некоторому семейству Т гиперграфов, имеющих особую структуру (например, J- состоит из всевозможных гамильтоновых циклов на V). Наша цель - обнаружить ребра Е этого гиперграфа, спросив N вопросов Q(S), где множество S - это некоторое подмножество У, а ответ на вопрос положительный, т.е. Q(S) = 1 в случае, если множество S содержит полностью хотя бы одно ребро из Е. В остальных случаях ответ на вопрос отрицательный, т.е. Q(S) = 0. Будем называть поиск неадаптивным, если все вопросы заранее спланированы и задаются одновременно. Если же вопросы задаются последовательно, и последующие вопросы зависят от ответов на предыдущие, то поиск называют адаптивным. Рассмотрим семейство гиперграфов J⁷^, s,), которое будет состоять из таких гиперграфов Н = (V,E), что множество вершин V = {1,2.../:}, множество ребер Е = {еі, Є2,..., e_s/}, 1 ^ s' ^ s, и размер каждого ребра 1 ^ \єі\ ^ , причем никакое ребро не содержится ни в каком другом. Итак, пусть задан скрытый гиперграф Н_ип = (У, Е) и мы знаем, что Н_ип Є J-(t,s,). Будем говорить, что Л является алгоритмом поиска скрытого гиперграфа из семейства J-(t,s,), если он находит Н_ип, т.е. существует ровно один гиперграф из семейства J-(t,s,), который удовлетворяет всем заданным вопросам.

Обозначим через N(A) максимальное количество вопросов алгоритма Л, необходимых для поиска скрытого гиперграфа из семейства J-(t,s,). Определим асимптотическую скорость алгоритмов поиска скрытого гиперграфа из семейства J-(t, s, ) как

— log2^

Rh(s,) = lim , (15)

t-^oo Nh(t, s,)

где число Nh(t, s, ) равно минимальному числу вопросов N(A) среди всех алгоритмов Л поиска скрытого гиперграфа из семейства J-(t,s,). Будем приписывать к величине Rh(s,) верхний индекс а и па в зависимости от адаптивности поиска.

В 2002 году А.Г. Дьячков и др. показали¹⁰, что задача неадаптивного поиска скрытого гиперграфа и свободные от перекрытия коды сильно связаны между собой, в частности, выполнены следующие неравенства

R%^a(s, ) ^ R(s,) ^ min (R%^a(s — 1,), R^^a(s, — 1)). (16)

²⁴Angluin D., Chen J., Learning a hidden hypergraph // Journal of Machine Learning Research, 7 (2006), 2215-2236.

Естественной теоретико-информационной границей для скорости адаптивного поиска служит следующее неравенство

R_h(s,z) ^ —. s

Отметим, что при = 1 данная задача вырождается в довольно известную задачу поиска дефектов. Известно²⁵, что адаптивный поиск дефектов достигает теоретико-информационную границу, т.е.

Rh(s, 1) = -. (17)

Для задачи поиска скрытого графа, т.е. при = 2, в 2008 году Д. Англуин и Ж. Чен привели²⁶ близкий к оптимальному алгоритм поиска скрытого графа, из которого следует, что

Rhis, 2) ^ 1/(125).

Для произвольных значений s и в 2014 году Х. Абаси и др. недавно показали²⁷, что

R^(s,) ^ l/(2s).

Рассмотрим следующее вероятностное обобщение. Под плохим событием будем понимать: «алгоритм поиска скрытого гиперграфа не находит скрытый гиперграф» (скрытый гиперграф выбирается равновероятно в семействе J-(t,s,)). Тогда пропускной способностью Ch{s,) будем называть точную верхнюю грань для скорости алгоритмов поиска скрытого гиперграфа из семейства J-(t,s,), для которых вероятность плохого события стремиться к нулю с ростом числа вершин t. Также будем приписывать к величине Ch{s,) верхний индекс а и па в зависимости от адаптивности алгоритма поиска.

Классическим результатом для теории планирования экспериментов является следующее равенство, доказанное²⁸ М.Б. Малютовым и В.Л Фрей-длиной:

Су и ( S J. ) —— Су и ( S J. ) ——

²⁵Du D.Z., Hwang F.K., Combinatorial Group Testing and Its Applications, 2nd ed., Series on Applied Mathematics, 12 (2000).

²⁶Angluin D., Chen J., Learning a hidden graph using O(logn) queries per edge // J. Comput. Syst. Sci., 74 (2008), 546–556.

²⁷Abasi H., Bshouty N.H., Mazzawi H., On Exact Learning Monotone DBF from Membership Queries // Lecture Notes in Artificial Intelligence, (2014), 111–124.

²⁸Малютов М.Б., Фрейдлина В.Л., О применении теории информации к одной задаче выделения значимых факторов // Теория вероятностей и ее применения, 18:2 (1973), 432-–444.

Цель работы

Целью диссертационной работы являются:

построение более точных оценок снизу для асимптотической скорости свободных от перекрытий кодов;

построение оценок снизу и сверху для пропускной способности почти свободных от перекрытий кодов;

исследование алгоритмов поиска скрытого гиперграфа из семейства локализованных гиперграфов.

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

Все результаты работы являются новыми. В диссертации получены следующие основные результаты.

1. Доказаны новые границы снизу для асимптотической скорости R(s,) свободных от перекрытий кодов при ^ 2, улучшающие наилучшие ранее известные границы, установленные¹⁰ А.Г. Дьячковым и др.

2. Предложена конструкция свободных от перекрытия кодов, обобщающая ранее известную конструкцию дизъюнктивных кодов, полученную²⁹ Э. Макулой.

3. Впервые получены границы снизу и сверху для пропускной способности C(s,) почти свободных от перекрытий кодов при ^ 2.

4. Доказана новая граница снизу для асимптотической скорости R^s, ) адаптивного поиска скрытого гиперграфа, достигающая теоретико-информационную границу и улучшающая результаты работы²⁷ Х. Аба-си и др.

5. Впервые получена граница снизу для пропускной способности C|^-st(s, ) двухступенчатой процедуры поиска скрытого гиперграфа, достигающая теоретико-информационную границу.

²⁹Macula A. J., A simple construction of Discrete Math., Ser. A, 162:1-3 (1996), 311-312.

Основные методы исследования

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

Теоретическая и практическая ценность работы

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

Апробация диссертации

Результаты диссертации неоднократно докладывались автором на следующих научно-исследовательских семинарах:

6. Cеминар по теории кодирования под рук. Л.А. Бассалыго в 2011– 2016 гг., Институт проблем передачи информации им. А.А. Харкевича РАН.

7. Семинар «Проблемы современной теории информации» в 2010-2016 гг. под рук. А.Г. Дьячкова, кафедра теории вероятностей, механико-математический факультет, Московский государственный университет им. М.В. Ломоносова.

8. Семинар по дискретной математике под рук. М.В. Вялого и СП. Тарасова в 2016 г., Вычислительный центр им. А.А. Дородницына РАН.

Результаты диссертации докладывались автором на следующих конференциях:

9. International workshop «Search Methodologies 1/7», Bielefeld, Germany, 2012.

10. Международная научная конференция студентов, аспирантов и молодых ученых «Ломоносов-2013», Москва, Россия, 2013.

11. 14th International Workshop «Algebraic and Combinatorial Coding Theory», Svetlogorsk, Russia, 2014.

4. IEEE International Symposium on Information Theory, Honolulu, USA, 2014.

5. Ninth International Workshop on Coding and Cryptography, Paris, France, 2015.

6. IEEE International Symposium on Information Theory, Hong Kong, China, 2015.

7. Международная научная конференция студентов, аспирантов и молодых ученых «Ломоносов-2016», Москва, Россия, 2016.

8. 15th International Workshop «Algebraic and Combinatorial Coding Theory», Albena, Bulgaria, 2016.

9. IEEE International Symposium on Information Theory, Barcelona, Spain, 2016.

Публикации

Результаты автора по теме диссертации опубликованы в 10 работах, список которых приведен в конце автореферата. Среди них 3 работы [1]-[3] в журналах из перечня ВАК и 7 работ [4]-[10] в рецензируемых трудах международных конференций.

Структура и объем диссертации

Верхние оценки R(s,)

Доказательство. Сначала докажем утверждение 1. При выводе теоремы 1.2.2 мы применяем метод случайного кодирования для ансамбля двоичных равновесных кодов, который является обобщением метода, разработанного в [16] для классического случая дизъюнктивных s-кодов. Зафиксируем параметр Q, 0 Q 1. Будем использовать обозначения (1.1.1)-(1.1.2), введенные для определения СП (й,)-кода X длины N и объема t. Для произвольного кода X и произвольного множества S С [], символом x(S) = {x(j) : j Є S} обозначим соответствующее подмножество кодовых слов кода X. Для любых непересекающихся множеств S, С С [], S = s, \С\ = : S П С = 0, соответствующую пару (ж(е ),ж()) подмножеств кодовых слов кода X будем называть (s,)-хорошей парой, если существует строка Хі: і Є [TV], в которой Xi(j) = 0 для любого j Є S, и ж (А;) = 1 для любого к Є С

В противном случае, пару (ж(е ),ж()) будем называть (s,)-nAoxou парой. Столбец x(j) назовем (в,)-плохим столбцом в коде X, если в X найдется (й,)-плохая пара (x(S),x(C)) и столбец x(j) Є х(С).

Определим E(N,t,Q) - ансамбль двоичных (N х )-матриц X с N строками и t столбцами, где столбцы выбираются независимо и равновероятно из множества, состоящего из UQNI) столоЦв фиксированного веса [Ql\\. Пусть множества S и С зафиксированы. Для ансамбля E(N,t,Q) символом Po(N,Q,s,) обозначим вероятность события: «пара (x(S),x(C)) является (s, )-плохой». Очевидно, что Po(N,Q,s,) не зависит от выбора S и С Для ансамбля E(N,t,Q) символом Pi(N,t,Q,s,) обозначим не зависящую от j Є [t] вероятность события: «столбец x(j) является (Й,)-ПЛОХИМ в коде X». Нетрудно видеть, что

Для завершения вывода утверждения 1 остается вычислить в явном виде функцию A(s,,Q) и показать, что правая часть (1.2.12) задается (1.2.6).

Будем использовать терминологию типов [10] последовательностей. Рассмотрим 2 фиксированных набора, состоящих из двоичных равновесных столбцов длины TV: и вес столбца ж(г) = \y{j)\ = [QX\ для любых і Є [s], j Є []. Первый набор образует двоичную (TV х й)-матрицу XS, а второй набор - (TV х )-матрицу У . Сопоставим данным матрицам их типы, т.е. наборы целых чисел {п(а)}, а = ( 2і, аг, 2S) Є {0,1}S, и {m(b)}, b = (pi, 62, M {0,1} , где элемент набора n(a), 0 n(a) TV, (m(b), 0 m(b) TV) определяется как количество строк в матрице Xs (У ); совпадающих с а (Ь). Очевидно, что для любых двоичных матриц Xs и Yi сумма

Через п(0) (т(1)) будем обозначать число нулевых (единичных) строк в Xs (Yi). Заметим, что если TV — п(0) т(1), то соответствующая пара (Xs,Yi) является (s,)-хорошей. В остальных случаях, число различных пар матриц (Xs, У ), которым сопоставлены фиксированные типы (n(a)j, m(b)}), равно т-г м, а доля (s, Л-плохих пар из общего чис VI

Пусть N — оо и п(а) = 7V[r(a) + о(1)], m(b) = 7V[i;(b) + о(1)], где фиксированные распределения вероятностей г = {г(а)}, а Є {0,1}S и г = {г (Ь)}, у Є {0,1} , обладают свойствами, индуцированными условиями (1.2.14), т.е. г(а) = і? 2 vfo) = i г( ) + (-0 i

С помощью формулы Стирлинга для типов, соответствующих этим распределениям, находим логарифмическую асимптотику слагаемого в (1.2.13):

Будем искать минимум функции F = F(r v Q) при ограничениях (1.2.15). Поскольку функция F непрерывна в рассматриваемой области допустимых значений аргумента (г, v), в том числе и на ее границе, то достаточно найти минимум F при условиях (1.2.15) с исключенными границами. Запишем соответствующую задачу минимизации: F — min.

Заметим, что уравнения ограничений (1.2.17) образуют аффинное подпространство G в M2S+2 размерности (2s + 2і — (s + + 2)). Откуда вытекает, что функция F строго выпукла и в G П X, что в свою очередь означает, что в GflX локальный минимум функции F является глобальным и единственным. Далее воспользуемся теоремой Каруша-Куна-Таккера [2], утверждающей, что всякое решение, удовлетворяющее системе (1.2.18), ограничениям (1.2.17) и имеющее положительно определенную матрицу вторых производных лагранжиана в этой точке, является локальным минимумом функции F. Таким образом, если есть решение системы (1.2.18) и (1.2.17) в области X, то оно единственно, и эта точка является минимумом функции F на X.

Докажем, что из симметрии задачи следует равенство: /І = \і\ = /І2 = ... = fis. Достаточно показать, что щ = fij для і ф j. Пусть а = (О,..., 1,..., 0) обозначает s-строку, в которой на г-м месте стоит 1. При перестановке индексов г и j мы получим задачу минимизации, эквивалентную исходной. Следовательно, если (TQ,VQ) - решение, то решением будет также и (TQ,VQ), ДЛЯ которого вероятнорсть тД(а) = Тд(а), где а- строка, полученная перестановкой индексов і и j из строки а. Из единственности решения TQ следует, что распределения (TQ,VQ) И (TQ,VQ) совпадают. В частности, вероятность тк(зц) = гА(а ). Равенство множителей Лагранжа вытекает из первого уравнения в системе (1.2.18). Используя те же рассуждения, можно доказать, что v = v\ = v i = ... = Уц.

Нижние оценки C(s,)

Будем пользоваться терминологией и обозначениями, ранее введенными в 1 главе настоящей диссертации. Двоичный код X объема t и длины N будем также называть (N, Д)-кодом, где параметр R = log2t/N. Пусть , д I х при х О, [х\ = при х О, и h{x) = — x\og2x (1 х) 1ё2(1 X)i 0 ж 1, обозначают положительную часть функции х и двоичную энтропию. Зафиксируем два натуральных числа s и такие, что s + t. Определим множество всевозможных s-подмножеств множества [t] Vs(t) = {S : S С [t], \S\ = s}. Определение 2.1.1. Пусть X = (ж(1), ж(2),..., x(t)) произвольный двоичный код длины N и объема t. Множество S Є Vs(t) будем называть (s,)-плохим для кода X, если существует такое множество , С \t\\S, мощности \С\ = , что \J x(j) )р Л x(j). (2.1.1) В остальных случаях будем говорить, что S является (s,)-хорошим множеством для кода X. Символом B(s,,X) (G(s,,X)) будем обозначать все (й,)-плохие ((s, )-хорошие) множества для кода X. Тогда выполнены следующие неравенства на мощность соответствующих множеств:

Предложение 2.1.1. Любое (s, + 1)-хорошее ((s,)-плохое) множество для кода X является (s,)-хорошим ((s, + 1)-плохим) для кода X. Таким образом, верны следующие включения: B(s,,X) С B(s, + 1,Х) и G(s, + 1,X) с G(s,,Х). Определение 2.1.2. Зафиксируем параметр є, 0 є 1. Двоичный код X будем называть почти свободным от перекрытий (s,)-кодом с вероятностью ошибки є (ПСП (s,,e)-KodoM), если B(s,,X) /А ттг є = G(S,,A) (1 — є) . (2.1.2) ( ) s Непосредственно из определений следует Предложение 2.1.2. Любой ПСП (s, + 1,є)-код является ПСП (s,,e)-кодом. Более того верно аналогичное свойство монотонности по параметру s, которое может быть записано в виде Предложение 2.1.3. Если X является ПСП (s, , є)-кодом объема t и длины N, тогда существует ПСП (s — 1, , є)-код X объема t — 1 и длины N.

Доказательство. Пусть B(s,,X, і) = {S : і Є S Є B(s,,X)} обозначает совокупность всех (s, )-плохих множеств S для кода X, содержащих элемент і Є [t]. Заметим, что тогда для мощностей B(s,,X,г), 0 B(s,, X,г) (SII), И, выполнено B(s,,X,i)=s-B(s,,X) s є, г=1 причем в неравенстве мы воспользовались определением 2.1.2. Отсюда следует, что существует такое j Є [t], для которого

Тогда несложно видеть, что X , полученный из X удалением столбца x(j), является ПСП (s — 1,-,є)-кодом объема t — 1 и длины N. П Пользуясь классической терминологией [10,26], дадим следующее определение. Определение 2.1.3. Зафиксируем параметр R, R 0. Ввиду неравенства (2.1.2) определим ошибку для ПСП (s,, є)-кодов:

Из определений 2.1.1 - 2.1.3 и предложений 2.1.1-2.1.3 вытекает Теорема 2.1.1. Имеют место следующие неравенства C(s + 1,) C(s,) C(s, — 1). (2.1.6) Из доказанных ранее оценок выделим границу случайного кодирования для величины C(s, 1), полученную в работе [37].

Одним из центральным результатов настоящей работы является следующая теорема, в которой мы развиваем метод, используемый в [16]. Доказывается граница случайного кодирования для C(s,) при ) 2, численные значения которой при малых значениях параметров s и указаны в таблице 2.4. Также в теореме произведен анализ асимптотики полученной границы при фиксированном и s — сю.

Зафиксируем параметры Q, 0 Q 1, и і?, О Д 1. Определим ансамбль i?(7V, , Q), состоящий из двоичных (7V х )-матриц X = (ж(1), ж(2),... ж()), где столбцы х(і), і Є [i\,t = _2ДЛГ], выбираются независимо и равновероятно из множества (\QN\) столбцов фиксированного веса [QN\. Зафиксируем также два множества S, С С [], таких что S = s, \С\ = и «Sfl/2 = 0. Из (2.2.8) вытекает, что в ансамбле {N,t, Q} математическое ожидание B(s,,X) числа B(s,,X) равно B(s,,X) = \Vs(t)\ Pr {S Є B(s, ,X)} . Таким образом, математическое ожидание вероятности ошибки для ПСП (s, )-кодов равно ск {s,,R,Q) = \Ps(t)\ B(s,, A J = Pr {о Є B(s,, A J} , (2.2.9) где число = _2ДЛГ]. Тогда очевидная случайная верхняя граница для вероятности ошибки (2.1.3) для ПСП (Й,)-кодов может быть записана следующим образом:

Таблица наилучших границ C(s,)

Рассмотрим семейство J-(t, s, ), которое будет состоять из таких гиперграфов Н = (V,E), что множество вершин V = {1,2.../:}, множество ребер Е = {еі, Є2,..., es/}, s s, и размер каждого ребра причем никакое ребро не содержится ни в каком другом:

Предположим, что задан скрытый гиперграф Нип = (У, Е1), ребра которого нам неизвестны, но мы знаем, что Нип Є J-(t,s,). Наша цель - обнаружить ребра Е этого гиперграфа, спросив N вопросов (тестов) Q(S), где множество S - это некоторое подмножество У, а ответ на вопрос положительный, т.е. Q(S) = 1, в случае, если множество S содержит полностью хотя бы одно ребро из Е. В остальных случаях ответ на вопрос отрицательный, т.е. Q(S) = 0. Будем называть поиск неадаптивным, если все вопросы заранее спланированы и задаются одновременно. Если же вопросы задаются последовательно, и последующие вопросы зависят от ответов на предыдущие, то поиск называют адаптивным. Промежуточным видом между адаптивным и неадаптивным поиском является многошаговый алгоритм. Прежде чем дать формальное определение, введем несколько вспомогательных.

Заметим, что N тестов неадаптивного алгоритма поиска можно записать в виде N х t матрицы поиска X. Столбец x(j) поставим в соответствие j-й вершине V; строчку ХІ поставим в соответствие г-й тест. Пусть u v обозначает дизъюнктивную сумму двух столбцов u, v Є {0,1} . Для произвольного гиперграфа Н = (V, Е) определим вектор-ответов:

Определение 3.1.1. Пусть задан скрытый гиперграф Нип Є J-(t,s,). Будем говорить, что Л является р-шаговым алгоритмом поиска скрытого гиперграфа из семейства J-(t,s,), если выполнено следующее: 1. задан код Х\ = ХД соответствующий первому шагу поиска (можно считать, что вопросы внутри одного шага тестирования задаются одновременно); 2. код Xj, соответствующий г-му шагу поиска, определяется как ХІ = Хг (r(Xi, Нип),..., r(Xj_i, Нип))] 3. можно точно определить Нип, используя векторы-ответы r(Xi, Нип), г(Х2, Нип),..., г(Хр, Нип). Пусть Nf-{Hun) равно числу тестов на г-м шаге при поиске Нип с помощью алгоритма Л. Тогда определим число тестов в худшем случае:

Символом T\h (t, s, ) обозначим минимальное число тестов 1\ среди всевозможных р-шаговых алгоритмов Л поиска скрытого гиперграфа из семейства J (t, s,). Определим асимптотическую скорость р-шаговых алгоритмов поиска скрытого гиперграфа как

Тогда асимптотическую скорость неадаптивного поиска можно понимать как R st(s,). Очевидно, что выполнена цепочка неравенств it a(s,) = Rhst(s,) Rhst(s,) ... Rh{s-,) Наиболее важными границами для скорости являются оценки для крайних величин, но и оценки для промежуточных величин также представляют определенный интерес.

Далее определим, что будем понимать под пропускной способностью Lh (s,i) для р-шагового алгоритма поиска скрытого гиперграфа.

Определение 3.1.2. Будем говорить, что Л является р-шаговым алгоритмом поиска скрытого гиперграфа из семейства J-(t,s,) с вероятностью ошибки , если выполнено следующее: существует такое подмножество J- С J-(t,s,) мощности \ \ (1 — e)\J-(t, s,)\, что для всякого Нип Є Т алгоритм Л позволяет (в смысле ранее указанных условий 1-3 в определении 3.1.1) точно определить Нип.

Заметим, что ранее введенное определение 3.1.1 можно понимать как алгоритм поиска с вероятностью ошибки 0. Пусть Nf-{Hun) число тестов на г-м шаге при поиске Нип с помощью Л. Тогда определим число тестов в худшем случае: р N = max у Nf{Hun). лтР-st ft л T A Символом iV (t, s,, є) обозначим минимальное число тестов 1\ среди всевозможных р-шаговых алгоритмов Л поиска скрытого гиперграфа из семейства J-(t, s,) с вероятностью ошибки є. Определим пропускную способность р-шаговых алгоритмов поиска скрытого гиперграфа как pst log2t Lh (s,i) = lim . (3.1.3) г о h Si iє) Тогда пропускную способность неадаптивного поиска, определение которой было дано в введении настоящей работы, можно понимать как Cl st(s,). 1-h Отметим, что выполнена очевидная цепочка неравенств C a(s,) = Chst(s,) Chst(s,) ... C%(s,). 3.2 Оценки Rh(s,) В работе [19] было показано, что задача неадаптивного поиска скрытого гиперграфа и свободные от перекрытия коды сильно связаны между собой. В частности, верна следующая теорема. Теорема 3.2.1. [19]. Для R1fla(s ) и R(s,) верна цепочка неравенств Rha(s,) R{s, ) min (R a(s — 1, ), R%a(s, — 1)). (3.2.1) Отметим, что при = 1 задача поиска скрытого гиперграфа вырождается в довольно известную задачу поиска дефектов. Известно [15], что адаптивный поиск дефектов достигает теоретико-информационную границу, т.е. Rh(s, 1) = -. (3.2.2)

Доказательство. Пусть Нип = (V, Е) является скрытым гиперграфом из семейства J-(t, s, ). Напомним, что вершину v Є V мы называем активной, если существует по крайней мере одно ребро є Є і?, такое что v Є е. Символом F, F С У, обозначим множество найденных к текущему моменту активных вершин. Символом Е1, Е С Е, обозначим множество найденных к текущему моменту ребер гиперграфа Нип, т.е. если е G и е С F, тоеє Е . Заметим, что пара (V, Е ) задает частичный гиперграф Нип. Пусть S, S С V, -это вопрос, который мы будем задавать в текущий момент. Прежде чем мы применим предложенный алгоритм, мы зададим F = 0, Е = 0 и S = V.

Во-первых, опишем алгоритм, отмеченный как алгоритм 2, который позволяет находить новые активные вершины -и, т.е. такие что v F. Входными параметрами данного алгоритма являются множество F, а также вопрос S, который содержит по крайней мере одно ребро є Є Е и е Е . Зададим множества S = S \ F и S" = S \ Sf. На каждом шаге множество S будет содержать по крайней мере одну активную вершину. Пока мощность 5" 1, мы запускаем следующую процедуру. Делим множество S на примерно равные по размеру множества S\ и 5 2, т.е. S = S\U S2, 5і = [5 //2] и 52І = LI S /2J. Далее мы задаем вопрос S\ U S". Если Q{S\ U S") = 1, то это означает, что Si содержит по крайней мере одну новую активную вершину, т.к. из предыдущих шагов очевидно выполнено, что Q(Sff) = 0. Далее положим S = Si и повторим процедуру. Если Q(Si U S") = 0, то это означает, что по крайней мере одна активная вершина содержится в множестве 5 2, т.к. из предыдущих шагов очевидно выполнено, что Q(Si U U S") = 1. Далее положим S = 5 2, Sff = Si L\ Sff и повторим процедуру. По окончании процедуры (5" = 1) мы знаем, что единственная вершина v множества S является активной вершиной гиперграфа Нип и v F. Отметим, что алгоритм 2 является вариацией бинарного поиска вершины.

Оценки Rh(s,)

Доказательство. Пусть Нип = (V, Е) является скрытым гиперграфом из семейства J-(t, s, ). Напомним, что вершину v Є V мы называем активной, если существует по крайней мере одно ребро є Є і?, такое что v Є е. Символом F, F С У, обозначим множество найденных к текущему моменту активных вершин. Символом Е1, Е С Е, обозначим множество найденных к текущему моменту ребер гиперграфа Нип, т.е. если е G и е С F, тоеє Е . Заметим, что пара (V, Е ) задает частичный гиперграф Нип. Пусть S, S С V, -это вопрос, который мы будем задавать в текущий момент. Прежде чем мы применим предложенный алгоритм, мы зададим F = 0, Е = 0 и S = V.

Во-первых, опишем алгоритм, отмеченный как алгоритм 2, который позволяет находить новые активные вершины -и, т.е. такие что v F. Входными параметрами данного алгоритма являются множество F, а также вопрос S, который содержит по крайней мере одно ребро є Є Е и е Е . Зададим множества S = S \ F и S" = S \ Sf. На каждом шаге множество S будет содержать по крайней мере одну активную вершину. Пока мощность 5" 1, мы запускаем следующую процедуру. Делим множество S на примерно равные по размеру множества S\ и 5 2, т.е. S = S\U S2, 5і = [5 //2] и 52І = LI S /2J. Далее мы задаем вопрос S\ U S". Если Q{S\ U S") = 1, то это означает, что Si содержит по крайней мере одну новую активную вершину, т.к. из предыдущих шагов очевидно выполнено, что Q(Sff) = 0. Далее положим S = Si и повторим процедуру. Если Q(Si U S") = 0, то это означает, что по крайней мере одна активная вершина содержится в множестве 5 2, т.к. из предыдущих шагов очевидно выполнено, что Q(Si U U S") =

Далее положим S = 5 2, Sff = Si L\ Sff и повторим процедуру. По окончании процедуры (5" = 1) мы знаем, что единственная вершина v множества S является активной вершиной гиперграфа Нип и v F. Отметим, что алгоритм 2 является вариацией бинарного поиска вершины. Во-вторых, опишем алгоритм, отмеченный как алгоритм 3, который позволяет находить все ребра Е , которые можно составить из уже найденных активных вершин F. Единственным входным параметром является множество F. После того, как мы найдем новую вершину -и, мы можем обновить множество ребер Е, если будем искать только ребра, содержащие v. Но поскольку \F\ si С t (число вопросов данного алгоритма будет невелико), то зададим Е = 0 и запустим следующую процедуру по всем множествам S, таким что S С F и \S\ І. Если не существует такого ребра е, что є Є Е и е С 5, то мы задаем вопрос S. Если Q(S) = 1, то мы удаляем все ребра є Є Е , такие что S С е, и добавляем ребро е = S к множеству ребер Е . Отметим, что алгоритм 3 является исчерпывающим поиском ребер.

В-третьих, опишем алгоритм, отмеченный как алгоритм 4, который позволяет находить множество (вопрос) S, S С V, такое что S содержит по крайней мере одно ребро е, такое что є Є Е и е Е (и как следствие множество S содержит по крайней мере одну активную вершину v F). Единственным входным параметром является множество Е . Зададим множество А как множество вершин, входящих в по крайней мере одно ребро є Є Е, множество B = V\AиS=0. Очевидно, что \А\ si С . запустим следующую процедуру по всем множествам С, С С У, таким что ВсС,и eG Е, е С С. Если Q(C) = 1, то мы задаем S = С и выходим из процедуры. Если Q(C) = 0, то мы рассматриваем следующее множество С. Если мы закончили процедуру и имеем S = 0, то это означает, что мы нашли все ребра гиперграфа Нun, т.е. Е = Е. Отметим, что алгоритм 4 является исчерпывающим поиском вопроса.

Таким образом, мы разбили основной алгоритм адаптивного поиска скрытого гиперграфа из семейства J-(t, s, ) на несколько частей. Полное описание стратегии поиска скрытого гиперграфа представлено алгоритмом 1, и он основывается на алгоритмах 2, 3 и 4. Полагаем F = 0, Е = 0 и S = V. Пока выходом алгоритма 3 является непустой вопрос S Ф 0, мы запускаем следующую процедуру. С помощью алгоритма 2 мы находим вершину v и добавляем ее к F. Далее мы используем алгоритм 3, чтобы обновить множество ребер Е", составленных из уже найденных активных вершин F. После этого запускаем алгоритм 4 для того, чтобы найти подходящий вопрос S, который далее будет использоваться алгоритмом 2.

Пусть \V\ = t. Несложно проверить, что алгоритм 2 использует не более log2 15 1] log2] тестов. Легко видеть, что общее число активных вершин в графе из семейства J-(t,s,) не превосходит si. Алгоритм 4 использует не более F s i) тестов, а алгоритм 3 — не более F (s,i) тестов, где функции F и F% не зависят от t. Также можно оценить число циклов в алгоритме 1 максимальным количеством активных вершин, т.е. si. Таким образом, общее число тестов для данного адаптивного алгоритма поиска скрытого гиперграфа из семейства J-(t,s,i) не превосходит s(log2 + F (s,i) + F s i) + 1). Исходные параметры: множество вершин V гиперграфа