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

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

Арутюнян Мариам Евгеньевна

ТЕОРЕТИКО-ИНФОРМАЦИОННОЕ ИССЛЕДОВАНИЕ МНОГОТЕРМИНАЛЬНЫХ И МЕНЯЮЩИХСЯ ДИСКРЕТНЫХ КАНАЛОВ СВЯЗИ

05.13.17. "Теоретические основы информатики"

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора физико-математических наук

Москва 2005

Работа выполнена в Институте проблем информатики и автоматизации Национальной академии наук Армении.

Официальные оппоненты:

доктор физ.-мат. наук, проф., Прелов Вячеслав Валерьевич доктор физ.-мат. наук, проф., Дьячков Аркадий Георгиевич доктор техн. наук, проф., Габидулин Эрнст Мухамедович

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

Институт вычислительных технологий РАН, Сибирское

отделение

Защита состоится июня 2005г. в 11 час. на заседании диссертационного совета Д.002.077.01 при Институте проблем передачи информации РАН по адресу: 127994, Москва, ГСП-4, Большой Каретный пер., 19.

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

Автореферат разослан мая 2005г.

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

Цитович И. И.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы.

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

Для каждого из исследуемых каналов W согласно Шеннону первоочередной теоретико-информационной задачей является нахождение его пропускной способности Скоторая определяется как верхняя грань скоростей кодов с вероятностью ошибки стремящейся к нулю при увеличении длины кода N. Важные свойства каждой системы передачи информации отражает функция надёжности, введенная (также как и понятие пропускной способности) Шенноном. Эта функция определяется как оптимальный показатель экспоненциального убывания вероятности ошибки при росте длины передачи N в зависимости от скорости передачи Я.

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

О < Я < С(№), полностью эта задача решена лишь в частных случаях. Для однопутевых каналов типична ситуация, когда найденные верхняя и нижняя оценки функции Е(Я^) совпадают лишь при скоростях в интервале Нсп < Я < г — значение скорости, в которой

производная Е(Я^) по R равна -1.

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

Цель диссертационной работы.

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

Объект исследования.

В данной диссертации объектом исследований являются дискретные многотерминальные и меняющиеся каналы без памяти. Исследуется E-пропускная способность, которая является оптимальной скоростью кодов, обеспечивающих экспоненциальное убывание по длине кода N вероятности ошибки с заданным показателем (надёжностью) Е. Эта функция С(Е, W) впервые была рассмотрена Е. Арутюняном и является обратной к функции надёжности.

Изучение E-пропускной способности в некоторых случаях оказывается более удобным. Кроме того, когда надёжность приближается к нулю, E-пропускная способность сходится к пропускной способности канала, и таким образом, с помощью построения оценок для С(Е, W) можно получить оценки и для пропускной способности С(М). В этом смысле E-пропускную способность можно рассматривать как обобщение понятия пропускной способности.

В настоящей работе предложены методы исследования Е-пропускной

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

Методы исследования.

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

В основе метода построения нижних границ E-пропускной способности лежит подход шенноновского метода случайного кодирования с использованием, так называемой, леммы об упаковке1. Этот метод, который ранее применялся для доказательства нижних оценок пропускной способности и функции надёжности дискретного канала без памяти, развит и применен к исследуемым сложным каналам. Имея ввиду способ доказательства, нижние границы называются границами случайного кодирования. Для каждой из рассмотренных в диссертации моделей, приходится доказывать новую модификацию леммы об упаковке и решать проблему нахождения и доказательства нижних границ.

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

Метод разбиения графов, предложенный Чисаром и Кернером2 для построения нижних границ функции надёжности обычного однопутевого канала, модифицирован для доказательства границы случайного кодирования и границы с выбрасыванием E-пропускной способности составного канала.

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

"Ceiszir 1., Körner J. Graph decomposition: A new key to coding theorems. IEEE Transactions

on Information Theory. 1981. V. 27. No. 1. P. 5-12.

Научная новизна.

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

— метод построения нижних границ ^-пропускной способности для меняющихся каналов;

— метод построения внутренних границ области ^-пропускной способности для многотерминальных каналов;

> л

— метод построения границы с выбрасыванием Е-пропускной способ-

у , ' .Г

ности для составного канала;

— метод построения верхних границ Е-пропускной способности для меняющихся каналов;

т » -- *

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

Разработанные методы применены для исследования ряда важных классов каналов. Построены

— внешние и внутренние оценки области E-пропускной способности для

• двустороннего канала с ограничениями,

— внутренние оценки области Е-пропускной способности для

• общего интерференционного канала,

• интерференционного канала с коррелированным кодированием,

• общего широковещательного канала,

• канала с множественным доступом с коррелированными источниками, а также ряда других моделей КМД,

• канала с двумя входами и двумя выходами.

— верхние и (или) нижние границы E-пропускной способности для

• составного канала,

• канала со случайным параметром,

• канала множественного доступа со случайным параметром,

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

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

Достоверность и обоснованность.

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

Теоретическая и практическая значимость полученных результатов.

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

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

Апробация работы. Основные результаты диссертации докладывались на DC симпозиуме по проблеме избыточности в информационных системах (Ленинград, 1986), Республиканской научно-практической конференции по методике преподавания математики и механики в ВУЗе (Ереван 1986), Международном семинаре по анализу статистических данных (София 1987), DC всесоюзной конференции по теории кодирования и передачи информации (Одесса, 1988), III Международном семинаре стран членов СЭВ по статистической теории связи и её применениям (Варна, 1988), IV международном коллоквиуме по теории кодирования (Дилижан, 1991), XXII пражской конференции по теории информации, статистическим решающим функциям и случайным процессам (Прага, 1994). Международных симпозиумах по теории

информации (Вистлер, 1995, Ульм, 1997), 7-ой совместной шведско-российской международной конференции по теории информации (Санкт-Петербург, 1995), Международных конференциях по компьютерным наукам и информационным технологиям (Ереван, 1997/ 1999, 2001, 2003), Международных встречах по общей теории информационной связи (Билефельд, февраль, ноябрь, 2002), на заседании семинара группы стохастической обработки изображений Женевского университета (Женева, 2005), на заседаниях семинаров по теории информации в ИППИ РАН, в Ереванском государственном университете, в ИПИА НАН РА, в Институте математики НАН РА.

Публикации.

По теме диссертации опубликованы 34 научные работы, список которых приведен в конце автореферата.

Структура и объем диссертации.

Диссертация состоит из введения, десяти глав, заключения и списка литературы. Тематически диссертация делится на две части: многотерминальные (главы 2—6) и меняющиеся каналы (главы 7 — 10). Главы разбиты на параграфы.

Объем работы — 232 страницы, влючено 16 рисунков, библиография содержит 246 наименований.

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

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

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

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

диссертации все логарифмические и экспоненциальные функции рассматриваются при основании 2.

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

В параграфе 1.3 описан однопутевой дискретный канал без памяти W с конечными входными и выходными алфавитами X, У и стохастической матрицей переходных вероятностей

матрицы является условной вероятностью получения символа у € У на выходе канала, если на входе был передан символ

м

т

У?

тп

М

Рис. 1. Модель простейшей однопутевой системы связи.

Передача осуществляется блоками длины Ы, при этом N называется длиной передачи. Канал без памяти в каждый момент действует независимо от предыдущих и последующих переданных и принятых сигналов. Сообщение, подлежащее передаче, обозначается через т, множество сообщений — М, число сообщений — через М. Блочным кодом длины N для канала Ж называется пара отображений (/,<?)> где кодирование, ад: У" -*М декодирование. Определяется вероятность е(т) ошибочной передачи по каналу сообщения т 6 М. при использовании кода

е(т) = - <Г'(т)|/(т)) = 1 - И^(<Г](т)|/(т)).

Рассматриваются две версии общей вероятности ошибки кода максимальная вероятность ошибки

и средняя вероятность ошибки для равновероятных сообщений

Очевидно, что e(f,g,N,W) >e(f,g,N,W).

Скоростью передачи кода (/, д) объема М называется

R(f,9,N)^N~4ogM.

Оптимальность передачи состоит в необходимости иметь наибольшее множество сообщений и при заданной малой максимальной или средней вепоятности ошибки. Задача рассматривается асимптотически, при

JV —к».

В параграфе 1.4. определяется функция надежности E(R,W) дискретного канала без памяти и приводятся формулировки известных верхних и нижних границ.

В следующем параграфе определяется .Е-пропускная способность R(E,W) = C(E,W) дискретного канала без памяти. Функция скорость—надежность, которую по аналогии с пропускной способностью можно называть £-пропускной способностью, определяется следующим образом:

R(E, W) = С(Е, W) = ТтГ-^г log М(Е, N, W),

где M(E,N,W) — наилучший объём кода длины N для канала W, удовлетворяющего условию экспоненциального убывания вероятности ошибки с заданной надёжностью Е > 0

е(/,0,ЛГ,ИО<ехр{-ЛГЯ}.

Для однопутевого дискретного канала без памяти W Е. Ару-

тюняном3 доказано, что E(R, W) является обратной к функции R(E, W).

E-пропускная способность называется максимальной или средней и

обозначается, соответственно, C(E>W) или "ü{E,W) в зависимости от

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

того, какая вероятность ошибки рассмотрена в определении. Очевидно, что при всех 0 < Е < оо

C(E,W) <V(E,W) <C{W).

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

Последний параграф первой главы содержит обзор основных результатов диссертации.

Во второй главе диссертации рассматривается модель двустороннего канала с ограничениями, впервые изученного Шенноном4. В первом параграфе главы описан общий двусторонний канал лишь для сравнения, для этой модели результатов не получено. Двусторонние каналы имеют два терминала. Каждый терминал передает сообщение на другой терминал через двусторонний канал, передача в одном направлении взаимодействует с передачей в противоположном направлении. Источники двух терминалов независимы. Кодирование на каждом терминале учитывает сообщение, подлежащее передаче, и последовательность символов, полученных на этом терминале. Аналогично, декодирование на каждом терминале основывается на последовательностях полученных и отправленных на этом терминале символов. Формально, область пропускной способности определяется как выпуклое замыкание множества всех пар скоростей для которых при всех достаточно болвших длинах передачи N существуют кодв1 с вероятностью ошибки, не превышающей заданное малое число

Более доступной изучению оказалась модель двустороннего канала с ограничениями, где по сравнению с общим каналом, передаваемая последовательность на каждом терминале зависит только от сообщения, но не зависит от полученной на этом терминале последовательности

'Shannon С. Е. Two-way communication channels. Ргос. 4th Berkeley Sympoe. Math. Statist, and Probability. Berkeley: Univ. of Calif. Press. 1961. V. 1. P. 61ЫИ4.

(рис. 2). Этой модели, обозначаемой посвящены все последующие параграфы главы 2.

Рис. 2. Двусторонний канал с ограничениями

Когда с терминала 1 посылается символ х\ б Х\, соответствующий ему выходной символ у\ 6 ЭД поступает на терминал 2. Одновременно с терминала 2 передается входной символ хг, и соответствующий символ У2 поступает на терминал 1.

Пусть Е — (EitEz), Ei > 0, i = 1,2. Неотрицательные числа Ri,R-2 называются ^-достижимой парой скоростей для двустороннего канала с ограничениями, если для любых S, > 0, г = 1,2, существует код такой, что при достаточно больших N

^ log М, > Я, - 6„ г =1,2,

и

e,(f,9,N,WT) < exvi-NE,}, г = 1,2.

