автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Оценки Е-пропускной способности меняющихся каналов

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

На правах рукописи УЖ 519.724.6

АРУТЮНЯН МАРИАМ ЕВГЕНЬЕВНА

ОЦЕНКИ Е-ПРОПУСКНОЙ СПОСОБНОСТИ МЕНЯЮЩИХСЯ КАНАЛОВ

05.13.17 - теоретические основы информатики

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

Ереван 1991

Работа выполнена в Ереванском ордена Трудового Красного Знамени государственном университете.

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

Р.В.Амбарцумян Официальные оппоненты -доктор физико-математических наук

А.Г. Дьячков доктор физико-математических наук Б.С.Нахапетян Ведущая организация -Институт проблем передачи

информации АН СССР Защита диссертации состоится " " узл?^ ил} 1991г. в час. на заседании специализированного совета

К 005.21.01 по специальности 05.13.17 -"Теоретические основы информатики" при ИПИА АН РА и ЕГУ по адресу: 375044, г.Ереван 44, ул. Паруйра Севака 1:

С диссертацией можно ознакомиться в научной библиотеке ИПИА АН РА и ЕГУ.

Автореферат разослан Ученый секретарь специализированного совета д.ф.-м.н. профессор

п .. 1991г

С

'1 ЛН-^Шш С.С.

■ . , ОбШАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. В настоящее время интенсивные теоретихо - информационные исследования ведутся под воздействием запросов выч1гслгггеггьпой техники, техники связи и радиолокации. Внимание исследователей привлекают все более сложные многотермкналькьЕ?. а также изменяющиеся во времени

•О"

модели систем связи.

Для каждой из исследуемых систем первоочередной задачей является нахождение ее пропускной способности, которая согласно К.Э.Шеннону1 является верхней грань» скоростей передачи кодов с вероятностью етгябяи стремящейся к нулю при увеличении длины передачи.

Следующей важной теоретико-шформацнонной задачей при

изучении каждой модели связи является исследование ее

2

функции надежности, также введенной Шенноном . В случае однопутеэого какала эта функция E(R) определяется как оптимальный показатель экспоненциального убывания

вероятности ошибки e(n,R) при росте длины передачи п в зави-

1Shannon C.E. Certain results in coding theory for noisy channels.Information and Control,1957,v.l,No.l, p. 6-25.

2Shannon C.E. Probability of error for optimal codes in a Gaussian channel. Bell System Techn.J., 1959, v.38, No.5, • p. 611-656.

- 4 -

сим ости от скорости передачи R.

eín,R) ~ г""010, 0<R<C.

Известны важные результаты о верхних и нижних оценках

функции E(R) полученные многими авторами.

В ряде случаев удобным оказывается изучение

E-пропускной способности- CÍE), которая является оптимальной

скоростью кодов, обеспечивающих экспоненциальное убывание по

п вероятности ошибки. expí-nE) с заданным показателем (надеж' ' 3"

ностью) Н .Такой подход; был предложен Арутюняном .который доказал4, что в случае дискретного канала без памяти функция С(Е) является обратной к E(R), Имеется ряд работ, посвященных построению верхних и нижних оценок функции E(R).

В последние годы особое место среди объектов исследований занимают меняющиеся каналы, матрица переходных вероятностей которых изменяется во времени. Для ряда классов этих каналов была решена задача нахождения пропускной

з.

Арутюнян Е.А. Оценка сверху скорости передачи по каналу без памяти со счетным числом сигналов на выходе при заданной экспоненте вероятности ошибки. Тезисы докл. на III конфер. по теории передачи и кодирования информации. Ташкент, Изд. ФАН Уз. ССР. 1967. с. 83-86.

4Арутюнян Е.А. Об оптимальности передачи информации по каналу с конечным «Дглам состояний, вычислимых на передающем конце. Известия АН Арм. ССР, серия матем.. 1969 т. IV. N 2. с. 81-90.

способности. Поэтому, нахождение границ для Е-пропускной способности является назревшей задачей.

