Задача кодирования (формулировка).
- Имеется источник сообщений с распределением $P_X$ и энтропией в битах на символ $H(X)=-\sum _x{P}_X(x){\log }_2{P}_X(x)$.
- Имеется шумный канал с пропускной способностью (ёмкостью) $C$ бит на одно использование канала.
- Нужно построить кодирующий оператор (сжатие + добавление избыточности) и декодер, которые для больших блоков исходных символов обеспечивают вероятность ошибки передачи $\to 0$.
Ключевые теоремы Шеннона (кратко).
1) Теорема о сжатии источника (source coding): для стационарного эргодического источника средняя длина кода на символ $\bar{L}$ удовлетворяет
$$\bar{L}\ge H(X),$$ и существуют коды с $\bar{L}\to H(X)$ при росте блока. То есть $H(X)$ — фундаментальный предел сжатия (не учитывая потери/примеров).
2) Теорема о пропускной способности канала (channel coding): для канала с ёмкостью $C$ любые скорости передачи $R<C$ достижимы с вероятностью ошибки, стремящейся к нулю при росте длины блока; а при $R>C$ надёжная передача невозможна (ошибка остаётся отличной от нуля). Формально: существуют коды размера $2^{nR}$ на блок длины $n$ с ошибкой $\to 0$ если $R<C$.
Связь сжатия и коррекции ошибок (разделение задач).
- При разделении (Shannon separation theorem) можно сначала сжать источник до примерно $H(X)$ бит/символ, затем кодировать для канала. Для надёжной передачи требуется, чтобы средовая скорость информации не превышала ёмкость канала:
$$\text{(информация за символ)}H(X)\le \rho C,$$ где $\rho$ — число использований канала на один символ источника (обычно $\rho =1$, тогда требование $H(X)\le C$). В блоковой форме: для $k$ источ. символов и $n$ использований канала требуется
$$kH(X)\le nC.$$
Примеры и численные иллюстрации.
1) Бинарный источник с вероятностью единицы $p$. Энтропия
$$H(p)=-p{\log }_{2}p-(1-p){\log }_2(1-p).$$ - Если $p=0.5$, то $H=1$ бит/символ — не удастся сжать ниже 1 бита/символ без потерь.
- Если $p=0.9$, то $H(0.9)\approx 0.469$ бита/символ — можно сжать до ≈0.47 бита/символ.
2) Бинарный симметричный канал (BSC) с вероятностью искажения $q$. Его ёмкость
$$C=1-H(q),$$ где $H(q)$ — бинарная энтропия. Например, при $q=0.1$ имеем $H(0.1)\approx 0.469$ и $C\approx 0.531$ бит/использование.
Комбинация источника и канала:
- Для источника с $p=0.9$ ($H\approx 0.469$) и BSC с $q=0.1$ ($C\approx 0.531$) выполняется $H<C$, значит при достаточно длинных блоках возможно сжатие до ~$0.469$ бита/символ и надежная передача (без потерь) через этот канал.
- Для равновероятного источника ($H=1$ бит/символ) и канала с $C=0.5$ бит/использование невозможно передать по одному использованию на символ: требуется по меньшей мере $\rho =H/C=2$ использ. канала на символ (т.е. добавить избыточность / уменьшить скорость).
Интуиция о компромиссе.
- Сжатие убирает избыточность источника, снижая количество бит информации; это хорошо для экономии канальных ресурсов, но оставляет меньше резервов для исправления ошибок.
- Канальное кодирование добавляет избыточность для коррекции ошибок; общая эффективность зависит от того, чтобы итоговая скорость передачи информации не превышала ёмкость $C$.
- На практике существуют ограничения конечной длины блока, задержек и вычислительной сложности: тогда достижение асимптотических пределов $H$ и $C$ невозможно, и появляется компромисс между скоростью, задержкой и вероятностью ошибки.
Короткое резюме.
- Предел сжатия: средняя длина кода $\ge H(X)$.
- Предел коррекции: надёжная передача возможна только при скорости информации $R<C$.
- Для надёжной передачи источника через канал требуется $kH\le nC$ (или $H\le \rho C$); при нарушении этого условия надёжность невозможна независимо от алгоритмов.