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

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

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

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

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

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

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

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

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