Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
2 Q(k)Q(i) Фд, г = 2<эа(0-к, i i 6/
В этом множестве 2 Q2 (0 достигает минимума, когда все Q (i), i f I, равны
i ei
друг другу. Поэтому минимум достигается на некотором множестве I (допустим, состоящим из L элементов) и равен ML. Очевидно, что минимум достигается на наибольшем таком множестве и
RK. oc = max —1п 2 Q(k)Q(i)4h,i= InI-Q к, i
5.26. Заметим, что Rx_х из задачи 5.25 равен In 2. Поэтому при любой R > In 2 и любом распределении, которое является произведением распределений, выражение Еех (R, Q) является конечным. Вместе с тем, если рассмотреть пары букв в канале как буквы в произведении каналов, то, используя задачи 5.11 (б) и 5.25, можно найти, что Rxх для произведения каналов равна In 5. Производя нормировку на буквы первоначального канала, отсюда получим скорость (1/2) In 5. Поэтому, используя входное распределение, при котором последовательные пары букв будут статистически зависимыми, получим, что граница (5.7.7) равна 0 при R < (1/2) In 5.
5.27. Первая часть задачи представляет собой часть теоремы 5.7.2 и она доказана в приложении 5Б; однако Ех (р, Q) равно нулю, если ^(Q; Р) равно нулю, и это непосредственно следует из определения. Имеем
} = - Inа2 Q<*)Q<0 [2 V Р(Л*)Р(Л0]1/р +
625
2 Q (A) Q (0 [S VP{i\k)PU[i)V,p In [2 1~P(i\k)P(l\i)\ k¦ /_______LJ____________________I/_______ J
ll/p
2 Q{k)(Ui) [2 tfPU\k)P(i\i)j
Up
В пределе при p -*¦ 0 достигается максимум, так как Ех (р, Q) является выпуклой В этом пределе второе из написанных выше выражений стремится к нулю, а первое выражение может быть ограничено сверху, если заметить, что
Пт [2 /Р(/|Л)Р(ЛТ)11/р(=‘ ПРИ * = *;
P-о | / J { > 0 при k ф I.
Используя эти границы, получаем
дЕх(р, Q) дЕх(р, Q)
р=о
-Ш 2 «(*)*•
k
Зр Зр
5.28. В ДСК без шума при Q = (0,1; 0,9) имеем
Рх(Р, Q)=—Р In [Q (0)2 + Q (1)2J = —р In 0,82, Ео(Р, Q)=-In[Q(0)1+p + Q(l)1 + p]-
1 Ег, (Я, а)
,13 ,2 ,32 S Я
Главное в этой задаче состоит в том, чтобы показать, что если на Q не достигается максимум Er(R, Q), то можно получить Еех (R, Q) > Er (R, Q) при дЕ0 (р, Q)
R -------------- . Это невозможно для оптимального Q, так как функция
dp p=i
надежности равна Ет (R, Q) при R > дЕ0 (р, Q)/dp|p= t.
5.29. В ДКБП с двумя входами
1 1 г_______________
ех (р, q)= — р in 2 2 о (А) «?(0 2 Vpuiqpuio
k=0 i=0 L /
1/p
= -pln |Q2(0) + Q2 (1) + 2Q(0)Q(1) ^yrp(i\^P(i\°)]UP)- 0)
Подставляя Q (1) = 1 — Q (0) и дифференцируя выражение, стоящее в фигурных скобках, по Q (0), находим стационарную точку Q (0) = V2- Вторая производная выражения в фигурных скобках равна
(2)
:{1- [2 )/>(/|1)Р(Л0)]1/Р[.
626
В соответствии с задачей 4.15 (а) выражение в квадратных скобках в (2) меньше, чем 1, если только не имеет место равенство Р (/|1) = Р (/10) при всех j. Следовательно, Q (0) = 1/2 минимизирует выражение, стоящее в фигурных скобках в (1), и поэтому максимизирует Ех (р, Q) при всех р > 0.
5.30. (а) Матрица А с элементами
яг*= р? Vp(i\k)P(i\i)j1/р
является в соответствии с гипотезой неотрицательно определенной. Это означает, что для любого вектора х = {х0....... хк—0
2 xk xt ацг > 0. (1)
к, i
Нужно показать, что 2 Q (Щ Q (0 aik является выпуклой функцией век-k, i
тора вероятностей Q. Из задачи 4.11 следует, что для этого достаточно показать, что для любых векторов вероятностей Q и q
2 [XQ(A)+(l-b)?(A)] [XQ (i) + (l-Я,) ?(0] aih (2)
k, i
является выпуклой функцией X. Вторая производная от (2) по % равна
2 2 [Q{k)-q(k)][Q{i)-q(i)]aik. k, i
Из (1) следует, что это выражение неотрицательно, так что 20 {Щ Q (0 aik
k, i
является выпуклой функцией.
(б) Поскольку А является симметричной К X К матрицей, то она имеет К ортогональных собственных векторов, допустим 0), — 1)).
1 < т < К, с собственными значениями %т, 1 < т < К\
К— 1
2 aik^m (к)— ’кт^тп (0> 1 ^ ^
k =0 К— 1
2 lm(k) tm-(k) = 0-, тфт'.
k= о
Рассмотрим теперь KN X К^-матрицу В со строкой х и столбцом х' для каж-дой .входной последовательности и