Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
(9.4.27)
Так как dFj (p, P, f)/dP (j (k) \ k) = 0, то, очевидно, в (9.4.27) сумма по / Ф /' не имеет членов первого порядка по е, так что с точностью до членов первого порядка по е
s
F (р, Р', f)-F (Р, Р, f) = 2 Q (k) Р' (/' I k) In
k
^(i(k)P'(i'\k) - k
477
- 2 Q (k) P' (/' | k) In-—• (9.4.28)
2Jk* k
Так как P минимизирует F (p, P, f), то правая часть (9.4.28) неотрицательна, откуда следует
j,
k
что завершает доказательство теоремы. |
Следствие 9.4.1. Для конечной меры искажения с d,*ax >
> 0 наклон R (d*) непрерывен при 0 < d* < d*nax и стремится к —оо при d*, стремящемся к 0.
Доказательство. Как было показано, R (d*) выпукла w и min R0 (р, Р) является точкой пересечения оси R с касательной к R (d*) р
с наклоном ¦—р. Если наклон имеет разрывы или если он сходится к конечному пределу при d* 0, то на кривой R (d*) должна быть точка, которая является точкой касания различных касательных с наклонами из некоторой области. Любое Р, при котором достигается эта точка на кривой R (d*), должно тогда минимизировать R0 (р, Р) для этой области наклонов. Для завершения доказательства остается показать, что если Р минимизирует R0 (р, Р) для двух различных значений р, скажем р и р', то У (Q; Р) = 0. Пусть f' — максимизирующее f для р';
имеем
P(j\k)= &Wk.e~pd(k-j) (9.4.29)
1 ’ Q(k) Q (k)
Следовательно, если со (/) > 0, то
Ik=e(P-P')d(k-,i)' (9.4.30)
• k
Это означает, что d (/г; /) не зависит от / для всех / с со (/) > 0 и, следовательно, как вытекает из (9.4.29), Q (k)P (/ | k) = со (/)а (k), где а (k) —
= fk ехр [—р (d; /)] не зависит от /. Следовательно, Р (/1 k) = со (/) и Cf (Q; Р) = 0. |
Задача 9.1 дает пример кривой R (d*), у которой наклон теряет непрерывность при d„ax, а задача 9.4 показывает, что ограничение на конечность меры искажения в следствии является необходимым.
Следствие 9.4.2. R (d*) является непрерывной функцией d* при d* ^ 0.
Доказательство. Так как R (d*) выпукла ^ и не возрастает с d*. при d* ^ 0, то, как известно, функция R (d*) должна быть всюду непрерывна, за исключением, быть может, точки d* = 0. Итак, поскольку R (d*) ^ Я (U) для d* ^ 0 и поскольку R (d*) не может убывать с убыванием d*, то, как известно, существует
478
lim R (d*).
d* - о+
Следовательно, остается только показать, что
R(0)= lim R(d*). d*^ 0+
Для этого рассмотрим новую меру искажения d' (k\ /), задаваемую равенством
d' (*; rt - I °’ есл"‘1<*Л = 0’ (9.4.31)
{оо во всех других случаях.
Скорость как функция искажения для d' (k; /) равна R’ (d*) = R (0), d* ^ 0, так как среднее искажение для любого Р, равно или 0 или оо, и R (0) является минимумом J(Q; Р), для которого среднее искажение равно 0. Следовательно, функция
minR' (р, Р) р
для d' (k\ j) также равна R (0) при всех р > 0, и, используя (9.4.8) для
min R'0 (р, Р) р
при любом р > 0, получаем
R (0) = Н (U) + max 2 Q (k) In К (9.4.32)
V k
при ограничении
Щ'h Для всех /. (9.4.33)
fc:d(&;/) = 0
Взяв р достаточно большим, можно аппроксимировать f', которое максимизирует (9.4.32) при условии (9.4.33), сколь угодно точно с помощью f (р), которое удовлетворяет
2Мр)е~р^(&:/) ^ 1 для всех /. (9.4.34)
k
Следовательно, для любого е > 0 можно выбрать р достаточно большим, так что
min R0 (р, Р)> H(U) + ^Q(k)\nfh(p)> R(0)~e. (9.4.35)
Р к
Так как
R (d*) ^ min R0 (р, Р) — pd*, р
то имеем
min R (d*) > R (0) — е при любом е>0. d*^0
Так как R (d*) R (0) для d* ^ 0, то это завершает доказательство. | Следствие 9.4.3. При любом заданном d* для достижения R (d*) требуется не более К + 1 букв алфавита адресата. Для любой части кривой R (d*), для которой наклон не является постоянным,
моЛно использовать не более К букв адресата. -----------
479
Доказательство. Для любого заданного р пусть f максимизирует правую часть (9.4.8) при условии (9.4.9). Из теоремы следует, что Р, которое минимизирует R0 (р, Р), может быть найдено из (9.4.5), где выходные вероятности удовлетворяют равенствам