Энтропия источника:
$H=-{\sum }_i{p}_i{\log }_2{p}_i=-(0.5{\log }_{2}0.5+0.25{\log }_{2}0.25+0.125{\log }_{2}0.125+0.125{\log }_{2}0.125)$.
Вычисления по членам:
$-0.5{\log }_{2}0.5=0.5$, $-0.25{\log }_{2}0.25=0.5$, $-0.125{\log }_{2}0.125=0.375$ (для C и D по одному).
Итого
$H=0.5+0.5+0.375+0.375=1.75$ бит/символ.
Оптимальный префиксный (Хаффманов) код:
Объединяем минимальные вероятности C и D в узел $0.125+0.125=0.25$, затем этот узел с B (0.25) в узел 0.5, затем с A (0.5). Один возможный код:
A: 0
B: 10
C: 110
D: 111
Средняя длина кода:
$L={\sum }_i{p}_i{l}_i=0.5\cdot 1+0.25\cdot 2+0.125\cdot 3+0.125\cdot 3=1.75$ бит/символ.
Здесь $L=H$ потому что вероятности являются двоичными степенями: $p_i=2^{-l_i}$.
Практические ограничения, влияющие на достижение энтропийного предела:
- Целые длины кодов: для общих $p_i$ длины $l_i$ должны быть целыми, поэтому для односимвольного Хаффмана справедливо $H\le L<H+1$. С блоковым кодированием длина на символ может быть ближе к $H$: для блоков длины $n$ обычно $H\le L_n<H+1/n$.
- Префиксность и синхронизация: префиксный код обеспечивает мгновенное декодирование, но при ошибке бита синхронизация может быть нарушена (пока не встретится следующий кодовый граничный узор). Требуются маркеры/фреймы или специальные самосинхронизирующие коды для устойчивости.
- Ошибки передачи: пробой одного бита может исказить несколько последующих символов (ошибка распространяется). Исправление ошибок (канальное кодирование) добавляет избыточность и повышает среднюю длину/битовую нагрузку выше энтропийного предела источника.
- Сложность и задержки: методы, приближающие $H$ (аритметическое кодирование, блочное кодирование большого $n$) требуют большего вычисления/памяти и вводят задержки; арифметическое кодирование чувствительно к точности вычислений и ошибкам.
- Практические ограничения протоколов: выравнивание по байтам, требования к минимальной задержке, ограничения на поток битов и др. также увеличивают реальную среднюю длину на символ.
Вывод: для данного распределения Хаффман даёт оптимальный префиксный код с $L=H=1.75$ бита/символ; в общем же конечные длины, синхронизация, ошибки и требование к надёжности делают достижение теоретического предела в реальной системе компромиссом.