Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
348
N
IV
В приведенных выше выражениях р^1,г^0иб>0 — произвольны, а |л определено в (7.3.15) и оценено в (7.3.29).
Теперь можно применить эти результаты к произвольному дискретному по времени каналу без памяти с ограничением на входе f(x)^.<$. Как в § 7.2, пусть Xd — конечное множество входных букв канала аъ ..., ак с заданными вероятностями Q (аг), ..., Q (ак), удовлетворяющими ограничению XQ(ah) / (ak) ^ Й. Пусть Yp — разбиение выходного пространства на события Ви ..., Bj. Пусть Е0 (р, Xd, Yp, г) и Ех (р, Xd, Yp, г) задаются соотношениями
Е0(Р, Xd, Yp, г) =
in i / = i
i+p
2 Q(aft)er V(4)-cS]pY}x{Bjlakyio + p) k= l
Ex (p. xd, Yp> r) = — p in f 2 2 Q Ю Q (fl|) x
= i (¦= i
(7.3.34)
X er (ak)+f (Д YPy\x (Bj I ak) PY, x (B} | a,)) I/P). (7.3.35)
Определим для рассматриваемого канала показатель экспоненты случайного кодирования и показатель экспоненты для процедуры с выбрасыванием равенствами
Er(R) = sup [?0(Р, Xd, Yp, г)—pjR], (7.3.36)
?e* (#) = sup [Я* (р, Xd, Yp, г) — pR], (7.3.37)
Верхняя грань в обоих приведенных выше равенствах берется по всем конечным наборам входных букв; всем вероятностям, удовлетворяющим ограничению; всем разбиениям на выходе; всем г^О и всем р, удовлетворяющим Os^p^l для (7.3.36) и р^1 для (7.3.37).
Теорема 7.3.2. (Теорема кодирования.) Для произвольного дискретного по времени канала без памяти с ограничением на входе / (х)^& пусть Ет (R), Еех (R) и С определены в (7.3.36), (7.3.37) и (7.3.1). Пусть R^s 0 и Е С шах [Ет (R), Еех (7?)] произвольны. Тогда для всех достаточно больших N существует блоковый код длины N с М = = | o.NR j кодовыми словами хь ..., хм, каждое из которых удовлетворяет ограничению
2 / (хт, „) < NS
и для каждого из которых удовлетворяется неравенство
?е, т ехр (—NE). (7.3.38)
Кроме того, Ет (R) > 0 для всех R, 0 ^ R < С. ___________
Доказательство. Выберем Еи удовлетворяющее условию
Е <E1Cmax[Er(R), Eex(R)]. Если ET(R)^ Eex(R), выберем Xd, Yp, г^ 0 и 0<р< 1 так, что
?i<?o(P. Xd, Yp, r) — pR.
Из (7.3.21) следует, что для любого б >0 и каждого N ^=1 существует код для этих Xd, Yp с М = Г 'ew/?"""'j кодовыми словами, каждое из которых удовлетворяет ограничению и удовлетворяет неравенству
Ре, т ^ [егб/[1]‘ + рехр (— NE^)\ 1 Ог^М. (7.3.39)
Так как для достаточно больших N выражение [егб/ц]1+р возрастает как jV(1+ и так как ? то для достаточно больших N имеем
Ре, т ^ + P ехр ( — NEj) ^ ехр (— NE). (7.3.40)
Эти же рассуждения применимы и в случае, когда Еех (R) > ЕТ (R), за исключением того, что Ех должно стоять вместо Е0. Далее примем, что R < С и выберем Xd, Yp так, чтобы R < I (Xd; Yp) << С. Из соображений, следующих за (7.3.23), видно, что для г = 0
max [?0(р, Xd, Yp, г)—pR] > 0
о < р < 1
и, следовательно, Ет (R) > 0. |
Теорема 7.3.2 обладает большой общностью, однако часто ее трудно применить ввиду трудности вычисления верхних граней, введенных при определении Ет (R) и Еех (R). Для каналов, задаваемых переходной плотностью вероятности, обе величины Е0 (р, Xd, Yр, г) и Ех (р, Xd, Yp, г) не убывают при измельчении разбиения пространства Y. Этот результат доказывается точно так же, как и для каналов без ограничений на входе. Верхняя грань по Y достигается и имеет вид
Е0(р, Xd,Y,r)=---ln |Г2<2К)ег^Ы-?] х
L k
X p(y\ak)ini + p)
Ех (р, Xd, Y, г) = —pin (22<3 К) <3 (flj) х
I k i
х er lf(n*)+f у p(y\ah)p(jy\at) dyj!p}. (7.3.42)
Если верхняя грань Е0 и Ех по Хй достигается в пределе на распределениях, сходящихся к плотности вероятности q (х), то можно 350
1 + pdy, (7.3.41)
положить по определению Е0(р, X, У, г) = — In J §q(x)er V <Х)~С?1 p(y\x)4ll + p) dx ‘ + Р dy,
(7.3.43)
Ех(р, X,Y, r) = —plnj \q(x)q(x’)zf ['W + f U')-*»] x
X [JK p(y\x)p(y\x') dyy/pdxdx'. (7.3.44)
Показатели экспонент ET (R) и Eex (R) могут теперь быть найдены прямо из (7.3.43) и (7.3.44) после максимизации лишь по р и г. В этом случае можно получить в некотором смысле более точные результаты, повторяя выводы теорем 5.6.1 и 5.7.1 и используя при этом плотности вместо вероятностей и интегралы вместо сумм. Упрощая результаты, так же как при переходе от (7.3.16) к (7.3.2), находим, что существует код, для которого каждое кодовое слово удовлетворяет как ограничению, так и следующим границам вероятности ошибки:
Ре,т<[2е'в/[х]2ехр{ — N[E0(p, X, У, г) — pR]}; 0<р<1, (7.3.45) Ре,т<ехр{-ЛЧ?ж(р, X.Y, г)-рК']}; Р>1 (7.3.46)
