Полная версия

Главная arrow Информатика arrow Теоретическая информатика arrow
Избыточность информации

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

Минимизация средней длины кодового слова.

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

,

где li – длина кодового слова для кодирования i-го сообщения

pi - вероятность появления i-го сообщения.

Возникает вопрос, как выбрать кодовые слова, чтобы для заданных вероятностей p1,p2,….. pN обеспечить по возможности меньшую среднюю длину кодового слова?

Для ответа на этот вопрос учтем тот очевидный факт, что равномерный код, всем кодовым комбинациям которого соответствуют равновероятные сообщения, является оптимальным, т.е. имеет минимальную длину кодового слова. На каждом шаге двоичного кодирования производится разбиение множества сообщений на два подмножества, причем одному из них приписывается единица, а другому – ноль. Таким образом, на каждом шаге производится кодирование подмножеств равномерным кодом длиной в I двоичный знак. Отсюда следует принцип: нужно стремиться так производить разбиение на два подмножества, чтобы суммарные вероятности подмножеств были одинаковыми (или как можно более близкими друг к другу).

 
<<   СОДЕРЖАНИЕ   >>

Похожие темы