Асимптотические задачи комбинаторной теории кодирования и теории информации тема диссертации и автореферата по ВАК РФ 01.01.05, кандидат физико-математических наук Виленкин, Павел Александрович

• Виленкин, Павел Александрович
• кандидат физико-математических наук
• 2001

Оглавление диссертации кандидат физико-математических наук Виленкин, Павел Александрович

Введение

Глава

В данной главе рассматривается следующая задача. Фиксирован </-ичный алфавит А = {0,1,., q — 1}, на котором задана произвольная метрика 6(-, •). На множестве Ап, состоящем из всех векторов (слов) вида х = (ej, .жп), Х{ £ А, вводится аддитивная метрика :

Для произвольного подмножества (кода) С С Ап мы определяем минимальное S -расстояние <$(n)(C) = min<$(п)(х,у), где минимум берется по всем парам кодовых слов х,у € С, х ф у. Ставится задача об исследовании скорости кодов с заданным <$-расстоянием, т. е. функции ад £ IE ЬЬМРШ, п-юо п d > О, где величина D > О, равна максимальному объему кода С С Ап, <fW(C) > D.

Данную задачу можно отнести к фундаментальным вопросам теории информации. Главным образом она изучалась для метрики Хемминга (5(х,у) = 1 для всех х ф у) в связи с приложениями к теории передачи сообщений по каналу связи. До конца эта задача до сих пор не решена, т.е. функция 1Zs(d) точно не известна. Для нее имеются лишь различные границы сверху и снизу. Соответственно, и результаты настоящей работы, описывающие случай произвольной метрики 5, заключаются в ряде верхних и нижних границ функции TZs(d).

Наиболее известная граница снизу для метрики Хемминга получена методом Варшамова-Гильберта (или случайного кодирования). Для некоторых случаев она может быть улучшена.

Что же касается верхних границ, то для них имеется большое число различных методов. Классическими можно назвать границы Хемминга, Плоткина и Элайса [9]. Наилучшей же на сегодняшний момент является граница линейного программирования [16].

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

Одно из таких приложений возникло недавно в связи с некоторыми задачами молекулярной биологии. Оно подробно рассматривается во второй главе настоящей диссертации. При этом вводится новый тип кодов, называемых кодами подобия, скорость которых выражается через скорости кодов с расстоянием в некоторой специальной метрике, которую мы называем метрикой подобия. Это обстоятельство и привело к необходимости построения границ функции скорости TZg(d) для различных метрик 8.

Обратим внимание на две сравнительно недавние работы, в которых рассматривается аналогичная задача. В [27] данный вопрос изучается с точки зрения связи между объемами кодов с расстоянием и дизайнов в метрических пространствах с мерой. С помощью ортогональных полиномов там строятся универсальные границы скорости кодов. В работе [45] рассматривается произвольная метрика и строятся границы скорости, основанные главным образом на методах случайного кодирования и сферической упаковки.

Важным обстоятельством является то, что в обеих работах [27, 45] на метрику не накладывается условие аддитивности. Это не позволяет использовать метод типов (т. е. коды фиксированной композиции) для получения требуемых оценок скорости. В настоящей работе с помощью данного метода и рассуждений, аналогичных применяемым в оценках Варшамова-Гильберта (случайного кодирования), Хемминга, Плоткина и Элайса, мы получаем обобщения данных оценок для различных классов метрик. Также обсуждаются вопросы о сравнении границ друг с другом и об их численном построении. Заметим, что все полученные оценки выражаются через функции, входящие в показатели экспонент для вероятностей больших уклонений сумм некоторых случайных величин.

При этом границы случайного кодирования, Хемминга и Плоткина справедливы для любых метрик, а граница Элайса — только для тех, для которых выполнено специальное условие выпуклости среднего значения (опр. 1.3, стр. 14). В разделе 1.4.3 показано, что данному условию удовлетворяют все метрики подобия, что позволяет в полной мере использовать полученные результаты для исследования кодов подобия. Вообще же вопрос о том, какие еще метрики удовлетворяют данному условию, остается открытым.

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

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

Данный биологический эксперимент подробно описан в

§2.4, а его математическая модель имеет следующий вид. Рассматривается четверичный алфавит Л = {0,1,2,3}. На нем задана весовая функция w: u;(0) = w(3) = 2, ги(1) = w(2) = 3. На ее основе определяется следующая бинарная алфавитная функция w -подобия Sw:

На множестве Лп вводится соответствующая аддитивная функция w -подобия для векторов

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

Ставится задача об исследовании кодов С С Лп, удовлетворяющих следующим свойствам для заданных чисел 5 > 0 и Д > 0:

Глава если а = Ь, если х ф у,

4nW) = ££»(®i'K)> х,уе А".

1) <siT'(x,x) > S + Д для каждого кодового слова х £ С;

