Page 31 - 4522

середня кількість двійкових кодових сигналів на один символ
повідомлення наближатиметься як завгодно близько до
ентропії джерела повідомлень.
Метод ефективного кодування розглянемо на прикладі
коду Хаффмана. Код Хаффмана (1953) має такий алгоритм:
1. Розташувати символи алфавіту джерела у порядку
спадання (не зростання) їх ймовірностей.
2. Додати останні дві ймовірності і переписати
стовпчик ймовірностей у порядку спадання.
3. Повторити пункт 2 (N-1) раз, N - число символів
початкового алфавіту (табл. 4.1).
Таблиця 4.1 – Принцип побудови коду Хаффмана
A 0.25 0.25 0.25 0.31 0.44 0.56 1
B 0.23 0.23 0.23 0.25 0.31 0.44
C 0.16 0.16 0.21 0.23 0.25
D 0.15 0.15 0.16 0.21
E 0.10 0.11 0.15
F 0.09 0.10
G 0.02

4. За одержаною таблицею, рухаючись справа наліво,
побудувати кодове дерево і словник.
Приклад побудови коду Хаффмана приведено на рис.
4.1 для приведеного початкового алфавіту.

Рисунок 4.1 – Приклад побудови кодового дерева Хаффмана

30