В этом параграфе приведены некоторые теоремы о свойствах побуквенного кодирования. Одной из основных задач теории информации является построение кодов для сообщений, порождаемых некоторым источником информации, для дальнейшей передачи уже закодированных сообщений по каналу связи. Очевидным требованием к кодированию сообщений источника является условие однозначного декодирования, т.е. после получения закодированного сообщения получатель должен иметь возможность прочитать исходное сообщение. В данной главе рассматривается задача построения однозначно декодируемых кодов без учета статистики источника информации, т.е. можно считать, что сообщения источника независимы и равновероятны.
Определение. Пусть известны алфавит источника информации и кодовый алфавит
. Кодирование сообщения, которое порождает источник информации, будем понимать как сопоставление кодовой последовательности всему сообщению в целом или как построение кода сообщения из кодов его частей (побуквенное кодирование).
Пример 3.1 Пусть ,
. Побуквенное кодирование символов источника
позволяет следующим образом закодировать сообщение
Пример 3.2 Азбука Морзе. Входной алфавит – английский. Наиболее часто встречающиеся буквы кодируются более короткими словами:
Определение. Побуквенное кодирование задается таблицей кодовых слов: – конечные последовательности в алфавите B.
Определение. Множество кодовых слов называется множеством элементарных кодов. Используя побуквенное кодирование, можно закодировать любое сообщение
следующим образом
,
т.е. общий код сообщения складывается из элементарных кодов символов входного алфавита.
Определение. Количество букв в слове (последовательности символов) называется длиной слова. (Обозначение
) Пустое слово, т.е. слово, не содержащее ни одного символа обозначается
. Если
, то
– начало (префикс) слова
, – окончание (постфикс) слова
.
Определение. Побуквенный код называется разделимым (или однозначно декодируемым), если любое сообщение из символов алфавита источника, закодированное этим кодом, может быть однозначно декодировано, т.е.
если , то
и при любых
.
При разделимом кодировании любое кодовое слово единственным образом разлагается на элементарные коды.
Пример 3.2.1 Код из примера 3.1 не является разделимым, поскольку кодовое слово 010010 может быть декодируемо двумя способами: или
.
Определение.Побуквенный код называется префиксным, если в его множестве кодовых слов ни одно слово не является началом другого, т.е. элементарный код одной буквы не является префиксом элементарного кода другой буквы.
Пример 3.2.2. Код из примера 3.1 не является префиксным, поскольку элементарный код буквы является префиксом элементарного кода буквы
.
Утверждение. Префиксный код является разделимым.
Доказательство (от противного). Пусть префиксный код не является разделимым. Тогда существует такая кодовая последовательность , что она представлена различными способами из элементарных кодов:
(побитовое представление одинаковое) и существует L такое, что при любом
следует
и при любом
,
, т.е. начало каждого из этих представлений имеет одинаковую последовательность элементарных кодов. Уберем эту часть. Тогда
, т.е. последовательности элементарных кодов разные и существует такой элементарный код
, что
или
, т.е.
– начало
, или наоборот. Получили противоречие с префиксностью кода.
Пример 3.2.3. Заметим, что разделимый код может быть не префиксным.
Пусть . Пример разделимого, но не префиксного кода:
Теорема (Крафт). Для того, чтобы существовал побуквенный двоичный префиксный код с длинами кодовых слов необходимо и достаточно, чтобы
Доказательство. Докажем необходимость. Пусть существует префиксный код с длинами. Рассмотрим полное двоичное дерево. Каждая вершина закодирована последовательностью нулей и единиц (как показано на рисунке).
Рисунок 2 Полное двоичное дерево с помеченными вершинами
В этом дереве выделим вершины, соответствующие кодовым словам. Тогда любые два поддерева, соответствующие кодовым вершинам дерева, не пересекаются, т.к. код префиксный. У i-того поддерева на r-том уровне – вершин. Всего вершин в поддереве
. Тогда
,
.
Докажем достаточность утверждения. Пусть существует набор длин кодовых слов такой, что . Рассмотрим полное двоичное дерево с помеченными вершинами. Пусть длины кодовых слов упорядочены по возрастанию
. Выберем в двоичном дереве вершину
на уровне
. Уберем поддерево с корнем в вершине
. В оставшемся дереве возьмем вершину
на уровне
и удалим поддерево с корнем в этой вершине и т.д. Последовательности, соответствующие вершинам
образуют префиксный код. Теорема доказана.
Пример 3.3.1. Построить префиксный код с длинами для алфавита
. Проверим неравенство Крафта для набора длин
Неравенство выполняется и, следовательно, префиксный код с таким набором длин кодовых слов существует. Рассмотрим полное двоичное дерево с помеченными вершинами и выберем вершины дерева, как описано выше в доказательстве теоремы Крафта. Тогда элементарные коды могут быть такими:
. (Возможен и другой выбор элементарных кодов). Нетрудно видеть, что полученный код является префиксным, поскольку ни одно кодовое слово не является префиксом другого кодового слова.
Рисунок 3 Построение префиксного кода с заданными длинами
Процесс декодирования может быть организован следующим образом. Просматриваем полученное сообщение, двигаясь по дереву. Если попадем в кодовую вершину, то выдаем соответствующую букву и возвращаемся в корень дерева и т.д.
Теорема Крафта, доказанная в предыдущем параграфе, может быть обобщена на случай разделимых кодов.
Теорема (МакМиллан). Для того чтобы существовал побуквенный двоичный разделимый код с длинами кодовых слов , необходимо и достаточно, чтобы
Доказательство.Покажем достаточность. Если выполнено неравенство для набора чисел , то по теореме Крафта существует префиксный код с длинами
и это код является разделимым.
Докажем необходимость утверждения. Рассмотрим тождество
Положим . Тогда тождество можно переписать следующим образом
где ,
– число всевозможных представлений числа j в виде суммы
. Сопоставим каждому представлению числа j в виде суммы последовательность нулей и единиц длины j по следующему правилу
где – элементарный код длины s. Тогда различным представлениям числа j будут соответствовать различные кодовые слова, поскольку код является разделимым. Таким образом,
и
. Используя предельный переход получим
при
. Теорема доказана.
Пример 3.4.1. Азбука Морзе – это схема алфавитного кодирования
Неравенство МакМиллана для азбуки Морзе не выполнено, поскольку
Следовательно, этот код не является разделимым, тем менее азбука Морзе успешно используется для передачи сообщений, которые однозначно декодируются получателем. Это возможно, поскольку на самом деле в азбуке Морзе имеются дополнительные элементы – паузы между буквами (и словами), которые позволяют декодировать сообщение. Эти дополнительные элементы определены неформально, поэтому прием и передача сообщений (особенно с высокой скоростью) является некоторым искусством, а не простой технической процедурой.