ПРОБЛЕМЫ ПЕРЕДАЧИ ИНФОРМАЦИИ

Том 55

2019

Вып. 1

УДК 621.391.1 : 519.72

C.Л. Фон, В.Я.Ф. Тань

СИЛЬНЫЕ ОБРАЩЕНИЯ ТЕОРЕМЫ КОДИРОВАНИЯ

ДЛЯ СЕТЕЙ ОДНОВРЕМЕННОЙ ПЕРЕДАЧИ СООБЩЕНИЙ

C ТОЧНОЙ ГРАНИЦЕЙ МНОЖЕСТВА РАЗРЕЗА

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

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

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

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

Из этого результата следует, что для любого фиксированного вектора скоро-

стей, находящегося вне области пропускной способности средняя вероятность

ошибки декодирования для любой последовательности кодов длины n с дан-

ным вектором скоростей должна стремиться к 1 при n, стремящемся к беско-

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

Чисара и Кёрнера 1982 г., в которой была полностью охарактеризована функ-

ция надежности любого дискретного канала без памяти с обратной связью для

скоростей выше пропускной способности. Кроме того, сильное обращение тео-

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

няется ограничению на мощность почти наверное. Важными следствиями этих

результатов являются новые результаты об обращении теоремы кодирования

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

для следующих каналов с ретрансляцией в обеих моделях: ухудшенный канал

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

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

DOI: 10.1134/S0134347519010042

§ 1. Введение

Рассматривается сеть одновременной передачи сообщений общего вида, которая

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

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

и выходные алфавиты предполагаются конечными, такая сеть называется дискрет-

ной сетью без памяти (ДСБП) [1, гл. 18]. Известной внешней границей на об-

ласть пропускной способности ДСБП является граница множества разреза (cut-set

bound), полученная Эль-Гамалем в [2]. Если ДСБП можно представить в виде транс-

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

максимального потока/минимального разреза, которую можно вычислить по ал-

горитму Форда - Фалкерсона [3]. Граница множества разреза утверждает, что для

любого множества разреза T в сети с узлами, индексированными множеством I,

сумма скоростей передачи сообщений по одну сторону от разреза ограничена сверху

условной взаимной информацией между входными переменными из T и выходны-

= I \ T относительно входных переменных из T^c. ДСБП

является обобщением хорошо изученного дискретного канала с ретрансляцией без

памяти (ДКРБП) [4]. Известно [5], что в общем случае граница множества разре-

за не является точной (достижимой), но является таковой для нескольких классов

ДСБП, включая, среди прочих, ухудшенные ДКРБП [4], ухудшенные ДСБП [6, 7],

полудетерминированные ДКРБП [8], ДКРБП с ортогональными компонентами на

передающем конце [9] и линейные детерминированные многоадресные сети [10].

Возможным недостатком границы множества разреза является тот факт, что она

дает только слабое обращение теоремы кодирования для сетей с точной границей

множества разреза. Слабое обращение теоремы кодирования гарантирует лишь то,

что для любой сети с точной границей множества разреза и любого фиксированно-

го вектора скоростей, находящегося вне области пропускной способности, средняя

вероятность ошибки декодирования для любой последовательности кодов длины n

с данным вектором скоростей отделена от 0 при n, стремящемся к бесконечности.

В теории информации также бывает важно установить сильное обращение теоре-

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

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

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

ющем смысле: для любого вектора скоростей, лежащего внутри области пропускной

способности, найдется последовательность кодов длины n с этими скоростями, для

которой асимптотическая вероятность ошибки равна 0, а асимптотическая веро-

ятность ошибки любой последовательности кодов длины n с вектором скоростей,

лежащим вне области пропускной способности, равна 1. Контрапозицию сильного

обращения теоремы кодирования можно приблизительно сформулировать так: все

коды, дающие с ростом длины блока вероятность ошибки не выше допустимого

уровня ε ∈ (0, 1), т.е. ε-надежные коды, должны иметь векторы скоростей, при-

надлежащие области пропускной способности. Таким образом, сильное обращение

теоремы кодирования устанавливает строгий фазовый переход между достижимы-

ми и недостижимыми скоростями, гарантируя отсутствие компромисса между ве-

роятностью ошибки и скоростью при длине блока, стремящейся к бесконечности.

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

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

теоремы кодирования.

1.1. История вопроса. Впервые гипотеза о справедливости сильного обращения

теоремы кодирования при наличии точной границы множества разреза была выдви-

нута в [11] для ДКРБП и в [12] для ДСБП (см. также [13, Приложение C]). К сожа-

лению, как обнаружили авторы настоящей статьи, некоторые шаги доказательств,

основанные на методе информационных спектров [14], неполны (см. замечание 2

ниже).

В нашей предыдущей работе [15], мотивированной работой [16], для доказатель-

ства сильного обращения теоремы кодирования для определенных классов ДСБП

с точной границей множества разреза использовались свойства условного расхожде-

ния Реньи. Эти классы включали в себя линейные детерминированные многоадрес-

ные сети [10], многоадресные сети одновременной передачи сообщений, состоящие

из независимых ДКБП [17] и беспроводные сети со стиранием [18], но не включа-

ли следующие сети с точной границей множества разреза: ухудшенные ДКРБП [4],

ухудшенные ДСБП [6,7], полудетерминированные ДКРБП [8] и ДКРБП с ортого-

нальными компонентами на передающем конце [9]. Настоящая статья значительно

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

ние теоремы кодирования для всех ДСБП с точной границей множества разреза,

включая вышеупомянутые четыре сети, не охваченные предыдущей работой. Более

подробное обсуждение см. в замечании 4.

Наше обобщение доказательства сильного обращения теоремы кодирования для

ДСБП на гауссовские сети далеко не очевидно, в основном благодаря тому, что

доказательство сильного обращения теоремы кодирования для ДСБП основано на

методе типов [19, гл. 2]. Действительно, сильное обращение теоремы кодирования

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

случае, если вместо ограничений на мощность почти наверное используются огра-

ничения на мощность в длительном режиме, как доказано в [20] для гауссовского

ухудшенного канала с ретрансляцией и в [21] для гауссовского канала множествен-

ного доступа (КМД) с обратной связью. Поскольку в существующей литературе

нет окончательных утверждений о сильном обращении теоремы кодирования для

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

теоремы кодирования для гауссовских сетей с точной границей множества разреза

при ограничениях на мощность почти наверное.

1.2. Основные результаты. Первый результат настоящей статьи - независимое

доказательство сильного обращения теоремы кодирования для ДСБП с точной гра-

ницей множества разреза. Более точно, мы доказываем, что для заданной ДСБП

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

с асимптотической вероятностью ошибки, равной ε, должно содержаться в области,

задаваемой границей множества разреза, при ε ∈ [0, 1). Доказательство основано на

методе типов [19, гл. 2]. В основе техники доказательства лежат идеи работы [22],

в которой была полностью охарактеризована функция надежности любого дискрет-

ного канала без памяти (ДКБП) с обратной связью для скоростей выше пропуск-

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

Важными следствиями этого результата являются новые сильные обращения теоре-

мы кодирования для ухудшенного ДКРБП [4], общего канала с ретрансляцией (КР)

с обратной связью [4], ухудшенной ДСБП [6,7], полудетерминированного ДКРБП [8]

и ДКРБП с ортогональными компонентами на передающем конце [9].

Второй результат настоящей статьи - обобщение полученного доказательства

сильного обращения теоремы кодирования на гауссовские сети, в которых шумом

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

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

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

Более точно, метод типов для ДСБП основан на подсчете, поскольку входной и вы-

ходной алфавиты в ДСБП конечны. Напротив того, метод типов для гауссовских се-

тей основан на аккуратной аппроксимации и квантовании, поскольку входной и вы-

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

Имеется еще одно ключевое отличие между доказательствами для ДСБП в § 5 и для

гауссовских сетей в § 7: в доказательстве для гауссовских сетей приходится избегать

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

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

этого в определении 15 мы модифицируем наше определение классов совместных

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

зательстве. Доказательство же для ДСБП в § 5, наоборот, в значительной степени

опирается на определение условных типов. Важными следствиями этого результата

являются новые сильные обращения теоремы кодирования для гауссовского ухуд-

шенного КР [4], общего гауссовского КР с обратной связью [4], гауссовского КР

с разделением частот на передающем конце [9] и гауссовского КМД с обратной свя-

зью при ограничениях на мощность почти наверное [23]¹.

1.3. Структура статьи. Статья организована следующим образом. Используемые

в статье обозначения описаны в п. 1.4. В § 2 дается формулировка задачи для ДСБП

и ее области пропускной способности при ε ∈ [0, 1) и приводится первый основной

результат настоящей статьи - сильное обращение теоремы кодирования для ДСБП

¹ Хотя схема достижимости, предложенная в [23], удовлетворяет только ограничениям на мощ-

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

мощность почти наверное.

с точной границей множества разреза. В § 3 дается формулировка задачи для гаус-

совской сети и ее области пропускной способности при ε ∈ [0, 1) и приводится вто-

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

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

необходимые для доказательства первой теоремы, содержатся в § 4, в том числе хо-

рошо известные результаты, основанные на методе типов. В § 5 дается доказатель-

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

доказательства второго результата, содержатся в § 6, где объясняется построение и

квантование гауссовских типов. В § 7 приведено доказательство второго основного

результата, а в § 8 даны заключительные замечание.

1.4. Обозначения. Множества натуральных, действительных и неотрицательных

действительных чисел обозначаются через N, R и R₊ соответственно. Единичная

матрица размерности N обозначается через I_N , нулевой вектор длины N - через 0^N ,

нулевая матрица размера N₁ × N₂ обозначается через 0N1×N2, а матрица размера

N₁ × N₂ из всех единиц - через 1N1×N2. Для любой вещественной матрицы K че-

рез K^t обозначается транспонированная матрица. Для квадратной матрицы K через

|K| и tr(K) обозначаются ее определитель и след соответственно. Если K симмет-

рична, то записи K ≻ 0 и K ≽ 0 означают, что K положительно определена или

положительно полуопределена соответственно. Через K-1 обозначается обратная

матрица для любой обратимой матрицы K. Для двух вещественных матриц A и B

одной размерности записи A < B, A ≤ B, A ≥ B и A = B обозначают соответ-

ствующие поэлементные соотношения между A и B. По всей статье все логарифмы

берутся по основанию e.

Через P{E} будем обозначать вероятность события E, а через 1{E} - индика-

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

(например, X), а их реализации и алфавиты - соответствующими прописными (на-

пример, x) и рукописными (например, X ) буквами соответственно. Через Xⁿ будем

обозначать набор случайных величин (X₁, X₂, . . . , X_n), где все компоненты X_k име-

ют один и тот же алфавит X . Для любых случайных величин X и Y (обе могут быть

дискретными, непрерывными, или одна дискретной, а другая непрерывной) через p_X

и pY |X будем обозначать распределение вероятностей X и условное распределение

вероятностей Y относительно X соответственно. Через p_Xp_Y|X обозначается сов-

местное распределение пары (X, Y ), т.е. p_X p_Y|X (x, y) = p_X (x)p_Y|X (y | x) для любых

x и y. Математическое ожидание случайной величины X обозначается через E[X].

Для любой дискретной случайной величины (U, X, Y, Z) с распределением p_U,X,Y,Z

будем обозначать через HpU,X,Y,Z (X | Z) или просто HpX,Z (X | Z) энтропию X при

условии Z, а через IpU,X,Y,Z (X; Y | Z) или просто IpX,Y,Z (X; Y | Z) - взаимную ин-

формацию между X и Y при условии Z. Для любых r_X, p_Y|X и q_Y|X, таких что

rX pY |X абсолютно непрерывно относительно rX qY |X , относительная энтропия меж-

ду p_Y|X и q_Y|X при условии r_X конечна и обозначается через D(p_Y|X ∥ q_Y|X | r_X ).

L₁-расстояние между двумя распределениями p_X и q_X на одном и том же дискрет-

ном алфавите X , обозначаемое через ∥p_X - q_X ∥L1, определяется как

∑

|p_X (x) - q_X (x)|.

x∈X

= [Z₁ Z₂ . . . Z_N ]^t со сред-

ним μ ∈ R^N и ковариационной матрицей Σ ∈ R^N×N через

√

e-2 (z-μ)tΣ-1(z-μ)

(1)

(2π)^N |Σ|

обозначается соответствующая плотность вероятности.

§ 2. Дискретная сеть без памяти и первый основной результат

Рассматривается сеть общего вида, состоящая из N узлов. Пусть

= {1, 2, . . ., N}

- множество индексов узлов. Эти N узлов обмениваются информацией за n интер-

валов времени следующим образом. Узел i выбирает сообщение W_i,j из алфавита

= {1, 2, . . ., ⌈enRi,j ⌉}

(2)

согласно равномерному распределению и посылает W_i,j узлу j для всех (i, j) ∈ I ×I,

где R_i,j характеризует скорость передачи сообщения W_i,j и все сообщения взаимно

независимы. Для каждого k ∈ {1, 2, . . . , n} и каждого i ∈ I в k-м интервале времени

узел i передает элемент X_i,k ∈ X_i, зависящий от {W_i,ℓ : ℓ ∈ I} и Yk-1i, и получает

элемент Y_i,k ∈ Y_i, где X_i и Y_i - некоторые алфавиты, возможно, зависящие от i.

Получив n символов за n интервалов времени, узел j объявляетWi,j переданным

сообщением W_i,j на основе {W_j,ℓ : ℓ ∈ I} и Y^nj для каждых (i, j) ∈ I × I.

Для упрощения обозначений будем использовать следующие соглашения для лю-

бого непустого множества T ⊆ I. Для любого случайного вектора

[X₁ X₂ . . . X_N ]^t ∈ X₁ × X₂ × . . . × X_N

