Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
где последнее выражение в фигурных скобках в (5.9.13) было ограничено сверху максимальным значением этого выражения по sn. Используя, наконец, неравенство Минковского (см. задачу 4.15 (з)) при изменении порядка суммирования по sn и х1; будем иметь
ехр [—NFn (р)] <
< 2 (2Qn(хО[2рп(yi> sJXl, s5)]«/o+p)i>+px
У1 I х, L sn J j
X exp [ — IFг (p)] < exp [—nFn (p) — lFl (p)], (5.9.15)
где было проведено суммирование по sn и затем найден максимум по начальному состоянию Sq. Преобразуя (5.9.15), получаем (5.9.9), что завершает доказательство. |
194
Лемма 5.9.2. Пусть Рос (р) sup PN (р). Тогда
N
lim Fn (р) = Fcc (р). (5.9.16)
N-*00
При 0 ^ р ^ 1 сходимость является равномерной по р и Fx (р) равномерно непрерывна.
Доказательство. Применяя теорему 5.6.3 с использованием Qn (х) вместо Q (k) и PN (у) | х, So) вместо Р (/1 k), будем иметь
О <; ^LEa (f' 1°1 <g .J (Q.v; pw). (5.9.17)
dp
При входном алфавите с К буквами имеются KN последовательностей на входе длины /V и поэтому (5.9.17) может быть далее оценена следующим образом:
0< —) fiC log К. (5.9.18)
dp
Отсюда и из (5.9.7) при любых 0 ^ рх р2 ^ 1 выводим
_-(р2-?1ЛпА < Fn (p2)-Fn (Pl) < (Pa-Pl) log к. (5.9.19)
N
Из этого, в частности, следует, что при любом р, 0 р 1 функция Fn (р) ограничена выражением, не зависящим от N. Таким образом, сочетая лемму 5.9.1 и лемму 2 приложения 4 А, получаем (5.9.16). Равномерная сходимость и равномерная непрерывность вытекают из того, что, как показывает (5.9.19), наклон FN (р) является ограниченным при всех N. ]
Теорема 5.9.2. Пусть задан произвольный канал с конечным числом состояний и пусть
Er(R) = max[Fao(p) — pR]. (5.9.20)
0<р<1
Тогда при любом е > 0 существует N (е), такое, что для всех N ^
> N (г) и любых R ^ 0 существует (N, R)-код, такой, что для всех
т, 1 ^ т ^ М =[”" е^я-], и всех начальных состояниях
Pe,n(s0)^exp{-N[Er(R)-e}}. (5.9.21)
Более того, при 0 ^ R < С функция ЕГ (R) является строго положительной строго убывающей с ростом R и выпуклой
Обсуждение. Эта теорема устанавливает экспоненциальную границу для вероятности ошибки при всех R < С, где С определяется согласно (4.6.3) и (4.6.4). Кажется правдоподобным, что ЕТ (R) является надежностью канала при R, близких к С, но доказательство этого существует только в частных случаях. Эта теорема в какой-то степени 7* 195
является более слабой, чем соответствующая теорема для дискретного канала без памяти, так как (5.9.21) выполняется лишь при N %- N (е) и мало известно о зависимости N (е) от канала. Наконец, мало известно о том, как найти Fте (р) [и, следовательно, Ет (#)], кроме некоторых частных случаев, наиболее важные из которых будут рассмотрены ниже. Однако функция Fx (р) всегда может быть оценена снизу следующим образом:
Faо (р) > + minЕо.к (р, Qn, «о) (5.9.22)
A So
при любых N И Q;v.
Доказательство. При любых N и R неравенство (5.9.6) можно переписать в виде
рв1 т (So) < ехр {- Г-рД + Fn (Р)-1—]) • (5.9.23)
Лемма 5.9.2 утверждает, что при любом е >¦ О можно выбрать N (е) так, чтобы при N ^ N (г)
Fx(p)~FN(p) + ^~^e, 0<р<1. (5.9.24)
Подставляя (5.9.24) в (5.9.23), получаем
Ре, m(s0)<exP{-N [ — pi? + foc(p) — е]}, 0<р<1. (5.9.25)
При р, на котором достигается максимум —рR + Fx (р), граница (5.9.25) сводится к (5.9.21). Предположим теперь, что R < С и покажем, что ЕТ (R) > 0. Положим б равным С — R. Согласно теореме
4.6.1, N можно выбрать достаточно большим, так, чтобы
?> + 1bA<cn—~ . (5.9.26)
N — 2
Пусть Qjv при таком N будет распределением на входе, на котором достигается CN. Тогда согласно теореме 5.6.3 имеем
Я?о.*(Р. so)
при всех s0. (5.9.27)
р = 0 ~
Так как dE0i N (р, QN, s0)/dp является непрерывной функцией р, то при любом s0 существует интервал значений р > 0, такой, что
Eo,n(p, Qn, s0)-p(tf + -^j>0. (5.9.28)
В силу того, что имеется конечное число начальных состояний s0,
можно выбрать р* > 0 достаточно малым, чтобы
Eq,n(p*, Qn, s0) р* ( # + >° ПРИ всех V (5.9.29)
196
Но, так как
foo(p*)>/w)>fo,Hp*. q,v, so)-jq^.
