Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Р^М<(М- l)P2(2QN(x)P„(ylx, %>1/(1+р)11+р. (4)
у ' X I
Для того чтобы вывести равномерную границу для Ре> m(s0)> умножим это выражение на 4 и возьмем максимум по s0, получим (5.9.5) без коэффициента Если передатчик знает также начальное состояние, то можно произвести минимизацию по QN (х) раздельно для каждого s0, изменяя порядок знаков min и max в (5.9.5).
(в) Доказательство того, что при независимых равновероятных входах достигается минимакс в (5.9.5), аналогично доказательству, приведенному в ре-
633
шснии задачи 4.23; единственное отличие состоит в том, что выпуклость применяется здесь к (5.9.5), а не к средней взаимной информации. Для нахождения максмина заметим, что при заданном s0 канал эквивалентен паре параллельных каналов без памяти и оптимизирующее входное распределение совпадает с тем, на котором достигается С.
5.38. (а) / (ХЛ'; Y'v | s„) = Я (Yw | s„) — Я (Yw | \N, s„) =
= Я (Y'v I s0)—Я (ZA'| s0).
Ho lim -~H(ZN | s0)=H(x (Z) и H{\N | s0) < ЛПп 2
N-*oc N
с равенством для равновероятных выходов, которые образуются при равнове-
роятных входах. Поэтому С = 1п2 — Я^ (Z).
(б) Заметим, что PN (у | х , s0) является вероятностью того, что z принимает значение у — х при заданном s0, т. е. Pz (у — x|s0). Следовательно,
у ^ X '
Полагая z = у — х и замечая, что для фиксированного у суммирование по всем х эквивалентно суммированию по всем z, получаем
Z0,n(P. Q N, so) = --Jr 1п2{2^Д: (z|s0)1/<I+p)}1 + P =
1
.__— in • 2~~n <1 + p)
N
2 P7 (z I s0)I/(1 + p)
l + P
= P In 2 Pz(z|So)1/(1 +p).
(в) Поскольку z является выходом марковского источника, то z и s0 однозначно определяют последовательность состояний s = (s1; s2, ..., sN) (см. § 3.6). Следовательно,
f Р (z I s0) для определенного s,
P(s, z(s„) = *
[ 0 для всех остальных s,
Eo, n(P> °А' , In 2 — 1 + P ln 2p(s, z I S0)1/(1+ p> =
N s, z
N
=pln2_-i±Linx: n yp(S„, 2Il|Sn-l),/(i+p>.
s n= 1 *n
a(s„_b s7)) = VP(sn, z„ | s„ _ г)1 /(1 + P), гп
N
E0,n(P> Qn, so) = P !n 2 П a(sn-i, s„).
s n=l
Это выражение теперь имеет тот же самый вид, что и выражение в (5.9.37). Также А X A-матрица [сс(р)] с элементами а(г, /) является неприводимой, так как цепь Маркова по предположению является эргодической. Поэтому с помощью тех же рассуждений, что и при переходе от (5.9.37) к (5.9.44), получим
Поло жив
получим
Пт Е0 Л,(р, Qw ; s ) =р In 2 — (1 + р) 1п Л. (р),
N -* ОС
634
где Х(р) является наибольшим собственным значением [а(р)].
5.39. Так как sn является детерминированной функцией уп, то
I РЛ, (у | х, s0) для s, соответствующего у,
Р (y>s I х> so) — 1 „
I. О во всех остальных случаях.
Таким образом,
H{\N | \N , s„) = -lnP(y,s|x, S„) , где математическое ожидание берется по х и у при заданном s0. Имеем
H{\N \XN , s0)-- In П Р(!/п,*п\хп,*п-1) =
П= 1
N __________________________ _____________________
= — 2 1пР(Уп, sn\хп, sn_1) ; — In Р(уп, sn j хп, $„_г) =
П = 1
" 2 Р (у П * Sn, Хп , Sn.il S0) In Р (уп , Sn | Хп , Sn _ i) —
Уп > sn , xn , sn-1
= 2 0)1 (Xll) P (sn - 1 I So) P (.Уп 1 xn> sn -1) X
xn , sn-l, Уп
X In P (yn | xn, sn-1) =H (Yn ] Xn ,Sn_ j, s0). (1)
Поскольку последовательность состояний не зависит от входа, то вероятность P(s„_1|s0) не зависит от входного ансамбля и поэтому Н (Y п\Хп, Sn-\, s0) зависит от входного ансамбля только через Qn(xn)• Также имеем
N
tf(Y'vUo)= ^HiYnlYn-!, Yn-i, .... s„) =
= 1
N N
= 2 HiYnlSn-г, Yn-u .... Ylt s0) 2 Я O'" I S«~i> so) ¦ (2)
fl= 1 n = 1
Замечая, что yn зависит от предыдущих выходов только через sn-1 и что имеет место статистическая зависимость между входными буквами, получаем, что (2) удовлетворяется с равенством при независимых входах. Объединяя (1) и (2), будем иметь