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

Не следует путать с другими теоремами Шеннона.

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

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

$\frac{N}{L} \approx \frac{{H\left( U \right)\left( {1 + \varepsilon } \right)}}{{\log _2 D}}$

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

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

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

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

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

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

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

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

Литература

• Габидулин, Э. М., Пилипчук, Н. И. Глава 6. Кодирование с потерями // Лекции по теории информации. — М.: МФТИ, 2007. — С. 89-93. — 214 с. — ISBN 5-7417-0197-3