Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
(б) При N = 1 получаем нулевую вероятность ошибки, когда xt = О, х2 = 2. При N — 2 нулевую вероятность ошибки дают следующие пять кодовых слов:
(О, 0), (1,2), (2, 4), (3, 1), (4, 3).
5.12. Пусть Ео (р) равно значению Е0 (р, Q) для распределения Q, на
котором достигается пропускная способность. Следует рассмотреть два случая. В вырожденном случае, в котором Е'о (0) = 0, имеем Er (R, Q) х С — R.
В общем случае, когда ЕЪ (0) < 0, можно использовать два первых члена
ряда Тейлора для Е0 (р) в окрестности р = 0. Получим
г р3 „
Ео (р)=р?о (0) + — Ео (pi) при некотором pt из 0 < рх < р.
Аналогично Ео (р)—?о (0) + р?о (р2) при некотером р2, 0 < р2 < р. Параметрические уравнения для Er(R, Q) имеют вид
R=Eо (р) =С+р?о (р2),
612
Eo (pi)
— Ео (р2)
Ео (Pi)
Er(R, Q) =Ео (р) — рЕо (р) = р2 Решая (1) относительно р, получаем
Er(R, Q) — (С—R)2 „
|_2?о (р2) Ео (р2)
При R С имеем р 0 и, следовательно, Pi -> 0, р2 -*¦ 0. Получим
ET(R, Q) 1
I im-----------= —-----------.
1^с (C—RY- 2Ео (0)
Таким образом, для R, близких к С, имеем Er (R, Q) ж а (С
_ 1
2?о (0) '
(I)
R)'2, где
(2)
Для несимметричных каналов поведение Ег (R) не обязательно описывается таким же образом. Для Er (R) следовало бы заменить Ео (0) в (2) на
а2шах[?0(р, Q)]
др2
5.13. ?0(1, Q)
р = 0
-in2[Q(0) VP(j 10)н-Q (l) Урц 11)]2 =
-InStQ (0)2P(/|0)^Q(l)2P(/[l)-f2Q (0)Q(1)/P(/|0)P(/|1)1 =
1
n|Q (0)2 + Q (1)2^2Q (0) Q (1)J V~P (j \ 0) P (j \ l)j • (1)
Подставляя 1 — Q (0) вместо Q (1) в написанное выше выражение и выполняя дифференцирование по Q (0), получаем, что точка, соответствующая Q (0) = 1/2, стационарна. Беря вторую производную, находим, что Q (0) = 1/2 максимизирует (1), если 2~\/Р (/10) Р (/| 1) < 1. Однако, как показано в задаче /
4.15 (а), Я = V2, это последнее неравенство всегда справедливо.
5.14. (а) P1 = Pr [Im < TN | сообщение tn]. При условии, что задано гп, , Р (Уп I хтп, п)
величины In -------------- образуют последовательность независимых случайных
®(</п)
величин с распределением вероятностей Q (xm- п) Р (уп | хт,п). Заметим, что , Р (Уп I хтп, п)
1П ------------ принимает только конечное число значении с ненулевыми веро-
to) (Уп)
ятностямн. Следовательно, из (5.4.16) при г < 0 получаем
Pi
- гТN
12
U./
Q (k) Р (j \ к) ехр
г In
PU\k) (Л (I)
где суммирование ведется по к, j, для которых Q (к) Р (/] k) > 0. Полагая s=—г, при любом s> 0 получаем
Рх <expj-JV j-s7’-ln^SQ(ft)o)0rP(/|ft)wj}} •
Замечая, что граница, очевидно, выполняется для s = 0, получаем Р1 < е ^ля а, определенном в условии задачи.
Используя аддитивную границу, имеем
: S Рг [/„
m фгп
TN I сообщение /и].
— Na
613
При заданном сообщении т в ансамбле кодов кодовые слова х и хт, и принятая последовательность у имеют распределение вероятностей QN (хт) PN (у | хт)х xQiV (хт') ¦ Таким образом у и хт, статистически независимы и имеют распределение вероятности сОд, (у) <2д, (хт<). Отсюда и из (5.4.15) при любом г > О получаем
Полагая s=l—г и ограничивая сверху М—1 с помощью e^N, получаем, что при s < 1,
При s~ 1 этот результат является тривиально справедливым. Таким образом,
Заметим, что а = max [—sT — [г (s)] и что j,i (s) является семиин-
вариантной производящей функцией моментов взятой со знаком минус взаимной информации, поэтому \i’ (0) = —С и отсюда следует, что при любом Т < С значение —sT — (х (s) является положительным для достаточно малого s > 0. Следовательно, а > 0. Из выпуклости (s) следует также, что —sT — [г (s) достигает максимума по s при Т = —|х’ (s). При Т, стремящемся к С, максимизирующее значение s убывает к 0 и —sT — ц (s) стремится к 0.
(в) Для того чтобы произошло стирание, когда передавалось сообщение т, должно бытьлибо 1т ¦< ТМ, либо 1 m, > TN при некотором т! ф т. Таким
образом, Рг (стирание) < Рг + Р2.
Для того чтобы произошла ошибка, / , должно быть большим или равным TN в точности для одного значения т’ ф т и 1т должно быть меньше чем TN. Вероятность этого ограничена вероятностью того, что 1 т, ТЫ для одного
или большего числа т! ф т, т. е. Рг (ошибка) < Р2.
Отметим, что если декодер модифицируется так, чтобы производить стирание, когда Im < TN при всех т, и декодировать такое т, для которого 1т является наибольшим среди остальных, то можно было бы показать, что Рг (стирание) < Рг, но отличие является несущественным в том интересном случае, когда Р2 < Рг.