Цель данной работы - исследование Е-пропускной

способности, а именно построение верхних и нижних границ функции С(Е) для ряда типов меняющихся каналов.

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

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

Методы исследований. Использованы как классические, так и разработанные в последние годы методы оценивания. Для построения верхних оценок Е-пропускной способности использован комбинаторный метод, предложенный Е.А. Арутюняном5. Нижние границы Е-пропускной способности составного канала построены методом разбиения графов,

5Арутюнян Е.А. Комбинаторный метод построения верхней границы Е-пропускной способности. Матем., Межвуз. сборник науч. трудов, Ереван, 1982, вып. 1, с. 213-220.

предложенного Чисаром и Кернером6. В главах 3 и 4 нижинг границы для С(Е) построены методой случайного кодарззания.

7 Ö

введенного Шенноном . с использованием леммы об упакоике .

Апробация работы. Основные результат диссертации докладывались на IX симпозиуме по проблеме избыточности в информационных системах (Ленинград, 1986), ¡¡а научно-практической конференции по методике преподавания матекатккии механики в ВУЗ-е (Ереван, 1386), на X праксской конференции по теории информации, статистическим решающим функциям и случайным процессам (Прага, 1986), ка III г..;ел;дународпом семинаре стран членов СЭВ по статистической теории связи и ее применениям (Варна, 1983), на 1Хвсесо:озной конференции по теории кодирования и передачи информации (Одесса, 1988), на III международном коллоквиуме по теории кодирования (Дилижан, 1990), на заседаниях семинаров по теории ¡¡¡¡формации в ИППИ АН СССР, в Ереванском гусугаЕерситете, а ИПИА АН РА и ЕГУ.

Публикации. По теме диссертации опубликовано Э рсбот, список котфых приведен в конце г.аторгфера^.г -

Структура и объем диссертации. . работа состоит из введеигш, четырех глав, разбитых ка 9 1гсргхрафоа.Изложена на

6Csiszär I., Körner J. Graph decomposition a new key tocoding theorems. IEEE Trans, on Inform. Theory, 1981, v.27, No.l,p.5-12.

7

Shannon C.E. A mathematical theory of communication. Bell System Tech. j, 1948, v.27, No.3, pf379-423.. , ■ . .

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

84 страницах машинописного текста.. Библиография содержит 70 наименований. .

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

Приведем следующие определения. Дискретным меняющимся каналом называется семейство дискретных каналов без памяти W = { W : I -УУ , s е 6 } с матрицами переходных вероятностей IIW(y|x,s)ü, х е I, у е У, s е 6, где £ и "У конечные входной и выходной алфавиты, а 6 конечное множество состояний канала. Параметр s может подчиняться какому-либо закону или же меняться произвольным образом. Пусть х =

