3. КОД ФАНО — ЭКОНОМНЫЙ код

Алфавита из двух (а подавно — из большего] числа) символов, как мы убедились в § 1, достаточно для кодирования любого множества сообщений. Устанавливая этот факт, мы кодировали все сообщения словами одинако­вой длины, что, однако, далеко не всегда бывает выгодно.

Представим себе, что одни сообщения приходится пере-| давать довольно часто, другие — редко, третьи — совсем в исключительных случаях. Понятно, что первые лучше за­кодировать тогда короткими словами, оставив более длин­ные слова для кодирования сообщений, появляющихся ре­же. В результате кодовый текст станет в среднем короче, и на его передачу потребуется меньше времени.

Впервые эта простая идея была реализована упоминав­шимся нами американским инженером Морзе в предложен­ном им коде. Рассказывают, что создавая свой код, Морзе отправился в ближайшую типографию и подсчитал число литер в наборных кассах. Буквам и знакам, для которых литер в этих кассах было припасено больше, он сопоставил более короткие кодовые обозначения (ведь эти буквы встре­чаются чаще). Так, например, в русском варианте азбуки Морзе буква «е» передается одной точкой, а редко встречаю­щаяся буква «ц» — набором из четырех символов.

В математике мерой частоты появления того или иного события является его вероятность. Вероятность события А обозначают обычно символом Р (А) или просто буквой Р. Не останавливаясь на определении вероятности, заметим только, что вероятность некоторого события (сообщения) можно представлять себе как долю тех случаев, в которых оно появляется, от общего числа появившихся событий (сообщени I).

Так, если заданы четыре сообщения Лх, Л2, Ая, А4 с вероятностями Р(Лх)=1/2, Р(А2)=1/4, Р(А3)=Р(А<) ■=1/8, то это означает, что среди, например, 1 ООО передан­ных сообщений около 500 раз появляется сообщение Аи около 250 — сообщение А2 и примерно по 125 раз — каж­дое из сообщений Ая и Л4.

Эти сообщения нетрудно закодировать двоичными сло­вами длины 2, например так, как показано в следующей таблице:

Однако при таком кодировании вероятность появления сооб­щений никак не учитывается. Поступим теперь иначе. Разо­бьем сообщения на две равновероятные группы: в первую попадает сообщение Аво вторую — сообщения А$, А 3, А1. Сопоставим первой группе символ 0, второй — символ I (см. таблицу 8; во второй графе таблицы указаны вероятности сообщений).

Это вполне в духе принципа, применявшегося в задаче с' угадыванием. Действительно, символ 0 соответствует отве­ту «да» на вопрос «принадлежит ли сообщение первой группе?», а 1 — ответу «нет». Разница лишь в том, что рань­ше все множество разбивалось на две группы с одинаковым числом элементов, теперь же в первой группе один, а во второй — три элемента. Но, как и раньше, разбиение это таково, что оба ответа «да» и «нет» равновозможны. Продол­жая в том же духе, разобьем множество сообщений А А3, А4 снова на две равновероятные группы. Первой, состоя­щей из одного сообщения А 2, сопоставим символ 0, а второй, в которую входят сообщения А3 и Ац,— символ 1. Наконец оставшуюся группу из двух сообщений разобьем на две группы, содержащие соответственно сообщения А„ и Л4,

сопоставив первой из них 0, а второй — символ 1. Сообще ни'г Лх образовало «самостоятельную» группу на первол шаге, ему был сопоставлен символ 0, слово 0 и будем счи тать кодом этого сообщения. Сообщение А2 образовало са мостоятельную группу за два шага, на первом шаге ему со поставлялся символ I, на втором — 0; поэтому будем коди ровать сообщение Аг словом 10. Аналогично, для А3 и .1 выбираем соответственно коды 110 и 111. В итоге получает ся следующая кодовая таблица:

Указанный здесь способ кодирования был предложе! американским математиком Фано. Оценим тот выигрыл который дает в нашем случае код Фано по сравнению с рав­номерным кодом, когда все сообщения кодируются слова Л1 длины 2. Представим себе, что нужно передать в общей слсж ности 1000 сообщений. При использовании равномерного кода на их передачу потребуется 2000 двоичных символов

Пусть теперь используется код Фано. Вспомним, что и: 1000 сообщений примерно 500 раз появляется сообщение А1 которое кодируется всего одним символом (на это уйдет 50 символов), 250 раз — сообщение А2, кодируемое двум] символами (еще 500 символов), примерно по 125 раз - сообщения А3 и А4 с кодами длины 3 (еще Зх 125+3 X 125^ =750 символов). Всего придется передать примерно 175* символов. В итоге мы экономим восьмую часть того време ни, которое требуется для передачи сообщений равномер­ным кодом. В других случаях экономия от применения код Фано может оказаться еще значительнее.

 

