Теоремы Шеннона для источника общего вида

Шаблон:Не путать Теоремы Шеннона для источника общего вида описывают возможности кодирования источника общего вида с помощью разделимых кодов. Другими словами, описываются максимально достижимые возможности кодирования без потерь.

Прямая теорема

В применении к побуквенному кодированию прямая теорема может быть сформулирована следующим образом:

Существует префиксный, то есть разделимый код, для которого средняя длина сообщений отличается от нормированной энтропии не более, чем на единицу:

$E_{U}w\left(U\right)<\frac{H\left(U\right)}{{\log }_{2}D}+1$

где:

• $U$ — некоторый источник сообщений, а также множество всех его сообщений $u_1,u_2,...,u_K$
• $w_1,w_2,...,w_K$ — длины сообщений источника после кодирования
• $E_{U}w\left(U\right)$ — средняя длина сообщений
• $H\left(U\right)$ — энтропия источника
• $D$ — количество букв в алфавите кодирования (например, 2 для двоичного алфавита, 33 — для кодирования заглавными русскими буквами и т. д.)

В качестве доказательства теоремы исследуются характеристики кода Шеннона-Фано. Данный код удовлетворяет условиям теоремы, и он обладает указанными свойствами.

Обратная теорема

Обратная теорема ограничивает максимальную степень сжатия, достигаемую с помощью кодирования без потерь. В применении к побуквенному кодированию, описывает ограничение на среднюю длину кодового слова для любого разделимого кода.

Для любого разделимого кода с длинами $w_1,w_2,...,w_K$ средняя длина сообщений больше или равна энтропии источника $U$, нормированный на двоичный логарифм от числа букв $D$ в алфавите кодера:

$\frac{H\left(U\right)}{{\log }_{2}D}\le E_{U}w\left(U\right)$

Литература

• Шаблон:Source