Энтропия бинарного источника (вероятность единицы $p$):
$$H(p)=-p{\log }_{2}p-(1-p){\log }_2(1-p),$$ максимум при $p=\frac{1}{2}$ равен $1$ бит на символ.
Оптимальная длина кода (асимптотически):
- Теорема Шеннона (сжатие): средняя длина кода на символ $L$ удовлетворяет $L\ge H(p)$. При блочном кодировании при увеличении блока можно получить $L\to H(p)$.
- Практические оценки: префиксный (Хаффман) код даёт
$$H(p)\le L_{\text{Huffman}}<H(p)+1,$$ арифметическое и контекстно-адаптивное кодирование (или LZ-методы) приближают $H(p)$ сколь угодно близко при больших блоках.
Добавление шума (BSC с вероятностью ошибки $\epsilon$):
- Ёмкость бинарного симметричного канала (BSC):
$$C=1-H(\epsilon )=1-(-\epsilon {\log }_2\epsilon -(1-\epsilon ){\log }_2(1-\epsilon )).$$ - Условие возможности безошибочной (с вероятностью ошибки стремящейся к нулю) передачи: скорость источника не должна превышать ёмкость канала, т.е.
$$H(p)\le C=1-H(\epsilon ).$$ Если это выполняется, то по теореме разделённого кодирования возможно сначала сжать до скорости $R\approx H(p)$, затем передать с кодом исправления ошибок с кодовой скоростью $R\le C$. Если $H(p)>C$, то при любом кодировании нельзя обеспечить надёжную передачу всех исходных битов без потерь.
В практических единицах: минимальное число каналных использований на символ источника (асимптотически) не меньше
$$\frac{H(p)}{C}=\frac{H(p)}{1-H(\epsilon )}.$$
Связь теоретических пределов с практическими алгоритмами:
- Сжатие: Huffman, arithmetic coding, LZ-семейство приближают среднюю длину к $H(p)$ при конечной вычислимости и ресурсах; при малых блоках наблюдается избыточность порядка $O\left(\frac{\log n}{n}\right)$.
- Исправление ошибок: современные коды (LDPC, turbo, polar) приближают ёмкость $C$ при больших блоках и умеренной сложности; для конечной длины существует штраф (finite-blocklength) — отклонение от $C$ порядка $O(1/\sqrt{n})$.
- Разделённое кодирование (сжатие затем кодирование по Шеннону) асимптотически оптимально, но в практических конечных длинах иногда выигрывает совместное кодирование (joint source–channel), особенно при жёстких задержках или малых блоках.
Кратко: энтропия $H(p)$ задаёт нижнюю границу средней длины сжатого кода; при наличии шума канал имеет ёмкость $1-H(\epsilon )$, и для надёжной передачи требуется $H(p)\le 1-H(\epsilon )$. Практические алгоритмы стремятся достигнуть этих пределов, но в конечной длине наблюдается неизбежная потеря эффективности, компенсируемая выбором конкретных кодов и блоковых размеров.