пусть

= [X₁ X₂ . . . X_N ]^t

обозначает весь вектор целиком,

∏

= X_i

i=1

- алфавит вектора X,

= [X_i : i ∈ T ]^t

- подвектор вектора X, а X_T - алфавит подвектора X_T . Аналогично для любого

k ∈ {1,2,...,n} и любого случайного вектора

[X1,k X2,k . . . X_N,k]^t ∈ X₁ × X₂ × . . . × X_N

пусть

= [X1,k X2,k . . . X_N,k]^t ∈ X

обозначает весь вектор целиком, а

= [X_i,k : i ∈ T ]^t ∈ X_T

- подвектор вектора X_k. Для любых непустых множеств T₁, T₂ ⊆ I и любого

N²-мерного случайного вектора

[W1,1 W1,2 . . . W_N,N ]^t ∈ W1,1 × W1,2 × . . . × W_N,N

пусть

= [W1,1 W1,2 . . . W_N,N ]^t

- весь вектор целиком,

∏

W_i,j

i=1 j=1

- алфавит вектора W,

= [W_i,j : (i, j) ∈ T₁ × T₂]

- подвектор вектора W , а WT1×T2 - алфавит подвектора WT1×T2. Следующие шесть

определений дают формальное описание ДСБП и ее области пропускной способ-

ности.

Определение 1. Дискретная сеть состоит из N конечных входных множеств

X₁, X₂, . . . , X_N , N конечных выходных множеств Y₁, Y₂, . . . , Y_N и матрицы перехо-

да q_Y|X . Дискретная сеть обозначается через (X , Y, q_Y|X ). Для каждого непустого

множества T ⊊ I маргинальное распределение q_Y

Tc |X определяетсякак

∑

q_Y

q_Y|X(y |x)

yT ∈YT

для всех x ∈ X и всех y_T c ∈ Y_T c .

= [R1,1 R1,2 . . . R_N,N ]^t ≥ 0N2 обозна-

чен N²-мерный вектор скоростей, для n обращений к дискретной сети (X , Y, q_Y|X )

состоит из следующих элементов:

1. Множество сообщений W_i,j узла i для каждого (i, j) ∈ I × I в соответствии с

определением в (2). Сообщение W_i,j равномерно на W_i,j ;

2. Кодирующая функция

f_i,k : W_{i}×I × Yk-1i → X_i

для каждого i ∈ I и каждого k ∈ {1, 2, . . . , n}, где f_i,k - кодирующая функция в

узле i в k-м интервале времени, такая что²

X_i,k = f_i,k(W_{i}×I, Yk-1i);

3. Декодирующая функция

ϕ_i : W_{i}×I × Yⁿⁱ → W_I×{i}

для каждого i ∈ I, где ϕ_i - декодирующая функция для W_I×{i} в узле i, такая

что

