Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
[2Kpw(ylx) pn( у | х') ] 1/р=
N
в качестве элемента, стоящего на пересечении строки х и столбцах'. Для заданной последовательности \т ,\т , ¦¦¦, ввеДенных выше собственных векторов
пусть г) будет вектором с KN компонентами г) (х) = ?mi (*i) (хг) ...
(т. е. одна компонента для каждой входной последовательности х). Теперь
2(х) |2 ypN(y \x)pN(y I*')]1/р •
627
= П 2 bnn(Xn)\'2iVP(yn\Xn)P(yn\Xn)YlP =
n=I хп Lуп
= П hmnlmn(xh)= Г П %тп П (х')-
п= 1 1
Поэтому г] (х) является собственным вектором В с собственным значением
N
П К > 0. Можно получить таких собственных векторов с помощью рассмо-
л=1 и
трения всех возможных наборов щ, m2...... mN и, если
л'(х)=Ет; М-l' (xN),
N
2n(x)n'(x) = П 2 1тп(Хп)% '(хп)= о,
х л = 1 п
если тп ф тп для некоторого n, 1 < га < N.
Таким образом, найдены KN ортогональных собственных векторов матрицы В, каждый из которых соответствует неотрицательному собственному значению. Поэтому В является неотрицательно определенной матрицей и
2 Qn W Qn (х') [2 VPN (у I х) PN (у ! х')
1/Р
является выпуклой w функцией по Q. Теперь теорема 4.4.1 дает необходимые и достаточные условия для максимума этой функции, взятой со знаком минус; непосредственно проверяется то, что произведение распределений QN (х) =
N
= П Q(xn ) удовлетворяет этим условиям, если Q(xn) выбрано так, чтобы
Л=1
максимизировать
2Q(*)Q(0 [S yp(il*)pui0]l/p-
5.31. Напомним, что согласно задаче 5.24
lim Eex(R, Q)=-'ZiQ(k)Q(i)\n'XVPU\k)PU \ i).
R^O k,i /
(1)
Так же как и в примере 3 на стр. 163, определим с помощью равенства
P(l\k) = t0j(l+Bjk), (2)
где Wj является распределением вероятностей и Ejk ние в ряд до второго порядка по Sjъ, получаем
Производя разложе-
1п 2 VP(i\k)P(i\i)= in 2 wy i^( 1 + ?jh) (i + eji)
• in 2
1 +
+ ?}i ejk eji Bjk + e/j
= in i+ 2®;
Zjk Eji
in 2 Vp(l\ *)P(/io«2®y
I i
8 jk ~T 8 ji
?jk Sji
2 . 2
8/A -j- 8Jj
(3)
(4)
(5)
628
При переходе от (3) к (4) было использовано (2) для того, чтобы убедиться, что
2 шjBjk = 0. Подставляя выражение (5) в (1) и производя соответствующие пре-/
образования, получаем
RIhn Eex(R, Q ) = - 2 Х [(2 <2 (*) е^)2 - 2 <2 (А)
(6)
I к J
Сравнивая это с (5.6.48) и (5.6.49), будем иметь
lim Eg* (#, Q) = ?'0(l, Q) с точностью до члена второго порядка по е(7)
Так как Еех (R, Q) уменьшается при увеличении R быстрее, чем Ет (R, Q), то из этого следует, что Еех (R, Q) = Ет (R, Q) при R < Rcr, по крайней мере, с той же точностью, что и приближение, сделанное в (7).
1
м
5.32. Поскольку Pe(N, М) является минимумом
М
Ре, тп по всем ко-
= 1
1
М
дам с длиной блока N и с М кодовыми словами и так как для каждого такого м
2 Р'е.т, ТО получим
П— 1
Ртах (N, М) > Ре (N, М).
Теперь при заданном М рассмотрим код с 2М кодовыми словами и длиной блока N и вероятностью ошибки Ре (N, 2М). Устраним М кодовых слов, для которых Ре, т является наибольшей. Заметим, что невозможно, чтобы Ре,т была больше, чем 2Ре (N, 2М) для каждого из этих устраненных слов. Поэтому для каждого из оставшихся слов при первоначально заданных областях декодирования имеем Ре т < 2Ре (N, 2М). Отсюда следует, что Pmax{N, Л4) <
< 2Ре (N, 2/И).
5.33. Декодер отображает выходные последовательности в сообщения и У ^ Ут тогда и только тогда, когда у отображается в сообщение т. Поэтому области декодирования Ylt ..., Ум являются непересекающимися. Далее заметим, что для данного сообщения m и принятой последовательности у каждый символ переданного кодового слова однозначно определяется по m и предыдущим принятым символам. Следовательно, т и у однозначно задают кодовое слово Хт (у)- Это значит, что при заданном т только шумовая последовательность У © хт (у) может привести к тому, чтобы было принято у и, таким образом, различные у ? Ут соответствуют различным шумовым последовательностям. Пусть теперь Мп,т будет числом шумовых последовательностей с л единицами, которые правильно декодируются в случае, когда на кодер поступает сообщение т. Так как Ут являются непересекающимися и каждое у ? Ут соответствует различным шумовым последовательностям, то ограничения (5.8.15) и (5.8.16) для Ап<т выполняются. Граница сферической упаковки при наличии обратной связи совпадает с этой границей без обратной связи, которая представлена (5.8.19).