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

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

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

(1.3)

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

(1.4)

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

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

Таблица 1.1

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

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

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

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

Как же выбирать кодовые слова в общем случае, чтобы для заданных вероятностей p₁, p₂, … , p_mобеспечить по возможности меньшую среднюю длину кодового слова, т.е. λ_k^S → min?

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

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