Теоремы Шеннона для источника общего вида
Теоремы Шеннона для источника общего вида описывают возможности кодирования источника общего вида с помощью разделимых кодов. Другими словами, описываются максимально достижимые возможности кодирования без потерь.
Прямая теорема
В применении к побуквенному кодированию прямая теорема может быть сформулирована следующим образом:
Существует префиксный, то есть разделимый код, для которого средняя длина сообщений отличается от нормированной энтропии не более, чем на единицу:
- [math]\displaystyle{ E_U w\left( U \right) \lt \frac{{H\left( U \right)}}{{\log _2 D}} + 1 }[/math]
где:
- [math]\displaystyle{ U }[/math] — некоторый источник сообщений, а также множество всех его сообщений [math]\displaystyle{ u_1 ,u_2 ,...,u_K }[/math]
- [math]\displaystyle{ w_1 ,w_2 ,...,w_K }[/math] — длины сообщений источника после кодирования
- [math]\displaystyle{ E_U w\left( U \right) }[/math] — средняя длина сообщений
- [math]\displaystyle{ H\left( U \right) }[/math] — энтропия источника
- [math]\displaystyle{ D }[/math] — количество букв в алфавите кодирования (например, 2 для двоичного алфавита, 33 — для кодирования заглавными русскими буквами и т. д.)
В качестве доказательства теоремы исследуются характеристики кода Шеннона-Фано. Данный код удовлетворяет условиям теоремы, и он обладает указанными свойствами.
Обратная теорема
Обратная теорема ограничивает максимальную степень сжатия, достигаемую с помощью кодирования без потерь. В применении к побуквенному кодированию, описывает ограничение на среднюю длину кодового слова для любого разделимого кода.
Для любого разделимого кода с длинами [math]\displaystyle{ w_1 ,w_2 ,...,w_K }[/math] средняя длина сообщений больше или равна энтропии источника [math]\displaystyle{ U }[/math], нормированный на двоичный логарифм от числа букв [math]\displaystyle{ D }[/math] в алфавите кодера:
- [math]\displaystyle{ \frac{{H\left( U \right)}}{{\log _2 D}} \le E_U w\left( U \right) }[/math]