Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
(а) Имеют ли какие-либо кодовые слова длины, неравные / или / + 1? Почем у?
(б) Выразить с помощью / и х число кодовых слов, имеющих длину /.
(в) Чему равна средняя длина кодового слова?
3.16. Определим рассогласование между двоичным кодом и ансамблем сообщений U как п — H(U). Показать, что рассогласование между U и оптимальным двоичным кодом для U всегда больше или равно рассогласованию между U' и оптимальным двоичным кодом для W, где U' — редуцированный ансамбль для U, рассмотренный в § 3.4.
3.17. В нижеследующей задаче изложен метод, который называется кодированием длин серий. Этот метод является не только полезным сам по себе, но он также позволяет понять более точно причину, по которой метод кодирования Хаффмана является оптимальным. Источник U производит последовательность независимых двоичных символов с вероятностями Р(0) = 0,9, Р(1) = 0,1. Будем кодировать эти последовательности в два этапа, сначала подсчитывая число нулей между последовательными единицами на выходе источника, и затем кодируя эти длины серий двоичными кодовыми словами. Первый этап кодирования отображает последовательности источника в промежуточные числа по следующему правилу:
Последователь Промежуточные Последователь Промежуточные
ность источника числа (число нулей) ность источника числа (число нулей)
1 0
01 1 .
00 1 2 .
0 0 0 1 3 000 00001 7
00000000 8
Таким образом, приводимая ниже последовательность кодируется следующим образом:
100100000000001 100001
0, 2, 8, 2,0, 4
Последний этап кодирования сопоставляет кодовое слово из одного двоичного символа промежуточному числу 8 и кодовые слова из четырех двоичных символо-лов — другим промежуточным числам.
(а) Показать справедливость (настолько подробно, насколько вам будет удобно) того, что получившийся код однозначно декодируем.
(б) Найти среднее число пх букв источника, приходящихся на промежуточное число.
(в) Найти среднее число я2 кодовых двоичных символов, приходящихся на промежуточное число.
(г) Используя закон больших чисел, показать, что для очень длинной последовательности букв источника отношение числа кодовых двоичных символов к числу букв источника с большой вероятностью будет близко к п21пх. Сравнить это отношение со средним числом кодовых символов на букву источника для кода Хаффмана, кодирующего сразу четыре буквы источника.
3.18. (а) Источник имеет пять букв со следующими вероятностями: -Р^) = = 0,3; Р{а2) — 0,2; Р(а3) = 0,2; Р(а4) = 0,15; Р(а5) = 0,15. Эти буквы должны быть закодированы двоичным кодом для передачи по каналу без шумов. Передача 0 занимает 1 с, а передача 1 занимает 3 с. Используя метод проб и ошибок, найти префиксный код, который минимизирует среднее время, требуемое для передачи буквы источника, и вычислить это минимальное среднее время.
(б) Любой такой код может быть представлен деревом, в котором длина ребра пропорциональна времени, требующемуся для передачи соответствующей буквы. Показать, что у кода, минимизирующего среднее время передачи, вероят-
528
ности, соответствующие промежуточным и концевым узлам, не должны увеличиваться с увеличением длины.
3.19. Имеется некоторое число М пенни и известно, что Л1 — 1 из них имеют один и тот же вес. М-я пенни может иметь тот же вес, что и остальные, может быть тяжелее, может быть легче. Имеются балансные весы, на которых можно сравнить вес любых двух групп пенни. Нужно найти отличающуюся пенни, если таковая имеется, и определить, тяжелее ли она или легче остальных. Найти максимальное значение М, для которого задача может быть решена с помощью п взвешиваний, и подробно описать процедуру взвешивания, если:
(а) В дополнение к М пенни имеется, для сравнения, стандартная пенни.
(б) Стандартная пенни отсутствует.
Предложение: рассмотрите 2М т 1 возможных ответов как множество равновероятных исходов и сопоставьте каждому исходу кодовое слово, представляющее результаты последовательных взвешиваний.
3.20. Определим условную энтропию дискретного стационарного источника с алфавитом объема /С:
VL\L (U)=jyH (U2L ...uL+l\uL...u1).
(а) Доказать, что НцЬ(11) не возрастает вместе с L.
(б) Доказать, что
lim HL,L (t/) = W00 (U).
L->oo
(в) Рассмотрим метод кодирования для источника, при котором для каждой из KL возможных последовательностей из предыдущих L букв, поступивших в кодер, строится код Хаффмана для множества возможных последовательностей из L последующих букв, поступающих в кодер. Сформулировать аналог теоремы 3.5.2 для этого метода.
