9.2. Префексные коды

Префиксные коды это такие коды, в которых ни одна более короткая кодовая комбинация не является началом более длиной кодовой комбинации (второе условие обратимости кодов). Это позволяет однозначно декодировать кодовую комбинацию без использования разделителей между ними.

Для построения префиксных кодов используется кодовое дерево. Каждому листу дерева, расположенном на j-ом уровне соответствует кодовая комбинация с весом равным p_j= D^-k,. где D количество потомком каждой вершины дерева, не являющейся листом.

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

Оптимальным кодированием считается такой код, который обеспечивает минимальное время передачи, т. е. минимальный объем передаваемых сообщений.

9.3.1. Код Шеннона -Фано

Рассмотрим пример кодирования с использованием кода Шеннона-Фано.

Таблица 9.1

Входное слово	a	b	c	d	e	f	g	h	Всего
Количество передаваемых слов	20	20	10	10	5	5	5	5	80
Коды	000	001	010	011	100	101	110	111
Длина кодовой комбинации	3	3	3	3	3	3	3	3
Объем передачи данных	60	60	30	30	15	15	15	15	240 бит

Таблица 9.2

Входное слово	Количество передаваемых слов					Коды слов
a	20	0	0			00
b	20		1			01
c	10	1	0	0		100
d	10			1		101
e	5		1	0	0	1100
f	5				1	1101
g	5			1	0	1110
h	5				1	1111

Таблица 9.3

Входное слово	a	b	c	d	e	f	g	h	Всего
Количество передаваемых слов	20	20	10	10	5	5	5	5	80
Коды	00	01	100	101	1100	1101	1110	1111
Длина кодовой комбинации	2	2	3	3	4	4	4	4
Объем передачи данных	40	40	30	30	20	20	20	20	180 бит