Даны p(a)=0.50, p(b)=0.25, p(c)=0.15, p(d)=0.10.

1) Энтропия (в битах)
H = −Σ p_i log2 p_i =
-0.5·log2 0.5 − 0.25·log2 0.25 − 0.15·log2 0.15 − 0.1·log2 0.1 =
0.5 + 0.5 + 0.4105448 + 0.3321928 ≈ 1.7427 бит/символ.

2) Оптимальный префиксный код (Хаффман)
Склеиваем наименьшие вероятности: 0.15+0.10=0.25, затем 0.25+0.25=0.5 и т.д. Получаем дерево с длинами:
l(a)=1, l(b)=2, l(c)=3, l(d)=3.

Один возможный код (префиксный):
a: 0
b: 10
c: 110
d: 111

3) Средняя длина кода
L = Σ p_i l_i = 0.5·1 + 0.25·2 + 0.15·3 + 0.10·3 = 1.75 бит/символ.

4) Что показывает разница H и L
Разница (избыточность, redundancy) R = L − H ≈ 1.75 − 1.7427 = 0.00726 бит/символ (≈0.42% относительн.). Это показывает неэффективность кода по сравнению с теоретическим нижним пределом (энтропией). Для префиксных кодов с целыми длинами выполняется неравенство H ≤ L < H + 1; алгоритм Хаффмана даёт оптимальную среднюю длину среди префиксных (целочисленных) кодов, поэтому оставшаяся разница обусловлена в основном требованием целочисленных длин кодовых слов (и структурой распределения). При блоковом кодировании (кодирование групп символов) можно приблизить среднюю длину ещё ближе к H.