3. Коды без разделителя. Условие Фано

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

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

Наиболее простыми и употребимыми кодами без разделителя являются так называемые префиксные коды, которые удовлетворяют следующему условию –условию Фано:Сообщение, закодированное с использованием неравномерного кода может быть однозначно декодировано, если никакой из кодов в данном сообщении не совпадает с префиксом^* (началом) какого-либо иного более длинного кода.

Например, если имеется код 110, то уже не могут использоваться коды 1, 11, 1101, 110101 и пр.

Если условие Фано выполняется, то при прочтении (декодировании, расшифровке) закодированного сообщения путем сопоставления с таблицей кодов всегда можно точно указать, где заканчивается один код и начинается другой.

Пример 1. Являются ли коды, представленные втабл. 4,префиксными? Коды, представленные в табл. 4, не являются префиксными. См., например, коды букв «О» и «Е», «А» и «Н», «С» и «М», «Д» и «Ч».

Пример 2. Имеется таблица префиксных кодов (табл. 6). Требуется декодировать следующее сообщение, закодированное с использованием этой приведенной кодовой таблицы:

00100010000111010101110000110

Табл. 6. Таблица префиксных кодов

А	Л	М	Р	У	Ы
10	010	00	11	0110	0111

Декодирование производится циклическим повторением следующих действий:

1. «Отрезать» от текущего сообщения крайний слева символ, присоединить его справа к рабочему (текущему) кодовому слову;

2. сравнить текущее кодовое слово с кодовой таблицей; если совпадения нет, вернуться к пункту 1.

3. С помощью кодовой таблицы текущему кодовому слову поставить в соответствие символ первичного алфавита;

4. Проверить, имеются ли еще знаки в закодированном сообщении; если да, то перейти к пункту 1.

Применение данного алгоритма к предложенному выше закодированному сообщению дает:

00100010000111010101110000110

00	10	00	10	00	0111	010	10	11	10	00	0110
м	а	м	а	м	ы	л	а	р	а	м	у

Таким образом, доведя процедуру декодирования до конца, можно получить сообщение: «мама мыла раму».

Таким образом, использование префиксного кодирования позволяет делать сообщение более коротким, поскольку нет необходимости передавать разделители знаков.

Однако условие Фано не устанавливает конкретного способа формирования префиксного кода, оставляя поле для деятельности по разработке наилучшего из возможных префиксных кодов.

4. Префиксный код Шеннона–Фано

Рассмотрим вариант кодирования, который был предложен в 1948 – 1949 гг. независимо К. Шенноном и Р. Фано.

Рассмотрим схему кодирования (как она строится) Шеннона–Фано на следующем примере.

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

Разделим знаки на две группы так, чтобы суммы вероятностей в каждой из этих двух групп были бы приблизительно равными. При этом в 1-ю группу попадут и, а остальные – во 2-ю группу. Знакампервой группы присвоим первый слева разряд их кодов «0», а первым слева разрядом кодов символов второй группы пусть будет «1».

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

Вся эта процедура может быть схематически изображена в табл 7.

Табл. 7. Построение кода Шеннона-Фано

Знак		Разряды кода				Код
		1-й	2-й	3-й	4-й
	0.30	0	0			00
	0.20	0	1			01
	0.20	1	0			10
	0.15	1	1	0		110
	0.10	1	1	1	0	1110
	0.05	1	1	1	1	1111

Видно, что построенные коды знаков удовлетворяют условию Фано, следовательно, такое кодирование является префиксным.

Найдем среднюю длину полученного кода по формуле

,

где – число разрядов (символов) в коде, соответсвующем символу.

Из таблицы видно, что ,,.

Таким образом, получаем:

.

Таким образом, для кодирования одного символа первичного алфавитапотребовалось в среднем 2.45 символов вторичного (двоичного) алфавита.

Определим среднее количество информации, приходящееся на знак первичного алфавита в первом приближении (с учетом различной вероятности появления этих знаков в сообщениях). Применим формулу Шеннона:

.

Найдем избыточность полученного двоичного кода:

,

то есть избыточность – около 2.5.

Выясним, является ли полученный код оптимальным. Нулей в полученных кодах – 6 штук, а единиц – 11 штук. Таким образом, вероятности появления 0 и 1 далеко не одинаковы. Следовательно, полученный код нельзя считать оптимальным.