Теория кодирования — раздел математической кибернетики, служащий теоретической основой при проектировании систем передачи, хранения и переработки информации. Основные задачи теории кодирования связаны с построением и исследованием помехоустойчивых кодов, состоящих из Пмерных векторов. Обычно помехоустойчивость кода характеризуется значением некоторого функционала, который нужно оптимизировать на множестве кодов с заданным числом векторов. Важнейшими примерами таких функционалов, которые исследуются в теории кодирования и, в частности, в настоящей работе, являются вероятность ошибки декодирования и вероятность необнаруженной ошибки в заданном канале с шумами, максимальное число исправляемых ошибок заданного типа и корреляции кода (максимум модуля нетривиальных значений автокорреляционных и взаимно-корреляционных функций векторов). Оптимальные помехоустойчивые коды характерны тем, что их элементы в определенном смысле далеки друг от друга. При некоторых определениях помехоустойчивости этот смысл можно непосредственно перевести на метрический язык. Так, задачи построения максимальных кодов с исправлением заданного числа аддитивных ошибок, арифметических ошибок, ошибок типа выпадения и вставки, фазовых ошибок, амплитудных ошибок и т. п. равносильны задачам плотнейшей упаковки дискретного пространства с соответствующим образом подобранной метрикой, а задачи построения кодов с минимальной корреляцией близки к задачам плотнейшей упаковки некоторых проективных пространств. Однако, и в других случаях задачи упаковки метрических пространств могут играть существенную роль при исследовании помехоустойчивости. Рассмотрим, в частности, такую характеристику кода как вероятность ошибки декодирования. Первым и самым значительным результатом в теории кодирования и теории информации является теорема Шеннона [87^ о кодировании для канала с шумами. Согласно этой теореме при любой скорости передачи, меньшей пропускной способности канала, минимальная вероятность ошибки декодирования стремится к нулю с ростом длины кодов. После того, как было установлено, что это стремление экспоненциальное, возникла важная с практической точки зрения задача о нахождении логарифмической асимптотики минимальной вероятности ошибки декодирования или, в терминологии К. Шеннона [88J, задача вычисления функции надежности канала. В настоящее время эта задача не решена полностью даже для простейших каналов: дискретного двоичного симметричного канала и непрерывного канала с аддитивным гауссовским шумом при ограничении мощности сигналов. К. Шеннон, Р. Галлагер и Э. Бердекэмп [89] установили связь задачи вычисления функции надежности для указанных каналов с задачей плотней-шей упаковки хэммингова пространства и евклидовой сферы соответственно. Эта связь такова, что всякое усиление границы, показывающей, что упаковка пространства не может быть очень плотной, приводит к усилению границы для функции надежности соответствующего канала. При этом, если будет доказано некоторое весьма правдоподобное предположение о плотнейшей упаковке хэммингова пространства и евклидовой сферы, то будет получено окончательное решение задачи о вычислении функции надежности для соответствующего канала. Как показал автор [3l], аналогичная связь с плотнейшей упаковкой хэммингова пространства возникает и в задаче минимизации вероятности необнаруженной ошибки в двоичном симметричном канале. Вероятность необнаруженной ошибки имеет ватаое значение (см. [51J) при проектировании реальных систем передачи с переспросом (обратной связью). Из сказанного выше следует, что трудности решения многих основных задач теории кодирования сосредоточены в задачах плотнейшей упаковки метрических пространств. Установлению связей между задачами теории кодирования и упаковками метрических пространств и посвящена глава I (§ § 1−4), носящая, в основном, вспомогательный характер. Из результатов автора, приведенных в этой главе, можно отметить получение границ для минимальной вероятности необнаруженной ошибки в двоичном симметричном канале (§ 2) и получение асимптотики максимальной мощности двоичных кодов длины п, исправлявших одиночную ошибку типа выпадения и вставки (§ 3).
Известные результаты для упаковок метрических пространств приведены в § I. Для максимальной мощности упаковки компактного метрического пространства Tfl шарами радиуса 2 имеются две общие (для всех метрических пространств) границы. Верхняя граница (граница неизбыточной упаковки) отражает тот факт, что плотность упаковки не превышает единицы, а нижняя — что если в максимальной по мощности упаковке пространства 7П шарами радиуса Z удвоить радиус шаров, то получится покрытие пространства ffl шарами радиуса 2l. Эти верхняя и нижняя границы сильно отличаются друг от друга. При этом, с одной стороны, можно привести примеры метрических простршств (см. пространство в § I), для которых граница неизбыточной упаковки достигается для бесконечного множества радиусов упаковки. С другой стороны, в работах Г. Блихфельдта [57], Р. Рэнкина [82], М. Плоткина [78], С. Джонсона [б8], П. Элайеса (см. [б9]), Л. А. Бассалыго [i], В. М. Сидельникова [44−47], автора [27, 28, 30], а также в работе Р. Мак-^Элиса, Е. Родемича, Г. Рамсея и Л. Велча [77], основанной на «границе линейного программирования» Дельсарта [15], граница неизбыточной упаковки для основных метрических пространств, рассматриваемых в теории кодирования, была значительно усилена вне области малых радиусов упаковки.
Отправным пунктом для развитого в диссертационной работе общего метода получения границ послужило то наблюдение, что все известные результаты, показывающие, что упаковки метрических пространств не могут быть очень плотными, могут быть получены с помощью неравенств определенного вида (названных в работе неравенствами «о среднем») для некоторых инвариантных неотрицательно определенных функций. При этом прослеживается, что прогресс в задаче получения границ фактически был связан с более подходящим выбором инвариантных неотрицательно определённых функций. В связи с этим в работе исследованы условия выполнения неравенства «о среднем» для неотрицательно определенных функций и, в частности, установлено, что в случае однородного пространства ЦП неравенство «о среднем» справедливо для любой инвариантной неотрицательно определенной функции. Как оказалось, основные метрические пространства теории кодирования обладают достаточно «богатыми» группами движений и принадлежат классу однородных пространств, для которых зональные сферические функции и, следовательно, инвариантные неотрицательно определенные функции являются многочленами от расстояния (такие пространства названы в работе полиномиальными). Это позволило перейти от получения границ для отдельных пространств к получению общей границы для основных метрических пространств теории кодирования. В работе с помощью неравенства «о среднем» для специально подобранных инвариантных неотрицательно определенных функций получена общая для всех полиномиальных пространств верхняя граница максимальной мощности упаковки. Общая граница была вычислена для основных метрических пространств теории кодирования. Для каждого из пространств полученная граница лучше известных границ, когда радиус упаковки не слишком мал и не очень велик (при больших радиусах упаковки имеет место совпадение с известными границами). Полученные границы позволили доказать максимальность многих упаковок (на которых они достигаются) и усилить некоторые известные асимптотические результаты.
Основные результаты диссертации приведены в главах 2 и 3. В главе 2 (§§ 5−8) излагается метод получения верхних границ максимальной мощности упаковок, основанный на использовании неравенств для неотрицательно определенных функций — с помощью этого метода устанавливается общая верхняя граница максимальной мощности упаковок полиномиальных пространств — исследуются условия достижения этой границы, В главе 3 (§§ 9−12) общая верхняя граница вычисляется для основных метрических пространств, рассматриваемых в теории кодировения — указываются примеры достижения этой границы — устанавливаются и сопоставляются с известными асимптотические оценки — приводятся приложения полученных результатов к задачам теории кодирования, геометрии и теории чисел.
Метод получения границ можно условно разбить на три этапа: формулировка и доказательство неравенства «о среднем» для неотрицательно определенных функций, описание множества инвариантных неотрицательно определенных функций, выбор инвариантной неотрицательно определенной функции для получения верхней границы максимальной мощности упаковок. Автором была высказана.
75] и развита^ jj6j идея о том, что основные неравенства в. задачах упаковки могут быть получены в рамках единой конструкции, основанной на неравенствах для средних значений неотрица-х/ Работа [1б] написана в соавторстве с Г. А. Кабатянским. тельно определенных функций. Будем говорить, что для функции справедливо неравенство «о среднем», если среднее значениеL 2 -f (oc, u,) функции Т (ос, и) по любому.
1W| x^GW конечно^ множеству Д/ с Jft не меньше, чем среднее значение по всему пространству Ж. Верхняя граница максимальной мощности упаковки шарами заданного радиуса может быть получена с помощью любой неотрицательно определенной функции Т С^уО, для которой справедливо неравенство «о среднем» и выполнено условие неотрицательности в некоторой области, зависящей от радиуса упаковки. В § 5 установлены общие неравенства для неотрицательно определенных функций, с помощью которых получено простое достаточное условие выполнения неравенства «о среднем». В частности, из этих результатов следует, что если группа движений £г метрического пространства ТЪ действует транзитивно на w (т.е. пространство m является однородным), то неравенство «о среднем» справедливо для любой неотрицательно определенной функции, инвариантной относительно G". Известные границы в задачах упаковки фактически были получены с помощью неравенств «о среднем» для некоторых неотрицательно определенных функций на некоторых однородных пространствах. Так, границы Елихфельдта, Рэнкина, Плоткина, Джонсона, Элайесар-Бассалыго могут быть получены с помощью неравенства «о среднем» для скалярного произведения fe^) в некоторых подпространствах КЛ. Существенное улучшение границ Елихфельдта, Рэнкина и Элайеса-Бассалыго, полученное В. М. Сидельниковым [45−47], основано на неравенстве «о среднем» для функций (ос,^)^, к =1,2,.. Известная граница Велча [9l] по существу является неравенством «о среднем» для неотрицательно определенной функции jC0^)!^, lc=1,2,., на единичной комплексной сфере. Отметим также, что «граница линейного программирования» Дельоарта [15J в схемах отношений основана на неравенстве «о среднем» для неотрицательно определенных функций, являющихся функциями отношений { для таких функций выполняется упомянутое выше достаточное условие). Общий подход, основанный на неравенстве «о среднем», открыл новые возможности для получения границ максимальной мощности упаковок различных пространств и позволил значительно упростить доказательство некоторых известных границ.
При исследовании схем отношений теории кодирования Ф. Дель-сарт [l5j фактически дал описание множества инвариантных неотрицательно определенных функций в конечных пространствах Хэмминга и №онсона. Указанное множество функций для этих пространств описывается с помощью многочленов, которые разлагаются с неотрицательными коэффициентами по системе ортогональных многочленов Кравчука и Хана соответственно. Для того, чтобы получить подобное описание и для некоторого класса непрерывных пространств, включающего евклидову сферу, был предложен [16] новый для задач упаковки подход, основанный на использовании групп движений метрических пространств. В силу известных результатов теории представлений групп, множество инвариантных функций в однородных пространствах описывается с помощью ортогональных систем зональных сферических функций. В § 6 был исследован класс метрических пространств, названных полиномиальными, в которых зональные сферические функции являются многочленами. Для евклидовой сферы и проективной (действительной и комплексной) евклидовой сферы эти функции являются многочленами Якоби с определенными параметрами. Множество инвариантных неотрицательно определенных функций в полиномиальных пространствах описывается с помощью систем ортогональных многочленов подобно тому, как это указано выше для пространств Хэмминга и Ддонсона. Отметим также, что использованный подход позволил прояснить теоретико-групповой смысл многочленов Кравчука и Хана как зональных сферических функций, связанных с группой движений соответствующих пространств.
В классе полиномиальных пространств выбор инвариантной неотрицательно определенной функции для получения с помощью неравенств «о среднем» наилучшей верхней границы максимальной мощности упаковки сводится к одной экстремальной задаче для систем ортогональных многочленов. Автор предложил [32] некоторое, общее для всех полиномиальных пространств, решение этой задачи, которое приведено в § 7. В результате был получен один из основных результатов — верхняя граница максимальной мощности упаковки полиномиального пространства, выраженная через некоторые характеристики соответствующей ему системы ортогональных многочленов. Способ доказательства этой границы позволил установить (§ 8) алгебраические и комбинаторные свойства упаковок, мощность которых достигает этой границы. Такие упаковки должны образовывать (симметричные) схемы отношений в терминологии Ф. Дельсарта [15] и являться Т-конфигурациями в некотором обобщенном смысле.
В главе 3 (§§ 9−12) полученная общая граница вычислена для основных метрических пространств, рассматриваемых в теории кодирования, в частности, для евклидовой сферы, проективных пространств, пространств Хэмминга и Джонсона. С этими пространствами связаны системы классических ортогональных многочленов Гегенбауэ-ра, Якоби, Кравчука и Хана. При вычислении этой границы использовались особые свойства и параметры этих систем ортогональных многочленов. Для указанных пространств новая граница оказалась сильнее известных границ при всех радиусах упаковки, за исключением некоторых областей больших и малых радиусов (в области больших радиусов она совпала с известными границами). Доказана максимальность большого числа известных упаковок, на которых достигается новая граница. Тем самым установлено, что эти упаковки образуют схемы отношений и являются Тконфигурациями. Приведены также примеры бесконечных последовательностей упаковок, для которых новая граница достигается в точном или асимптотическом смыслах. С помощью некоторых методов и результатов теории ортогональных многочленов и специальных функций получены также асимптотические результаты, вытекающие из новой границы. Приведем их для случая евклидовой сферы. Пусть М) — косинус максимального угла ^ такого, что на сфере пространства существует М точек, находящихся на угловых расстояниях не менее друг от друга. В работе установлено, что при фиксированном к (к = 1,2, .. .) и П-* где — наибольший нуль многочлена Эрмита Н ^ (?) (fi.]=0,.
ЧТО, если ntlogn-fybfrM) Ч п я где Сг (у) = y+y^fojfl-vj}) — J {oj-jf. Все эти асимптотические неравенства лучше тех, которые были известны. Подобные соотношения получены и для других пространств. В случае проективных пространств они улучшают известные границы Сидельникова и Велча для максимального модуля скалярных произведений различных векторов кода.
Полученные в работе результаты позволили продвинуться в задачах теории кодирования, связанных с исследованием таких характеристик кодов как корректирующая способность, корреляция, вероятность ошибки декодирования и вероятность необнаруженной ошибки в некоторых каналах. Практическая ценность полученных результатов состоит в возможности использовать установленные границы для исследования потенциальной помехоустойчивости кодов. В частности, из новой границы следует максимальность многих кодов с заданным минимальным расстоянием или с заданной корреляцией. Коды с заданной корреляцией используются в радиолокационных системах и системах связи с множественным доступом. Хотя поставленные цели были вызваны, в основном, потребностями теории кодирования, установленные в работе границы оказались такими, что позволили также продвинуться в некоторых классических задачах геометрии и теории чисел. В частности, в § 9 получена следующая граница для максимальной плотности бд, упаковки пространства ft^ равными шарами п (7 (Ю) где j (V) — наименьший положительный нуль функции Бесселя первого рода Jy (2-), а Г (?¦) — гамма-функция. Эта граница при достаточно больших /1 (начиная с Ц =97 по данным А. Боса ?58]) лучше известной границы Роджерса [83]. Получена также (наилучшая из известных в настоящее время) асимптотическая граница л-п (0,Г99+(г (?)) Оп 4 2 при.
В том же § 9 при /1=8 и П-24 установлено максимальное число.
М, а .< одинаковых шаров в, которые, не перекрываясь, могут касаться одного такого шара (до последнего времени точное значение М ^ было известно лишь при п? 3). В § 12 о помощью границ для упаковок проективных пространств улучшены известные в теории чисел нижние границы для модулей полных и частичных сумм характеров от многочленов над конечными полями.
Для полноты изложения в работу включены два приложения, А и Б, в которых с помощью известных методов доказаны некоторые утверждения, касающиеся систем ортогональных многочленов и упаковок в евклидовом пространстве соответственно.
В заключении перечислены основные результаты диссертации. В работе использована двойная нумерация утверждений, замечаний, формул (первый элемент указывает номер параграфа или буквенное обозначение приложения) и использованы следующие обозначения: jf^ - ftмерное действительное евклидово пространство, (Q^ - tlмерное комплексное евклидово пространство, |" 2| - модуль числа 2 (если Z- - число) или число элементов множества 2 (если Z- - множество),.
1 — число, комплексно сопряженное с Ъ, Re 2 — действительная часть числа 2 ,.
2 Па?- - мнимая часть числа 2-, п ос^) = Д/Хс ij t ~ скалярное произведение векторов = .>0rOeCft, to^x — двоичный логарифм числа X ,.
In X — натуральный логарифм числа X, х] - целая часть числа X, .
Н (ОС) — энтропия Шеннона (Н (*)= -хЦхЧ^ЦМ, 0.
Р (2г) -гамма-функция,.
P (cH-i).
Заключение
.
Главное значение работы автор видит в том, что в ней для задач упаковки метрических пространств развит метод получения границ, основанный на неравенствах для неотрицательно определенных функций, С помощью этого метода для класса полиномиальных метрических пространств (содержащего основные пространства, рассматриваемые в теории кодирования) получена общая верхняя граница для максимальной мощности упаковки шарами заданного радиуса. Основной вклад автора в развитие метода и получение границы составляют: формулировка неравенства «о среднем» и нахождение условий его выполнения для неотрицательно определенных функций, использование в задачах упаковки гармонического анализа на группах движений метрических пространств для описания множества инвариантных неотрицательно определенных функций, указание и обоснование некоторой единой конструкции для выбора инвариантных неотрицательно определенных функций в полиномиальных пространствах. Общая граница для максимальной мощности упаковок полиномиальных метрических пространств выражается через некоторые характеристики соответствующих систем ортогональных многочленов и, в конечном счете, определяется инвариантной мерой метрических шаров. Способ доказательства этой границы позволил установить некоторые алгебраические и комбинаторные свойства упаковок, на которых она достигается (в частности, такие упаковки должны образовывать симметричные схемы отношений и быть Тконфигурациями в некотором обобщенном смысле).
Общая верхняя граница вычислена для основных метрических пространств, рассматриваемых в теории кодирования. Для каждого из пространств полученная новая граница оказалась сильнее известных границ при всех радиусах упаковки, за исключением некоторых областей больших и малых радиусов (в области больших радиусов она совпала с известными границами). Указано свыше 25 известных упаковок различных пространств, для которых новые границы дости~ гаются. Тем самым доказана максимальность этих упаковок и устаг-новлено, что они образуют симметричные схемы отношений и Тконфигурации. Приведены также примеры бесконечных последовательностей упаковок, для которых новые границы достигаются в точном или асимптотическом смыслах. Основными асимптотическими результатами являются асимптотические неравенства для евклидовой сферы (9.32), (9.35) и (9.36) (или равносильное ему неравенство (9.40)). Все эти неравенства улучшают известные результаты. Аналогичные асимптотические соотношения получены и для других пространств. Среди этих соотношений отметим верхние границы (11.26), (11.56) и (II.81) для корректирующей способности кодов, мощность которых растет как некоторая степень длины. В том же асимптотическом процессе для максимального модуля скалярных произведений различных векторов кода получены нижние границы (11.39), (10.23) и (10.37), которые сильнее известных границ Сидельникова и Велча.
Полученные результаты применены к задачам теории кодирования, а также к некоторым задачам геометрии и теории чисел, связанным с упаковками пространств. Улучшена граница для функции надежности канала с аддитивным гауссовским шумом при ограничении мощности сигналов (см. (2.16)). Для вероятности необнаруженной ошибки в двоичном симметричном канале найдены границы (в том числе «граница минимального расстояния» (2.21) и (2.31)), которые сильнее известных границ. Улучшены границы для корректирующей способности и вероятности ошибки декодирования кодов, мощность которых растет как степень длины. Улучшены границы максимальной мощности кодов с ограниченной корреляцией и кодов с ограниченным модулем скалярных произведений. Доказана максимальность ряда известных кодов и нескольких бесконечных семейств известных кодов (§§ 9-II). Построены класс максимальных двоичных кодов, исправляющих аддитивные ошибки (теорема II.2), классы максимальных кодов на единичных сферах пространств f^ и (С^, для которых модуль скалярных произведений различных векторов не превышает (§ 10), а также класс асимптотически максимальных двоичных кодов, исправляющих одиночную ошибку типа выпадения или вставки (теорема 3.1). С помощью новой границы для упаковок на евклидовой сфере получена верхняя граница (9.45) для максимальной плотности упаковки пространства jf^^ равными шарами, которая при (lz-97 лучше известной границы Роджерса, а также асимптотическая граница (9.44), которая лучше известных границ. Улучшена верхняя граница и найдены точные значения при lft =8 и Ц=24 для максимального числа М ^ одинаковых шаров в jj^, которые, не перекрываясь, могут касаться одного такого шара. С помощью границ для упаковок проективных пространств улучшены (§ 12) известные в теории чисел нижние границы для модулей полных и частичных суш характеров от многочленов над конечными полями.