Метод неотрицательно определенных функций в метрических задачах теории кодирования тема диссертации и автореферата по ВАК РФ 01.01.09, доктор физико-математических наук Левенштейн, Владимир Иосифович

• Левенштейн, Владимир Иосифович
• доктор физико-математических наук
• 1983

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

Введение

ГЛАВА I. УПАКОВКИ МЕТРИЧЕСКИХ ПРОСТРАНСТВ И ЗАДАЧИ ТЕОРИИ КОДИРОВАНИЯ

§ I. Задача, плотнейшей упаковки метрического пространства

§ 2. Границы минимального расстояния для вероятности ошибки декодирования и вероятности необнаруженной ошибки •

§ 3. Метрическое описание кодов, исправляющих ошибки различных типов . . . . • . •

§ 4, Синхронизационные свойства кодов и проективные пространства. . • •

ГЛАВА 2. МЕТОД Ш ОТРИЦАТЕЛЬНО ОПРЕДЕЛЕННЫХ ФУНКЦИЙ В ЗАДАЧАХ УПАКОВКИ

§5. Неравенства для неотрицательно определенных функций

§ 6. Описание множества инвариантных неотрицательно определенных функций

§ 7. Границы максимальной мощности упаковок полиномиальных пространств . • •••••••••••

§ 8. Алгебраические и комбинаторные свойства максимальных D -кодов. III

