Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
1 (X; У | Z)</ (X; У). (4.4.33)
Так как это эквивалентно (4.4.26), то доказательство теоремы закончено. |
Другое (более прямое) доказательство намечено в задаче 4.16. Приведенное здесь доказательство обладает преимуществом большей общности и оно применимо, в сущности, к любым каналам. До того как использовать этот результат при вычислении пропускной способности
106
канала, докажем тесно связанную с ним теорему, которая полезна как при исследовании неизвестных каналов, так и в гл. 9.
Теорема 4.4.3. Рассмотрим I (Х\ У) в (4.4.25) как функцию переходных вероятностей Р (/'| k) и входного распределения Q(k). При фиксированном входном распределении I (Х\ У) является выпуклой ^ функцией переходных вероятностей (отметим, что она является выпуклой а не выпуклой как в теореме 4.4.2).
Доказательство. Пусть Р0 (/1 k) и Р г (/ | k), 0 -< k С К — 1; 0 -< /
— 1, два произвольных множества переходных вероятностей и пусть Р (/1 k) = QP0 (j | k) + (1 — 6) P г (/1 k) для любого 0, 0 < 0 < 1. Пусть /о, 1г и / являются средними взаимными информациями для этих множеств переходных вероятностей. Требуется показать, что
Как и в последней теореме, вероятности Р0 и Рг можно рассмотреть как условные при условии, что задана двоичная случайная величина z, т. е.
ро (/1 k) = pY\xz а I к о)-, рг а | щ = Ру | xz а \ к i). (4.4.35)
Полагая Pz (0) = 0, Pz {1) = 1 — 0 и определяя z статистически независимой от х, находим, что левая часть (4.4.34) равна / (Х\ Y\Z), а правая часть равна / (X; У). Продолжая далее, так же как и в последней теореме, будем иметь
Теорема 4.5.1. Для дискретного канала без памяти с переходными вероятностями Р (j | k) необходимые и достаточные условия того, что на входном векторе вероятностей Q = [Q(0), ..., Q (К— 1)] достигается пропускная способность канала, состоят в том, что для некоторого числа С
I (х = k; Y) = С при всех k, для которых Q (k) > 0, (4.5.1)
/ (х — k\ Y)^C при всех k, для которых Q (k) = 0, (4.5.2)
где 1 (х = k\ Y) является взаимной информацией при входе k, усредненной по выходам, т. е.
0/о + (1 - 0)h>I-
(4.4.34)
(4.4.38)
(4.4.39)
(4.4.36)
(4.4.37)
4.5. НАХОЖДЕНИЕ ПРОПУСКНОЙ СПОСОБНОСТИ ДИСКРЕТНОГО КАНАЛА БЕЗ ПАМЯТИ
Kx^k- У)-= 2P(/|*)log
р a I k)
(4.5.3)
107
Более того, число С равно пропускной способности канала.
Доказательство. Требуется максимизировать величину
(X; Y)= ^Q{k)P{i \k)\og k, i
P(i\ k)
%QV)PU\i)
по всем Q. Взяв частные производные, получим**
dJ?w=,ix=k'- r)-loge'
(4.5.4)
(4.5.5)
в)
Рис. 4.5.!.
Можно применить теорему 4.4.1 для того, чтобы произвести максимизацию; это можно сделать, так как I (Х\ Y) является выпуклой по Q и частные производные удовлетворяют соответствующим условиям непрерывности. Таким образом, необходимыми и достаточными условиями, которым должно удовлетворять Q, максимизирующее / (X; Y), являются условия
Q(k)> 0, (4.5.6)
оЦ (к) »
Q (k) = 0. (4.5.7)
Используя (4.5.5) и полагая С = Я + Jog е, получаем (4.5.1) и
(4.5.2). Умножая обе стороны (4.5.1) на Q (k) и суммируя по всем
k, для которых Q (к) > 0, получаем слева максимальное значение
I (X; Y) и справа постоянную С, что показывает, что С действительно является пропускной способностью канала. |
*> Отметим, что сумма в знаменателе, стоящая под знаком логарифма в (4.5.4), содержит слагаемое Q(k) Р(j | k); это слагаемое приводит к log е в (4.5.5).
108
Теорема 4.5.1 допускает простую интуитивно понятную интерпретацию. Если одна входная буква приводит к большей взаимной информации, чем другая буква, то можно увеличить среднюю взаимную информацию, используя входы с большей взаимной информацией чаще. Однако любое такое изменение будет изменять взаимную информацию каждой буквы и, следовательно, после достаточного числа изменений все входы будут иметь одну и ту же информацию, за исключением, возможно, нескольких^в’ходов, которые столь малозначительны, что их вероятности сводятся к нулю.
Несмотря на изящность теоремы
4.5.1, остается открытым вопрос о том, как использовать ее при практическом вычислении пропускной способности канала. Ниже будут даны несколько методов практического вычисления пропускной способности. Начнем с рассмотрения примеров, изображенных на рис.
4.5.1.
В двоичном симметричном канале (ДСК), изображенном на рис. 4.5.1, а можно использовать симметрию, чтобы догадаться, что пропускная способность достигается на Q (0) = Q (1)= 7а. Проверяя эту догадку с помощью (4.5.1), получаем I (х = 0; Y) = = I (х = 1; Y) — 1 —Ж (в) бит, где Ж (в) = — е log2 е — (1 — е) X Xlog2(l — е) является энтропией двоичной случайной величины, принимающей значения с вероятностями е и (1 — е). Так как (4.5.1) справедливо для обоих входов, то это Q приводит к пропускной способности и С = 1 —Ж(е) бит. Таким образом, одно из важных применений теоремы состоит в том, что она дает простой тест для проверки любой гипотезы относительно достижения пропускной способности на заданных входных вероятностях. Это означает также, что можно проявить математическую беззаботность при отыскании Q, которое приводит к пропускной способности, так как результат поддается легкой проверке. Пропускную способность двоичного стирающего канала (ДСтК), изображенного на рис. 4.5.1, б, можно найти подобным же образом. Можно догадаться, что Q (0) = Q (1) = 72 и проверить, что 1(х = 0; Y) = I (х = 1; Y) = С = 1 — е. Эти пропускные способности изображены на рис. 4.5.2. На рис. 4.5.1, в заметим ту же самую симметрию и опять убедимся с помощью проверки, что пропускная способность достигается на Q (0) = Q (1) = 72. Рис. 4.5.1, г при поверхностном рассмотрении кажется подобным рис. 4.5.1, в, однако в некотором отношении он является менее симметричным и если предположить, что Q (0) = Q (1) = V2, то найдем, что (4.5.1) не удовлетворяется и, следовательно, пропускная способность не достигается на этих вероятностях.
