Статистические коды

Учитывая статистические свойства источника сообщений, можно минимизировать среднюю длину кодовых сообщений. Это можно осуществить с помощью, так называемых, статистических кодов. Такие коды являются неравномерными. Длина кодовой комбинации статистического кода зависит от вероятности появления сообщения, соответствующего этой кодовой комбинации.. Сообщениям с большими вероятностями соответствуют более короткие кодовые комбинации, а а сообщениям с меньшими вероятностями – более длинные. В результате сокращается средняя длина кодовой комбинации.

По количеству переносимой информации данные коды приближается к оптимальному коду, т.е. на каждый элемент этого кода приходится около 1 бита информации. А избыточность таких кодов стремится к нулю (но не равна нулю). Поэтому такое кодирование часто называют экономным, а сами коды называют экономными или квазиоптимальными (т.е. подобные оптимальным).

Средняя длина кодовой комбинации определяется выражением

,

где M - количество кодовых комбинаций, - длина i -ой кодовой комбинации, - вероятность появления i -ой кодовой комбинации.

Количество информации приходящейся на один элемент кода определяется выражением

,

где - средняя длина кодовой комбинации, - энтропия источника сообщений.

Согласно теореме Шеннона об оптимальном кодировании в каналах без помех средняя длина кодовой комбинации статистического кода не может быть меньше величины n_min, которая определяется выражением

,

где K - объем алфавита кода, - некоторая малая величина.

Это минимально возможное значение интересно при сравнении эффективности кодов, полученных по различным алгоритмам. Чем ближе средняя длина кодовой комбинации кода к значению n_min, тем эффективнее код. При решении практических задач значением можно пренебречь и пользоваться приближенной формулой.

.

Избыточность статистического кода определяется выражением

.

Рассмотрим алгоритмы построения двух квазиоптимальных кодов.

Дата добавления: 2015-07-01