Введение к работе
Актуальность темы. Познание реальных возможностей современных многотерминальных систем связи является причиной бурно развивающихся теоретических исследований в теории информации. Решение таких проблем создает представление о надежности практически проектируемых систем передачи информации и способствует их развитию и усовершенствованию. Математические методы оценок позволяют проектировщикам найти правильные пути к созданию высокоэффективно функционирующих конкретных систем. Важным элементом процесса передачи информации является источник информации. Источником информации может быть природа, человек, вычислительная машина и т. д. Продукцией источника являются его сообщения. Простейшая шенноновская модель системы связи без шума показана на Рис. 1. Это однопутевая связь между источником и получателем, которая является необходимым составным элементом любых сложных пнфоманпонных систем.
Рис. 1. Простая схема кодирования источника.
Цель кодирования - передача на расстояние или хранение во времени последовательностей сообщений источника информации путем представления их в виде символов из некоторого множества ,И={1,2, ...,|Лт|}. Через \J*A\ мы обозначаем число элементов множества Ля. Декодирование является обратным преобразованием с целью восстановления сообщений источника. В общем случае, получатель не заинтересован в абсолютно точном воспроизведении этих сообщений в результате передачи, т. к. часто достаточно полупить приближенные сообщения, но за более короткое время, или за меньшую "плату".
Рассматриваемые нами модели источников относятся к дискрет ным источникам без памяти (ДИБП). Математически это - поел* довательность дискретных, одинаково распределенных, независимы случайных величин {А',}^,. где X,- принимает значение из конечног множества Л', называемого алфавитом источника. Элементы алф; вита называются буквами. Алфавитом для воспроизведенных coot щений служит конечное множество И, вообще говоря отличное о Л'. Шенноновская классическая постановка задачи кодирования m точніша формулируется следующим образом '. Кодируются послі довательности сообщении длины п. п — 1,2,... Критерий качестг воспроизведения формулируется как отображение
d : X х U - [0, оо) .
Искажение между п—векторами определяется как среднее пскажі нпїі между соответствующими компонентами этих векторов. Чпсі R — 1/nlog \М.\ называется скоростью кодирования. Требуется наі тп ту минимальную скорость R(A). с которой можно при болыш: п передавать сообщения источника так, чтобы искажение не превь шало ранее заданный уровень Д > 0. Все скорости, большие Я(Д называются Д—достижимыми. Когда Д = 0 и X = U, мы говорим критерии по вероятности ошибки. Пусть ДИБП имеет порождают распределение Р*.
Классический результат, отражающий взаимосвязь скорости и и
'Shannon С. Е., Coding theorems for a discrete source with a fideli criterioa, IRE Nat. Conv. Rec, Part 4, pp. 142-163, 1959.
кажения, представляется следующей формулой 2
R(A) = min Ip- п(Х Л U),
Q:EP.Qd{X.U)
где Q— условное распределение Q(u \ х). х Є Л', и Є U, а Ep-Q(l(X,U) и 1р-д(Х Л С/*)— математическое ожидание искажения, и шенноновская информация, соответствующие вероятностным распределениям Р* и Q.
Есть п более "строгий" подход к проблеме. Обобщенной характеристикой простой системы кодирования источника является зависимость R(E,A) 3. где Е называется надежностью. Для фиксированных Е > 0 и Д > 0 это та минимальная скорость, с которой при достаточно больших п можно передавать сообщения источника, с вероятностью превышения данного уровня искажения А, не-болыпей 2~п(ехр{— пЕ}). Все скорости, большие R(E,A), называются (Е, А)— достижимыми. При бесконечном убывании Е значение R(E, А) стремится к R(A). Это видно из формулы для R(E, Д)
R(E,A) = max min IPQ(X All),
P:D(P\\P')
где P = {P(x),x Є X} распределение на X, D(P \\ P*)— дивергенция между распределениями P и P*, известная также под названием "расстояния Кульбака-Лепблера распределений Р и Р*". Большой научный интерес представляет изучение всех (Е, А)— достижимых скоростей для многотерминальных систем.
2Чисар И., Кернер Я. Теория информации. Теоремы кодирования для дискретных систем без памяти, М.,Мир, 1985.
'Арутюнян Е. А., Мекауш Б., Оценки оптимальной скорости кодов с заданной экспонентой вероятности ошибки для некоторых источников, шестой межд. симп. по теории информации, тезисы докладов, ч. 1, стр. 22-23, Москва-Ташкент, 1984.
Цель работы. Целью настоящей работы является изучение зави спмостії R(E,A): ее характершацпя в случае бинарного источник; и меры искажения Хэмыинга, а также нахождение (Е, Д)— достпжп мых скоростей для одной модели множественного описания неточнії ка.
Научная новизна. Получены новые результаты, отноептель но характеризацин R(E, Д) как функции от Е и найдена області (Е.А)— достижимых скоростей множественного описания дискрет ного источника без памяти.
Методы исследования. Использованы вероятностные, комбина торные н теоретико-информационные методы исследования и дока зательств соответствующих теорем.
Апробация работы. Основные положения и результаты работь докладывались на семинарах Института проблем информатики и ав томатизации НАН РА, дважды докладывались на конфпренциях Ма тематического общества Армении, на международной конференщн по вычислительным наукам и информационным технологиям (CSIT Ереван, 1997 г.). Один доклад принят на двадцатый международ ный симпозиум по теории информации и ее применениям (S1TA'97 декабрь 2-5, Япония).
Структура диссертации. Диссертация состоит из введения трех глав и списка литературы.
Публикации. По теме диссертации опубликовано 5 работ.