Теоремы Шеннона для источника без памяти

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

,

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

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

[править | править код]

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

  •  — некоторый источник сообщений, а также множество всех его сообщений
  •  — множество всех входных последовательностей длины , которое разделяется на:
    •  — множество входных последовательностей однозначного декодирования
    •  — множество входных последовательностей неоднозначного декодирования
  •  — количество букв в алфавите кодера (в сообщениях после кодирования)
  •  — длина сообщений после кодирования
Прямая теорема

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

Обратная теорема

Пусть задан источник без памяти с энтропией и любой . Для любой последовательности множеств однозначного декодирования мощности вероятность множества неоднозначного декодирования стремится к единице: при увеличении длины блока . Другими словами, сжатие невозможно.

Литература

[править | править код]