Энтропия источника:
$$H=-\sum _{x\in \{a,b,c\}}p(x){\log }_{2}p(x)=-(0.5{\log }_{2}0.5+0.3{\log }_{2}0.3+0.2{\log }_{2}0.2)$$ $$=-(0.5\cdot (-1)+0.3\cdot {\log }_{2}0.3+0.2\cdot {\log }_{2}0.2)\approx 0.5+0.3\cdot 1.737+0.2\cdot 2.322\approx 1.4855\text{бит/символ}.$$
Построение оптимального префиксного (Хаффмана) кода:
- Сортируем вероятности: $0.5,0.3,0.2$.
- Сливаем два наименьших: $0.3+0.2=0.5$. Осталось две ветви $0.5$ и $0.5$.
- Присваиваем бит для верхнего разветвления; внутри объединённой ветви $0.3$ и $0.2$ — ещё один бит.
Один возможный код (символы и длины):
$$a:0(\ell (a)=1),b:10(\ell (b)=2),c:11(\ell (c)=2).$$
Средняя длина кода:
$$\bar{L}=\sum _{x}p(x)\ell (x)=0.5\cdot 1+0.3\cdot 2+0.2\cdot 2=1.5\text{бит/символ}.$$ Избыточность относительно энтропии:
$$\bar{L}-H\approx 1.5-1.4855\approx 0.0145\text{бит/символ}.$$
Ограничения и компромиссы в практической реализации (задержка и ошибки канала):
- Дискретность длин: префиксные коды дают целочисленные длины бит → небольшая избыточность (здесь мала).
- Задержка: Хаффман — потоковый и мгновенный (минимальная буферизация), но для ещё более близкого к энтропии сжатия используют блочное кодирование или арифметическое кодирование, что увеличивает задержку (нужно накапливать блок).
- Чувствительность к ошибкам: переменная длина приводит к сильной локальной деградации и потере синхронизации при ошибках; фиксированная длина устойчивее. Для надёжности требуется канальное кодирование (FEC) или добавление синхросигналов, что увеличивает нагрузку и задержку.
- Изменчивость статистики: при несоответствии модели (реальные p отличаются) эффективность падает; адаптивный Хаффман исправляет это, но добавляет вычислительную сложность и возможные задержки/накладные расходы.
- Сложность реализации: простые префиксные коды лёгки в декодировании; арифметическое/асимпт. кодирование даёт лучшую эффективность, но сложнее и чувствительнее к ошибкам и точности арифметики.
Краткое резюме: энтропия ≈ $1.4855$ бит/символ, оптимальный префиксный код (Хаффман) даёт среднюю длину $1.5$ бит/символ с очень малой избыточностью; выбор между немедленной передачей (малая задержка) и более плотным кодированием (меньше избыточности, больше задержки и чувствительности к ошибкам) — главный практический компромисс.