Множество всех E-достижимых пар скоростей называется областью Е-пропускной способности для средней вероятности ошибки и обозначается

Двусторонний канал с ограничениями также был исследован Шенноном4, который получил область пропускной способности C{Wt) этого канала. Дуек5 показал, что пропускные способности двустороннего канала для средней и максимальной вероятностей ошибок не совпадают. Несмотря на большое число работ, посвященных изучению двусторонних каналов, до сих пор результатов относительно функции надёжности или Е-пропускной способности не было получено.

"Dueck G. Maximal error capacity regions are smaller than average error capacity regions for

multi-user channels. Problems of Control and Information Theory. 1978. V. 7. No. 1. P. 11-19.

Для двустороннего канала с ограничениями в работах [16] и [19] были построены границы сферической упаковки "R.sp(E, WT) и случайного кодирования ИТ{Е, Wr) области ^-пропускной способности при средней вероятности ошибки. Пусть 1lsp(P,E,WT) = {(RuR2):

О < Äi < min Im (Xi Л YilXj),

О < R2 < min Ip,v2(X2 Л Y2|Xi)},

и

K,P(E, WT) = со(иП„(Р, E, WT)), p

(здесь и далее через со(А) обозначается выпуклая оболочка множества

•А)

nr(P*,E,WT) = {(RuR2):

О < üi < min \IrvAXi Л Хь У,)+

+D{PoVi\\P*oW1)-El\+, О < Д2 < min л ХЬУ2)+

+D{PoV2\\P,OW2)-E2\+},

Пг(Е, \УТ) = соЩ^Р^Е^т)). р*

Имеет место следующая теорема:

Теорема 2.1. При всех Е = (ЕиЕг), Е\ > 0, £2 > О,

^(Я, И^г) С ~С{Е, У/т) С 7гвр(£7, Жг).

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

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

вероятностей. Параграфы 2.4 — 2.6 содержат подробные доказательства полученных границ.

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

0 1 о г 0.3 0.4 0.5 о.с

Л

Рис. 3. Пропускная способность

1

двустороннего канала с ограничениями Трехмерные области границ случайного кодирования и сферической упаковки представлены соответственно на рис. 4а и 46.

Рис. 4а. Граница случайного кодирования E-пропускной способности двустороннего канала с ограничениями

/»'л /

Рис 46 Граница сферической упаковки

E-пропускной способности двустороннего канала с ограничениями В третьей главе изучаются сложные модели общего интерференционного канала и интерференционного канала с коррелированным кодированием В многотерминальной системе связи называемой интерференционным каналом (в диссертации обозначается через имеется несколько входов и столько же выходов С каждого входа через обший канал посылаются сообщения соответствующему адресату Для простоты изложения достаточно рассматривать случай с двумя входами и двумя выходами

В параграфе 3 1 обсуждается общий случай, введенный в рассмотрение Шенноном1 когда кодеры функционируют независимо один от другого (рис 5)

Рис 5 Общии интерференционный канал

Исследованию интерференционных каналов посвящены работы Алсведе, Карлайла и других, однако пропускная способность пока найдена лишь для частных случаев

Обозначим

В параграфе 3.2. сформулирована, а в параграфе 3.3 доказана теорема о внутренней границе области Е-пропускной способности общего интерференционного канала. Определим следующую область:

nT(P*,E,Wi) = {(Rl,R2):

О < Ri < min |Ipv,(Yj Л Xi)+ Q.ViißtPomiPW,)^! '

+D(PoV1\\P*oW1)-Ei\+, 0 <R2< min | л X2)+ + D{PoV2\\PtoW2)-E2\+}.

Hr{E, Wi) = со (jj W, E, W/)) .

Результаты автора, полученные для этого канала, опубликованы в работах [20], [23], где была доказана следующая теорема:

Теорема 3.1. При всех Е > 0 о б л асГЕД^л я е т с я оценкой случайного кодирования для области E-пропускной способности общего интерференционного канала в случае средней вероятности ошибки:

ЩЕМ) C-Ö(E,Wr).

В качестве следствия при Е\ —* О, Е2 —* 0 получается внутренняя граница области пропускной способности, совпадающая с нижней границей, полученной Алсведе6.

В параграфе 3.4 изучается другая конфигурация интерференционного канала, введенная в рассмотрение автором, а именно интерференционный канал с коррелированным кодированием, когда один из двух кодеров до кодирования получает кодовое слово, посылаемое с другого кодера (рис. 6).

6Ah!swede P. F. The capacity region of a channel with two senders ««id two receivers. Ann.

771] fl Xl У1 91 m\ ,

\ XI W

rm n x2 , n 92 m'j

Рис. б. Интерференционный канал с коррелированным Рассмотрим

nr(P,E,WI) = {{R1,R2):

О <Ri< min |/w (У, Л Xj) + Vi || |Р) - Г, о < R2 < min |W (У2 А Х2) - ЫХу Л Х2)+

Обозначим

П»{Е, Wj) = со (у Е, .

В работах [20], [21] доказана следующая теорема:

Теорема 3.2. При всех Е > 0 область HJ^EjWi) является оценкой случайного кодирования для области E-пропускной способности интерференционного канала с коррелированным кодированием в случае средней вероятности ошибки:

n,{E,Wi) CC(E,W¡).

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

Четвертая глава посвящена исследованию важной модели общего широковещательного канала (рис. 7), впервые рассмотренной Ковером7.

'Cover Т. М. Broadcast channels. IEEE Transactions on Information Theory. 1972. V. 18. P. 2-14.

Рис. 7. Широковещательный канал В обзорной статье Ковера8, посвященной 50-летию теории информации, приводится список более чем 100 работ, в которых изучались широковещательные каналы, однако нахождение области пропускной способности остается пока открытой проблемой.

Широковещательный канал \¥в — это система связи с одним кодером и многими адресатами. Однако для краткости формулировок достаточно изучать канал с двумя получателями. В параграфе 4.1 рассмотрен общий широковещательный канал с тремя источниками. Три источника создают, соответственно, сообщения из соответствующих

конечных множеств Ма, .Мь -М.2- Сообщения должны быть закодированы общим кодером в кодовое слово х длины N и переданы через каналы ^ и '2 двум получателям. В параграфе 4.2. сформулирована внутренняя граница области Е-пропускной способности. Обозначим

ВД, Р, Д) - (К : вдад, Р) < £,}, ¿=1,2.

Рассмотрим следующие области:

0 < До < min

min г ( IIQiP,v.(Yt А i/o) + D(V,\\Wt\Q, Р) - Е,\

0<Я,< min IiQjmfX Л U,\Uo) + D{V,\\W,\Q,Р) - Ег\+,

8Cover Т. М. Comments on broadcast channels 1998 V 44 P. 2524-2530

IEEE Transactions on Information Theory.

° - ñ3- £ > л U3.,\u0)+

+£>(V3_,||W3_,|Q,P) - £3-,Г - IQ(UX Л U2\UO),

UriQ, P, E, WB) = U K(Q, P, E, WB), .=1,2

