Задача 4.Показать, что двоичный код из n кодовых слов с длинами l1, l2, …, ln и с частотой их появления, соответственно, 2-l1, 2-l2, …, 2-ln оптимален (избыточность равна 0).
Пример к этой задаче: неравномерный код из таблицы 2 (и таблицы 3) – оптимальный (удовлетворяет условию задачи). Но если у кода из таблицы 3 кодовые слова были бы равновероятны, то нетрудно подсчитать, что он будет избыточным. У кода из таблицы 1 все наоборот: он будет оптимальным, если кодовые слова равновероятны, и будет избыточным, если вероятности кодовых слов разные. (Подсчитайте избыточность всех четырех упомянутых вариантов для кодов их таблиц 1 и 3).
Троичное кодирование Фано
| сообщения
|
|
|
|
|
|
|
|
| вероятности
| 0,4
| 0,2
| 0,1
| 0,1
| 0,1
| 0,05
| 0,05
|
|
| A
| B
| B
| C
| C
| C
| C
|
| Фано
| A
| BA
| BB
| CA
| CB
| CCA
| CCB
|
| Каффман
| A
| BA
| BB
| BC
| CA
| CB
| CC
|
Cсравним цены этих троичных кодов:
Lf = 0.4+0.2*2+0.3*2+0.1*3=0.8+0.6+0,3=1.7Lk = 0.4+0.6*2=1.6
Задача 5. Подсчитать среднюю длину символа в текстах кодируемых азбукой Морзе, используя таблицу часто букв русского языка и считая азбуку Морзе троичным кодом.
Задача 6. Закодировать двоичными кодами Фано и Хаффмана 6 сообщений со следующими вероятностями: 0.25, 0.2, 0.15, 0.15, 0.15, 0.1, найти цены полученных кодов и их избыточности.
Префиксный код называется полным, если присоединение к нему любого нового кодового слова нарушает его свойство быть префиксным.
Задача 7. Какие коды из приведенных выше примеров префиксных кодов являются полными, а какие нет.
