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

• Автор: Левенштейн, Владимир Иосифович
• Шифр специальности: 01.01.09
• Научная степень: Докторская
• Год защиты: 1983
• Место защиты: Москва
• Количество страниц: 226 c. : ил

Введение . *

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

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

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

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

различных типов

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

пространства

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

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

§ 6. Описание множества инвариантных неотрицательно определенных функций
§ 7. Границы максимальной мощности упаковок полиномиальных пространств
§ 8. Алгебраические и комбинаторные свойства максимальных D-кодов
ГЛАВА 3. ГРАНИЦЫ МАКСИМАЛЬНОЙ МОЩНОСТИ УПАКОВОК ОСНОВНЫХ МЕТРИЧЕСКИХ ПРОСТРАНСТВ ТЕОРИИ КОДИРОВАНИЯ И НЕКОТОРЫЕ ПРИЛОЖЕНИЯ
§ 9. Границы для упаковок на евклидовой сфере. Геометрические приложения
§ 10.Границы для упаковок проективных пространств
§ II .Границы для упаковок конечных пространств
§ 12.Нижние границы для суш характеров от многочленов
Приложение А. О нулях ортогональных многочленов
Приложение Б. О плотности упаковки (г-мерного евклидова
Пространства равными шарами
Заключение
Литература

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

как вероятность ошибки декодирования. Первым и самым значительным результатом в теории кодирования и теории информации является теорема Шеннона [873 о кодировании для канала с шумами. Согласно этой теореме при любой скорости передачи, меньшей пропускной способности канала, минимальная вероятность ошибки декодирования стремится к нулю с ростом длины кодов. После того, как было установлено, что это стремление экспоненциальное, возникла важная с практической точки зрения задача о нахождении логарифмической асимптотики минимальной вероятности ошибки декодирования или, в терминологии К.Шеннона [883 » задача вычисления функции надежности канала. В настоящее время эта задача не решена полностью даже для простейших каналов: дискретного двоичного симметричного канала и непрерывного канала с аддитивным гауссовским шумом при ограничении мощности сигналов. К.Шеннон, Р.Галлагер и Э.Беряекэмп [вэ] установили связь задачи вычисления функции надежности для указанных каналов с задачей плотнейшей упаковки хэммингова пространства и евклидовой сферы соответственно. Эта связь такова, что всякое усиление границы, показывающей, что упаковка пространства не может быть очень плотной, приводит к усилению границы для функции надежности соответствующего канала. При этом, если будет доказано некоторое весьма правдоподобное предположение о плотнейшей упаковке хэммингова пространства и евклидовой сферы, то будет получено окончательное решение задачи о вычислении функции надежности для соответствующего канала. Как показал автор [31] , аналогичная связь с
плотнейшей упаковкой хэммингова пространства возникает и в задаче минимизации вероятности необнаруженной ошибки в двоичном симметричном канале. Вероятность необнаруженной ошибки имеет важное значение (см. [51] ) при проектировании реальных систем передачи

из некоторого вектора 2 , который получается из X в результате І - 1 шибок-. Обозначим через ^ (X) ( Ї-1,2,;..) множество векторов, которые получаются из вектора X в результате і или менее ошибок, и полежим -р0 (х) ={Х} * Множество
С Е ^ будем называть кодом, иецравляющим ^ шибок типа -р , если
^(Х)П^(У) = Ф для любых X,V^ А/ (Х^У) (3.1)
(здесь ф - пустое множество); Условие (3.1) равносильно тому, что по любоцу вектору У Є Еу, , который получается из некоторого вектора X £ V/ в результате У или менее ошибок, можно
однозначно определить вектор X •
Покажем, что при некоторых ограничениях на тип Е одиночных шибок можно ввести в Е ^ такую метрику с1^ (X, У) , чтобы совпали понятия код, исправляющий У шибок типа Е , и + 1)-код в метрическом пространстве Рассмотрим на £ £ х Еср величину
ґ , если X Е , /і =0,X,
] (3.2)
") Шъ г в противном случае ,
По построению I) (Х,У)-0 тогда и только тогда, когда
X — У , и 2) оі ^ (XX V) удовлетворяет неравенству треугольника: сІ_р(Х,ї)^ ^(ХД+сЕ^У)* БУДем говорить, что тип -Г сишетричен, если из того, что У £ Е* получается из X <= Е^ в результате одной ошибки, следует, что и X получается из У в результате одной ошибки. Очевидно, что (У,Х)
для любых Х,У Є (и, следовательно, сЦ (X, Ч) является
метрикой) тогда и только тогда, когда тип £ симметричен. В метрическом пространстве Жі — { Е^ } бір (Х,У)} шар радиуса І
-С центром в точке Хе совпадает с множеством "Іу. (X)
<Ц(х,у)