Рассматривается постоянный источник X с вероятностями букв 110

Вычисляем энтропию источника:
HX=-110log2110+…+49078580log249078580≈1,82
1. Код Хаффмана
Построение дерева начинаем со списка листьев (буквы сортируем по не возрастанию вероятностей):
На первом шаге из листьев дерева выбираются два с наименьшим весом - x2 и x3. Они присоединяются к узлу-родителю, вес которого устанавливается в 111+112=23132. Затем узлы x2 и x3 удаляются из списка свободных. Узел x2 (с большей вероятностью) соответствует ветви 0 родителя, узел x3 - ветви 1. Дерево кодирования после первого шага:
На втором шаге «наилегчайшей» парой оказываются листья x4 и x1 – присоединяем их к родителю и т.д. Окончательно получаем:
На основании построенного дерева буквы представляются кодами, отражающими путь от корневого узла до листа, соответствующего нужному символу (в третьей строке укажем также вероятности букв):
x1
x2
x3
x4
x5
101 110 111 100 0
110
111
112
213
49078580
Определяем среднюю длину кодовой комбинации как среднее количество символов, требуемых для кодирования одного символа с учетом вероятностей генерации случайных символов:
lкод=3∙110+111+112+213+1∙49078580≈1,86
2 . Код Шеннона
Сортируем буквы по не возрастанию вероятностей и вычисляем кумулятивную вероятность:
x5
x4
x1
x2
x3
49078580
213
110
111
112
0 49078580
479660
109132
1112
Переводим кумулятивную вероятность в двоичную систему счисления, вычисляем длину кодового слова по формуле Lxi=-log2pxi (z – наименьшее целое число, не меньшее z) и получаем код соответствующей буквы:
x5
x4
x1
x2
x3
0,00000… 0,10010… 0,10111… 0,11010… 0,11101
Lxi
1 3 4 4 4
Код 0 100 1011 1101 1110
Определяем среднюю длину кодовой комбинации:
lкод=1∙49078580+3∙213+4∙110+111+112≈2,13
3