2) (х, у) < S для каждой пары кодовых слов х, у £ С, х ф у.

Такие коды мы называем подами с параметрами w-подобия (S, Д). Кроме того, про любой такой код мы говорим, что он имеет порог w-подобия Д.

Учитывая отмеченную выше связь между подобием и расстоянием, можно заметить, что условие 2) близко к тому, что код поддерживает определенное минимальное расстояние между различными кодовыми словами. Условие 1) сводится к некоторому ограничению на композиции рассматриваемых слов, поскольку величина <si"^(x, х), которую мы называем самоподобием вектора х £ Лп, полностью определяется композицией х.

Данная задача рассматривалась в работе [46]. Были получены некоторые оценки на функции скорости соответствующих кодов. Все они являются частными случаями более общих и точных границ, построенных в настоящей работе.

Далее мы обобщаем эту задачу, рассматривая произвольный алфавит Д={0,1,.,</-1} и произвольную весовую функцию w на нем, которая принимает строго положительные значения. Обозначим через Д) максимальный объем кода С С Лп, имеющего параметры ад-подобия (5, Д). Через Mw (Д) мы обозначим максимальный объем кода, имеющего порог го-подобия Д. Определим функции скорости данных кодов следующим образом:

Задача заключается в исследовании данных функций. В работе показано, что эти функции выражаются через скорость кодов с расстоянием 7Zs(d) в метрике 5 = 5W, которая имеет вид

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

Практические приложения накладывают на код еще одно дополнительное условие, которое имеет следующий вид. На алфавите вводится операция сопряжения, т. е. каждому элементу а £ А ставится в соответствие сопряженный ему элемент а £ Л (возможно, совпадающий с а), причем а = а для любого а £ Л. В частности, для исходного примера рассматривается следующее сопряжение: 0 = 3, 1=2, 2 = 1, 3 = 0.

Далее определяется операция обратного сопряжения для векторов х £ Лп, которая имеет следующий вид: если х = х2,., жп), то обратно сопряженным к нему называется вектор = (хп,., х2, xi). Очевидно, что повторное применение данной операции к слову переводит его обратно в х.

Код С С Лп называется самосопряженным, если, во-первых, он замкнут относительно данной операции, т. е. ^с £ С для любого кодового слова х £ С, и, во-вторых, он не содержит самосопряженных слов, т. е. ^х ф х для любого х £ С. В этом случае можно считать, что код составлен из пар слов {х, ^Г}, причем оба слова во всех парах различны.

В исследуемой практической задаче молекулярной биологии возникает потребность в кодах подобия, которые удовлетворяют данному условию самосопряженности. Поскольку последнее является дополнительным ограничением, то очевидно, что скорость таких кодов не превосходит скорости кодов подобия, т. е. верхние оценки для нее сохраняют силу. В работе показано, d > 0. s > 0, d > 0, $w{x,y) = д w(x) + w(y) ~ при х ф у, х,у е Л. что и нижние оценки для данной величины, полученные методом случайного кодирования, также не меняются при учете условия самосопряженности. Таким образом, введение условия самосопряженности не влияет на результаты, полученные в работе.

Рассматриваемая задача является новой. Как уже было отмечено, она возникает в математической модели некоторых экспериментов молекулярной биологии, в которых используются специальные свойства ряда химических веществ (в частности, молекул дезоксирибонуклеиновой кислоты и рибонуклеиновой кислоты — ДНК и РНК). Данные молекулы могут сцепляться друг с другом, образуя двойки, каждая из которых характеризуется прочностью. В рассматриваемой нами модели прочность каждой двойки равна значению функции подобия на соответствующих векторах. Требуется найти такое семейство молекул, чтобы каждая образовывала прочную пару с равной себе и слабую пару с любой другой молекулой. Эти требования в точности приводят к свойствам 1) и 2), входящим в определение кодов подобия. Более подробное описание эксперимента и обсуждение используемой нами математической модели приведено в

§2.4.

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

Глава

