Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
для всех ink при i < k, то можно использовать процедуру, описанную в задаче
3.5. Если это условие не выполнено, то можно поступить следующим образом. Пусть
1 ~1 1
Qi= 2 р(аь) +~irP(ai) при Qi=°-
k= 1 2
Кодовое слово для сообщения о; составляется усечением двоичного «десятичного» разложения (?; после первых «г символов, где я; является наименьшим целым числом, большим или равным/(aj) + 1. Доказать, что код, построенный согласно указанному здесь правилу, является алфавитным, удовлетворяет свойству префикса и для его средней длины справедливо неравенство п < H(U) + 2.
3.7. (а) Показать, что теоремы 3.2.1 и 3.2.2 справедливы при К = оо.
Указание: покажите, что из теоремы 3.2.2 следует, что однозначная декодируемость влечет за собой выполнение условия
k
2 D~ni < 1 ( = 1
для всех конечных k, затем перейти к пределу.
(б) Показать, что теорема 3.3.1 справедлива для ансамбля источника с бесконечным счетным алфавитом и конечной энтропией.
3.8. Теорема кодирования для источника утверждает, что для источника с энтропией H(U) можно каждой букве алфавита сопоставить двоичное кодовое слово таким образом, чтобы образовался префиксный код со средней длиной п < H{U) + 1.
526
Показать на примере, что эта теорема не может быть улучшена. Т. е. для любого е > 0 найти источник, для которого минимальная длина п удовлетворяет п > H(U) +1—8.
3.9. Рассмотрите два дискретных источника без памяти. Источник 1 имеет алфавит из 6 букв с вероятностями 0,3,0,2, 0,15, 0,15, 0,1, 0,1. Источник 2 имеет алфавит из 7 букв с вероятностями 0, 3, 0,25, 0,15, 0,1, 0,1, 0,05, 0,05. Построить двоичный код Хаффмана и троичный код Хаффмана для каждого множества сообщений. Найти среднее число кодовых букв на букву источника для каждого кода.
3.10. Рассмотрите двоичный код Хаффмана для источника 1 из задачи 3.9. Пусть NL является случайной величиной, представляющей общее число кодовых букв, порождаемых последовательностью L букв источника, поступающих на кодер.
(а) Найти \im(N JL) и четко указать, в каком смысле этот предел сущест-
оо
вует.
(б) Предположить, что двоичный код строится с использованием множества всех последовательностей длины К из того же самого источника, что и множество сообщений, и пусть NL[^(K) является случайной величиной, обозначающей общее число кодовых букв, порождаемых последовательностью из LK букв источника, поступающих на кодер. Найти
К ОО L -> оо LK
и указать, в каком смысле этот предел существует.
3.11. Для каждого множества сообщений задачи 3.9 найти префиксный код с минимальной средней длиной при условии, что первая буква каждого кодового слова должна быть 0 или 1 и каждая последовательная кодовая буква может быть 0, 1 или 2. Найти общее правило для построения префиксных кодов с минимальной средней длиной при указанном ограничении и объяснить, почему оно работает.
3.12. Для источника 1 задачи 3.9 найти двоичный код с минимальной средней длиной, который удовлетворяет свойству суффикса. Свойство суффикса состоит в том, что никакое кодовое слово не совпадает с никаким суффиксом никакого другого кодового слова. Показать, что код, обладающий свойством суффикса, всегда однозначно декодируем, и показать, что минимальная средняя длина, взятая по всем кодам, обладающим свойством суффикса, для данного источника равна средней длине кода Хаффмана для того же источника.
3.13. Множество из 8 сообщений с вероятностями 0,2, 0,15, 0,15, 0,1, 0,1,
0,1, 0,1, 0,1 должно быть закодировано троичным префиксным кодом. Построить два множества кодовых слов, длины которых имеют одно и то же минимальное среднее значение, но различные дисперсии. Найти общую среднюю длину и каждую из дисперсий. Указать причины, по которым тот или другой код предпочтительнее для применения.
3.14. Дискретный источник без памяти с алфавитом объема К имеет энтро пию H(U) бит. Множество троичных кодовых слов, удовлетворяющее свойству префикса, найдено для букв источника, и средняя длина кодовых слов равна
- П{11)
п =------- .
logs 3
(а) Доказать, что вероятность каждой буквы источника имеет вид 3 где » — целое число, зависящее от буквы.
(б) Доказать, что число сообщений в алфавите источника нечетно.
3.15. Источник имеет алфавит из К букв и все буквы равновероятны. Эти буквы кодируются двоичными кодовыми словами по методу Хаффмана (т. е. так, чтобы минимизировать среднюю длину кодового слова).
Пусть / и х выбраны так, что К = х2^ > где j является целым числом и
1 < х < 2.
527
