Разработка кода сообщения

Для построения оптимального кода на базе кодового дерева необходимо учитывать следующее:

1) символ ансамбля с наибольшей вероятностью появления должен находиться в узле наименьшего порядка.

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

3) если выбран узел порядка i, то все узлы более высокого порядка, связанные с ним, не могут быть использованы для кодирования.

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

При укрупнении сообщения, т.е. при переходе от улов порядка i к i – 1 количество символов, закодированных в узлах более высокого порядка, уменьшается. Однако в узлах самого высокого порядка количество закодированных символов m₀ должно лежать в пределах [2,k], где k – основание кода.

При выборе k используют следующую формулу:

M = 1 + (k – 1) + (m₀ – 1)                                        (5.9)

где М – общее количество символов в алфавите

  m₀ – количество закодированных символов

– целое число, которое подбирается таким образом, чтобы выполнялось условие:

                                                          (5.9)

где k – основание кода

Если найдено m₀, то оно определяет количество закодированных символов в узлах само высокого порядка. Все остальные узлы низких порядков полностью заполняются.

Требуется построить двоичный код Хаффмана. 

k = 2  m₀ = 2

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

Необходимо построить вспомогательную таблицу:

Таблица 5.3

Буква	аi	Pi		аi	n
		0.579	0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 1 0.056 1 1 1 1 1 1 1 0.579 0.421 0.23 0.191 0.319 0.124 0.144 0.106 0.101
		0.421
		0.319
пауза	а1	P1 = 0.26		а1 10	2
		0.23
		0.191
_	а2	P2 = 0.175		а2 000	3
		0.144
		0.124
		0.106
		0.101
О	а3	P3 = 0.09		а3 111	3
Е	а4	P4 = 0.072		а4 0100	4
Е	а5	P5 = 0.072		а5 1100	4
А	а6	P6 = 0.062		а6 0001	4
И	а7	P7 = 0.062		а7 1001	4
Н	а8	P8 = 0.053		а8 0101	4
Н	а9	P9 = 0.053		а9 1101	4
С	а10	P10 = 0.045		а10 0011	4
К	а11	P11 = 0.028		а11 01011	5
К	а12	P12 = 0.028		а12 11011	5

Таким образом, можно окончательно записать код Хаффмана для сообщения:

1000010101100110100010111001101110111110001001

Среднее количество разрядов, необходимого для передачи одного символа рассчитается по формуле (5.3):