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

РГб од

" о к ¿И 'ЯП?

<изиизиъь ад>5пмэ-зпнл>ь№ иач-изьъ илшаьимгзь ьълппииБьчив!^ ьч ичзттБизитгъ <прприыгъь№ къиБмпьв

ЭЬпшцр[1 (1рш4п10рги4

прпсаииыч1 иорзпьпъьрь ^паичпгчгиъ ипио-пыэ-зпьъъьрь и <ПНД11Г>ПМЭ-31ГЬ ¿ШДГЬЫЬ ФП1ииаЪЭПИ9-зиЧ/ {ЬБЦЭПБПНГС

Чши Й шц [иптр доШ 11.01.09. ЦшрЬйшифЦшЦшО ЩфЬпйЬт^ш и ¿¡шрЬйшифЦш^шй тршйшршбтрртШ

¿ЬфсО^ш-йшрЬйшщМш^шО q[шmlpJruG(ibp¡^ рЫ^шйпф qJlшшl^шG шии1]1бш0[1 ЬиудйшО штЬйш^ипщшй

иьаиич-ьп

ЬришО-1997

ИНСТИТУТ ПРОБЛЕМ ИНФОРМАТИКИ И АВТОМАТИЗАЦИИ НАЦИОНАЛЬНОЙ АКАДЕМИИ НАУК РЕСПУБЛИКИ АРМЕНИЯ

На правах рукописи

Арутюнян Ашот Ншанович

ИССЛЕДОВАНИЕ ДОСТИЖИМОЙ ВЗАИМОЗАВИСИМОСТИ МЕЖДУ СКОРОСТЯМИ КОДИРОВАНИЯ И НАДЕЖНОСТЬЮ ИСТОЧНИКОВ НЕКОТОРЫХ

КЛАССОВ

Специальность 1X01.09. Математическая кибернетика и математическая логика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Ереван-1997.

Работа выполнена в Институте проблем информатики и автоматизации HAH РА

Научный руководитель:

доктор физико-математических наук профессор Арутюнян Е. А.

Официальные оппоненты: Академик HAH РА

Хачатрян Г. Г.

кандидат физико-математических наук Кошелев В. Н.

Ведущая организация:

Институт математики HAH РА

Защита состоится 28 ноября 1997 г. в 11:00 часов на заседани специализированного совета 037 "Математическая кибернетика математическая логика" в институте проблем информатики автоматизации НАН РА по адресу: 375044, г. Ереван, ул. П.Севака,1.

С диссертацией можно ознакомиться в научной библиотеке

ИПИА HAH РА.

Автореферат разослан

Ученый секретарь специализированного сов< к.э.н., с.н.с.

Мелконян А. Е.

Актуальность темы. Познание реальных возможностей современных многотерминальных; систем связи является причиной бурно развивающихся теоретических исследований в теории информации. Решение таких проблем создает представление о надежности практически проектируемых систем передачи информации и способствует их развитию и усовершенствованию. Математические методы оценок позволяют проектировщикам найти правильные пути к созданию высокоэффективно функционирующих конкретных систем. Важным элементом процесса передачи информации является источник информации. Источником информации может быть природа, человек, вычислительная машина и т. д. Продукцией источника являются его сообщения. Простейшая шенноновская модель системы связи без шума показана на Рис. 1. Это однопутевая связь между источником и получателем, которая является необходимым составным элементом любых сложных пнфоманпонных систем.

источник коде]) декодер получатель

Рис. 1. Простая схема кодирования источника.

Цель кодирования - передача на расстояние или хранение во времени последовательностей сообщений источника информации путем представления их в виде символов из некоторого множества М={1,2, ..., [А^]}. Через |.М| мы обозначаем число элементов множества ЛЛ. Декодирование является обратным преобразованием с целью восстановления сообщений источника. В общем случае, получатель не заинтересован в абсолютно точном воспроизведении этих сообщений в результате передачи, т. к. часто достаточно получить приближенные сообщения, но за более короткое время, или за меньшую "плату".

з

Рассматриваемые нами модели источников относятся к дискрет ным источникам без памяти (ДИБП). Математически это - поел* довательность дискретных, одинаково распределенных, независимы случайных величин {А',}^,. где X,- принимает значение из конечног множества Л', называемого алфавитом источника. Элементы алф; вита называются буквами. Алфавитом для воспроизведенных со о с щенин служит конечное множество Ы, вообще говоря отличное о X. Шенноновская классическая постановка задачи кодирования т точнпка формулируется следующим образом Кодируются поел! довательности сообщений длины п. п — 1,2,... Критерий качестг воспроизведения формулируется как отображение

й : Л' х Ы [0, оо) .

Искажение между п—векторами определяется как среднее иска,ж нпй между соответствующими компонентами этих векторов. Чпс! Д = l/nlog |А4| называется скоростью кодирования. Требуется на] тп ту минимальную скорость Я(А). с которой можно при болыш: п передавать сообщения источника так, чтобы искажение не превь шало ранее заданный уровень Д > 0. Все скорости, большие Я(Д называются Д—достижимыхш. Когда Д = 0 и X = Ы, мы говорим критерии по вероятности ошибки. Пусть ДИБП имеет порождают распределение Р*.

Классический результат, отражающий взаимосвязь скорости и и

'Shannon C. E., Coding theorems for a discrete source with a fideli criterion, IRE Nat. Conv. Rec., Part 4, pp. 142-163, 1959.

кажения, представляется следующей формулой 2

R(A) = min Ip- Q(X Л U),

Q:Ep.Qd(X.U)<A

где Q— условное распределение Q(u | л;), x € Л', и £ Ы, а Ep- q(1(X,U) и AU) — математическое ожидание искажения,

и шенноновская информация, соответствующие вероятностным распределениям Р* и О.

Есть п более "строгий" подход к проблеме. Обобщенной характеристикой простой системы кодирования источника является зависимость R(E, А) 3, где Е называется надежностью. Для фиксированных Е > 0 и Д > 0 это та минимальная скорость, с которой при достаточно больших п можно передавать сообщения источника, с вероятностью превышения данного уровня искажения Д, небольшей: 2~п£(ехр{— пЕ}). Все скорости, большие R(E,A), называются (Е, А)— достижимыми. При бесконечном убывании Е значенне R(E, Л) стремится к R(A). Это видно из формулы для R(E, Д)

RIE, Д) = max min 1ро(Х Л ¡7),

P:D(P\\P')<E Q:Ep:Qd(X,U)<b ,VV '

где P = {P(x),x £ X} распределение на X, D(P || P*)— дивергенция между распределениями P и P*, известная также под названием "расстояния Кульбака-Леиблера распределений Р и Р*". Большой научный интерес представляет изучение всех (Е,А)— достижимых скоростей для многотерминальных систем.

2Чисар И., Кернер Я. Теория информации. Теоремы кодирования для дискретных систем без памяти, М.,Мир, 1985.

'Арутюнян Е. А., Мекауш Б., Оценки оптимальной скорости кодов с заданной экспонентой вероятности ошибки для некоторых источников, шестой межд. симп. по теории информации, тезисы докладов, ч. 1, стр. 22-23, Москва-Ташкент, 1984.

Цель работы. Целью настоящей работы является изучение зави ciiMOcTii R(E,A): ее характеризацпя в случае бинарного источник; и меры искажения Хэмминга, а также нахождение (Е, Д)— достижп мых скоростей для одной модели множественного описания нсточнн ка.

Научная новизна. Получены новые результаты, относитель но характеризацин R(E, А) как функции от Е и найдена облает! (Е. А)— достижимых скоростей множественного описания дискрет ного источника без памяти.

Методы исследования. Использованы вероятностные, комбина торные и теоретико-информационные методы исследования и дока зательств соответствующих теорем.

Апробация работы. Основные положения и результаты работь докладывались на семинарах Института проблем информатики и ав томатизации HAH РА, дважды докладывались на конфпренциях Ма тематического общества Армении, на международной конференцш по вычислительным наукам и информационным технологиям (CSIT Ереван, 1997 г.). Одпн доклад принят на двадцатый международ ный симпозиум по теории информации и ее применениям (S1TA'97 декабрь 2-5, Япония).

Структура диссертации. Диссертация состоит из введения трех глав и списка литературы.

Публикации. По теме диссертации опубликовано 5 работ.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

б

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

Вторая глава посвящена характернзации функции R(E, Д) в случае бинарного источника и расстояния Хэммпнга в качестве меры искажения (обозначим ее через Rви(Е, Д)).

Пусть Р* = {р*,1—р*} — бинарное распределение задающее источник. Пусть НрЕ(Х) и Яд(А') двоичные энтропии, соответствующие распределениям Ре = {ре, 1 - Ре} п {Д, 1 — Д} на где ре близкое к 1/2 решение уровнения D(Pe || Р*) = Е. Обозначим через [01,02] следующий отрезок:

ехр{£} - ^ехр{2Д} - 1 ехр{Д} + у/ехр{2Д} -Т" exp{¿? +1} ' ехр{£ + 1}

В главе 2 доказаны следующие утверждения.

Теорема 1. Для любого Е > 0 и Д > О

[аьаг] =

rbh{E, Д) =

НРе(Х)-НА(Х), р*<£[аьа2], 1 -ЯД(Х), p'eKüjl,

О, Д > mia{p£, 1 - рЕ}.

где первые два равенства верны при Д < гшп{р£, 1 — Ре}-

Теорема 2. Для положительных значений, Ивн(Е, Д) является вогнутой по Е функцией.

В третьей главе рассматривается так называемая задача тройного описания источника (Рис. 2). В случае двойного описания, аналогичная задача решена Р. Ш. Марутяном4 и в более общем случае, зави-

'Марутян Р. Ш., Скорости множественного описания источника при заданных экспонентах и уровнях качества, Проб, перед, информ., т. 26. вып. 1, с. 83-89, 1990.

спмость ГЦ А) найдена Б. Рпмолди5. Сообщения источника должнь быть доставлены трем адресатам в соответствии с предъявляемым! ими требованиями к точности воспроизведения.

Сообщения ДИБП. с порождающей вероятностью Р* — {Р'(.т) х € Л'}, кодируются тремя кодерами /], /2, /3.

Рис. 2. Конфигурация трех описаний.

Первому декодеру F\ известны выходы лишь Д, второму декодер; известны два описания от /1 и /2, а на третий декодер поступае-информация от всех кодеров. Сообщения восстанавливаются в со отвстствующих алфавитах Л'1, А'2, Л'3 в пределах заданных уровне) искажения А,-, г = 1,3. относительно мер искажения

df : X х X' [0; 00), г = ТД

Пусть е\. б2, ез— вероятности превышения заданных уровней иска жения на соответствующих декодерах. Пусть Е — (Е\, Ej, £3) : Д = (Д1.Д2, Д3).

Тройка скоростей (lii, /(21 R3) называется (Д, Д)—достижимо!

'Rimoldi В., Successive refinement of information: characterization с the achievable rates, IEEE Trans, on Inform. Theory, vol. 40. No. ] January 1994.

сели для достаточно больших тг при этих скоростях

< ехр{—ггЕ,}, г = 1.3.

Обозначим через ЩЕ.А) множество всех (Е. А) —достижимых троек скоростей. Введем следующие множества:

«(Я,-) = {Р:0(Р || Р*) < Е,}. I = ТТЗ.

Обозначим через Ф(Р) функцию, которая каждому распределению Р на X ставит в соответствие условное распределение (^(х1, х2, х3 \ .г:), х' £ X', х 6 Х,г = 1,3. так, что если Р £ а(Е{). то

ЕР^{Х,Х{) < Д,-, г = ТЛ.

Пусть М(Е.А)— множество всех таких функций Ф. Доказана следующая

Теорема 3: Для любых Д- > О, А,- > 0, г = 1.3. имеет место

ЩЕ.А)Э и {(ЯЬД,,Я3):

Фем(ЕА)

> тахРба(£;1) /Р,д {X Л А1), + Д2 > тахРеа(^) /Л<3 [X Л А1, А2),

Щ + Д2 + йз > тахРеа(Ез) (X Л А1, А2, X3)}.

При Е; —у 0, г = 1.3. получается Теорема 4: Ери любых Д,- > 0, г =■ 1,3,

I) {(ЯьЛ2,Дз):

ФеЛ<(Д)

Ri > Ip-л (P-) {X АХ1), Ri + R2 > Ip-^p-) (X A X\ X2), Ri + R-2 + Rz > Ip-w) (lAl'.l'U3)}.

Рассматривается частный случай двойного описания Эль Гамаля-Ковера. Результат обобщен для множественного описания с к кодерами и декодерами.

По теме диссертации опубликованы следующие работы:

1. Haroutunian A. N., An achievable rates-reliabilities-distortions dependence for source coding with three descriptions, Деп. в АрмНИ-ИНТИ, ном. 206-Ар97, 7 е.. 1997.

2. Haroutunian A. N., Haroutunian Б. A., The binary Hamming rate-reliability-distortion function, Proceedings of Conference oil Computer Science ancl Information Technologies, pp. 222-225, Yerevan 1997.

3. Haroutunian Б. A., Haroutunian A. N., Three Descriptions rates-reliabilities-distortions region inner bound, Proceedings of Conference on Computer Science and Information Technologies, pp. 225228, Yerevan, 1997.

4. Haroutunian A. N.. Haroutunian Б. A., An achievable rates-reliabilities-distortions dependence for source coding with three descriptions, Математические вопросы кибернетики и вычислительно! техники, т. 17, с. 70-75, Ереван, 1997.

5. Haroutunian Б. A., Haroutunian A. N., The binary Hamming rate-reliability-distortion function, Математические вопросы кнберне тики и вычислительной техники, т. 18, с. 40-45, Ереван, 1997.

ю

Utiijinijiuiqjip

ll2nm b2iu0fi <uipnipjmGjiuCi, "flpn2 ryxiukpji iuqpjnipGhp{i linrpnQnpiiuiG uipuiqiupjiuGGhp|i U hniuuiiJinipjuxG huiuiuGhi{i ilinfuujnG^mpjnuiG hbininqninnuSp"

Ashot Nshan Haroutunian, "Investigation of achievable interdependence between coding rates and reliability for several classes of sources"

UuihGuifunuiupjniGp Gi|lipi|uj& t aiqpjnipji IjnqiuilnpiiujQ ¿hQOnlljuiQ huiiliul|wpq[i (q&. 1) pGnhiuGpuigiluifr pGmpuiqpli^ huiQqJiuuignu R(.E,A) ^)niQlig|iuij}i (7?-iupujqnipjniG, E-hniuuiiJinipjniG, A -¿brpSuiG iluiljiupijuil}) ipnpuphpiiuiGp hpl]niuiljiiiG uiripjnipli U <biSi5fiQqJi hhmui{npmpjiuG hunluip, hwinljmpjniGGbpfi munnIGuiu]ipi5iuGp, JiQjqhu GrnU uiqpjnipli puiqi5uil[{i GlpupiuqpiIuiG iS}i rpuu]i (/j,A)-haiuaiGhi}i iupuiqnipjniQGhp[i ui[]pmjp[i npryiliuGp:

^luilnuQjijnq E hnmiui]inipjuiG U ;hq\5ujQ A iiuilpupquil|[i hiuiiuip, R(E,A) uiptfbpp uijG iJinppuiqmjG uipuiqnipjniQG t, npmj uiripjnipli inhr^hljnipjniGQhpp l}uiphi]i t huiqnpqb] huiughiuuifipngG' uiu}iuhni{hpiil A-Jig uinuiGui[ni. exp{-nE}-G ¿qhpuiquiGgnii