Глава посвящена исследованиям дизъюнктных кодов. Дизъюнктным (s, -кодом (где s и / — целые числа) объема t > s + £ и длины N мы называем двоичную матрицу, содержащую N строк и t столбцов, обладающую следующим свойством: для любых двух непересекающихся множеств столбцов, имеющих объемы s и £, найдется такая строка матрицы, в которой все s столбцов содержат нули, а все £ столбцов — единицы.

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

§3.1.

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

Для частного случая 1 = 1 дизъюнктные коды были впервые введены в работе [4]. С тех пор они активно изучались. В работах [17, 18, 22] были построены границы скорости дизъюнктных (s, 1) -кодов, которые являются наилучшими на настоящий момент. Некоторые конструкции данных кодов рассматривались в работах [32, 43, 44].

Насколько известно автору, дизъюнктные (s, ^)-коды в общем виде впервые рассматривались в [21]. В работах [29, 31, 50] рассматриваются верхние границы скорости таких кодов.

Также отметим, что имеется отдельное независимое направление, в котором дизъюнктные (2, 2)-коды рассматривались в связи с исследованиями разделяющих систем. Для этого частного случая получены и границы скорости, и конструкции. Обзор соответствующих результатов имеется в работе [25].

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

В настоящей работе получены следующие результаты. Построена нижняя оценка скорости дизъюнктных (s,£) -кодов. Она основана на методе случайного кодирования и обобщает известную аналогичную границу для частного случая £ = 1 [17, 18, 22]. Также получена верхняя граница, которая немного (примерно в два раза) улучшает оценку из работы [50], однако выражается менее простой формулой.

Также в работе приводится ряд результатов, относящихся к двум конструкциям дизъюнктных кодов. Первая — это известная каскадная конструкция, которая позволяет получать новые дизъюнктные (s, ^)-коды больших объемов из существующих разделяющих g-ичных (s, £) -кодов больших объемов и дизъюнктных (s,^)-кодов объема q. Эта конструкция является известной: она приведена в работе [25], а также на ней основаны конструкции дизъюнктных (s, 1)-кодов в работах [43, 44]. Задача о построении разделяющих кодов больших объемов также исследовалась ранее. Мы подробно на ней не останавливаемся, ограничиваясь формулировкой одного известного метода построения разделяющих кодов из кодов с максимально достижимым расстоянием (МДР). Новым результатом является таблица дизъюнктных (2, 2)-кодов малых объемов. Некоторые из них были известны ранее [25], однако большинство являются новыми. Отметим, что при построении этой таблицы были использованы некоторые новые идеи, которые представляются достаточно перспективными и, по мнению автора, могут получить дальнейшее развитие. Построение таблицы осуществлено совместно с А. Г. Дьячковым и В. С. Лебедевым.

В работе [32] появилась новая идея построения дизъюнктных (s, 1)-кодов на основе матриц инцидентности. В настоящей работе находится один из параметров кодов, построенных данным методом. Также вводится и исследуется обобщение данной конструкции.

Глава

В данной главе рассматривается следующая задача. Дана последовательность независимых одинаково распределенных случайных величин. Мы рассматриваем два случая: дискретный, при котором максимальный шаг распределения равен единице, и абсолютно непрерывный, при котором распределение обладает плотностью. Заметим, что формулировки результатов для этих двух случаев дословно совпадают.

Обозначим через Sn сумму первых п членов данной последовательности. Для этой случайной величины определяется энтропия Шеннона Нп и энтропия Реньи порядка О! > 1 Нп(а). Ставится вопрос об отыскании асимптотики этих величин при п —> оо.

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

В настоящей работе все эти результаты значительно уточняются, приобретая законченный вид, а также обобщаются на случай энтропии Реньи. При условии конечного второго момента, как и выше, найден главный член рассматриваемых величин. Если же конечен момент порядка N > 3, то построено разложение по степеням п с остаточным членом о (п 2~^ . Заметим, что представление энтропии с точностью до бесконечно малой величины имеет место при конечном третьем моменте распределения, а не четвертом, как ранее.

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

Автор выражает глубокую благодарность своему научному руководителю доктору физико-математических наук профессору Дьячкову А. Г. за постановку задач и постоянное внимание к работе.

Глава 1.

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

Данная

глава устроена следующим образом. В

§1.1 даются основные определения и постановка задачи. В

§1.2 мы вводим некоторые вспомогательные обозначения и функции. Основные результаты сформулированы и доказаны в

§1.3. Некоторые вспомогательные и технические утверждения вынесены в

§1.4.

§1.1. Постановка задачи и исторический обзор

Рассмотрим произвольное целое число q > 2. На всем протяжении данной главы оно будет фиксированным. Все логарифмы берутся по основанию q.

Символом А будем обозначать q-ичный алфавит А = {0, l,.,q — 1}. На нем задана произвольная алфавитная метрика 8 = 6(х,у), х,у £ А.

Для целого числа п > 1 обозначим через Ап множество всевозможных векторов (слов) вида х = (ж1,., хп), Xi £ А. Определим на нем аддитивную метрику , соответствующую алфавитной метрике 8, т.е. для произвольных слов х = (а?!,., хп) Е Ап и у = (ji.уп) € Ап положим

Определение 1.1. Произвольное подмножество С С Ап будем называть кодом длины п. Минимальным 8 -расстоянием кода С называется величина j(n>(C)= min <S(n)(x,y). v ' x,y ее Хфу

Мы говорим, что код С С Дп имеет 8-расстояние D > 0, если <S(n)(C) > D.

Определение 1.2. Функцией скорости (g-ичных) кодов с заданным минимальным (5-расстоянием называется функция

TZs(d) й ПЕ bg^n)(dn), d > О, где величина Mg%\D) равна максимальному объему кода длины п с <5-расстоянием D:

M(sn)(B) = max {|С| : <5<n>(C) > d} , D > 0. (1.4)

В настоящей главе строятся верхние и нижние общие (т.е. справедливые для различных классов метрик) границы для функции lZs(d). Ранее данная задача активно изучалась для некоторых специальных метрик: Хемминга (8(х,у) = 1 для всех х ф у), Ли [9] и некоторых других. Наиболее известной границей снизу является оценка Варшамова-Гильберта (она же получается с помощью метода случайного кодирования). Для некоторых случаев она может быть улучшена (см. обзор в работе [45]). Классическими верхними границами считаются оценки Хемминга, Плоткина и Элайса [9] (последняя равномерно лучше первых двух). В работах [13,14] граница Элайса была улучшена. Наилучшей же на сегодняшний момент является граница линейного программирования [16].

Еще раз отметим, что данные границы были построены в основном для метрики Хемминга. Случай произвольных метрик ранее практически не рассматривался. Только недавно стали появляться работы, в которых строятся общие оценки. В [27] исследуется связь между объемами кодов с расстоянием и дизайнов в метрических пространствах с мерой. С помощью ортогональных полиномов там же строятся универсальные границы скорости кодов. Отметим также работу [45], где рассматривается произвольная метрика и строятся границы скорости, основанные на методах случайного кодирования и сферической упаковки.

В обеих работах [27, 45] на метрику не накладывается условие аддитивности (1.1). Это не позволяет использовать метод типов (т. е. коды фиксированной композиции) для получения требуемых оценок скорости. В настоящей работе с помощью данного метода и рассуждений, аналогичных тем, на которых основаны оценки Варшамова-Гильберта (случайного кодирования), Хемминга, Плоткина и Элайса, мы получаем обобщения данных оценок для различных классов метрик. При этом границы случайного кодирования, Хемминга и Плоткина справедливы для любых метрик, а граница Элайса — только для тех, для которых выполнено специальное условие выпуклости среднего значения, вводимое ниже. j 1.2. Вспомогательные обозначения и функции

1. Обозначим через Р множество всех вероятностных векторов на алфавите Л:

Р = \ Р = {Р0,Р1, • • • ,Pq-l) ■ Ра> О для любого (x £ Л, Ра = 1 > . ^ аеЛ )

Каждому слову х £ Лп поставим в соответствие его композицию, т. е. вектор с целочисленными компонентами с(х) = (со(х), ci(x),., cgi(x)), где са(х) — количество символов а £ Л в векторе х. Множество всех возможных композиций обозначим через CW: с(п) = < с = (с0, сх,., cgi) : са £ {0,1,2,.} для любого а £ Л, У^ са = п > . I аеЛ )

Через *4.п(с) мы будем обозначать множество слов х £ Лп, имеющих композицию с £ cw.

2. Для произвольного слова х £ композиции с' £ С'"' и числа D > 0 рассмотрим следующие подмножества Лп: х> D) й {уеЛп : 8W(x,y)<D}, (х,с\D) ± {у£Л"(с') :Sln)(x,y)<D} = BW(x,D)f)An(c').

Множество В^(х, D) будем называть 8-шаром с центром х радиуса D, а с', D) —

8-шаром фиксированной композиции с' с центром х радиуса D. Зафиксируем произвольную композицию с £ сН. Если известно, что х £ Д"(с), то в силу леммы 1.10 (стр. 27) объемы шаров (1.7) не зависят от выбора центра х. Таким образом, следующие функции определены корректно:

Vjn)(c, c',D) й |в{п)(х,с',£))|, х £ Лп(с).

