Теория передачи сигналов (2 часть)

Алгоритм статистического кодирования Хаффмана

Рассмотрим на предыдущем примере. Сообщение:

«аттестат».

ai	p(ai)		Разбиения				Код	qi
т	4/8	4/8		4/8		1	1	1
а	2/8	2/8		4/8			00	2
е	1/8	2/8					010	3
с	1/8						011	3

21

Алгоритм статистического кодирования Хаффмана

		1
	0	1
	4/8	4/8
0	1	т
2/8		2/8

а	0	1
	1/8	1/8

е с

Если вероятности равны, то значения двоичных разрядов записываем произвольно. Например, слева 0, а справа 1.

На основании графа заполняется последний столбец

предыдущей таблицы.

22

Алгоритм статистического кодирования Хаффмана

Сообщение будет иметь вид:

А	Т	Т	Е	С	Т	А	Т
00	1	1	010	011	1	00	1

	Длина двоичного сообщения с	хф=14 бит.
	неравномерным кодом Хаффмана:

Сообщение стало на 12.5 % короче, чем при кодировании равномерным кодом.

	рав − хф	=	16 − 14		= 0.125	→ 12.5%
	рав		16
Ранее вычисленная избыточность =0.125						устранена.

23

Алгоритм статистического кодирования Хаффмана

Средняя длина одной буквы исходного сообщения после кодирования неравномерным кодом:

	=	бит/букву
ср

=1

qi – количество разрядов использованных для кодирования i-го символа (т→1→qт=1; а→00→qа=2; е→010→qе=3; с→011→qс=3).

ср = т т + а а + е е + с сср = 48 1 + 28 2 + 18 3 + 18 3 = 1.75 бит/букву

На одну букву алфавита источника, после кодирования неравномерным кодом Хаффмана, приходится в среднем 1,75

двоичных символа.	24

Алгоритм статистического кодирования Хаффмана

Остаточная избыточность после кодирования:

		=	ср −		=	1.75 − 1.75	= 0.
ост			ср	1.75
С помощью кода Хаффмана, как и с помощью кода
Шеннона-Фано,	удалось			полностью устранить избыточность

исходного буквенного сообщения.

25

Декодирование сообщения с неравномерным двоичным кодом

00110100111001

Считывание одного символа

00→А; 1→Т; 010→Е; 011→С

совпадает Нет

Да

А..

Двоичное сообщение (код Хаффмана)

Таблица соответствия символов буквам

Проверка совпадения с таблицей

Декодирование одной буквы

АТТЕСТАТ	Буквенное сообщение

26

Декодирование сообщения с неравномерным двоичным кодом

	А	Т	Т	Е	С	Т	А	Т	Исходное буквенное
									сообщение
	00110100111001								Двоичный код
	10110100111001								Двоичный код с ошибкой
									при декодировании

Т	С	Е	С	Т	А	Т	Декодированное сообщение

Ошибка в одном разряде приводит к неправильному приёму группы символов, или всего сообщения.

А	Т	Т	Е	С	Т	А	Т
00	1	1	010	011	1	00	1

27

Статистическое кодирование источника при группировании символов

Больший эффект от статистического кодирования можно получить, если кодировать не отдельные буквы, а многобуквенные элементы сообщения, которые образуют вторичный алфавит источника.

	,		2	…	1	, , …		,
	1					1 2	2
где: a –	символы (буквы) первичного алфавита,						b –	символы
(буквы)	вторичного	алфавита,				m1 – количество		символов

первичного алфавита, m2 – количество символов вторичного алфавита.

				Выход
				источника
Первичный		Вторичный
алфавит		алфавит

28

Статистическое кодирование источника при группировании символов

Рассмотрим процедуру статистического кодирования сообщений, образованных с помощью алфавита, состоящего

всего из двух букв а1 и а2 с вероятностями появления соответственно:

Р(а1) = 0.9; P(а2) = 0.1

Так как вероятности не равны, то последовательность из таких букв будет обладать избыточностью. Однако при побуквенном кодировании (а1→«0», а2→«1») мы никакого эффекта не получим. На передачу каждой буквы в этом случае требуется символ либо «1», либо «0».

29

Статистическое кодирование источника при группировании символов

Энтропия и средняя длина букв:

= − ( 1) log2 ( 1) − ( 2) log2 2

= −0.9 log2 0.9 − 0.1 log2 0.1 = 0.47 бит/букву

= log2 1 = log2 2 = 1ср = 1 1 + 2 2

ср = 0.9 ∙ 1 + 0.1 ∙ 1 = 1 бит/букву

Избыточность:

= − = 1 − 0.47 = 0.53 − или 53%.

1

30