Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
* =(ai, «2.
S log е
Беря производную, преобразуя выражение и обозначая К = —^— (эта
/v*+s*
= К при Si > 0,
> К при Si = 0.
(1)
k
будут связанными с ними распределениями вероятностей на выходе.
и пусть
СО (/)= SQ(A)P(/|A) к
(2)
596
со (/) = 00)! (/)+(1— 0) ш2 (/).
(3)
Нам нужно показать, что
е//1(К) + (1-0)//,(П<я(П. (4)
где Нг (У), Н2 (У) и Н (У) являются энтропиями ш1 (/), (о2 (/) и со (/) соответственно. В задаче 4.10 (б) было показано, что (4) справедливо и поэтому Н (У) является выпуклой гл в области векторов вероятностей на входе.
(б) Заметим здесь, что Н (Y) является строго выпуклой о по распределению вероятностей на выходе, но не является строго выпуклой по распределению вероятностей на входе. Какой-либо пример, в котором входные вероятности могут быть изменены без изменения выходных вероятностей, был бы ответом на этот пункт задачи.
(в) -я (14 X) = 2 Q (А) 2]Р (/I A) log Р(М ft).
* /
Это выражение является линейным по Q (k) и, следовательно, выпуклым г~\ по Q.
(г) Согласно свойству 1 на стр. 101 I (X; Y) = Н (Y) — Н (Y | X) является выпуклой о по Q. Недостатком этого доказательства по сравнению с доказательством в теореме 4.4.2 является то, что оно не распространяется на недискретные каналы, в которых Н (Y) не определено.
4.17. Средняя взаимная информация для входного распределения вероятности Q0 равна
/о (Х\ K) = 2Qo(6)/(* = fe; Y) < С.
Пусть J (Q) обозначает среднюю взаимную информацию между X и К при входном распределении Q. Переписывая соотношение, определяющее выпуклость для J (Q), будем иметь
J [0Qi + (l—0) Q0] —J (Q0)
0
J (Qi) < J (Qo) +
Переходя к пределу при 0-^0, получаем
J (Qi) < J (Qo) + 2 17 Wi (*)'^ ¦
? ^yVO (K)
Это соотношение утверждает, что функция J (Q) лежит ниже гиперплоскости, которая касается J (Q) в точке Q0. Выполняя дифференцирование [см. (4.5.5)], получаем
J (Qi) < 2 Qi (k) I о {x=k\ У). k
Отсюда, обозначая через Qx такое Q, на котором достигается пропускная способность, будем иметь
С < шах /0 (x = k; У). (1)
k
Наконец, для Q0, на котором достигается пропускная способность, согласно теореме 4.5.1 имеем
С—тах I0(x = k; Y). \(2)
k
Из (1), (2) следует, что
C = min max 10 (x = k; У).
Qo *
4.18. (а) Пусть Q; (k) является входным распределением, на котором достигается пропускная способность i-ro канала, и пусть Pi (j | k) представляет со-
597
бой переходные вероятности i'-го канала. Тогда взаимная информация, соответствующая ft-му входу i'-го канала, равна
(б) Рассматривая канал как сумму каналов со входами 0,1 от первого канала и 2 от второго, получаем
Сх = 1—Ж(г) [бит], С2 = 0,
и, таким образом, / (X; Y) = Н (Y) — Я (Z).
(б) Пропускная способность отыскивается с помощью максимизации Я (Y). В силу симметрии шума по отношению к различным входам равновероятные входы дают равновероятные выходы и, следовательно, пропускную способность
4.20. Каналы а), г) и д) являются симметричными, и пропускную способность в каждом из них достигается на равновероятных входах. Небольшое усилие позволяет догадаться, что пропускная способность для каналов (б) и в) достигается на Q (0) = Q (2) = 1/2; Q (1) = 0. Пропускные способности (в битах) равны
/(* = (*, i)\Y) = ^PiU \k)log
i
= Ct + log— при Qi (k) > 0.
4i
Применяя теорему 4.5.1 к сумме каналов, получаем
C = Cj + log— при всех (, Я1
(I)
Отсюда, используя условие 2 = 1. выводим
C=log22 2С*.
Умножая далее обе части (1) на qt и суммируя по г, получим
C = log2 [1+21-Ж <е>] = logg[ 1 + 2еЕ (1 — е)1—Е] • 4.19.(а) /(X; Y)=H(Y)— H(Y\X),
Замечая, что P(j\ k)=Pz([j—fe) mod/C), получаем, что
C = \ogK-H(Z).
(д) log2 4,-26 (8).
Канал е) дан для того, чтобы продемонстрировать трудность непосредственного вычисления пропускной способности даже для простейшего канала, у которого нет упрощающей симметрии. Можно использовать метод, представленный (4.5.9)—(4.5.12), или прямые вычисления на основе теоремы 4.5.1; оба они требуют приблизительно одинаковое количество усилий. Получим
