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


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

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

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

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

E U w ( U ) < H ( U ) log 2 ⁡ D + 1 {displaystyle E_{U}wleft(U ight)<{frac {Hleft(U ight)}{log _{2}D}}+1}

где:

  • U {displaystyle U} — некоторый источник сообщений, а также множество всех его сообщений u 1 , u 2 , . . . , u K {displaystyle u_{1},u_{2},...,u_{K}}
  • w 1 , w 2 , . . . , w K {displaystyle w_{1},w_{2},...,w_{K}} — длины сообщений источника после кодирования
  • E U w ( U ) {displaystyle E_{U}wleft(U ight)} — средняя длина сообщений
  • H ( U ) {displaystyle Hleft(U ight)} — энтропия источника
  • D {displaystyle D} — количество букв в алфавите кодирования (например, 2 для двоичного алфавита, 33 — для кодирования заглавными русскими буквами и т. д.)

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

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

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

Для любого разделимого кода с длинами w 1 , w 2 , . . . , w K {displaystyle w_{1},w_{2},...,w_{K}} средняя длина сообщений больше или равна энтропии источника U {displaystyle U} , нормированный на двоичный логарифм от числа букв D {displaystyle D} в алфавите кодера:

H ( U ) log 2 ⁡ D ≤ E U w ( U ) {displaystyle {frac {Hleft(U ight)}{log _{2}D}}leq E_{U}wleft(U ight)}

  • Троичный код
  • Теорема Дирихле о рядах Фурье
  • Теорема Колмогорова — Арнольда
  • Код
  • Структурная теорема для конечнопорождённых модулей над областями главных идеалов

  •  

    • Яндекс.Метрика
    • Индекс цитирования