Вопрос № 8. Исторически первый из методов кодирования источника, подтверждающих теорему 2.2.3, был предложен в 1948-49 гг

Код Шеннона – Фано.

 

Исторически первый из методов кодирования источника, подтверждающих теорему 2.2.3, был предложен в 1948-49 гг. независимо друг от друга Р.Фано и К.Шенноном. Основу построения кода Шеннона – Фано составляет процедура дихотомии, т.е. последовательного разбиения ансамбля на две части.

На первом шаге (итерации) множество X разбивается на два подмножества таким образом, чтобы суммарные вероятности каждого из них были по возможности одинаковыми и близкими к 0,5. При этом сообщениям из одного подмножества в качестве первого символа кодового слова присваивается нуль, а сообщениям из другого – единица.

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

Таблица 2.2

		Итерации
X	p (x)	I	II	III	IV	V	Код
x 1	0,50
x 2	0,20
x 3	0,05
x 4	0,15
x 5	0,04
x 6	0,03
x 7	0,02
x 8	0,01

 

Пример 2.3.1. Рассмотрим дискретный источник, генерирующий 8 сообщений с вероятностями, представленными в табл. 2.2. Видно, что процесс заканчивается после 5 итераций, причем варианты разбиений можно проследить по жирным разграничительным линиям и полутоновому фону. На первом шаге сообщение x ₁ сразу оказывается единственным элементом одного из подмножеств, поскольку его вероятность равна 0,5. Поэтому с присвоением x ₁ кодового символа 0 кодирование этого сообщения завершается. Естественно, первый символ всех кодовых слов, отображающих сообщения из второго подмножества, полагается равным 1. Разумеется, конкретное соответствие между упомянутыми символами и подмножествами сообщений несущественно, и с равным успехом можно приписать x ₁ символ 1, а остальным сообщениям – 0. Второе разбиение приводит к образованию двух подмножеств с равными суммарными вероятностями, первое из которых включает сообщения , а второе – все оставшиеся, т.е. . При этом в качестве второго кодового символа нуль приписывается словам первого из подмножеств, тогда как единица – словам второго. Дальнейшие действия ясны из таблицы и не нуждаются в комментарии.

Алгоритм Шеннона-Фано гарантирует соблюдение требования префиксности, так как каждое разбиение заканчивается присвоением разным подмножествам противоположных символов.

Обратимся теперь к границе (2.4) и сравним среднюю длину кодового слова с энтропией. Вычисления согласно (1.3) и (2.2) дают

и .

Из принципа построения кода Шеннона-Фано можно видеть, что сообщение, вероятность которого не ниже 1/2, будет закодировано на первом же шаге, сообщение с вероятностью между 1/4 и 1/2 – не позднее, чем на втором шаге и т.д. Таким образом, и средняя длина кода

.

Как видно, рассматриваемый код отвечает критерию экономности, установленному теоремой 2.2.3, доказывая тем самым справедливость последней. В то же время, алгоритм Шеннона-Фано не гарантирует построения наиболее экономного кода, уступая в этом смысле обсуждаемому ниже алгоритму Хаффмена.