Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
5.34. Из (5.8.69) имеем
max 2 pU i k)
* i
<»(/)
(1)
P(i\k)l
где со (/) = 2 Q (k) P (j\ k) с Q, на котором достигается пропускная способ
ность. При со(у') > P(j\k) используем неравенство (In*)2
для х > 1.
Это неравенство следует непосредственно из того, что (In*)2 — ----------------------- х
е2
при х > 1 имеет минимум, равный 0, который достигается в точке * = е2, При (Oj <С Р (/1 к) получаем
1п
<»(/) P(i\ k)
In
P(i\k) СО (/)
All2
/') J
ln
P(!\k)-CO O') .
l
CO ( /> .
629
Используя эти неравенства и полагая Bk={j : со ( ) < P(i\ k)}, пыводим
У>Р(ЦЬ)
/
1п
С0(/)
P(i\k)
42 + 2р(/|А) ln-^-Ц^ 1п-
е" «с В»,
1
©(/) ©(/)
1
max In --------
/ ©(у)
2Я(/|*)1п —77^-
^ <о(1)
Из (5.8.60) будем иметь
5j Р (i \ k) In —- < с при всех к,
, со (/)
(2)
(3)
с+ У, я (Л ft) in —^— f 1 P(i\k)
2lnJ при всех ft.
Таким образом,
ln
1
2 In 7
©(/) PCl\k)
при всех ft.
(4)
Отсюда следует, что (4) справедливо для ft, которое максимизирует Р (/1 ft). Имеем
max In---------
/ ©(/)
max
/
In J
max P (j | ft) k
2 ln 7
min [max Я (Д ft)] / *
Для последнего выражения в (2) , используя (3), будем иметь 2 Я(/|*)1п < С + ^Р(Цк)1п-^~
©(/)
P(i\k)
(5)
(6)
Используя неравенство In х ^ - л: при л: > 1, получаем следующую границу сверху для (6):
^p(j]k)lnpim<c+A.
в1 ©(/) е
InJ + —• е
(7)
Подставляя (5) и (7) в (2), получаем искомый результат. Для того чтобы понять, почему нельзя выразить границу для А лишь через объем алфавита, рассмотрим изображенный ниже канал, где е произвольно мало.
После некоторых вычислений можно найти, что для пропускной способности нужно, чтобы Q (1) sre-11г. Более того, максимизирующим входом при отыскании А будет ft= 1 и Л я: 1/s. Таким образом, А нельзя ограничить лишь в терминах объема алфавита,
630
5.35. Применяя границу Чернова (5.4.15) к (5.8.66), получаем
2 Pn (У I xm) < е_sN (С+ е) [g (S)1'V при любом s > О, У?Вт
8 (s) = 2 Q (А) Р (/ I А) ехР Is In ^^ ------1
u { 2 Q(О Р(Ц 0 j'
Границу (1) можно переписать в виде;
2 ?V(y|xm) <ехР {—Л'ИС + е) —lng(s)]}, s > 0.
уев,„
(1)
(2)
Так как g (s) является производящей функцией моментов взаимной информации, то
dlng(s)
ds
¦-С.
s =0
Поэтому при любом 8 > 0 значение s (С + е) — In g (s) является положительным для достаточно малого s > 0. Подставляя (2) и (5.8.65) в (5.8.64), получаем
ехр [./V (С+е)] .
-+ехр { — -V [s(C + s) — lng(s)]}.
М
Для любой скорости R'P’C пусть М = Г ewi^ j и пусть е = (#—С)/2. Тогда
¦ ехр
Ре (N, j eNR~l ) > 1 —ехр R— С
- N
R-C
{-4
s С +
a (R) — min
R —С
-------, max
2 s >о
j — lng-(s) J> 1— 2 ехр [— Na (R)], R-C\
s C-
-lng-(s)
>0.
5.36. При заданном кодовом слове xm взаимная информация I (хт; у) является суммой N независимых случайных величин:
N
I (Xml у) = 2 ^ (ХТП, п': Уп)' (О
п= 1
где хт,п фиксированно, а уп выбирается в соответствии с распределением вероятности Р (уп | хт,п)- Из (5.8.60) следует, что каждая из этих случайных величин имеет среднее значение, не большее, чем С так, что I (xm; YN) (среднее значение I (xmJ У) ПРИ фиксированном хт) удовлетворяет неравенству
JVC > I (xm; Yn).
Введем теперь обозначение
А (*т, п) — ^ (хт, я» Уп)]-
(2)
(3)
Отметим, что А (хт,п) определяется лишь тем, какой буквой алфавита является хт,п- На основании теоремы Берри-Эссена имеем
Рг [/(хт; у) > NC + VN | хJ <
< Рг [/ (хт; у )> I (хт; Yw) + 8Х YN | хт] <
