Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
k
Пусть Qn (х) — распределение вероятностей на последовательностях N входов канала, задаваемое соотношением
Qn (х) = ц-1 ср (х) П Q (хп), (7.3.13)
п = 1
где
( 1 для 6<2/(*пХ##.
ф = (х)Н „
\ 0 в остальных случаях;
И- = 2ф(х) П Q(xn)
Х П— 1
и б — произвольное положительное число, определенное ниже.
*> Утверждение теоремы 4.4.2 относится к каналам с дискретным выходом, однако легко видеть, что доказательство также применимо к случаю произвольного выхода.
(7.3.14)
(7.3.15)
344
Можно заметить, что QN (х) является условной вероятностью последовательности х при условии N&—б < 2/ (хп) ^ NS, если буквы слова х выбраны независимо с вероятностями Q (к). Величина [г — это вероятность того, что при таком независимом выборе последовательностей удовлетворяется условие NS — б <2/ (хп) ^ N&.
Рассмотрим ансамбль кодов с М кодовыми словами блоковой длины N, в котором кодовые слова выбраны независимо с вероятностями Qn (х). Из теоремы 5.6.1 следует, что для каждого сообщения,
1 ^ т М, вероятность ошибки, усредненная по ансамблю кодов, ограничена сверху при всех р, 0 ^ р ^ 1, выражением
Pe,m<(^-i)p2f2Q^(x)Pw(y|x)>/('+p)]‘+p. (7.3.16)
у L х
Неравенство (7.3.16) не очень удобно по форме, так как при больших N трудно иметь дело с входящими в него суммами. Если оценить сверху Qn (х) и упростить получившееся выражение, то можно получить более удобный результат. Для любого г^О можно построить верхнюю границу для ср (х) [см. (7.3.14)]:
ср (х) < ехр {г [2 / (xn) — N% + б]}. (7.3.17)
Неравенство (7.3.17), очевидно, справедливо, когда ср (х) = 0. Когда ср (х) = 1, выражение, стоящее в скобках в (7.3.17), неотрицательно и правая часть (7.3.17) больше или равна 1. Сочетая (7.3.13) и (7.3.17), имеем для любого г ^ 0
N
Qn (х)< ц-1 егб П Q(xn)erV(xn)-%]' (7.3.18)
п = 1
Мажорируя Qn (х) в (7.3.16) выражением (7.3.18) и повторяя выкладки, проведенные при переходе от (5.6.11) к (5.6.13), получаем
^,m<[-^-]1 + Pexp{-^[?o(P, Q,r)-pR]}, (7.3.19)
*o(p, Q- /-)=-in2(2Q(^er[M")-g]P(/[^)]/(1 + p))1 + P, (7.3.20)
где М и R связаны равенством М = [ eNR~1i. Используя соображения следствия 2 теоремы 5.6.2, можно заметить, что существует также код, для которого при любом т, 1^ т s::C М, и любом р, 0 ^ р^ 1,
2е'
ехр { — Л?[?0(Р, Q, г) — р#]}. (7.3.21)
Г J
Приведенная выше граница записана с помощью некоторых произвольных параметров, а именно O^p^l, r^O, Q и 6^0. Прежде чем попытаться оптимизировать выражение по этим параметрам, полезно исследовать поведение границы при г = 0 и сколь угодно большом б. В этом случае (7.3.19) упрощается следующим образом:
Pe,m<(y)1 + Pexp{-yV[?0(p, Q)-pR]}, (7.3.22)
345
где Ео (р, Q) — pR — показатель экспоненты, знакомый по теореме 5.6.2, за исключением множителя (1/[х)>+р; (7.3.22) эквивалентно теореме 5.6.2.
Так как теперь ц, — вероятность того, что при независимом выборе букв с распределением Q (k) последовательность х удовлетворяет неравенству
i/(*„)< л^,
п = 1
то из центральной предельной теоремы следует, что \i стремится
к V2 при возрастании N, если 23 Q (k)f(k) = <§, и \i стремится к 1, если
k
23 Q (k) }(k) < S. Таким образом, множитель (1/[х)1+р не отражается k
на экспоненциальной зависимости границы от N.
Пропускная способность этого канала в натах задается как частный случай формулы (7.3.1):
С = шах 22 Q (k)Р (/1 k) In , (7.3.23)
i
где максимум берется по всем заданиям вероятностей Q (k), удовлетворяющих (7.3.12). Используя рассуждения теоремы 5.6.4, можно показать, что для Q, максимизирующем (7.3.23) при условии (7.3.12), выражение
шах Е0(р, Q) — pR 0<р< 1
положительно при R < С. В итоге получаем,' что при г = 0 и сколь угодно большом 6 и при подходящим образом выбранных р и Q вероятность Ре>т, как следует из (7.3.21), экспоненциально убывает с N для любого R < С.
Как побочный результат приведенного выше рассмотрения находим, что если максимум Е0(р, Q) по всем векторам вероятностей Q достигается на векторе Q, который удовлетворяет ограничению 2Q(k) f (k) $, то для канала с ограничением можно достигнуть того
же показателя экспоненты, что и для канала без ограничения.
Обратимся теперь к более интересной ситуации, в которой при заданном р, максимум Е0 (р, Q) достигается на Q, не удовлетворяющем ограничению. В этом случае оказывается, что максимум Е0 (р, Q, г) при заданных ограничениях достигается на Q, удовлетворяющем (k) Q (?) = $> и на г >0. Наглядно причину этого можно пояснить следующим образом. Предположим, что используется ансамбль кодов, в котором все буквы кодовых слов выбираются независимо и так, что
