Необходимо кодировать в двоичном коде сообщение, алфавит которого состоит из двух независимых символов z1 и z2, вероятность которых p1 и p2 даны. Провести кодирование по одному символу, блоками по два и по три символа, используя метод Хаффмана. Рассчитать эффективность кода в каждом случае и сравнить их
p1=0,85, p2=0,15
Решение
Произведем кодирование по одному символу - z1 = 1, z2 = 0.
Энтропия
Hpi=-0,85log20,85+0,15log20,15=0,6098
Эффективность кода
χ=Hpilog22=0,60981=0,6098 60,98 %
Проведем кодирование блоками по 2 символа
Вероятность появления блока
p11=p1p1=0,85×0,85=0,7225
p12=p1p2=0,85×0,15=0,1275
p21=p2p1=0,15×0,85=0,1275
p22=p2p2=0,15×0,15=0,0225
Строим объединение вероятностей в соответствии с алгоритмом Хаффмана
Рисунок 1. Объединение вероятностей при кодировании блоками по два
Строим кодовое дереве и записываем кодовые комбинации
Рисунок 2
. Кодовое дерево Хаффмана при кодировании блоками по два
Таблица 1. Таблица кода при кодировании блоками по два
Блок Код Длина кода Li
x1x1 1 1
x1x2 01 2
x2x1 001 3
x2x2 000 3
Средняя длина кода
L=piLi=0,7225×1+0,1275×2+0,1275×3+0,0225×3=1,4275
Эффективность кода при кодировании блоками по два
χ=2HpiL=2×0,60981,4275=0,8544 85,44 %
Проведем кодирование блоками по 3 символа
Вероятность появления блока
p111=p1p1p1=0,85×0,85×0,85=0,6141
p112=p1p1p2=0,85×0,85×0,15=0,1084
p121=p1p2p1=0,85×0,15×0,85=0,1084
p122=p1p2p2=0,85×0,15×0,15=0,0191
p211=p2p1p1=0,15×0,85×0,85=0,1084
p212=p2p1p2=0,15×0,85×0,15=0,0191
p221=p2p2p1=0,15×0,15×0,85=0,0191
p222=p2p2p2=0,15×0,15×0,15=0,0034
Строим объединение вероятностей в соответствии с алгоритмом Хаффмана
Рисунок 3