Теоремы Шеннона для источника без памяти | это... Что такое Теоремы Шеннона для источника без памяти? (original) (raw)

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

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

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

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

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

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

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

Для источника без памяти 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 . Другими словами, сжатие невозможно.

Литература