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

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

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

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

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

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

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

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

• U — некоторый источник сообщений, а также множество всех его сообщений u₁,u₂,...,u_K
• Ω — множество всех входных последовательностей длины 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