Теоремы Шеннона для источника без памяти (Mykjybd Oyuukug ;lx nvmkcuntg Qy[ hgbxmn)

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

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

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

,

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

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

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

$U$ — некоторый источник сообщений, а также множество всех его сообщений $u_{1},u_{2},...,u_{K}$
$\Omega$ $\Omega$ — множество всех входных последовательностей длины $L$ $L$ , которое разделяется на:
- $M_{L}$ — множество входных последовательностей однозначного декодирования
- $M_{L}^{C}$ — множество входных последовательностей неоднозначного декодирования
$D$ — количество букв в алфавите кодера (в сообщениях после кодирования)
$N$ — длина сообщений после кодирования

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

Для источника без памяти $U$ с энтропией $H\left(U\right)$ и любого $\varepsilon >0$ существует последовательность множеств однозначного декодирования $M_{L}$ мощности $2^{L\left({1+\varepsilon }\right)H\left(U\right)}$ такая, что вероятность множества неоднозначного декодирования стремится к нулю $P\left({M_{L}^{C}}\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_{L}^{C}}\right)\to 1$ при увеличении длины блока $L\to \infty$ . Другими словами, сжатие невозможно.

Литература

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