Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
списком | т, хт, у] <
2 Qn (х)
р,у (У I х)5 Ру (У I хт)5
PoL
/М—1\Ро
Положив p = p0L, s=l/(l+p), и используя неравенство у ^ J — 1) ,
<(М— 1)р2 [2 QnWPn^ I x)1/(1+p)j1 + p так же, как это
было сделано в теореме 5.6.1. Заметим, однако, что это справедливо для всех р из интервала 0 < р < L, так как р = р0L. В ДКБП это сводится к
получим PLe>m>
L,e,m
<ехр[—W {max [—pR+E0(p, Q)]}]
о sTp<L
точно так же, как это было сделано в теореме 5.6.2.
5.21. (а) Для случая I весь канал экивалентен ДСтК с вероятностью стирания ег = 2в •— е2. Показатель экспоненты случайного кодирования был найден в задаче 5.10. Для случая II имеем
Er(R)
где ЕТ (R) является показателем экспоненты случайного кодирования для ДСтК с вероятностью стирания е. Заметим, что пропускная способность больше для случая II, и поэтому он предпочтительнее при больших скоростях. В пределе при нулевой скорости с помощью небольших вычислений можно найти, что случай I предпочтительнее при малых е, а случай II при больших г.
(б) В случае III символ стирается с вероятностью ег = 2е — в2. Выражая скорость в натуральных единицах [в соответствии с (а)], находим вероят-
R к,
ность того, что на выходе появятся менее чем правильных символов при
621
/V-кратном использовании канала или, другими словами, вероятность более чем 8N стираний при Л'-кратном использовании канала, где
Используя задачу 5.8 (г), находим, что вероятность того, что не будут получены RN!In 2 правильных символов, равна
Это та же самая граница, как и в случае I при Rcr^R<^C и эта экспонента больше при R<Rcr.
5.22. Так же как и в доказательстве теоремы 5.6.1, при заданных т, хт, у обозначим через Ат, событие, состоящее в том, что Яд, (у [ хт-) ^Я^, (у I хт). Тогда
Положив s = 1 /(1 -(-р) (что не является наилучшим выбором при P^^PN), получим
В ДСК, полагая Я (1 | 0) = Я (0|1) = 1 — е и Я' (1|0) = Я' (0|1) =
— в, в < 1/2, получаем, что значение f будет отрицательным и, в действительности, алгоритм декодирования строится так, что всегда выбирается наиболее вероятное кодовое слово.
5.23. Эта задача довольно трудоемкая, но ее результат часто оказывается полезным. Разлагая Е0 (р, Q) в окрестности р = 0 с точностью до членов второго порядка, получаем
Яе<ехр{ЛГ [я? (6) + 6 In + (1 —6) In (I — e()]>.
В силу того, что Яд, (у | х) задает переходные вероятности в канале,
Ре,т<(М— 1)р 2 <2д,(хт)Яд,(у|хт)Ям(у 1*т) sp Г2 Qn (х)рх(У I x)s]p.
X„.y |x I
Pc,m<exp{-N[-pR+f[p, Qlt P, P')]},
/=—in: )-p/(i+p)ix
E0(P, Q) = pC+-^-?0'(Pi,Q)
при некотором рх, 0 < Pj «Sj p,
E0(p, Q)<pC—?-os,
Er(R, Q)>?„(r. Q) —РЯ>Р(С—Я)—-у a; 0<p< 1,
(Г D) 2
Er(R, Q)^—------ при (C-R)^a,
(1)
где было положено p = (C — R)/a- Теперь E0 (p, Q) можно представить в виде
?э(Р. Q)=— ln2«J+p>
/
a/ = SQ(A)P(/|A)1/(1+p).
k
(2)
622
-Е„(р. Q) =
S^ + P
(! + p) da j ' a j dp
Vn1 +P
z “/
Q(k)
где
= 2>y- [lna—A)1/(1+P)| =2 wy-(?fty-ln-
/ L * J /.* 9ft;
Q (*) P (/1 *)1/{1 +p)
aj + p
(3)
(4)
Найдем теперь — El (p, Q), используя (3),
5 Q (k) ^ 5
-?S(P, Q) = — >j — (a>j qhj) In —---------(5)
j,k °P 4kj /,* °P
d
Так как \\qftj=l при всех р, j, то можно заметить, что ^~7~Як} — ^ и ВТ0‘
к к °Р
рая из написанных выше сумм равна нулю. Используя (4) (а также (2), чтобы ввести член Е'0), будем иметь
^(«>}Як}) = ч>}Як}
In aj +
pa.
In a;
1 !+P i
1+P
2^1пР(ло,/(,+р)
\uP(j\k)l^l+p)-E^ (p, Q)
\nP(j\k)'/UA~p) —
1 + P
—EUP. Q)
= Як j
p „ Q(i) 1 Q(k)
— + Y~^qkj In ~—— ?0 (p, Q)
1+P i
Подставляя это в (5), получаем
Ео (Р> Q) —^
+ Р
Я1} 1 + Р
Q(k)
Як)
У,Як}\п
к Як} J 1+РЙ
1п
Q(k) Як} .
— [Ео (P. Q)]2-
Используя неравенство задачи 4.15 (г) для выражения в первых квад-. ратных скобках и затем преобразуя первые два выражения, будем иметь
