Коды и математика (рассказы о кодировании) - Аршинов М.Н.
Скачать (прямая ссылка):
Так, если заданы четыре сообщения A1, A2, A3, Ai с вероятностями P (A!) = 1/2, P (А 2) = 1/4, P (A3)=P (Ai)-= = 1/8, то это означает, что среди, например, 1 ООО переданных сообщений около 500 раз появляется сообщение A1, около 250 — сообщение А 2 и примерно по 125 раз — каждое из сообщений A3 и A4.
18 Эти сообщения нетрудно закодировать двоичными словами длины 2, например так, как показано в следующей таблице:
Таблица 7
Ai A2 I A3 Л4
00 01 J 10 11
Однако при таком кодировании вероятность появления сообщений никак не учитывается. Поступим теперь иначе. Разобьем сообщения на две равновероятные группы: в первую попадает сообщение Ail во вторую — сообщения Аг, A3, Ai. Сопоставим первой группе символ 0, второй — символ 1 (см. таблицу 8; во второй графе таблицы указаны вероятности сообщений).
Таблица 8
A1 V2 0
A2 1U 0
A3 V8 1 і 0
Ai Ve і
Это вполне в духе принципа, применявшегося в задаче с угадыванием. Действительно, символ 0 соответствует ответу «да» на вопрос «принадлежит ли сообщение первой группе?», а 1 — ответу «нет». Разница лишь в том, что раньше все множество разбивалось на две группы с одинаковым числом элементов, теперь же в первой группе один, а во второй — три элемента. Но, как и раньше, разбиение это таково, что оба ответа «да» и «нет» равновозможны. Продолжая в том же духе, разобьем множество сообщений A2, A3, Ai снова на две равновероятные группы. Первой, состоящей из одного сообщения А г, сопоставим символ 0, а второй, в которую входят сообщения A3 и Ai,— символ 1. Наконец оставшуюся группу из двух сообщений разобьем на две группы, содержащие соответственно сообщения A3 и A1,
19 сопоставив первой из них 0, а второй — символ 1. Сообщение A1 образовало «самостоятельную» группу на первом шаге, ему был сопоставлен символ 0, слово 0 и будем считать кодом этого сообщения. Сообщение A2 образовало самостоятельную группу за два шага, на первом шаге ему сопоставлялся символ 1, на втором — 0; поэтому будем кодировать сообщение A2 словом 10. Аналогично, для A3 и A1 выбираем соответственно коды 110 и 111. В итоге получается следующая кодовая таблица: Таблица 9
A1 A2 A3 Л4
і 0 і 10 I 110 J 111
Указанный здесь способ кодирования был предложен американским математиком Фано. Оценим тот выигрыш, который дает в нашем случае код Фано по сравнению с равномерным кодом, когда все сообщения кодируются словами длины 2. Представим себе, что нужно передать в общей сложности 1000 сообщений. При использовании равномерного кода на их передачу потребуется 2000 двоичных символов.
Пусть теперь используется код Фано. Вспомним, что из 1000 сообщений примерно 500 раз появляется сообщение A1, которое кодируется всего одним символом (на это уйдет 500 символов), 250 раз — сообщение A3, кодируемое двумя символами (еще 500 символов), примерно по 125 раз — сообщения А з и Ai с кодами длины 3 (еще 3 X 125+3 х 125= =750 символов). Всего придется передать примерно 1750 символов. В итоге мы экономим восьмую часть того времени, которое требуется для передачи сообщений равномер» ным кодом. В других случаях экономия от применения кода Фано может оказаться еще значительнее.
Уже этот пример показывает, что показателем экономности или эффективности неравномерного кода являются не длины отдельных кодовых слов, а «средняя» их длина L определяемая равенством:
N
I=IihP(Ai),
1=1
где Ii — длина кодового обозначения для сообщения Ац P(Ai) — вероятность сообщения Ai, N — общее число со« общений.
20 Наиболее экономным оказывается код с наименьшей средней длиной L В примере для кода Фано T= 1 X 0,5+2 X 0,25+3 X 2 X 0,125= 1,75,
в то время как для равномерного кода средняя длина 7=2 (она совпадает с общей длиной кодовых слов).
Нетрудно описать общую схему метода Фано. Располагаем N сообщений в порядке убывания их вероятностей: P (Л i)^P (A2)^. . .^P(An). Далее разбиваем множество сообщений на две группы так, чтобы суммарные вероятности сообщений каждой из групп были как можно более близки друг к другу. Сообщениям из одной группы в качестве первого символа кодового слова приписывается символ 0, сообщениям из другой — символ 1. По тому же принципу каждая из полученных групп снова разбивается на две части, и это разбиение определяет значение второго символа кодового слова. Процедура продолжается до тех пор,.пока все множество не будет разбито на отдельные сообщения. В результате каждому из сообщений будет сопоставлено кодовое слово из нулей и единиц.
Понятно, что чем более вероятно сообщение, тем быстрее оно образует «самостоятельную» группу и тем более коротким словом оно будет закодировано. Это обстоятельство и обеспечивает высокую экономность кода Фано.
Описанный метод кодирования можно применять и в случае произвольного алфавита из d символов с той лишь разницей, что на каждом шаге следует производить разбиение па d равновероятных групп.
Алгоритм кодирования Фано имеет очень простую графическую иллюстрацию в виде множества точек (вершин) на плоскости, соединенных отрезками (ребрами) по определенному правилу (такие фигуры в математике называют графами). Граф для кода Фано строится следующим образом (см. рис. 3). Из нижней (корневой) вершины графа исходят два ребра, одно из которых помечено символом 0, другое —символом 1. Эти два ребра соответствуют разбиению множества сообщений на две равновероятныег руппы, одной из которых сопоставляется символ 0, а другой — символ 1. Ребра, исходящие из вершин следующего «этажа», соответ-
