- Прямая теорема Шеннона для канала без помех
-
- Не следует путать с другими теоремами Шеннона.
Теоремы Шеннона для источника общего вида описывают возможности кодирования источника общего вида с помощью разделимых кодов. Другими словами, описываются максимально достижимые возможности кодирования без потерь.
Прямая теорема
В применении к побуквенному кодированию прямая теорема может быть сформулирована следующим образом:
Существует префиксный, то есть разделимый код, для которого средняя длина сообщений отличается от нормированной энтропии не более, чем на единицу:
где:
- U — некоторый источник сообщений, а также множество всех его сообщений u1,u2,...,uK
- w1,w2,...,wK — длины сообщений истоника после кодирования
— средняя длина сообщений
— энтропия источника
- D — количество букв в алфавите кодирования (например, 2 для двоичного алфавита, 33 — для кодирования заглавными русскими буквами и т. д.)
В качестве доказательства теоремы исследуются характеристики кода Шеннона-Фано. Данный код удовлетворяет условиям теоремы, и он обладает указанными свойствами.
Обратная теорема
Обратная теорема ограничивает максимальную степень сжатия, достигаемую с помощью кодирования без потерь. В применении к побуквенному кодированию, описывает ограничение на среднюю длину кодового слова для любого разделимого кода.
Для любого разделимого кода с длинами w1,w2,...,wK средняя длина сообщений больше или равна энтропии источника U, нормированный на двоичный логарифм от числа букв D в алфавите кодера:
Литература
- Габидулин, Э. М., Пилипчук, Н. И. §3.4 Теоремы Шеннона для источника // Лекции по теории информации. — М.: МФТИ, 2007. — С. 49-52. — 214 с. — ISBN 5-7417-0197-3
Wikimedia Foundation. 2010.