Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
dN(s’0, si) =.SMswK) — <7(^К)|- (4.6.27)
SN
При N = 0 и Sot^so будем считать, что dN (so, so) равно 2.
*> Если быть точным, то эту вероятность следует обозначить:
| %1...х^5о (г | k1% ..., kN, /), что означает вероятность того, что принимает
значение i при условии, что заданы последонателыюсть х = (kx, k ) и со-
стояние s0 = /.
№
Как показывает следующая лемма, зависимость sN от s0 в смысле этой вероятностной меры не увеличивается с увеличением N.
Лемма 4.6.1. Для любых заданных входов хи х2,..., любых заданных so, s'o определенное выше расстояние dN (so, so) не увеличивается с ростом N.
Доказательство. При N ^ 1 имеем
dN(s0, So) I 9 ! so) — <7(S*K)I= (4.6.28)
N
==2
SN
2 Я I —l) (“jV—1 I So) Я (®jV— 1 I so)l
SN-1
(4.6.29)
Ограничивая сверху модуль суммы суммой модулей, получаем
(So > So) 2 2 <7 (SA’ I ^N— i) I Я (SN— 1 I So) Я (SN-l I So) I = (4.6.30)
= 2 l?(sw_i|s;)—<7(Sjv_iK)I= (4.6.31)
SN-1
= dw_i(s;, О-1 (4.6.32)
Следующая лемма дает условие, при котором dN (so, So) стремится к 0 с ростом N.
Лемма 4.6.2. Предположим, что при некотором п > 0, некотором б > 0 и каждом N ^ 0 существует некоторое sN+n, для которого
q ($ьг+п j S/s/) ^ б для всех значений sn- (4.6.33)
Тогда dN (so, so) стремится к 0 экспоненциально с ростом N и
dN(sо, sS)<2(l-6p/n)-i .
Доказательство. Имеем
^-|_n(sci> sci) “ 2 I Я (SiV-|- п I So) Я (SN + n I so) I = (4.6.34)
sN + n
= 2 12 ц (sN+n ISN) \q (sN I s')—q (sN [ sj)] [. (4.6.35)
SN + nSN
Введем обозначение:
a (sN+n) = vainq(sN+n\sN). (4.6.36)
sN
Замечая, что
2 a (sN+n) W (SNI so)—я (Sjv I so)l = 0.
SN
представим (4.6.35) в виде dN+n(s'a, s0')= 2 li^(sN+n\sN)~a(sN+n)][q(sN\s'a)--q(sN\s')]\.
SN + n SN
(4.6.37)
123
Ограничивая модуль суммы с помощью суммы модулей и заме-чая, что 9(sw+n| sN)—a(sN+n) > 0, будем иметь
djv+nK.^X 2 2[<7(sw+^lsw)—1a(sw+n)]|<7(swK) — <?(%К)|.
SN+nSN (4.6.38)
После суммирования no sn+п получаем
dN+n(s'a, <)<[]- 2 a(sw+n)lSI<7(sw|So) —9(%|sJi)| =
SW + f! SN
= [1— 2 a(s/V+r!)]dw(s;, s"0). (4.6.39)
SN + n
По предположению, a (sn+п)^ 8 по крайней мере для одного значения sw+rj и, следовательно,
dN+n(s'0, sr0)^(\—6)dN(s'0, s"). (4.6.40)
Используя последнее неравенство при N = 0, затем при N = п, затем при N = 2п и т. д. и вспоминая, что d0 (so, So) = 2, получаем
dmn(s'0,sl)^ 2(1-6)». (4.6.41)
В силу того, что dN (so, so) не увеличивается с ростом N, это доказывает лемму. |
Следующая ниже теорема дает критерий того, является ли ККЧС неразложимым или нет.
Теорема 4.6.3. Необходимым и достаточным условием того, что ККЧС будет неразложимым, является существование при некотором фиксированном п для каждого х такого состояния s„, что
q (s„ | х, s0) > 0 при всех s0 (4.6.42)
(это sn может зависеть от х). Более того, если канал является неразложимым, то указанное выше п можно всегда выбрать меньшим 2А\ где А — число состояний канала.
Доказательство. Достаточность. Если (4.6.42) справедливо для некоторого п, то, так как s0 и х = (хг, ..., хп) могут принимать только конечное число значений, существует некоторое 8>0, такое, что
<7 (sn | х, s0) > 6 (4.6.43)
при всех s0, всех х и некотором sn, зависящем от х.
Также в силу того, что вероятности в канале не зависят от времени, имеем для любых N и некоторого Sn+п, зависящего от
Xn +ь • ¦ • > Xn -f п
q{sN+n\xN+\, ...,xN+n, sN)>b при всех sN. (4.6.44)
Таким образом, условия предыдущей леммы удовлетворяются и 21<?Ых, sl)—q(sN\x, s;')|
124
стремится к нул!о экспоненциально при N-^oo, равномерно по х, so и so- Следовательно, (4.6.26) справедливо для достаточно больших N, и канал является неразложимым.
Необходимость. Выберем е< НА, где А — число состояний, вы* берем N достаточно большим, чтобы удовлетворялось (4.6.26), и для заданного s0 и х выберем sN так, чтобы q (sw|x, s0) ^ 11А. Тогда согласно (4.6.26) q (s^ I х, so) > 0 для всех s'0 и условие теоремы удовлетворяется при п, равном этому N.
