НОВОСТИ   БИБЛИОТЕКА   ЮМОР   КАРТА САЙТА   ССЫЛКИ   О САЙТЕ  




предыдущая главасодержаниеследующая глава

Задачи и дополнения

1. Доказать, что всякий оптимальный код является

2. Закодировать двоичным кодом Хаффмена множество сообщений, имеющих вероятности:

p1 = 0,25; p2 = 0,2; p3 = p4 = p5 = 0,15; p6 = 0,1.

Построить соответствующее кодовое дерево.

3. Основываясь на алгоритме Хаффмена, найти способ непосредственного построения кодового дерева оптимального кода.

Указание. Построение дерева надо начинать не с корня, а с концевых вершин.

4. В некоторых случаях результаты двоичного кодирования по методу Фано те же, что и по методу Хаффмена, в том смысле, что длины соответствующих кодовых слов для обоих методов совпадают. Так, например, обстоит дело для множества сообщений с вероятностями:

p1 = 1/4; р2 = p3 = р4 = р5 = 1/8; p6 = p7 = p8 = p9 = 1/16.

На самом деле справедливо следующее утверждение: если pi = 2-ni (т. е. если вероятности являются степенями двойки), то длины соответствующих кодовых слов в кодах Фано и Хаффмена одинаковы и равны ni.

5. Не всегда полный код является оптимальным для данного множества сообщений, Можно доказать, однако, что всякий полный код является оптимальным для некоторого множества сообщений с подходящим образом подобранными вероятностями. Так, если кодовые слова полного кода с основанием d имеют длины n1, n2, ..., nN, то он оптимален для множества сообщений с вероятностями d-n1, d-n2, ..., d-nN.

предыдущая главасодержаниеследующая глава








© Злыгостев А.С., 2001-2019
При использовании материалов сайта активная ссылка обязательна:
http://informaticslib.ru/ 'Библиотека по информатике'
Рейтинг@Mail.ru
Поможем с курсовой, контрольной, дипломной
1500+ квалифицированных специалистов готовы вам помочь