Кодирование сообщений словами переменной длины

 

Пусть имеется множество передаваемых сообщений S={sj}, i=1,…,m, причем известна вероятность pj появления каждого из сообщений на входе устройства кодирования (при соблюдении условия нормировки ). Пусть также имеется множество двоичных кодовых слов переменной длины, используемых для кодирования этих сообщений K={kj},причем lj =l(kj) –длина кодового слова kj, соответствующего сообщению sj.

Тогда в качестве критерия эффективности кодирования сообщений множества S кодовыми словами множества K выступает величина λkS , называемая средней длиной кодового слова и определяемая следующим образом:

(1.3)

Рассмотрим пример. Пусть множество сообщений S={s1, s2, … , s10}характеризуется вероятностями появления, определяемыми по следующей формуле:

(1.4)

(Можно проверить, что условие нормировки при этом соблюдается).

Воспользуемся для кодирования данных сообщений кодовыми словами рассмотренного выше префиксного кода так, как это показано в таблице 1.1.

Таблица 1.1

Сообщение sj Вероятность pj Кодовое слово kj Длина кодового слова lj
s1 1/55
s2 2/55
s3 3/55
s4 4/55
s5 5/55
s6 6/55
s7 7/55
s8 8/55
s9 9/55
s10 10/55

 

 

По формуле (4.3) получим:

(бит/сообщение)

Если бы мы закодировали сообщения равномерным кодом, то, согласно формуле (1.1) нам потребовались бы кодовые слова длины (бит/сообщение), т.е. кодирование словами переменной длины оказывается более эффективным.

Заметим, что в приведенном примере кодовые слова ставились в соответствие сообщениям таким образом, что их длина оказывалась обратно пропорциональной вероятности появления каждого из сообщений. Тем самым обеспечивалось наиболее экономное кодирование, поскольку при данном способе распределения значение величины λkS минимально.

Как же выбирать кодовые слова в общем случае, чтобы для заданных вероятностей p1, p2, … , pmобеспечить по возможности меньшую среднюю длину кодового слова, т.е. λkS → min?

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

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

 

<== предыдущая лекция | следующая лекция ==>
Сжатие на основе статистических свойств данных и неравномерные коды | Процедура Шеннона-Фано


Дата добавления: 2017-11-04; просмотров: 14; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию, введите в поисковое поле ключевые слова и изучайте нужную вам информацию.

Поделитесь с друзьями:

Если вам понравился данный ресурс вы можете рассказать о нем друзьям. Сделать это можно через соц. кнопки выше.
helpiks.org - Хелпикс.Орг - 2014-2017 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.005 сек.