Коротко — что такое энтропия и как она влияет на кодирование, на конкретном примере.
Определение: энтропия источника $X$ с распределением $p(x)$ — среднее количество информации в символе
$$H(X)=-\sum _{x}p(x){\log }_{2}p(x).$$
Дано: $p(a)=0.5,p(b)=0.25,p(c)=0.125,p(d)=0.125$.
Вычислим вклад каждого символа:
$$-p(a){\log }_{2}p(a)=-0.5{\log }_{2}0.5=0.5,$$ $$-p(b){\log }_{2}p(b)=-0.25{\log }_{2}0.25=0.5,$$ $$-p(c){\log }_{2}p(c)=-0.125{\log }_{2}0.125=0.375,$$ $$-p(d){\log }_{2}p(d)=0.125\cdot 3=\mathrm{0.375.}$$ Сумма даёт энтропию
$$H(X)=0.5+0.5+0.375+0.375=1.75\text{bits}.$$
Влияние на кодирование: теоретически средняя длина любого префиксного (безамбигуозного) кода $\bar{L}$ удовлетворяет
$$H(X)\le \bar{L}<H(X)+1.$$ Для частот, которые являются степенями $1/2$ (диадические), можно построить префиксный код с целочисленными длинами, дающий $\bar{L}=H(X)$.
Построим оптимальный (Хаффмана) код для данного распределения: сначала объединяем $c$ и $d$ (оба по $0.125$), затем объединяем их с $b$ ($0.25$), затем с $a$ ($0.5$). Один возможный префиксный код:
$$a\mapsto 0,b\mapsto 10,c\mapsto 110,d\mapsto 111.$$ Длины кодов: $l(a)=1,l(b)=2,l(c)=3,l(d)=3$. Средняя длина
$$\bar{L}=0.5\cdot 1+0.25\cdot 2+0.125\cdot 3+0.125\cdot 3=1.75\text{bits}.$$ Здесь $\bar{L}=H(X)$, то есть код оптимален и без избыточности, потому что распределение диадическое.
Сравнение с равномерным 4-символьным источником: при равномерном распределении $H_{\text{uniform}}=-4\cdot \frac{1}{4}{\log }_2\frac{1}{4}=2$ bits, т.е. неравномерность снизила среднюю длину на $2-1.75=0.25$ bits в среднем на символ.
Вывод: энтропия даёт нижнюю границу средней длины кода; для диадических вероятностей можно добиться равенства $\bar{L}=H$. В общем случае оптимизация кодов (например, Хаффмана) стремится приблизить $\bar{L}$ к $H(X)$.