Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
4.4. Источник производит статистически независимые равновероятные двоичные символы со скоростью один символ в секунду. Выход источника кодируется и передается по двоичному симметричному каналу с вероятностью ошибки s, 0 < s < У2- Каждую секунду передается один символ канала. Используя обращение теоремы кодирования, найти границу сверху и снизу для <Ре>- Объяснить, почему невозможно сделать вероятность ошибки больше, чем полученная вами верхняя граница. Сравнить ваши границы с <Ре> для случая, когда кодирование и декодирование не производится.
4.5. Дискретный источник без памяти производит один символ каждую секунду и имеет энтропию 2 бита. Выход источника кодируется и передается по каналу с пропускной способностью Q бит в секунду.
(а) Предполагая, что алфавит источника имеет объем М = 4, тщательно вычертить зависимость от Ct нижней границы вероятности ошибки на символ источника, которая дана в теореме 4.3.4.
(б) Для любого заданного Ct найти канал, для которого указанная нижняя граница точно достигается без какого-либо кодирования.
(в) Предположите теперь,что объем алфавита источника неизвестен, по что Ct = 1 и <Ре> = 10_ 6. Найти нижнюю границу для М, используя теорему
4.3.4.
4.6. В этой задаче показывается, что пропускная способность дискретного канала без памяти не увеличивается при введении обратной связи от приемника к передатчику. Рассмотрите схему, изображенную ниже.
Источник I—И Кодер
X = f -2
Дискретный
• ‘ 9 У г/ _
Каждый символ на выходе канала после его получения приемником посылается назад к кодеру и может оказывать влияние на выбор последующих входов канала. Докажем, что
N
/ (U; \N) < 2 ЦХп;Уп) <NC. я = I
531
Это можно показать с помощью следующих соотношений (ваша задача — показать, что каждое из этих соотношений справедливо):
N
ЦU;Y^)= 2 l{V-,Yn\Yn-X
П= 1
HV-.YnlY, ...Уп_,) <I(VXn\Yn\Y1 ...У„_1) =
= I(Xn-Yn\Y1...Yn^1)<I(Xn-Yn).
С помощью этого результата показать, что обращение теоремы кодирования остается в силе для дискретного канала без памяти с обратной связью. Замечание', этот результат несправедлив для каналов с памятью.
4.7. В теореме 4.3.1 была найдена нижняя граница для Ре, выраженная че-
рез H(U\V). Предположим здесь, что декодер проводит декодирование с минимальной вероятностью ошибки, и найдем верхнюю границу для Ре. Будем считать, что U и V имеют одно и то же выборочное пространство, скажем alt ..., а^\ при декодировании с минимальной вероятностью ошибки имеет место следующее соотношение: P(j\V{ai\ai) > ПРИ всех k ф L Используя это неравен-
ство, показать, что
Ре < H(U\V) натуральных единиц. (*)
Указание: пусть IV является произвольным ансамблем с вероятностями </;. Покажите, что (в натуральных единицах)
H{W) > 2 </;(! -<7г)>1 -W- (**>
i
Пусть H(U\v)=—^ Р (и I v) In Р (и I у)
и
и пусть Pe(v) является вероятностью ошибки при условии, что декодировано сообщение v. Используйте (**) для того, чтобы показать, что H(U\v) > Pe(v), и используйте этот результат, чтобы установить справедливость (*).
Усложнение задачи. Показать, что (**) можно заменить на более сильное неравенство для H(W) в битах: H(W) > 2(1 — Цтах) и, таким образом, Ре ^
< 42H(U\V) бит.
4.8. Используя неравенство log г < (z — 1) log е, показать справедливость (4.3.16).
4.9. Доказать, что неравенства (4.4.4) и (4.4.5) справедливы.
Указание [для (4.4.4)]: пусть а, |3 — две точки на интервале и пусть б = = Яа + (1 —Л)Р является точкой, лежащей между а и |3. Используйте затем разложение в ряд Тейлора при любом х
/(*)=/(6) +(*—6)/' (S)
при некотором у между х и б. Изобразите также это на рисунке.
Указание [для (4.4.5)]: используйте индукцию по L.
4.10. Пусть Q^x) и Q2(x) — некоторые распределения вероятностей на одном и том же дискретном выборочном пространстве и пусть Н^Х) и Н2(Х) — соответствующие им энтропии.
(а) Показать что Q(x) = ^Qi(x) + (1 — X)Q3(x) при 0 < X < 1 являет ся распределением вероятностей на выборочном пространстве.
(б) Пусть Н(Х) является энтропией, соответствующей распределению вероятностей Q(x) из пункта (а). Доказать, что
Н(Х) >ХН1 (Л-) + (1-Я)Н2(Х)
и найти условия равенства.
(в) Дать геометрическую интерпретацию результата пункта (б).
4.11. Функция Да) определена в выпуклой области R векторного пространства. Доказать, что f является выпуклой о тогда и только тогда, когда функ-
532
ция f(k<zi + (1 — ^)я2) является выпуклой функцией К, 0 < ). < 1, при всех а1; а2 из R-
