Метод Шеннона-Фано

Практические методы оптимального кодирования

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

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

В специальную таблицу (см. ниже) справа колонкой выписывают состояния кодируемого источника информации в порядке убывания вероятностей их реализации. Эти вероятности указываются в следующей колонке таблицы.

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

Рабочая таблица кодирования источника

Состояние	Вероятность	Кодовое слово Первый вариант…… Второй вариант разбиения
S1	0,22	11 11
S2	0,20	101 10
S3	0,16	100 011
S4	0,16	01 010
S5	0,10	001 001
S6	0,10	0001 0001
S7	0,04	00001 00001
S8	0,02	00000 00000

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

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

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

Процесс продолжается до тех пор, пока последняя пара событий- событий с самыми малыми вероятностями не поделят (на основе всё того же принципа) между собой ноль и единицу.

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

Энтропия источника находится по известному набору вероятностей его состояний, а средняя длинна кодового слова – как математическое ожидание на множестве получившихся в итоге кодовых слов.

В нашем примере энтропия Hs =2,76 бит, а среднее количество двоичных символов на кодируемое состояние источника – 2, 84 и 2, 80 (они будут в среднем на столько же бит пополнять количество информации в сообщениях) и для первого и второго разбиений, соответственно. Коды, как мы видим разные по оптимальности и оба не очень хорошие. Это результат приблизительности разбиения и неудобной неравномерности убывания вероятностей. И с этим ничего не поделаешь.

Дата добавления: 2015-06-27