3. Введем на множестве Лп два распределения вероятностей: (1.9) и (1.10). Для произвольного вероятностного вектора р € Р рассмотрим случайное слово z(p) £ Лп, все компоненты которого независимы и имеют распределение р на множестве Л, что соответствует следующему распределению вероятностей на Лп:

Pr{z(p) =х}= HftW, х £ Ап, где в случае ра = 0 и са(х) = 0 мы по определению полагаем рсаа^ = 0° = 1.

Второе распределение определяется композицией с 6 С'"' и соответствует случайному равновероятному выбору слова z(c) из множества Ап(с):

Рг (z(c) - xl ± f 1ДП(С)1-1' ПРИ Х G Лп(с)> j~l0, прих^А"(с),

1.10)

Рассмотрим произвольные вектора р, р' € Р, композиции с, с' £ CW и число D > 0. Введем вероятности следующих трех событий: vln\p,p',D) й Pr{jW(Bl(p),»2(p')) <!>}, 7>jn)(c,p',.D) й Рг {<*Н (21(с),22(р')) <d}, ^n)(c,c',Z?) й Pr{<jW(z1(c),z2(c'))<I>},

1.11) где случайные слова zi и z2 независимы и имеют распределения (1.9) или (1.10) в зависимости от аргумента.

4. Таким образом, мы ввели пять функций: объемы шаров (1.8) и вероятности (1.11). Нас интересует главный член их логарифмической асимптотики при следующих условиях: тг -» оо, все вероятностные вектора фиксированы, а все композиции и число D растут линейно по п.