(х1(х2,...,хп) б гп, у = (У^Уз.....У ) 6 уп, s =

[Sj,s ,.'..,s ) е бП, где п обозначает длину передачи.

Пусть N множество сообщений, подлежащих передаче, a R = i/2 log 1N| - скорость передачи, где |Nf это число элементов множества N. В работе логарифмическая и жспоненциальная функции имеют основанием 2. Кодом газывается пара отображений (f^.g^), где f : N -> £П солирование, a g : УП N - декодирование.

Вероятность ошибочной передачи сообщений i е N обозначается е. . Как обычно, рассмотрены максимальная

_ ! INI

е = max е. и средняя е = -тттч £ ej вероятности ошибки. ieN 1 i'l=l

Через N(n,E) обозначается наилучший объем кода длины г

с вероятностью ошибки не большей чем ехр(-пЕ) для задатка

надежности ЕХ):

N(n,E) = sup { |NI : e(fn>gn) a exp(-nE) }. f.g П " E-пропускной способностью называется функция

С(Е) = ГГпГ - log N(n,E) . Как обычно определяются энтропии H_(S), Hnp(X|S),

Ч Vi"

нп р V(Y|X,S), взаимные информации In p(XaS), In v(YaXS),

,V Vi* Vi"

Iq p v(YaX|S), дивергенции Кульбака - Лейблера D(Q'IIQ) D(P'ÍlP|Q), D(VIIW|Q,P), D(Q'PVIIQPW).

Вторая глава посвящена построению оценок Е-пропускно/ спосбности составных каналов. Дискретный меняющийся кана. называется составным каналом и обозначается Kg , есл состояние s канала неизменно во время передачи одного слов длины п, однако оно может произвольным образом меняться пр переходе к следующему слову.

Составные каналы могут рассматриваться в четыре случаях, когда состояние s известно или неизвестно на кодер или декодере. Однако, оказывается, что знание- состояни

канала на декодере не приводит к улучшению асимптотических характеристик передачи. Поэтому в диссертации рассмотрен лишь случай, когда состояние канала известно и на кодере, и на декодере (в этом случае Е-пропускная способность обозначена С^(Е)), и случай, когда состояние неизвестно ни на кодере, ни на декодере (Сц(Е)).

Доказаны следующие теоремы:

Теорема 1. При любом ЕМ) для Е-пропускной способности канала Кц верны оценки

где

Сс(Е) * R6 (Е) , СЛЕ) з R6 (Е) б sp 6 sp

R6 (Е) = max inf min I (УлХ) ,

sp P s€6 V:D(VIIW |P)sE '

s

R6 (E) = inf max min I v(YaX) .

Sp se6 P V:D(VIIW |P)sE '

s

Теорема 2. Для любого E > 0 верны неравенства

CUE) £ max (R 6(Е), R 6(E)) 6 г x

Cc(E) £ max (R 6(E),R 6(E)), b г x

где

R 6(E) = max inf min II(YaX) + D(VUW |P) - E|+,

Г P se6 V:D(VflW 1P)SE P'V S

s

R 6(E) = max inf min { ID „(ХлХ) + |Md_ (X,X) - E|+}, X P 56бРх=РГР P'V . BlS

R б(Е) = inf шах min |I (YaX) + D(VÜW |P) - E{+,

Г se6 P V:D(VRW |P)sE ' S

s

R 6(E) = inf max min г.(ХлХ) + |Md_ (X,X) - Е|"">. x • se6 . P ,V 'S

Здесь V:I I вероятностная ыатрица, отличная от единичкой,

а d (х,х) - расстояние Бхаттачарня: и, s

dn (х,х) = - log £ /w~(y|x) W (у|х).

Lj, Ь S S

у

В третьей главе построены оценки Е-пропуск! юн способности канала со случайным параметром с информированным кодером. Меняющийся канал называется каналом со случайным параметром и обозначается К^, если состояние se6 меняется независимо в каждый момент времени с одним и тем же распределением Q(s) на 6. В работе рассмотрена ситуация,

когда выбор состояний канала не зависит ни от передаваемого, , . » ... • 1 ни от получаемого слов; вся последовательность состояний s

известна при кодировании и неизвестна при декодировании.

Е-пропускные % способности этого канала в случае максимальной

и средней. , вероятности . ощкбки обозначены, соответственно,

Cq(E) и ¿^Ш).

, Доказана следующая.теорема: . ; ; - , ,

Теорема При любых Е>0 ' для канала К^ имеют место

оценки.

'-Ч1

R Q(E!) W с' (Е) s:cl!) s R Q (К), г Q Q sp

где

- и -

Г< Q(E)=max min {I (YaXS) - I . (SaXY)>

jP P Q\V:D(Q'PV!IQPW)£E g ' '

R Q(E)=max min 11 (YaXS) -1 (SaXY) +

P Q',V:D(Q'PVÜQPW)£E V '

+ D(Q'PVIIQPW) - E|+.

Рассмотрен такх<е более общин капал со случайным параметром.з котором распределение случайного параметра s фиксировано при передаче длины п, но при следующей передаче может произвольным образом меняться в пределах множества Р'с р(б), где Щ6) семейство всех вероятностных распределений на 6. Здесь также предполагается наличие на кодере полной информации о состояниях. Е-пропускные способности этого канала з случае максимальной и средней вероятностей ошибки

обозначены, соотвествекно, С„,(Е) и С^ЛЕ).

V V

Теорема 4. При любых Е > 0 верны оценки

R^'iE) ^ Ср,(Е) з"С^7ТЕ) ^ Rgp' iE) ,

