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

Алгоритм Шеннона-Фано заключается в следующем.

1. Символы алфавита источника записываются в порядке не возрас­тающих вероятностей.

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

3. Затем каждая из этих частей (если она содержит более одного символа) делится в свою очередь на две, по возможности равновероятные части и к ним применяется то же самое правило кодирования.

4. Этот процесс повторя­ется до тех пор, пока в каждой из полученных частей не останется по одному сообщению.

Пример. Пусть алфавит А источника состоит из 8 символов А, Б, В, Г, Д, Е, Ж, З с ве­роятностями р (А) = 0,6; р (Б) = 0,2; р (В) = 0,1; р (Г) = 0,04; р (Д)=0,025; р (Е) = 0,015, р (Ж)=0,01; р (З) = 0,01. Про­цедура построения неравномерного кода Шеннона-Фано задается в таблице 8.9.

Таблица 8.9. Про­цедура построения неравномерного кода Шеннона-Фано

Буква	рi	I	II	III	IV	V	VI	Kод	mi	mi × pi
А	0.6									0.6
Б	0.2									0.6
В	0.1							0.3
Г	0.04								0.12
Д	0.025							0.1
Е	0.015						0.075
Ж	0.01					0.06
З	0.01				0.06

На первом этапе производится деление на два множества А, и Б, В, Г, Д, Е, Ж, З, так как вероятность р(А)=0,6 и сумма вероятностей

примерно одинаковы. При этом символу А присваивается «1», а всем остальным Б, В, Г, Д, Е, Ж, З присваивается «0».

На втором этапе производится деление второго множества на два множества Б, В, и Г, Д, Е, Ж, З. Множеству Б, В присваивается «1», а множеству Г, Д, Е, Ж, З присваивается «0».

Hа третьем этапе производится деление множества Б, В, на два множества (уже символа) Б и В. Символу Б присваивается «1», а символу Вприсваивается «0». Множество Г, Д, Е, Ж, З делится на множества Г и Д, Е, Ж, З. Символу Г присваивается «1», а множеству Д, Е, Ж, З присваивается «0».

На четвёртом этапе производится деление множества Д, Е, Ж, З на два множества Д и Е, Ж, З. Символу Д присваивается «1», а множеству Е, Ж, З присваивается «0».

На пятом этапе производится деление множества Е, Ж, З на два множества Е и Ж, З. Символу Е присваивается «1», а множеству Ж, З присваивается «0».

На шестом этапе производится деление множества Ж, З на два множества Ж и З. Символу Ж присваивается «1», а символу З присваивается «0».

Легко проверить, что данный код оказывается префиксным и средняя длина кодовой комбинации 1,915, что менее чем на 7 % превышает энтропию данного источника, равную 1,7813. A избыточность кода составит

.

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