Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
6.42. (а) Предположим, что и и и' — информационные последовательности, впервые отличающиеся в (п + 1)-м подблоке, и пусть s и s' — соответствующие им выходные последовательности двоичного сверточного кодера. Пусть s" = = s ф s'. Рассуждая так же, как и при доказательстве леммы 6.9.1, находим, что S; где i изменяется от п + 1 до п + L, а / независимо изменяется от 1 до V, представляют собой множество vL независимых одинаково распределенных двоичных случайных величин. Так же как и в § 6.9, показывается, что после сложения последовательностей s и s' со случайной последовательностью v отрезки получившихся последовательностей х и х' от (п + 1))-го до (п + L)-го подблока статистически независимы и состоят из статистически независимых символов. Если передается х и цена, принятая для первых п + / подблоков х, равна Гп+г, а цена, принятая для первых п + I подблоков х', равна то из сказанного выше
следует, что Гп+г — Гл. и Гл-}-; — Гп при I < .L имеют те же статистические свойства, что и Г; и Г/ в лемме 6.9.3. Из леммы 6.9.3 также следует, что Гm!-n <
< min Гi и потому соотношение (6.9.16) по-прежнему остается справедливым
1 < I < L
при замене Гт;п на min Г;. Поэтому в рассмотренном здесь случае 1KKL
Рг j Гп + l —Гп > min Гп + [, — Гп + ((— 2) Д| <
(I +1) ехр
(/—2) Д
-vl
Е0 (1, Q)+5
656
Из этого результата аналогично тому, как это сделано в основном тексте, получаем (6.9.23). Единственное отличие состоит в том, что в (6.9.13) суммирование проводится только от / ¦= 0 до I = L.
(б) Ошибка может произойти лишь в том случае, если существует некоторый неправильный путь на глубине л + L, ответвляющийся от правильного пути в л-м узле, цена которого превышает min Гп-)-г — Д. Вероятность того, что ка-
кой-либо отдельный путь удовлетворяет этому условию, определяется формулой 1) при / = L и i = 1. Так как число таких путей меньше e^v, то
Ре < (L + 1) ехр
—vL
6.43. (а)
V
а — 1
In
Р(у\а
?о(1, Q) + в
-R
и>
Мв))
1
Z.Q(k)P(y^\k) = -гг (где К, — к Л
В силу симмметрии заданных условий (о(у^) =
объем алфавита) независимо от символа у^К Аналогично, так как х' статистически не зависит от х и у и так как каждый из символов х^ принимает любое из К значений входного алфавита независимо от других символов и с равными вероятностями и, следовательно, независимо от х и у, то каждая величина Р(У\а> I принимает значения Р(у^ \ k) независимо и с вероятностями
1IK при О < к < К — 1. Поэтому последовательность {yi} статистически не зависит от х и у и, следовательно, не зависит от последовательности {yt}. Заметим, что рассмотренный случай представляет собой один из примеров особой ситуации, когда случайные величины х^а\ у^ и Р(у^ I х^) будут попарно статистически независимыми, но не будут статистически независимыми.
(б) Используя эту независимость, имеем
Рг 1г; > Гтг„ + (I -2) Д] = S Рг [Г! - (i -2) Д = «]Рг1Гтгп < и].
0)
Как и при переходе от (6Б.14) к (6Б.15), получим
Рг [Гпип. < г^] < е“/2.
(2)
Подставляя (2) в (1) и используя те же рассуждения, что и при переходе от (6Б.17) к (6Б.22), получаем
Рг [Гг > Г min + (i—2) Д1 < ехр
(i—2) Д v/
[?<>(I, Q) + SU.
(в) Границы для Wn и Ре> „ можно найти аналогично тому, как это сделано в (6. 9.17) — (6.9.23) и (6.9.38) — (6.9.45). Единственное отличие состоит в том, что в (6.9.17) опускается множитель (I + 1). а в (6.9.38) — множитель (С + + L — b + 1). В результате получим следующие неравенства:
1 —ехр {—v [?0 (1. Q)—/?]}’
_vtf + A/2
<
I-exp[-v(?0(l.Q)-^)]}2
ехр {— vLE0(l, Q)}.
657
6.44. Используя те же рассуждения, что й при рассмотрении (6.9.13) и 6.9.14), имеем
Г0(«) <2 2 2 Рг1Гт <'>>« + (*~2) Д].
; = о т (I) i = 1 Из границы Чернова (5.4.15) следует
Рг [Гт (/) > u + (t—2) Д] < е—*[«+(' —2) Д1 [g (s)]'v; s>0 любое,
sin ^Ш-sB
(1)
(2)
g(s)=mQ(k)P(j\k)Q(k')exp k i k'
1 \ 1 — s D
[(1—е^ + е^е
<*>(/)
где в — вероятность ошибки в ДСК- Полагая s— 1/(1 + р) или р = (1 —s)/s, приводим это соотношение к виду
g
1
= ехр
1
[Ео(9)+В]
(3)
1+ Р) I 1+Р
Подставляя (2) и (3) в (1), вспоминая, что сумма по т(1) содержит не более ev/R слагаемых и используя различные значения р = р^ при различных /, получаем
оо оо I 1 1
2 % ехр vlR-——[u + (i-2)A^Blv + E0(p)lv]}.