Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Указание: внимательно рассмотрите ваше решение пункта (б) задачи 5.11.
5.27. Показать, что Ех{р, Q) является положительной при всех р > 0 и что
дЕх (р, Q)/dp < —In 2 IQ W]a* k
5.28. Вычислить и изобразить на графике ^(р, Q) и Е0(р, Q) для двоичного канала без шума при Q(0) = 0, 1 и (?(1) = 0,9. Построить графики Eex(R, Q) и Er(R, Q).
5.29. Показать, что для любых двух входов ДКБП Ех(р, Q) достигает максимума по Q на Q(0) = Q(l) = V2.
Указание: заметьте, что слагаемые в двойной сумме по k и г в определении Ех принимают только два различных значения: одно при k = г и другое при k ф С. Этот результат и результат следующей задачи были получены Джелине-ком (1968).
5.30. (а) Показать, что если матрица А с элементами
«Jft=[^/P(fl*)P(/IO],/p
является неотрицательно определенной, то
2. Q (A) Q (I) ^УР(у|А)Р(у|о]1 /р
является выпуклой w по Q.
(б) Показать, что из этого также следует, что матрица с элементами
[2 УР„(у|х)Р„(у|х') р<\
549
Имеющими индексы х, х', также неотрицательно определена, и поэтому 2 Qn (х) Qn (х') I S Vpn (у I *) PN (У I х') ]^р
X, X' L у J
является выпуклой ^ функцией qn.
Указание: покажите, что собственные значения последней матрицы являются произведениями N собственных значений первой матрицы. Покажите на основе этого, что указанная выше сумма по х и х' достигает минимума на произведении распределений.
Указание: см. пример 4 § 5.6.
5.31. Показать, что в пределе для канала с очень большим шумом
lim Еех (R, Q)
Л-о
[см. (5.7.20)] сходится к Er(R, Q). Используйте этот результат, чтобы показать, что в таком канале Eex(R, Q) стремится к Er(R, Q) при R < Rcr.
5.32. Пусть для любого заданного входа и метода декодирования Ре,т обозначает вероятность ошибки для т-го кодового слова и
Рmax = max Ре, т-
1 <т<Л1
Пусть Pmax(N, М) является минимальным значением Ртах Для заданного канала при вариации по всем кодам с длиной блока N и сМ кодовыми словами. Показать, что
Pmax(N, M)>Pe(N, М)
Ртах (N, М) < 2Ре (N, 2М),
где Pe{N, М) определена в § 5.8.
Указание: см. следствие 2 теоремы 5.6.2.
5.33. Доказать, что граница сферической упаковки для ДСК (5.8.19) остается справедливой в случае, если между приемником и передатчиком имеется обратная связь (т. е. если передатчик знает, что было получено, и каждый переданный символ является функцией как сообщения, так и предыдущих принятых символов).
Указание: пусть опять Ym будет множеством принятых последовательностей, декодированных в сообщение т\ покажите, что эти множества взаимно исключают друг друга. Пусть г(у) является последовательностью ошибок для у, т. е., если Ym и хт(у) является переданной последовательностью для сообщения т и принятой последовательностью у, то полагаем z(y) = xm(y) + у. Покажите, что если для заданного т у ? Ym и у' ? Yт пуфу', то z(y) ф z(y').
5.34. Показать, что параметр А в теореме 5.8.5 удовлетворяет неравенству:
2 (In J) (In ./ + 2/е)
Ч-
р2
4 е2
min maxP (/1 / *
Указание: заметьте, что
550
In
А < max ^ Р (/1 k) /
In
Р (i I k) Ю (/)
ц(у) V PU\k) J
+
In
Р (J I k) г и (/) J
2 P(i\k)x
1 '¦ Р (/I*) < ш (/)
р (У I k) . 1
P(i I Л) ln -
i : P (/| &) > to (/)
W (/)
ln
Для первой суммы используйте неравенство
4
[In*]2 < — х при х>1. е2
Для второй суммы используйте (5.8.60) для того, чтобы показать, что
1 C + H(Y\x=k)
In-----< ---------------- при всех k.
со O') Р (Л k)
5.35. Используйте границу Чернова вместо неравенства Чебышева в (5.8.67) для того, чтобы показать, что при фиксированной R > С имеем
Pe(N, Геад_|)> 1 —2 ехр [—Na (/?)],
где а(Р)> 0 при /?>С.
5.36. Примените центральную предельную теорему в форме Берри — Эссена (см. Феллер (1968), гл. XVI, § 5) вместо неравенства Чебышева в (5.8.67). Предположите, что канал такой, что выражение ln[P(/|ft)/<o(/)] не зависит от j при любом k. Пусть б — произвольное действительное число (положительное или отрицательное) и пусть R(8, N) = С + б/^/N. Показать, что для любого 8 > 0 существует такое N(8, е), что для всех N > N(8, е)