Необходимо уточнить, что понимается под линейным ростом композиции. Мы говорим, что последовательность композиций с'"' растет линейно с ростом п, если отношение с(п'/п (это всегда вероятностный вектор с рациональными координатами) стремится к некоторому пределу р G Р при п -» оо. Для простоты введем отображение 7г(п) : Р —» С'"), переводящее вероятностный вектор р G Р в композицию 7п"'р G , наиболее близкую (в обычной евклидовой метрике) к вектору п • р. Далее для всех используемых композиций с G С(п) мы будем рассматривать асимптотику с = 7г(п'р, где п —)■ оо, а вектор р G Р фиксирован.

Для произвольных векторов р, р' £ Р и числа d > 0 введем следующие функции (там, где рассматриваемые пределы существуют):

Vs(p,d) д lim n—J-oo

VS(P,P \d) д lim n—>

Vr(P,P',d) Д lim n-> oo

VsP(p,p',d) A lim n—>

Vcsc(p,p',d) Д lim n—>oo

Л logvjn)(7rHp,7rWp,,dn) log?in)(P,P ',dn)

1.12)

- log РПя-Нр.р', tin) log-pjn)(7rHp,7r(n)p',dn)

Эти функции играют основную роль во всем последующем изложении. Все границы функции скорости 1Z$(d) (1.3) будут выражены через них.

В §1.4 данные функции будут исследованы более подробно. Для них будут установлены области определения, свойства монотонности и выпуклости по d. Также будут получены связи между ними. Анализ функций V<5(p, d), VjP(p,p',d) и Р^р, р', d) проводится с помощью теорем о больших уклонениях для сумм независимых случайных величин, а для исследования функций Vi(p,p', d) и ^"(р, рd) используются методы выпуклого анализа (решение выпуклых экстремальных задач с ограничениями с помощью одной из форм теоремы Куна-Таккера).

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

5. Рассмотрим числовые вектора v = (vq, v\, ., Ug-i) и w = (wo, wi,., , а также произвольный вероятностный вектор р = (po,pi,. ,pq-1) € P. Определим функционалы j(v,w)= J2 5{a,b)vawb, H(p) = - Palogpa, a,b£A a^A

1.13)

Величина H(p) — это обычная энтропия вектора р. Если р, р' 6 Р, то значение р') равно математическому ожиданию случайной величины S(z,z'), где z и z' — независимые случайные элементы алфавита А, имеющие распределения р и р'. Если же рассмотреть произвольную композицию с G С(п', то величина ^(с, с) равна сумме всех попарных расстояний между координатами любого вектора х 6 Лп(с). Введем также следующие обозначения:

•^(Р) = -^(Р.Р).

-rmax max ^(р).

1.14)

Ниже будет показано, что скорость 1Z$(d) строго положительна тогда и только тогда, когда О < d < Т)

Определение 1.3. Будем говорить, что метрика S обладает свойством выпуклости среднего значения, если квадратичный функционал ^(р) является выпуклым вверх на множестве вероятностных векторов р € Р.

Как уже было отмечено, данное свойство метрики существенно используется при выводе границы Элайса. Оно сводится к неотрицательной определенности некоторой квадратичной формы и поэтому для любой конкретной метрики может быть легко проверено непосредственно. В разделе 1.4.3 (стр. 36) будет показано, что если алфавит Л состоит из не более чем четырех элементов, то данному свойству удовлетворяет любая метрика 5. Также будет доказано простое утверждение, что свойство выпуклости среднего значения выполнено, если метрика S имеет вид

J(a, b) = w(a) + w(b), а ф b, где w — произвольная числовая функция на Л, принимающая строго положительные значения (очевидно, что для любой такой функции указанное соотношение действительно задает метрику). Заметим, что метрики такого типа играют основную роль в главе 2.