hun[uiGuiljiuQnipjniG, nip w-p 1) ui rjnp rpu qpn 1 pj niG G hpji hpljuipnipjniGG t:

R(E,A) 4)niGligtiuiQ lunaijjiG uiGquiiS r^iinuiplpjbi t •4uipnipjniGjuiG}i U LThlpuru2[i IjnqiJfig:

trpliniuilpuG uiqpjnipli U <biSG}iGqfi hhnuiilnpnipjiuG qbiqpnid uuiuigi|uJ(J R(E,A) ^niGligJiuij]! inbupp pnip t uiuiiJiu taqpiuhiuGqhpii, np qnjnipjniG mG[i E hniuiuifmipjuiG ii[i uapcfbp, npfig ul(uui£r uijG ipunGnuJ t hiuumiuuiniG U pGipuGniil Jip llb&uiqnijG uipdbpp: O-iu inijui& A -Ji huitiuip bplpuuilpuG hwi|iuuiuphiui4uiGiul}uiG mr[pjnipli R{A) pJiilG t: 3mjg t mpi|ui&, np R(E,K) -G fip rpuilpuG uipcfbpGbpJi pGrpuGiSwG ilfijuilpiijpnul qnqaii{np t puui E-\v. <tunLuipuip, pGrihuiGpuiiqbu, uijG nuinigjili ¿t:

IrfcpljiujnuSu, inhuiulpuG U Guili I}}ipuinuiljiuG ilhd hhmiupppprupjniG t GhplpujuigGnuS ituiGiuGuiliiulj|ig pmqiiiui|hp2nijp ljuiajji hiudwliiupqhpfi hGiupiuiJnpnipjniGGbpli puiguihuijuinulp: UjG pnijt t uiuiiJiu qGuihuiinh^ qnp&GuiljuiGnui Giufmuqcnlnq hiuiSuiliuipq)i npuiljp, huiiSuiuiiuuiuiuJuuiG pGnipuiqpli^Gbpp huiiSbiSiuuihpii| inhumljiuGnpbG huijinGfi GpuiGg oupnfiilui^ uuihiiuiGfi hbui: Ujq

n

jiiîuiuinni{, uimuQàûmyi t luripjnipli puiqiSuiliJi QlpupuiqiiiíuiG JuQr]Jipii:

Ципшр^шб t mripjmpli bnuil)}i ûljiupuiqpiSuiG huiüuiljuipq, npnitf uiniugliû шщшЦгщшЦпр^р uinuiGnuS t i5[uujG iShlj ЦгщшЦпр^!1 uii|jiLi|Gfapfi, hpljpnpqp hpljni l]nr^tu 14np[i¿Qhp}i, Jiulj bppnprçp mhrpiul] t pnpip hpbp l|ni]uii)np)i^Cihp}i QL|mpuiq[mipjniûQhp[iQ (q&. 2): Uju luuiîuiliujpqii h ш il 111 p щт^фид t шщшЦпфцфгр^йЬуф tqphpnuî hniuuiiJinipjuiG U ¿bqduiG duiljuiprpul(Gbp|ig lpufiii|uiö huiuuiGbiJi lupuiqnipjntûGbpli injipnijpp: UpryniGpQ pGiihiuGpuigilui& t giuGljuiguiô к ЦпгриЦпр^йЬр}! U uiupul}nrpm}npli¿Ghpli цЬи|р}1 hiuiîuip: £GGiuplpJui& bG uiiipjnipli pmqiSiulifi GlpupuiqpúiuG luj^GriJipGbp:

Q-njntpjiuG pbnpbiJGbpp hfitfGi|nii5 bG öiuöl|mjpübp]i i|bpaiphji|iu| püi|hiuüpiugijiu& ]biSüiujli ijpiu, npji uiu|iugnijgp ЦштшрЦшй t CbCGnGfi щидтшЬшЦшй 1рщш1(прйшй rpuuiuljiuG iShpnrpiiJ: