Теоремы Шеннона для источника без памяти

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

Прямая теорема показывает, что с помощью кодирования с потерями возможно достичь степени сжатия

$\frac{N}{L}\approx \frac{H\left(U\right)\left(1+\epsilon \right)}{{\log }_{2}D}$,

сколь угодно близкой к энтропии источника, но всё же больше последней. Обратная показывает, что лучший результат не достижим.

Формулировка теорем

Пусть заданы:

• $U$ — некоторый источник сообщений, а также множество всех его сообщений $u_1,u_2,...,u_K$
• $\mathrm{\Omega }$ — множество всех входных последовательностей длины $L$, которое разделяется на:
  • $M_L$ — множество входных последовательностей однозначного декодирования
  • $M_L^C$ — множество входных последовательностей неоднозначного декодирования
• $D$ — количество букв в алфавите кодера (в сообщениях после кодирования)
• $N$ — длина сообщений после кодирования

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

Для источника без памяти $U$ с энтропией $H\left(U\right)$ и любого $\epsilon >0$ существует последовательность множеств однозначного декодирования $M_L$ мощности $2^{L\left(1+\epsilon \right)H\left(U\right)}$ такая, что вероятность множества неоднозначного декодирования стремится к нулю $P\left(M_L^C\right)\to 0$ при увеличении длины блока $L\to \mathrm{\infty }$. Другими словами, сжатие возможно.

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

Пусть задан источник без памяти $U$ с энтропией $H\left(U\right)$ и любой ${\epsilon }_1>0$. Для любой последовательности множеств однозначного декодирования $M_L$ мощности $2^{L\left(1-{\epsilon }_1\right)H\left(U\right)}$ вероятность множества неоднозначного декодирования стремится к единице: $P\left(M_L^C\right)\to 1$ при увеличении длины блока $L\to \mathrm{\infty }$. Другими словами, сжатие невозможно.

Литература

• Шаблон:Source