WI×{i} = ϕi(W{i}×I ,

Определение 3. Дискретная сеть (X,Y,q_Y|X) с многократным обращени-

ем к ней называется дискретной сетью без памяти (ДСБП), если для любого

(n, R)-кода выполняется следующее условие:

Пусть Uk-1 = (W , Xk-1, Yk-1) - набор случайных величин, порожденных до

k-го интервала времени. Тогда для любого k ∈ {1, 2, . . ., n} и любого множества

T ⊊ I равенство

P{Uk-1 = uk-1, X_k = x_k, Y_T c_,k = y_T c_,k} =

= P{Uk-1 = uk-1, X_k = x_k}q_Y

Tc |X(^yT^c,k^|xk⁾

² По определению полагаем, что областью определения функции fi,1 является W_{i}×I × ∅.

имеет место для любых uk-1 ∈ Uk-1, x_k ∈ X и y_T c_,k ∈ Y_T c .

Замечание 1. Определение 3 согласуется с определением ДКБП с обратной свя-

зью, данным Мэсси в [24]. Как указано в [24], для определения ДСБП нельзя исполь-

∏

зовать

q_Y|X(y_k |x_k) из-за наличия обратной связи, учитываемой кодирующими

k=1

функциями в определении 2.

Определение 4. Для (n,R)-кода можно вычислить среднюю вероятность

ошибки декодирования

}

{⋃

{ϕ_i(W_{i}×I, Yⁿⁱ) = W_I×{i}}

i∈I

Тогда (n, R)-код со средней вероятностью ошибки декодирования не выше ε_n будем

называть (n, R, ε_n)-кодом.

Определение 5. Вектор скоростей R ∈ RN2+ называется ε-достижимым, если

существует последовательность (n, R, ε_n)-кодов, такая что limsup ε_n ≤ ε.

n→∞

Без ограничения общности всюду далее будем полагать, что R_i,i = 0 для любого

i∈I.

Определение 6. Будем называть ε-областью пропускной способности ДСБП

и обозначать через C_ε замыкание множества, состоящего из всех ε-достижимых век-

торов скоростей R с R_i,i = 0 для всех i ∈ I. Область пропускной способности

определяется как 0-область пропускной способности C₀.

Первым основным результатом настоящей статьи является

Теорема 1. Пусть (X,Y,q_Y|X) - ДСБП. Определим

{

∑

}



⋃

⋂



R_i,j ≤ IpX q_Y

(X_T ; Y_T c | X_T c ),

Tc|X



i,j)∈T ×T^c

(3)

R ∈ RN2+

(

pX T ⊊I

R_i,i = 0 для всех i ∈ I

T =∅

Тогда для любого ε ∈ [0, 1)

C_ε ⊆ R_cut-set.

(4)

Замечание 2. Авторы работ [12,13] выдвинули гипотезу, что сильное обращение

теоремы кодирования должно выполняться для ДСБП общего вида с точной гра-

ницей множества разреза, и для доказательства этого применяли технику инфор-

мационных спектров. Однако четвертое равенство в цепочке равенств после фор-

мулы (C.8) в работе [13] может не выполняться, и тем самым, первый шаг дока-

зательства в [12, раздел IV.B] не завершен. Следовательно, в представленном там

доказательстве имеется пробел. Наше доказательство теоремы 1 не использует ме-

тоды информационных спектров. Вместо этого мы применяем метод типов и уста-

навливаем сильное обращение теоремы кодирования для ДСБП с точной границей

множества разреза.

Замечание 3. Из теоремы 1 видно, что граница множества разреза, указанная

в (4), является универсальной внешней границей на C_ε для всех 0 ≤ ε < 1, откуда

вытекает сильное обращение теоремы кодирования для класса всех ДСБП, у кото-

рых границы множества разреза достижимы. Как отмечено в первой части п. 1.2,

этот класс включает в себя ухудшенный ДКРБП [4], общий КР с обратной свя-

зью [4], ухудшенная ДСБП [6, 7], полудетерминированный ДКРБП [8] и ДКРБП

с ортогональными компонентами на передающем конце [9].

Замечание 4. Теорема 1 устанавливает сильное обращение теоремы кодирования

для любой ДСБП с точной границей множества разреза при условии множествен-

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

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

вает наш предыдущий результат [15] о сильном обращении теоремы кодирования

для некоторых классов ДСБП с точной границей множества разреза при условии

многоадресной передачи, когда каждый источник передает единственное сообщение,

а каждый получатель стремится восстановить сообщения от всех источников. Более

точно, наше предыдущее сильное обращение теоремы кодирования применительно

к сценарию множественной одноадресной передачи утверждает, что

C_ε ⊆ R_out

для всех ε ∈ [0, 1), где

{

∑

}



⋂

⋃



R_i,j ≤ IpX q_Y

(X_T ; Y_T c | X_T c ),

Tc|X



i,j)∈T ×T^c

(5)

R ∈ RN2+

(

T⊊I

R_i,i = 0 для всех i ∈ I

T =∅

Сравнивая (3) и (5), мы видим, что операции объединения и пересечения поменя-

лись местами, и поэтому имеет место включение R_cut-set ⊆ R_out, причем для многих

классов сетей это включение строгое. Таким образом, теорема 1 значительно сильнее

основной теоремы работы [15]. В частности, теорема 1 устанавливает сильное обра-

щение теоремы кодирования для следующих четырех видов сетей: физически ухуд-

шенный ДКРБП, физически ухудшенная ДСБП, полудетерминированный ДКРБП

и ДКРБП с ортогональными компонентами на передающем конце. Сильные обра-

щения теоремы кодирования для этих важных видов сетей не были доказаны в [15].

Доказательство теоремы 1 основано на методе типов [19], т.е. абсолютно иное по

сравнению с подходом работы [15], основанным на расхождении Реньи. Вызыва-

ет интерес (у авторов) задача попробовать доказать теорему 1 с помощью других

стандартных техник доказательства сильных обращений теоремы кодирования, та-

ких как подход, основанный на расхождении Реньи [15,16], метод информационных

спектров [14], лемма о раздувании [19,25] и метод обратных гиперсжимающих отоб-

ражений [26]. В частности, метод обратных гиперсжимающих отображений кажется

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

вспомогательные случайные величины, а граница множества разреза их не содер-

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

∏

основаны на анализе каналов-произведений

q_Y|X(y_k |x_k), то согласно замеча-

k=1

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

кодирования для ДСБП с обратной связью.

Замечание 5. Из доказательства теоремы 1 вытекает, что для любого фиксиро-

ванного вектора скоростей R, лежащего вне границы множества разреза R_cut-set,

средние вероятности правильного декодирования для любой последовательности

(n, R)-кодов стремятся к 0 экспоненциально быстро (о полученной верхней границе

на доасимптотическую вероятность правильного декодирования см. формулу (40)

в доказательстве). Другими словами, доказано экспоненциальное сильное обраще-

ние теоремы кодирования для сетей с точной границей множества разреза (см. ра-

боты [27,28], в которых установлено экспоненциальное сильное обращение теоремы

кодирования для широковещательных каналов). Точная характеризация экспонен-

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

Замечание 6. Доказательство теоремы 1 использует идеи двух работ, основан-

ных на методе типов [19]. Во-первых, в [29] показано, что технику доказательств,

используемую для анализа функций надежности ДКБП с обратной связью, можно

применить к ДКРБП. Во-вторых, в [22] были полностью описаны функции надежно-

сти любого ДКБП с обратной связью при скоростях выше пропускной способности.

Эти идеи используются в доказательстве теоремы 1.

Пример 1. Рассмотрим ДКРБП с тремя узлами, где источник, ретранслятор

и получатель пронумерованы индексами 1, 2 и 3 соответственно. Источник переда-

ет сообщение получателю с помощью ретранслятора, и нас интересует пропускная

способность, определяемая как

= max {R1,3 | R ∈ C₀} .

(6)

Пропускная способность ДКРБП в общем случае неизвестна. Однако если существу-

ет бесшумный канал обратной связи, передающий Yk-13 узлу 2 в каждом интервале

времени k, то пропускная способность получаемого ДКРБП с обратной связью сов-

падает с границей множества разреза max {R1,3 | R ∈ R_cut-set} [1, раздел 17.4], что

интуитивно ясно, поскольку канал обратной связи превращает ДКРБП в физически

ухудшенный ДКРБП. Поэтому из теоремы 1 следует, что ДКРБП с обратной связью

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

При этом добавление двух бесшумных каналов обратной связи, по которым Yk-12

и Yk-13 передаются узлу 1 в каждом интервале времени k, не приводит к дальней-

шему увеличению пропускной способности ДКРБП с обратной связью, и поэтому

в этой постановке также выполняется сильное обращение теоремы кодирования.

§ 3. Гауссовская сеть и второй основной результат

В этом параграфе рассматривается гауссовская сеть, устроенная следующим об-

разом. Для каждого k ∈ {1, 2, . . . , n} и каждого i ∈ I узел i передает X_i,k ∈ R,

зависящее от {W_i,ℓ : ℓ ∈ I} и Yk-1i, и получает

∑

Y_i,k =

g_ijX_j,k + Z_i,k

j=1

в k-м интервале времени, где g_ij ∈ R описывает постоянный коэффициент усиления

канала, связанного с прохождением сигнала от узла j до узла i, а Z_i,k - аддитивный

гауссовский шум в узле i. Каждый узел i ∈ I подчиняется ограничению на мощность

почти наверное [1, формула (17.4)]

}

∑

^{1

X²

≤P_i

= 1,

(7)

i,k

k=1

где Pi > 0 - некоторая константа, описывающая допустимую мощность для уз-

= [g_ij ](i,j) ∈ I × I - (N × N)-матрица коэффици-

= [Z1,k Z2,k . . . Z_N,k]^t -

гауссовский вектор с нулевым средним и ковариационной матрицей Σ ≻ 0, где Σ

характеризует корреляцию между N случайными величинами гауссовского шума.

Соотношение между X_k и Y_k можно записать для каждого k ∈ {1, 2, . . . , n} следу-

ющим образом:

Y k = GXk + Zk.

(8)

Получив n символов за n интервалов времени, узел j объявляетWi,j полученным

сообщением W_i,j на основе {W_j,ℓ : ℓ ∈ I} и Y^nj для всех (i, j) ∈ I × I.

Для упрощения обозначений будем использовать следующее соглашение для лю-

бых непустых множеств T₁, T₂ ⊆ I: для (N ×N)-матрицы G = [g_ij](i,j) ∈ I × I будем

обозначать через

GT1×T2 = [gij](i,j)∈T1×T2

подматрицу матрицы G.

= [P₁ P₂ . . . P_N ]^t > 0^N обозначает

N-мерный вектор, задающий допустимую мощность, для гауссовской сети называ-

ется (n, R)-код в смысле определения 2 со следующими дополнительными предпо-

ложениями: X = Y = R, и ограничение на мощность (7) выполнено для любого

i∈I.

Определение 8. Гауссовская сеть, обозначаемая через (G,Σ), задается мат-

рицей коэффициентов усиления G ∈ R^N×N , вещественной ковариационной матри-

цей Σ ≻ 0 размера N × N и условным распределением q_Y|X , где

= N(y;Gx,Σ),

такими что для любого (n, R, P )-кода выполнено следующее условие:

Пусть Uk-1 = (W , Xk-1, Yk-1) - набор случайных величин, порожденных до

k-го интервала времени. Тогда для любого k ∈ {1, 2, . . ., n} и любого T ⊊ I имеет

место равенство

p_Uk-1_,X

(uk-1, x_k, y_T c_,k) = p_U k-1_,X

(uk-1, x_k)q_Y

k,YTc,k

Tc |X(^yT^c,k^|xk⁾

для всех uk-1, x_k и y_T c_,k, где q_Y

Tc |X -маргинальноераспределениедляqY |X^,опре-

деляемое как

⎧

∫

⎨

q_Y|X(y |x)dy_T , если T = ∅,

qYTc |X(yTc |x)=

R^|T|

⎩

q_Y|X(y |x)

в противном случае,

для всех x и всех y_T c.

Средняя вероятность ошибки декодирования для (n, R, P )-кода задается анало-

гично определению 4. При этом вектор скоростей R ∈ RN2+ называется ε-дости-

жимым, если существует последовательность (n, R, P , ε_n)-кодов, для которой

lim sup ε_n ≤ ε, а ε-область пропускной способности гауссовской сети, обозначаемая

n→∞

через C_ε, - это замыкание множества, состоящего из всех ε-достижимых векторов

скоростей. Область пропускной способности определяется как 0-область пропуск-

ной способности C₀.

Вторым основным результатом настоящей статьи является

Теорема 2. Пусть (G,Σ) - гауссовская сеть. Для любой ковариационной

матрицы K размера N × N и любого непустого множества T ⊊ I обозначим

через K_T|Tc условную ковариацию X_T относительно X_Tc, когда X ∼ N(x; 0^N, K),

т.е.

[

]]

= E

(X_T - E[X_T | X_T c])(X_T - E[X_T | X_T c])^t | X_T c

(9)

Пусть

{



}



K ≽ 0, где i-й диагональный элемент k_ii удо-

= K ∈R^N×N



(10)

влетворяет условию k_ii ≤ P_i для всех i ∈ I

- множество ковариационных матриц, характеризующих корреляцию между пе-

редаваемыми символами. Положим

⎧



⎫

∑



⎪

R_i,j ≤

log

^I_|Tc_| +

⎪



⎨

⎬

⋃

⋂



(i,j)∈T ×T^c



R ∈ RN2+

(11)

⎪



+ G_Tc×T KT |TcG^tTc×T (ΣTc×Tc)-1

^,⎪

K∈S(P ) T⊊I

⎩



⎭



T =∅

R_i,i = 0 для всех i ∈ I

Тогда для любого ε ∈ [0, 1)

C_ε ⊆ R_cut-set.

(12)

Замечание 7. Из теоремы 2 видно, что граница множества разреза, данная в (12),

является универсальной внешней границей на C_ε для всех 0 ≤ ε < 1, откуда вытека-

ет утверждение сильного обращения теоремы кодирования для класса гауссовских

сетей, для которых границы множества разреза являются достижимыми при огра-

ничениях на мощность почти наверное (7). Этот класс включает в себя гауссовский

ухудшенный канал с ретрансляцией [4], общий гауссовский КР с обратной связью [4],

гауссовский КР с частотным разделением на передающем конце [9] и гауссовский

КМД с обратной связью.

Замечание 8. Из доказательства теоремы 2 вытекает, что для любого фиксиро-

ванного вектора скоростей R, лежащего вне границы множества разреза R_cut-set,

средние вероятности правильного декодирования для любой последовательности

(n, R, P )-кодов стремятся к 0 экспоненциально быстро (о полученной верхней гра-

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

лу (101) в доказательстве). Другими словами, доказано экспоненциальное сильное

обращение теоремы кодирования (см. [27, 28]) для гауссовских сетей с достижимой

границей множества разреза. Точная характеризация экспоненты сильного обраще-

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

Пример 2. Рассмотрим гауссовский КР с тремя узлами, где источник, ретранс-

лятор и получатель пронумерованы индексами 1, 2 и 3 соответственно. Предполо-

жим, что узлы 1 и 2 удовлетворяют условию ограничения на мощность почти на-

верное (7). Пропускная способность этого гауссовского КР в смысле (6) в общем

виде неизвестна. Однако если существует бесшумная линия обратной связи, пере-

дающая Yk-13 узлу 2 на каждом интервале времени k, то пропускная способность

полученного гауссовского КР с обратной связью совпадает с границей множества

разреза max{R1,3 | R ∈ R_cut-set} [1, раздел 17.4], что интуитивно ясно, поскольку

наличие канала обратной связи преобразует гауссовский КР в гауссовский ухуд-

шенный КР. Поэтому из теоремы 2 следует, что гауссовский КР с обратной связью

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

При этом добавление двух бесшумных каналов обратной связи, по которым Yk-12

и Y k-13 передаются узлу 1 на каждом интервале времени k, не приводит к дальней-

шему увеличению пропускной способности ДКРБП с обратной связью, и поэтому

в этой постановке также имеет место сильное обращение теоремы кодирования. Од-

нако если ограничения на мощность почти наверное (7) заменить на ограничения

на мощность в длительном режиме

[

]

∑

X²

i,k

≤P_i,

(13)

k=1

то, как доказано в [20], гауссовский КР уже не будет удовлетворять условию силь-

ного обращения теоремы кодирования.

Пример 3. Рассмотрим гауссовский КМД с обратной связью с двумя источни-

ками, пронумерованными индексами 1 и 2 соответственно, и получателем, имеющим

индекс 3. Пусть узлы 1 и 2 удовлетворяют ограничениям на мощность почти навер-

ное (7). Кроме того, существует бесшумная линия обратной связи, по которой Yk-1

предается обоим узлам 1 и 2 в каждом интервале времени k. Нас интересует область

пропускной способности, определяемая как

= {(R1,3, R2,3) | R ∈ C₀}.

Хотя предложенная в [23] схема достижимости, позволяющая достичь границы

множества разреза {(R1,3, R2,3) | R ∈ R_cut-set}, удовлетворяет лишь ограничению на

мощность в длительном режиме (13), ее нетрудно модифицировать так, чтобы вы-

полнялись ограничения на мощность почти наверное (7). Тем самым, область про-

пускной способности этого гауссовского КМД с обратной связью совпадает с гра-

ницей множества разреза. Поэтому из теоремы 2 вытекает, что гауссовский КМД

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

ния. Однако если ограничения на мощность почти наверное (7) заменить на ограни-

чения на мощность в длительном режиме (13), то, как доказано в [21], гауссовский

КМД с обратной связью уже не будет удовлетворять свойству сильного обращения

теоремы кодирования.

§4. Предварительные сведения для доказательства теоремы 1: метод типов

Перечислим стандартные определения и результаты [19, гл. 2]. Типом последо-

вательности xⁿ ∈ Xⁿ, который обозначается через ϕ[xn]_X, называется эмпирическое

распределение выборки xⁿ, т.е.

N (a | xⁿ)

для всех a ∈ X , где через N(a | xⁿ) обозначено число появлений символа a в xⁿ.

Множество всех возможных типов последовательностей из Xⁿ обозначается через

{

ϕ[xn]_X | xⁿ ∈ Xⁿ}.

Аналогично, множество всех возможных типов последовательностей из Yⁿ при усло-

вии типа r_X ∈ P_n(X ) обозначается через

{



= s_Y|X

 существует пара (xⁿ, yⁿ), такая что ϕ[xn]_X = r_X и

}

ϕ[(xn,yn)]X,Y = r_Xs_Y|X

Для заданного типа r_X ∈ P_n(X ) его классом называется

{

T(n)r

^def=

xⁿ ∈ Xⁿ | ϕ[xn]_X = r_X}.

Хорошо известна граница для числа типов

|P_n(X )| ≤ (n + 1)^|X|.

(14)

Мы будем часто использовать без явного объяснения следующий факт: для любого

rX ∈ Pn(X ), любого sY |X ∈ Pn(Y | rX ) и любой матрицы перехода qY |X справедливо

следующее равенство для всех (xⁿ, yⁿ) ∈

rXsY |X :

∏

q_Y|X(y_k |x_k) =

q_Y|X(y |x)nrX (x)sY|X (y|x) =

k=1

x,y

(

)

=e-nHrXsY|X(Y|X)+D(sY|X∥qY|X|rX) .

§ 5. Доказательство теоремы 1

В этом параграфе будет показано, что

C_ε ⊆ R_cut-set

(15)

для всех ε ∈ [0, 1), где R_cut-set определено в (3). Достаточно показать, что для любого

R ∈ R_cut-set и любой последовательности (n,R,ε_n)-кодов выполняется

lim

ε_n = 1.

(16)

n→∞

Для доказательства зафиксируем вектор скоростей R ∈ R_cut-set и последователь-

ность (n, R, ε_n)-кодов.

5.1. Связь R с границей множества разреза. Так как R ∈ R_cut-set, а область

R_cut-set замкнута, всегда найдется положительное число δ, такое что для любого

распределения r_X на X существует непустое множество VrX ⊊ I, для которого

∑

R_i,j ≥ IrX q_Y

(XVr ; Y_V c

|X_Vc) + δ,

(17)

(i,j)∈Vr ×Vr

где сокращенная запись V_r используется для обозначения VrX .

5.2. Упрощение вероятности правильного декодирования с учетом дискретности

и отсутствия памяти. Зафиксируем натуральное n, и пусть pW,Xn,Y n,W^{-распре-}

деление вероятностей, индуцированное (n, R, ε_n)-кодом. Если не будет оговорено

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

вычисляются в соответствии с pW,Xn,Y n, W^{.Рассмотримвероятностьправильного}

декодирования

}

∑ {⋂{

}

1-ε_n =

ϕ_i(w_{i}×I, Yⁿⁱ) = w_I×{i}

W =w .

(18)

|W|

w∈W

i∈I

Чтобы упростить правую часть равенства (18), для каждого w ∈ W запишем

}

{⋂{

}

ϕ_i(w_{i}×I, Yⁿⁱ) = w_I×{i}

W =w

i∈I

}

∑

{⋂{

}

p_Y n |W =w(yⁿ) × 1

ϕ_i(w_{i}×I, yⁿⁱ) = w_I×{i}

yⁿ∈Yⁿ

i∈I

∑

∏

p_Yk |Y k-1,W_{i}×I=w_{i}×I (yk | yk-1) ×

yⁿ∈Yⁿ k=1

}

{⋂{

}

×1

ϕ_i(w_{i}×I, yⁿⁱ) = w_I×{i}

^(a)=

i∈I

∑

∏

(

)

(a)

p_Y

y_k |(f_i,k(w_{i}×I, yk-1i) : i ∈ I)

k|Xk

yⁿ∈Yⁿ k=1

}

{⋂{

}

×1

ϕ_i(w_{i}×I, yⁿⁱ) = w_I×{i}

(19)

i∈I

где (a) вытекает из следующего равенства, справедливого для всех yⁿ ∈ Yⁿ и всех

k ∈ {1,2,...,n} согласно определению кода (определение 2), а также свойствам

дискретности и отсутствия памяти сети, вытекающим из определения 3:

p_Y

(y_k | yk-1) =

k|Yk-1,W{i}×I=w{i}×I

(

)

=p_Y

y_k |(f_i,k(w_{i}×I, yk-1i) : i ∈ I), yk-1

k|Xk,Yk-1,W{i}×I=w{i}×I

(

)

=p_Y

y_k |(f_i,k(w_{i}×I, yk-1i) : i ∈ I)

k|Xk

Чтобы упростить обозначения, для любого T ⊊ I:

= ϕ_i(w_{i}×I, yⁿⁱ),

^def= (

w_I×I, положим

= f_i,k(w_{i}×I, yk-1i),

(

)

x_i,k(w_{i}×I, yk-1i) : i ∈ T^c

= x_I,k(w_I×I, yk-1I),

(

)

x_Tc,1(w_Tc_×I), x_Tc,2(w_Tc_×I, y_Tc,1), . . . , x_Tc_,n(w_Tc_×I, yn-1Tc)

(

)

x₁(w), x₂(w, y₁), . . . , x_n(w, yn-1)

Перепишем (19) в виде

}

{⋂{

}

ϕ_i(w_{i}×I, Yⁿⁱ) = w_I×{i}

W =w =

i∈I

∑

∏

pYk |X_k (yk |xk(w, yk-1)) × 1{w = w}.

(20)

yⁿ∈Yⁿ k=1

5.3. Дальнейшее упрощение вероятности правильного декодирования с помощью

метода типов. Для любого w ∈ W, любого типа r_X ∈ P_n(X ) и любого условного

типа s_Y|X ∈ P_n(Y | r_X ) определим

{

}

yⁿ ∈ Yⁿ | (xⁿ(w, yn-1), yⁿ) ∈ T(n)

(21)

rX sY |X

и для любого непустого T ⊊ I и любого w_T c_×I ∈ W_T c_×I положим

F_T (w_Tc_×I; r_X, s_Y

⎧

⎫

(

)



⎨



x^nTc (wTc×I, y^Tc ), y^Tc

∈

где⎬

uXT c,YT c ,



^def=

y^nTc ∈ Y^nTc

(22)



uXTc ,YTc - маргинальный тип rXsYT c |X,

⎩

⎭

ограниченный на (X_Tc, Y_Tc)

Заметим, что множество A(w; r_X, s_Y|X) в (21) играет также ключевую роль в дока-

зательстве верхней границы на функции надежности ДКРБП в работе [29]. Продол-

жая равенство (20) и используя краткое обозначение A(w; r, s) для множества (21),

поскольку множества из набора

{

}

A(w; r, s) | r_X ∈ P_n(X ), s_Y|X ∈ P_n(Y | r_X )

образуют разбиение на Yⁿ, такое что

⋃

Yⁿ =

A(w; r_X , s_Y|X )

rX ∈Pn(X) sY |X ∈Pn(Y|rX )

A(w; r_X , s_Y|X ) ∩ A(w; r^′X , s^′Y|X ) = ∅

для любого (r_X , s_Y|X ) = (r^′X , s^′Y|X ), получаем

∑ n∏

p_Y

k|Xk(^yk^|xk(w,yk-1))×1{w=w}=

yⁿ∈Yⁿ k=1

∑

∏

pYk |X_k (yk |xk(w, yk-1)) × 1{w = w}.

(23)

rX ∈Pn(X) sY |X ∈Pn(Y|rX ) yⁿ∈

k=1

A(w;r,s)

5.4. Оценка вероятности правильного декодирования через F_T (w_T c_×I ; r, s). За-

фиксируем произвольное непустое T ⊊ I. Для упрощения обозначений положим

= HrXs_Y

(Y_T c | X) + D(sYTc |X ∥ qYT c |X | rX ).

(24)

Tc|X

Чтобы упростить правую часть равенства (23), рассмотрим самую внутреннюю сум-

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

rX ∈ Pn(X ), sY |X ∈ Pn(Y | rX ), w ∈ W и yⁿ ∈ A(w; r, s):

∏

pYk |X_k (yk |xk(w, yk-1)) =

k=1

∏

= p_Y

k=1(∏

)

^(b)=

qYTc |X(yTc

|x)nr(x)s(yTc |x)

x,yTc

)

∏

pYT,k |X_k,YT c,k (yT,k |xk(w, yk-1), yTc,k)

⁽²⁴⁾=

k=1

∏

⁽²⁴⁾= e-naT (r,s)

pYT,k |X_k,YT c,k (yT,k |xk(w, yk-1), yTc,k)

(25)

k=1

где равенство (b) вытекает из определения 3 и того факта, что yⁿ ∈ A(w; r, s)

(см. определение множества A(w; r, s) в (21)). Продолжая (23) и вводя обозначе-

ние F_T (w_T c_×I ; r, s) для множества, определенного в (22), рассмотрим следующую

цепочку неравенств для любых r_X ∈ P_n(X ) и s_Y|X ∈ P_n(Y | r_X ):

∑ ∑

∏

p_Y

= e-naT(r,s) ×

k|Xk(^yk^|xk(w,yk-1))×1{w=w}(2

w∈W yⁿ∈

k=1

A(w;r,s)

∑

∏

(c)

p_Y

≤

T ,k |Xk ,YT c,k (^yT,k^|xk(w,yk-1)^,yT^c,k)×1{w=w}

w∈W yⁿ∈

k=1

A(w;r,s)

^(c)≤ e^-naT(r,s) ×

∑

∏

p_Y

T ,k |Xk,YT c,k (^yT,k^|xk(w,yk-1)^,yT^c,k)×

w∈W

ynTc ∈

y^nT ∈Yⁿ

k=1

FT (wT c×I;r,s)

× 1{

w_I×Tc = w_I×Tc}

^(d)=

∑

^(d)= e-naT (r,s)

w_I×Tc = w_I×Tc} = e-naT(r,s) ×

w∈W ynTc∈FT(wTc×I;r,s)

∑

w_I×Tc = w_I×Tc}

^(e)≤

w(T×T c₎c ∈W(T×Tc₎c ynTc ∈FT (wT c×I;r,s) wT×Tc ∈WT ×Tc

∑

^(e)≤ e^-naT(r,s)

w(T×Tc₎c ∈W(T×T c₎c ynTc ∈FT (wT c×I ;r,s)

∑

=e-naT(r,s)

|F_T (w_T c_×I ; r, s)|,

(26)

w(T×Tc₎c ∈W(T×T c₎c

где

ветственно;

(d) следует из того, что 1 {wI×Tc = wI×Tc} является функцией от (w, ynTc);

(e) вытекает из следующего неравенства, справедливого благодаря тому, что

w_I×Tc

является функцией (w(T×T c₎c , y^nTc ):

∑

w_I×Tc = w_I×Tc} ≤ 1

wT×Tc ∈WT×T c

для любого (w(T×T c₎c , y^nTc ) ∈ W(T×T c₎c × Y^nTc .

5.5. Оценка мощности множества F_T (w_T c_×I ; r, s). Для любых r_X ∈ P_n(X ) и

s_Y|X ∈ P_n(Y |r_X), обозначим через u_X

Tc ,YT c маргинальныйтип,индуцированный

распределением r_X sYTc |X , и выведем следующую верхнюю границу на величину

|F_T (w_T c_×I ; r, s)|. Для любых r_X ∈ P_n(X ), s_Y|X ∈ P_n(Y | r_X ) и w_T c_×I ∈ W_T c_×I ,

поскольку

∑

∏

uYTc |XT c (yT^c,k |xT^c,k(wT^c×I, y^T

)) ≤ 1,

yⁿ

Tc ∈FT(wTc×I;r,s)k=1

то получаем

∑

∏

u_Y

Tc |XT c (^yT^c |xT^c )nuXTc,YTc (xTc ,yTc )≤1

yⁿ

Tc ∈FT(wTc×I;r,s)xTc ,yTc

(см. определение множества F_T (w_T c_×I ; r, s) в (22)), откуда следует, что

∑

e-nHuXTc,YT c(YTc |XTc ) ≤ 1,

yⁿ

Tc ∈FT(wTc×I;r,s)

из чего, в свою очередь, вытекает, что

(YT c |XT c )

|F_T (w_T c_×I ; r, s)| ≤ enHuXT c,YT c(YTc |XTc ) = enHrXsYT c

(27)

Объединяя (26), (24) и (27) и используя тот факт, что в силу (24) справедлива оценка

∑

|W(T×T c₎c |

-n

∏

≤e(i,j)∈T×Tc

R^i,j ,

|W|

⌈enRi,j⌉

(i,j)∈T ×T^c

для любых r_X ∈ P_n(X ) и s_Y|X ∈ P_n(Y | r_X ) получаем

∑

∏

pYk |X_k (yk |xk(w, yk-1)) × 1{w = w} ≤

|W|

w∈W yⁿ∈

k=1

A(w;r,s)

(

∑

)

−n

Ri,j -IrX sY

(XT ;YT c |XT c )+D(sYT c |X^∥qYT c |X^|rX⁾

≤e(i,j)∈T×Tc

(28)

Отметим, что неравенство (28) напоминает формулу (5) в [22], полученную при

доказательстве оценки для функций надежности ДКБП с обратной связью.

5.6. Оценка вероятности правильного декодирования через A(w; r, s). Теперь

оценим другим способом левую часть неравенства (28) для любых r_X ∈ P_n(X ) и

s_Y|X ∈ P_n(Y |r_X):

∑

∏

pYk |X_k (yk^|xk(w,yk-1)) × 1{w = w} ≤

|W|

w∈W yⁿ∈

k=1

A(w;r,s)

∑

∏

≤

pYk |X_k (yk^|xk(w,yk-1))⁽

|W|

w∈W yⁿ∈

k=1

A(w;r,s)

∑

∏

^(f)=

q_Y|X(y |x)nr(x)s(y|x) =

|W|

w∈W yⁿ∈

x,y

A(w;r,s)

(

)

-n

HrXsY |X(Y|X)+D(sY |X^∥qY |X|rX )

∑

|A(w; r, s)|

(29)

|W|

w∈W

где равенство (f) следует из определения множества A(w; r, s), данного в (21), и опре-

деления 3.

5.7. Оценка мощности множества A(w; r, s). Для любых r_X ∈ P_n(X ), s_Y|X ∈

∈ P_n(Y |r_X) и w ∈ W, поскольку

∑ n∏

s_Y|X(y_k |x_k(w, yk-1)) ≤ 1,

yⁿ∈A(w;r,s) k=1

то

∑ ∏

s_Y|X(y |x)nr(x)s(y|x) ≤ 1

yⁿ∈A(w;r,s)^x,y

(см. определение множества A(w; r, s) в (21)), откуда получаем

∑

e-nHrXsY |X(Y|X) ≤ 1,

yⁿ∈A(w;r,s)

из чего, в свою очередь, следует, что

|A(w; r, s)| ≤ enHrXsY |X(Y|X).

(30)

Объединяя (29) и (30), получаем, что для любых r_X ∈ P_n(X) и s_Y|X ∈ P_n(Y |r_X )

справедливо неравенство

∑

∏

pYk |X_k (yk |xk(w, yk-1)) × 1{w = w} ≤

|W|

w∈W yⁿ∈

k=1

A(w;r,s)

≤e-nD(sY|X∥qY|X|rX).

(31)

5.8. Связь оценок вероятности правильного декодирования с границей множества

разреза. Вводя обозначения

(

)

∑

−n

Ri,j -IrX sY

(XT ;YT c |XT c )+D(sYT c |X^∥qYT c |X^|rX⁾

= e(i,j)∈T×Tc

(32)

= e-nD(sY|X∥qY|X|rX),

(33)

из (28) и (31) получаем, что для любых r_X ∈ P_n(X ) и s_Y|X ∈ P_n(Y | r_X ) имеет

место оценка

∑

∏

pYk |X_k (yk |xk(w, yk-1)) × 1{w = w} ≤

|W|

w∈W yⁿ∈

k=1

A(w;r,s)

≤ min{α_T (r, s), β(r, s)}.

(34)

Объединяя(18), (20), (23) и используя тот факт, что оценка (34) справедлива для

любых r_X ∈ P_n(X ) и s_Y|X ∈ P_n(Y | r_X ) и произвольного непустого T ⊊ I, заклю-

чаем, что

∑

1-ε_n ≤

min{αVr (r, s), β(r, s)},

(35)

rX ∈Pn(X) sY |X ∈Pn(Y|rX )

где множество V_r ⊆ I следует аккуратно выбрать в зависимости от r_X ∈ P_n(X )

таким образом, чтобы выполнялось условие (17). Отметим, что неравенство (35)

напоминает формулу (7) в [22]. Пусть ξ > 0 - положительная константа, значение

который будет выбрано позже. Тогда из (35) вытекает, что

∑

1-ε_n ≤

min{αVr (r, s), β(r, s)} ×

rX ∈Pn(X) sY |X ∈Pn(Y|rX )

(

{

}

{

})

D(s_Y|X ∥ q_Y|X | r_X ) ≥ ξ

D(s_Y|X ∥ q_Y|X | r_X ) < ξ

(36)

5.9. Оценивание вероятности правильного декодирования двумя способами. Учи-

тывая, что δ > 0 было выбрано таким образом, чтобы выполнялось условие (17),

выберем теперь значение константы ξ > 0 таким образом, чтобы для всех непустых

T ⊊ I было выполнено следующее условие:

|IgX,Y (X_T ; Y_T c | X_T c ) - IhX,Y (X_T ; Y_T c | X_T c )| ≤ δ/2

(37)

для всех распределений g_X,Y и h_X,Y на (X , Y), таких что

√

∥g_X,Y - h_X,Y ∥L1 ≤

2ξ.

Существование такой константы ξ > 0 вытекает из того факта, что отображение

pX,Y → IpX,Y (XT;YTc |XTc) непрерывно относительно L1-метрики для всех непу-

стых T ⊊ I. Продолжая неравенство (36), рассмотрим следующие две цепочки нера-

венств для любых r_X ∈ P_n(X) и s_Y|X ∈ P_n(Y |r_X):

{

}

min{αVr (r, s), β(r, s)} × 1

D(s_Y|X ∥ q_Y|X | r_X ) ≥ ξ

≤

{

} (33)

≤ β(r, s) × 1

D(s_Y|X ∥ q_Y|X | r_X ) ≥ ξ

≤ e^-nξ

(38)

min{αVr (r, s), β(r, s)} × 1{D(s_Y|X ∥ q_Y|X | r_X ) < ξ}

^(g)≤

≤

⁽³⁷⁾≤ αVr (r, s) × 1^{|IrX s_Y|X (XVr ; YV cr | XV c ) -_r

} (32)

- IrXqY |X(XVr; YV ^cr |XV ^c)| ≤ δ/2

≤

(

)

∑

(32)

-n

Ri,j -IrX sY

(XVr;YVcr |XVcr )

Vcr

≤ e(i,j)∈Vr×

{

}

×1

≤

(

)

∑

-n

Ri,j -IrX qY

(XVr;YVcr |XVcr )-δ/2

Vcr

≤e(i,j)∈Vr×

⁽¹⁷⁾≤ e-nδ/2,

(39)

где (g) следует из неравенства Пинскера. Объединяя (36), (38), (39) и пользуясь тем,

что в силу (14) справедлива оценка

|P_n(X × Y)| ≤ (n + 1)^|X||Y|,

получаем

1 - ε_n ≤ (n + 1)^|X||Y|e-nmin{ξ,δ/2}

(40)

(аналогично последнему неравенству в [22]), откуда следует (16), поскольку |X ||Y|,

ξ и δ - положительные константы, не зависящие от n. Так как равенство (16) вы-

полнено для любой последовательности (n, R, ε_n)-кодов, таких что R ∈ R_cut-set, то

включение (15) справедливо для всех ε ∈ [0, 1).

§6. Предварительные сведения для доказательства теоремы 2: гауссовские типы

В этом параграфе мы обобщаем определения и результаты метода типов [19, гл. 2]

на гауссовский случай, опираясь на идеи предшествующих обобщений на гауссов-

ский случай для двух переменных в задаче угадывания [30, раздел VI] и трех пе-

ременных в задаче кодирования источников [31, Приложение D]. Более точно, мы

обобщаем метод типов на случай многих переменных, что позволит исследовать

задачу кодирования каналов для любой гауссовской сети. Всюду далее в этом пара-

графе через n обозначается произвольное натуральное число, а через T, T₁ и T₂ -

произвольные непустые подмножества множества I.

6.1. Гауссовские типы.

Определение 9. Эмпирической корреляцией между двумя последовательно-

стями векторов-столбцов x^nT ∈ R^n|T| и y^nT ∈ R^n|T| называется следующая матрица

размера |T| × |T|:

∑

Υ[xT ,yT]

^def=

x_T,k y^tT,k.

(41)

k=1

Автокорреляция вектора-столбца x_T ∈ R^|T| определяется как

= Υ[xT,xT] =x_Tx^tT.

(42)

Эмпирическая автокорреляция последовательности векторов-столбцов x^nT ∈ R^n|T|

определяется как

∑

= Υ[xT,xT] =

R[x_T,k].

k=1

Определение 10. Гауссовским типом пары (x^nT

,yⁿ ) ∈ Rn|T1| × Rn|T2| назы-_T

вается матрица размера (|T₁| + |T₂|) × (|T₁| + |T₂|)

[

]

Υ[x

,xnT1 ] Υ[xT1,yT2^]

(43)

Υ[yT2,xT1^] Υ[yT2,yT2^]

Для любого заданного (n, R, P )-кода, порождающего распределение вероятно-

стей p^nX, из ограничений на мощность почти наверное (7) следует, что

{

}

∫

∑

p_Xn

(xⁿⁱ) × 1

i,k

≤ P_i dxⁿⁱ = 1

(44)

k=1

Rⁿ

для всех i ∈ I, откуда согласно определению множества S(P ) в (10) вытекает, что

вероятность того, что эмпирическая автокорреляция Xⁿ принадлежит S(P ), рав-

на 1, т.е.

∫

p_Xn(xⁿ) × 1{R[xⁿ] ∈ S(P )} dxⁿ = 1.

(45)

R^nN

Для любого δ > 0 и любой (N × N)-матрицы A ∈ R^N×N определим δ-окрестность

матрицы A как

{

}

B ∈ R^N×N | -δ · 1^N×N ≤ B - A ≤ δ · 1^N×N

(46)

Пусть

⎧



⎫



⎪

K¹¹ ∈ S(P ),

⎪

[

]



⎨

⎬



K¹¹

K¹²

K¹² - K¹¹G^t ∈ Γ_δ(0^N×N),



^def=

∈R2N×2N

(47)

⎪

K²¹

K²²

 K21 - GK11 ∈ Γδ(0N×N ),

⎪



⎩

⎭

_K22 + GK¹¹G^t - GK¹² - K²¹G^t ∈ Γ_δ(Σ)

– множество типичных гауссовских типов пар (xⁿ, yⁿ), где эмпирическая автокорре-

ляция xⁿ принадлежит S(P ), а эмпирическая автокорреляция zⁿ попадает в некото-

рую окрестность ковариационной матрицы шума Σ. Следующая лемма показывает,

что вероятность того, что гауссовский тип пары (Xⁿ, Yⁿ) не принадлежит множе-

ству U(δ,P)X,Y, экспоненциально мала. Доказательство леммы 1 довольно громоздко,

поэтому оно вынесено в Приложение.

Лемма 1. Для любого δ > 0 существует константа τ > 0, зависящая от

(P , Σ), такая что для всех достаточно больших n неравенство

∫

{

}

p_Xn_,Y n (xⁿ, yⁿ) × 1 K[xn,yn] ∈ U(δ,P)

dyⁿ dxⁿ > 1 - e^-τn

X,Y

R^nN R^nN

справедливо для любого (n, R, P)-кода, где p_Xn_,Y n - распределение, индуцированное

кодом.

6.2. Квантователи, типы и классы типов. В определении 10 были введены гаус-

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

несчетное множество. Поэтому мы хотим ввести равномерное квантование евклидо-

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

ше Δ. Для этого в определении 11 вводятся Δ-квантователи, с помощью которых

любая ковариационная матрица будет квантоваться с точностью Δ вдоль каждого

измерения.

Определение 11. Зафиксируем положительное число Δ. Вещественная мат-

рица Λ размера N × N называется Δ-квантователем, если существует целочислен-

ная матрица Π размера N × N, такая что

Λ = ΔΠ.

Множество Δ-квантователей обозначается через L^Δ, что можно рассматривать как

масштабированную версию N²-мерной целочисленной решетки.

Определение 12. Для любого Δ-квантователя Λ ∈ L^Δ определим Δ-прямоу-

гольник, представленный квантователем Λ, как

{

}

B∈R^N×N |Λ≤B <Λ+Δ·1^N×N

Множество V будем называть Δ-прямоугольником, если оно является Δ-прямоу-

гольником, представленным некоторым Λ из L^Δ.

Из определения 12 видно, что множество L^Δ счетно, а множество {V^ΔΛ : Λ ∈ L^Δ}

образует разбиение пространства R^N×N . С учетом определения множества S(P )

в (10) определим для каждого γ > 0 множество положительно определенных кова-

риационных матриц

{

}



для всех непустых T ⊆ I все собственные

= K ∈ S(P)



(48)

значения K_T×T не меньше γ

Теперь определим подмножество множества L^Δ, называемое множеством входных

(Δ, γ, P )-квантователей и обозначаемое через L(Δ,γ,P), такое что его мощность ко-

нечна.

Определение 13. Множеством входных (Δ,γ,P)-квантователей называет-

ся множество

= {Λ ∈ L^Δ | V^ΔΛ ∩ S_γ(P) = ∅}.

(49)

Из определения 13 следует, что

⋃

V^ΔΛ ⊇ S_γ(P ).

(50)

Λ∈L(Δ,γ,P)

Следующее предложение, показывающее, что мощность |L(Δ,γ,P)| конечна, имеет

простое доказательство, приведенное в Приложении для полноты изложения.

Предложение 1. Для любых Δ > 0 и γ > 0 справедливо неравенство

(

)

∏

^⌈√P_iP_j ⌉

|L(Δ,γ,P)| ≤

+1 .

(i,j)∈I×I

Теперь мы готовы приступить к построению (Δ, γ, P )-типов.

Определение 14. Для каждого Λ ∈ L(Δ,γ,P) выберем и зафиксируем одну

ковариационную матрицу K_Λ ∈ V^ΔΛ ∩ S_γ (P ) и назовем ее (Δ, γ, P )-типом, пред-

ставленным квантователем Λ. Ковариационную матрицу J ∈ S(P ) будем назы-

вать (Δ, γ, P )-типом, если она является (Δ, γ, P)-типом, представленным Λ, для

некоторого Λ ∈ L(Δ,γ,P), и пусть

= V^ΔΛ

- Δ-прямоугольник, содержащий J. Множество (Δ, γ, P )-типов обозначим через

P(Δ,γ,P).

Следующий результат непосредственно вытекает из определения 14, соотноше-

ния (50) и предложения 1, поэтому его доказательство опускается.

Следствие. Для любых Δ > 0 и γ > 0 имеет место включение

⋃

V^Δ(J) ⊇ S_γ(P ).

(51)

J∈P(Δ,γ,P)

Кроме того,

(

)

∏

^⌈√P_iP_j ⌉

|P(Δ,γ,P)| ≤

+1 .

(i,j)∈I×I

Определение 15. Зафиксируем произвольное n ∈ N. Для каждого (Δ,γ,P)-

типа J ∈ P(Δ,γ,P) его входной класс Δ-типов определяется как

{

}

xn ∈ R^nN | R[xⁿ] ∈ V^Δ(J)

Кроме того, для каждого J определим его класс совместных (Δ, δ, P )-типов

{

}

^def=

(xⁿ, yⁿ) ∈ R^nN × R^nN | xⁿ ∈ T(n,Δ)J(X), K[xn,yn] ∈ U(δ,P)X,Y

(52)

и класс совместных (Δ, δ, P )-типов при ограничении на (X_T c, Y_T c )

{



}

существует пара



^def= (x^nTc , y^nTc ) ∈ Rn|Tc| × Rn|Tc|



(x^nI, y^nI) ∈ T(n,Δ,δ,P)J(X, Y ),

(53)



такая что (x^nTc , y^nTc ) = (x^nTc , y^nTc )

В доказательстве теоремы 2 используются следующие две простые, но полезные

границы.

Предложение 2. Пусть K ≻ 0 - вещественная матрица размера N × N.

Пусть k_min > 0 - наименьшее собственное значение матрицы K. Тогда

K-1 ∈ Γ N (0^N×N ),

^kmin

где множество Γ_δ(0^N×N ) определено в (46).

Доказательство. Требуемый результат можно получить приведением мат-

рицы K к диагональному виду. Более точно, пусть

K =UDU^t

(54)

– разложение K по собственным значениям, где U - унитарная матрица, стро-

ки которой составляют ортонормированный базис из собственных векторов мат-

рицы K, а D - диагональная матрица с положительными диагональными элемен-

= λ₁ > 0. Об-

ращая обе стороны равенства (54) и применяя стандартные умножения, получаем

K-1 = UD-1U^t. Поскольку наибольший элемент диагональной матрицы D-1 ра-

вен 1/k_min, а абсолютные величины элементов матрицы U не больше 1 (строки U

ортогональны), из равенства K-1 = UD-1U^t следует, что абсолютные величины

элементов матрицы K-1 не превышают^N . ▴

kmin

Предложение 3. Пусть Π₁ и Π₂ - вещественные матрицы размера N₁×N₂

и N₂ × N₃ соответственно. Пусть

πmaxi = max{|r| : r - элемент матрицы Π_i}, i ∈ {1, 2}.

Тогда

Π₁Π₂ ∈ ΓN2πmax1πmax (0N1×N3 ).₂

Доказательство. Требуемый результат легко вытекает из того, что Π₁ ∈

∈ Γ_πmax

(0N1×N2 ) и Π₂ ∈ Γ_πmax (0N2×N3 ).

▴

Ключевым шагом в доказательстве теоремы 2 является применение следующей

∏

леммы, ограничивающей произведения вероятностей

qYTc |X(yTc,k |xk) для лю-

k=1

бых (Δ, γ, P )-типов J ∈ P(Δ,γ,P) и любых (xⁿ, yⁿ) ∈ T(n,Δ,δ,P)J(X, Y ). Так как до-

казательство леммы 2 довольно громоздко, оно вынесено в Приложение.

Лемма 2. Пусть σ_min - наименьшее собственное значение матрицы Σ. За-

фиксируем произвольное T ⊊ I и произвольный (Δ, γ, P )-тип J ∈ P(Δ,γ,P). Тогда

для любой пары (xⁿ, yⁿ) ∈ T(n,Δ,δ,P)J(X, Y ) справедливо неравенство

(

)

∏

q_Y

)≤e-n2log((2πe)|Tc||ΣTc×Tc|)-2σmi

(55)

Tc |X(^yT^c,k^|xk

k=1

§ 7. Доказательство теоремы 2

В этом параграфе будет показано, что

C_ε ⊆ R_cut-set

(56)

для всех ε ∈ [0, 1), где область R_cut-set определена в (11). Достаточно показать,

что для любого R ∈ R_cut-set и любой последовательности (n, R, P , ε_n)-кодов предел

вероятностей ошибки удовлетворяет равенству

lim

ε_n = 1.

(57)

n→∞

Чтобы показать это, зафиксируем вектор скоростей R ∈ R_cut-set и последователь-

ность (n, R, P , ε_n)-кодов.

7.1. Связь R с границей множества разреза. Так как R ∈ R_cut-set, а область

R_cut-set замкнута, то из определения области R_cut-set в (11) следует, что всегда

найдется положительное число η, такое что для любой ковариационной матрицы

K ∈ S(P) существует непустое множество V_K ⊊ I, для которого

∑



+η,

R_i,j ≥

log

I|Vc| + GV c×V KV |V c G^V c×V (ΣV^c×V^c )-1

(i,j)∈V ×V^c

где через V для краткости обозначено множество V_K , а величина K_V|V c определе-

на в (9). Положим

(

)

δN

2N⁴gmax(1 + δ)Pmax

δN + (2Ng_max + 1)δ +

(58)

2σ_min

P_min

= min

= maxPi > 0, а σmin > 0 определяется как наименьшее

i∈I

собственное значение матрицы Σ. Далее, всегда найдется достаточно малое δ > 0,

такое что для любой ковариационной матрицы K ∈ S((1 + δ)P ) выполняется сле-

дующее неравенство:

∑

(1 - δ)R_i,j ≥

(i,j)∈V ×V^c



≥

log

+2η(δ).

(59)

I|Vc| + GV c×V KV |V c G^V c×V (ΣV^c×V^c )-1

В частности, для любой K ≻ 0 величина K_V|V c в (59) допускает выражение в за-

мкнутом виде

K_V|V c = K_V×V - K_V×V c(K_V c_×V c)-1K_V c_×V

(60)

согласно формуле условной дисперсии для многомерного нормального распределе-

ния (см. [32, п. 8.1.3]).

7.2. Добавление N избыточных передач. В данном доказательстве величина

K_V|V c в (59) тесно связана с R[Xⁿ], т.е. с эмпирической автокорреляцией Xⁿ. По-

скольку для K_V|V c имеется простое выражение в замкнутом виде (60), если K ≻ 0,

то мы собираемся к каждому (n, R, P, ε_n)-коду аккуратно добавить N избыточных

передач таким образом, чтобы для полученного таким образом кода длины n + N

с вероятностью 1 выполнялось соотношение R[Xⁿ] ≻ 0. Для этого рассмотрим каж-

дое достаточно большое n, такое что неравенство

nR_i,j ≥ (n + N)(1 - δ)R_i,j

(61)

выполняется для всех (i, j) ∈ I × I, и соответствующий (n, R, P , ε_n)-код, зафик-

сированный выше, и построим (n + N, (1 - δ)R, (1 + δ)P , ε_n)-код следующим об-

разом. На первых n интервалах времени этот (n + N, (1 - δ)R, (1 + δ)P , ε_n)-код

совпадает с (n, R, P, ε_n)-кодом. На последних N интервалах времени N узлов после-

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

i ∈ {1, 2, . . ., N} на i-м из последних интервалов времени только узел i передает

√

ненулевой символ

δ(n + N)P_min. Так как эмпирическая автокорреляция каждо-

го передаваемого xⁿ имеет минимальное собственное значение, равное нулю, то за

счет N избыточных передач эмпирическая автокорреляция каждого передаваемого

xn+N будет иметь минимальное собственное значение δP_min.

= (1 + δ)P .

Для каждого построенного выше (n, (1 - δ)R, P(δ), ε_n)-кода пусть pW,Xn,Y n, W^-

индуцированное распределение вероятностей. В силу (48) и согласно вышеописанной

конструкции для любого i ∈ I имеем

∫

{

}

p_Xn(xⁿ) × 1

R[xⁿ] ∈ SδPmin (P(δ))

dxⁿ = 1,

R^nN

откуда следует, что для этого (n, (1 - δ)R, P(δ), ε_n)-кода с вероятностью 1 справед-

ливо R[Xⁿ] ≻ 0.

7.3. Упрощение вероятности правильного декодирования с учетом отсутствия

памяти. Зафиксируем достаточно большое n, для которого выполняются неравен-

ство (61), неравенство

∫

{

}

p_Xn_,Y n (xⁿ, yⁿ) × 1 K[xn,yn] ∈ U(δ2,P(δ))

dyⁿ dxⁿ > 1 - e^-τn

X,Y

R^nN R^nN

для некоторого τ > 0 как следствие леммы 1 (где специально выбрано δ²) и нера-

венство

(

)

)₂

⁽g_max(1 + δ)P_max

N²g^2max + 2N⁵

+N⁸

≤ δ,

(62)

δP_min

где

= max{|g| : g - элемент матрицы G}.

Если не будет указано обратное, в дальнейшей части доказательства все вероятно-

сти вычисляются согласно распределению pW,Xn,Y n, W^{.Согласнолемме1инера-}

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

вания можно оценить сверху следующим образом:

}

{⋂{

}

1-ε_n =P

ϕ_i(W_{i}×I, Yⁿⁱ) = W_I×{i}

≤

i∈I

{

}

{⋂{

}

≤P

ϕ_i(W_{i}×I, Yⁿⁱ) = W_I×{i}

∩ K[Xn,Yn] ∈ U(δ2,P(δ))

∩

X,Y

i∈I

}

{

}

∩

R[Xⁿ] ∈ SδPmin(P(δ))

+e^-τn =

⎧

⎫

⎪

⋂ {ϕ_i(w_{i}×I, Y ni) = w_I×{i}} ∩



⎪

∑

⎨

i∈I



⎬

{

}



)



W =w +e^-τn.

(63)

∩

|W|

^P⎪⎪



⎪

{

}

w∈W

⎩

⎭

∩

R[Xⁿ] ∈ SδPmin (P(δ))

Для упрощения дальнейшего изложения будем использовать обозначения

w_I×{i},

x_Tc_,k(w_Tc_×I, yk-1Tc), xk(w, yk-1), x^Tc (wTc×I, yTc1) и xⁿ(w, yn-1), введенные перед

формулой (20). Кроме того, определим события

{

}

E_w,yn

^def=

w_I×{i} = w_I×{i}

{

}

= K[xn(w,yn-1),yn] ∈ U(δ2,P(δ))

X,Y

{

}

R[xⁿ(w, yn-1)] ∈ SδPmin (P(δ))

Чтобы упростить правую часть равенства (63), для каждого w ∈ W запишем

{

}

{⋂{

}

ϕ_i(w_{i}×I, Yⁿⁱ) = w_I×{i}

∩ K[Xn,Yn] ∈ U(δ2,P(δ))

∩

X,Y

i∈I

}

{

}

∩

R[Xⁿ] ∈ SδPmin(P(δ))

W =w

∫

}

{⋂

= pY n|W=w(yⁿ) × 1

E_w,yn

i∈I

R^nN

∫

∏

^(a)=

pYk |X_k (yk^|xk(w,yk-1)) ×

k=1

R^nN

}

{⋂

×1

E_w,yn

1{G_w,yn }1{H_w,yn-1} dyⁿ

(64)

i∈I

где равенство (a) следует из того, что согласно определениям 7 и 8

∏

p_Y n |W =w(yⁿ) =

pYk |X_k (yk |xk(w, yk-1))

k=1

для всех yⁿ ∈ R^nN .

7.4. Дальнейшее упрощение вероятности правильного декодирования с помощью

метода гауссовских типов. Положим

= δP_min

(65)

= 1/n.

(66)

Для любого w ∈ W и любого (Δ, γ, P(δ))-типа J ∈ P(Δ,γ,P(δ)) положим

{

}

)

= yⁿ ∈ R^nN | (xⁿ(w, yn-1), yⁿ) ∈ T (n,Δ,δ2,P(δ)

(X, Y )

(67)

а для любого непустого множества T ⊊ I и любого w_T c_×I ∈ W_T c_×I определим

{

}



)

^def= y^nTc ∈ Rn|Tc|

 (x^nTc (wT c ×I , y^Tc ), y^Tc ) ∈ T (n,Δ,δ2,P(δ)

(X_T c , Y_T c )

(68)

Поскольку

⋃

{

)

T(n,Δ,δ2,P(δ)

(X, Y ) ⊇ (xⁿ(w, yn-1), yⁿ) ∈

J∈P(Δ,γ,P(δ))

}

)

∈X ×Y |K[xn(w,yn-1),yn] ∈U(δ2,P(δ)

X,Y

, R[xⁿ(w, yn-1)] ∈ S_γ (P(δ))

согласно соотношению (51) и определениям U(δ2,P(δ))_X,Y, S_γ(P(δ)), T(n,Δ,δ2,P(δ))_J(X, Y )

и P(Δ,γ,P(δ)), данным в (47), (48) и определениях 15 и 14 соответственно, с уче-

том определения множества A(Δ,δ2)(w; J) в (67) получаем отсюда, что объединение

⋃

A(Δ,δ2)(w; J) покрывает множество

J∈P(Δ,γ,P(δ))

{

}



)

yⁿ ∈ R^nN

_K[xⁿ(w,yn-1),yⁿ]∈U(δ2,P(δ)

, R[xⁿ(w, yn-1)] ∈ S_γ(P(δ))

X,Y

откуда следует, что правую часть (64) можно оценить сверху как

}

∏

{⋂

E_w,yn

1{G_w,yn }1{H_w,yn-1} dyⁿ ≤

pYk |X_k (yk |xk(w, yk-1)) × 1

k=1

i∈I

R^nN

∫

}

∑

∏

{⋂

≤

E_w,yn

dyⁿ.

(69)

pYk |X_k (yk |xk(w, yk-1)) × 1

J∈P(Δ,γ,P(δ))

k=1

i∈I

A(Δ,δ2)(w;J)

Объединяя (63), (64) и (69), заключаем, что вероятность правильного декодирования

удовлетворяет соотношению

1-ε_n ≤e^-τn +

∫

∑

∏

pYk |X_k (yk |xk(w, yk-1)) ×

|W|

w∈WJ∈P(Δ,γ,P(δ))

k=1

A(Δ,δ2)(w;J)

}

{⋂

×1

E_w,yn

dyⁿ.

(70)

i∈I

7.5. Оценка вероятности правильного декодирования через F(Δ,δ2)_T(w_T c_×I ; J).

Зафиксируем произвольное непустое множество T ⊊ I. Для упрощения обозначений

100

положим

(

)

δ²N³

log

(2πe)|Tc||Σ_T c_×T c |

(71)

2σ_min

где σmin > 0 - наименьшее собственное значение матрицы Σ. Чтобы упростить

правую часть неравенства (70), рассмотрим в ней самое внутреннее произведение.

В частности, для любых w ∈ W, J ∈ P(Δ,γ,P(δ)) и yⁿ ∈ A(Δ,δ2)(w; J) рассмотрим

следующую цепочку соотношений:

∏

p_Y

k|Xk(^yk^|xk(w,yk-1))=

k=1

∏

= p_Y

^(b)≤

Tc,k |Xk (^yT^c,k^|xk(w,yk-1))pYT,k |Xk,YTc,k(yT,k^|xk(w,yk-1)^,yT^c,k⁾

k=1

(b)

∏

≤ e-naT p_Y

(72)

T ,k |Xk,YT c ,k (^yT,k^|xk(w,yk-1)^,yT^c,k),

k=1

где неравенство (b) вытекает из леммы 2. Повторяя действия, аналогичные сделан-

ным при выводе цепочки неравенств, приводящих к соотношению (26), получаем

следующее неравенство, справедливое для любого J ∈ P(Δ,γ,P(δ)):

∫

}

∑

∏

{⋂

E_w,yn

dyⁿ

⁽⁷²⁾≤

pYk |X_k (yk |xk(w, yk-1)) × 1

w∈W

k=1

i∈I

A(Δ,δ2)(w;J)

∫

(72)

∑

∏

≤ e-naT

pYT,k |X_k,YTc,k (yT,k |xk(w, yk-1), yTc,k) ×

w∈W

k=1

A(Δ,δ2)(w;J)

{⋂

}

∫

∑

×1

E_w,yn

dyⁿ ≤ e-naT

1 dy

(73)

T^c

i∈T^c

w(T×Tc₎c ∈W(T×T c₎c

)

F(Δ,δ2

(wT c×I ;J)

7.6. Оценка мощности множества F(Δ,δ2)_T(w_T c_×I ; J). Для вывода верхней гра-

ницы на мощность множества F(Δ,δ2)_T(w_T c_×I ; J) для каждого J = J_I×I ∈ P(Δ,γ,P(δ))

обозначим через

ϕXTc,YT c (xTc , yTc ) ≡

([

]

[

])

x_Tc

J_Tc_×Tc

J_Tc_×IG^tTc_×I

≡N

;02|Tc|,

y_Tc

G_Tc_×IJ_I×Tc G_Tc_×IJG^tTc_×I + ΣTc×Tc

соответствующее многомерное нормальное распределение. Для любых w_Tc_×I

∈

∈ W_Tc_×I и J ∈ P(Δ,γ,P(δ)), поскольку наименьшее собственное значение матрицы J

не меньше γ > 0 по определению множества P(Δ,γ,P(δ)) (см. определение 14 и (48)),

из предложения 2 следует, что

(J_Tc_×Tc )-1 ∈ ΓN (0^N×N );

(74)

кроме того, хорошо известно [32, п. 8.1.3], что

ϕYTc |XT c (yTc |xTc ) ≡ N(yTc ; μTc (xTc ; J),^ΣTc (J)),

(75)

101

где

= G_Tc_×IJ_I×Tc (J_Tc_×Tc)-1 x_Tc

(76)

= G_Tc_×IJG^tTc_×I + ΣTc×Tc - GTc×IJI×Tc (JTc×Tc)-1 JTc×IGT c×I.

(77)

Далее в этом пункте мы собираемся показать, что экспонента мощности множе-

(

)

ства F(Δ,δ2)_T(w_Tc_×I; J) близка к¹

log

(2πe)|Tc||ΣT c (J)|

. С этой целью для любых

w_Tc_×I ∈ W_Tc_×I и J ∈ P(Δ,γ,P(δ)) рассмотрим неравенство

∫

∏

ϕ_Y

)) dy^nTc ≤ 1

Tc |XT c (^yT^c,k^|xT^c,k(wT^c×I,yT

k=1

F(Δ,δ2)T(wT c×I;J)

(см. определение F(Δ,δ2)_T(w_T c_×I ; J) в (68)), из которого с учетом (75)-(77) вытекает,

что

(

)

∫

∑

);J)])

2n k=1

× dy^nTc ≤ 1,

(78)

где интеграл берется по множеству F(Δ,δ2)_T(w_T c_×I ; J). Зафиксируем произвольные

w_Tc_×I ∈ W_Tc_×I и J ∈ P(Δ,γ,P(δ)). Чтобы получить оценку снизу на левую часть

неравенства (78), для каждого y^nTc ∈ F(Δ,δ2)_T(wT c ×I ; J) рассмотрим

∑

k-1

R[y_T c_,k - μ_T c (x_T c_,k(w_T c_×I , y_T

); J)] =

k=1

∑

)]+

= R[y^nTc] -

Υ[yTc,k,GTc×I J^I×Tc (JTc×Tc )-1x^Tc,k(wTc×I,yT

k=1

∑

R[G_T c_×I J_I×T c(J_T c_×T c)-1x_T c_,k(w_T c_×I , yk-1Tc)].

(79)

k=1

С учетом данных в (68), (53), (52) и (47) определений множеств F(Δ,δ2)_T(w_Tc_×I; J),

T (n,Δ,δ2,P(δ))_J(X_Tc, Y_Tc), T (n,Δ,δ2,P(δ))_J(X, Y ) и U(δ2,P(δ))_X,Y заключаем, что для любого

y^nTc ∈ F(Δ,δ2)_T(wTc×I; J) существует пара (xⁿ, yⁿ) ∈ T(n,Δ,δ2,P(δ))_J(X, Y ), такая что

(x^nTc, y^nTc) = (x^nTc(wTc×I, y^Tc), y^Tc),

(80)

R[xⁿ] ∈ V^Δ(J)

(81)

K[xn,yn] ∈ U(δ2,P(δ))_X,Y.

(82)

Теперь из (82), определения множества U(δ2,P(δ) )_X,Y в (47) и предложения 3 следует,

что

Υ[yn,xn] ∈ Γ_δ2 (GR[xⁿ])

(83)

102

R[yⁿ] ∈ Γ(2Ng

(84)

max+1)δ² (GR[xn]G^t + Σ)

(вывод этих соотношений приведен в Приложении для полноты изложения). Объ-

единяя (81), (83) и (84), заключаем, что существует матрица QΔI×I ∈ Γ_Δ(0^N×N ),

такая что

R[x^nTc ] = JTc×Tc + Q^Tc_×Tc,

(85)

(86)

R[y^nTc ] ∈ Γ(2Ngmax+1)δ2 (GTc×I(J + QI×I)G^Tc×I + ΣT^c×T^c )

Υ[yTc ,xTc ] ∈ Γ_δ2 (G_Tc_×I(J_I×Tc + QΔI×Tc )).

(87)

Так как

G_Tc_×IQΔI×I ∈ ΓNgmaxΔ(0Tc×I) и GTc×IQ^I×IG^Tc_×I ∈ ΓN2g2maxΔ(0Tc×Tc)

согласно предложению 3, то из из (86) и (87) следует, что

Υ[yTc ,xTc ] ∈ Γ_δ2+Ng

maxΔ(^GT^c ×I^JI×T^c )

(88)

R[y^nTc ] ∈ Γ(2Ngmax+1)δ2+N2g2maxΔ(GTc×IJG^Tc×I + ΣT^c×T^c ).

(89)

Продолжая равенство (79), с учетом (74), (80), (85), (88), (89), того факта, что

J ∈ Γ(1+δ)Pmax(0^N×N), и предложения 3 получаем

(90)

R[y^nTc ] ∈ Γ(2Ngmax+1)δ2+N2g2maxΔ(GT c ×I JG^T c ×I + ΣT^c ×T^c ),

∑

)]_∈

Υ[yTc,k,GTc×I J^I×Tc (JTc×Tc )-1x^Tc,k(wTc×I,yT

k=1

(91)

∈ Γ_N4gmax(δ²+NgmaxΔ)(1+δ)Pmax/γ(GT^c×I^JI×T^c(^JT^c×T^c)-1JT^c×IGT c×I)

∑

k-1

R[G_T c_×I J_I×T c(J_T c_×T c )-1x_T c_,k(w_T c_×I , y_T

)] ∈

k=1

∈ΓΔ(N4_g

(92)

max(1+δ)Pmax /γ)² (^GT^c ×I^JI×T^c (^JT^c ×T^c )-1JT^c×IGTc ×I).

Для упрощения обозначений положим

= (2Ng_max + 1)δ² + N²g^2maxΔ +

(

)₂

+ 2N⁴g_max(δ² + Ng_maxΔ)(1 + δ)P_max/γ + Δ

N⁴g_max(1 + δ)P_max/γ

(93)

Объединяя (79) и (90)-(93), получаем

∑

k-1

R[y_T c_,k - μ_T c (x_T c_,k(w_T c_×I , y_T

); J)] ∈

k=1

(

)

∈Γκ(δ,Δ)

G_Tc_×IJG^tTc_×I + ΣTc×Tc - GTc×IJI×Tc(JTc×Tc)-1JTc×IG^Tc_×I

103

откуда с учетом (77) вытекает, что

∑

k-1

R[y_T c_,k - μ_T c (x_T c_,k(w_T c_×I , y_T

); J)] ∈ Γκ(δ,Δ)(ΣTc(J)).

(94)

k=1

Так как упрощение (77) приводит к

(

)

ΣTc (J) = G_Tc_×T

J_T×T - J_T×Tc(J_Tc_×Tc)-1J_Tc_×T

(95)

G^tTc×T + ΣT^c×T^c,

то отсюда следует, что все собственные значения матрицы

ΣTc (J) не меньше σ_min,

и тогда по предложению 2 получаем

(ΣTc (J))-1 ∈ Γ N

(0Tc×Tc ).

(96)

^σmin

Таким образом, из (94), (96) и предложения 2 вытекает неравенство



∑

(

)

1



N²κ(δ, Δ)



(ΣTc (J))-1R[y_Tc_,k - μ_Tc (x_Tc_,k(w_Tc_×I, yk-1Tc); J)]



≤

n



σ_min

k=1

откуда с учетом (78) получаем

(

)

∫

log((2πe)^|Tc||^ΣT c (J)|)+N2κ(δ,Δ)

2σmin

1 dy^nTc

≤e

(97)

F(Δ,δ2)T(wT c×I;J)

7.7. Экспоненциальное убывание вероятности правильного декодирования. Объ-

единяя (73), (71) и (97) и пользуясь тем, что в соответствии с (2) справедливо

∑

-n

(1-δ)Ri,j

|W(T×T c₎c |

∏

≤e(i,j)∈T×Tc

|W|

⌈en(1-δ)Ri,j⌉

(i,j)∈T ×T^c

получаем для любого J ∈ P(Δ,γ,P(δ))

∫

}

∑

∏

{⋂

E_w,yn

dyⁿ ≤

pYk |X_k (yk |xk(w, yk-1)) × 1

|W|

w∈W

k=1

i∈I

A(Δ,δ2)(w;J)

(

)

∑

|ΣTc (J)|

-n

(1-δ)Ri,j -¹² log

-δ2N3+N2κ(δ,Δ)

|ΣTc×Tc|

2σmin

≤e(i,j)∈T×Tc

(98)

Используя (58), (62), (65), (66) и (93), приходим к

δ²N³ + N²κ(δ, Δ)

≤ η(δ).

(99)

2σ_min

Объединяя (95), (98) и (99), для любого J ∈ P(Δ,γ,P(δ)) получаем

}

∫

∑

∏

{⋂

pYk |X_k (yk |xk(w, yk-1)) × 1

E_w,yn dyⁿ ≤

|W|

w∈W

k=1

i∈I

A(Δ,δ2)(w;J)

(

)

∑

-n

(1-δ)Ri,j -¹² log|I|T c|+GT c×T JT |T c GT c ×T (ΣTc×Tc )-1|-η(δ)

≤e(i,j)∈T×Tc

(100)

104

= JT×T -J_T×Tc (J_Tc_×Tc)-1 J_Tc_×T.

Используя (70), (100), (59), (60), следствие из предложения 1 и равенство (66), по-

лучаем

∏

( ⌈

√

⌉

)

1-ε_n ≤e^-τn +

2 n

P_iP_j

+1 e-nη(δ) ≤

(i,j)∈I×I

≤ e^-τn + (2nP_max + 3)N2e-nη(δ).

(101)

Следовательно, равенство (57) справедливо в силу (101), поскольку η(δ) положи-

тельно согласно (58), и значит, включение (56) имеет место для всех ε ∈ [0, 1).

§ 8. Заключительные замечания

В статье предложено первое полное доказательство сильного обращения тео-

ремы кодирования для любой ДСБП с точной границей множества разреза. До-

казательство основано на методе типов. Кроме того, сильное обращение теоремы

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

разреза в условиях ограничений на мощность почти наверное. Наше обобщение до-

казательства сильного обращения теоремы кодирования для ДСБП на гауссовские

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

обращения теоремы кодирования для ДСБП основано на методе типов [19, гл. 2].

Более точно, метод типов для ДСБП основан на соображениях подсчета, посколь-

ку входной и выходной алфавиты в ДСБП конечны. Напротив того, метод типов

для гауссовских сетей основан на аккуратной аппроксимации и квантовании, по-

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

отличие между доказательствами для ДСБП в § 5 и для гауссовских сетей в § 7:

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

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

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

определение классов совместных типов (определение 15) таким образом, что удается

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

ДСБП в § 5, наоборот, в значительной степени опирается на определение условных

типов.

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

ляются новые сильные обращения теоремы кодирования для гауссовских КМД с об-

ратной связью и следующих каналов с ретрансляцией как в дискретной модели

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

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

канал с ретрансляцией и обратной связью. Сильное обращение теоремы кодирова-

ния в гауссовском случае служит дополнением к следующим недавно полученным

результатам: если вместо ограничений на мощность почти наверное использовать

ограничения на мощность в длительном режиме, то сильное обращение теоремы

кодирования не выполняется для гауссовского ухудшенного канала с ретрансляци-

ей [20] и гауссовского канала множественного доступа (КМД) с обратной связью [21].

ПРИЛОЖЕНИЕ

Доказательство леммы 1. Перед тем как доказывать лемму 1, докажем два необ-

ходимых нам предварительных результата. Следующее предложение утверждает,

что вероятность того, что эмпирическая автокорреляция Zⁿ не принадлежит мно-

жеству Γ_δ(Σ), экспоненциально мала. Доказательство предложения 4 основано на

теории больших уклонений [33] и приведено здесь для полноты изложения.

105

Предложение 4. Пусть p_Z(z) = N(z;0^N,Σ) для всех z, пусть Zⁿ пред-

ставляет собой n независимых копий случайной величины Z ∼ p_Z, и пусть p_Zn -

распределение Zⁿ, т.е.

∏

p_Zn(zⁿ) =

p_Z(z_k)

k=1

для всех zⁿ. Для любого δ > 0 существует константа τ > 0, зависящая от Σ,

такая что для всех достаточно больших n выполняется неравенство

∫

p_Zn(zⁿ) × 1 {R[zⁿ] ∈ Γ_δ(Σ)} dzⁿ > 1 - e^-τn.

(102)

R^nN

Доказательство. Пусть t > 0 - произвольное действительное число. Рас-

смотрим следующую цепочку неравенств для любых (i, j) ∈ I × I, где все вероят-

ности и математические ожидания вычисляются согласно распределению p_Zn:

{



}



∑



1



Z_i,kZ_j,k - E[Z_i,kZ_j,k]



>δ

(103)

n



k=1

{

}

(

)_n

∑

(a) 2

E[etZi,k Z^j,k ]

=2P

Z_i,kZ_j,k > E[Z_i,kZ_j,k] + δ

≤

etn(E[Zi,k^Zj,k]+δ)

k=1

= 2e^tn(^t log E[etZi,kZj,k ]^-E[Zi,kZ^j,k]^-δ),

(104)

где неравенство (a) следует из границы Чернова. Так как

lim

log E[etZi,kZ^j,k ] = E[Z_i,kZ_j,k],

t→0 t

то существует достаточно малое t_ij > 0, зависящее от Σ, такое что

log E[etij Z^i,k Z^j,k ] - E[Z_i,kZ_j,k] ≤ δ/2,

t_ij

откуда с учетом (104) следует, что

{



}



∑



1



Z_i,kZ_j,k - E[Z_i,kZ_j,k]



>δ

≤ 2e-tijδn/2.

(105)

n



k=1

Поскольку существует конечное множество положительных чисел {t_ij > 0 | (i, j) ∈

^def=^δ

min

{t_ij}, заключаем, что неравенство (102) справедливо для всех достаточ-

(i,j)∈I×I

но больших n. ▴

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

корреляция между Xⁿ и Zⁿ не принадлежит множеству Γ_δ(0^N×N ), экспоненциально

мала. Доказательство предложения 5 основано на границе Чернова и ограничениях

на мощность почти наверное (7).

Предложение 5. Для любого δ > 0 существует константа τ > 0, завися-

щая от (P , Σ), такая что для всех достаточно больших n неравенство

∫

{

}

p_Xn_,Zn (xⁿ, zⁿ) × 1 Υ[xn,zn] ∈ Γ_δ(0^N×N ) dzⁿ dxⁿ > 1 - e^-τn

(106)

R^nN R^nN

106

справедливо для любого (n, R, P)-кода, где p_Xn_,Zn - распределение, индуцированное

этим кодом.

Доказательство. Пусть t > 0 - произвольное действительное число. Пусть

σ2j > 0 - дисперсия Z_j,k для любых j ∈ I и k ∈ {1, 2, . . ., n}. Зафиксируем δ > 0

и произвольный (n, R, P )-код. Рассмотрим следующую цепочку неравенств для лю-

бых (i, j) ∈ I × I, где все вероятности и математические ожидания вычисляются

согласно распределению, индуцированному этим (n, R, P )-кодом (см. (8)):

{



}

{

}



∑



∑

1



X_i,kZ_j,k



>δ

=2P

X_i,kZ_j,k > δ

^(a)≤

n



k=1

∑

]

X_i,kZ_j,k

∑

]

(a) 2 E ek=1

(b)

X_i,kZ_j,k+

)

(Pi-

i,k

≤

E ek=1

k=1

(107)

e^δtn

где

(a) следует из границы Чернова;

(b) следует из ограничения на мощность почти наверное (7) для узла i.

Поскольку Z_j,k не зависит от (X^ki, Zk-1j) для каждого k ∈ {1, 2, . . ., n}, непосред-

ственные вычисления показывают, что

∑

]

X_i,kZ_j,k-

X²

i,k

E ek=1

k=1

= 1.

(108)

Объединяя (107) и (108), для любых (i, j) ∈ I × I получаем

{



}



∑



1



2eσjtijnPi/²



X_i,kZ_j,k



>δ

≤

n



eδtij n

k=1

, получаем отсюда, что

σ2jPi

{



}



∑

- δ2n

1



2σ²



X_i,kZ_j,k



>δ

≤ 2e

n



k=1

, заключаем, что

max

σ2jPi

(i,j)∈I×I

неравенство (106) справедливо для всех достаточно больших n. ▴

Теперь мы готовы привести доказательство леммы 1. Зафиксируем δ > 0 и про-

извольный (n, R, P )-код. Пусть p_Xn_,Zn_,Y n - распределение, индуцированное этим

кодом (см. (8)). Используя неравенство для вероятности объединения событий, ра-

венство (45), определение K[xn,yn] в (43) и определение U(δ,P)X,Y в (47), для всех до-

статочно больших n имеем

∫

{

}

p_Xn_,Y n (xⁿ, yⁿ) × 1 K[xn,yn] ∈ U(δ,P)

dyⁿ dxⁿ ≤

X,Y

R^nN R^nN

∫

{

}

≤

p_Xn_,Y n (xⁿ, yⁿ) × 1

Υ[xn,yn] - R[xⁿ]G^t ∈ Γ_δ(0^N×N)

dyⁿ dxⁿ +

R^nN R^nN

107

∫

{

}

p_Xn_,Y n (xⁿ, yⁿ) × 1

Υ[yn,xn] - GR[xⁿ] ∈ Γ_δ(0^N×N )

dyⁿ dxⁿ +

R^nN R^nN

∫

{

p_Xn_,Y n (xⁿ, yⁿ) × 1

R[yⁿ] + GR[xⁿ]G^t - GΥ[xn,yn] -

R^nN R^nN

}

- Υ[yn,xn]G^t ∈ Γ_δ(Σ)

dyⁿ dxⁿ.

(109)

= yⁿ - Gxⁿ, получаем

Υ[xn,yn] - R[xⁿ]G^t = Υ[xn,zn],

(110)

Υ[yn,xn] - GR[xⁿ] = Υ[zn,xn]

(111)

R[yⁿ] + GR[xⁿ]G^t - GΥ[xn,yn] - Υ[yn,xn]G^t = R[zⁿ].

(112)

Объединяя закон канала (8), соотношения (109)-(112) и применяя предложения 4

и 5, получаем

∫

{

}

p_Xn_,Y n (xⁿ, yⁿ) × 1 K[xn,yn] ∈ U(δ,P)

dyⁿ dxⁿ ≤ e^-λn

X,Y

R^nN R^nN

для некоторого λ > 0, зависящего от P и Σ, что завершает доказательство. ▴

Доказательство предложения 1. Зафиксируем Δ > 0 и γ > 0. Поскольку множе-

ство S(P ), определенное в (10), является множеством ковариационных матриц, то

S(P ) - ограниченное множество, содержащееся в

{

}



K ≽ 0, где для ij-го элемента k_ij верно

S(P ) = K ∈ R^N×N



√

|k_ij | ≤

P_iP_j для всех (i, j) ∈ I × I

Определим

{

}



≽ 0, где для ij-го элемента k_ij верно

^K

= K ∈R^N×N



⌈^√PiPj^⌉

 |k_ij | ≤

Δ для всех (i, j) ∈ I × I

Так как S_γ (P ) ⊆ S(P ) ⊆

S(P ) ⊆

S^Δ(P), а множество

S^Δ(P ) содержит не более

(

)

∏

⌈^√PiPj^⌉

Δ-квантователей (см. определение 11), получаем, что мно-

(i,j)∈I×I

(

)

∏

⌈^√PiPj^⌉

жество S_γ (P ) содержит не более

Δ-квантователей, откуда

(i,j)∈I×I

с учетом определения множества L(Δ,γ,P) в (49) следует, что

(

⌈√

⌉

)

∏

PiPj

|L(Δ,γ,P)| ≤

+1 .

▴

(i,j)∈I×I

Доказательство леммы 2. Для любых (xⁿ, yⁿ) ∈ T(n,Δ,δ,P)J(X, Y ) рассмотрим

∏

k=1

108

∏

(a)

k=1

(

)

∑

tr((ΣT c ×T c )-1R[yT c ,k-GT c×I xk(w,yk-1)])

⁽¹⁾= e^-n

k=1

(

))

∑

−n

R[yT c,k -GT c×I x_k(w,yk-1)]

k=1

(113)

где равенство (a) выполнено согласно определению 8. Согласно определениям мно-

жеств T(n,Δ,δ,P)J(X, Y ) и U(δ,P)X,Y в (52) и (47), соответственно, имеем

R[yⁿ] + GR[xⁿ]G^t - GΥ[xn,yn] - Υ[yn,xn]G^t ∈ Γ_δ(Σ),

откуда

∑

R[y_k - Gx_k(w, yk-1)] ∈ Γ_δ(Σ),

k=1

что в свою очередь дает

∑

[

]

y_Tc_,k - G_Tc_×I x_k(w, yk-1)

∈ Γ_δ(Σ_Tc_×Tc).

(114)

k=1

Используя (114) и предложения 3 и 2, получаем

∑

[

]

(Σ_T c_×T c )-1

y_Tc_,k - G_Tc_×I x_k(w, yk-1)

∈ Γ _δN2 (I_Tc).

(115)

^σmin

k=1

Поскольку



(

)



∑

[

]



δN³



r (Σ_T c_×T c )-1

y_Tc_,k - G_Tc_×I x_k(w, yk-1)

- |T^c|

^t

≤

σ_min

k=1

согласно (115), из (113) следует справедливость неравенства (55). ▴

Вывод формул (83) и (84). Пусть (xⁿ, yⁿ) удовлетворяет условию (82), т.е.

K[xn,yn] ∈ U(δ2,P(δ))_X,Y.

По определению множества U(δ2,P(δ))_X,Y в (47) имеем

Υ[xn,yn] - Υ[xn,xn]G^t ∈ Γ_δ2 (0^N×N),

Υ[yn,xn] - GR[xⁿ] ∈ Γ_δ2 (0^N×N )

(116)

R[yⁿ] + GR[xⁿ]G^t - GΥ[xn,yn] - Υ[yn,xn]G^t ∈ Γ_δ2(Σ),

откуда по предложению 3 следует, что

(

)

GΥ[xn,yn] ∈ Γ_Ng

GR[xⁿ]G^t

maxδ²

(

)

Υ[yn,xn]G^t ∈ Γ_Ng

maxδ²

GR[xⁿ]G^t

109

(

)

R[yⁿ] ∈ Γ(2Ng

max+1)δ²

GR[xⁿ]G^t + Σ

(117)

Поэтому соотношения (83) и (84) вытекают из (116) и (117) соответственно. ▴

Авторы благодарят рецензента за внимательное прочтение текста и ценные за-

мечания, способствовавшие значительному улучшению изложения.

СПИСОК ЛИТЕРАТУРЫ

El Gamal A., Kim Y.-H. Network Information Theory. Cambridge, UK: Cambridge Univ.

Press, 2011.

El Gamal A. On Information Flow in Relay Networks // Proc. 1981 IEEE National Telecom-

munications Conf. (NTC’81). New Orleans, LA. November 29 - December 3, 1981. New

York: IEEE, 1981. V. 2. P. D4.1.1-D4.1.4.

Ford L.R., Jr., Fulkerson D.R. Maximal Flow through a Network // Canad. J. Math. 1956.

V. 8. P. 399-404.

Cover T., El Gamal A. Capacity Theorems for the Relay Channel // IEEE Trans. Inform.

Theory. 1979. V. 25. № 5. P. 572-584.

Aleksic M., Razaghi P., Yu W. Capacity of a Class of Modulo-Sum Relay Channels // IEEE

Trans. Inform. Theory. 2009. V. 55. № 3. P. 921-930.

Kramer G., Gastpar M., Gupta P. Cooperative Strategies and Capacity Theorems for Relay

Networks // IEEE Trans. Inform. Theory. 2005. V. 51. № 9. P. 3037-3063.

Aref M.R. Information Flow in Relay Networks. PhD Thesis. Dept. of Statistics, Stanford

Univ., CA, 1980.

El Gamal A., Aref M.R. The Capacity of the Semideterministic Relay Channel // IEEE

Trans. Inform. Theory. 1982. V. 28. № 3. P. 536.

El Gamal A., Zahedi S. Capacity of a Class of Relay Channels with Orthogonal Compo-

nents // IEEE Trans. Inform. Theory. 2005. V. 51. № 5. P. 1815-1817.

10.

Avestimehr A.S., Diggavi S.N., Tse D.N.C. Wireless Network Information Flow: A Deter-

ministic Approach // IEEE Trans. Inform. Theory. 2011. V. 57. № 4. P. 1872-1905.

11.

Behboodi A., Piantanida P. On the Asymptotic Error Probability of Composite Relay Chan-

nels // Proc. 2011 IEEE Int. Sympos. on Information Theory (ISIT’2011). St. Petersburg,

Russia. July 31 - August 5, 2011. P. 1524-1528.

12.

Behboodi A., Piantanida P. On the Asymptotic Spectrum of the Error Probability of Com-

posite Networks // Proc. 2012 IEEE Information Theory Workshop (ITW’2012). Lausanne,

Switzerland. September 3-7, 2012. P. 148-152.

13.

Behboodi A. Réseaux coopératifs avec incertitude du canal (Cooperative Networks with

Channel Uncertainty). PhD Thesis. Dept. of Telecommunications, Supélec (École Supérieure

d’Électricité), Gif-sur-Yvette, France, 2012. Available at http://tel.archives-ouvertes.

fr/tel-00765429.

14.

Han T.S. Information-Spectrum Methods in Information Theory. Berlin: Springer, 2003.

15.

Fong S.L., Tan V.Y.F. Strong Converse Theorems for Classes of Multimessage Multicast

Networks: A Rényi Divergence Approach // IEEE Trans. Inform. Theory. 2016. V. 62. № 9.

P. 4953-4967.

16.

Polyanskiy Y., Verdú S. Arimoto Channel Coding Converse and Rényi Divergence // Proc.

48th Annual Allerton Conf. on Communication, Control, and Computation. September 29 -

October 1, 2010. Allerton, IL, USA. P. 1327-1333.

17.

Kötter R., Effros M., Médard M. A Theory of Network Equivalence—Part I: Point-to-Point

Channels // IEEE Trans. Inform. Theory. 2011. V. 57. № 2. P. 972-995.

18.

Dana A.F., Gowaikar R., Palanki R., Hassibi B., Effros M. Capacity of Wireless Erasure

Networks // IEEE Trans. Inform. Theory. 2006. V. 52. № 3. P. 789-804.

19.

Csiszár I., Körner J. Information Theory: Coding Theorems for Discrete Memoryless Sys-

tems. Cambridge, UK: Cambridge Univ. Press, 2011.

110

20.

Fong S.L., Tan V.Y.F. Achievable Rates for Gaussian Degraded Relay Channels with Non-

vanishing Error Probabilities // IEEE Trans. Inform. Theory. 2017. V. 63. № 7. P. 4183-4201.

21.

Truong L.V., Fong S.L., Tan V.Y.F. On Gaussian Channels with Feedback under Expected

Power Constraints and with Non-vanishing Error Probabilities // IEEE Trans. Inform.

Theory. 2017. V. 63. № 3. P. 1746-1765.

22.

Csiszár I., Körner J. Feedback Does Not Affect the Reliability Function of a DMC at Rates

above Capacity // IEEE Trans. Inform. Theory. 1982. V. 28. № 1. P. 92-93.

23.

Ozarow L.H. The Capacity of the White Gaussian Multiple Access Channel with Feedback //

IEEE Trans. Inform. Theory. 1984. V. 30. № 4. P. 623-629.

24.

Massey J.L. Causality, Feedback and Directed Information // Proc. 1990 IEEE Int. Sympos.

on Information Theory and Its Applications (ISITA’90). Waikiki, Hawaii. November 27-30,

1990. P. 303-305.

25.

Marton K. A Simple Proof of the Blowing-Up Lemma // IEEE Trans. Inform. Theory. 1986.

V. 32. № 3. P. 445-446.

26.

Liu J., van Hendel R., Verdú S. Beyond the Blowing-Up Lemma: Sharp Converses via

Reverse Hypercontractivity // Proc. 2017 IEEE Int. Sympos. on Information Theory

(ISIT’2017). Aachen, Germany. June 25-30, 2017. P. 943-947.

27.

Oohama Y. Strong Converse Exponent for Degraded Broadcast Channels at Rates Outside

the Capacity Region // Proc. 2015 IEEE Int. Sympos. on Information Theory (ISIT’2015).

Hong Kong, China. June 14-19, 2015. P. 939-943.

28.

Oohama Y. Exponent Function for Asymmetric Broadcast Channels at Rates Outside the

Capacity Region // Proc. 2016 IEE Int. Sympos. on Information Theory and Its Applications

(ISITA’2016). Monterey, CA, USA. October 30 - November 2, 2016. P. 537-541.

29.

Tan V.Y.F. On the Reliability Function of the Discrete Memoryless Relay Channel // IEEE

Trans. Inform. Theory. 2015. V. 61. № 4. P. 1550-1573.

30.

Arıkan E., Merhav N. Guessing Subject to Distortion // IEEE Trans. Inform. Theory. 1998.

V. 44. № 3. P. 1041-1056.

31.

Kelly B.G., Wagner A.B. Reliability in Source Coding with Side Information. arXiv:1109.

0923 [cs.IT], 2011.

32.

Petersen K.B., Pedersen M.S. The Matrix Cookbook. Technical Univ. of Denmark, 2012.

Available at http://www2.imm.dtu.dk/pubdb/p.php?3274.

33.

Санов И.Н. О вероятности больших отклонений случайных величин // Матем. сб. 1957.

Т. 42 (84). № 1. С. 11-44.

Фон Сайлас Лик Хан

Поступила в редакцию

Факультет электротехники и компьютерной техники,

24.07.2018

Университет Торонто, Торонто, Онтарио, Канада

После доработки

silas.fong@utoronto.ca

16.01.2019

Тань Винсент Янь Фу

Принята к публикации

Факультет электротехники и компьютерной техники,

18.01.2019

факультет математики,

Национальный университет Сингапура, Сингапур

vtan@nus.edu.sg

111