Теоремы Шеннона для источника общего вида | это... Что такое Теоремы Шеннона для источника общего вида? (original) (raw)

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

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

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

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

E_U w\left( U \right) < \frac{{H\left( U \right)}}{{\log _2 D}} + 1

где:

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

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

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

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

\frac{{H\left( U \right)}}{{\log _2 D}} \le E_U w\left( U \right)

Литература