Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
С чисто математической точки зрения это включает в себя дополнительное предположение, что последовательность источника связана с последовательностью, которая выдается адресату с помощью /V-кратного использования канала
N
Р (у I х,и) = Р (у I х) = П Р (Уп | хп).
п= 1
Просуммируем обе части этого равенства по Уп+\---Ун- Разделив результат на Р и), получим (1). Из теоремы 2.3.3 и (1) следует, что I (U; Yn\XnYj...
•..К„_1) = 0. Для завершения доказательства воспользуемся тем, что / (Хп\ Yn | Уг ... Yn-1)=H (Yn | ... Yn-i)—H (Yn \ Xn Ki... Yn-1).
Поскольку канал является каналом без памяти, то имеем H(Yn\Xn Y1...Yn-1) = H(Yn\Xn)
и
ЦХп\ Yn\Yx ...Yn-i) < Н (Yn)-H (Yn\Xn) = I (Хп\ Yn).
Если выход канала \N преобразуется в последовательность V, которая поступает к адресату, то
N
I (U; V) < I (U; Yn) < I (Xn\ Yn) < NC.
n= 1
Обращение теоремы кодирования получается теперь точно таким же образом, как это было для каналов без обратной связи.
4.7. Для ансамбля W с вероятностями qi имеем
Н (Ц7) = 2 — Qi In Qi > 2 — Qi (Qi 1) ^ 2 Qi (1 Qmax)= 1 Qmax-
i i i
Применяя этот результат к Н (U\v) и замечая, что Ре (v) равно 1 — Qmax, будем иметь Н (U \v) > Pe(v). После умножения на Pv (v) и суммирования по v, получим Н (U | V) > Ре. Для получения более сильного результата предположим сначала, что Qmax> 1/2. При заданном qmax > 1/2 величина Н (W) достигает
минимума по qi при q1 = qmax• Qz=\—Qmax, так что
Н (W)> Qmax 1°б2 qmax (1 —Qmax) logj (1 Qmax)-
Выражение, стоящее справа, равно 2(1—qmax) при qmax = 1l2 и qmax=l-В силу выпуклости оно всюду ограничено снизу 2(1—qтах)- В случае, когда
593
Чтах < !/г. имеем
H.[W) = ^ Qi log — > S 4i log ------------= “log Чтах-
Qi i Чтах
Это выражение равно 2(1—qmax) в точке qmax = 1/2, но имеет производную — (log e)/?max< —2 и, таким образом, превосходит 2 (1 —qmax) при qmax<llа.
1 L 1
4.8. — ^ M(Pe,i)=-~r2i [Pe,llogPe,i + (l ~Pe.i)log(l-Pe,i)l, L l=i L I
&(Рв)]= -Pe log Pe-O-Pe) log (1-Pe) =
= -T“S 1^, г !og Pe + (1 — Pe>/) log (1 ~Pe)],
L I
4~^^(Pe,l) -^(Pe) = ^-'ZiPe,ll0g^- +
L L j Ге, I
1 — Pe log e ( I Pe \
7Г7<—?{'>-(^-1) +
1 -Pe
+ 0-P*. /)
1-
e. I
= 0.
4.9. Эта задача сформулирована не очень аккуратно, но ее цель показать, что если d2f (a)/da2 < 0 на некотором интервале, то / (а) является выпуклой гл на этом интервале. Для любых а и р из этого интервала и любого 0, 0 < 0 < 1, пусть б = 0a + (1 — 0)р. Используя разложение в ряд Тейлора в окрестности б, будем иметь
/ (а) = / (б) + (а - б) /' (б) + ~ ~ 6)Я - Г (У) ¦
при некотором у между б и а. Так как /" (у) < 0, то
/ (а) < / (б) + (а — б)/' (б). (1)
Аналогично
/ (Р) < / (б) + (Р - 6) /' (б). (2)
Имеем
0/ (a) + (1 -0) / (Р) < / (б) + [0 (а - б) + (1 - 0) (Р - б)] Г (б) = f (б)
в силу того, что 0а — 06 + (1 — ©) Р — (1 — 0) б = б — б = 0. Если вто-
рая производная строго отрицательна, то неравенство (1) является строгим и выпуклость является строгой. В обозначениях рис. 4.4.2 (1) и (2) связывают
ординаты концевых точек кривой и величины отрезков прямых 0 = 0 и 1, отсе-
каемых касательной к кривой в точке © = б.
Равенство (4.4.5) тривиально при L = 1 и равносильно определению выпуклости при L = 2. Предположим теперь, что (4.4.5) справедливо для L < п — 1; покажем, что оно справедливо для L = п, и по индукции это завершит доказательство. Имеем
п п— 1 0г
2 в*/(се*)= (1—е„) 2 -r-^rf(°4)+®nf(vn) <
(=1 i = l ‘“ип
{ " ®г \
<(1 —0п)/( 2 1_0 ) +®nf(an) < (3)
/ п \
< / ( 2 0г“г )• (4)
594
Неравенство (3) следует из справедливости (4.4.5) для L = п — 1 и того, что сумма ©,/(1 — 0П) по 1 < i < п — 1 равна 1. Неравенство (4) следует из определения выпуклости.
4.10. (а) Так как 0 < А, < 1, то A,Qi (лг) + (1— k)Q2(x) > 0 для любого х из выборочного пространства. Также имеем