K(E,WB)= (J K(Q,P,E,WB).

QPeQP{H,xUixUixX)

Теорема 4.1. Для всех E¡ > 0, £2 > 0 область Hr,{E, WB) является внутренней оценкой для области E-пропускной способности широковещательного канала:

Пг(Е, Wb) С С(Е, Wb) СÜ(£, Wb),

или, другими словами, любая тройка скоростей (Rq,Ri,R2) £ Лт(E,WB) является Е-достижимой для широковещательного канала.

Предел полученной оценки при Е —*0 совпадает с известной областью случайного кодирования для пропускной способности канала, которую получила Мартон9. Теорема 4.1 доказана в параграфе 4.3. Материал этой главы опубликован в работах [18J, [24], [25].

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

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

•Marton К. A coding theorem For the discrete memoryless broadcast channel. IEEE Transactions on Information Theory. 1979. V. 25. P. 306-311.

множественного доступа с коррелированными источниками (рис. 8), обозначенный в диссертации через ЖМ.

Рис. 8. Канал с множественным доступом Три независимых источника с множествами сообщений Мо = {1,2,..., Мо}, М\ = {1,2,..., Мх} и М2 = {1,2,..., М2} создают сообщения, которые должны быть переданы двумя кодерами. Один из источников связан с двумя кодерами, а каждый из двух других связан только с одним из кодеров. В частном случае с М0 = 1 получаем классический, так называемый, обычный канал с множественным доступом. Модель, в котором М1 = 1, называется асимметричным каналом с множественным доступом. Рассмотрена также конфигурация, называемая каналом множественного доступа с подглядывающими кодерами, когда первый кодер имеет информацию о кодовом слове, созданном вторым кодером.

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

В работах [10], [141 были получены соответствующие оценки сферической упаковки и случайного кодирования области Е-пропускной способности при средней вероятности ошибки для вышеотмеченных

I0Dueck G. Maximal error capacity regions are smaller than average error capacity regions for multi-user channels. Problems of Control and Information Theory. 1978. V. 7. No. 1. P. 11-19.

моделей. В статье [30] автором получены новые улучшенные внутренние оценки областей E-пропускной способности для тех же случаев, формулировки которых в виде теорем 5.1 — 5.4 приведены в параграфе 5.2. В параграфе 5.3 доказывается модификация леммы об упаковке для канала с множественным доступом, на которую опирается доказательство внутренней оценки области E-пропускной способности.

Доказательство самой оценки для случая канала с коррелированными источниками приведено в параграфе 5.4. Так же, как и в случае двустороннего канала, предел границы случайного кодирования при совпадает с областью пропускной способности, найденной Слепяном и Вулфом11. Уже известная граница сферической упаковки отличается от этого предела только входным распределением вероятностей, т. е. получение более точной верхней оценки остается открытой проблемой. Оценки для остальных случаев можно доказать аналогично. Для асимметричного канала с множественным доступом и канала множественного доступа с подглядывающими кодерами внешние и внутренние оценки при Е —* 0 совпадают с областями пропускных способностей соответствующих каналов.

В шестой главе модель канала с множественным доступом усложняется. Рассматривается так называемый канал с двумя входами и двумя выходами WD. Алсведе6 нашел область пропускной способности этого канала при средней вероятности ошибки. Основные определения приведены в параграфе 6.1.

Для этой конфигурации в статье [22] получена граница случайного кодирования области E-пропускной способности при средней вероятности ошибки. В диссертации она сформулирована в виде теоремы 6.1 в параграфе 6.2 и доказана в следующем параграфе. Доказательство соответствующей модификации леммы об упаковке изложено в последнем параграфе главы.

Следующие три главы составляют вторую часть диссертации, посвя-

"Slepian D., Wolf J. К. A coding theorem for multiple access channels with correlated sources. Bell System Techn. J. 1973. V. 52, P. 1037-1076.

щенную изучению меняющихся каналов. Дискретным меняющимся каналом называется семейство дискретных каналов без памяти с входным алфавитом выходным алфавитом и множеством состояний канала S. Состояния канала могут изменяться по какому-либо закону или произвольным образом. В зависимости от этого получаются различные модели меняющихся каналов.

Седьмая глава посвящена исследованию самой простой модели среди меняющихся каналов, называемой составным каналом. Описание системы приводится в параграфе 7.1. Дискретный меняющийся канал называется составным каналом, если состояние канала

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

Задача вычисления пропускной способности составных каналов была решена Вольфовицем12. В книге Чисара и Кернера1 приведена граница случайного кодирования и граница сферической упаковки для функции надёжности составного канала. Автор построил аналогичные границы сферической упаковки, случайного кодирования и границы с выбрасыванием для E-пропускной способности во всех возможных случаях информированности кодера и декодера о состоянии канала. Результаты, сформулированные в параграфе 7.2 в теоремах 7.1 и 7.2., отражены в публикациях [1], [3], а также включены в [5], [12], [13]. Следующие два параграфа содержат выводы, соответственно, верхней и нижних границ. Кроме границы случайного кодирования получена граница с выбрасыванием, улучшающая границу случайного кодирования при малых скоростях передачи. Построение нижних границ основано на методе разбиения графов, доказательство разбито на леммы 7.1—7.6.

"Wolfowitz J. Simultaneous channels. Arch. Rational Mech. Anal. 1960. V. 4. No. 4. P. 371 386.

Канал со случайным параметром, которому посвящена восьмая глава. — это совокупность дискретных каналов без памяти •. X —* У, где з есть состояние канала, меняющееся независимо в каждый момент с распределением вероятностей на В параграфе 8.1 рассмотрена наиболее интересная ситуация, когда выбор состояний канала не зависит ни от передаваемого, ни от получаемого слова; вся последовательность состояний 8 известна при кодировании; последовательность состояний 8 не известна при декодировании. Канал со случайным параметром WQ был изучен Гельфандом и Пинскером13, они нашли пропускную способность этого канала. Однако, для функции надёжности или Е-пропускной способности никаких результатов не было известно.

Некоторые верхние и нижние границы Л-пропускной способности для канала со случайным параметром были получены в работах [2], [4], [6], [7], [11]. В параграфе 8.2 диссертации приведены формулировки улучшенных верхней и нижней границ, полученных автором позднее [26], [27]. Рассмотрим следующие функции:

Теорема 8.1. При всех Е > 0, для канала со случайным параметром, когда последовательность состояний канала известна на кодере, имеют место следующие неравенства:

Rr(E, WQ) < С(Е, WQ) < WQ) < Rsp(E, WQ).

Когда E —> 0, предел границы случайного кодирования совпадает с пропускной способностью канала со случайным параметром.

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

"Gelfand S. I., Pinsker M. S. Coding for channel with random parameters. Problems of Control and Information Theory. 1980. V. 8. No. 1. P. 19-31.

Автором в [15] были получены оценки и для остальных трех моделей канала со случайным параметром, когда состояния канала известны на кодере и декодере, сосотояния канала неизвестны ни на кодере, ни на декодере, сосотояния канала известны на декодере и неизвестны на кодере. Для этих случаев верхние и нижние оценки совпадают при малых Е и получаются пропускные способности, которые ранее не были опубликованы. Отметим также интересный факт, состоящий в том, что в последних двух случаях пропускные способности совпадают, в то время как соответствующие границы E-пропускных способностей различны.

В этой же главе, в параграфе 8.7 рассмотрен также обобщенный канал со случайным параметром, когда распределение Q состояния s неизменно во время передачи длины N, но может меняться произвольным образом в пределах некоторого множества распределений V во время следующей передачи длины N. Этот канал, обозначим его Wg, был впервые рассмотрен Алсведе14, который нашел пропускную способность, одинаковую для средней и максимальной вероятностей ошибок. Изучена ситуация, когда только кодер информирован о состояниях канала, сформулированы границы Е-пропускной способности. В последнем параграфе главы, на примере двоичного канала со случайными дефектами и ошибками, исследована граница сферической упаковки E-пропускной способности, которая записывается в параметрическом виде.

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

Канал множественного доступа WR СО случайным параметром это

"Ahlswede R. F. Arbitrarily varying Channels with statcs sequence known to the sender. IEEE TVansactions on Information Theory. 1986. V. 32. No. 5. P. 621-629.

семейство дискретных каналов множественного доступа без памяти ]¥,: Х\хХ2—* У, где состояние канала 5 меняется независимо в каждый момент с распределением вероятностей на Другими словами имеется множество матриц условных вероятностей

УГ, = {уу(у\хихьз),х1 € Хи Хч €Х2,у€ € 5.

В [331 и [34] доказана следующая теорема, где границы случайного кодирования и сферической упаковки в каждом из пяти рассмотренных случаев принимает различный вид.

Теорема 9.1. При всех Е> О, для канала множественного доступа со случайным параметром имеют место следующие включения

Пг{Е, ИЪ) С ЩЕ, С К,Р(Е, УГВ).

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

Дискретный меняющийся канал называется произвольно меняющимся, если состояние канала 5 принимает в каждый момент времени произвольные значения из множества 5, Исследованию произвольно меняющихся каналов в различных ситуациях посвящен ряд работ, однако, пропускная способность в общем случае до сих пор не найдена. Кроме того, экспоненциальные границы вероятностей ошибок для произвольно меняющихся каналов не были получены. Автором [8], [9] были найдены нижняя и верхняя границы Е-пропускной способности для класса произвольно меняющихся каналов с информированным кодером И^, которые позднее улучшены в работах [26], [27]. Полученные границы верны как для случая средней вероятности ошибки, так и для случая максимальной вероятности ошибки. Граница случайного кодирования в пределе при совпадает с пропускной способностью

канала, найденной Алсведе14.

Заключение

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

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

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

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

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

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

Перечень публикаций по теме диссертации

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

[2] Арутюнян Е. А., Арутюнян М. Е. Верхняя граница Е - пропускной способности дискретного канала со случайными параметрами. Материалы Республ. научно-практич. конференции по методике препод, математики и механики в ВУЗе. Ереван. 1986. С. 53-54.

[3] Арутюнян М. Е. Границы Е-пропускной способности составных каналов. Ученые записки ЕГУ, Естественные науки. 1987. Но. 3(165). С. 22-29.

[4] Haroutunian E. A., Haroutunian M. E. Sphere packing bound for rate-reliability function of the channel with random parameter. Abstracts of conf. Statistical Data Analysis. Sofia. 1987. P. 20-21.

[51 Арутюнян Е. А., Арутюнян М. Е. Теория информации. Учебно-вспомогательное пособие на армянском языке. Ереван. Изд.-во ЕГУ. 1987.

[6] Haroutunian E. A., Haroutunian M. E. л-capacity upper bound for channel with random parameter. Problems of Control and Information Theory. 1988. V. 17. No.2. P. 99-105.

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

[81 Арутюнян М. Е. Лоптимальные коды для произвольно меняющегося канала с информированным кодером. Тезисы докл. IX Всесоюзн.

конф. по теории кодирования и передачи информации. Одесса. 1988. Ч. 1. С. 24-26.

[9] Арутюнян М. Е. E-пропускная способность произвольно меняющегося канала с информированным кодером. Проблемы передачи информации. 1990. Т. 26. Но. 4. С. 16—23.

[10] Арутюнян Е. А., Арутюнян М. Е. Границы достижимых скоростей передачи по каналу с множественным доступом при заданной экспоненте вероятности ошибки. Доклады Академии наук Армении. 1990. Т. 91. Вып. 3. С. 99-104.

{11] Арутюнян М. Е. Границы Е-пропускной способности канала со случайным параметром. Проблемы передачи информации. 1991. Т. 27. Но. 1.С. 14-23.

[12] Арутюнян М. Е. Оценки E-пропускной способности меняющихся каналов, кандидатская диссертация, 1991.

[13] Арутюнян Е. А, Арутюнян М. Е., Марутян Р. Ш. Обзор некоторых исследований по теории информации. Третий международный семинар стран членов СЭВ по статистической теории связи и ее применениям. Варна. София. 1991. С. 5—21.

[14] Арутюнян Е. А, Арутюнян М. Е., Аветисян А. Е. Область достижимых скоростей канала множественного доступа и надежность. Известия Академии наук Армении, серия Математика. 1992. Т. 27. Но. 5. С. 51 - 68.

[15] Haroutunian E. A, Haroutunian M. E. Channel with random parameter. Proc. of XXII Prague conf. on Inform. Theory, Statistical Decision Functions, Rundom Processes. 1994. P. 20.

[16] Haroutunian E. A.f Haroutunian M. E.f Avetissian A. E. Restricted two-way channel: Bounds for achievable rates region for given error probability exponent. Proc. of IEEE International Symposium on Information Theory. Whistler. Canada. 1995. P. 13.

[17] Haroutunian M. E., Haroutunian E. A. An outer bound for E-capacity region of broadcast channel giving a new outer bound for capacity region.' Proc. of IEEE International Symposium on Information Theory. Ulm. Germany. 1997. P. 267.

[181 Haroutunian M. E., Haroutunian E. A. Random coding bound for E-capacity region of general broadcast channel. Proc. of International Conf. on Computer Sciences and Inform. Technologies. Yerevan. Armenia. 1997. P. 211-214.

[19] Арутюнян Е. А., Арутюнян М. Е. Границы области 12-пропускной способности двустороннего канала с ограничениями. Проблемы передачи информации. 1998. Т. 34. Но. 3. С. 7-16.

[20] Арутюнян М. Е. О достижимых скоростях передачи интерференционного канала. Математические вопросы кибернетики и вычислительной техники. 1998. Т. 20. С. 79-89.

[21] Арутюнян М. Е. Об интерференционном канале с коррелированным кодированием. Доклады Национальной академии наук Армении. 1998. Т. 98. Вып. 2. С. 102-107.

[22] Haroutunian М. Е„ Amirbekyan A. H. Random coding bound for incapacity region of the channel with two inputs and two outputs. Trans, of Institute for Informatics and Automation Problems of NAS RA and YSU, Mathematical Problems of Computer Sciences. 1998. V. 20. P. 90-97.

[23] Haroutunian M. E., Random coding bound for incapacity region of general interference channel. Trans, of International conf. on Computer sciences and Information Technologies. Yerevan. Armenia. 1999. P. 127-130.

[24] Haroutunian M. E.f Haroutunian E. A. E-capacity and capacity regions of general broadcast channel. Trans, of International conf. on Computer sciences and Information Technologies. Yerevan. Armenia. 1999. P. 155-158.

[25] Haroutunian M. E. Random coding bound for incapacity region of the broadcast channel. Trans, of Institute for Informatics and Automation Problems of NAS RA and YSU, Mathematical Problems of Computer Sciences. 2000. V. 21. P. 50-60.

[26] Haroutunian M. E. New bounds for incapacities of arbitrarily varying channel and channel with random parameter. Trans, of Institute for Informatics and Automation Problems of NAS RA and YSU, Mathematical Problems of Computer Sciences. 2001. V. 22. P. 44-59.

[27] Haroutunian M. E. Arbitrarily varying and random parameter channels with informed encoder. Proc. of International Conf. on Computer science and Inform. Technologies. Yerevan. Armenia. 2001. P. 207—210.

[28] Haroutunian M. E. Bounds for rate-reliability function of multi-user channels. International Meeting on General Theory of Information Transfer. Bielefeld. Germany. February. 2002. P. 16.

[29] Haroutunian M. E., Haroutunian E. A. E-capacities of varying channels. Opening conference on General Theory of Information Transfer and Combinatorics. Bielefeld. Germany. November. 2002. P. 25.

[30] Haroutunian M. E. New inner bounds of the rate-reliability regions for certain multiple-access channels. Доклады Национальной академии наук Армении. 2002. Т. 102. Вып. 2. С. 113-120.

[31] Арутюнян М. Е. Об области E-пропускной способности канала с множественным доступом. Известия НАН РА "Математика". 2003. Т. 38. Но. 1. С. 3-22.

[32] Haroutunian M. E., Tonoyan S. A. Computation of incapacity and capacity bounds for binary restricted two-way channel. Proc. of International Conf. on Computer science and Inform. Technologies. Yerevan. Armenia. 2003. P. 168-172.

[33] Haroutunian M. E. On multiple-access channel with random parameter. Proc. of International Conf. on Computer science and Inform. Technologies. Yerevan. Armenia. 2003. P. 174-178.

[34] Haroutunian M. E. Bounds of E-capacity for multiple-access channel with random parameter. Trans, of Institute for Informatics and Automation Problems of NAS RA, Mathematical Problems of Computer Sciences. 2005. V. 24. P. 16-35.

Отпечатано в ООО «Компания Спутник+» ПД № 1-00007 от25.09.2000 г. Подписано в печать 19.05.05 Тираж 70 экз. Усл. пл. 1,94 Печать авторефератов (095) 730-47-74,778-45-60

О 9 ИЮЛ 2005 «4 -'^í'íjf*/

/

Обозначения и сокращения

Введение

Глава 1. Основные понятия и постановка проблемы.

1.1. Определения и обозначения мер информации.

1.2. Определения и формулировки метода типов

1.3. Описание дискретного канала без памяти.

1.4. Функция надежности дискретного канала без памяти.

1.5. Е-пропускная способность дискретного канала без памяти.

1.6. Обзор основных результатов диссертации.

Часть 1. Многотерминальные каналы.

Глава 2. Двусторонние каналы.

2.1. Общий двусторонний канал.

2.2. Двусторонний канал с ограничениями.

2.3. Формулировка результатов.

2.4. Доказательство границы сферической упаковки для двустороннего канала с ограничениями.

2.5. Модификация леммы об упаковке.

2.6. Доказательство границы случайного кодирования.

2.7. Пример вычисления границ.

Глава 3. Интерференционные каналы.

3.1. Общий интерференционный канал.

3.2. Формулировка границы случайного кодирования.

3.3. Доказательство теоремы 3.1 для общего интерференционного канала.

3.4. Интерференционный канал с коррелированным кодированием.

3.5. Доказательство теоремы 3.2 для интерференционного канала с коррелированным кодированием.

Глава 4. Широковещательные каналы.

4.1. Общий широковещательный канал.

4.2. Внутренняя граница области Е-пропускной способности

4.3. Доказательство теоремы 4.1.

4.4. Оценки для частных моделей.

Глава 5. Каналы с множественным доступом

5.1. Основные модели.

5.2. Формулировка оценок области Е-пропускной способности для различных моделей.

5.3. Лемма об упаковке для канала с множественным доступом.

5.4. Доказательство внутренней оценки.

Глава б. Канал с двумя входами и двумя выходами

6.1. Основные определения.

6.2. Граница случайного кодирования области Е-пропускной способности.

6.3. Доказательство теоремы 6.1.

6.4. Доказательство леммы об упаковке для случая канала с двумя входами и двумя выходами.

Часть 2. Меняющиеся каналы.

Глава 7. Составной канал

7.1. Описание системы связи.

7.2. Формулировки границ Е-пропускной способности составного канала.

7.3. Вывод границы сферической упаковки.

7.4. Граница случайного кодирования и граница с выбрасыванием.

Глава 8. Канал со случайным параметром

8.1. Информация о канале.

8.2. Формулировка результатов для канала с информированным кодером.

8.3. Доказательство верхней границы.

8.4. Доказательство нижней границы.

8.5. Доказательство леммы 8.1.

8.6. Другие модели канала со случайным параметром.

8.7. Обобщенный канал со случайным параметром.

8.8. Пример.

Глава 9. Канал множественного доступа со случайным параметром

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

9.2. Доказательство внутренней границы для случая 5.

Глава 10. Произвольно меняющийся канал с информированным кодером

10.1. Формулировка результатов.

10.2. Доказательство теоремы 10.1.

Актуальность темы.

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

Для каждого из исследуемых каналов W согласно Шеннону первоочередной теоретико-информационной задачей является нахождение его пропускной способности C(W), которая определяется как верхняя грань скоростей кодов с вероятностью ошибки стремящейся к нулю при увеличении длины кода N. Важные свойства каждой системы передачи информации отражает функция надёжности, введенная (также как и понятие пропускной способности) Шенноном. Эта функция E(R,W) определяется как оптимальный показатель экспоненциального убывания вероятности ошибки при росте длины передачи N в зависимости от скорости передачи 11.

Большое число исследований посвящено изучению функции надёжности различных информационных моделей. Обычно удается построить верхние и нижние границы этой функции. В этом разделе шенноновской теории оптимального кодирования информации для большинства многотерминальных и меняющихся каналов такие оценки не были найдены из-за сложности проблемы. В связи с принципиальной трудностью нахождения функции надёжности для всего диапазона скоростей 0 < R < C{W), полностью эта задача решена лишь в частных случаях. Для однопутевых каналов типична ситуация, когда найденные верхняя и нижняя оценки функции E(R, W) совпадают лишь при скоростях в интервале Rcr < R < C(W), где Rcr — значение скорости, в которой производная E(R, W) по R равна —1.

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

Цель диссертационной работы.

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

Рассмотренные в работе классы каналов находятся в центре внимания исследователей современной теории информации.

Объект исследования.

В данной диссертации объектом исследований являются дискретные многотерминальные и меняющиеся каналы без памяти. Исследуется Е-пропускная способность, которая является оптимальной скоростью кодов, обеспечивающих экспоненциальное убывание по длине кода N вероятности ошибки с заданным показателем (надёжностью) Е. Эта функция С(Е, W) впервые была рассмотрена Е. Арутюняном и является обратной к функции надёжности.

Изучение Е-пропускной способности в некоторых случаях оказывается более удобным. Кроме того, когда надёжность приближается к нулю, Е-пропускная способность сходится к пропускной способности канала, и таким образом, с помощью построения оценок для С(Е, W) можно получить оценки и для пропускной способности C{W). В этом смысле Е-пропускную способность можно рассматривать как обобщение понятия пропускной способности.

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

Методы исследования.

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

В основе метода построения нижних границ /^-пропускной способности лежит подход шенноновского метода случайного кодирования с использованием, так называемой, леммы об упаковке [44]. Этот метод, который ранее применялся для доказательства нижних оценок пропускной способности и функции надёжности дискретного канала без памяти, развит и применен к исследуемым сложным каналам. Имея ввиду способ доказательства, нижние границы называются границами случайного кодирования. Для каждой из рассмотренных в диссертации моделей, приходится доказывать новую модификацию леммы об упаковке и решать проблему нахождения и доказательства нижних границ.

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

Метод разбиения графов, предложенный Чисаром и Кёрнером [98] для построения нижних границ функции надёжности обычного однопутевого канала, модифицирован для доказательства границы случайного кодирования и границы с выбрасыванием /^-пропускной способности составного канала.

Научная новизна.

В диссертации предложена методология изучения оптимальной скорости передачи в зависимости от экспоненциального показателя вероятности ошибки для различных каналов. Методология включает: метод построения нижних границ Е-пропускной способности для меняющихся каналов; метод построения внутренних границ области ^-пропускной способности для многотерминальных каналов; метод построения границы с выбрасыванием Е-пропускной способности для составного канала; метод построения верхних границ Е-пропускной способности для меняющихся каналов; метод построения внешних границ области Е-пропускной способности для многотерминальных каналов.

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

• двустороннего канала с ограничениями, внутренние оценки области /^-пропускной способности для

• общего интерференционного канала,

• интерференционного канала с коррелированным кодированием,

• общего широковещательного канала,

• канала с множественным доступом с коррелированными источниками, а также ряда других моделей КМД,

• канала с двумя входами и двумя выходами. верхние и (или) нижние границы £7-пропускной способности для

• составного канала,

• канала со случайным параметром,

• канала множественного доступа со случайным параметром,

• произвольно меняющегося канала с информированным кодером.

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

Достоверность и обоснованность.

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

Теоретическая и практическая значимость полученных результатов.

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

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

Апробация работы. Основные результаты диссертации докладывались на IX симпозиуме по проблеме избыточности в информационных системах (Ленинград, 1986), Республиканской научно-практической конференции по методике преподавания математики и механики в ВУЗе (Ереван 1986), Международном семинаре по анализу статистических данных (София 1987), IX всесоюзной конференции по теории кодирования и передачи информации (Одесса, 1988), III Международном семинаре стран членов СЭВ по статистической теории связи и её применениям (Варна, 1988), IV международном коллоквиуме по теории кодирования (Дилижан, 1991), XXII пражской конференции по теории информации, статистическим решающим функциям и случайным процессам (Прага, 1994). Международных симпозиумах по теории информации (Вистлер, 1995, Ульм, 1997), 7-ой совместной шведско-российской международной конференции по теории информации (Санкт-Петербург, 1995), Международных конференциях по компьютерным наукам и информационным технологиям (Ереван, 1997, 1999, 2001, 2003), Международных встречах по общей теории информационной связи (Билефельд, февраль, ноябрь, 2002), на заседании семинара группы стохастической обработки изображений Женевского университета (Женева, 2005), на заседаниях семинаров по теории информации в ИППИ РАН, в Ереванском государственном университете, в ИПИА НАН РА, в Институте математики НАН РА.

Заключение

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

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

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

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

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

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

2. Арутюнян Е. А. Оценки экспоненты вероятности ошибки для полунепрерывного канала без памяти. Проблемы передачи информации. 1968. Т. 4. Но. 4. С. 37 — 48.

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

4. Арутюнян Е. А. Нижняя граница вероятности ошибки для каналов со многими передающими сторонами. Проблемы передачи информации. 1975. Т. 11. Но. 2. С. 23 — 36.

5. Арутюнян Е. А. Нижняя граница для вероятности ошибки в каналах с обратной связью. Проблемы передачи информации.1977. Т. 13. Но. 2. С. 36-44.

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

7. Арутюнян Е. А. Скорость как функция надежности при оптимальной передаче информации. Докторская дис. 1991.

8. Арутюнян Е., Казанчян Т., Месропян Н., Асатрян Д., Арутюнян М. и др. Вероятность и прикладная статистика. Учебник и задачник на армянском языке. Ереван, изд.-во Гитутюн. 2000.

9. Бассалыго Л. А. Оценка допустимых скоростей передачи в широковещательном канале с ошибками в обеих компонентах. Проблемы передачи информации. 1981. Т. 17. Но. 4. С. 19—28.

10. Бассалыго Л. А., Пинскер М. С. Границы мощности кодов, исправляющих ошибки в широковещательном канале (обобщенный канал Блекуэлла). Проблемы передачи информации. 1980. Т. 16. Но. 3. С. 3—16.

11. Бассалыго Л. А., Пинскер М. С., Прелов В. В. Пропускная способность при нулевой ошибке и наличии общей информации для детерминированных каналов с множественным доступом. Проблемы передачи информации. 1982. Т. 18. Но. 1. С. 3—11.

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

13. Галлагер Р. Г. Пропускная способность и кодирование для некоторых широковещательных каналов. Проблемы передачи информации. 1974. Т. 10. Но. 3. С. 3—14.

14. Гельфанд С. И. Пропускная способность одного широковещательного канала. Проблемы передачи информации. 1977. Т. 13. Но. 3, С. 106-108.

15. Гельфанд С. И., Пинскер М. С. Пропускная способность широковещательного канала с одной детерминированной компонентой. Проблемы передачи информации. 1980. Т. 16. Но. 1. С. 24 — 34.

16. Гельфанд С. И., Прелов В. В. Связь с многими пользователями. Итоги науки и техники. Теория вероятностей, математическая статистика. Техническая кибернетика. М. ВИНИТИ. 1978. Т. 15. С. 123-162.

17. Добрушин Р. Л. Передача информации по каналу с обратной связью. Теория вероятности и ее применения. 1958. Т. 34. Но. 4. С. 395-412.

18. Добрушин Р. Л. Оптимальная передача информации по каналу с неизвестными параметрами. Радиотехника и Электро1шка. Т. 4, С. 1951-1956, 1959.

19. Добрушин Р. Л. Общая формулировка основной теоремы Шеннона в теории информации. Успехи математических наук. 1959. Т. 14. Но. 6. С. 3-104.

20. Добрушин Р. Л. Математические вопросы шенноновской теории оптимального кодирования информации. Проблемы передачи информации. 1961. Но. 10. С. 63 — 107.

21. Добрушин Р. Л. Асимптотическая оценка вероятности ошибки при передаче сообщения по каналу без памяти с использованием обратной связи. Проблемы киберн. 1962. Вып. 3, С. 161 — 168.

22. Добрушин Р. Л. Асимптотическая оценка вероятности ошибки при передаче сообщения по дискретному каналу связи без памяти с симметрической матрицей вероятностей перехода. Теория вероятности и ее примен. 1962. Т. 7. Но. 3. С. 283 — 311.

23. Добрушин Р. Л., Стамблер С. 3. Теоремы кодирования для некоторых классов произвольно меняющихся дискретных каналов без памяти. Проблемы передачи информации. 1975. Т. 11. Но. 2. С. 3-22.

24. Дьячков А. Г. Верхние границы для вероятности ошибки при передаче с обратной связью в случае дискретных каналов без памяти. Проблемы передачи информации. 1975. Т. 11. Но. 4. С. 13-28.

25. Дьячков А. Г. Границы вероятности ошибки для некоторых ансамблей случайных кодов. Проблемы передачи информации. 1979. Т. 15. Но. 2. С. 23-35.

26. Дьячков А. Г. Границы средней вероятности ошибки для ансамбля кодов с фиксированной композицией. Проблемы передачи информации. 1980. Т. 16. Но. 4. С. 3 — 8.

27. Дьячков А Г. Нижняя граница средней по ансамблю вероятности ошибки для дискретного канала без памяти. Проблемы передачи информации. 1980. Т. 16. Но. 2. С. 18-24.

28. Дьячков А. Г. Нижняя граница средней по ансамблю вероятности ошибки для канала множественного доступа. Проблемы передачи информации. 1986. Т. 22. Но. 1. С. 98—103.

29. Дьячков А. Г., Рыков В. В. Об одной модели кодирования для суммирующего канала с множественным доступом. Проблемы передачи информации. 1981. Т. 17. Но. 2. С. 26 — 38.

30. Дьячков А. Г., Рыков В. В. Улучшение нижней границы длины кодов для суммирующего канала с множественным доступом. Проблемы передачи информации. 1983. Т. 19. Но. 4. С. 103— 105.

31. Колесник В. Д., Полтырев Г. Ш. Курс теории информации. Москва. Наука. 1982.

32. Кудряшов Б. Д., Полтырев Г. Ш. Верхние границы для вероятности ошибок декодирования в некоторых широковещательных каналах. Проблемы передачи информации. 1979. Т. 15. Но. 3. С. 3-17.

33. Кузнецов А. В., Цыбаков Б. С. Кодирование в памяти с дефектными ячейками. Проблемы передачи информации. 1974. Т. 10. Но. 2. С. 52-60.

34. Кульбак С. Теория информации и статистика. Москва. Наука. 1967.

35. Пинскер М. С. Пропускная способность широковещательных каналов без шумов. Проблемы передачи информации. 1978. Т. 14. Но. 2. С. 28-32.

36. Полтырев Г. Ш. Пропускная способность для параллельных широковещательных каналов с ухудшающимися компонентами. Проблемы передачи информации, 1977. Т. 13. Но. 2. С. 23 — 35.

37. Полтырев Г. Ш. Пропускная способность для суммы некоторых широковещательных каналов. Проблемы передачи информации, 1979. Т. 15. Но. 2. С. 40-44.

38. Полтырев Г. Ш. Границы случайного кодирования для дискретных каналов без памяти. Проблемы передачи информации, 1982. Т. 18. Но. 1. С. 12-26.

39. Полтырев Г. Ш. О точности границ случайного кодирования для широковещательных каналов. Проблемы управления и теории информации, 1982. Т. 11. Но. 5. С. 353-364.

40. Полтьгрев Г. Ш. Границы случайного кодирования для некоторых широковещательных каналов. Проблемы передачи информации, 1983. Т. 19. Но. 1. С. 9-20.

41. Прелов В. В. Передача информации по каналу с множественным доступом при специальной иерархии источников. Проблемы передачи информации, 1984. Т. 20. Но. 4. С. 3—10.

42. Файнстейн А. Основы теории информации, Москва, Иностр. литерарура, I960.

43. Фано Р. Передача информации. Статистическая теория связи, Москва, Мир, 1965.

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

45. Эль Гамаль А. А. Пропускная способность произведения и суммы двух несогласованных широковещательных каналов. Проблемы передачи информации, 1980. Т. 16. Но. 1. С. 3 — 23.

46. Ahlswede R. F. On two-way communication channels and a problem by Zarankiewicz. Trans. 6th Prague Conference on Inform. Theory, Statistical Decision Functions, Random Processes. Prague. 1971. P. 23-37.

47. Ahlswede R. F. Multy-way communication channels. Proc. of 2nd Intern. Sympos. Inform. Theory. Tsahkadsor, Armenia, 1971, Budapest: Akad. Kiado. 1973. P. 23-52.

48. Ahlswede R. F. The capacity region of a channel with two senders and two receivers. Ann. Probability, 1974. V. 2. No. 2. P. 805-814.

49. Ahlswede R. F. Elimination of correlation in random codes for arbitrarily varying channels. Zeitschrift fur Wahrscheinlichkeitsth. Verwandte Gebiete, 1978. V. 33. P. 159-175.

50. Ahlswede R. F. A method of coding and an application to arbitrarily varying channels. Journal of Combinatorics, Information and System Sciences, 1980. V. 5. P. 10-35.

51. Ahlswede R. F. An elementary proof of the strong converse theorem for the multiple-access channel. Journal of Combinatorics, Information and System Sciences, 1982. V. 7. No. 3. P. 216 — 230.

52. Ahlswede R. F. Arbitrarily varying channels with states sequence known to the sender. IEEE Transactions on Information Theory, 1986. V. 32. No. 5. P. 621 -629.

53. Ahlswede R. F. Eight problems in information theory" in "Open Problems in Comunication and Computation. Т. M. Cover and B. Gopinath Editors, Springer Verlag, 1987.

54. Ahlswede R. F. The maximal error capacity of arbitrarily varying channels for constant list sizes. IEEE Transactions on Information Theory, 1993. V. 39. P. 1416-1417.

55. Ahlswede R. F.( Wolfowitz J. Correlated decoding for channels with arbitrarily varying channel probability functions. Information and Control, 1969. V. 14. No. 5. P. 457-473.

56. Ahlswede R. F.r Wolfowitz J. The capacity of a channel with arbitrarily varying channel probability functions and binary output alphabet. Zeitschrift fiir Wahrscheinlichkcitsth. Verwandte Gebiete, 1970. V. 15. No. 3. P. 186- 194.

57. Ahlswede R. F.( Korner J. Source coding with side information and a converse for degraded broadcast channels. IEEE Transactions on Information Theory, 1975. V. 21. P. 629-637.

58. Ahlswede R. F., Han T. S. On source coding with side information via a multiple-access channel and related problems in multi-user information theory. IEEE Transactions on Information Theory, 1983. V. 29. No. 3. P. 396-412.

59. Ahlswede R. F., Cai N. Two proofs of Pinsker's conjecture concerning arbitrarily varying channels. IEEE Transactions on Information Theory, 1991. V. 37. P. 1647-1649.

60. Ahlswede R. F., Cai N. Correlated sources help transmission over an arbitrarily varying channel. IEEE Transactions on Information Theory, 1997. V. 43. No. 4. P. 1254- 1255.

61. Ahlswede R. F., Cai N. Arbitrarily varying multiple access channels. Part 1, IEEE Trans. Inform. Theory, 1999. V. IT-45. No. 2. P. 742749.

62. Ahlswede R. F.( Cai N. Arbitrarily varying multiple access channels. Part 2, IEEE Trans. Inform. Theory, 1999. V. IT-45. No. 2. P. 749756.

63. Ahlswede R. F., Cai N. Information and control: matching channels.

64. EE Transactions on Information Theory, 1998. V. 44. No. 2, P. 542-563.

65. Ahlswede R. F., Cai N. Seminoisy deterministic multiple-access channels: coding theorems for list codes and codes with feedback.

66. EE Transactions on Information Theory, 2002. V. 48. P. 21532162.

67. Ahlswede R. F.( Csiszar I. Common randomness in information theory and cryptography. P. 1 Secret sharing. IEEE Transactions on Information Theory, 1993. V. 39. No. 4. P. 1121 -1132.

68. Ahlswede R. F., Csiszar I. Common randomness in information theory and cryptography. P.2 CR capacity. IEEE Transactions on Information Theory, 1998. V. 44. No. 1. P. 55-62.

69. Ahlswede R. F., Gacs P., Korner J. Bounds on conditional probabilities with applications in multi-user communication. Zeitschrift fur Wahrscheinlichkeitsth. Vcrwandte Gebiete, 1976. V. 34. P. 157—177.

70. Ahlswede R. F., Cai NM Zhang Z. Zero-error capacity for models with memory and the enlightened dictator channel. IEEE Transactions on Information Theory, 1998. V. 44. No. 3. P. 1250-1252.

71. Balakirsky V. В. A converse coding theorem for mismatched decoding at the output of binary-input memoryless channels. IEEE Transactions on Information Theory, 1995. V. 41. P. 1889— 1902.

72. Bergmans P. P. A simple converse for broadcast channels with additive white Gaussian noise. IEEE Transactions on Information Theory, 1974. V. 20. No. 2. P. 279-280.

73. Bergmans P. P. The Gaussian interference channel. IEEE Intern. Symp. Infrom. Theory, Ronneby, Sweden, 1976.

74. Bierbaum M., Wallmeier H. A note on the capacity region of the multiple-access channel. IEEE Transactions on Information Theory, 1979. V. 25. No. 4, P. 484.

75. Blackwell D., Breiman L., Thomasian A. J. The capacity of a class of channels. Annals of Mathem. Statist., 1959. V. 30. No. 4. P. 12291241.

76. Blahut R. E. Computation of channel capacity and rate distortion functions. IEEE Transactions on Information Theory, 1972. V. 18. P. 460-473.

77. Blahut R. E. Hypothesis testing and information theory. IEEE Transactions on Information Theory, 1974. V. 20. P. 405 — 417.

78. Blahut R. E. Composition bounds for channel block codes. IEEE Transactions on Information Theory, 1977. V. 23. P. 656 — 674.

79. Blahut R. E. Principles and Practice of Information Theory. Addison-Wesley, Reading, MA, 1987.

80. Blinovsky V., Narayan P., Pinsker M. Capacity of the arbitrarily varying channel under list decoding. Problemi Peredachi Informatcii, 1995. V. 31. P. 99-113.

81. Carleial A B. A case where interference does not reduce capacity. IEEE Transactions on Information Theory, 1975. V. 21. P. 569-570.

82. Carleial A. B. Interference channels. IEEE 'Transactions on Information Theory, 1978. V. 24. No. 1. P. 60-70.

83. Carleial A. B. Outer bounds on the capacity of interference channels. IEEE Transactions on Information Theory, 1983. V. 29. No. 4. P. 602-604.

84. Cohen A., Lapidoth A. The Gaussian watermarking game. Preprint, 2001.

85. Costa M. H. М.( Gamal A. El The capacity region of the discrete memoryless interference channel with strong interference. IEEE Transactions on Information Theory, 1987. V. 33. P. 710 — 711.

86. Cover Т. M. Broadcast channels. IEEE Transactions on Information Theory, 1972. V. 18. P. 2 14.

87. Cover Т. M. An achievable rate region for the broadcast channel. IEEE Transactions on Information Theory, 1975. V. 21. P. 399-404.

88. Cover Т. M. Some advances in broadcast channels, in Advances in Communication Systems. V. 4, A. Viterbi, Ed. San Francisco: Academic Press, 1975.

89. Cover Т. M. Comments on broadcast channels. IEEE Transactions on Information Theory, 1998. V. 44. P. 2524-2530.

90. Cover Т. M., El Gamal A., Salehi M. Multiple access channels with arbitrarily correlated sources. IEEE Transactions on Information Theory, 1980. V. 26. No. 6. P. 648-657.

91. Cover Т. M., Mceliece R. G., Posner E. C. Asynchronous multiple-access channel capacity. IEEE Transactions on Information Theory, 1981. V. 27. No. 4. P. 409-413.

92. Cover Т. M., Leung C. S. An achievable rate region for the multiple-access channel with feedback. IEEE Transactions on Information Theory, 1981. V. 27. No. 3. P. 292-298.

93. Cover Т. Мм Thomas J. A. Elements of Information Theory. Wiley, 1991.

94. Csiszar I. Joint source-channel error exponent. Problems of Control and Information Theory, 1980. V. 9. No. 5. P. 315-328.

95. Csiszar I. Arbitrarily varying channels with general alphabets and states. IEEE Transactions on Information Theory, 1992. V. 38. P. 1725-1742.

96. Csiszar I. The method of types. IEEE Transactions on Information Theory, 1998. V. 44. No. 6. P. 2505-2523.

97. Csiszar I., Korner J. Broadcast channels with confidential messages. IEEE Transactions on Information Theory, 1978. V. 24, P. 339-348.

98. Csiszar I., Korner J. Graph decomposition: A new key to coding theorems. IEEE Transactions on Information Theory, 1981. V. 27. No. 1. P. 5-12.

99. Csiszar I., Korner J. On the capacity of the arbitrarily varying channel for maximum probability of error. Zeitschrift fur Wahrscheinlichkeit-sth. Verwandte Gebiete, 1981. V. 57. P. 87-101.

100. Csiszar I., Korner J. Feedback does not affect the reliability function of a discrete memoryless channel at rates above capacity. IEEE Transactions on Information Theory, 1982. V. 28. No. 1. P. 92 — 93.

101. Csiszar I., Korner J., Marton K. A new look at the error exponent of a discrete memoryless channel. IEEE International Symp. on Information Theory, Cornell Univ., Ithaca, N.Y., 1977.

102. Csiszar I., Narayan P. The capacity of arbitrarily varying channel revisited: Positivity, constraints. IEEE Transactions on Information Theory, 1988. V. 34. P. 181-193.

103. Csiszar I., Narayan P. Capacity and decoding rules for arbitrarily varying channels. IEEE Transactions on Information Theory, 1989. V. 35. P. 752-769.

104. Csiszar I., Narayan P. Capacity of the Gaussian arbitrarily varying channel. IEEE Transactions on Information Theory, 1991. V. 37. P. 18-26.

105. Csiszar I., Narayan P. Channel capacity for a given decoding metric. IEEE Transactions on Information Theory, 1995. V. 41. P. 35 — 43.

106. Das A., Narayan P. Capacities of time-varying multiple-access channels with side information. IEEE Transactions on Information Theory, 2002. V. 48. No. 1. P. 4-25.

107. De Bruyn K., Prelov V. V., van der Meulen E. C. Reliable transmission of two correlated sources over an asymmetric multiple access channel. IEEE Transactions on Information Theory, 1987. V. 33. No. 5. P. 716-718.

108. Dobrushin R. L. Survey of Soviet research in information theory. IEEE Transactions on Information Theory, 1972. V. 18. P. 703 — 724.

109. Dueck G. Maximal error capacity regions are smaller than average error capacity regions for multi-user channels. Problems of Control and Information Theory, 1978. V. 7. No. 1. P. 11 -19.

110. Dueck G. The capacity region of two-way channel can exceed the inner bound. Information and Control, 1979. V. 40. No. 3. P. 258 — 266.

111. Dueck G. Partial feedback for two-way and broadcast channels. Information and Control, 1980. V. 46. No. 1. P. 1 — 15.

112. Dueck G. The strong converse of the coding theorem for the multiple-access channel. Journal of Combinatorics, Information and System Sciences, 1981. V. 6. No. 3. P. 187-196.

113. Dueck G. A note on the multiple access channel with correlated sources. IEEE Transactions on Information Theory, 1981. V. 27. No. 2. P. 232-235.

114. Dueck G.( Korner J. Reliability function of a discrete memoryless channel at rates above capacity. IEEE Transactions on Information Theory, 1979. V. 25. No. 1. P. 82-85.

115. Dyachkov A. G. Random constant composition codes for multiple access channels. Problems of Control and Information Theory, 1984. V. 13. No. 6. P. 357-369.

116. El Gamal A. The feedback capacity of degraded broadcast channel. IEEE Transactions on Information Theory, 1978. V. 24, P. 379 — 381.

117. El Gamal A. The capacity of a class of broadcast channels. IEEE Transactions on Information Theory, 1979. V. 25. P. 166—169.

118. El Gamal A. The capacity of the physically degraded Gaussian broadcast channel with feedback. IEEE Transactions on Information Theory, 1981. V. 27. P. 508.

119. El Gamal A., M. N. Costa The capacity region of a class of deterministic interference channel. IEEE Transactions on Information Theory. V. 28. No. 2. P. 343-346, 1982.

120. Elias P. Coding for noisy channels. IRE Convention Record, 1955, part 4. P. 37-46.

121. Ericson T. Exponential error bounds for random codes in the arbitrarily varying channels. IEEE Transactions on Information Theory, 1985. V. 31. P. 42-48.

122. Feinstein A. A new basic theorem of information theory. IRE

123. Transactions on Information Theory, 1954. V. 4. P. 2 — 22.

124. Forney G. D. Exponential error bounds for erasure, list and decision feedback schemes. IRE Transactions on Information Theory, 1968, 11. P. 549-557.

125. Gaarder N. Т., Wolf J. K. The capacity region of a multiple access discrete memoryless channel can increase with feedback. IEEE Transactions on Information Theory, 1975. V. 21, P. 100— 102.

126. Gacs P., Korner J. Common information is much less than mutual information. Problems of Control and Information Theorey, 1973. V. 2. No. 2. P. 149-162.

127. Gallager R. G. A simple derivation of the coding theorems and some applications. IEEE Transactions on Information Theory, 1965. V. 11. No. 1. P. 3-18.

128. Gallager R. G. The random coding bound is tight for the average code. IEEE Transactions on Information Theory, 1973. V. 19. No. 2. P. 244-246.

129. Gallager R. G. A perspective on multiaccess channels. IEEE Transactions on Information Theory, 1985. V. 31. No. 1. P. 124— 142.

130. Gelfand S. I., Pinsker M. S. Coding for channel with random parameters. Problems of Control and Information Theory, 1980. V. 8. No. 1. P. 19-31.

131. Gubner J. A. On the deterministic-code capacity of the multiple-access arbitrarily varying channel. IEEE Transactions on Information Theory, 1990. V. 36, P. 262-275.

132. Hajek В. E., Pursley M. B. Evaluation of an achievable rate region for the broadcast channel. IEEE Transactions on Information Theory, 1979. V. 25. P. 36-46.

133. Han T. S. The capacity region of general multiple-access channel with certain correlated sources. Information and Control, 1979. V. 40. No. 1. P. 37-60.

134. Han T. S. Slepian-Wolf-Cover theorem for networks of channels. Information and Control, 1980. V. 47. No. 1. P. 67-83.

135. Han T. S. The capacity region for the deterministic broadcast channel with a common message. IEEE Transactions on Information Theory, 1981. V. 27. P. 122-125.

136. Han T. S. A general coding scheme for the two-way channels. IEEE Transactions on Information Theory, 1984. V. 30. No. 1. P. 35 — 44.

137. Han T. S., Kobayashi K. A new achievable rate region for the interference channel. IEEE Transactions on Information Theory, 1981. V. 27. No. 1, P. 49-60.

138. Han T. S., Costa M. H. M. Broadcast channels with arbitrarily correlated sources. IEEE Transactions on Information Theory, 1987. V. 33, P. 641-650.

139. Han Т. S., Verdu S. A general formula for channel capacity. IEEE Transactions on Information Theory, 1994. V. 40. No. 4, P. 1147 — 1157.

140. Hekstra A S. , Willems F. M. J. Dependence balance bounds for single-output two-way channel. IEEE Transactions on Information Theory, 1989. V. 35. No. 1. P. 44-53.

141. Hughes B. L. The smallest list for the arbitrarily varying channel. IEEE Transactions on Information Theory, 1997. V. 43, P. 803 — 815.

142. Hughes B. L., Thomas T. G. On error exponents for arbitrarily varying channels. IEEE Transactions on Information Theory, 1996. V. 42, no. 1. P. 87-98.

143. J. Y. N. Hui , Humblet P. A. The capacity region of the totally asynchronous multiple access channel. IEEE Transactions on Information Theory, 1985. V. 31, P. 207-216.

144. Jahn J. H. Coding for arbitrarily varying multiuser channels. IEEE Transactions on Information Theory., 1981 V. 27, P. 212 — 226.

145. Jelinek F. Evaluation of expurgated bound exponents. IEEE Transactions on Information Theory, 1968. V. 14, P. 501—505.

146. Kasami Т., Lin S., Wei V. K., Yamamura S. Coding for the binary symmetric broadcast channel with two receivers. IEEE Transactions on Information Theory, 1985. V. 31, P. 616-625.

147. Kiefer J., Wolfowitz J. Channels with arbitrarily varying channel probability functions. Information and Control, 1962. V. 5. P. 44 — 54.

148. Korner J. Some methods in multi-user communications: a tutorial survey. Inform. Theory. New trends and open problems. CISM Courses and Lectures no. 219, Springer Verlag. P. 173—224, 1975.

149. Korner J. , Marton K. Images of a set via two channels and their role in multi-user communication. IEEE Transactions on Information Theory, 1977. V. 23. P. 751-761.

150. Korner J. , Marton K. General broadcast channels with degraded message sets. IEEE 'Transactions on Information Theory, 1977. V. 23. P. 60-64.

151. Korner J. , Sgarro A. Universally attainable error exponents for broadcast channels with degraded message sets. IEEE Transactions on Information Theory, 1980. V. 26. P. 670-679.

152. Lapidoth A. On the reliability function of the ideal Poisson channel with noiseless feedback. IEEE Transactions on Information Theory, 1993. V. 39. P. 491-503.

153. Lapidoth A Mismatched decoding and the multiple-access channel. IEEE Transactions on Information Theory, 1996. V. 42. P. 1439 — 1452.

154. Lapidoth A., Shamai S. The Poisson multiple-access channel. IEEE Transactions on Information Theory, 1998. V. 44. No. 2, P. 488 — 501.

155. Leighton W. J., Tan H. H. Capacity region of degraded broadcast channels with feedback. Information Sciences, 1977. V. 13. No. 2. P. 167-177.

156. Leung C. On the capacity of an n-receiver broadcast channel with partial feedback. Trans, of IEEE International Symposium on Information Theory, 1981, Santa Monica, CA, p. 27.

157. Liao H. H. J. Multiple access channels. P.h.D. dissertation, University of Hawaii, Department of Electrical Engineering, 1972.

158. Liu Y. S., Hughes B. L. A new universal coding bound for the multiple-access channel. IEEE Transactions on Information Theory, 1996. V. 42. No. 2. P. 376-386.

159. Marton K. The capacity region of deterministic broadcast channels.

160. Trans, of IEEE International Symposium on Information Theory, Paris-Cachan, France, 1977.

161. Marton K. A coding theorem for the discrete memoryless broadcast channel. IEEE Transactions on Information Theory, 1979. V. 25. P. 306-311.

162. MerhavN., Kaplan G., Lapidoth A., Shamai S. (Shitz) On information rates for mismatched decoders. IEEE Transactions on Information Theory, 1994. V. 40. No. 6. P. 1953-1967.

163. Moulin P., O'Sullivan J. A. Information theoretic analysis of information hiding. IEEE Transactions on Information Theory, 2003. V. 49. No. 3. P. 563-593. .

164. Narayan P., Snyder D. L. The two-user cutoff rate for an asynchronous and a synchronous multiple-access channel are the same. IEEE Transactions on Information Theory, 1984. V. 27, P. 667 — 671.

165. Ozarow L. H., Leung-Yan-Cheong S. K. An achievable region and outer bound for the Gaussian broadcast channel with feedback. IEEE Transactions on Information Theory, 1981. V. 30. No. 4, P. 414 — 419.

166. Pinsker M. S. Multi-user channels. II Joint Swedish-Soviet Intern, workshop on Inform. Theory, 1985, GrSnna, Sweden. P. 160—165.

167. Pippenger N. Bounds on the performance of protocols for multiple-access broadcast channel. IEEE Transactions on Information Theory, 1981. V. 27, P. 145-151.

168. Pokorny J., Wallmeier H. M. Random coding bound and codes produced by permutations for the multiple-access channel. IEEE Transactions on Information Theory, 1985. V. 31, P. 741—750.

169. Prelov V. V. On the capacity and zero-error capacity of certain multiple access channels. 9th Prague Conf. on Inform. Theorey, Statist. Decis. Funct. and Random Process Abstracts, 1982.

170. Sato H. Two-user communication channels. IEEE Transactions on Information Theory, 1977. V. 23. No. 3. P. 295-304.

171. Sato H. On degraded Gaussian two-user channels. IEEE Transactions on Information Theory, 1978. V. 24. P. 637.

172. Sato H. On the capacity region of a discrete two-user channel for strong interference. IEEE Transactions on Information Theory, 1978, V. 24. No. 3. P. 377-379.

173. Sato H. An outer bound to the capacity region of broadcast channel. IEEE Transactions on Inform. Theory, 1979. V. 24. No. 3. P.374-377.

174. Sato H. The capacity of the Gaussian interference channel under strong interference. IEEE Transactions on Information Theory, 1981, V. 27, P. 786-788.

175. Shannon С. E. A mathematical theory of communication. Bell System Tech. J., 1948. V. 27. No. 3. P. 379-423. No. 4. P. 623-656.

176. Shannon С. E. Communication in the presence of noise. Proc. IRE, 1949. V. 37. P. 10-21.

177. Shannon С. E. The zero-error capacity of a noisy channel. IRE

178. Transactions on Information Theory, 1956. V. 2. No. 1. P. 8—19.

179. Shannon С. E. Certain results in coding theory for noisy channels. Information and Control, 1957. V. 1. No. 1. P. 6 — 25.

180. Shannon С. E. Channel with side information at the transmitter. IBM Res. Developm., 1958. V. 2. No. 4. P. 289-293.

181. Shannon С. E. Probability of error for optimal codes in a Gaussian channel. Bell System Tech. J., 1959. V. 38. No. 5. P. 611-656.

182. Shannon С. E. Coding theorems for a discrete source with a fidelity-criterion. IRE National convention record, 1959, part 4. P. 142 — 163.

183. Shannon С. E. Two-way communication channels. Proc. 4th Berkeley Sympos. Math. Statist and Probability. Berkeley: Univ. of Calif. Press, 1961, V. 1. P. 611-644.

184. Shannon С. E. , Gallager R. G., Berlekamp E. R. Lower bounds to error probability for coding in discrete memoryless channel. Information and Control, 1967. V. 10. No. 1. P. 65-103. No. 2. P. 522-552.

185. Sharma B. D., Priya V. On broadcast channels with side informationtunder fidelity criteria. Kybernetika, 1983. V. 19. No. 1. P. 27-41.

186. Slepian D., Wolf J. K. Noiseless coding of correlated information sources. IEEE Transactions on Information Theory, 1973. V. 19. No. 7, P. 471-480.

187. Slepian D., Wolf J. K. A coding theorem for multiple access channels with correlated sources. Bell System Techn. J., 1973. V. 52. P. 1037 — 1076.

188. Somekh-Baruch A., Merhav N. On the error exponent and capacity games of private watermarking systems. IEEE Transactions on Information Theory, 2003. V. 49. No. 3. P. 537-562.

189. Steinberg Y. Resolvability theory for the multiple-access channel. IEEE Transactions on Information Theory, 1998. V. 44. No. 2, P. 472-487.

190. Steinberg Y. On the broadcast channel with random parameter. Proc. of International symposium on Information Theory, 2002, Lausanne, Switzerland.

191. Steinberg Y., Merhav N. Identification in the presence of side information with application to watermarking. IEEE Transactions on Information Theory, 2001. V. 47, P. 1410- 1422.

192. Tan H. H. Two-user interference channels with correlated information sources. Information and Control, 1980. V. 44. No. 1, P. 77— 104.

193. Ulrey M. L. The capacity region of a channel with s senders and r receivers. Information and Control, 1975. V. 29. P. 185 — 203.

194. Van der Meulen E. C. The discrete memoryless channel with two senders and one receiver. Proc. of second International Symposium on Information Theory, 1971, Tsahkadsor, Armenia , 1973, Budapest: Akad. Kiado. P. 103-135.

195. Van der Meulen E. C. On a problem by Ahlswede regarding the capacity region of certain multiway channels. Information and Control, 1974. V. 25. P. 351 -356.

196. Van der Meulen E. C. Random coding theorems for the general discrete memoryless broadcast channel. IEEE Transactions on Information Theory, 1975. V. 21, P. 180- 190.

197. Van der Meulen E. C. A Survey of multi-way channels in information theory: 1961 — 1976. IEEE Transactions on Information Theory, 1977. V. 23. no. 1. P. 1-37.

198. Van der Meulen E. C. Recent coding theorems for multi-way channels. Part II: The multiple access channel (1976-1985). Department Wiskunde, Katholieke Universiteit Leuven, Belgium, 1985.

199. Van der Meulen E. C. Some recent results on the asymmetric multiple-access channel. Proc. 2nd Joint Swedish-Soviet Intern. Workshop on Inform. Theory, 1985, Granna, Sweden. P. 172—176.

200. Van Dijk M. On a special class of broadcast channels with confidential messages. IEEE Transactions on Information Theory, 1997, V. 43, P. 712-714.

201. Verboven В., Van der Meulen E. C. Capacity bounds for identification via broadcast channels that are optimal for the deterministicbroadcast channel. IEEE Transactions on Information Theory, 1990, V. 36. P. 1197-1205.

202. Verdu S. Multiple-access channel with memory with and without frame synchronism. IEEE Transactions on Information Theory, 1989, V. 35. No. 3, P. 605-619.

203. Willems F. M. J. The feedback capacity region of a class of discrete memoryless multiple access channels. IEEE Transactions on Information Theory, 1982. V. 28. No. 1. P. 93-95.

204. Willems F. M. J. Informationtheoretical results for the discrete memoryless multiple access channel. P.h.D. dissertation, Katholieke university, Leuven, 156 p., 1982.

205. Willems F. M. J. The discrete memoryless multiple access channel with partially cooperating encoders. IEEE Transactions on Information Theory, 1983. V. 29. No. 3. P.441 -445.

206. Willems F. M. J. The maximal-error and average-error capacity region of the broadcast channel are identical. Problems of Control and Information Theory, 1990, V. 19. No. 4. P. 339-347.

207. Willems F. M. J. , Van der Meulen E. C. The discrete memoryless multiple-access channel with cribbing encoders. IEEE Transactions on Information Theory, 1985. V. 31. No. 3. P.313-327.

208. Wolfowitz J. Simultaneous channels. Arch. Rational Mech. Anal., 1960. V. 4. No. 4. P. 371-386.

209. Wolfowitz J. Coding theorems of information theory, Springer, Berlin-Heidelberg, 3rd edition, 1978.

210. Wyner A. Recent results in the Shannon theory. IEEE Transactions on Information Theory, 1974. V. 20. P. 2—10.

211. Wyner A. On source coding with side information at the decoder. IEEE Transactions on Information Theory, 1975. V. 21. P. 294-300.

212. Zhang Z., Berger Т., Schalkwijk J. P. M. New outer bounds to capacity regions of two-way channels. IEEE Transactions on Information Theory, 1986. V. 32. no. 3. P. 383 — 386.

213. Арутюнян M. E. Границы ^-пропускной способности для составных каналов. IX симпозиум по проблеме избыточности в информ. системах. Тез. докл. Ленинград. 1986. Т. 1. С. 23 — 25.

214. Арутюнян Е. А., Арутюнян М. Е. Верхняя граница Е пропускной способности дискретного канала со случайными параметрами. Материалы Республ. научно-практич. конференции по методике препод, математики и механики в ВУЗе. Ереван. 1986. С. 53-54.

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

216. Haroutunian E. A., Haroutunian M. E. Sphere packing bound for rate- reliability function of the channel with random parameter. Abstracts of conf. Statistical Data Analysis. Sofia. 1987. P. 20-21.

217. Арутюнян E. А., Арутюнян M. E. Теория информации. Учебно-вспомогательное пособие на армянском языке. Ереван. Изд.-во ЕГУ. 1987.

218. Haroutunian Е. A., Haroutunian М. Е. incapacity upper bound for channel with random parameter. Problems of Control and Information Theory. 1988. V. 17. No.2. P. 99-105.

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

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

221. Арутюнян М. Е. ^-пропускная способность произвольно меняющегося канала с информированным кодером. Проблемы передачи информации. 1990. Т. 26. Но. 4. С. 16 — 23.

222. Арутюнян Е. А., Арутюнян М. Е. Границы достижимых скоростей передачи по каналу с множественным доступом призаданной экспоненте вероятности ошибки. Доклады Академии наук Армении. 1990. Т. 91. Вып. 3. С. 99—104.

223. Арутюнян М. Е. Границы Е-пропускной способности канала со случайным параметром. Проблемы передачи информации. 1991. Т. 27. Но. 1. С. 14-23.

224. Арутюнян М. Е. Оценки Е-пропускной способности меняющихся каналов, кандидатская диссертация, 1991.

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

226. Арутюнян Е. А., Арутюнян М. Е., Аветисян А. Е. Область достижимых скоростей канала множественного доступа и надежность. Известия Академии наук Армении, серия Математика. 1992. Т. 27. Но. 5. С. 51-68.

227. Haroutunian Е. A., Haroutunian М. Е. Channel with random parameter. Proc. of XXII Prague conf. on Inform. Theory, Statistical Decision Functions, Rundom Processes. 1994. P. 20.

228. Haroutunian E. A., Haroutunian M. E., Avetissian A. E. Restricted two-way channel: Bounds for achievable rates region for given error probability exponent. Proc. of IEEE International Symposium on Information Theory. Whistler. Canada. 1995. P. 13.

229. Haroutunian M. E., Haroutunian E. A. An outer bound for E-capacity region of broadcast channel giving a new outer bound for capacity region. Proc. of IEEE International Symposium on Information Theory. Ulm. Germany. 1997. P. 267.

230. Haroutunian M. E., Haroutunian E. A. Random coding bound for incapacity region of general broadcast channel. Proc. of International Conf. on Computer Sciences and Inform. Technologies. Yerevan. Armenia. 1997. P. 211-214.

231. Арутюнян E. А., Арутюнян M. E. Границы области ^-пропускной способности двустороннего канала с ограничениями. Проблемы передачи информации. 1998. Т. 34. Но. 3. С. 7 — 16.

232. Арутюнян М. Е. О достижимых скоростях передачи интерференционного канала. Математические вопросы кибернетики и вычислительной техники. 1998. Т. 20. С. 79 — 89.

233. Арутюнян М. Е. Об интерференционном канале с коррелированным кодированием. Доклады Национальной академии наук Армении. 1998. Т. 98. Вып. 2. С. 102- 107.

234. Haroutunian M. E. Random coding bound for incapacity region of general interference channel. Trans, of International conf. on Computer sciences and Information Technologies. Yerevan. Armenia. 1999. P. 127-130.

235. Haroutunian M. E., Haroutunian E. A. incapacity and capacity regions of general broadcast channel. Trans, of International conf. on Computer sciences and Information Technologies. Yerevan. Armenia. 1999. P. 155-158.

236. Haroutunian M. E. Random coding bound for incapacity region of the broadcast channel. Trans, of Institute for Informatics and Automation Problems of NAS RA and YSU, Mathematical Problems of Computer Sciences. 2000. V. 21. P. 50-60.

237. Haroutunian M. E. Arbitrarily varying and random parameter channels with informed encoder. Proc. of International Conf. on Computer science and Inform. Technologies. Yerevan. Armenia. 2001. P. 207-210.

238. Haroutunian M. E. Bounds for rate-reliability function of multi-user channels. International Meeting on General Theory of Information Transfer. Bielefeld. Germany. February. 2002. P. 16.

239. Haroutunian M. E., Haroutunian E. A. ^-capacities of varying channels. Opening conf. on General Theory of Information Transfer and Combinatorics. Bielefeld. Germany. November. 2002. P. 25.

240. Haroutunian M. E. New inner bounds of the rate-reliability regions for certain multiple-access channels. Доклады Национальной академии наук Армении. 2002. Т. 102. Вып. 2. С. 113-120.

241. Арутюнян М. Е. Об области ^-пропускной способности канала с множественным доступом. Известия НАН РА "Математика". 2003. Т. 38. Но. 1. С. 3-22.

242. Haroutunian М. Е.( Tonoyan S. A. Computation of ^-capacity and capacity bounds for binary restricted two-way channel. Proc. of International Conf. on Computer science and Inform. Technologies. Yerevan. Armenia. 2003. P. 168-172.

243. Haroutunian M. E. On multiple-access channel with random parameter. Proc. of International Conf. on Computer science and Inform. Technologies. Yerevan. Armenia. 2003. P. 174— 178.

244. Haroutunian M. E. Bounds of incapacity for multiple-access channel with random parameter. Trans, of Institute for Informatics and Automation Problems of NAS RA, Mathematical Problems of Computer Sciences. 2005. V. 24. P. 16-35.