Основные определения и положения

 

Пусть X – ансамбль, содержащий L сообщений, а – некоторое множество, состоящее из элементов. Предположим, что каждое из сообщений X необходимо отобразить в некоторую последовательность элементов множества (см. рис. 2.1). Подобная задача называется кодированием сообщений (состояний) источника или коротко кодированием источника. Множество при этом называется алфавитом кода, а его отдельные элементы – кодовыми символами. Каждая из полученных последовательностей, отображающих сообщения, называется кодовым словом (кодовым вектором), а полное множество слов – кодом (источника). Будем далее полагать , т.е. рассматривать двоичные коды. Обобщение результатов на случай ( ‑ичные коды) не составляет труда.

Если бы задача кодирования источника не сопровождалась никакими оговорками, ее решение носило бы тривиальный характер. Действительно, выбрав k из условия , можно было бы использовать в качестве взаимно-однозначных кодовых слов различные двоичные комбинации длины k бит. Однако задача становится весьма содержательной с появлением требования экономности кодирования, понимаемого как минимизация числа кодовых символов, затрачиваемых на отображение сообщения.

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

 

2.2. Префиксные коды. Неравенство Крафта. Средняя длина кодового слова.

 

Таблица 2.1. X 1-й способ 2-й способ x 1     x 2     x 3     x 4

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

Пример 2.2.1. Пусть имеется некоторый дискретный источник X, генерирующий за одно использование одно из сообщений. Два варианта неравномерного кодирования такого источника представлены в табл. 2.1.

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

Простейшим путем преодоления этого затруднения является введение специального разделительного символа, который в технической литературе называют «запятой». Коды, содержащие такой специальный символ, называют «кодами с запятой». Понятно, что введение запятой означает добавление еще одного символа в кодовый алфавит, так что ‑ичный код с запятой является частным случаем (q +1) ‑ичного произвольного неравномерного кода. Очевидно, грамотнее решать задачу экономного кодирования не навязыванием заранее какому-то кодовому символу роль запятой, стремясь вместо этого наилучшим образом распорядиться всем алфавитом. Поэтому далее обратимся к кодам «без запятой», не содержащим специального разделительного символа.

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

Неопределенность начала слов в последнем примере устраняется тем, что никакое кодовое слово не начинается с комбинации (префикса), совпадающей с другим словом.

Определение 2.2.1. Коды, в которых ни одно слово не является префиксом другого, называются префиксными кодами.

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

Необходимое и достаточное условие существования префиксных кодов формулируется следующей теоремой.