Содержание к диссертации
Введение
Глава 1. Основные понятия и постановка проблемы .
1.1. Определения и обозначения мер информации 18
1.2. Определения и форАгулировки метода типов 22
1.3. Описание дискретного канала без памяти 24
1.4. Функция надежности дискретного канала без памяти 28
1.5. Е-пропускная способность дискретного канала
без памяти 31
1.6. Обзор основных результатов диссертации 34
Часть 1. Многотерминальные каналы 41
Глава 2. Двусторонние каналы .
2.1. Общий двусторонний канал 42
2.2. Двусторонний канал с ограничениями 43
2.3. Формулировка результатов 47
2.4. Доказательство границы сферической упаковки для
двустороннего канала с ограничениями 49
2.5. Модификация леммы об упаковке 51
2.6. Доказательство границы случайного кодирования 56
2.7. Пример вычисления границ 58
Глава 3. Интерференционные каналы .
3.1. Общий интерференционный канал 63
3.2. Формулировка границы случайного кодирования 66
3.3. Доказательство теоремы
3.1 для общего интерференционного канала 69
3.4. Интерференционный канал с коррелированным кодированием 71
3.5. Доказательство теоремы 3.2 для интерференционного канала с коррелированным кодированием 73
Глава 4. Широковещательные каналы .
4.1. Общий широковещательный канал 80
4.2. Внутренняя граница области Е-пропускной способности 84
4.3. Доказательство теоремы 4.1 86
4.4. Оценки для частных моделей 95
Глава 5. Каналы с множественным доступом
5.1. Основные модели 98
5.2. Формулировка оценок области Е-пропускной способности для различных моделей 103
5.3. Лемма об упаковке для канала с множественным доступом. 108
5.4. Доказательство внутренней оценки 116
Глава 6. Канал с двумя входами и двумя выходами
6.1. Основные определения 118
6.2. Граница случайного кодирования области Е-пропускной способности 120
6.3. Доказательство теоремы 6.1 122
6.4. Доказательство леммы об упаковке для случая канала с двумя входами и двумя выходами 124
Часть 2. Меняющиеся каналы 130
Глава 7. Составной канал
7.1. Описание системы связи 131
7.2. Формулировки границ Е-пропускной способности составного канала 133
7.3. Вывод границы сферической упаковки 135
7.4. Граница случайного кодирования и граница с выбрасыванием 138
Глава 8. Канал со случайным параметром
8.1. Информация о канале 149
8.2. Формулировка результатов для канала с информированным кодером 152
8.3. Доказательство верхней границы 153
8.4. Доказательство нижней границы 157
8.5. Доказательство леммы 8.1 163
8.6. Другие модели канала со случайным параметром 167
8.7. Обобщенный канал со случайным параметром 171
8.8. Пример 173
Глава 9. Канал множественного доступа со случайным параметром
9.1. Формулировка полученных результатов для различных ситуаций 177
9.2. Доказательство внутренней границы для случая 5 187
Глава 10. Произвольно меняющийся канал с информированным кодером
10.1. Формулировка результатов 192
10.2. Доказательство теоремы 10.1 195
Заключение 198
Литература
- Определения и форАгулировки метода типов
- Формулировка границы случайного кодирования
- Внутренняя граница области Е-пропускной способности
- Граница случайного кодирования области Е-пропускной способности
Введение к работе
Актуальность темы.
Изучение сложных информационных систем, предназначенных для одновременного обслуживания большого числа пользователей и систем, изменяющихся во времени, образует два важных раздела современной теории информации. Существенным в этом направлении является нахождение границ скорости передачи при условии достижения требуемой высокой надежности, т. е. малой вероятности ошибочной передачи информации. Особую актуальность эти исследования приобрели в связи с изучением все более сложных многотерминальных каналов, т. е. каналов со многими передающими и (или) принимающими сторонами. Большой интерес представляют также модели так называемых меняющихся каналов, матрица переходных вероятностей которых изменяется во времени.
Для каждого из исследуемых каналов W согласно Шеннону первоочередной теоретико-информационной задачей является нахождение его пропускной способности C(W), которая определяется как верхняя грань скоростей кодов с вероятностью ошибки стремящейся к нулю при увеличении длины кода N. Важные свойства каждой системы передачи информации отражает функция надёжности, введенная (также как и понятие пропускной способности) Шенноном. Эта функция E(R,W) определяется как оптимальный показатель
т
J.
экспоненциального убывания вероятности ошибки при росте длины передачи N в зависимости от скорости передачи R.
Большое число исследований посвящено изучению функции надёжности различных информационных моделей. Обычно удается построить верхние и нижние границы этой функции. В этом разделе шенноновской теории оптимального кодирования информации для большинства многотерминальных и меняющихся каналов такие оценки не были найдены из-за сложности проблемы. В связи с принципиальной трудностью нахождения функции надёжности для всего диапазона скоростей 0 < R < C(W), полностью эта задача решена лишь в частных случаях. Для однопутевых каналов типична ситуация, когда найденные верхняя и нижняя оценки функции E(R, W) совпадают лишь при скоростях в интервале Rcr < R < C(W), где Rcr — значение скорости, в которой производная E(R, W) по R равна —1.
В диссертационной работе поставлена актуальная научная задача создания гармоничной общей теории и более эффективных методов изучения функции, обратной к функции надежности, для новых классов более сложных систем передачи информации, имеющих практическое применение.
Цель диссертационной работы.
Диссертация посвящена углубленному математическому исследованию взаимозависимости важнейших характеристик ряда классов моделей (типов) многотерминальных и меняющихся каналов связи.
Рассмотренные в работе классы каналов находятся в центре внимания исследователей современной теории информации.
Объект исследования.
В данной диссертации объектом исследований являются дискретные многотерминальные и меняющиеся каналы без памяти. Исследуется Е'-пропускная способность, которая является оптимальной скоростью кодов, обеспечивающих экспоненциальное убывание по длине кода N вероятности ошибки с заданным показателем (надёжностью) Е. Эта функция С(Е, W) впервые была рассмотрена Е. Арутюняном и является обратной к функции надёжности.
Изучение 12-пропускной способности в некоторых случаях оказывается более удобным. Кроме того, когда надёжность приближается к нулю, Е-пропускная способность сходится к пропускной способности канала, и таким образом, с помощью построения оценок для С(Е, W) можно получить оценки и для пропускной способности C{W). В этом смысле ^-пропускную способность можно рассматривать как обобщение понятия пропускной способности.
В настоящей работе предложены методы исследования .Е-пропуск-ной способности для ряда моделей дискретных меняющихся и многотерминальных каналов без памяти.
Методы исследования.
Разработанная в работе методология применяет методы теории вероятностей и теории информации. Для получения верхних и нижних границ используется понятие типов, примененное рядом
авторов при изучении однопутевого дискретного канала.
В основе метода построения нижних границ /^-пропускной способности лежит подход шенноновского метода случайного кодирования с использованием, так называемой, леммы об упаковке [44]. Этот метод, который ранее применялся для доказательства нижних оценок пропускной способности и функции надёжности дискретного канала без памяти, развит и применен к исследуемым сложным каналам. Имея ввиду способ доказательства, нижние границы называются границами случайного кодирования. Для каждой из рассмотренных в диссертации моделей, приходится доказывать новую модификацию леммы об упаковке и решать проблему нахождения и доказательства нижних границ.
Основой для разработки метода построения верхних оценок Е-пропускной способности явился комбинаторный метод, предложенный Е. Арутюняном. К преимуществам этого метода следует отнести то, что он не опирается на предварительное доказательство строгого обращения теоремы кодирования, как было в случае метода, использованного в ряде работ при выводе границ упаковки сфер для функции надёжности.
Метод разбиения графов, предложенный Чисаром и Кернером [98] для построения нижних границ функции надёжности обычного однопутевого канала, модифицирован для доказательства границы случайного кодирования и границы с выбрасыванием 2?-пропускной способности составного канала.
Научная новизна.
В диссертации предложена методология изучения оптимальной скорости передачи в зависимости от экспоненциального показателя вероятности ошибки для различных каналов. Методология включает:
— метод построения нижних границ ^-пропускной способности для
меняющихся каналов;
— метод построения внутренних границ области Е'-пропускной
способности для многотерминальных каналов;
метод построения границы с выбрасыванием Е'-пропускной способности для составного канала;
метод построения верхних границ ^-пропускной способности для меняющихся каналов;
метод построения внешних границ области Е'-пропускной способности для многотерминальных каналов.
Разработанные методы применены для исследования ряда важных классов каналов. Построены
— внешние и внутренние оценки области ^-пропускной способности
для
двустороннего канала с ограничениями,
— внутренние оценки области /^-пропускной способности для
общего интерференционного канала,
интерференционного канала с коррелированным кодированием,
общего широковещательного канала,
канала с множественным доступом с коррелированными источни-
ками, а также ряда других моделей КМД,
канала с двумя входами и двумя выходами.
— верхние и (или) нижние границы 7-пропускной способности для
составного канала,
канала со случайным параметром,
канала множественного доступа со случайным параметром,
произвольно меняющегося канала с информированным кодером.
Из основных результатов в качестве следствий вытекают соответствующие оценки для пропускных способностей вышеперечисленных каналов, а также их частных случаев. Приведен пример вычисления границ Е'-пропускной и пропускной способностей для двустороннего канала с ограничениями.
Достоверность и обоснованность.
Достоверность научных результатов, а именно, предложенная методология изучения основных характеристик различных каналов, обоснована приведенными в работе строгими математическими доказательствами.
Теоретическая и практическая значимость полученных результатов.
Диссертация носит теоретический характер. Исследование всё более сложных моделей каналов приближает к познанию различных реальных средств связи настоящего и будущего. Научная значимость результатов диссертации заключается в том, что разработанные в работе методы являются теоретической базой для изучения все новых
каналов связи.
С точки зрения приложений, решение этих задач позволяет устанавливать предельные возможности различных систем передачи информации и путём сравнения определять, в какой мере проектируемая система близка к оптимальной. Полученные результаты по меняющимся и многотерминальным каналам имеют практическое применение также в задачах сокрытия информации.
Апробация работы. Основные результаты диссертации докладывались на IX симпозиуме по проблеме избыточности в информационных системах (Ленинград, 1986), Республиканской научно-практической конференции по методике преподавания математики и механики в ВУЗе (Ереван 1986), Международном семинаре по анализу статистических данных (София 1987), IX всесоюзной конференции по теории кодирования и передачи информации (Одесса, 1988), III Международном семинаре стран членов СЭВ по статистической теории связи и её применениям (Варна, 1988), IV международном коллоквиуме по теории кодирования (Дилижан, 1991), XXII пражской конференции по теории информации, статистическим решающим функциям и случайным процессам (Прага, 1994). Международных симпозиумах по теории информации (Вистлер, 1995, Ульм, 1997), 7-ой совместной шведско-российской международной конференции по теории информации (Санкт-Петербург, 1995), Международных конференциях по компьютерным наукам и информационным технологиям (Ереван, 1997, 1999, 2001, 2003), Международных встречах по
общей теории информационной связи (Билефельд, февраль, ноябрь, 2002), на заседании семинара группы стохастической обработки изображений Женевского университета (Женева, 2005), на заседаниях семинаров по теории информации в ИППИ РАН, в Ереванском государственном университете, в ИПИА НАН РА, в Институте математики НАН РА.
Определения и форАгулировки метода типов
Доказательства в данной работе основаны на методе типов [44], [93], [96], одного из основных в теории информации. Понятие типа развито и использовано в книгах Вольфовица [209], Чисара и Кернера [44], Ковера и Томаса [93]. Применения метода типов указаны в обзорной статье Чисара [96].
Пусть N(x\x) — число повторений івх= (жі,..., XN) Є XN. Типом P вектора x называется распределение вероятностей Р = ІР( ) = j U Є X]. (1.1) Совокупность всех последовательностей х типа Р на Xм обозначается Тр(Х) и часто также называется типом Р.
Любое распределение вероятностей Р вида (1.1), т.е. имеющее компонентами вероятности, задаваемые отношением числителя к знаменателю N, может рассматриваться как тип векторов в XN.
Множество всех распределений на X часто обозначается V(X), а его подмножество, состоящее из возможных типов последовательностей х Є XN обозначается VN{X).
Если iV(cc,2/x,y) есть число пар символов {х,у) в (х, у) Є XN х yN, то совместный тип последовательностей х Є XN и у Є Ум определяется как совместное распределение Другими словами, совместный тип это тип последовательности ((жь 2/L), (Ж2, 2/2), (жлг, Ум)) из {X х y)N. Будем говорить, что у Є Ум имеет условный тип V = {V(y\x), хЄХ,уеУ} при заданной х Є XN, если W(ar,2/x,y) = N(x\x)V{y\x), хеХ,уеУ. Множество всех последовательностей у Є yN условного типа V при заданном векторе х Є Тр(Х) обозначается через Тру(у\х). Совокупность всех возможных условных типов V при любом х типа Р обозначается Улг(У, Р) В следующих леммах сформулированы важные свойства типов, неоднократно используемые в работе. Лемма 1.1. Число различных типов последовательностей при фиксированном N ограничено сверху следующим образом: \VN{X)\ (N + l)V\ (1.2) \VN(y,P)\ (N + l)WM. (1.3) Лемма 1.2. При любом типе Р є VN(X) число элементов множества Тр(Х) следующим образом оценивается сверху и снизу: (N + 1)-Мехр{ЛГ#ррО} \Т?(Х)\ exp{NIIP(X)}. (1.4) Если V Є Ум(У,Р) и х Є Тр{Х), то число элементов множества Тру(У\х) ограничено следующим образом: (N + l)-WWexp{NHP,v(Y\X)} Г (Гх) exp{NHPy(Y\X)}. (1.5) Лемма 1.3. Для любого типа Р и любого распределения Q на X, если х Є Ту{Х), то QN(x) = exp{-N(ITp(X) + (PQ))}, (1.6) для любого условного типа V и любой стохастической матрицы W : X - У, если х Є Т/РО и у Є Г (Гх), то И (ух) = ехр{-АГ(Яр,г(ГХ) + /?(К Р))}. (1.7) Доказательства этих лемм опускаем, так как они неоднократно приводились во многих работах. Их можно найти, например, в [44].
Каналы бывают дискретными, непрерывными или полунепрерывными. Канал называется дискретным, если множество входных сигналов конечно. Канал называется непрерывным, если множество входных сигналов бесконечно. Канал называется полунепрерывным, если множество входных сигналов конечно, а множество выходных сигналов бесконечно.
В данной диссертации рассматриваются дискретные каналы с конечными входными и выходными алфавитами.
Пусть X, У конечные множества сигналов, соответственно, на входе и на выходе канала и W = {W(y\x),xeX,yey} стохастическая матрица условных (переходных) вероятностей. Однопутевой дискретный канал W с входным алфавитом X и выходным алфавитом У определяется стохастической матрицей переходных вероятностей W : X -* У.
Элемент И^(т/|ж) матрицы является условной вероятностью получения символа у Є У на выходе канала, если символ х Є X был передан с входа.
Формулировка границы случайного кодирования
Широковещательный канал это система связи с одним кодером и многими адресатами. Однако для краткости формулировки достаточно изучать канал с двумя получателями. Рассмотрим общий широковещательный канал WB (Рис. 11) с тремя источниками, с дискретным каналом без памяти W : X — 34 х У2, где X — конечный входной, а З ь 3 2 — конечные выходные алфавиты. Матрица переходных вероятностей имеет вид WB = {W(yi,y2\x), 2/1 Є Уи т/2 Є У2, х є X), однако достаточно рассматривать только маргинальные переходные вероятности Wi(yi\x)= Y, W(yuy2\x), W2(y2\x)= W{yuy2\x). У2ЄУ2 уієУі
Три источника создают сообщения mo, ті, т2 из соответствующих конечных множеств Mo, Мі, Л42. Сообщения должны быть закодированы общим кодером в кодовое слово х длины N и переданы через каналы Wi и W2 двум получателям.
Кодом для общего широковещательного канала называется тройка отображений (/,01,02). где f:M0xMixM2- XN есть кодирование, а 91 : У? Мох Ми д2 : У% - М0хМ2 — декодирования. Ri(f, &,#) = ЛГ1 log МІ, і = 0,1,2 — скорости кода. Как и в остальных каналах, N мерные переходные вероятности определяются условием отсутствия памяти.
Обозначим через V%mQm. = g [l{mo,mi) множество всех уі( которые декодируются, соответственно, в то,ті, і — 1,2. Эти множества несовместимы и
Вероятности ошибки декодирования на двух выходах, когда переданы сообщения mo, ті,т,2 , зависят от кода: Єі(т0, ти т2) = W? \ U , 1/( 0, гпи т2) , г = 1,2, [(то,ггг,-)/(т 0,т і) а для всего кода (/, #ь 7г) рассматриваются максимальная е (/, 7ьiV",ИЪ) = mmaxi2е (mo,тьm2), і = 1,2, (4.1) или средняя еі(/, 7І, А/", Wb) = Ci(m0,mi, m2), і = 1,2, (4.2) M0M1M2 m0,mi,m2 вероятности ошибок.
Пусть E = (Ei, E2), ЕІ 0, г = 1,2. Неотрицательные действительные числа Ло, Ri, R2 называются і?-достижимой тройкой для общего широковещательного канала, если для любого S 0 и достаточно больших N существует код, такой что jj log М0Мі 7 + Ri - 5, ї = 1,2, (4.3) и ei(f,gi,N,WI}) exp{-NEi], і = 1,2. (4.4)
Область і -пропускной способности C(E,WH) при максимальной вероятности ошибки есть множество всех .Е-достижимых троек скоростей. Через С(Е, WB) обозначаем область і?-пропускной способности при средней вероятности ошибки.
Широковещательные каналы впервые были изучены Ковером [86]. Область пропускной способности детерминированного широковещательного канала была найдена Пинскером [35] и Мартон [160], [ 161 ]. Область пропускной способности широковещательного канала с одной детерминированной компонентой была определена независимо Мартон [161] и Гельфандом и Пинскером [15]. Большое число работ посвящено решению проблемы для ассимметричного широковещательного канала [195], [87], [150], [151], область пропускной способности была найдена в [151]. Несмотря на тот факт, что во многих работах рассматривались различные модели широковещательных каналов ([12], [14], [32], [36], [37], [39], [40], [45], [57], [71], [72], [88], [97], [111], [116], [117], [118], [121], [133], [136], [136], [139], [152], [156], [157], [165], [167], [173], [184], [200]), область пропускной способности общего широковещательного канала, когда передаются одно общее и два частных сообщения, до сых пор не найдена. Оценки функции скорость-надежность также не получены. В [161] найдена внутренняя граница области пропускной способности широковещательного канала. Внешние оценки области пропускной способности широковещательного канала без общего сообщения (когда RQ — 0) были найдены в [86] и в [173]. Вилемс [206] доказал, что области пропускной способности широковещательного канала при максимальной и средней вероятностях ошибки совпадают. Работы [31], [44], [79], [89], [93], [108], [196], [197] содержат подробные обзоры.
Внутренняя граница области Е-пропускной способности
Пусть Ко, U\, U2 некоторые конечные множества. Рассмотрим случайные величины С/о, U\, U2, X, Yi, Y2 со значениями, соответственно, в Uo, U\, U2, X, Уі, У2 и с совместным расспределением вероятностей Q о Р о Ц = {Q о Р о Ц(щ, щ, и2, х, yi) = = Q(u0,ui,U2)P(x\uo,ui,u2)Vi(yi\x)}, «= 1,2, где Q = {Q(uo,ui,u2), щ Є Ни і = 0,1,2}, Р = {P(x\uo,Ui,u2), х Є X, щ Є НІ, і = 0,1, 2}, Vi = {Vi(yi\x), хЄХ, Уі Є УІ}, і = 1,2. Таким образом, имеются две цепи Маркова {UQ,UuU2)- X- Yh г = 1,2. Обозначим Vi(Q, Р,Ei) = {Vi : D(Vi\\Wi\Q,P) E{}, і = 1,2. (4.5) , (4.6)
Рассмотрим следующие неравенства при і — 1,2: О R0 mjn [Цбда,д) VQMW Л UQ) + D(Vi\\Wi\Q, Р) - ЕІ\+ {) Ri v да, VQMiYi Л Ui\U0) + DiViWWilQ, Р) - ЕІ\+ , (4.7) 0 І?З-І ,. "%і ,І ,РУ,-,( з-іЛ%-іОД+ (4.8) +D{V3-i\\W3-i\Q, Р) - з-і+ - № Л U2\Uo), и области 7 . Р. Е. \VB) = {(Яо, Rh R2) : неравенства (4.6), (4.7), (4.8) имеют место при некотором (U0M1M2)-+X- Yl}ti = l,2, Kr{Q.P4E.WB)= U K(Q.P.E.WB), ї=1,2 ПГ(Е, WB) = U Kr(Q, P.. E, WB). (4.9)
Теорема 4.1. Для всех i?i 0. 2 0 область 7Zr(E. WB) является внутренней оценкой для области . -пропускной способности широковещательного канала: ПГ(Е. WB) С С(Е. WD) С С(Е. WB), или, другими словами, любая тройка скоростей (R0.R1.R2) Є TZriEAVn) является Е-достижимой для широковещательного канала WB.
В [133] Гаек и Пурслей высказали предположение, что область достижимых скоростей широковещательного канала не изменится, если рассмотреть следующие ограничения множеств М іііт(АГ,н»»х(Уі,й)) и \Щ 1 + \ (шіи(Л . \УІ\) - 1), г = 1,2.
Это предположение остается в силе также в нашем случае. Следствие 4.1. Когда Е\ — 0. Е2 —» 0, используя аргументы разделения времени, из (4.9) получаем внутреннюю границу области пропускной способности C(\VB) широковещательного канала, которую получила Мартон в [161]: Пг(ПЪ) = U Kr{Qi Р- изд, QPQP(UoxKixl(2xX) где nr(Q,P,WB) = {(RQ,Rl.R2) : 0 До + ДІ /д,р,и ,( Л W0, (4.10) 0 R0 + Лі + R2 min {/дди Уі Л С/о); /д,р,и ,( 2 Л tf0)} + (4.11) +IQ,p,m(Yi Л tfiltfo) + IQtP,w2{Y2 Л (/2f/0) - IQ{UI Л ОД), для некоторого (UQ, U\. U2) — X — Yi, і = 1,2}. Для некоторых UQ. UI, U2, пусть следующим образом задано распределение Q: Q(UQ.UI,U2) = QO(UO)QI(UI\UQ)Q2(U2\UO.UI), Qo = {Qo{uo), щ є Ко}, Q\ = {Qi(«i«o). «і є Wb "о є ОД, Q2 = { 2(И2І«0? «і)- "О Є Wo, Ul Є U\, 111 Є W2}. Для краткости обозначим iioiiiii2x(mo, mi,m2) вместо (uo(mo), UI(7HO, mi). 112(mo, mi, тг).х(то, ті, тг)), обозначим также uouiii2(mo, тіляг) вместо (uo(mo).ui(mi?no),U2(m2mo,mi)), и так далее.
Пусть тройка (Яо. Ді- /) принадлежит области 7Zr(Q, P. Е. И #) для некоторых Wo, Wi, W2. Е\, Е2: Q, P. Нужно показать, что для любого 5 О и достаточно большого N существует код длины N с Л/о = охр iV min [ I W№ л %)+ (4.12) +0(Щ\\У№,Р)-ЕІ-6\+]}, Мі = охр jiV КіЄІі »и,Ях) I WiO i Л 7іад+ (4.13) +ДКіИ ід,Р)-Еі-5+}, Л/2 = охр JJV mipfb) lWafl 2 Л U2\U0)+ (4.14) +D(l/2ir2Q, P) - E2 - S\+ - IQ(Ui A U2\Uo)} , удовлетворяющий (4.3) и максимальные вероятности ошибок (4.1) удовлетворяющие (4.4).
Выберем случайным образом, независимо с равномерным распре-деленим Л/о векторов uo(wo) из TQ0(UQ), Ah векторов ui(r/7o, mi) из lQ(Ui\uo(mo)), Л/2 наборов по \J(Q,m0,mv)\ = exp{N(IQ(Ui Л U2\U0)+ 5/8)} ВеКТОрОВ U2j(77Jo,"l2) ИЗ 7д([/2іІо(т0)). Построим код следующим образом. Для каждого uoiii(mo,mi) и 7П2 Є М 2 выберем такое j из J{Q, то, т2), что \\2j{mo,m2) Є TQ{U2\\\Q\\i{mQ,mi)). Обозначим этот вектор ii2(mo, mi, тг). Если такого j не существует, пусть U2(rn0, mi. т2) = u2j(mo, m2) для j = J(Q, m0, m2). Следующим шагом выберем вектор x(mo,mi,m2) из 7 ( 110111112 (mo, mii 2)), если u2(mo,mi,m2) Є Зд(/2іі0ііі(то,ті)) и из TQ,P{X) если u2(mo,mb77i2) . 7Q(f/2iioUi(mo,mi)).
Определим правило декодирования для декодера gi (аналогичное правило может быть использовано для декодера д2) использующее критерий "минимизации дивергенции": каждый вектор у і декодируется в такую пару r/?0.m lr что для некоторых т2 и V{ дивергенция Z F/IIWilQ, P) минимальна и Уі Є 7QtpfiY01iiouiU2x(rno.m 1,m2)). Для любых то Є Мо, ті Є Мі, т2 Є Л4г обозначим через А(то,ті,т2) случайное событие А(то,ті,т2) = {112( 0, 1: 2) Зд(/2І11о11і(о,ті))}. Декодер ()1 МОЖЄТ ДОПУСТИТЬ ОШИбку, ЄСЛИ Л(777о,ТПі,Ш2) имеет место или если А{то,ті,т2) имеет место и сообщения то,ті были переданы, но существует (т 0. т\) {то,ті) такое, что для некоторых т 2 и V{
Граница случайного кодирования области Е-пропускной способности
Пусть U. Х\. Лг2, Уі, І2 случайные величины со значениями в алфавитах Ы.Х\,Х2.У\.У2 соответственно, где U удовлетворяет условию \Ы\ 6 и U A"iAr2 0 Y\Y2. Ограничение \U\ б может быть доказано с помощью техники, предложенной независимо Алсведе и Корнером [57] и Вайнером [211].
Рассмотрим следующие распределения вероятностей: Ро = {РоИ, и еЩ, Р = {P(u,xi,x2) = Po(u)P(xi,x2\u), XI Є Хи х2 Є Х2], Pi = {Pi(Xi\u) = P(XUX2\U). Хі Є Хі}, і = 1,2, Р = {Д}(«)Р (хіїЯ:2м) = Po(u)Pi(.riU)P2(.r2W). an Є Л ь .т2 Є А2}, РоЦ = {РоС Р ь ІиЖСг/іІжьагг). агі Є Лі. .т2 6 Л хц Є #}, г = 1,2, где Уі. Т — вероятностные матрицы. Используем также матрицу Q = {Q(.T2.TI,M) — P(.TI..T2U)/P (.XI,:C2U). .ті Є Лі. д;2 Є Х2}. Рассмотрим область случайного кодирования 7Zr(E. WD) nr{P\E.\VD) = {{RhR2): () Ri min , min /р,ц№ ЛХ2.У (/) + +D(Pol/iP oIKl-)-,i+, (6.1) О і?2 шіп тіи \IpvAX2 Л Л ь Yi\U)+ + (P о KP о И ,) - ;+ , (6.2) R\ + #2 min min \IpvAYi Л ХЬХ2Ш+ + /P(AI Л X2\U) + D(P о Vi\\P о 11 - +, г = 1,2,} (6.3) и p Имеет место следующая теорема:
Теорема 6.1. При всех Е — (Е1.Е2). Е\ 0. 2 0, область случайного кодирования Иг(Е.\1Ъ) является вігутренней оценкой области Е -пропускной способности канала с двумя входами и двумя выходами: 7Zr{EJVD)QC{E.\VD).
Доказательство теоремы 6.1. основано на следующей модификации леммы об упаковке (аналогичная лемма имеет место для второго выхода). Лемма 6.1. Для всех Е\ 0,5 Є (0, Е\) и любого типа Р , если 0 iV_1 log Mi шііі UpVtiXi A X2. Yi\U)+ +D(P о Vi\\P о Wi) -Ei\+- S, (6.4) 0 N 1 logA/2 mill /pvi№ Л Yi\U)+ +D{P о Vi\\P о U i) - i+ - (5, (6.5) то для любого u Є TpQ{U) существует M\ векторов /і(mi) Є ТрУ(Л іІіі) и Л/г векторов /г(г/і2) Є Tp A lu) таких, что для матриц 17і : Л і х Х2 — ЗЛ, i : А і х Л2 —» ЗЛ и достаточно больших iV имеют место следующие неравенства (Уі/(тьт2))П /(ті,т2)єГ (ХьХ2и) П U ГРу{{\\ 1/(777,;. 7П2)) (mi,7n2)/(mi,m2) Mu\[2 x 1} i/(mb m2)) x exp{-A/ \Ei - D{P о V/P о И і)+} x x схр{-ІУ( (РР ) - 8)}. (6.6)
Доказательство леммы 6.1 приведено в следующем параграфе. Чтобы доказать теорему 6.1, нужно показать существование кода (/1,/2,01,02). Для которого ёД/. ЛМ1Ъ) 2- , г = 1,2 и (6.1)-(6.3) удовлетворены для любого фиксированного Р . Существование кодовых слов /\(піі) Є T (Xi\u) и /2(7712) Є Т Л и), удовлетворяющих (6.6), установлено леммой 6.1. Используем следующий метод декодирования; каждому уі ставится в соответствие такая пара (777,1,777,2), для которой уі Є T Vl(Yi\f(mi.m2)) с такими P.Vi, что дивергенция D(P о Vi\\P о \V\) минимальна.
Дискретный меняющийся канал называется составным каналом, если состояние s Є S канала неизменно во время передачи одного слова длины N, однако оно может произвольным образом меняться при переходе к следующему слову. Будем обозначать через Wc и писать И (ух,5)=її (ух).
Так же как и все меняющиеся каналы составные каналы могут рассматриваться в четырех случаях, когда состояние s известно или неизвестно на кодере или декодере. Однако, оказывается, что знание состояния канала на декодере не приводит к улучшению асимптотических характеристик передачи [209]. Поэтому достаточно рассмотреть случай, когда состояние канала известно и на кодере, и на декодере, и случай, когда состояние канала неизвестно ни на кодере, ни на декодере.
Дискретные составные каналы без памяти были впервые изучены Блекуэллом, Брейманом и Томасяном [75] и Добрушиным [18]. Задача вычисления пропускной способности составных каналов была решена Вольфовицем [208].
Аналогично дискретному каналу без памяти, пропускные способности составного канала для средней и максимальной вероятностей ошибок совпадают. В книге Чисара и Кернера [44] приведены граница случайного кодирования и граница сферической упаковки для функции надёжности составного канала. В [213], [215], [224] автором получены границы сферической упаковки, случайного кодирования и граница с выбрасыванием для -пропускной способности составного канала.
