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