Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
3.21. Рассмотрим стационарный эргодический двоичный источник, последовательность на выходе которого обозначим через и = (..., и_х, и0, и1(...). Предположим, что символы, имеющие четные номера, ..., и2, и0, и2,..., суть статистически независимые равновероятные двоичные случайные величины. С вероятностью V2 «2П.+1 = и2П для всех п не вероятностью V2 u2n_1 = и2п для всех п. Будем считать, что пары букв источника (и2п, и2П+1) кодируются в соот» ветствии с правилом
00 - 0 \
11 -*¦ 10 01-110 10 - Ш
Показать, что с вероятностью V2 число кодовых букв на букву источника в длинной последовательности стремится к 3/4 и с вероятностью х/2 стремится к 9/s.
3.22. (а) Найти стационарные вероятности состояний q(j) для марковского источника, указанного ниже, и найти стационарные вероятности отдельных букв.
(б) Найти условную энтропию буквы на выходе источника при условии, что задано текущее состояние источника H(U\s = /) при 1 < / < 3.
(в) Найти энтропию на букву последовательности источника (U).
(г) Для любого состояния источника s = j найти оптимальный неравномер-
ный двоичный код, чтобы кодировать буквы алфавита источника, для которых Pj(ah) > 0- Показать, что весь код (при выборе кодовых слов в соответствии с текущим состоянием и выходом) является однозначно декодируемым даже тогда, когда выбрано одно кодовое слово нулевой длины для состояния 3. _
(д^ Подсчитать среднее число кодовых букв на букву источника п. Сформулировать общие условия, при которых п = H^(U) для такого метода кодирования.
3.23. Для указанных ниже источников введем в рассмотрение следующий процесс Маркова, состояния которого отмечены кружками. В течение каждой единицы времени источник находится в определенном состоянии, производит букву (aj или о2) и переходит в новое состояние. Число, написанное на каждой стрелке, означает вероятность произвести указанную букву и перейти в указанное стрелкой состояние при условии того, что источник находится в состоянии, ука-
ат;о9*
занном на хвосте стрелки. Заметим, что такие источники не являются марковскими, так как новое состояние не определяется текущим состоянием и выходной буквой. Источники такого типа часто называются источниками, порождаемыми марковскими источниками.
(а) Показать, что источник 1, изображенный на рисунке, является тонко замаскированным двоичным источником с независимыми равновероятными буквами и имеет энтропию 1 бит на букву (неосторожное применение (3.6.21) могло бы дать энтропию, равную нулю).
(б) Показать, что энтропия второго источника (и любого такого источника) ограничена неравенствами
H(fJi\Ui.t ... UiSx) <Hm{U)<H(fJl\Ut^...Ul).
Показать, что нижняя граница не убывает с ростом I, а верхняя граница не возрастает с ростом I. (Для того чтобы найти Н (U) для частного источника, приведенного здесь, см. Гилберт (1960), где развит метод разложения в ряды.)
Глава 4
4.1. Пропускные способности каналов из множества N дискретных каналов без памяти равны Сх, С2, ..., Сдг. Пусть эти каналы соединены параллельно в том смысле, что в каждую единицу времени по каждому каналу передается и принимается произвольный символ. Следовательно, вход х = (xlt ..., xN) параллельного соединения каналов представляет собой последовательность N компонент, каждая из которых является входом одного из каналов, а выход у= (ylt ..., yNj представляет собой последовательность N компонент, каждая из которых является выходом одного из каналов. Доказать, что пропускная способность парал-
N
лельного соединения каналов равна 2 Сп.
п=1
Предполагается, что выход каждого канала статистически зависит лишь от входа этого канала, т. е.
'D (У ! Х) = П -Р (Уп I хп).
п
Не делайте предположения, что входы независимы.
Указание: см. доказательство теоремы 4.2.1.
4.2. Выход канала проходит через устройство обработки информации без потери информации, т. е./(X; F) — I(X;Z), где X — ансамбль на входе канала; Y — ансамбль на выходе канала, a Z — выход устройства обработки информации. Привести пример, в котором H(Y) > H(Z), и привести пример, в котором Я(Г) < H(Z). Устройство обработки информации не обязательно должно быть неслучайным.
4.3. Другое доказательство теоремы 4.3.1 проводится следующим образом. Можно интерпретировать совместный ансамбль UV как ансамбль UVE, где выборочными точками Е являются события е и с, причем е соответствует ошибке (и Ф v), а с соответствует правильному приему (и = у). Тогда
и (U I V) = Н (UE I V) =н (Е j V) +Н (U | VE)=H(E\V) +PeH(U\ Ve) -f + (l—Pe)H(U\ Vc) < H (E) + Pe H (U | Ve) < H (E) + Pe log (M -1).
Обосновать те из указанных выше соотношений,которые не являются очевидными.
