Код Шеннона - Фано

Метод двоичной системы счисления

Этот метод используется для построения наиболее экономного двоичного кода. В деся-тичной системе счисления каждое число представляется в виде суммы степеней числа 10: k = a_k · 10^k + a_k−1 · 10^k−1 + : : : + a₀ · 10⁰, где числа a_k; : : : ; a₁; a₀ - цифры числа,

принимающие значения от 0 до 9. Число N при этом обозначается последовательностью своих цифр a_ka_k−1 : : : a₀. Аналогично этому число n можно представить в виде степе-ней числа 2: n = b_l · 10^l + : : : + b₀ · 10⁰, где числа b_l; : : : ; b₀ - цифры числа, принимаю-щие значения 0 и 1. Число n обозначается последовательностью соответствующих цифр (6 = 1 ∗ 2² + 1 ∗ 2¹ + 0 ∗ 2⁰). Аналогично можно представить число в виде суммы степеней числа m - т.н. m-ичная система счисления.

Число k цифр в десятичной системе для записи числа n удовлетворяет неравенству 10^k−1 6 n < 10^k. В промежутке между 10¹ и 10² − 1 все цифры будут двузначными, а в промежутке 10²::10³ − 1 - трёхзначными и.т.д. В двоичной системе счисления число k удовлетворяет неравенству 2^k−1 6 n < 2^k, значит, число 6 - трёхзначное, а число 9 - че-тырёхзначное. При добавлении к двоичной записи ведущих нулей, мы придём к равно-мерномудвоичному коду дляn-буквенного алфавита с минимальной длиной кодовогообозначения k.

Основной результат предыдущего параграфа : если число букв в алфавит равно n, а чис-ло используемых элементарных сигналов равно m, то при любом методе кодирования,

среднее число k элементарных сигналов, приходящихся на одну букву алфавита должно быть k > _log^log_mⁿ . (из неравенства 2^k−1 6 n < 2^k ⇒ log n < k · log m).

На самом деле, результаты предыдущих параграфов могут быть значительно улучшены, если воспользоваться введённым понятием энтропии и учесть статистические свойства реальных сообщений. Рассмотрим далее простейший случай сообщений, записанных

при помощи некоторых n букв нашего алфавита, частоты появления которых на любом

∑

месте сообщения характеризуются вероятностями p₁; : : : ; p_n, причём p_n = 1. Вероят-

n

ность p_i появления i-й буквы на любом месте сообщения принимается одной и той же вне зависимости от того, какие буквы стояли на всех предыдущих местах. Последовательные буквы сообщения предполагаются независимыми друг от друга.

Будем далее рассматривать только двоичные коды с элементарными сигналами 0 и 1. Среднее число k двоичных элементарных сигналов, приходящихся в закодированном сообщении на 1 букву исходного сообщения должно быть больше числа энтропии H : (k > H = −p₁ log p₁ − p₂ log p₂ − : : : − p_n log p_n), где H - энтропия опыта, состояще-го в распознавании одной буквы текста (энтропии одной буквы). Отсюда сразу следует, что при любом методе кодирования, для записи сообщения из M букв не меньше MH элементарных сигналов.

Если вероятности p1; : : : ; p_n - не все равны между собой, тогда H < log n = H( ₀), по-этому учёт статистических закономерностей сообщения может позволить построить код более экономный, чем наилучший равномерный код, требующий M ·log n двоичных зна-ков для записи текста из M букв.

Код Шеннона - Фано

Для получения наиболее экономного кода удобно начать с того, чтобы расположить все n букв алфавита в один столбец в порядке убывания вероятностей.Затем все эти буквыследует разбить на 2 группы: верхнюю и нижнюю, так, чтобы суммарные вероятности для буквы сообщения принадлежать каждой из этих групп были возможно более близки одна к другой. Для букв первой группы в качестве первой цифры кодового обозначения используется 1, для букв второй группы - 0.

Далее, каждую из 2 полученных групп снова надо разделить на 2 части с возможно бо-лее близкой суммарной вероятностью. В качестве второй цифры кодового обозначения используют 1 или 0 в зависимости, принадлежит ли наша буква к первой или ко второй подгруппе. Процесс повторяется до тех пор, пока мы не придём к группам, каждая из ко-торых не содержит по одной букве. Такой метод кодирования сообщений был впервые предложен в 1948-49 гг. независимо друг от друга Р.Фано, К.Шенноном.

ПримерПустьn= 6(алфавит из6букв),вероятности которых равны соответственно

0:4; 0:2; 0:2; 0:1; 0:05; 0:05:

На первом этапе деления на группы отщепим одну первую букву, оставив во второй груп-пе все остальные. Далее, вторая буква составит первую подгруппу второй группы …

Выводы: Основной принцип, положенный в основу кодирования по методу Шеннона - Фано заключается в том, что при выборе каждой цифры кодового обозначения мы ста-раемся, чтобы содержащееся в ней количество информации было наибольшим, т.е. что-бы независимо от значения всех предыдущих цифр эта цифра принимала оба возмож-ных для неё значений 0 и 1 о возможности с одинаковой вероятностью. Существенно, что буква, имеющая большую вероятность в коде Шеннона - Фано соответствуют бо-лее короткие кодовые обозначения (эти буквы быстрее оказываются выделенными в отдельную группу. В результате среднее значение k длины такого кодового обозначе-ния оказывается только немногим большим минимального значения H, допускаемого со-ображениями сохранения количества информации при кодировании. Так, для рассмот-ренного выше примера шестибуквенного алфавита наилучший равномерный код состо-ит из трёхзначных кодовых обозначений (т.к. 2² 6 6 < 2³), поэтому в нём на каж-дую букву приходится ровно 3 элементарных сигнала. При использовании кода Шенно-

на - Фано среднее число k элементарных сигналов, приходящихся на одну буку равно

∑

M = L · принимаемые значения вероятности= 1 ∗ 0:4 + 2 ∗ 0:2 + 3 ∗ 0:2 + 4 ∗ 0:1 + 5 ∗ (0:05 + 0:05) = 2:3. Это значение заметно меньше, чем 3, но не очень сильно отличается от энтропии H = −0:4 log 0:4 − 2 ∗ 0:2 log 0:2 − 0:1 log 0:1 − 2 ∗ 0:05 log 0:05 ≈ 2:22: