WikiSort.ru - Не сортированное

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

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

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

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

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

где:

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

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

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

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

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

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

Литература

• Габидулин Э. М., Пилипчук Н. И. §3.4 Теоремы Шеннона для источника // Лекции по теории информации — МФТИ, 2007. — С. 49–52. — 214 с. — ISBN 978-5-7417-0197-3
  <a href='https://wikidata.org/wiki/Track:Q4130888'></a><a href='https://wikidata.org/wiki/Track:Q27473237'></a><a href='https://wikidata.org/wiki/Track:Q27473383'></a>