Открытым остается вопрос о том, выполнено ли данное свойство для всех возможных метрик или нет. На настоящий момент автору не известно ни одного контрпримера.

6. Через е<а) ( а £ А) обозначим вероятностный вектор, задающий вырожденное распределение (сконцентрированное в точке о), а через и — вектор, задающий равномерное распределение на А: (>) >) >) 1 — Ve0 > е1 ) • • -Cq-l)

Ve' <?'•'ч) • д | 1, при а = Ь, О, при а ф b '

1.15)

1.16)

7. Рассмотрим функцию р, Р', r) = r , max , ч I]

1.17) где р G Р, р' = (PoiPi' • • •Pq-i) ^ Р, г > 0, и максимум берется по множеству pV) = f{q(o)}^:q(o)?P, £ р'аЧ(а) = Р, £ р'аЫ^\ Л < 4 •

V а аеЛ аеЛ )

Очевидно, что величина <р(р, р', г) определена тогда и только тогда, когда г > к(р, р') = min [г > 0 : К(р, р', г) ф 0}

Величину к(р, р') можно найти как решение задачи линейного программирования к(р,р') = min

1.18)

1.19)

1.20) где минимум берется по объединению множеств /С(р,р', г) по всем г > 0, которое задается следующими линейными соотношениями q(a' G Р для всех a G Л, £ РаЧ^ = Р

Поведение функции <р{р, р', г) подробно описано в теореме 1.19 (стр. 38), доказательство которой основано на свойстве выпуклости функционала ^(р) (когда метрика удовлетворяет определению 1.3). Кроме того, в разделе 1.4.4 приводится способ вычисления величины у>(р, р', г), основанный на решении выпуклых экстремальных задач с ограничениями с помощью условий Куна-Таккера.

Рассмотрим также функцию у>(р,г) = таху>(р,р',г). Р'еР

1.21)

Ее свойства могут быть легко получены из свойств функции у(р, р', г). Они приводятся в следствии 1.19.1 (стр. 39).

§1.3. Основные результаты

1.3.1. Формулировки основных результатов

Теорема 1.1 (оценки снизу). Для произвольной метрики 8 и любого числа d > 0 справедливы следующие неравенства:

1) оценка на полностью рандомизованном ансамбле

Ks(d) > maxPf (р,р,d); реР

2) оценка на ансамбле фиксированной композиции

7Zs(d) > max7>f (Р,Р,d)t

1.22)

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

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

Из следствия 1.12.1 (стр. 31) вытекает, что оценка (1.23) равномерно не хуже, чем (1.22). Однако мы предполагаем, что справедливо следующее утверждение.

Гипотеза 1. Нижние оценки случайного кодирования (1.22) и (1.23) совпадают для каждого значения d (хотя существуют вектора р, для которых выполнено строгое неравенство nPP(P»P,d)<7>f(p,p,d))

Из свойств функций V$p{p,p\d) и "Р|с(р, р', d) вытекает следующее утверждение.

Следствие 1.1.1. Если 0 < d < •7rjnax, то скорость %&(d) положительна.

Теорема 1.2 (оценки сверху — произвольная метрика). Для произвольной метрики 8 скорость 1Z$(d) равна нулю для всех значений d > J7™**. Если же 0 < d < , то справедливы следующие неравенства, в которых минимумы и максимумы берутся только по таким вероятностным векторам, для которых соответствующие функции определены, а вектор и Г Р имеет вид (1.16):

1) оценка Плоткина

2) оценка Хемминга

3) оценка Хемминга-П

S ) > n5(d)<l-d ffi

Tls{d) < maxmin {^(р); ^ср(р, и, й/2)} ;

TZs(d) < max min ТГ{р, р', d/2). реР р'еР

1.24)

1.25)

1.26)

Теорема 1.3 (оценки сверху — метрика с условием выпуклости среднего значения). Пусть метрика 8 удовлетворяет условию выпуклости среднего значения. Тогда для всех значений О < d < jcjnax справедливы следующие неравенства, в которых минимумы и максимумы берутся только по таким вероятностным векторам, для которых соответствующие функции определены, а вектор и 6 Р имеет вид (1.16):

1) оценка Плоткина-П lZs(d) < maxmin < Hiр); 1 реР р))"1};

2) оценка Элайса

7ls{d) < m^cmin{^(p);T?(5cp(p,u,r)},

1.27)

1.28) где значение г = r(p, d) определяется следующим образом: г = р) при всех d > J-$(p), а при 0 < d < j\j(p) число г является единственным решением уравнения <p(p,r) = d, где функция <р(р,г) имеет вид (1.21);

3) оценка Элайса-П