ГЛАВА 3. ГРАНИЦЫ МАКСИМАЛЬНОЙ МОДНОСТИ У ПАКОВ (К ОСНОВНЫХ МЕТРИЧЕСКИХ ПРОСТРАНСТВ ТЕОРИИ КОДИРОВАНИЯ Ж НЕКОТОРЫЕ ПРИЛОЖЕНИЯ

§ 9. Границы для упаковок на евклидовой сфере. Геометрические приложения •••••••.•••.

§ 10.Границы для упаковок проективных пространств

§ II .Границы для упаковок конечных пространств

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

Введение диссертации (часть автореферата) на тему «Метод неотрицательно определенных функций в метрических задачах теории кодирования»

Теория кодирования - раздел математической кибернетики, служащий теоретической основой при проектировании систем передачи, хранения и переработки информации. Основные задачи теории кодирования связаны с построением и исследованием помехоустойчивых кодов, состоящих из П -мерных векторов. Обычно помехоустойчивость кода характеризуется значением некоторого функционала, который нужно оптимизировать на множестве кодов с заданным числом векторов. Важнейшими примерами таких функционалов, которые исследуются в теории кодирования и, в частности, в настоящей работе, являются вероятность ошибки декодирования и вероятность необнаруженной ошибки в заданном канале с шумами, максимальное число исправляемых ошибок заданного типа и корреляции кода (максимум модуля нетривиальных значений автокорреляционных и взаимно-корреляционных функций векторов). Оптимальные помехоустойчивые коды характерны тем, что их элементы в определенном смысле далеки друг от друга. При некоторых определениях помехоустойчивости этот смысл можно непосредственно перевести на метрический язык. Так, задачи построения максимальных кодов с исправлением заданного числа аддитивных ошибок, арифметических ошибок, ошибок типа выпадения и вставки, фазовых ошибок, амплитудных ошибок и т.п. равносильны задачам плотнейшей упаковки дискретного пространства с соответствующим образом подобранной метрикой, а задачи построения кодов с минимальной корреляцией близки к задачам плотнейшей упаковки некоторых проективных пространств. Однако, и в других случаях задачи упаковки метрических пространств могут играть существенную роль при исследовании помехоустойчивости. Рассмотрим, в частности, такую характеристику кода как вероятность ошибки декодирования. Первым и самым значительным результатом в теории кодирования и теории информации является теорема Шеннона [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<Xii\

Р(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) известные в теории чисел нижние границы для модулей полных и частичных суш характеров от многочленов над конечными полями.

Список литературы диссертационного исследования доктор физико-математических наук Левенштейн, Владимир Иосифович, 1983 год

1. Бейтмен IV, Эрдейи А; Высшие трансцендентные функции, т.2. М;: Наука, 1974.

2. Березин Ф.А., Гельфанд И.М. Несколько замечаний к теории сферических функций на симметрических ришновых многообразиях. Труды Моск.штем. общ., т.5, 1956, с.311-351.

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

4. Варшамов P.P. Сменка числа сигналов в кодах с коррекцией ошибок. ДАН СССР, 1957, 117, гё 5, с.739-741.

5. Варшамов P.P. О некоторых особенностях линейных кодов, корректирующих несимметрические ошибки. ДАН СССР, 1964, 157, № 3, с.546-548.

6. Варшамов P.P., Тененгольц Г.М. Код, исправляющий одиночные несимметрические ошибки. Автоматика и телемеханика, 1965, 26, JS 2, с.288-292.

7. Ватсон Г.Н. Теория бесселевых функций, ч.1 М.: ИЛ, I949-.

8. Виленкин Н.;Я. Специальные функции и теория представлений групп. М.: Наука, 1965.

9. Габидулин Э .М., Сидоренко В.Р. Об одной общей границе для объема кода. Пробл. перед .информ., 1976, 12, № 4, с.31-35.

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

11. Гинзбург Б.Д. Об одной теоретико-числовой функции, имеющей приложение в теории кодирования. Проблемы кибернетики, вып. 19, М.: Наука, 1967, с. 249-252.

12. Гнеденко Б.В. Курс теории вероятностей. М.: Физматгиз, 1961.

13. Дадаев Ю.Г. Теория арифметических кодов,- М.: Радио и связь, 1981.

14. Дельсарт Ф. Алгебраический подход к схемам отношений теории кодирования. М.: Мир, 1973.

15. Кабатянский Г.А., Левенштейн В.И. О границах для упаковок на сфере и в пространстве. Пробл.перед.информ., 1978,14, В I, с.3-25.

16. Карацуба А.А. Об оценках полных тригонометрических сумм.- Матем. заметки, 1967, I, Л 2, с.199-208.

17. Карацуба А.А. Об оценках снизу сумм характеров от многочленов. Матем. заметки, 1973, 14, Л I, с.67-72.

18. Книжнерман Л.А., Соколинский"В.3.Некоторые оценки рациональных тригонометрических сумм и сумм символов Лежандра. Успехи матем.наук, 1979, 34, № 3, с.199-200.

19. Колмогоров А.Н., Тихомиров В.М. £ энтропия и S -емкость множеств в функциональных пространствах. - Успехи матем. наук, 1959, 14, В 2 (86), с.3-86.

20. Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа. М;: Наука, 1972.

21. Коржик В.И. Границы по вероятности необнаружения ошибок и оптимальные групповые коды в канале с обратной связью. -Радиотехника, 1965, 20, $ I, с.27-33.

22. Коржик В.И., Осмоловский С.А., Финк Л.М. Универсальное стохастическое кодирование в системах с решающей обратной связью. Пробл.перед. информ., 1974, 10, № 4, с.26-42.

23. Коробов Н.М., Митькин Д.А. 0 нижних оценках полных тригонометрических сумм. Вестн. МГУ, сер. Математика, Механика, 1977, № 5, с.54-57.

24. Левенштейн В.И. Применение матриц Адамара к одной задаче теории кодирования. Проблемы кибернетики, вып;5, М.: Наука, 196I, с.123-136.

25. Левенштейн В.И. Двоичные коды с исцравлением выпадений, вставок и замещений символов. ДАН СССР, 1965, 163, 4, с1.707-710.

26. Левенштейн В.И-. 0 верхних оценках для кодов с фиксированным весом векторов. Пробл.перед. информ., 1971, 7, 4, с.3-12.28.- Левенштейн В.И. 0 минимальной избыточности двоичных кодов, исправляющих ошибки. Пробл. перед, информ., 1974, 10, № 2, с. 26-42.

27. Левенштейн В.И. Элементы теории кодирования. В кн. Дисьфет-ная математика и математические вопросы кибернетики, М.: Наука, 1974, с.207-305.

28. Левенштейн В.И. О максимальной плотности заполнения ft-мерного евклидова пространства равными шарами. Матем.заметки, 1975, 18, & 2, с.301-311.

29. Левенштейн В.И. О границах вероятности необнаружения шибки. Пробл. перед, информ., 1977, 13, № I, с.3-18.

30. Левенштейн В.И. О выборе многочленов для получения границ в задачах упаковки. УП Всесоюзная конференция по теориикодирования и передачи информации (тезисы докладов), ч.П, Москва-Вильнюс, 1978, с.103-108.

31. Левенштейн В.И. 0 границах для упаковок в метрических пространствах. Пятый международный симпозиум по теории информации (тезисы докладов), ч.П, Москва-Тбилиси, 1979, с. 4749;

32. Левенштейн В.И. Границы для упаковок метрических пространств и некоторые приложения. Проблемы кибернетики, вып.40,

33. М.: Наука, 1983, с.43-110.

34. Леонтьев В.К. Кодирование с обнаружением ошибок. -Пробл.перед, информ., 1972, 8, 2, с.6-14.

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

36. Монтгомери Г. Мультипликативная теория чисел. М.: Мир, 1974.

37. Никифоров А.Ф., Уваров В.Б. Специальные функции математической физики. М.: Наука, 1978.

38. Оре 0. Теория графов. М.: Наука, 1968.

39. Роджерс К.-Укладки и покрытия. М.: Мир, 1968.

40. Сеге Г. Ортогональные многочлены. М.: Физматгиз, 1962.

41. Сидельников В.М. 0 взаимной корреляции последовательностей. Проблемы кибернетики, вып.24, М.: Наука, 1971, с.15-42.

42. Сидельников В.М. 0 плотнейшей укладке шаров на поверхности1.-мерной евклидовой сферы и числе векторов двоичного кодас заданным кодовым расстоянием. ДАН СССР, 1973, 213, 5, с.1029-1032.

43. Сидельников В.М. Новые оценки плотнейшей упаковки шаров в

44. Л-мерном евклидовом цространстве. Матем.сборник, 1974, 95, с.148-158.

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

46. Сидельников В;М. Об экстремальных многочленах, используемых цри оценках мощности кода. Пробл.перед. информ., 1980, 16, № 3, с.17-30.

47. Степанов С;А. Об оценках снизу неполных суш характеров от многочленов. Труды Матем. ин-та АН СССР, 1977, 143, с. 175-177.

48. Феллер В. Введение в теорию вероятностей и ее приложения.- М.: Мир, 1964.

49. Финк Л.М. Теория передачи дискретных сообщений. М.: Советское радио, 1970.

50. Фихтенгольц Г.М. Курс дифференциального и интегрального исчисления, т.З. М.: ГИФМЛ, I960.

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

52. Шевердяев А.Ю. О методах декодирования в каналах с пумами.- Диссертация на соискание ученой степени канд. физико-матем. наук, М., 1971, 94с.

53. Яглом И;М. Некоторые результаты, касающиеся расположенийв yi -мерном пространстве. Приложение к кн. Тот Л.Ф. Расположения на плоскости, на .сфере и в пространстве. М.: ГИФМЛ, 1958.

54. Alltop W.O. Complex sequences with low periodic correlations,- IEEE Trans. Inform. Theory, 1980, 26, №3, p, 350-354.

55. Blichfeldt H.F. The minimum value of quadratic form, and the closest packing spheres.- Math. Ann., 1929, 101, p.605-608.

56. Bos A. Sphere packings in high-dimensional space.- Technological University Eindhoven, The Netherlands, Department of Math., Report 80-WSK-03, July 1980, p.1-23.

57. Bose R.C., Ray-Cnaudhuri D.K. On a class of error-correcting binary group codes.- Inform, and Control, I960, 3, №l, p.68-79.

58. Cartan Й. Sur la determination d'un syst&ne orthogonal com-plet dans un espace d£ Riemann sym^trique clos.- Rend. Circ. Mat. Palermo, 1929, 53, p.217-252.

59. Coxeter H.S.M. An upper bound for the number of equal non-overlapping spheres that can touch another of the same size. Proc. Symp. in Pure Math., v. VII, Providence, 1963, p. 53-72.

60. Delsarte P., Goethals J.M., Seidel J.J. Bounds for systemsof lines and Jacobi polynomials.- Philips Res. Rep., 1975,30» p.9I*-I05*.

61. Delsarte P., Goethals J.M., Seidel J.J. Spherical codes and designs.- Geometriae Dedicata, 1977, 6, p.363-388.

62. Elias P., Coding for two noisy channels.- Information theory, Academic Press, New York, 1956, p.61-74*

63. Gilbert E.N. A comparison of signalling alphabets.- Bell. Syst. Techn. J., 1952, 31, №3, p.504-522.

64. Hamming R.W. Error-detecting and error-correcting codes.-Bell. Syst. Techn. J., 1950, 29, №2, p.147-160.

65. Iizuka Т., Kasahara М., Namekawa Т. Block codes capable of correcting both additive and timing errors,- IEEE Trans. Inform. Theory, 1980, 26, №4, p.393-400.

66. Johnson S.M. A new upper bound for error-correcting codes.-IRE Trans. Inform. Theory, 1962, 8, №3, p.203-207.

67. Johnson S.M. Improved asymptotic bounds for error-correcting codes.- IEEE Trans. Inform. Theory, 1963, 9, №3, p.198-205.

68. Kerdock A.M. A class of low-rate nonlinear binary codes.-Inform, and Control, 1972, 20, №2, p.I82-I87.

69. Lee С.У. Some properties of nonbinary error-correcting codes.- IEEE Trans. Inform. Theory, 1958, 4» p.77-82.

70. Leech J. Notes on sphere packing.- Canad. J. Math., 1967» 19, №2, p.251-267.

71. Leech J., Sloane N.J.A. Sphere packings and error-correcting codes.- Canad. J. Math., 1971» 23, p.718-74-5.

72. Lemmens P.W.H., Seidel J.J. Equiangular lines.- J.of Algebra, 1973, 24, p.494-512.

73. Levenshtein V.I. Methods for obtaining bounds in metric problems of coding theory.- Proc. of the 1975 IEEE-USSR Joint Workshop on Information Theory. N.Y., 1976, p.126-143.76. van Lint J.H. Coding theory.- N.Y., Springer, 1971.

74. McEliece P.J., Rodemich E.R., Rumsey H., Jr., Welch L.R. New upper bounds on the rate of a code via the Delsarte -MacWilliams inequalities.- IEEE Trans, Inform. Theory, 1977, 23, №2, p.157-166.

75. Plotkin M. Binary codes with specified minimum distance IRE Trans, Inform, Theory, I960, 6, №4» p.445-450.

76. Odlyzko A.M., Sloane N.J.A. New bounds of the number of unit spheres that can touch a unit sphere in lb dimensions.

77. J. of Comb. Theory. Ser.A, 1979» 26, №2, p.210-214.

78. Okuda Т., Tanaka E., Kasai T. A method for correction of carbled words based on the Levenshtein metric.- IEEE Trans, on Computers, 1976, 25, №2, p.I72-I78.

79. Olsen J.D., Scholtz R.A., Welch L.R. Bent-function sequences.- IEEE Trans. Inform* Theory, 1982, 28, №6,p.858-864.

80. Rankin R.A. The closest packing of spherical caps in XI dimensions.- Proc. Glasgow Math. Ass., 1955» 2, p.I39-I44.

81. Rogers С.A. The packing of equal spheres.- Proc. bond. Math. Soc., 1958, 8, p.609-620.

82. Sankoff D. Matching sequences under deletion/insertion constraints.- Proc. Nat. Acad. Sci. USA, 1972, 69, №1, p.4-6.

83. Sarwate D.V. Bounds on crosscorrelation and autocorrelation of sequences.- IEEE Trans. Inform. Theory, 1979, 25, N«6, p.720-724.

84. Schmidt W.M. Equations over finite fields. An elementary approach.- Lecture notes in Mathematics, 536, Springer-Ver-lag, Berlin, Heidelberg, N.Y., 1976.

85. Shannon C.E. A mathematical theory of communication.- Bell Syst. Techn. J., 1948, 27, NB3,p.379-423, №4,p.623-656.

86. Shannon C.E. Probability of error for optimal codes in Gaussian channel.- Bell Syst. Techn. J., 1959, 38, №3,p.611-656

87. Snannon C.E., Gallager R.G., Berlekamp E.R. Lower bounds of error probability for on discrete memoryless channels.-Inform, and Contpol, 1967, Io, p. 65-103, 522-552.

88. Tanaka E., Kasai T. Synchronization and substitution error-correcting code design based on the Levenshtein metric.-IEEE Trans. Inform. Theory, 1976, 22, №2, p.156-162.

89. Welch L.R. Lower bounds on the maximum cross correlation of signals.- IEEE Trans. Inform. Theory, 1974, 20,№8,p.397-399.