Научная литература
booksshare.net -> Добавить материал -> Физика -> Галлагер Р. -> "Теория информации и надежная связь" -> 143

Теория информации и надежная связь - Галлагер Р.

Галлагер Р. Теория информации и надежная связь — М.: Советское радио, 1974. — 738 c.
Скачать (прямая ссылка): teoriyainformacii1974.pdf
Предыдущая << 1 .. 137 138 139 140 141 142 < 143 > 144 145 146 147 148 149 .. 355 >> Следующая


J) w[m{l), i]. t=i

Поэтому общее число F-проверок в исходном узле и всех узлах, которые принадлежат неправильному поддереву, исходящему из начального узла, ограничено неравенством

2 Е»И),а (6.9.12)

/ = 0 m(l) i — I

По условию, в сумму по т (I) при I = 0 войдет только одно слагаемое, соответствующее исходному узлу. При /^1 в сумму по т (I) войдут слагаемые, соответствующие (2я—1)2Я(/_1) узлам неправильного поддерева, лежащим на глубине I. Оценим теперь сверху математи-

294
ческое ожидание величины W0. Так как математическое ожидание суммы равно сумме математических ожиданий, то

С другой стороны, согласно (6.9.11)

w[m(l), i] =Рг [Гот(о > Гт,п—2А + /А]. (6.9.14)

В силу статистической независимости передаваемой кодовой последовательности и кодовой последовательности, соответствующей m (I), задача нахождения вероятности в правой части (6.9.14) аналогична задаче нахождения вероятности ошибки при передаче двух случайно выбираемых кодовых слов. Единственное различие заключается в том, что должны рассматриваться последовательности вдоль правильного пути различной длины. Принимая во внимание эту аналогию с задачами передачи двух кодовых слов, не следует удивляться, что в ответе появляется значение функции Е0 (р, Q) при р = 1:

j — I

?„(1,0) =-In 2

/ = о

К— 1

2 Q(k)YP(j\k)

k = 0

(6.9.15)

Следующая лемма доказана в приложении 6Б.

Лемма 6.9.3. Рассмотрим ансамбль кодов, в котором кодовая последовательность, соответствующая каждой последовательности сообщения, представляет собой последовательность статистически независимых символов, принимающих значения с вероятностями Q (k). Обозначим через Гтг-П нижнюю грань цен вдоль правильного пути в дереве принятых цен и через Г/ — цену в узле и/, где и/ — последовательность сообщения из I подблоков, такая, что первые I подблоков кодовой последовательности, соответствующей и/, статистически независимы от переданной кодовой последовательности. Тогда, если смещение В удовлетворяет неравенству В^.Е0 (1, Q), то

Pr[r;>rmtn + (i-2)A]<(/+l)X

Хехр

(*—2) A r, E0(\,Q) + B

(6.9.16)

Сравнивая (6.9.13), (6.9.14) и (6.9.16), получаем

^о<2 2 2 ('-Ы)ехР 1=0 тщ < = 1

(г — 2) Д

-vl

Е0( 1, Q) + B

(6.9.17)

Из (6.9.1) видно, что 251 = evR и поэтому приведенная выше сумма по т (I) содержит менее чем evlR одинаковых членов; следовательно,

2 2 U+ 1)ехр

1 = 0 1 = 1

(г-2) д

-vl

E0(l,Q)+B

-R

J. (6.9.18)

295
Эти ряды могут быть без труда просуммированы, если использовать разложение

(6.9.19)

и его производную

(6.9.20)

Эти ряды сходятся, если

^ ^ Е0(\, Q)+ В .

(6.9.21)

при этом получим

—2

. (6.9.22)

Приведенная граница дает некоторое представление о том, какие значения должны выбираться для смещения В и порогового интервала Д. Граница убывает с возрастанием В, но справедлива лишь при В <!(1, Q). Поэтому граница имеет минимум при В = Е0 (1, Q). Аналогично, минимизируя по Д, находим, что минимум достигается при ед/2 _ 2 или Д = 2 In 2. Используя эти значения, убеждаемся, что при R <. Ео (1, Q)

Эти рассуждения оставляют некоторое сомнение в том, что минимум W0 достигается при этих значениях В и Д, поскольку они минимизируют лишь границу для №0. Для слагаемых, соответствующих малым значениям i и /, которые доминируют в сумме (6.9.13), использованная нами экспоненциальная граница является довольно грубой. Блюстейн и Жордан (1963) экспериментально показали, что, как правило, величина W0 на два порядка меньше, чем приведенная здесь граница, и что она мало зависит от смещения и от порогового интервала. Важное значение неравенства (6.9.23) состоит не в том, что оно задает явную границу, а в доказательстве того, что граница конечна при R С Е0 (1, Q).

Рассмотрим теперь произвольный узел правильного пути, например п-й узел. Заметим, что статистическое описание неправильного поддерева и правильного пути, исходящих из этого узла, совершенно аналогично статистическому описанию неправильного поддерева и правильного пути, исходящих из начального узла. Единственная разница состоит в том, что к множеству цен узлов добавлена цена Гп. Лемма применяется здесь точно так же, как и раньше, и (6.9.23) позволяет получить верхнюю границу для Wn. Поэтому (6.9.23) оценивает сверху среднее число F-проверок на декодированный подблок.

№0 <4{ —ехр [—vE0 (1, Q) + vi?]}-2.

(6.9.23)

296
Из этой границы можно также увидеть довольно ясно, почему «работает» метод последовательного декодирования. Число узлов в неправильном поддереве растет экспоненциально с. глубиной дерева, а вероятность проверки узла является экспоненциально убывающей функцией глубины дерева. До тех пор пока скорость остается меньше, чем ?0(1,Q), убывание вероятности более чем компенсирует возрастание числа узлов. Ясно, что именно древовидная структура сверточных
Предыдущая << 1 .. 137 138 139 140 141 142 < 143 > 144 145 146 147 148 149 .. 355 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed