Теоремы Шеннона для источника без памяти | это... Что такое Теоремы Шеннона для источника без памяти? (original) (raw)
Теоремы Шеннона для источника без памяти связывают энтропию источника и возможность сжатия кодированием с потерями и последующим неоднозначным декодированием.
Прямая теорема показывает, что с помощью кодирования с потерями возможно достичь степени сжатия
сколь угодно близкой к энтропии источника, но всё же больше последней. Обратная показывает, что лучший результат не достижим.
Формулировка теорем
Пусть заданы:
Прямая теорема
Для источника без памяти с энтропией и любого существует последовательность множеств однозначного декодирования мощности такая, что вероятность множества неоднозначного декодирования стремится к нулю при увеличении длины блока . Другими словами, сжатие возможно.
Обратная теорема
Пусть задан источник без памяти с энтропией и любой . Для любой последовательности множеств однозначного декодирования мощности вероятность множества неоднозначного декодирования стремится к единице: при увеличении длины блока . Другими словами, сжатие невозможно.
Литература
- Габидулин, Э. М., Пилипчук, Н. И. Глава 6. Кодирование с потерями // Лекции по теории информации. — М.: МФТИ, 2007. — С. 89-93. — 214 с. — ISBN 5-7417-0197-3