Page 31 - 4522
P. 31
середня кількість двійкових кодових сигналів на один символ
повідомлення наближатиметься як завгодно близько до
ентропії джерела повідомлень.
Метод ефективного кодування розглянемо на прикладі
коду Хаффмана. Код Хаффмана (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