Энтропия Шеннона и взаимная информация — ключевые величины теории информации, задающие пределы сжатия и коррекции ошибок при передаче текстовых сообщений через шумный канал.
Что такое энтропия
- Определение: для дискретного источника символов $X$ с распределением $p(x)$ $$H(X)=-\sum _{x}p(x){\log }_{2}p(x).$$ Интерпретация: среднее количество бит «неопределённости» или «сюрприза» на символ.
- Последствия для сжатия:
- Верхняя теоретическая граница сжатия без потерь — не меньше $H(X)$ бит в среднем на символ.
- Для префиксного кода выполняется
$$H(X)\le \mathbb{E}[L]<H(X)+1,$$ где $\mathbb{E}[L]$ — средняя длина кода (в битах).
- Асимптотически для блоков длины $n$ типичное множество содержит примерно $2^{nH(X)}$ последовательностей (AEP), поэтому можно кодировать блоки кодуя только «типичные» последовательности и достигать средней длины близкой к $H(X)$.
Пример для текста: алфавит из 26 букв даёт максимум ${\log }_{2}26\approx 4.7$ бит/символ для равномерного распределения, но естественный язык избыточен, и при учёте контекста истинная энтропия на символ может быть заметно меньше (оценки для английского текста с учётом контекста — порядка единиц бит/символ).
Взаимная информация
- Определение для входа $X$ и выхода канала $Y$:
$$I(X;Y)=\sum _{x,y}p(x,y){\log }_2\frac{p(x,y)}{p(x)p(y)}=H(X)-H(X|Y)=H(Y)-H(Y|X).$$ Интерпретация: среднее число бит информации о $X$, которые даёт наблюдение $Y$. Уменьшает неопределённость: $H(X|Y)=H(X)-I(X;Y)$.
- Для шумного канала: если канал задан условными вероятностями $p(y|x)$, то при выборе распределения входа $p(x)$ взаимная информация на один прогон равна $I(X;Y)$. Максимум по $p(x)$ даёт пропускную способность (ёмкость) канала:
$$C=\underset{p(x)}{\max }I(X;Y).$$
Пример (бинарный симметричный канал, BSC):
- Канал, где бит переворачивается с вероятностью $p$. Для равномерного входа
$$I(X;Y)=1-H_b(p),$$ где бинарная энтропия $H_b(p)=-p{\log }_{2}p-(1-p){\log }_2(1-p)$. Следовательно
$$C=1-H_b(p).$$ Если $p=0.1$, то $C\approx 1-H_b(0.1)\approx 1-0.468\approx 0.532$ бита на использование канала.
Теоретические пределы передачи и коррекции ошибок
- Теорема кодирования источника (Шеннон): можно сжимать источник до близко к $H(X)$ бит/символ без потерь (асимптотически), но не ниже.
- Теорема о пропускной способности (noisy-channel coding theorem): для любого количества каналных использований можно надежно (с произвольно малой вероятностью ошибки) передавать информацию со скоростью $R$ бит/использование тогда и только тогда, когда $R<C$. Если $R>C$, вероятность ошибки не может стремиться к нулю.
- Следствие (разделимость): асимптотически оптимальную схему можно строить раздельно — сначала сжать до близко $H(X)$ бит/символ, затем применить код коррекции ошибок с кодовой скоростью $R$ не превышающей $C$. Для однопроходного соответствия символов и использований канала требуется
$$H(X)\le C$$ (или в общем на $n$ символов: требуется не менее $nH(X)/C$ использований канала).
- Остаточная неопределённость и нижние оценки ошибок: условная энтропия $H(X|Y)$ — это «эквивокация» (сколько остаётся неизвестного после приёма). Fano даёт связь между $H(X|Y)$ и вероятностью ошибки $P_e$:
$$H(X|Y)\le H(P_e)+P_e{\log }_2(|\mathcal{X}|-1),$$ что ограничивает минимально достижимую ошибку при данном $I(X;Y)=H(X)-H(X|Y)$.
Короткий практический вывод
- Энтропия $H(X)$ определяет, насколько можно сжать текст без потерь.
- Взаимная информация $I(X;Y)$ и её максимум $C$ определяют, сколько бит полезной информации канал способен передать на использование; если после сжатия требуемая скорость превышает $C$, надёжная передача невозможна.
- Для конкретного шумного канала (например, BSC) формулы дают численные пределы для сжатия и кодирования ошибок.