Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Рг
ошибка при декодировании списком
т, хп
<
М—1 \Ро
PN (у Iх)
РN (У 1 хп»)
s’! ^-Ро
(б) Оценить сверху
положить р
Ер0
и показать, что при 0 < р < L справедливо неравенство
Л ,<(Л*-1)Р2(2 Qn (*)Pn( У Iх)
vl/l+p\l+p
г
(в) Показать, что для ДКБП последнее неравенство принимает вид:
-ptf+?0(p, Q)]j
Pi р ехР Г —N I max [ -’ L lo<PSi
Изобразите графически выражение, стоящее в фигурных скобках, как функцию R при заданном L и проведите сравнение с Er(R, Q).
5.21. Рассмотрим следующие возможности для передачи данных из точки А в точку С (см. рисунок, изображенный ниже).
1-е
f-f
I. В точке В каждый выход первого канала непосредственно соединяется с соответствующим входом второго канала и данные передаются с использованием блокового кода длины N со скоростью R.
II. Блоковый код длины N/2 со скоростью R используется в первом канале, и данные декодируются в точке В и вновь кодируются блоковым кодом длины N12 со скоростью R для передачи по второму каналу с использованием только двух внешних входов.
III. Двоичные символы источника непосредственно передаются из Л в С при соответствующем соединении входов и выходов в точке В. С помощью бесшумного обратного канала передача организуется так, что символы источника повторяются вновь всегда тогда, когда принимается средний выход в точке С.
18*
547
(а) Найти показатели экспонент случайного кодирования при передачах
I и II и сравнить эти методы передачи на основе найденных экспонент.
(б) Применить границу Чернова для оценки сверху вероятности того, что меньше чем RN символов источника будут переданы за N использований канала при передаче III, и сравнить с двумя первыми методами передачи.
5.22. Дискретный канал без памяти имеет переходные вероятности P(j | k). К сожалению, декодер для канала является декодером максимального правдоподобия, построенным при ошибочном представлении, что переходные вероятности равны P'(j\k). Т. е. сообщение т декодируется, если Pw(y|xm) > Pn(y|xm) для всех т’ > т, где
Найти верхнюю границу для средней вероятности ошибочного декодирования в ансамбле кодов, в котором буквы кодовых слов выбраны независимо с распределением вероятности Q(k). Ваша граница должна иметь вид
Найти пример переходных вероятностей Р и Р', для которых / является неположительной, и объяснить, почему это не удивительно. См. Стиглитц (1966).
5.23. В заданном ДКБП с переходными вероятностями P(j\k) разложить Я0(Р> Q) ПРИ Q, на котором достигается пропускная способность, в степенной ряд для того, чтобы показать, что
при С — R < а, где а является верхней границей для—?о(р, Q) при 0 < р < 1. Показать, что
где J — объем выходного алфавита.
5.24. Рассмотрим ДКБП, в котором пропускная способность с нулевой ошибкой равна нулю (т. е. Rx определенная равенством (5.7.16), равна нулю). Показать что
PN (У I хт) = ПР' (уп I хп).
П
Ре < ехр { — N [ — рЯ + / (р, Q, Р, Р')]} при 0 « р « 1.
(I)
—?о(р, Q
/ *
Q(k)
(П)
P(i\ ?)1/(1+р)
где
/
Взяв производную в (II), показать, что
На основе этого показать, что
Указание: покажите сначала, что lim Eex(R, Q) = lim ?x(p, Q). Далее
R-+ 0 р-УОО
используйте либо правило Лопиталя, либо разложите Ех(р, Q) в ряд по степеням 1/р.
5.25. Показать, что Rx х [см. (5.7.16)] задается равенством Rx = = In L, где L — объем наибольшего множества I целых чисел, такого, что для всех i ? I, k (J I, i ф k имеем q^, * = 0 [см. (5.7.15)]. (Другими словами, I является наибольшим множеством входов, таким, что никакой выход не может быть достигнут из более чем одного входа этого множества; при использовании только этого множества входов каждая выходная буква однозначно определяет вход).
Указание: предположите, что cp0, i = 1 и покажите, что
2 <?№<?(<)<Pft,i = [Q(0)+Q(i)]3 + k, i
К-1 К-1 К—1
+ 2 2 Q (О [Q(0)Фо. ; + Q(l)<Pi,;]+ 2 2 Q(*)Q(0Фл. i-
1 — 2 k = 2 г = 2
Показать, что при любых заданных значениях Q(2).......Q(K — 1) это выражение
достигает минимума по Q(0) и Q(l) либо при Q(0)=0, либо при Q(l) = 0. Используйте это для того, чтобы показать, что
2 Q (*) Q (0 Фа. ;
k, i
достигает минимума при Q(k), неравных нулю только на некотором множестве /, для которого фk,i = 0 ПРИ всех k ? I, i ? I, k Ф i.
5.26. Для канала из задачи 5.11 выбрать длину блока N=2 и R = (1п5)/2. Показать, что выражение для Ре,т из (5.7.7) не достигает минимума по р и QN(x) на произведении распределений.