где

R ^ (Е) = inf R °(Е), SP - QeJTr SP

R ^'(E) = inf R Q<E).'

• Г . = . • QsP' r ..........• -

В конце третьей главы в качестве примера вычисления

верхней границы E-пропускной способности рассмотрен канал со . случайными дефектами и ошибками.

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

Дискретный меняющийся канал называется произвольно меняющимся и обозначается К, если состояние канала se6 меняется в каждый момент времени произвольным образом. Рассмотрена та же ситуация, что и для канала со случайным параметром. Е-пропускные способности этого канала в случае максимальной и средней вероятностей ошибки обозначены, соответственно, С(Е) и С(Е). Доказана следующая

Теорема 5. Для любого Е>0 имеют место неравенства

R' (Е) £ С(Е) £ СШ i R (Е), г sp

где г ■ . . : ,

R (Е) = min max min {I_ (YaXS) - I (SaXY)>

Sp Qef)(G) P V:D(VI1W|Q,P)SE ' '

R (E)= min max min |I (YaXS)-I (SaXY) +

r Qep(6) P V:D(VIIW|Q,P)sE • '

'л , +D(VIIW|Q,P) - E|+.

Отмечается, что во всех рассмотренных каналах, так же

как ' и в дискретном , канале без памяти, при значениях Е.

меньших некоторой критической величины, имеет место

совпадение верхних и нижних оценок.

Основные результаты диссертации опубликованы, в

следующих работах: - .

1. Арутюнян Е.А.. Арутюнян М.Е. Верхняя граница Е - пропускной способности для дискретного канала со случайным

параметром. Матер, республ. научно-практич. конференции

■í •

по методике преподавания матем. и механ. в ВУЗ-е, Ереван, 1986, с. 53-54.

2. Арутюнян Е.А., Арутюнян М.Е. Оценки Е-пропускной способности канала со случайным параметром. Тезисы доклада IX всесоюзная конференция по теории кодирования и передачи информации. Одесса. 1988, ч. 1, с. 3-5.

3. Арутюнян Е.А.. Арутюнян М.Е., Марутян Р.Ш. Обзор некоторых исследований по теории информации. III Между нар. семинар стран членов СЭВ по статистической теории связи и

ее применениям. Тез. докл. Варна. НРБ, 1988, с.2.

4. Арутюнян М.Е. Границы Е-пропускной способности для составных каналов. Тезисы докладов, IX симпозиум по проблеме-избыточности в инф. системах, Ленинград. 1986, т.1, с. 23-25.

5. Арутюнян М.Е. Границы Е-пропускной способности составных каналов. Ученые записки ЕГУ, 1987. N 3. с.22-29.

6. Арутюнян М.Е. E-оптимальные коды для произвольно меняющегося канала с информированным кодером. Тезисы докладов. IX всесоюзная конференция по теории кодирования и передачи информации. Одесса. 1988. ч.1, с. 24-26.

- и -

7. Арутюнян М.Е. Границы оптимальных скоростей передачи по меняющемуся каналу при заданной экспоненте вероятности ошибки. Дел. в АрмНИИНТИ. 1990, N 22-Ар90, 24 с.

8. Haroutunian Е.А. Haroutunian М.Е. Sphere packing bound for rate-reliability function of the channel with random parameter. Statistical Data Analysis, Sofia, 1987, p. 20-21.

9. Haroutunian E.A. Haroutunian M.E. E-capacity upper bound for channel with random parameter. Problems of Control and Inform. Theory, 1988, v. 17, No. 2, p. 99-105.

Д

>