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