Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
5.15. В предыдущей задаче было отмечено, что вероятность того, что не произошло правильное декодирование (т. е. что была либо ошибка, либо стирание) ограничена сверху неравенством Ре < Ру + Р2; если положить Т = R, то Ре < 2 ехр(—Na), где
j-stf-ln [2 Q (*) <в (Л8 Р (Л А)1-*]} • (1)
Заметим, что так как а > 0 при R < С, то это дает очень простое доказательство теоремы кодирования (хотя с ненаилучшей экспонентой ошибки).
(а) Заменить s на р/(1 + р) и показать, что в двоичном симметричном канале (1) сводится к
1
a = max—— [E0(p) — pR].
Р>о 1 + р
Сравнить а с Er (R) графическим методом подобно тому, как это было сделано на рис. 5.6.3.
543
а = шах
0<s<l
(б) Используя неравенство Гёльдера [см. задачу 4.15. (б)], для суммы no j в (1), показать, что в общем ДКБП
1Е0 (Р) — РЯ]-
а > max —— р>о 1 + Р
(в) Положив s = р в (1) и использовав неравенство Гёльдера для
2<2(/г)Я(Л й)1/(1 + р)> к
показать, что а < Ет (R).
5.16. Совместная теорема кодирования для источника и канала.
(а) Пусть Ядг(у|х) будут переходными вероятностями для последовательностей длины N в дискретном канале; рассмотрим ансамбль кодов, в котором М кодовых слов выбраны независимо, каждое с распределением вероятностей QN(\). Пусть сообщения кодируются в эти кодовые слова и имеют распределение вероятностей qm, 1 < т < М; рассмотрим декодер по максимуму апостериорной вероятности, который при заданном у выбирает т, для которого 9тРдг(у|хт) максимально. Пусть
Ре — Qm Ре, i
будет средней по этому ансамблю сообщений и кодов вероятностью ошибки. Видоизменяя доказательство теоремы 5. 6. 1, там где это необходимо, показать, что
м
т = L
j /(1+р)
tn
1+р
2 2 ^.v (х) Pn (у | х)1 /(1+р)
У
1 + р
(1)
(б) Пусть канал является каналом без памяти с переходными вероятностями P(j\k), пусть буквы кодовых слов выбраны независимо с распределением вероятностей Q(k) и пусть сообщениями являются последовательности длины L дискретного источника без памяти U с распределением вероятности я(г), 0 < г < А — 1. Показать, что (1) равносильно неравенству
Ре <¦ ехр {— NE0(p, Q) + L^(p)} ?S(P) = (1+P) In
(2)
я(01/(1 + р)
г = 0
(в) Показать, что Es(0) = 0,
3?s(p)
= H(U) в натуральных едини-
dp |р=о
цах и что ?'s(p) — строго возрастающая функция р (если я(<) < 1 для всех г).
(г) Пусть К = L/N и пусть N оо при фиксированном К. Показать, что Ре -у 0, если KH(U) < С при соответствующем выборе Q(k).
(д) Показать, что граница (2) равносильна (5.6.13) в случае, когда я(г) = = 1/Л при 0 < г < А — 1, и равносильна положительной части утверждения теоремы кодирования для источника 3.1.1 (за исключением экспоненциальной сходимости здесь) в случае, когда канал является каналом без шума. Указанные выше результаты были получены автором и впервые использованы в 1964 г.
5.17. Рассмотрим сумму каналов (как в задаче 4.18), соответствующую множеству из п ДКБП. Пусть Е0 *(р) = шах Е0 г-(р, Q) для г'-ro канала из множест-
Q
ва ДКБП и пусть ?“0(Р) = ma* ?o(P> Q) Для суммы каналов. Пусть q; — вероят-
Q
ность использования г'-го канала, так что на этом распределении вероятности 544
достигается максимум ^(Р)" и пусть Qi(k) является вероятностью использования входа к в i-м каиал# при условии, что используется /-й каиал. Показать, что
ехр
Е0(Р)
ЯГ-
П
2 ехР г=1
Е0. i (р)
]
Применить ваш результат для нахождения Е0(р) канала, изображенного на рисунке.
г ¦
5.18. Следующее доказательство теоремы кодирования не позволяет получить точную границу вероятности ошибки, найденной в § 5.6, но выявляет с большей ясностью значение пропускной способности канала. Пусть P(j\k) обозначают переходные вероятности в ДКБП, пусть Q(k) — распределение на входе, на котором достигается пропускная способность, и пусть
