Теоремы Шеннона для источника без памяти связывают энтропию источника и возможность сжатия кодированием с потерями и последующим неоднозначным декодированием.
Прямая теорема показывает, что с помощью кодирования с потерями возможно достичь степени сжатия
,
сколь угодно близкой к энтропии источника, но всё же больше последней. Обратная показывает, что лучший результат не достижим.
Формулировка теорем
Пусть заданы:
— некоторый источник сообщений, а также множество всех его сообщений
— множество всех входных последовательностей длины
, которое разделяется на:
— множество входных последовательностей однозначного декодирования
— множество входных последовательностей неоднозначного декодирования
— количество букв в алфавите кодера (в сообщениях после кодирования)
— длина сообщений после кодирования
- Прямая теорема
Для источника без памяти
с энтропией
и любого
существует последовательность множеств однозначного декодирования
мощности
такая, что вероятность множества неоднозначного декодирования стремится к нулю
при увеличении длины блока
. Другими словами, сжатие возможно.
- Обратная теорема
Пусть задан источник без памяти
с энтропией
и любой
. Для любой последовательности множеств однозначного декодирования
мощности
вероятность множества неоднозначного декодирования стремится к единице:
при увеличении длины блока
. Другими словами, сжатие невозможно.
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .