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

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

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

Таблица 2.2

Ясно, что при обычном кодировании (не учитывающем статистических характеристик) для представления каждой буквы требуется три символа, т.к. 2³=8.

Среднее число разрядов на одну букву (2.6)

где - число разрядов в кодовой комбинации, соответствующей букве z_i.

Рассмотренная методика не всегда приводит к однозначному построению кода. Ведь при разбиении на подгруппы можно сделать большей по вероятности как верхнюю так и нижнюю подгруппы. Множество вероятностей в предыдущей таблице можно было разбить иначе. При этом среднее число разрядов на одну букву кардинально не изменится. Построенный код может оказаться не самым лучшим. При построении эффективных кодов с основанием q>2 неопределенность возрастает.

От указанного недостатка свободна методика Д. Хаффмена.