Сообщения дискретного источника X описываются матрицей. Закодировать сообщения равномерным двоичным кодом и заданным эффективным кодом – кодом Хаффмена

Сначала кодируем сообщения кодом Хаффмена:
Сообщения источника ранжируются в порядке убывания вероятностей.
Группируются два сообщения и вычисляется их суммарная вероятность. При этом два сообщения объединяются в одно.
(N-1) сообщения ранжируются в порядке убывания вероятностей и повторяется циклически п.2. Процесс продолжается до тех пор, пока суммарная вероятность не станет равна единице. Результатом указанных процедур является двоичное кодовое дерево, ветви которого кодируются нулем и единицей, а кодовая последовательность каждого сообщения образуется в результате движения от основания дерева к вершине .
Получаем следующий результат (рис. 2, табл. 1).
xi
p(xi)
x2
0,3
x6
0,2
x7
0,2
x1
0,1
x5
0,1
x3
0,05
x4
0,05
1
0,1
1
0
1
0
1
0
0,2
0,3
0
1
1
0
0,5
0,5
1
0
xi
p(xi)
x2
0,3
x6
0,2
x7
0,2
x1
0,1
x5
0,1
x3
0,05
x4
0,05
1
0,1
1
0
1
0
1
0
0,2
0,3
0
1
1
0
0,5
0,5
1
0
Рисунок 2 – Кодирование методом Хаффмена
Таблица 1 – Кодирование методом Хаффмена
xi p(xi) ni
y
x2 0,3 2 01
x6 0,2 2 00
x7 0,2 3 101
x1 0,1 3 100
x5 0,1 3 111
x3 0,05 4 1101
x4 0,05 4 1100
Средняя длина кодового слова:
Энтропия:
Избыточность источника X определяется как:

Избыточность кода Хаффмена равна:
.
При равномерном кодирования длина кодового слова определяется из соотношения:
.
Получаем (табл