Код ФАНО — экономный код

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

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

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

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

Так, если заданы четыре сообщения А_и А_е, А₃, А₄ с вероятностями Р{А_Х)=1/2, Я(у4₂)=1/4, Р(А₃)=Р = 1/8, то это означает, что среди, например, 1 ООО передан­ных сообщений около 500 раз появляется сообщение А_1г около 250 — сообщение А _г и примерно по 125 раз — каж­дое из сообщений А _а и А₄.

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

Таблица 7

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

Таблица 8

Это вполне в духе принципа, применявшегося в задаче с' угадыванием. Действительно, символ 0 соответствует отве­ту «да» на вопрос «принадлежит ли сообщение первой группе?», а I — ответу «нет». Разница лишь в том, что рань­ше все множество разбивалось на две группы с одинаковым числом элементов, теперь же в первой группе один, а во второй — три элемента. Но, как и раньше, разбиение это таково, что оба ответа «да» и «нет» равновозможны. Продол­жая в том же духе, разобьем множество сообщений А 2, A_it А₄ снова на две равновероятные группы. Первой, состоя­щей из одного сообщения A i, сопоставим символ 0, а второй, в которую входят сообщения А_д и A_it— символ 1. Наконец оставшуюся группу из двух сообщений разобьем на две группы, содержащие соответственно сообщения А_в и A_if сопоставив первой из них 0, а второй — символ 1. Сообще, ннг A_t образовало «самостоятельную» группу па первое шаге, ему был сопоставлен символ 0, слово 0 и будем счц. тать кодом этого сообщения. Сообщение А₂ образовало са. мостоятельную группу за два шага, на первом шаге ему со. поставлялся символ I, на втором — 0; поэтому будем коди. ровать сообщение А₂ словом 10. Аналогично, для A_s и выбираем соответственно коды 110 и 111. В итоге получает* ся следующая кодовая таблица: Таблица 9

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

Пусть теперь используется код Фано. Вспомним, что № 1000 сообщений примерно 500 раз появляется сообщение Ai которое кодируется всего одним символом (на это уйдет 50( символов), 250 раз — сообщение А₂, кодируемое двуш символами (еще 500 символов), примерно по 125 раз - сообщения А₃ и А₄ с кодами длины 3 (еще Зх 125+3 х 125^ *=750 символов). Всего придется передать примерно 17о< символов. В итоге мы экономим восьмую часть того време ни, которое требуется для передачи сообщений равномер ным кодом. В других случаях экономия от применения код! Фано может оказаться еще значительнее.

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

где l_t — длина кодового обозначения для сообщения 4t\ ^(^i) — вероятность сообщения A_t, N — общее число col общений.

Наиболее экономным оказывается код с наимень­шей средней длиной /. В примере для кода Фано

в то время как для равномерного кода средняя длина /=2 (она совпадает с общей длиной кодовых слов).

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

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

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

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

Граф для рассмотренного выше примера представлен на рис. 4.

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

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

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

Предлагаю ознакомиться с аналогичными статьями: