Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
(в) Используйте неравенство Чебышева для того, чтобы оценить вероятность появления последовательности, которой не соответствует кодовое слово, и сравните результат с пунктом (б).
3.2. Источник производит статистически независимые двоичные символы с вероятностями Р(0) =- 3/4, Р(1) = 1/4. Рассмотрите последовательности и из L последовательных символов и связанное с ними неравенство
Рг
/(я)
L
-H(U)
|>б
<е.
(*)
где H(U) — энтропия источника.
524
(а) Найти L0, такое, что (*) справедливо при L > L0, когда б — 0,05,
Указание: используйте неравенство Чебышева.
(б) Повторить вычисления для б = 10_3, s = 10_в.
(в) Пусть А является множеством последовательностей и, для которых
/(и)
-H(V)
б.
Найти верхнюю и нижнюю границы числа последовательностей в А, когда L = L0 для случаев, описанных в пунктах (а) и (б).
3.3. Источник имеет алфавит из 4 букв. Вероятности букв и два возможных множества двоичных кодовых слов для источника приведены ниже.
Буква Вероятность Код I
Код II
Ol
а г а3
«4
0,4
0,3
0,2
0,1
1
01 00 1 000
1
1 о 100 1000
Для каждого кода ответьте на следующие вопросы (не требуются доказательства или численные подтверждения).
(а) Удовлетворяет ли код свойству префикса?
(б) Является ли код однозначно декодируемым?
(в) Чему равна взаимная информация о событии, что буква источника равна аъ содержащаяся в событии, что первый символ кодового слова равен 1?
(г) Чему равна средняя взаимная информация о букве источника, содержащаяся в первом символе кодового слова? Дайте эвристическое объяснение цели, с которой используется первая буква в кодовых словах кода II.
3.4. Код не является однозначно декодируемым тогда и только тогда, когда существует конечная последовательность, которая может быть разбита двумя различными способами на последовательности кодовых слов. То есть должна произойти ситуация, такая, как изображена ниже
А,
где Ai (и Bj) — кодовое слово. Заметим, что Вг должно быть префиксом Alt и при этом образуется некоторый «повисший суффикс». Каждый повисший суффикс в этой последовательности в свою очередь должен быть либо префиксом кодового слова, либо иметь кодовое слово в качестве префикса и давать другой повисший суффикс. Наконец, последний повисший суффикс последовательности должен сам быть кодовым словом. Таким образом, можно предложить следующий способ проверки однозначности декодирования [который на самом деле является критерием Сардинаса — Паттерсона (1953)]. Постройте множество S всех возможных повисших суффиксов. Код является однозначно декодируемым тогда и только тогда, когда 5 не содержит кодовых слов.
(а) Составить точные правила для построения множества 5.
(б) Предположите, что длины кодовых слов равны m;, i— 1, 2, ........... М.
Найти хорошую границу сверху для числа элементов в множестве S.
(в) Определить, какой их следующих кодов однозначно декодируем:
525
{о, 10, 11} { 00, 01, 10, 11}
{О, 01, 11} {110, И, 10}
{0, 01, 10} {по, 11, 100, 00, 10}
{о, 01}
(г) Для каждого однозначно декодируемого кода из (в) построить, если это возможно, бесконечно длинную кодовую последовательность с известным начальным символом, такую, что она может быть разложена на кодовые слова двумя различными способами. (Это иллюстрирует тот факт, что однозначная декодиру-емость не всегда означает конечную декодируемость.) Доказать, что такая последовательность не возникает для префиксного кода.
3.5. Рассмотрите следующий метод построения двоичных кодовых слов для ансамбля сообщений U с распределением вероятности Р(и). Пусть Р(од) <
< P(aj) для k > / > 1; определим
;—1
Qi^^p(ak) при i>l; Qx-Q-
k=\
Кодовое слово, соответствующее сообщению а;, составляется с помощью «десятичного» разложения <?г < 1 в двоичной системе (т. е. V2 -*¦ 100..., Vt 0100..., 6/8 10100...,) и усечения этого разложения после первых щ
символов, где я; является наименьшим целым числом, большим или равным /(а;) бит.
(а) Построить двоичные кодовые слова для множества из восьми сообщений, появляющихся с вероятностями V4, V4, V8, V8, Vm, Vie, Vie, Vie-
(б) Доказать, что описанный выше метод во всех случаях приводит к множеству кодовых слов, удовлетворяющему свойству префикса, и что для средней длины п справедливо неравенство H(U) < п < H{U) + 1.
3.6. Иногда требуется закодировать множество сообщений источника «ал-
фавитным» двоичным кодом. Двоичный код называется алфавитным, если для любых (, k при i < k кодовое слово для а{ (рассматриваемое как двоичное «десятичное» разложение) меньше, чем кодовое слово для яд. Если Р(й*) > Р(а{)