где 1г—длина кодового обозначения для сообщения 4/ вероятность сообщения А ^, N — общее число со!

общений.

Уже этот пример показывает, что показателем эконом ности или эффективности неравномерного кода являются не длины отдельных кодовых слов, а «средняя» их длина определяемая равенством:

Наиболее экономным оказывается код с наимень­шей средней длиной I. В примере для кода Фано в то время как для равномерного кода средняя длина 1=2 (она совпадает с общей длиной кодовых слов).

Нетрудно описать общую схему метода Фано. Распола­гаем N сообщений в порядке убывания их вероятностей: Р {А^Т^Р   • ■^Р(Ах). Далее разбиваем множество

сообщений на две группы так, чтобы суммарные вероятно­сти сообщений каждой из групп были как можно более близки друг к другу. Сообщениям из одной группы в каче­стве первого символа кодового слова приписывается сим­вол 0, сообщениям из другой — символ 1. По тому же прин­ципу каждая из полученных групп снова разбивается на две части, и это разбиение определяет значение второго символа кодового слова. Процедура продолжается до тех пор, пока все множество не будет разбито на отдельные сообщения. В результате каждому из сообщений будет сопоставлено кодовое слово из нулей и единиц.

Понятно, что чем более вероятно сообщение, тем быстрее оно образует «самостоятельную» группу и тем более корот­ким словом оно будет закодировано. Это обстоятельство и обеспечивает высокую экономность кода Фано.

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

 

Алгоритм кодирования Фано имеет очень простую гра­фическую иллюстрацию в виде множества точек (вершин) на плоскости, соединенных отрезками (ребрами) по опре­деленному правилу (такие фи­гуры в математике называют графами). Граф для кода Фа­но строится следующим обра­зом (см. рис. 3). Из нижней (корневой) вершины графа ис­ходят два ребра, одно из кото­рых помечено символом 0, дру­гое —символом 1. Эти два реб­ра соответствуют разбиению множества сообщений на две равновероятныег руппы, одной из которых сопоставляется символ 0, а другой — символ 1. Ребра, исходящие из вершин следующего «этажа», соответ­ствуют разбиению получившихся групп снова на равнове­роятные подгруппы и т. д. Построение графа заканчивается, когда множество сообщений будет разбито на одноэлемент­

ные подмножества. Каждая конце­вая вершина графа, т. е. верши­на, из которой уже не исходят ребра, соответствует некоторо­му кодовому слову. Чтобы ука­зать это слово, надо пройти путь от корневой вершины до соответст­вующей концевой, выписывая в по­рядке следования по этому пути символы проходимых ребер. На­пример, вершине а3 на рис. 3 соответствует слово 100, а вершине ав— слово 1110 (вер­шины, соответствующие кодовым словам, помечены на рисунке кружками).

 

Кодовое дерево может быть построено для кода с произ­вольным основанием й. Каждое его ребро помечается тогда

Получающиеся для кодов Фано графы всегда обладают тем свойством, что они не содержат замкнутых контуров. Такие графы называют деревьями (мы будем называть их, учитывая происхождение, кодовыми деревьями). Кодовые деревья можно строить не только для кодов Фано, но и для других кодов. Независимо от алгоритма кодирования каж­дому дереву соответствует определенное множество кодовых слов. Например, для кодового дерева, изображенного на рис. 3, имеем:

одним из а символов алфавита и из каждой вершины такого дерева исходит самое большее й различных ребер. Напри­мер, на рис. 5 представлено кодовое дерево для троичного кода со следующим множест­вом кодовых слов: 0, 10, 11, 120, 121,20,21, 220, 221, 222.

Кодовые деревья дают удобное геометрическое представ­ление для многих важных понятий и облегчают, как мы уви­дим, решение различных задач, возникающих при построе­нии экономных кодов.

Задачи и дополнения

I. Закодировать двоичным кодом Фано следующие мно­жества сообщений;

а) семь сообщений с вероятностями

 

 

 

 

 б) десять сообщений с вероятностями

 

 

 

 

 Найти среднюю длину каждого из полученных кодов. Выяснить, каков выигрыш по сравнению с равномерным кодирова­нием.

2. Приведем пример троичного кодирования методом Фаио для множества из 8 сообщений с вероятностями

 

Закодировать троичным кодом Фано следующие множества сооб­щений:

а)         9 сообщений с вероятностями

1/3; 1/9; 1/9; 1/9; 1/9; 1/9; 1/27; 1/27; 1/27;

б)         10 сообщений с вероятностями

0,2; 0,15; 0,15; 0,1; 0,1; 0,1; 0,05; 0,05; 0,05; 0,05.