1) Энтропия источника:
$$H(X)=-\sum _i{p}_i{\log }_2{p}_i=-(0.5{\log }_{2}0.5+0.25{\log }_{2}0.25+0.25{\log }_{2}0.25)=1.5\text{бит}.$$
2) Оптимальный префиксный (Хаффманов) код:
- Свернем две наименьшие вероятности $0.25+0.25=0.5$.
- Возможный оптимальный код (символы A с $0.5$, B и C с $0.25$):
A: $0$
B: $10$
C: $11$
3) Средняя длина кода:
$$L=\sum _i{p}_i{l}_i=0.5\cdot 1+0.25\cdot 2+0.25\cdot 2=1.5\text{бит/символ}.$$
4) Избыточность:
$$R=L-H=1.5-1.5=0.$$ (Избыточность нулевая потому, что вероятности являются степенями $1/2$, что позволяет достичь $L=H$.)
5) Влияние ёмкости канала и шума на выбор кодирования (кратко):
- Ёмкость канала $C$ (бит/использование) ограничивает максимально возможную скорость передачи без ошибок: при скорости источника $R_{\text{src}}$ нужно, чтобы $R_{\text{src}}\le C$ либо применять сжатие/уменьшать скорость.
- Сжатие (например, Хаффман) оптимально для безошибочного канала — минимизирует среднюю длину. Но в реальном шумном канале после сжатия обычно добавляют канальное кодирование (избыточность для защиты от ошибок).
- Теорема разделения утверждает: асимптотически оптимально разделять сжатие и защиту от шума (source coding + channel coding), если допускается большой блок и малые ошибки. На практике важны задержка, сложность, искажения; иногда используют совместное (joint) source–channel кодирование или несимметричную защиту (более защита для важной информации).
- Следствие: выбор кодов — компромисс между степенью сжатия, требуемой защитой от шума, доступной пропускной способностью $C$, задержкой и вычислительными ресурсами.