Коды и математика (рассказы о кодировании) - Аршинов М.Н.
Скачать (прямая ссылка):
Наиболее простыми и употребимыми кодами без запятой являются так называемые префиксные коды, обладающие тем ствойством, что никакое кодовое слово не является началом (префиксом) другого кодового слова. Если код префиксный, то, читая кодовую запись подряд от начала, мы всегда сможем разобраться, где кончается одно кодовое слово и начинается следующее. Если, например, в кодовой записи встретилось кодовое обозначение 110, то разночтений быть не может, так как в силу префиксности наш код не содержит кодовых обозначений 1, 11 или, скажем, 1101. <а Именно так обстояло дело для рассмотрен- ^ ного выше кода, который очевидно является префиксным. Рис. 6.
Нетрудно понять, как отражается свойство префиксности или его отсутствие на кодовом дереве. На рис. 6 представлено дерево для кода из таблицы 11 (кружками, как и раньше, помечены те вершины, которые соответствуют кодовым словам). Таким образом, если свойство префикса не выполняется, то некоторые промежуточные вершины дерева могут соответствовать кодовым словам. Для кода Фано это невозможно, так как по самому алгоритму кодирования построение кодового слова заканчивается одновременно с достижением концевой вершины. Следовательно, код Фано является префиксным кодом.
25 Задачи и дополнений
1. Префиксный код называют полным, если добавление к нему любого нового кодового слова (в данном алфавите) нарушает свойство префиксности. Убедиться, что двоичные коды, деревья которых изображены на рис. 3, 4, являются полными.
На рис. 7 представлено кодовое дерево префиксного, но неполного двоичного кода. Действительно, добавив к кодовым словам 0, 10, 111 слово 110, получим снова префиксный код.
2. Доказать, что двоичный код Фано является полным кодом. Верно ли аналогичное утверждение для кода Фано с произвольным основанием?
3. Проанализировав задачи 1 и 2, сформулировать необходимое и достаточное условие, которому должно удовлетворять кодовое дерево полного префиксного кода, и доказать его необходимость и достаточность.
4. Используя кодовое дерево, доказать, что всякий префиксный код может быть расширен до полного кода добавлением к нему некоторого множества кодовых слоз.
5. Пусть k — максимальное значение длин кодовых слоз префиксного кода. Показать, что число кодовых слов не превосходит величины 2к в случае двоичного кода и величины dk в случае кода с произвольным основанием d. При каких условиях достигается равенство?
6. Код, представленный на рис. 7, можно сделать более экономным, отбрасывая в слове 111 последний символ. При этом свойство префиксности не нарушится. Подобная операция, состоящая в том, что каждое
Рис. 7, Рис. 8.
слово префиксного кода заменяется наименьшим его началом, не явля« гещимся началом других кодовых слов, называется усечением. Очевидно, что в результате усечения получается префиксный код и при этом более экономный, чем исходный. Возникают такие два вопроса:
1. Возможно ли усечение полного кода?
2. Можно ли утверждать, что в результате усечения получается полный код?
7. На рис. 8,а представлено кодовое дерево префиксного кода, для которого усечение невозможно. В то же время мы получим более экономный префиксный код (рис. 8, б), если в словах 110 и 111 вычеркнем второй символ 1.
Справедливо следующее утверждение: префиксный код является полным тогда и только тогда, когда его невозможно сократить (т. е. вычеркнуть хотя бы один знак в любом из кодовых слов), не нарушив свойства префикса.
8. Любопытно рассмотреть примеры однозначно декодируемых кодов, не обладающих свойством префикса. Пожалуй, простейшим примером такого рода является двоичный код (1, 10}. Ясно, что в любой кодовой последовательности, составленной из этих слов, всякое появле-
26 ниє символа 1 означает начало нового кодового слова. Последнее остается справедливым для кода, каждое слово которого есть единица с последующими нулями. Разумеется, подобные коды далеко не самые экономные.
Приведем менее тривиальный пример однозначно декодируемого кода: {01, 10, 011}. Рекомендуем читателю указать алгоритм однозначного выделения кодовых слов из кодовой последовательности для этого кода.
9. Как узнать, является ли произвольный код однозначно декодируемым? Для этого можно предложить следующий способ. Возьмем всевозможные пары кодовых слов, в которых одно слово является префиксом другого. Для каждой такой пары найдем «повисший» суффикс, который остается после удаления префиксного слова из начальной части более длинного слова. Например, повисший суффикс для пары 10 и 10010 есть 010. Выпишем все повисшие суффиксы. Далее проделаем то же самое для каждой пары слов, состоящей из повисшего суффикса и кодового слова, в которой одно слово является префиксом другого. Выпишем все новые повисшие суффиксы, которые при этом получатся. Будем продолжать этот процесс до тех пор, пока будут появляться новые суффиксы. Код является однозначно декодируемым тогда и только тогда, когда никакой суффикс не совпадет ни с одним кодовым словом.
10. Выяснить, обладают ли свойством однозначной декодируемое™ следующие коды:
