Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Наконец, рассмотрим случай Гг < Т. Тогда при первой проверке и; применяется правило 3, совершается движение вбок или назад и и; перепроверяется лишь после следующей Р-проверки иг-i, на этот раз при окончательном пороге Т—Д. При каждой из последовательных проверок щ первоначальный порог понижается на Д до тех пор, пока порог не станет меньше или равен Гг; совершаемая в этот момент проверка — это F-проверка и для иг выполняется (6А.6). Как и ранее, окончательные пороги при последовательных проверках иг уменьшаются по сравнению с предыдущим значением на величину Д.
Доказательство теоремы 6.9.1 (пункт в). Пусть в узле иг производится f-проверка с окончательным порогом Т\. Мы хотим показать, что прежде чем иг можно будет проверить вновь, каждый из потомков иг, для которого путь из иг лежит выше Тдолжен будет пройти Р-проверку с окончательным порогом Тг, В процессе доказательства пункта (б) для каждого из непосредственных потомков иг, например для иг+ь было показано, что если путь из и; лежит выше Тг (т. е. если Гг+Х > Тг), то прежде чем произвести первую перепроверку узла и;, будет произведена F-проверка узла иг+i с окончательным порогом Т. Теорема доказывается индукцией по длине пути потомков узла и;, т. е. если потомок ui+j, находящийся на глубине / от узла иг, проходит F-проверку с окончательным порогом Тг, то каждый из непосредственных потомков узла и;+у, для которого Гг+7-+! > Тг, проходит F-проверку с окончательным порогом Тг, прежде чем щ+j и, следовательно, иг пройдет перепроверку. Из (6.9.3) следует, что этот порог не может быть сделан ниже Тг до тех пор, пока иг не будет перепроверен. Это завершает доказательство. |
ПРИЛОЖЕНИЕ 6Б
В этом приложении находится верхняя граница Рг[Гт(0 > Гтг-П где а —• произвольная постоянная. Случайная переменная Гтгл равна
где Г0, Г j, Г2, ... — цены узлов правильного пути в дереве принятых цеп. значениях переданной и принятой по каналу последовательности Г0 = О п > О
+ а],
infrn,
л>0 В обо-и при
i= 1
Yi =
ln
p (Ha) 1 *ia))
CO ((/<•“>)
(6Б.1)
(6Б.2)
327
В ансамбле кодов величины хявляются независимыми выборками букв входного алфавита с вероятностями Q(k). Величины у^ через переходные вероятности канала P(j\k) статистически связаны с х^\ легко видеть, что у; в (6Б.2) — статистически независимые случайные величины. Значение случайной величины Тт(1) является ценой некоторого данного узла на глубине I в дереве принятых цен, определяемой с помощью равенства
I
Гт0)= 3 Г/, (6Б.З)
i = i
где
1
In
p{y\a)Wa))
СО (у\а))
(6Б.4)
а х = х [ '.....х у', х 2 > • •• — кодовая последовательность, соответствую-
щая узлу т(1). По предположению путь т(1) соответствует последовательности источника, отличающейся от переданной последовательности в первом подблоке. В ансамбле кодов величины х'^ статистически независимы от величин из (6Б.2), а также статистически независимы друг от друга. Поэтому из (6Б.4) — также статистически независимые случайные величины. Следует заме-
тить, что так как ук^ из (6Б.4) — те же самые, что у^п} из (6Б.2), то "у; и yi, вообще говоря, не являются статистически независимыми случайными величинами (см. задачу 6.43).
Положим при п > I
и при п = I положим Гп Пусть
Гп, I— 2
i = l+ 1
I = 0. Отсюда получим Г„ = Г; + Гп, i при п > I.
min Г„, i = inf Гп, ь
п > I
Событие, состоящее в том, что Тт(1) > rmjn-fa, является объединением двух событий, первое из которых состоит в том, что при 0 < п < I — 1 выполняется Гш (I) > Гц -f а, а второе—в том, что Гт (!) > Г; +minrni ; +а. Следовательно,
Рг [Гт (I) > Tmin -fa]
+ Рг [Гт (О > Г/ -f min Г„,г + а].
I- 1
У Рг[Гт(0 > Гп + а] +
п = 0
(6Б.5)
Теперь найдем границу сверху для каждого из слагаемых суммы в правой части (6Б.5), применяя границу Чернова к Тт(1) иГ„в (6Б.1) и (6Б.З):
Рг [Гт (I) > Г„ + a] < ехр s
(6Б.6)
при всех s > 0. Используя статистическую независимость пар у^ и для различных значений i, это неравенство можно переписать в виде
п ________________ I
Рг [Гт (О > Г„ -fa] < e~s0: П ехр [s (-у^ —-yj)] Г1 exp(S7('). (6Б.7)
i=i
[ —п+ 1
328
Удобно выбрать s = 1/2; используя (6Б.2) и (6Б.4), получаем
ехр [1/2 (Vi'-Vi)] = И П Q (*ja)) Р (У\а) | *<-а)) Q (*;<“>) х
а— 1
X
' р (у f | *:<a)) • % - р (</(“> | *<“>) -
со (у\а)) _ [ со(^)) I
(6Б.8)
где суммирование производится по всем возможным значениям л:^, л' ^, у^ ¦ Произведя суммирование отдельно для каждого а, 1 < а < v [как в (5.5.7) — (5.5.10)], получим
