Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Удобное графическое представление множества кодовых слов, удовлетворяющих свойству префикса, можно получить, представляя каждое кодовое слово концевым узлом на дереве. Дерево, представляющее кодовые слова кода III рис. 2.3.1, показано на рис. 3.2.2. Начиная с основания дерева, два ребра, ведущие к узлам первого порядка, соответствуют выбору между 0 и 1, рассматриваемым в качестве первой буквы кодовых слов. Подобно этому два ребра, исходящие из правого узла первого порядка, соответствуют выбору между 0 и 1 для второй буквы кодового слова, если первая буква была 1; такое же представление применимо и для других ребер. Последовательность символов каждого кодового слова можно рассматривать как правило восхождения от основания дерева к концевому узлу, представляющему желае-62
мую букву источника. Дерево можно также использовать для представления кодовых слов кода, который не обладает свойством префикса, однако в этом случае некоторые промежуточные узлы дерева будут соответствовать кодовым словам.
Обратим теперь наше внимание на задачу выбора кода, обладающего свойством префикса, так чтобы минимизировать п. В начале приведем эвристическое рассмотрение этой задачи, затем докажем некоторые общие теоремы относительно длин кодовых слов и, наконец, дадим алгоритм построения кода, который минимизирует п.
Для префиксного кода приемник можно представить себе как устройство, наблюдающее последовательность кодовых букв и прослеживающее их путь вверх по дереву, как изображено рис. 3.2.2, чтобы
Рис. 3.2,2. Представление в виде дерева кодовых слов кода III, изображенного
на рис. 3.2.1.
декодировать сообщение источника. В каждом узле этого дерева следующий кодовый символ дает информацию о том, какое нужно взять ребро. Можно заметить, что сумма взаимных информаций в последовательных узлах, ведущих к некоторому данному концевому узлу, равна в точности собственной информации символа источника, соответствующего этому узлу. Таким образом, чтобы достичь малого значения п, следует достичь большого значения средней взаимной информации во всех промежуточных узлах дерева. Это в свою очередь говорит о том, что нужно попытаться выбрать кодовые слова таким образом, чтобы все ребра, исходящие из узла, в соответствующем дереве, были равновероятными. Сопоставляя дерево рис. 3.2.2 с вероятностями букв источника для кода III рис. 3.2.1, можно заметить, что каждое ребро дерева берется с вероятностью 1/2. Для этого примера п = 1,75 и Я (U) = 1,75. В длинной последовательности L букв источника значение п с большой вероятностью близко к числу кодовых букв на одну букву источника. Следовательно, если бы существовал код с п<.Н (U), можно было бы при больших L закодировать большинство последовательностей источника длины L с помощью меньше чем Я (U) кодовых букв на одну букву источника, в нарушение теоремы 3.1.1. Это означает, что 1,75 является минимальной возможной величиной п для этого кода. Это не удивительно, так как мы смогли построить код так, что каждая кодовая буква содержит в точности 1 бит информации о выходе источника.
110
fit
— Узлы третьего порядка.
—- Узлы второго порядка.
63
Этот пример дает возможность произвести очевидное обобщение, позволяющее построить префиксные коды для общего множества букв источника. Разобьем вначале множество букв на D подмножеств так, чтобы вероятность каждого подмножества была по возможности наиболее близкой к 1 ID. Припишем различные начальные кодовые буквы каждому из этих подмножеств. Затем разобьем вновь каждое подмножество на D приближенно равновероятных групп и припишем вторую букву, соответствующую этому разделению. Продолжим этот процесс до тех пор, пока каждая группа не будет содержать только одну букву источника. Полученный в результате код удовлетворяет, очевидно, свойству префикса. Эта процедура не обязательно минимизирует п, так как достижение большого значения средней собственной информации на одной кодовой букве может привести к обедненному выбору для последующих кодовых букв. Заметим, что если это разбиение может быть выполнено так, что группы будут в точности равновероятными на каждом этапе, то вероятности букв источника и длины кодовых слов будут связаны равенством
P(ah) = D-nK (3.2.2)
До того как обратиться к деталям процедуры минимизации средней длины множества кодовых слов, исследуем ограничения на длины кодовых слов префиксного кода.
Теорема 3.2.1. [Неравенство Крафта (1949)]. Если целые числа пи пг, ..., пц удовлетворяют неравенству
к
2 1, (3.2.3)
k= I
то существует код, обладающий свойством префикса, с алфавитом объема/), длины кодовых слов в котором равны этим числам. Обратно, длины кодовых слов любого кода, обладающего свойством префикса, удовлетворяют неравенству (3.2.3). (Замечание. Теорема не утверждает, что любой код с длинами кодовых слов, удовлетворяющими (3.2.3), является префиксным. Так, например, множество двоичных кодовых слов 0, 00, 11 удовлетворяет (3.2.3), но не обладает свойством префикса. Теорема утверждает, что существует некоторый префиксный код с такими длинами, например, 0, 10 и 11).
