2.2. Оптимальные неравномерные двоичные коды

Описывается метод построения оптимальных однозначно декоди­руемых двоичных кодов (с минимальной средней длиной кодовых слов) для дискретных ансамблей {А,р(а)}.

В простом частном случае вероятности сообщений ансамбля мо­гут быть целыми отрицательными степенями числа 2: p(a_i) = 2^-di, i = 1 ,...,К. Доказано , что оптимальный двоичный однозначно декодируемый код в этом случае имеет среднюю длину кодовых словd(A) = Н(А). В таком коде сообщению а_i сопо­ставляется слово длины d_i= - logр(а_i).

Следующий метод построения такого кода известен как метод Шеннона-Фано:

1. Подразделить множество сообщений на два равновероятных подмножества, произвольным образом переименовать подмножества. Для всех сообщений из 1-го подмножества положить первый символ 0, для второго подмножества — 1.

2. Каждое из подмножеств рассматривать как некоторое новое множество сообщений. Выполнить наj-м шаге,j = 2,3,..., действия, указанные в п. 1, для определенияj-го символа кодовых слов. Счи­тать, что действия над данным подмножеством закончены, если оно содержит одно сообщение.

Кодирование методом Шеннона-Фано ансамбля из 9 сообщений с вероятностями 0,25; 0,125; 0,0625; 0,0625; 0,0625; 0,0625; 0,125; 0,125; 0,125 показано в табл. 2, в которой сделаны четыре последовательных шага кодирования в соответствии с указанном выше алгоритмом.

На рис. 3 представлено соответствующее кодовое дерево.

В общем случае, когда сообщения имеют произвольные вероятно­сти, рассматривается метод построения оптимального префиксного ко­да, называемый методом Хаффмена. Здесь предполагается, что сообщения в ансамбле упорядочены, так чтоp(a₁) ≥ р(а₂) ≥ ... ≥ р(а_к). В обосновании метода лежат три леммы.

1. В оптимальном коде слово, соответствующее наименее вероят­ному сообщению, имеет наибольшую длину.

Таблица 2.2

Сообщения	Вероятности	1-й шаг	2-й шаг	3-й шаг	4-й шаг	Кодовые слова
a1	0,25	I	I			00
a2	0,125		II	I		010
a3	0,0625			II	I	0110
a4	0,0625				II	0111
a5	0,0625	II	I II	I	I	1000
a6	0,0625				II	1001
a7	0,125			II		101
a8	0,125		II	I		110
a9	0,125			II		111

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

Далее рассматривается новый ансамбль , состоящий из К - 1 сообщений с вероятностями

Любой префиксный код для ансамбля можно превратить в пре­фиксный код для ансамбля А приписыванием к кодовому слову, коди­рующему сообщение символов 0, 1 для получения слов, кодиру­ющих сообщения Следующая лемма обосновывает после­довательную процедуру кодирования.

Рис. 2.2

3. Если оптимален однозначно декодируемый префиксный код для ансамбля , то оптимален полученный из него префиксный код для ансамбля А.

Таким образом, задача построения оптимального кода сводится к задаче построения оптимального кода для ансамбля, содержащего на одно сообщение меньше. В этом ансамбле снова можно выделить два наименее вероятных сообщения и, объединяя их, получить новый ан­самбль, содержащий теперь уже на два сообщения меньше, чем ис­ходный. В итоге мы приходим к ансамблю, содержащему всего два слова, кодируемых символами 0 и 1.

Рассмотрим на примере ансамбля из 9 сообщений с вероятностя­ми 0,2; 0,15; 0,15; 0,12; 0,1; 0,1; 0,08; 0,06; 0,04 кодирование методом Хаффмена. В табл. 3 показаны семь последовательных шагов, на ка­ждом из которых происходит образование нового ансамбля с помощью склеивания наименее вероятных сообщений предыдущего ансамбля.

Таблица 2.3

Сообщения	Вероятности	1	2	3	4	5	6	7	8	Кодовое слово
a1	0,20										10
a2	0,15										001
a3	0,15										010
a4	0,12										011
a5	0,10										110
a6	0,10										111
a7	0,08										0001
a8	0,06 0,04										00000
a9											00001

Рис. 2.3

Алгоритм кодирования отражает в таблице и кодовое дерево. На рис. 2.3 дается его более наглядное представление.

_{Средняя длина кодового слова} . Однозначно декодируемого кода с меньшей длиной не существует. При оптималь­ном кодировании минимальная длина кодового слова неравномерного кода равна энтропии источника сообщений, в данном случае равной