Коды и математика (рассказы о кодировании) - Аршинов М.Н.
Скачать (прямая ссылка):
21 ствуют разбиению получившихся групп снова на равновероятные подгруппы и т. д. Построение графа заканчивается, когда множество сообщений будет разбито на одноэлементные подмножества. Каждая концевая вершина графа, т. е. вершина, из которой уже не исходят ребра, соответствует некоторому кодовому слову. Чтобы указать это слово, надо пройти путь от корневой вершины до соответствующей концевой, выписывая в порядке следования по этому пути символы проходимых ребер. Например, вершине а3 на рис. 3 со-а вершине ав — слово 1110 (вер-кодовым словам, помечены на
Рис. 4.
ответствует слово 100 шины, соответствующие рисунке кружками).
Граф для рассмотренного выше примера представлен на рис. 4.
Получающиеся для кодов Фано графы всегда обладают тем свойством, что они не содержат замкнутых контуров. Такие графы называют деревьями (мы будем называть их, учитывая происхождение, кодовыми деревьями). Кодовые деревья можно строить не только для кодов Фано, но и для других кодов. Независимо от алгоритма кодирования каждому дереву соответствует определенное множество кодовых слов. Например, для кодового дерева, изображенного на рис. 3, имеем:
• G1=OO, а2=01, а8=100, а4=101, A5 = 110, Afl = I 1 10, A7=Illl.
Кодовое дерево может быть построено для кода с произвольным основанием d. Каждое его ребро помечается тогда
одним из d символов алфавита и из каждой вершины такого дерева исходит самое большее d различных ребер. Например, на рис. 5 представлено кодовое дерево для троичного кода со следующим множест вом кодовых слов: 0, 10, 11 120, 121,20,21, 220, 221, 222
Кодовые деревья дают удобное геометрическое представ ление для многих важных понятий и облегчают, как мы уви дим, решение различных задач, возникающих при построе НИИ экономных кодов.
Рис. 5.
22 Задачи в дополнения
1. Закодировать двоичным кодом Фано следующие множества сообщений:
а) семь сообщений с вероятностями
Pi=Pi= 1/4; р3=р4=рь= 1/8; р6=р7= 1/16;
б) десять сообщений с вероятностями
w = p2=o, 22; p3=p4=ps=pe=0.1; p7=p8=p9=pio=0,04.
Найти среднюю длину каждого из полученных кодов.
Выяснить, каков выигрыш по сравнению с равномерным кодированием.
2. Приведем пример троичного кодирования методом Фано для множества из 8 сообщений с вероятностями
pi=O, 3; P2=P3=Pi=OtIb', ръ= Po= р7=0,07; р8=0,04.
Таблица 10
Сооб - ІД єни я Вероятности Кодовые слова
A1 0,3 0 0
A2 0,15 0 10
A3 0,15 1 11
Ai 0,15 0 20
A1 0,07 0 210
As 0,07 2 1 211
A7 0,07 2 0 220
As 0,04 1 221
3. Закодировать троичным кодом Фано следующие множества сообщений:
а) 9 сообщений с вероятностями
1/3; 1/9; 1/9; 1/9; 1/9; 1/9; 1/27; 1/27; 1/27J
б) 10 сообщений с вероятностями
0,2; 0,15; 0,15; 0,1; 0,1; 0,1; 0,05; 0,05; 0,05; 0,05.
23 4. СВОЙСТВО ПРЕФИКСА, ИЛИ КУДА ИДТИ РОБОТУ
При использовании неравномерных кодо» приходится сталкиваться с одной проблемой, которую мы поясним на примере кодовой таблицы 9 предыдущего параграфа. На первый взгляд разумно было бы укоротить второе и третье кодовые слова, отбросив в них последний символ, так как при этом основное наше требование сохраняется: по-прежнему различные сообщения кодируются разными словами, как это видно из получившейся новой кодовой таблицы.
T а б л и ц a U
Ai A2 ^3 I Ai I
0 1 11 111
Но пусть, к примеру, данные сообщения — это команды) выдаваемые электронному роботу: A1 — идти прямо, A2 — повернуть назад, /I3 — свернуть влево, Ai — свернуть вправо. Предположим, что программа поведения робота задается следующей последовательностью:
A1 A3 A1 А4 A1 A2 A1 ... (1)
В результате кодирования эта последовательность преобразуется в такой двоичный текст:
01101110111 ... .
Легко вообразить себе, в какое недоумение привели бы мы робота, снабдив его подобной инструкцией. Куда же ему идти? Ясно, что сначала надо идти прямо. А дальше -свернуть влево или повернуть назад, потом еще раз назад? Впереди же еще большая путаница...
Естественно возразить, что следовало бы отделить одни кодовое слово от другого. Разумеется, это можно сделать, но лишь используя либо паузу между словами, либо специальный разделительный знак, для которого необходимо особое кодовое обозначение. И тот и другой путь приведет к значительному удлинению кодового текста, сводя на нет наше предыдущее «усовершенствование».
24 Другое дело, если мы будем пользоваться прежними кодовыми обозначениями для сообщений Ai. Тогда последовательность (I) будет закодирована так:
011001110101100 ... .
Здесь уже не может быть разночтений. Первое слово 0 — идти прямо, второе слово 110 — свернуть влево, так как в списке кодовых слов не значатся слова 1 и 11. В этом сплошном тексте одно за другим однозначно выделяются кодовые слова, и нет сомнений, что робот найдет правильную дорогу.
Итак, суть проблемы в том, что нужно уметь в любом кодовом тексте выделять отдельные кодовые слова без использования специальных разделительных знаков. Иначе говоря, мы хотим, чтобы код удовлетворял следующему требованию: всякая последовательность кодовых символов может быть единственным образом разбита на кодовые слова. Коды, для которых последнее требование выполнено, называются однозначно декодируемыми (иногда их называют кодами без запятой).