Zs{d) < max min Т'ГЧр, р', г), реР р'еР

1.29) где значение г = r(p, р', d) имеет следующий вид: г = ^s(p) при всех d > ^(р, р'), а при О < d < J~s(p. р') число г определяется как единственный корень уравнения р(р, р', г) = d, если оно разрешимо (в противном случае мы считаем, что величина r(p,p',d) и соответствующая функция V$c(p,p',r) не определены).

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

Отметим некоторые свойства данных оценок. Можно показать, что для всех трех случаев оценки типа II равномерно не хуже, чем аналогичные оценки типа I. Для границы Плоткина это очевидно, а для границ Хемминга и Элайса данное утверждение вытекает из метода их доказательства и следствия 1.12.3 (стр. 31).

Мы предполагаем, что справедливо следующее утверждение.

Гипотеза 2. Оценка Элайса (1.29) равномерно лучше всех остальных верхних оценок.

Графики верхних и нижних оценок скорости кодов для одной специальной метрики, называемой метрикой ДНК (2.24), изображены на рис. 2.7, стр. 58. Мы предполагаем, что поведение границ, наблюдаемое на данном рисунке, является типичным для любой метрики.

Список литературы диссертационного исследования кандидат физико-математических наук Виленкин, Павел Александрович, 2001 год

1. Гнеденко Б. В., Колмогоров А. Н. Предельные распределения для сумм независимых случайных величин. — M.-JL: Гос. издат. технико-теоретической литературы, 1949.

2. ЭрроуК.Дж., ГурвицЛ., УдзаваХ. Исследования по линейному и нелинейному программированию. — М.: ИЛ, 1962.

3. Singleton R. С., "Maximum Distance Q-Nary Codes," IEEE Trans. Inform. Th., 10 (1964), N. 2, 116-118.

4. KautsW.H., Singleton R. C., "Nonrandom binary superimposed codes," IEEE Trans. Inform. Th., 10 (1964), N. 4, 364-377.

5. Петров В. В., "О вероятностях больших уклонений сумм независимых случайных величин," Теория вероятн. и ее примеч., 10 (1965), N. 2, 310-322.

6. Карр Ч., Хоув Ч. Количественные методы принятия решений в управлении и экономике. — М.: Мир, 1966.

7. RenyiA. Probability theory. — Akademiai Kiado, Budapest, 1970.

8. Холл M. Комбинаторика. — M.: Мир, 1970.

9. БерлекэмпЭ. Алгебраическая теория кодирования. — М.: Мир, 1971.

10. Петров В. В. Суммы независимых случайных величин. — М.: Наука, 1972.

11. ГаллагерР. Г. Теория информации и надежная связь. — М.: Сов. радио, 1974.

12. Левенштейн В. И., "Элементы теории кодирования." — В кн.: Дискретная математика и математические вопросы кибернетики. — М. Наука, 1974.

13. Сидельников В. М., "Верхние оценки числа точек двоичного кода с заданным кодовым расстоянием," Пробл. передачи инф., 10 (1974), N. 2, 43-51.

14. Сидоренко В. Р., "Верхняя граница мощности д-ичных кодов," Пробл. передачи инф., 11 (1975), N. 3, 14-20.

15. D'yachkov A. G., "On a search model of false coins," Topics in Information Theory, Colloquia Mathematica Societatis Janos Bolyai, 1977, N. 16, 163-170. — Amsterdam: North Holland.

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

17. Дьячков А. Г., Рыков В. В, "Обзор теории дизъюнктивных кодов," Prob. of Control and Inform. Th., 12 (1983), N. 4, 229-244.

18. ФеллерВ. Введение в теорию вероятностей и ее приложения. — М.: Мир, 1984.

19. Breslauer К. J., Frank R., Blocker Н., MarkyL. A., "Predicting DNA duplex stability from the base sequence," Proc. Nail. Acad. Sci. USA (Biochemistry), 83 (June 1986), 3746-3750.

20. MitchellC. J., Piper F.C., "Key Storage in Secure Networks," Discr. Appl. Math., 21 (1988), 213-228.

21. D'yachkov A. G., RykovV. V., RashadA. M., "Superimposed distance codes," Prob. of Control and Inform. Th., 18 (1989), N. 4, 237-250.

22. Cover T.M., Thomas J. A., Elements of information theory. — N. Y.: John Wiley & Sons, 1991.

23. DuD.-Z., Hwang F.K. Combinatorial Group Testing and its Applications. — World Scientific, Singapore-New Jersey-London-Hong Kong, 1993.

24. Сагалович Ю. JI., "Разделяющие системы," Пробл. передачи инф., 30 (1994), N. 2, 14-35.

25. BonehD., Shaw J., "Collusion-secure fingerprinting for digital data," Lecture Notes in Computer Science, 963 (1995), 452-465.

26. Levenstein V. I. "Krawtchouk Polynomials and Universal Bounds for Codes and Designs in Hamming Spaces," IEEE Trans. Inform. Th., 41 (1995), N. 5, 1303-1321.

27. KornerJ., "On the Extremal Combinatorics of the Hamming Space," J. Comb. Th. ser.A, 711995), N. 1, 112-126.

28. DyerM., Fenner Т., Frieze A., ThomasonA., "On key storage in secure networks," J. Cryptology, 8 (1995), 189-200.

29. Дьячков А. Г., "Асимптотика энтропии Шеннона для сумм независимых случайных величин," Фундам. и прикл. матем., 2 (1996), N. 4, 1019-1028.

30. EngelK., "Interval packing and covering in the boolean lattice," Combin. Probab. Comput., 51996), 373-384.

31. Macula A. J., "A Simple Construction of c?-Disjunct Matrices with Certain Constant Weight," Discrete Math., 162 (1996), 311-312.

32. D'yachkov A. G., Vilenkin P. A., "Asymptotics of the Shannon and Renyi Entropies for Sums of Independent Random Variables." Материалы международной Сибирской конференции по исследованию операций, Новосибирск, 1998, стр. 143-144.

33. D'yachkov A. G., Vilenkin P. A., "Asymptotics of the Shannon and Renyi Entropies for Sums of Independent Random Variables." Тезисы симпозиума ISIT-98, Кембридж, США, 1998, стр. 376.

34. Виленкин П. А., Дьячков А. Г., "Асимптотика энтропий Шеннона и Реньи для сумм независимых случайных величин," Проблемы передачи информации, 34 (1998), N. 3, 17-31.

35. Виленкин П. A., "On Constructions of List-Decoding Superimposed Codes." Материалы конференции ACCT-6, Псков, 1998, стр. 228-231.

36. Levenstein V. I. "Universal Bounds for Codes and Designs." — В кн.: Handbook of coding theory. — Elsevier Science B.V., 1998.

37. StinsonD.R., Tran van Trung, WeiR., "Secure Frameproof Codes, Key Distribution Patterns, Group Testing Algorithms and Related Structures," 1998.

38. D'yachkov A. G., TorneyD.C., "Bounds on the Rate of Similarity Codes." Тезисы конф. "Computer Science & Information Technologies", Ереван, Армения, 7-22 авг. 1999, стр. 117119.

39. Vilenkin P. A., "One construction of superimposed codes." Материалы конференции "Paul Erdos and his Mathematics", Будапешт, Венгрия, 1999, стр. 259-266.

40. Математические методы для анализа последовательностей ДНК. Под. ред. М. С. Уотермана. — М.: Мир, 1999.

41. Kyureghyan G. М., Combinatorial Problems Originated in Group Testing, Coding Theory, and Complexity Theory. Ph.D. dissertation, Bielefeld Univ., Germany, 2000.

42. D'yachkov A., Macula A., RykovV., "New applications and results of superimposed code theory arising from the potentialities of molecular biology." — В кн: Numbers, Information and Complexity. — Kluwer Academic Publishers, 2000, 265-282.

43. A. G. D'yachkov, A.J. Macula, V.V. Rykov, "New Constructions of Superimposed Codes," IEEE Trans. Inform. Theory, 46 (2000), N. 1, pp. 284-290.

44. Chen P.- N., LeeT.-Y., HanY. S., "Distance-Spectrum Formulas on the Largest Minimum Distance of Block Codes." IEEE Trans. Inform. Th., 46 (2000), N. 3, 869-885.

45. D'yachkov A. G., TorneyD.C., "On similarity codes," IEEE Trans. Inform. Th., 46 (2000), N.4, 1558-1664.

46. D'yachkov A., Macula A., TorneyD., Vilenkin P., YekhaninS., "New Results in the Theory of Superimposed Codes." Материалы конференции ACCT-7, Банско, Болгария, 2000, стр. 126136.

47. Macula A., Vilenkin P., "On Superimposed Codes Based on Incidence Systems." Тезисы симпозиума ISIT-2000, Сорренто, Италия, 25-30 июня 2000, стр. 3.

48. D'yachkov A.G., Torney D. С., Vilenkin P. A., White P.S., "Reverse-Complement Similarity Codes for DNA Sequences." Тезисы симпозиума ISIT-2000, Сорренто, Италия, 25-30 июня 2000, стр. 330.

49. StinsonD.R., WeiR., ZhuL., "Some New Bounds for Cover-Free Families," J. Comb. Th. ser.A, 90 (2000), 224-234.ОглавлениеСписок обозначений Введение